Python⼩⽩的数学建模课-19.⽹络流优化问题
流在⽣活中⼗分常见，例如交通系统中的⼈流、车流、物流，供⽔管⽹中的⽔流，⾦融系统中的现⾦流，⽹络中的信息流。⽹络流优化问题是基本的⽹络优化问题，应⽤⾮常⼴泛。
⽹络流优化问题最重要的指标是边的成本和容量限制，既要考虑成本最低，⼜要满⾜容量限制，由此产⽣了⽹络最⼤流问题、最⼩费⽤流问题、最⼩费⽤最⼤流问题。
本⽂基于 NetworkX ⼯具包，通过例程详细介绍⽹络最⼤流问题、最⼩费⽤流问题、最⼩费⽤最⼤流问题的建模和编程。
带你从数模⼩⽩成为国赛达⼈。
1. ⽹络流优化
1.1 ⽹络流
⽹络流优化问题是基本的⽹络优化问题，应⽤⾮常⼴泛，遍及通讯、运输、电⼒、⼯程规划、任务分派、设备更新以及计算机辅助设计等领域。
流从源点流出、通过路径输送、流⼊到汇点，从⽽将⽬标从源点输送到汇点。流在⽣活中⼗分常见，例如交通系统中的⼈流、车流、物流，供⽔管⽹中的⽔流，⾦融系统中的现⾦流，⽹络中的信息流。
现实中的任何路径都有最⼤流量（容量）的限制，在⽹络中也是如此，并以边的容量（Capacity）表⽰，⼀条边的流量不能超过它的容量。
把这些现实问题抽象为⽹络流问题，其特征是：（1）有向图上的每条边具有容量限制；（2）从源点流出的流量，等于汇点流⼊的流量；（3）源点和汇点之外的所有中间节点，流出的流量等于流⼊的流量。
注意在⽹络流问题中有⼏组概念容易混淆：
源点/汇点，起点/终点，供应点/需求点：源点是只进不出的点，汇点是只出不进的点。源点/汇点 可以指定为问题的 起点/终点，但本质上源点/汇点是由⽹络结构特征决定的，⽽不是被指定的。供应点的供应量和需求点的需求量是固定/确定的，⽽源点/汇点的⽬标是发出/接收的流量最⼤，不是固定值。
容量 与 流量：容量是路径（边、弧）允许的最⼤流通能⼒，⽤ c(i,j) 表⽰；流量则是路径（边、弧）上的实际流量，⽤ f(i,j) 表⽰。
1.2 典型的⽹络流优化问题
⽹络流优化问题最重要的指标是每条边的成本和容量限制，既要考虑成本最低（最短路径问题），⼜要满⾜容量限制（最⼤流问题），由此产⽣了⽹络最⼤流问题、最⼩费⽤流问题、最⼩费⽤最⼤流问题。
最⼤流问题（Maximun flow problem）：已知每条边的容量，研究如何充分利⽤⽹络能⼒，使从源点到汇点的总流量最⼤，也即在容量⽹络中求流量最⼤的可⾏流。
最⼩费⽤流问题（Minimum cost problem）：已知每条边的容量和单位流量的费⽤，对于给定的源点、汇点流量，研究如何分配流量和路径，使总费⽤最⼩，也即在容量费⽤⽹络中求成本最低的可⾏流。
最⼩费⽤最⼤流问题（Minimum cost maximum flow），已知每条边的容量和单位流量的费⽤，研究⽹络的流量最⼤的路径中，费⽤最⼩的路径。简单地说，就是满⾜最⼤流的路径可能有多条，需要从其中到成本最低的路径。
Network ⼯具包求解⽹络流优化，包括最⼤流算法、最⼩割算法、最⼩费⽤流算法、最⼩费⽤最⼤流算法、容量缩放最⼩成本流算法。
2. ⽹络最⼤流问题（MFP）
2.1 ⽹络最⼤流算法
⽹络最⼤流问题，是在容量⽹络 G(V,E) 中求流量 v(f) 达到最⼤的可⾏流 f。在最⼤流问题中，只能有⼀个源点和⼀个汇点。求解⽹络最⼤流主要有增⼴路法和预流推进法两类⽅法。
增⼴路⽅法从⼀条可⾏流开始，⽤ BFS 或 DFS 从源到汇到⼀条增⼴路，沿着该路径修改流量，不断重复这个过程，直到不到增⼴路时停⽌，此时的流就是最⼤流。增⼴路⽅法有多种的实现算法，如 Ford Fulkerson 标号法的算法复杂度为 （不稳
定），Edmonds Karp 算法的复杂度为 ，Dinic 算法的复杂度为 ，ISAP 算法的复杂度也是 ，但其速度是最快的。
预流推进⽅法也称压⼊与重标记⽅法，算法从源点开始向下推流，通过不断地寻活结点，将流量推向以该点为起点的可推流边（压⼊过程）；如果在该点处不到可推流边，则将该点的⾼度加 1，以实现将过⼤的流向后推进（重标记过程）。最⾼标号预流推进（HLPP）算法的复杂度为 ，改进的 HLPP 算法的复杂度为 。
2.2 NetworkX 求解⽹络最⼤流问题
Network ⼯具包提供了多种求解⽹络最⼤流问题的算法和函数。其中 maximum_flow()、maximum_flo
w_value()、minimum_cut()、minimum_cut_value() 是集成了多种算法的通⽤函数，可以设置算法选项调⽤对应的算法；其它函数则是具体的算法实现函数。
函数
功能maximum_flow(flowG,s,t[, capacity,…])计算最⼤流
maximum_flow_value(flowG,s,t[,…])计算最⼤的单⼀⽬标流的值minimum_cut(flowG,s,t[, capacity,flow_func])计算最⼩割的值和节点分区
minimum_cut_value(flowG,s,t[,capacity,…])
计算最⼩割的值
edmonds_karp(G,s,t[,capacity,…])Edmonds-Karp 算法求最⼤流
shortest_augmenting_path(G,s,t[,…])
SAP算法求最⼤流dinitz(G,s,t[,capacity,…])Dinitz 算法求最⼤流preflow_push(G,s,t[,capacity,…])HLPP 算法求最⼤流
boykov_kolmogorov(G,s,t[,capacity,…])
drake bellBoykov-Kolmogorov 算法求最⼤流
艾佳妮三十而已2.3 maximum_flow() 函数说明
maximum_flow (flowG, _s, _t, capacity=‘capacity’, flow_func=None, *kwargs)
maximum_flow_value (flowG, _s, _t, capacity=‘capacity’, flow_func=None, *kwargs)
主要参数：
flowG(NetworkX graph)：有向图，边必须带有容量属性 capacity（不能⽤ ‘weight’ ）。_s (node)：源点。_t (node)：汇点。
capacity (string)：边的容量属性 capacity，缺省视为⽆限容量。
flow_func(function)：调⽤算法的函数名，如：‘edmonds_karp’, ‘shortest_augmenting_path’, ‘dinitz’,‘preflow_push’, ‘boykov_kolmogorov’。缺省值 ‘None’ ，选择 ‘preflow_push’（HLPP 算法）。返回值：
flow_value(integer, float)：⽹络最⼤流的流量值
flow_dict (dict)：字典类型，⽹络最⼤流的流经路径及各路径的分配流量
O (Ef )O (V E )2O (V E )2O (V E )2O (V E )2O (V )2
(E )
注意：如果要选择指定算法，需要写成以下形式 flow_func=nx.algorithms.flow.edmonds_karp，⽽不是
flow_func=edmonds_karp。也可以写成：
from networkx.algorithms.flow import edmonds_karp
flowValue, flowDict = nx.maximum_flow(G1, 's', 't', flow_func=edmonds_karp)
2.4 案例：输油管⽹的最⼤流量
问题描述：
在输油管⽹中，通过输油管连接⽣产⽯油的油井、储存⽯油的油库和转运的中间泵站。各站点之间的连接及管路的容量如图（参见 2.6 程序运⾏结果图）所⽰，求从油井到油库的最⼤流量和具体⽅案。
问题分析：
这是⼀个⽹络最⼤流问题，可以⽤顶点表⽰油井、油库和泵站，其中油井为源点 s、油库为汇点 t，⽤有向边表⽰输油管，有向边的权capacity 表⽰输油管的最⼤流量（容量）。
⽤ NetworkX 的 maximum_flow() 函数即可求出从从源点 s 到汇点 t 的最⼤流量。
程序说明：
1. 图的输⼊。本例为稀疏有向图，使⽤ nx.DiGraph() 定义⼀个有向图。通过 add_edge(‘s’, ‘a’, capacity=6) 定义有向边和属性
capacity。注意必须以关键字 ‘capacity’ 表⽰容量，不能⽤权值 ‘weight’ 或其它关键字代替。
2. nx.maximum_flow_value() 返回⽹络最⼤流的值，nx.maximum_flow() 可以同时返回⽹络最⼤流的值和⽹络最⼤流的路径及分配
的流量。
3. maxFlowDict 为字典类型，具体格式参加 2.6 程序运⾏结果。为了得到最⼤流所流经的边的列表edgeLists，要对 maxFlowDict 进
⾏整理和格式转换。
4. 在⽹络最⼤流图中，以边的标签显⽰了边的容量 c 和流量 f。
2.5 Python 例程
# mathmodel19_v1.py
# Demo19 of mathematical modeling algorithm
# Demo of network flow problem optimization with NetworkX
# Copyright 2021 YouCans, XUPT
# Crated：2021-07-15
import numpy as np
import matplotlib.pyplot as plt # 导⼊ Matplotlib ⼯具包
import networkx as nx # 导⼊ NetworkX ⼯具包
# 1. 最⼤流问题 (Maximum Flow Problem，MFP)
# 创建有向图
G1 = nx.DiGraph()# 创建⼀个有向图 DiGraph
G1.add_edge('s','a', capacity=6)# 添加边的属性 "capacity"
G1.add_edge('s','c', capacity=8)
G1.add_edge('a','b', capacity=3)
G1.add_edge('a','d', capacity=3)
G1.add_edge('b','t', capacity=10)
G1.add_edge('c','d', capacity=4)
G1.add_edge('c','f', capacity=4)
G1.add_edge('d','e', capacity=3)
G1.add_edge('d','g', capacity=6)
G1.add_edge('e','b', capacity=7)
G1.add_edge('e','j', capacity=4)
G1.add_edge('f','h', capacity=4)
G1.add_edge('g','e', capacity=7)
G1.add_edge('h','g', capacity=1)
G1.add_edge('h','i', capacity=3)雪姨 男人装
G1.add_edge('i','j', capacity=3)
G1.add_edge('j','t', capacity=5)
# 求⽹络最⼤流
为你种下会长大的幸福
# maxFlowValue = nx.maximum_flow_value(G1, 's', 't') # 求⽹络最⼤流的值
# maxFlowValue, maxFlowDict = nx.maximum_flow(G1, 's', 't') # 求⽹络最⼤流
from networkx.algorithms.flow import edmonds_karp # 导⼊ edmonds_karp 算法函数
maxFlowValue, maxFlowDict = nx.maximum_flow(G1,'s','t', flow_func=edmonds_karp)# 求⽹络最⼤流
# 数据格式转换
edgeCapacity = nx.get_edge_attributes(G1,'capacity')
edgeLabel ={}# 边的标签
for i in edgeCapacity.keys():# 整理边的标签，⽤于绘图显⽰
edgeLabel[i]= f'c={edgeCapacity[i]:}'# 边的容量
edgeLists =[]# 最⼤流的边的 list
for i in maxFlowDict.keys():
for j in maxFlowDict[i].keys():
edgeLabel[(i, j)]+=',f='+str(maxFlowDict[i][j])# 取出每条边流量信息存⼊边显⽰值
if maxFlowDict[i][j]>0:# ⽹络最⼤流的边（流量>0）
edgeLists.append((i,j))
# 输出显⽰
红旗飘飘print("最⼤流值: ", maxFlowValue)
print("最⼤流的途径及流量: ", maxFlowDict)# 输出最⼤流的途径和各路径上的流量
print("最⼤流的路径：", edgeLists)# 输出最⼤流的途径
# 绘制有向⽹络图
fig, ax = plt.subplots(figsize=(8,6))
pos ={'s':(1,8),'a':(6,7.5),'b':(9,8),'c':(1.5,6),'d':(4,6),'e':(8,5.5),# 指定顶点绘图位置'f':(2,4),'g':(5,4),'h':(1,2),'i':(5.5,2.5),'j':(9.5,2),'t':(11,6)}
edge_labels = nx.get_edge_attributes(G1,'capacity')
ax.set_title("Maximum flow of petroleum network with NetworkX")# 设置标题
nx.draw(G1, pos, with_labels=True, node_color='c', node_size=300, font_size=10)# 绘制有向图，显⽰顶点标签nx.draw_networkx_edge_labels(G1, pos, edgeLabel, font_color='navy')# 显⽰边的标签：'capacity' + maxFlow nx.draw_networkx_edges(G1, pos, edgelist=edgeLists, edge_color='m')# 设置指定边的颜⾊、宽度
plt.axis('on')# Youcans@XUPT
plt.show()
2.6 程序运⾏结果
最⼤流值:14
最⼤流的途径及流量:{'s':{'a':6,'c':8},'a':{'b':3,'d':3},'c':{'d':4,'f':4},'b':{'t':10},'d':{'e':3,'g':4},'t':{},'f':{'h':4},'e':{'b':7,'j':1},'g':{'e':5},'j':{'t':4}, 'h':{'g':1,'i':3},'i':{'j':3}}
最⼤流的路径：[('s','a'),('s','c'),('a','b'),('a','d'),('c','d'),('c','f'),('b','t'),('d','e'),('d','g'),('f','h'),('e','b'),('e','j'),('g','e'),('j','t'),('h','g'),('h','i'),('i','j')]
3. 最⼩费⽤流问题（MCP）
3.1 最⼩费⽤流问题的算法
在实际问题中，我们总是希望在完成运输任务的同时，寻求运输费⽤最低的⽅案。最⼩费⽤流问题，就是要以最⼩费⽤从出发点（供应点）将⼀定的流量输送到接收点（需求点）。在最⼩流问题中，供应点、需求点的数量可以是⼀个或多个，但每个供应点的供应量和需求点的需求量是固定的。
最⼩费⽤流问题可以⽤如下的线性规划问题描述
KaTeX parse error: No such environment: align* at position 8: \begin{a l i g n*}& min\;Cost=\s…
求解最⼩费⽤流问题的⽅法很多，常见的如：连续最短路算法（Successive shortest path）、消圈算法（Cycle canceling）、原始对偶算法（Primal dual）、⽹络单纯性算法（Network simplex）和⾮均衡⽹络流算法（Out of Kilter法）等。
⽹络单纯形是单纯形算法的⼀个特殊应⽤，它使⽤⽣成树基来更有效地解决具有纯⽹络形式的线性规划问题。⽹络单纯性为最⼩费⽤流问题提供了标准的解决⽅法，可以解决数万个节点的⼤型问题。
最⼩费⽤流问题最重要的应⽤是配送⽹络的优化，如确定如何从出发地运送到中转站再转运到客户的配送⽅案。运输问题、指派问题、转运问题、最⼤流问题、最短路径问题，都是特殊情况下的最⼩费⽤流问题。例如，最短路径问题是流量 v=1 的最⼩费⽤流问题，最⼤流问题是最⼤流量下的最⼩费⽤流问题。只要选定合适的权重、容量、流量，解决最⼩费⽤流的⽅法就能⽤来解决上述问题。
陈星佛歌3.2 NetworkX 求解最⼩费⽤流问题
Network ⼯具包提供了多个求解最⼩费⽤流问题的函数，所⽤的基本算法都是⽹络单纯性算法。
函数功能
network_simplex(G,[,demand,capacity,weight])单纯性法计算最⼩成本流
min_cost_flow_cost(G,[,demand,capacity,weight])计算最⼩成本流的成本
min_cost_flow(G,[,demand,capacity,weight])计算最⼩成本流
max_flow_min_cost(G,s,t[,capacity,weight])计算最⼩成本的最⼤流
capacity_scaling(G[,demand,capacity,…])计算容量缩放最⼩成本流
3.3 min_cost_flow() 函数说明
min_cost_flow()、min_cost_flow_cost() 是求解费⽤最⼩流问题的函数，通过调⽤⽹络单纯性算法函数 network_simplex() 求解。
min_cost_flow(G, demand=‘demand’, capacity=‘capacity’, weight=‘weight’)
min_cost_flow_cost(G, demand=‘demand’, capacity=‘capacity’, weight=‘weight’)
主要参数：
发布评论