数学建模

 

编程知识点

模型库-networkx-优化-最小费用最大流流

 

Wang Haihua

🚅 🚋😜 🚑 🚔

流在生活中十分常见，例如交通系统中的人流、车流、物流，供水管网中的水流，金融系统中的现金流，网络中的信息流。网络流优化问题是基本的网络优化问题，应用非常广泛。 网络流优化问题最重要的指标是边的成本和容量限制，既要考虑成本最低，又要满足容量限制，由此产生了网络最大流问题、最小费用流问题、最小费用最大流问题。 本文基于 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 工具包求解网络流优化，包括最大流算法、最小割算法、最小费用流算法、最小费用最大流算法、容量缩放最小成本流算法。

# 输出显示
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()

最大流值:  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')]

4. 最小费用最大流问题（MCMF）

4.1 最小费用最大流问题的算法

最小成本最大流问题可以看做是最短路径问题和最大流问题的结合，既要像最短路径问题那样考虑成本最小，又要考虑到每条边上的流量限制。最短路径问题和最大流问题在本质上也是特殊的最小成本最大流问题，是网络优化中的基本问题。

求解最小费用最大流问题的常用方法有 Bellman-Ford算法、SPFA算法、Dijkstra 改进算法。

在 NetworkX 工具包中，求解最小费用最大流问题的方法与众不同：先调用 nx.maximum_flow_value() 函数求网络最大流，再以最大流调用 min_cost_flow() 函数求网络最大流时的最小费用流。哈哈，这样的处理方式，与本系列博文的思想十分吻合：容易理解，容易实现，容易掌握。

4.2 max_flow_min_cost() 函数说明

max_flow_min_cost()是求解最小费用最大流问题的函数。

max_flow_min_cost(G, s, t, capacity='capacity', weight='weight')
cost_of_flow(G, flowDict, weight='weight')

主要参数：

G(NetworkX graph)：有向图，边必须带有容量属性 capacity、单位成本属性 'weight' 。 s (node)：流的源点。 t (node)：流的汇点。 capacity (string)：边的容量，缺省视为无限容量。 weight (string)：边的单位流量的费用，缺省值为 0。 返回值：

flowDict (dict)：字典类型，最小费用最大流的流经路径及各路径的分配流量。 使用 cost_of_flow() 函数，可以由流经路径及各路径的分配流量 flowDict 计算可行流的成本。

4.3 案例：输油管网的最大流量和最小费用

问题描述：

某输油网络 G 中的每段管路允许的容量和单位流量的运输费用如图所示（参见4.5 程序运行结果图），图中边上的参数 (9,5) 表示边的容量为 9，单位流量的费用为 5。求从网络源点 s 到汇点 t 的最大流量，及输送最大流量的最小费用。

问题分析：

这是一个的最小费用最大流问题。用 NetworkX 的 nx.max_flow_min_cost() 函数可以求出从网络源点到汇点的最小费用最大流。

程序说明：

图的输入。用 nx.DiGraph() 定义一个有向图。用 G.add_weighted_edges_from() 函数以列表向图中添加多条赋权边，每个赋权边以元组 (node1,node2,{'capacity':c1, 'weight':w1}) 定义属性 'capacity' 和 'weight'。注意必须以关键字 'capacity' 表示容量，以 'weight' 表示单位流量的费用。 nx.max_flow_min_cost(G3, 's', 't') 用来计算从源点 's' 到汇点 't' 的最小费用最大流，返回最大流的途径和各路径上的流量分配，字典格式。 nx.cost_of_flow() 计算一个可行流的费用，例程中用来计算最小费用最大流的费用。 maxFlow 计算从源点 's' 发出的所有路径上的流量总和，得到最大流量的值。 在最小费用最大流图中，以边的标签显示了边的容量 c、单位流量的费用 w 和流量 f，如 (13,7),f=11表示边的容量为 13，单位流量的费用为 7，分配流量为 11。 在最小费用最大流图中，以不同颜色（edge_color='m'）和宽度（width=2）表示最小费用流的边，未使用的流量为 0 （f=0）的边以黑色绘制。

4.4 Python 例程

import numpy as np
import matplotlib.pyplot as plt # 导入 Matplotlib 工具包
import networkx as nx  # 导入 NetworkX 工具包

# 3. 最小费用最大流问题（Minimum Cost Maximum Flow，MCMF）
# 创建有向图
G3 = nx.DiGraph()  # 创建一个有向图 DiGraph
G3.add_edges_from([('s','v1',{'capacity': 13, 'weight': 7}),
                  ('s','v2',{'capacity': 9, 'weight': 9}),
                  ('v1','v3',{'capacity': 6, 'weight': 6}),
                  ('v1','v4',{'capacity': 5, 'weight': 5}),
                  ('v2','v1',{'capacity': 4, 'weight': 4}),
                  ('v2','v3',{'capacity': 5, 'weight': 2}),
                  ('v2','v5',{'capacity': 5, 'weight': 5}),
                  ('v3','v4',{'capacity': 5, 'weight': 2}),
                  ('v3','v5',{'capacity': 4, 'weight': 1}),
                  ('v3','t',{'capacity': 4, 'weight': 4}),
                  ('v4','t', {'capacity': 9, 'weight': 7}),
                  ('v5','t',{'capacity': 9, 'weight': 5})]) # 添加边的属性 'capacity', 'weight'

# 求最小费用最大流
minCostFlow = nx.max_flow_min_cost(G3, 's', 't')  # 求最小费用最大流
minCost = nx.cost_of_flow(G3, minCostFlow)  # 求最小费用的值
maxFlow = sum(minCostFlow['s'][j] for j in minCostFlow['s'].keys())  # 求最大流量的值

# # 数据格式转换
edgeLabel1 = nx.get_edge_attributes(G3,'capacity')  # 整理边的标签，用于绘图显示
edgeLabel2 = nx.get_edge_attributes(G3,'weight')
edgeLabel={}
for i in edgeLabel1.keys():
    edgeLabel[i]=f'({edgeLabel1[i]:},{edgeLabel2[i]:})'  # 边的(容量，成本)
edgeLists = []
for i in minCostFlow.keys():
    for j in minCostFlow[i].keys():
        edgeLabel[(i, j)] += ',f=' + str(minCostFlow[i][j])  # 将边的实际流量添加到 边的标签
        if minCostFlow[i][j]>0:
            edgeLists.append((i,j))

print("最小费用最大流的路径及流量: ", minCostFlow)  # 输出最大流的途径和各路径上的流量
print("最小费用最大流的路径：", edgeLists)  # 输出最小费用最大流的途径
print("最大流量: ", maxFlow)  # 输出最大流量的值
print("最小费用: ", minCost)  # 输出最小费用的值

# 绘制有向网络图
pos={'s':(0,5), 'v1':(3,9), 'v2':(3,1), 'v3':(6,5), 'v4':(9,9),'v5':(9,1), 't':(12,5)}  # 指定顶点绘图位置
fig, ax = plt.subplots(figsize=(8,6))
ax.text(5,1.5,"youcans-xupt",color='gainsboro')
ax.set_title("Minimum Cost Maximum Flow with NetworkX")
nx.draw(G3,pos,with_labels=True,node_color='c',node_size=300,font_size=10)   # 绘制有向图，显示顶点标签
nx.draw_networkx_edge_labels(G3,pos,edgeLabel,font_size=10)  # 显示边的标签：'capacity','weight' + minCostFlow
nx.draw_networkx_edges(G3,pos,edgelist=edgeLists,edge_color='m',width=2)  # 设置指定边的颜色、宽度
plt.axis('on') # Youcans@XUPT
plt.show()

最小费用最大流的路径及流量:  {'s': {'v1': 11, 'v2': 9}, 'v1': {'v3': 6, 'v4': 5}, 'v2': {'v1': 0, 'v3': 4, 'v5': 5}, 'v3': {'v4': 2, 'v5': 4, 't': 4}, 'v4': {'t': 7}, 'v5': {'t': 9}, 't': {}}
最小费用最大流的路径： [('s', 'v1'), ('s', 'v2'), ('v1', 'v3'), ('v1', 'v4'), ('v2', 'v3'), ('v2', 'v5'), ('v3', 'v4'), ('v3', 'v5'), ('v3', 't'), ('v4', 't'), ('v5', 't')]
最大流量:  20
最小费用:  370

5. 总结

本文基于 NetworkX 工具包，通过例程详细介绍了网络最大流问题、最小费用流问题、最小费用最大流问题的建模和编程。 运输问题、指派问题、转运问题、最大流问题、最短路径问题，都是特殊情况下的最小费用流问题。通过 3.6 中最短路径、最小费用最大流的结果与 v=1、v=14 的最小费用流结果的比较，可以理解这种关系。 例程给出了对部分指定的边设置颜色，为边设置指定格式的显示内容，NetworkX 函数输出值的数据格式转换的编程方法，建议读者多加留意。 网络流优化问题还有很多变形和衍生问题，将在今后的文中进行介绍。

参考文献

• youcans Python小白的数学建模课 https://www.zhihu.com/column/c_1381900867424075776
• 司守奎 的 《Python数学实验与建模》