数学建模Python图论习题

第五章 图与网络优化

• 数学建模简明教程-基于python
• 题目
• 三、3如表5.3是某运输问题的相关数据，将次问题转换为最小费用最大流问题，画出网络图并求解。
• 二、题解
• • 1.问题分析
  • 2.运行结果
• 问题总结

本文章为自己解答的教材答案：

要使用要使用最大流算法，必须构造一个发点s,和收点t，设出边和边的容量，且要解决最小费用问题需要设出费用且根据链路经行赋权,再构造有向赋权图。
构造有向图（V,E,f）V为图中的节点集合，E为vivj边的集合，C为每条边的容量，
Bij为每条边的费用。
（c,f）第一个数字为容量，f第二各数字为费用

代码如下（示例）：

from platform import node
import numpy as np
import networkx as nx
L=[('s','A',8,0),('s','B',7,0),
('A','1',8,20),('A','2',8,24),('A','3',8,5),
('B','1',7,30),('B','2',7,22),('B','3',7,20),
('1','t',4,0),('1','t',5,0),('1','t',6,0)
]
node=['s']+['A','B']+[str(i) for i in range(1,4)]+['t']
G=nx.DiGraph();n=len(node)
G.add_nodes_from(node)
for k in range(len(L)):
    G.add_edge(L[k][0],L[k][1],capacity=L[k][2],weight=L[k][3])
mincostFlow =nx.max_flow_min_cost(G,'s','t')
print('max flow',mincostFlow)
mincost=nx.cost_of_flow(G,mincostFlow)
print('min cost',mincost)

flow_mat=np.zeros((n,n))
for i,adj in mincostFlow.items():
    for j,f in adj.items():
        flow_mat[node.index(i),node.index(j)]=f
print('max flow:',sum(flow_mat[:-1]))
print('min cost max flow zero:',flow_mat)

（示例）：
max flow {‘s’: {‘A’: 6, ‘B’: 0}, ‘A’: {‘1’: 6, ‘2’: 0, ‘3’: 0}, ‘B’: {‘1’: 0, ‘2’: 0, ‘3’: 0}, ‘1’: {‘t’: 6}, ‘2’: {}, ‘3’: {}, ‘t’: {}}
min cost 120
max flow: [0. 6. 0. 6. 0. 0. 6.]
min cost max flow zero: [[0. 6. 0. 0. 0. 0. 0.]
[0. 0. 0. 6. 0. 0. 0.]
[0. 0. 0. 0. 0. 0. 0.]
[0. 0. 0. 0. 0. 0. 6.]
[0. 0. 0. 0. 0. 0. 0.]
[0. 0. 0. 0. 0. 0. 0.]
[0. 0. 0. 0. 0. 0. 0.]]

最短路径下的最大流量容量为6，在迭代了n次数后，没有出现负增长。