四川科隆建设有限公司网站,网站更改备案信息吗,网站开发 前台代码,如何实现一个响应式网页流在生活中十分常见#xff0c;例如交通系统中的人流、车流、物流#xff0c;供水管网中的水流#xff0c;金融系统中的现金流#xff0c;网络中的信息流。网络流优化问题是基本的网络优化问题#xff0c;应用非常广泛。网络流优化问题最重要的指标是边的成本和容量限制例如交通系统中的人流、车流、物流供水管网中的水流金融系统中的现金流网络中的信息流。网络流优化问题是基本的网络优化问题应用非常广泛。网络流优化问题最重要的指标是边的成本和容量限制既要考虑成本最低又要满足容量限制由此产生了网络最大流问题、最小费用流问题、最小费用最大流问题。本文基于 NetworkX 工具包通过例程详细介绍网络最大流问题、最小费用流问题、最小费用最大流问题的建模和编程。『Python小白的数学建模课 Youcans』带你从数模小白成为国赛达人。 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 标号法的算法复杂度为 O(Ef)O(E f)O(Ef)不稳定Edmonds Karp 算法的复杂度为 O(VE2)O(V E^2)O(VE2)Dinic 算法的复杂度为 O(V2E)O(V^2 E)O(V2E)ISAP 算法的复杂度也是 O(V2E)O(V^2 E)O(V2E)但其速度是最快的。
预流推进方法也称压入与重标记方法算法从源点开始向下推流通过不断地寻找活结点将流量推向以该点为起点的可推流边压入过程如果在该点处找不到可推流边则将该点的高度加 1以实现将过大的流向后推进重标记过程。最高标号预流推进HLPP算法的复杂度为 O(V2E)O(V^2 E)O(V2E)改进的 HLPP 算法的复杂度为 O(V2(E))O(V^2 \sqrt{(E)})O(V2(E))。 2.2 NetworkX 求解网络最大流问题
Network 工具包提供了多种求解网络最大流问题的算法和函数。其中 maximum_flow()、maximum_flow_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,…])Boykov-Kolmogorov 算法求最大流2.3 maximum_flow() 函数说明
maximum_flow()、maximum_flow_value() 是求解网络最大流问题的通用方法集成了多种算法可供选择。官网介绍详见https://networkx.org/documentation/stable/reference/algorithms/flow.html 。 maximum_flow (flowG, _s, _t, capacity‘capacity’, flow_funcNone, *kwargs) maximum_flow_value (flowG, _s, _t, capacity‘capacity’, flow_funcNone, *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)字典类型网络最大流的流经路径及各路径的分配流量
注意如果要选择指定算法需要写成以下形式 flow_funcnx.algorithms.flow.edmonds_karp而不是 flow_funcedmonds_karp。也可以写成
from networkx.algorithms.flow import edmonds_karp
flowValue, flowDict nx.maximum_flow(G1, s, t, flow_funcedmonds_karp) 2.4 案例输油管网的最大流量
问题描述
在输油管网中通过输油管连接生产石油的油井、储存石油的油库和转运的中间泵站。各站点之间的连接及管路的容量如图参见 2.6 程序运行结果图所示求从油井到油库的最大流量和具体方案。
问题分析
这是一个网络最大流问题可以用顶点表示油井、油库和泵站其中油井为源点 s、油库为汇点 t用有向边表示输油管有向边的权 capacity 表示输油管的最大流量容量。
用 NetworkX 的 maximum_flow() 函数即可求出从从源点 s 到汇点 t 的最大流量。
程序说明 图的输入。本例为稀疏有向图使用 nx.DiGraph() 定义一个有向图。通过 add_edge(‘s’, ‘a’, capacity6) 定义有向边和属性 capacity。注意必须以关键字 ‘capacity’ 表示容量不能用权值 ‘weight’ 或其它关键字代替。 nx.maximum_flow_value() 返回网络最大流的值nx.maximum_flow() 可以同时返回网络最大流的值和网络最大流的路径及分配的流量。 maxFlowDict 为字典类型具体格式参加 2.6 程序运行结果。为了得到最大流所流经的边的列表edgeLists要对 maxFlowDict 进行整理和格式转换。 在网络最大流图中以边的标签显示了边的容量 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
# Crated2021-07-15import numpy as np
import matplotlib.pyplot as plt # 导入 Matplotlib 工具包
import networkx as nx # 导入 NetworkX 工具包# 1. 最大流问题 (Maximum Flow ProblemMFP)
# 创建有向图
G1 nx.DiGraph() # 创建一个有向图 DiGraph
G1.add_edge(s, a, capacity6) # 添加边的属性 capacity
G1.add_edge(s, c, capacity8)
G1.add_edge(a, b, capacity3)
G1.add_edge(a, d, capacity3)
G1.add_edge(b, t, capacity10)
G1.add_edge(c, d, capacity4)
G1.add_edge(c, f, capacity4)
G1.add_edge(d, e, capacity3)
G1.add_edge(d, g, capacity6)
G1.add_edge(e, b, capacity7)
G1.add_edge(e, j, capacity4)
G1.add_edge(f, h, capacity4)
G1.add_edge(g, e, capacity7)
G1.add_edge(h, g, capacity1)
G1.add_edge(h, i, capacity3)
G1.add_edge(i, j, capacity3)
G1.add_edge(j, t, capacity5)# 求网络最大流
# 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_funcedmonds_karp) # 求网络最大流# 数据格式转换
edgeCapacity nx.get_edge_attributes(G1, capacity)
edgeLabel {} # 边的标签
for i in edgeCapacity.keys(): # 整理边的标签用于绘图显示edgeLabel[i] fc{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: # 网络最大流的边流量0edgeLists.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_labelsTrue, node_colorc, node_size300, font_size10) # 绘制有向图显示顶点标签
nx.draw_networkx_edge_labels(G1, pos, edgeLabel, font_colornavy) # 显示边的标签capacity maxFlow
nx.draw_networkx_edges(G1, pos, edgelistedgeLists, edge_colorm) # 设置指定边的颜色、宽度
plt.axis(on) # YoucansXUPT
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法等。
网络单纯形是单纯形算法的一个特殊应用它使用生成树基来更有效地解决具有纯网络形式的线性规划问题。网络单纯性为最小费用流问题提供了标准的解决方法可以解决数万个节点的大型问题。
最小费用流问题最重要的应用是配送网络的优化如确定如何从出发地运送到中转站再转运到客户的配送方案。运输问题、指派问题、转运问题、最大流问题、最短路径问题都是特殊情况下的最小费用流问题。例如最短路径问题是流量 v1 的最小费用流问题最大流问题是最大流量下的最小费用流问题。只要选定合适的权重、容量、流量解决最小费用流的方法就能用来解决上述问题。 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’) 主要参数
G(NetworkX graph)有向图边必须带有容量属性 capacity、单位成本属性 ‘weight’ 。demand (string)顶点的需求量属性 demand表示节点的净流量负数表示供应点的净流出量正数表示需求点的净流入量0 表示中转节点。缺省值为 0。capacity (string)边的容量缺省视为无限容量。weight (string)边的单位流量的费用缺省值为 0。
返回值
flowDict (dict)字典类型最小费用流的流经路径及各路径的分配流量flowCost(integer, float)满足需求的最小费用流的总费用NetworkXUnfeasible输入的净流量(demand)不平衡或没有满足需求流量的可行流时抛出异常信息。
注意费用最小流函数 min_cost_flow() 中并没有设定供应点、需求点而是通过设置顶点属性 ‘demand’ 确定供应点、需求点及各顶点的净流量因而允许网络中存在多个供应点、需求点。 3.4 案例运输费用
问题描述
从 s 将货物运送到 t。已知与 s、t 相连各道路的最大运输能力、单位运量的费用如图所示参见 3.6 程序运行结果图图中边上的参数 (9,4) 表示道路的容量为 9单位流量的费用为 4。求流量 v 的最小费用流。
问题分析
这是一个最小费用流问题。用 NetworkX 的 nx.min_cost_flow() 函数或 nx.network_simplex() 函数即可求出从供应点到需求点的给定流量 v 的最小费用流。
程序说明
图的输入。本例为稀疏的有向图使用 nx.DiGraph() 定义一个有向图用G.add_weighted_edges_from() 函数以列表向图中添加多条赋权边每个赋权边以元组 (node1,node2,{‘capacity’:c1, ‘weight’:w1}) 定义属性 ‘capacity’ 和 ‘weight’。注意必须以关键字 ‘capacity’ 表示容量以 ‘weight’ 表示单位流量的费用。nx.shortest_path() 用于计算最短路径该段不是必须的。将最短路径的计算结果与最小费用流的结果进行比较可以看到流量 v1 时最小费用流的结果与最短路径结果是相同的。nx.cost_of_flow() 用于计算最小费用最大流该段不是必须的。将最小费用最大流的计算结果与最小费用流的结果进行比较可以看到在最大流量 v14 时最小费用流的结果与最小费用最大流结果是相同的。最小费用流是基于确定的流量 v 而言的。流量 v 可以在程序中赋值例程中 v 从 1 逐渐递增计算所有流量下的最小费用流直到达到网络容量的极限如果再增大流量将会超出网络最大容量没有可行流计算最小费用流失败。NetworkX 计算最小费用流时不是在函数中指定源点、汇点和流量而是通过向源点、汇点添加属性 demand 实现的。demand 为正值时表示净输入流量demand 为负值时表示净输出流量这使我们可以指定多源多汇。nx.min_cost_flow() 返回最小费用流的路径和流量分配字典格式nx.min_cost_flow_cost() 返回最小费用流的费用值。nx.network_simplex() 也可以求最小费用流返回最小费用流的费用值路径和流量分配。在最小费用流图中最大流量 v14以边的标签显示了边的容量 c、单位流量的费用 w 和流量 f如 (8,4),f7 表示边的容量为 8单位流量的费用为 4分配流量为 7。在最小费用流图中最大流量 v14以不同颜色edge_color‘m’和宽度width2表示最小费用流的边未使用的流量为 0 f0的边以黑色绘制。 3.5 Python 例程
# mathmodel19_v1.py
# Demo19 of mathematical modeling algorithm
# Demo of network flow problem optimization with NetworkX
# Copyright 2021 YouCans, XUPT
# Crated2021-07-15import numpy as np
import matplotlib.pyplot as plt # 导入 Matplotlib 工具包
import networkx as nx # 导入 NetworkX 工具包# 2. 最小费用流问题Minimum Cost FlowMCF
# 创建有向图
G2 nx.DiGraph() # 创建一个有向图 DiGraph
G2.add_edges_from([(s,v1,{capacity: 7, weight: 4}),(s,v2,{capacity: 8, weight: 4}),(v1,v3,{capacity: 9, weight: 1}),(v2,v1,{capacity: 5, weight: 5}),(v2,v4,{capacity: 9, weight: 4}),(v3,v4,{capacity: 6, weight: 2}),(v3,t,{capacity: 10, weight: 6}),(v4,v1,{capacity: 2, weight: 1}),(v4,t,{capacity: 5, weight: 2})]) # 添加边的属性 capacity, weight
# 整理边的标签用于绘图显示
edgeLabel1 nx.get_edge_attributes(G2, capacity)
edgeLabel2 nx.get_edge_attributes(G2, weight)
edgeLabel {}
for i in edgeLabel1.keys():edgeLabel[i] f({edgeLabel1[i]:},{edgeLabel2[i]:}) # 边的(容量成本)# 计算最短路径---非必要用于与最小费用流的结果进行比较
lenShortestPath nx.shortest_path_length(G2, s, t, weightweight)
shortestPath nx.shortest_path(G2, s, t, weightweight)
print(\n最短路径: , shortestPath) # 输出最短路径
print(最短路径长度: , lenShortestPath) # 输出最短路径长度# 计算最小费用最大流---非必要用于与最小费用流的结果进行比较
minCostFlow nx.max_flow_min_cost(G2, s, t) # 求最小费用最大流
minCost nx.cost_of_flow(G2, minCostFlow) # 求最小费用的值
maxFlow sum(minCostFlow[s][j] for j in minCostFlow[s].keys()) # 求最大流量的值
print(\n最大流量: {}.format(maxFlow)) # 输出最小费用的值
print(最大流量的最小费用: {}\n.format(minCost)) # 输出最小费用的值# v input(Input flow (v0):)
v 0
while True:v 1 # 最小费用流的流量G2.add_node(s, demand-v) # nx.min_cost_flow() 的设置要求G2.add_node(t, demandv) # 设置源点/汇点的流量try: # YoucansXUPT# 求最小费用流(demandv)minFlowCost nx.min_cost_flow_cost(G2) # 求最小费用流的费用minFlowDict nx.min_cost_flow(G2) # 求最小费用流# minFlowCost, minFlowDict nx.network_simplex(G2) # 求最小费用流--与上行等效print(流量: {:2d}\t最小费用:{}.format(v, minFlowCost)) # 输出最小费用的值(demandv)# print(最小费用流的路径及流量: , minFlowDict) # 输出最大流的途径和各路径上的流量except Exception as e:print(流量: {:2d}\t超出网络最大容量没有可行流。.format(v))print(\n流量 v{:2d}计算最小费用流失败({})。.format(v, str(e)))break # 结束 while True 循环edgeLists []
for i in minFlowDict.keys():for j in minFlowDict[i].keys():edgeLabel[(i, j)] ,f str(minFlowDict[i][j]) # 取出每条边流量信息存入边显示值if minFlowDict[i][j] 0:edgeLists.append((i, j))maxFlow sum(minFlowDict[s][j] for j in minFlowDict[s].keys()) # 求最大流量的值
print(\n最大流量: {:2d},\t最小费用:{}.format(maxFlow, minFlowCost)) # 输出最小费用的值
print(最小费用流的路径及流量: , minFlowDict) # 输出最小费用流的途径和各路径上的流量
print(最小费用流的路径, edgeLists) # 输出最小费用流的途径# 绘制有向网络图
pos{s:(0,5),v1:(4,2),v2:(4,8),v3:(10,2),v4:(10,8),t:(14,5)} # 指定顶点绘图位置
fig, ax plt.subplots(figsize(8,6))
ax.text(6,2.5,youcans-xupt,colorgainsboro)
ax.set_title(Minimum Cost Maximum Flow with NetworkX)
nx.draw(G2,pos,with_labelsTrue,node_colorc,node_size300,font_size10) # 绘制有向图显示顶点标签
nx.draw_networkx_edge_labels(G2,pos,edgeLabel,font_size10) # 显示边的标签capacity,weight minCostFlow
nx.draw_networkx_edges(G2,pos,edgelistedgeLists,edge_colorm,width2) # 设置指定边的颜色、宽度
plt.axis(on)
plt.show()3.6 程序运行结果
最短路径: [s, v1, v3, v4, t]
最短路径长度: 9最大流量: 14
最大流量的最小费用: 159流量: 1 最小费用:9
流量: 2 最小费用:18
流量: 3 最小费用:27
流量: 4 最小费用:36
流量: 5 最小费用:45
流量: 6 最小费用:56
流量: 7 最小费用:67
流量: 8 最小费用:79
流量: 9 最小费用:91
流量: 10 最小费用:103
流量: 11 最小费用:115
流量: 12 最小费用:127
流量: 13 最小费用:143
流量: 14 最小费用:159
流量: 15 超出网络最大容量没有可行流。流量 v15计算最小费用流失败(no flow satisfies all node demands)。最大流量: 14, 最小费用:159
最小费用流的路径及流量: {s: {v1: 7, v2: 7}, v1: {v3: 9}, v2: {v1: 2, v4: 5}, v3: {v4: 0, t: 9}, v4: {v1: 0, t: 5}, t: {}}
最小费用流的路径 [(s, v1), (s, v2), (v1, v3), (v2, v1), (v2, v4), (v3, t), (v4, t)]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),f11表示边的容量为 13单位流量的费用为 7分配流量为 11。在最小费用最大流图中以不同颜色edge_color‘m’和宽度width2表示最小费用流的边未使用的流量为 0 f0的边以黑色绘制。 4.4 Python 例程
# mathmodel19_v1.py
# Demo19 of mathematical modeling algorithm
# Demo of network flow problem optimization with NetworkX
# Copyright 2021 YouCans, XUPT
# Crated2021-07-15import numpy as np
import matplotlib.pyplot as plt # 导入 Matplotlib 工具包
import networkx as nx # 导入 NetworkX 工具包# 3. 最小费用最大流问题Minimum Cost Maximum FlowMCMF
# 创建有向图
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,colorgainsboro)
ax.set_title(Minimum Cost Maximum Flow with NetworkX)
nx.draw(G3,pos,with_labelsTrue,node_colorc,node_size300,font_size10) # 绘制有向图显示顶点标签
nx.draw_networkx_edge_labels(G3,pos,edgeLabel,font_size10) # 显示边的标签capacity,weight minCostFlow
nx.draw_networkx_edges(G3,pos,edgelistedgeLists,edge_colorm,width2) # 设置指定边的颜色、宽度
plt.axis(on) # YoucansXUPT
plt.show()4.5 运行结果
最小费用最大流的路径及流量: {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
最小费用: 3705. 总结
本文基于 NetworkX 工具包通过例程详细介绍了网络最大流问题、最小费用流问题、最小费用最大流问题的建模和编程。运输问题、指派问题、转运问题、最大流问题、最短路径问题都是特殊情况下的最小费用流问题。通过 3.6 中最短路径、最小费用最大流的结果与 v1、v14 的最小费用流结果的比较可以理解这种关系。例程给出了对部分指定的边设置颜色为边设置指定格式的显示内容NetworkX 函数输出值的数据格式转换的编程方法建议读者多加留意。网络流优化问题还有很多变形和衍生问题将在今后的文中进行介绍。
【本节完】 版权声明
欢迎关注『Python小白的数学建模课 Youcans』 原创作品
原创作品转载必须标注原文链接(https://blog.csdn.net/youcans/article/details/118726642)。
Copyright 2021 Youcans, XUPT
Crated2021-07-16 欢迎关注 『Python小白的数学建模课 Youcans』 系列持续更新 Python小白的数学建模课-01.新手必读 Python小白的数学建模课-02.数据导入 Python小白的数学建模课-03.线性规划 Python小白的数学建模课-04.整数规划 Python小白的数学建模课-05.0-1规划 Python小白的数学建模课-06.固定费用问题 Python小白的数学建模课-07.选址问题 Python小白的数学建模课-09.微分方程模型 Python小白的数学建模课-10.微分方程边值问题 Python小白的数学建模课-12.非线性规划 Python小白的数学建模课-15.图论的基本概念 Python小白的数学建模课-16.最短路径算法 Python小白的数学建模课-17.条件最短路径算法 Python小白的数学建模课-18.最小生成树问题 Python小白的数学建模课-19.网络流优化问题 Python小白的数学建模课-A1.国赛赛题类型分析 Python小白的数学建模课-A2.2021年数维杯C题探讨 Python小白的数学建模课-A3.12个新冠疫情数模竞赛赛题及短评 Python小白的数学建模课-B2. 新冠疫情 SI模型 Python小白的数学建模课-B3. 新冠疫情 SIS模型 Python小白的数学建模课-B4. 新冠疫情 SIR模型 Python小白的数学建模课-B5. 新冠疫情 SEIR模型 Python小白的数学建模课-B6. 新冠疫情 SEIR改进模型 Python数模笔记-PuLP库 Python数模笔记-StatsModels统计回归 Python数模笔记-Sklearn Python数模笔记-NetworkX Python数模笔记-模拟退火算法
