第Ⅰ部分 运筹优化常见模型及建模技巧

第二章 运筹优化经典问题数学模型

P10 二部图

二部图（二分图）总结-CSDN博客

P15 Ford-Fulkerson算法

【最大流】Ford-Fulkerson算法——算法设计与分析-CSDN博客

福特-富尔克森算法 - 维基百科，自由的百科全书 (wikipedia.org)

Ford-Fulkerson算法 Python 源码

class Edge(object):
"""初始化边对象"""
    def __init__(self, u, v, w):
        self.source = u # 源节点
        self.sink = v  # 汇节点
        self.capacity = w # 边的容量
"""返回边的字符串表示"""
    def __repr__(self):
        return "%s->%s:%s" % (self.source, self.sink, self.capacity) # "source->sink:capacity"

class FlowNetwork(object):
"""初始化流网络对象"""
    def __init__(self):
        self.adj = {} # 邻接表
        self.flow = {} # 流量
 """向流网络添加节点"""
    def add_vertex(self, vertex):
        self.adj[vertex] = []
 """获取给定节点的出边列表"""
    def get_edges(self, v):
        return self.adj[v]
 """向网络中添加边和反向边"""
    def add_edge(self, u, v, w=0):
        if u == v:
            raise ValueError("u == v")
        edge = Edge(u,v,w) # 创建一条正向边
        redge = Edge(v,u,0) # 创建一条反向边
        edge.redge = redge  # 将正向边和反向边连接起来
        redge.redge = edge
        self.adj[u].append(edge) # 将正向边添加到节点u的邻接表中
        self.adj[v].append(redge) # 将反向边添加到节点v的邻接表中
        self.flow[edge] = 0 # 初始化网络流量为0
        self.flow[redge] = 0
 """寻找增广路径（深度优先搜索算法）"""
    def find_path(self, source, sink, path):
        if source == sink:
            return path
        for edge in self.get_edges(source): # 获取source节点的邻接边
            residual = edge.capacity - self.flow[edge]  # 计算残存网络
            if residual > 0 and edge not in path:
                result = self.find_path( edge.sink, sink, path + [edge]) 
                if result != None:
                    return result
"""迭代搜索增广路径（反向边也可以选择），直至无可用增广路径"""
    def max_flow(self, source, sink):
        path = self.find_path(source, sink, [])
        while path != None:
            residuals = [edge.capacity - self.flow[edge] for edge in path]
            flow = min(residuals) # 残存容量的最小值（可增加流量的最大值）
            """更新所选增广路径中的流量"""
            for edge in path:
                self.flow[edge] += flow # 正向边的流量增加
                self.flow[edge.redge] -= flow # 反向边的流量减小（缩减的流量减少）
            path = self.find_path(source, sink, [])
        return sum(self.flow[edge] for edge in self.get_edges(source)) # 总的流量

>>> g = FlowNetwork()
>>> [g.add_vertex(v) for v in "sopqrt"]
[None, None, None, None, None, None]
>>>
>>> g.add_edge('s','o',3)
>>> g.add_edge('s','p',3)
>>> g.add_edge('o','p',2)
>>> g.add_edge('o','q',3)
>>> g.add_edge('p','r',2)
>>> g.add_edge('r','t',3)
>>> g.add_edge('q','r',4)
>>> g.add_edge('q','t',2)
>>> print (g.max_flow('s','t'))
5

设施选址问题

 OM | 设施选址问题简介 - 知乎 (zhihu.com)

优化 | 五个经典设施选址模型的详解及其实践：Python调用Gurobi实现 - 知乎 (zhihu.com)

【Python】 gurobipy 学习笔记5——qiucksum函数_quicksum-CSDN博客

【Python】 gurobipy 学习笔记4——prod函数_gurobi prod-CSDN博客

Gurobipy求解速度慢

Gurobi 加速混合整数规划问题求解速度的建议 - 知乎 (zhihu.com)

分支定界法

【运筹学】-整数线性规划(一)(分支定界法)_哔哩哔哩_bilibili

干货 | 10分钟带你全面掌握branch and bound（分支定界）算法-概念篇 - 短短的路走走停停 - 博客园 (cnblogs.com)

分支定界法、割平面法、分支切割法

分支切割算法 - 知乎 (zhihu.com)

线性规划标准化

【线性规划2】线性规划的标准型 - 知乎 (zhihu.com)

单纯形法

【运筹学】单纯形法总结 ( 单纯形法原理 | 单纯形法流程 | 单纯形表 | 计算检验数 | 最优解判定 | 入基变量 | 出基变量 | 方程组同解变换 ) ★★★-CSDN博客

 史上最详细单纯形法—从理解到计算(带约束规划问题) - 知乎 (zhihu.com)

优化算法

【学界】智能优化算法--第四次工业革命的重要引擎 - 知乎 (zhihu.com)