別眨眼網

在實際工作和數模競賽中，網路最大流問題、最小費用流問題和最小費用最大流問題都有很多延伸和推廣的應用。

本文介紹了常見的網路最大流問題、最小費用流問題的應用與推廣，及其解題方法。

本文選擇多源多匯物流轉運問題、多商品流問題案例，詳細介紹網路流問題的分析方法和解決方案，並使用線性規劃方法建模和程式設計。

1。 網路流問題的應用與推廣

流在生活中十分常見，例如交通系統中的人流、車流、物流，供水管網中的水流，金融系統中的現金流，網路中的資訊流。網路流最佳化問題是基本的網路最佳化問題，應用非常廣泛，遍及通訊、運輸、電力、工程規劃、任務分派、裝置更新以及計算機輔助設計等領域。

網路流最佳化問題最重要的指標是每條邊的成本和容量限制，既要考慮成本最低（最短路徑問題），又要滿足容量限制（最大流問題），由此產生了網路最大流問題、最小費用流問題和最小費用最大流問題。在《Python小白的數學建模課-19。網路流最佳化》一文中，我們詳細介紹了網路最大流問題、最小費用流問題和最小費用最大流問題的演算法、程式設計和案例。

不論在實際工作中，還是在數模競賽中，網路最大流問題、最小費用流問題和最小費用最大流問題都有很多延伸和推廣的應用。小白同學對於網路圖的概念和思維邏輯比較生疏，面對變換和深化的題型往往對題目能有基本判斷和思路、但找不到具體的解決方法，覺得應該能做出來但就是差一點。

本文選擇多源多匯物流轉運問題、多商品流問題案例，詳細介紹網路流問題的分析方法和解決方案，並使用線性規劃方法建模和程式設計。

對於小白同學來說，這兩個案例的建模和程式設計都有些複雜。別急，也別怕，問題分析和程式說明都很詳細，只要靜下來慢慢讀，將程式說明、源程式和執行結果對照著讀，相信小白同學也能看懂。

2。 網路最大流問題的應用與推廣

2。1 指定流量的可行流

我們在《19。網路流最佳化》一文討論了網路最大流的演算法。如果不是計算最大流，而是要計算指定流量 v 的可行流，可以用如下圖所示的增廣路（相當於輔助線）方法處理。

（1）在容量網路 G 上增加一個頂點 t’ 和一條邊 （t，t’），構建一個新的容量網路 G’，令邊 （t，t’） 的容量為 v；

（2）對於容量網路 G‘，計算從源點 s 到匯點 t’ 的最大流 f m a x 顯然 f m a x ≤ v ；

（3）若 v < f m a x ，則容量網路 G 不存在滿足流量 v 的可行流；若 v = f m a x ，則從最大流 f m a x的路徑中去掉邊 （t，t’） 即得到容量網路 G 滿足流量 v 的可行流。

另一種思路是，設定源點 s /匯點 t 的流量為 v，再按最小費用流即可。這種方法不僅得到了流量 v 的可行流，而且是最小費用流，但該方法的計算量較大。主要程式如下，完整程式詳見《Python小白的數學建模課-19。網路流最佳化》。

G2。add_node（“s”， demand=-v） # nx。min_cost_flow（） 的設定要求G2。add_node（“t”， demand=v） # 設定源點/匯點的流量# 求最小費用流（demand=v）minFlowCost = nx。min_cost_flow_cost（G2） # 求最小費用流的費用minFlowDict = nx。min_cost_flow（G2） # 求最小費用流

2。2 多源點多匯點的最大流

《19。網路流最佳化》一文討論的網路流最佳化問題，都是單源點、單匯點的網路。對於多源點單匯點、單源點多匯點、多源點多匯點的容量網路的最大流問題，可以透過如下圖所示的增加一個超級源點和/或超級匯點的方法處理。

（1）在容量網路 G 上增加一個超級源點 s 和一個超級源點 t；從超級源點 s 向網路 G 中的每個源點連一條容量為 + ∞ +\infty+∞ 的邊，從網路 G 中的每個匯點向超級匯點 t 連一條容量為 + ∞ +\infty+∞ 的邊。於是得到了一個新的容量網路 G’。

（2）對於容量網路 G‘，計算從超級源點 s 到超級匯點 t 的最大流 f max ，即為多源多匯容量網路 G 的最大流。

使用 NetworkX 工具包，也有另一種特殊方法可以解決多源多匯最大流問題。

NetworkX 中求解費用最小流問題的函式

min_cost_flow（）

、

min_cost_flow_cost（）

是求解費用最小流問題的函式，並不是設定供應點、需求點，而是透過設定頂點屬性 ‘demand’ 確定供應點、需求點及各頂點的淨流量，因而允許網路中存在多個供應點、需求點。

min_cost_flow（G， demand=‘demand’， capacity=‘capacity’， weight=‘weight’）

min_cost_flow_cost（G， demand=‘demand’， capacity=‘capacity’， weight=‘weight’）

因此，對於指定流量的多源多匯網路可行流問題，只要在每個源點、匯點的頂點屬性 ‘demand’ 設定對應的供應量、需求量，再按最小費用流即可。這種方法不僅得到了流量 v 的可行流，而且是最小費用流。類似地，對於多源多匯網路的最大流問題，可以參考《19。網路流最佳化》中“3。4 案例：運輸費用”的方法，v 從 1 逐漸遞增，計算所有流量下的最小費用流，直到達到網路容量的極限，即得到容量網路的最大費用流。該方法不需要構造新的容量網路，程式設計實現簡單，而且可以獲得最大流量的最小費用流，但計算量很大。

2。3 帶頂點容量約束的最大流

標準形式的網路流最佳化問題，只有邊的容量約束，沒有頂點的容量約束。在實際問題中，頂點所表示的工廠、倉庫、銷售點，都存在最大儲存量，因而帶有頂點的容量約束。

對於頂點容量約束的網路流問題，可以透過如下圖所示的將每個帶約束的頂點 N 分拆為兩個頂點（入頂點 Nin 和出頂點 Nout）的方法處理：

（1）將指向頂點 N 的邊，改為指向入頂點 Nin；

（2）將頂點 N 所指向的邊，改為出頂點 Nout 所指向的邊；

（3）增加一條從入頂點 Nin 指向出頂點 Nout 的邊，邊的容量為頂點 N 的容量，單位費用為 0。

於是得到了一個新的容量網路 G’。由此，原有網路 G 的頂點 N 的容量限制，轉化為網路 G’ 的邊 （Nin，Nout） 的容量限制。帶頂點約束的容量網路 G 的最大流問題，轉化為新的標準形式的容量網路 G’ 的最大流問題。

3。 最小費用流問題的應用與推廣

3。1 運輸問題

有出發地（供應點、供應量）和目的地（需求點、需求量），沒有轉運點，沒有路段（邊）的容量限制，目標是總運輸成本最小或總利潤最大。

3。2 指派問題

出發地（供應點、供應量=1）是人，目的地（需求點、需求量=1）是任務，沒有轉運點，沒有路段（邊）的容量限制，目標是總指派成本最小或總利潤最大。

3。3 轉運問題

有出發地（供應點、供應量）和目的地（需求點、需求量），有轉運點，沒有路段（邊）的容量限制（或帶有容量限制），目標是總流量費用最小或總利潤最大。

3。4 最大流問題

最大流問題是特殊的最小費用流問題：有供應點、需求點、轉運點，有路段（邊）的容量限制，沒有供應量和需求量的限制，目標是透過網路到目的地的總流量最大。

3。5 最短路問題

有供應點（供應量=1）、需求點（需求量=1）、轉運點，沒有路段（邊）的容量限制，目標是透過網路到目的地的總距離最短。

4。 案例：多源多匯的物流轉運問題

4。1 問題描述

如圖所示，某公司的工廠（供應點）位於F1、F2，倉庫（中轉點）位於W1、W2，零售商（需求點）位於R1、R2、R3、R4。從工廠生產的產品先送到倉庫，再由倉庫發到零售商。圖中給出了各供應點和需求點的流量、每條發貨線路的最大流量、單位流量的運輸成本，要求在產銷平衡的條件下，找出總運輸費用最小的運輸方案。

4。2 問題分析

這是一個運輸路徑規劃問題，也是一個多源點、多匯點的最小費用流問題。

對於多源多匯的最小費用流問題，構造一個費用網路 G，網路 G 的各條邊沒有容量限制，單位流量的運輸成本為邊的權值 w。F1、F2 是網路 G 的源點（供應點），R1~R4 是匯點（需求點），W1、W2 是中間節點。F1、F2 的供應量與 R1~R4 的需求量是平衡的。因此可以用 NetworkX 的 maximum_flow（） 函式求出最小費用流。

該問題也是一個典型的線性規劃問題，可以用線性規劃方法求解。

式中：f（i，j） 表示路段 （i，j） 的流量，w（i，j） 表示路段 （i，j） 的單位流量運輸成本，S 表示源點（供應點），T 表示匯點（需求點）。

對於上式描述的線性規劃問題，可以用 PuLP工具包求解（參見《Python小白的數學建模課-03。線性規劃》），程式設計步驟如下：

（1） 匯入 PuLP庫函式；

（2） 定義一個線性規劃問題；

（3）定義決策變數，決策變數的上下限：

f11：F1-W1 流量， 0<=f11<=600 f12：F1-W2 流量， 0<=f12<=600 f21：F2-W1 流量， 0<=f21<=400 f22：F2-W2 流量， 0<=f22<=400 w11：W1-R1 流量， 0<=w11<=200 w12：W1-R2 流量， 0<=w12<=150 w13：W1-R3 流量， 0<=w13<=350 w14：W1-R4 流量， 0<=w14<=300 w21：W2-R1 流量， 0<=w21<=200 w22：W2-R2 流量， 0<=w22<=150 w23：W2-R3 流量， 0<=w23<=350 w24：W2-R4 流量， 0<=w24<=300

（4）定義目標函式：

min cost = 2*f11 + 3*f12 + 3*f21 + f22 + 2*w11 + 6*w12 + 3*w13 + 6*w14 + 4*w21 + 4*w22 + 6*w23 + 5*w24

（5）定義約束條件：

f11 + f12 <= 600 f21 + f22 <= 400 f11 + f21 = w11 + w12 + w13 + w14 f12 + f22 = w21 + w22 + w23 + w24 w11 + w21 = 200 w12 + w22 = 150 w13 + w23 = 350 w14 + w24 = 300

注意，f11+f12<=600， f21+f22<=400，意味著允許存在產銷不平衡的情況。

（6）求解規劃問題，輸出最佳化結果

本文給出了基於 NetworkX 工具包和基於 PuLP 工具包的兩種方法的程式，以便小白理解圖論中的最小費用流問題與線性規劃問題的聯絡。

4。3 Python 例程

# mathmodel21_v1。py# Demo21 of mathematical modeling algorithm# Demo of network flow problem optimization with NetworkX# Copyright 2021 YouCans， XUPT# Crated：2021-07-18import numpy as npimport matplotlib。pyplot as plt # 匯入 Matplotlib 工具包import networkx as nx # 匯入 NetworkX 工具包import pulp # 匯入 pulp庫# # 4。 多源多匯最小費用流問題 （Capacity network with multi source and multi sink）# # 4。1 費用網路# 建立有向圖G1 = nx。DiGraph（） # 建立一個有向圖 DiGraphG1。add_edges_from（［（‘F1’，‘W1’，{‘capacity’： 9e5， ‘weight’： 2}）， # F1~F2：工廠 （‘F1’，‘W2’，{‘capacity’： 9e5， ‘weight’： 3}）， # W1~W2：倉庫 （‘F2’，‘W1’，{‘capacity’： 9e5， ‘weight’： 3}）， （‘F2’，‘W2’，{‘capacity’： 9e5， ‘weight’： 1}）， （‘W1’，‘R1’，{‘capacity’： 9e5， ‘weight’： 2}）， # R1~R4：零售店 （‘W1’，‘R2’，{‘capacity’： 9e5， ‘weight’： 6}）， （‘W1’，‘R3’，{‘capacity’： 9e5， ‘weight’： 3}）， （‘W1’，‘R4’，{‘capacity’： 9e5， ‘weight’： 6}）， （‘W2’，‘R1’，{‘capacity’： 9e5， ‘weight’： 4}）， （‘W2’，‘R2’，{‘capacity’： 9e5， ‘weight’： 4}）， （‘W2’，‘R3’，{‘capacity’： 9e5， ‘weight’： 6}）， （‘W2’，‘R4’，{‘capacity’： 9e5， ‘weight’： 5}）］） # 新增邊的屬性 ‘capacity’， ‘weight’G1。add_node（“F1”， demand=-600） # nx。min_cost_flow（） 的設定要求G1。add_node（“F2”， demand=-400） # 設定源點的流量，負值表示淨流出G1。add_node（“R1”， demand=200） # 設定匯點的流量，正值表示淨流入G1。add_node（“R2”， demand=150）G1。add_node（“R3”， demand=350）G1。add_node（“R4”， demand=300）pos={‘F1’：（2，6。5），‘F2’：（2，3。5），‘W1’：（5，6。5），‘W2’：（5，3。5），‘R1’：（9，8），‘R2’：（9，6），‘R3’：（9，4），‘R4’：（9，2）} # 指定頂點繪圖位置# # 4。2 用 NetworkX 求最小費用流# 求最小費用流（demand=v）minFlowCost = nx。min_cost_flow_cost（G1） # 求最小費用流的費用minFlowDict = nx。min_cost_flow（G1） # 求最小費用流# minFlowCost， minFlowDict = nx。network_simplex（G2） # 求最小費用流——與上行等效# 整理邊的標籤，用於繪圖顯示# 資料格式轉換edgeCapacity = nx。get_edge_attributes（G1， ‘weight’）edgeLabel = {} # 邊的標籤for i in edgeCapacity。keys（）： # 整理邊的標籤，用於繪圖顯示 edgeLabel［i］ = f‘w={edgeCapacity［i］：}’ # 邊的容量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））print（“1。 NetworkX 網路與圖（最小費用流最佳化結果）：”） # NetworkX 工具包print（“最小費用：{}”。format（minFlowCost）） # 輸出最小費用的值print（“最小費用流的路徑及流量： ”， minFlowDict） # 輸出最小費用流的途徑和各路徑上的流量print（“最小費用流的路徑：”， edgeLists） # 輸出最小費用流的途徑# 繪製有向網路圖fig， ax = plt。subplots（figsize=（8，6））ax。text（1。2，6。4，“600”，color=‘navy’）ax。text（1。2，3。4，“400”，color=‘navy’）ax。text（9。3，7。9，“200”，color=‘navy’）ax。text（9。3，5。9，“150”，color=‘navy’）ax。text（9。3，3。9，“350”，color=‘navy’）ax。text（9。3，1。9，“300”，color=‘navy’）ax。set_title（“Capacity network with multi source and multi sink”）nx。draw（G1，pos，with_labels=True，node_color=‘skyblue’，node_size=300，font_size=10） # 繪製有向圖，顯示頂點標籤edgeLabel1 = nx。get_edge_attributes（G1， ‘weight’）nx。draw_networkx_nodes（G1， pos， nodelist=［‘F1’，‘F2’］， node_color=‘orange’） # 設定指定頂點的顏色、寬度nx。draw_networkx_nodes（G1， pos， nodelist=［‘W1’，‘W2’］， node_color=‘c’） # 設定指定頂點的顏色、寬度nx。draw_networkx_edge_labels（G1，pos，edgeLabel，font_size=10，label_pos=0。25） # 顯示邊的標籤：‘capacity’，‘weight’ + minCostFlownx。draw_networkx_edges（G1，pos，edgelist=edgeLists，edge_color=‘m’，width=2） # 設定指定邊的顏色、寬度plt。xlim（0。5， 10。5）plt。ylim（1， 9）plt。axis（‘on’）# plt。show（）# # 4。3 用線性規劃求最小費用流# （1） 建立最佳化問題 TransportCost： 求最小值（LpMinimize）transportLP = pulp。LpProblem（“TransportCostProblem”， sense=pulp。LpMinimize） # 定義問題，求最小值# （2） 定義決策變數 f11~f22， w11~w24f11 = pulp。LpVariable（‘F1-W1’， lowBound=0， upBound=600， cat=‘Continuous’） # 定義 f11f12 = pulp。LpVariable（‘F1-W2’， lowBound=0， upBound=600， cat=‘Continuous’） # 定義 f12f21 = pulp。LpVariable（‘F2-W1’， lowBound=0， upBound=400， cat=‘Continuous’） # 定義 f21f22 = pulp。LpVariable（‘F2-W2’， lowBound=0， upBound=400， cat=‘Continuous’） # 定義 f22w11 = pulp。LpVariable（‘W1-R1’， lowBound=0， upBound=200， cat=‘Continuous’） # 定義 w11w21 = pulp。LpVariable（‘W2-R1’， lowBound=0， upBound=200， cat=‘Continuous’） # 定義 w21w12 = pulp。LpVariable（‘W1-R2’， lowBound=0， upBound=150， cat=‘Continuous’） # 定義 w12w22 = pulp。LpVariable（‘W2-R2’， lowBound=0， upBound=150， cat=‘Continuous’） # 定義 w22w13 = pulp。LpVariable（‘W1-R3’， lowBound=0， upBound=350， cat=‘Continuous’） # 定義 w13w23 = pulp。LpVariable（‘W2-R3’， lowBound=0， upBound=350， cat=‘Continuous’） # 定義 w23w14 = pulp。LpVariable（‘W1-R4’， lowBound=0， upBound=300， cat=‘Continuous’） # 定義 w14w24 = pulp。LpVariable（‘W2-R4’， lowBound=0， upBound=300， cat=‘Continuous’） # 定義 w24# （3） 定義目標函式 costtransportLP += （2*f11 + 3*f12 + 3*f21 + f22 + 2*w11 + 6*w12 + 3*w13 + 6*w14 + 4*w21 + 4*w22 + 6*w23 + 5*w24） # 運輸費用# （4） 設定約束條件transportLP += （f11 + f12 <= 600） # 等式約束transportLP += （f21 + f22 <= 400） # 等式約束transportLP += （w11 + w21 == 200） # 等式約束transportLP += （w12 + w22 == 150） # 等式約束transportLP += （w13 + w23 == 350） # 等式約束transportLP += （w14 + w24 == 300） # 等式約束transportLP += （f11 +f21 == w11 + w12 + w13 + w14） # 等式約束transportLP += （f12 +f22 == w21 + w22 + w23 + w24） # 等式約束# （5） 求解線性規劃問題transportLP。solve（）# （6） 輸出最佳化結果print（“2。 PuLP 線性規劃（最小費用的最佳化結果）：”） # PuLP 工具包print（transportLP） # 輸出問題設定引數和條件print（“Optimization result”） # PuLP 工具包for v in transportLP。variables（）： print（v。name， “ = ”， v。varValue） # 輸出每個變數的最優值print（“\n最小運輸費用 = ”， pulp。value（transportLP。objective）） # 輸出最優解的目標函式值plt。show（）

4。4 程式執行結果

1。 NetworkX 網路與圖（最小費用流最佳化結果）：最小費用：5200最小費用流的路徑及流量： {‘F1’： {‘W1’： 600， ‘W2’： 0}， ‘W1’： {‘R1’： 200， ‘R2’： 0， ‘R3’： 350， ‘R4’： 50}， ‘W2’： {‘R1’： 0， ‘R2’： 150， ‘R3’： 0， ‘R4’： 250}， ‘F2’： {‘W1’： 0， ‘W2’： 400}， ‘R1’： {}， ‘R2’： {}， ‘R3’： {}， ‘R4’： {}}最小費用流的路徑： ［（‘F1’， ‘W1’）， （‘W1’， ‘R1’）， （‘W1’， ‘R3’）， （‘W1’， ‘R4’）， （‘W2’， ‘R2’）， （‘W2’， ‘R4’）， （‘F2’， ‘W2’）］2。 PuLP 線性規劃（最小費用的最佳化結果）：MINIMIZE2*F1_W1 + 3*F1_W2 + 3*F2_W1 + 1*F2_W2 + 2*W1_R1 + 6*W1_R2 + 3*W1_R3 + 6*W1_R4 + 4*W2_R1 + 4*W2_R2 + 6*W2_R3 + 5*W2_R4 + 0SUBJECT TO_C1： F1_W1 + F1_W2 <= 600_C2： F2_W1 + F2_W2 <= 400_C3： W1_R1 + W2_R1 = 200_C4： W1_R2 + W2_R2 = 150_C5： W1_R3 + W2_R3 = 350_C6： W1_R4 + W2_R4 = 300_C7： F1_W1 + F2_W1 - W1_R1 - W1_R2 - W1_R3 - W1_R4 = 0_C8： F1_W2 + F2_W2 - W2_R1 - W2_R2 - W2_R3 - W2_R4 = 0VARIABLESF1_W1 <= 600 ContinuousF1_W2 <= 600 ContinuousF2_W1 <= 400 ContinuousF2_W2 <= 400 ContinuousW1_R1 <= 200 ContinuousW1_R2 <= 150 ContinuousW1_R3 <= 350 ContinuousW1_R4 <= 300 ContinuousW2_R1 <= 200 ContinuousW2_R2 <= 150 ContinuousW2_R3 <= 350 ContinuousW2_R4 <= 300 ContinuousOptimization resultF1_W1 = 550。0F1_W2 = 50。0F2_W1 = 0。0F2_W2 = 400。0W1_R1 = 200。0W1_R2 = -0。0W1_R3 = 350。0W1_R4 = -0。0W2_R1 = 0。0W2_R2 = 150。0W2_R3 = 0。0W2_R4 = 300。0最小運輸費用 = 5200。0

5。 案例：多商品流問題

多商品流問題（Multi-Commodity Flow Prolem）是多種商品（物流、人流、資料流等）在具有容量限制的網路中從供應點流到需求點的網路流問題，通常是 NP 問題。多商品流問題的最佳化目標是以最小的成本實現商品在網路中的流通，約束條件主要是每條邊的容量。

多商品流路徑最佳化問題具有廣泛的實際應用，如交通運輸、物流網路、電信網路以及產銷系統。一些實際問題帶有特殊要求，如在電信網路中要考慮時間延遲和可靠性問題，在零擔貨運中需要考慮配貨拼車，有時需要綜合考慮運輸的時間和成本。

5。1 問題描述

將城市 v0 生產的商品 A、B 透過鐵路網分別運送到 城市 v6、v5，商品 A、B 的需求量分別為 6。0、5。0 單位。鐵路網的結構如圖所示，每條線路（邊）上的數值表示該線路的容量和單位運費。求完成商品運輸任務的最小費用的運輸方案。

5。2 問題分析

這是一個多商品流問題，具有 1 個供應點 V0 和 2個需求點 V5、V6。

對於多源多匯的多商品流最小費用流問題，構造一個費用網路 G，網路 G 的各條邊具有容量限制，單位流量的運輸成本為邊的權值 w。源點（供應點）為流量淨輸出，匯點（需求點）為流量淨輸入；中間節點不帶儲存，每種商品的淨流量都為 0。所有線路的商品總流量不超過邊的容量限制。

該問題也是一個典型的線性規劃問題，可以用如下模型描述：

式中：M 表示商品品種，S 表示源點（供應點），T 表示匯點（需求點），w（i，j） 表示路段 （i，j） 的單位流量運輸成本，f（i，j，m） 表示商品 m 在路段 （i，j） 的流量，

NetworkX 工具包中沒有多商品流問題的解決方法，在 Python 其它圖與網路工具包也沒有找到多商品流問題的函式。網路流問題本質上是線性規劃問題，對於上式描述的線性規劃問題，可以用 PuLP工具包求解（參見《Python小白的數學建模課-03。線性規劃》）。

多商品流的目標是各種商品從供應點運送到需求點的總費用最小。定義各商品 m 在各路段 （i，j） 的流量 f（i，j，m） 為決策變數，則目標函式為商品 m 在各路段 （i，j） 的運輸費用之和 ∑ m ∑ i ， j ∈ E w i j f i j 。多商品流的模型主要包含流守恆約束和容量限制。

本案例的問題中，不同商品 A、B 是從同一供應點發出，運送到不同需求點。但本案例的數學模型和例程，並不限定從不同商品從同一供應點發出，也就是說可以適用於多源多匯的多商品流問題。另外，如果如果不同商品在各條邊的運費單價不同，只要相應修改例程的目標函式即可處理。

5.3 程式說明

本程式並不複雜，但有些地方的處理可能會令小白感到困惑，詳細說明如下：

圖的輸入：稀疏有向圖，使用 nx。DiGraph（） 定義有向圖，使用G。add_weighted_edges_from（） 函式以列表向圖中新增多條賦權邊，每個賦權邊以元組 （node1，node2，{‘capacity’：c1， ‘weight’：w1}） 定義屬性 ‘capacity’ 和 ‘weight’。注意必須以關鍵字 ‘capacity’ 表示容量，以 ‘weight’ 表示單位流量的成本。

supplyA、supplyB 表示商品 A、B 的供應量，來自題目要求。注意網路的最大流量必須大於等於各種商品的總供應量或總需求量，否則將沒有可行解。

繪製網路圖，以邊的標籤顯示邊的容量 ‘capacity’ 和單位流量的成本 ‘weight’ 。

用 PuLP 求解多商品流線性規劃問題：

（1） 定義一個線性規劃問題 MCFproblem。

（2）定義決策變數 fA、fB ，並設定決策變數型別和上下限：

fA、fB 都是一維陣列，表示商品 A、B 在網路 G2 各條邊的實際流量。根據題意將決策變數設為連續變數，如果問題要求整車配貨等條件，可以相應地設為整數變數。

fA、fB 的下限為 0，上限應為各條邊的容量。但由於 pulp。LpVariable。dicts 函式中定義上限 upBound 為實數型別，不能是陣列，無法對每個決策變數設定不同的上限值。

因此，在定義決策變數 fA、fB 時，將上限設為所有邊的容量的最大值 maxCapacity。每條邊的具體容量約束，則作為約束條件處理。

G2。edges（） 表示遍歷網路 G2 的邊，因此 fA、fB 是 A、B 在所有邊 edges 的流量：

{（‘v0’， ‘v1’）： FlowA_（‘v0’，_‘v1’）， （‘v0’， ‘v2’）： FlowA_（‘v0’，_‘v2’）， （‘v1’， ‘v3’）： FlowA_（‘v1’，_‘v3’）， （‘v2’， ‘v1’）： FlowA_（‘v2’，_‘v1’）， （‘v2’， ‘v4’）： FlowA_（‘v2’，_‘v4’）， （‘v3’， ‘v4’）： FlowA_（‘v3’，_‘v4’）， （‘v3’， ‘v5’）： FlowA_（‘v3’，_‘v5’）， （‘v3’， ‘v6’）： FlowA_（‘v3’，_‘v6’）， （‘v4’， ‘v1’）： FlowA_（‘v4’，_‘v1’）， （‘v4’， ‘v5’）： FlowA_（‘v4’，_‘v5’）， （‘v4’， ‘v6’）： FlowA_（‘v4’，_‘v6’）}{（‘v0’， ‘v1’）： FlowB_（‘v0’，_‘v1’）， （‘v0’， ‘v2’）： FlowB_（‘v0’，_‘v2’）， （‘v1’， ‘v3’）： FlowB_（‘v1’，_‘v3’）， （‘v2’， ‘v1’）： FlowB_（‘v2’，_‘v1’）， （‘v2’， ‘v4’）： FlowB_（‘v2’，_‘v4’）， （‘v3’， ‘v4’）： FlowB_（‘v3’，_‘v4’）， （‘v3’， ‘v5’）： FlowB_（‘v3’，_‘v5’）， （‘v3’， ‘v6’）： FlowB_（‘v3’，_‘v6’）， （‘v4’， ‘v1’）： FlowB_（‘v4’，_‘v1’）， （‘v4’， ‘v5’）： FlowB_（‘v4’，_‘v5’）， （‘v4’， ‘v6’）： FlowB_（‘v4’，_‘v6’）}

（3）定義目標函式：

目標函式是 A、B 在所有邊 edges 的總運費，即流量 fA、fB 與單位流量成本 ‘weight’的乘積的總和。

需要說明的是：（1）透過 edgeWeight = nx。get_edge_attributes（G2， ‘weight’） 將所有邊的屬性 ‘weight’ 轉換為字典型別，就可以用 for edge in G2。edges 遍歷操作。（2）如果不同商品在各條邊的運費單價不同，只要將目標函式中的 KaTeX parse error： Undefined control sequence： \* at position 8： w（edge）\̲*̲ ［fA（edge）+fB（e… 修改為 KaTeX parse error： Undefined control sequence： \* at position 9： wA（edge）\̲*̲fA（edge）+wB（edg… 即可。

# （3）。 設定目標函式MCFproblem += pulp。lpSum（［edgeWeight［edge］ * （fA［edge］+fB［edge］） for edge in G2。edges］） # 總運輸費用

（4）定義約束條件：

（4）定義約束條件：

多商品流的模型主要包含邊的容量約束和頂點的流守恆約束和兩個方面。

1。邊的容量約束，即每條邊上各種商品流量之和不大於邊的容量。

2。頂點的流守恆約束，分為源點（供應點）、匯點（需求點）和中間節點三種情況：

透過 for node in G2。nodes 可以遍歷網路的所有頂點。

in_degree（node） 計算頂點 node 的入度，入度為 0 的頂點是源點；out_degree（node） 計算頂點 node 的出度，出度為 0 的頂點是匯點。由此可以判斷網路的源點、匯點和中間節點；也可以根據題目直接判斷各中商品的供應點、需求點進行定義。

in_edges（nbunch=node） 返回頂點 node 的所有入邊，out_edges（nbunch=node） 返回頂點 node 的所有出邊。

源點：對於每種商品，所有輸出邊的流量之和不大於該頂點該商品的供應量。對於供應量、需求量相等的問題，也可以將該約束條件設為輸出流量等於供應量。

匯點：對於每種商品，所有輸入邊的流量之和等於該頂點該商品的供應量。案例問題有多個需求點，並對應了不同品種的商品，因此需要分別進行設定。

中間節點：對於每種商品，中間節點的總流入量與總流出量相等。

注意，如果供應點、需求點也是流通線路而不是源點、匯點，則不必分作三種情況，都按照中間節點處理，但對每個節點需要設定每種商品的淨流量。

源點：v0， 出邊：［（‘v0’， ‘v1’）， （‘v0’， ‘v2’）］ 中間點：v1， 入邊：［（‘v0’， ‘v1’）， （‘v2’， ‘v1’）， （‘v4’， ‘v1’）］， 出邊：［（‘v1’， ‘v3’）］ 中間點：v2， 入邊：［（‘v0’， ‘v2’）］， 出邊：［（‘v2’， ‘v1’）， （‘v2’， ‘v4’）］ 中間點：v3， 入邊：［（‘v1’， ‘v3’）］， 出邊：［（‘v3’， ‘v4’）， （‘v3’， ‘v5’）， （‘v3’， ‘v6’）］ 中間點：v4， 入邊：［（‘v2’， ‘v4’）， （‘v3’， ‘v4’）］， 出邊：［（‘v4’， ‘v1’）， （‘v4’， ‘v5’）， （‘v4’， ‘v6’）］ 匯點：v5， 入邊：［（‘v3’， ‘v5’）， （‘v4’， ‘v5’）］ 匯點：v6， 入邊：［（‘v3’， ‘v6’）， （‘v4’， ‘v6’）］

（6）求解規劃問題，輸出最佳化結果

5。4 Python 例程

# mathmodel21_v1。py# Demo21 of mathematical modeling algorithm# Demo of network flow problem optimization with NetworkX# Copyright 2021 YouCans， XUPT# Crated：2021-07-22import numpy as npimport matplotlib。pyplot as plt # 匯入 Matplotlib 工具包import networkx as nx # 匯入 NetworkX 工具包import pulp # 匯入 pulp庫# 5。 多商品流問題 （Multi-commodity Flow Problem）# 5。1 建立有向圖G2 = nx。DiGraph（） # 建立一個有向圖 DiGraphG2。add_edges_from（［（‘v0’，‘v1’，{‘capacity’： 7， ‘weight’： 4}）， （‘v0’，‘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’，‘v5’，{‘capacity’： 10， ‘weight’： 6}）， （‘v3’，‘v6’，{‘capacity’： 10， ‘weight’： 6}）， （‘v4’，‘v1’，{‘capacity’： 2， ‘weight’： 1}）， （‘v4’，‘v5’，{‘capacity’： 5， ‘weight’： 2}）， （‘v4’，‘v6’，{‘capacity’： 5， ‘weight’： 2}）］） # 新增邊的屬性 ‘capacity’， ‘weight’pos={‘v0’：（0，5），‘v1’：（4，2），‘v2’：（4，8），‘v3’：（10，2），‘v4’：（10，8），‘v5’：（15，3），‘v6’：（15，7）} # 指定頂點繪圖位置supplyA = 6。0 # 商品 A 供應量supplyB = 5。0 # 商品 B 供應量print（“Supply A：{}\tSupply B：{}”。format（supplyA，supplyB））# 整理邊的標籤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］：}）’ # 邊的（容量，成本）# 5。2 繪製有向網路圖fig， ax = plt。subplots（figsize=（8，6））nx。draw（G2，pos，with_labels=True，node_color=‘skyblue’，node_size=400，font_size=10） # 繪製有向圖，顯示頂點標籤nx。draw_networkx_nodes（G2， pos， nodelist=［‘v0’］， node_color=‘orange’，node_size=400） # 設定指定頂點的顏色、寬度nx。draw_networkx_nodes（G2， pos， nodelist=［‘v5’，‘v6’］， node_color=‘c’，node_size=400） # 設定指定頂點的顏色、寬度nx。draw_networkx_edge_labels（G2，pos，edgeLabel，font_size=10） # 顯示邊的標籤：‘capacity’，‘weight’ax。set_title（“Multi-commodity Flow Problem by youcans@xupt”）ax。text（-1。8，5。2，“A：{}”。format（supplyA），color=‘m’）ax。text（-1。8，4。6，“B：{}”。format（supplyB），color=‘navy’）ax。text（15。8，7。0，“A：{}”。format（supplyA），color=‘m’）ax。text（15。8，2。8，“B：{}”。format（supplyB），color=‘navy’）plt。xlim（-3， 18）plt。ylim（1， 9）plt。axis（‘on’）# plt。show（YouCans-XUPT）# 5。3 用 PuLP 求解多商品流最小費用問題 （Multi-commodity Flow Problem YouCans-XUPT）edgeWeight = nx。get_edge_attributes（G2， ‘weight’） # ‘weight’， 單位流量的成本edgeCapacity = nx。get_edge_attributes（G2， ‘capacity’） # ‘capacity’， 邊的容量maxCapacity = max（edgeCapacity。values（）） # 邊的容量的最大值print（edgeWeight）print（“max（Weight）”，max（edgeWeight。values（）））print（“max（Capacity）”，max（edgeCapacity。values（）））# （1） 建立最佳化問題 MCFproblem： 求最小值（LpMinimize）MCFproblem = pulp。LpProblem（“MultiCommodityFlowProb”， sense=pulp。LpMinimize） # 定義問題，求最小值# （2） 定義決策變數 fA（edges）， fB（edges）# itemsG2 = ［“A”，“B”］ # 商品種類fA = pulp。LpVariable。dicts（“FlowA”， G2。edges（）， lowBound=0。0， upBound=maxCapacity， cat=‘Continuous’）fB = pulp。LpVariable。dicts（“FlowB”， G2。edges（）， lowBound=0。0， upBound=maxCapacity， cat=‘Continuous’）print（fA）print（fB）# （3）。 設定目標函式MCFproblem += pulp。lpSum（［edgeWeight［edge］ * （fA［edge］+fB［edge］） for edge in G2。edges］） # 總運輸費用# （4） 設定約束條件for edge in G2。edges： # 邊的最大流量約束 MCFproblem += （fA［edge］ + fB［edge］ - edgeCapacity［edge］ <= 0） # edgeCapacity［edge］， 邊的容量for node in G2。nodes： # 頂點的淨流量約束 if G2。in_degree（node） == 0： # 入度為 0，判斷是否為源點 print（“源點：{}， 出邊：{}”。format（node，G2。out_edges（nbunch=node））） MCFproblem += （sum（fA［edge］ for edge in G2。out_edges（nbunch=node）） <= supplyA） # A 供應量約束 MCFproblem += （sum（fB［edge］ for edge in G2。out_edges（nbunch=node）） <= supplyB） # B 供應量約束 elif G2。out_degree（node） == 0： # 出度為 0，判斷是否為匯點 print（“匯點：{}， 入邊：{}”。format（node，G2。in_edges（nbunch=node））） if node==‘v6’： # 題目條件， v6 需求為 B MCFproblem += （sum（fA［edge］ for edge in G2。in_edges（nbunch=node）） == supplyA） # A 需求量約束 if node==‘v5’： # 題目條件， v5 需求為 A MCFproblem += （sum（fB［edge］ for edge in G2。in_edges（nbunch=node）） == supplyB） # B 需求量約束 else： # 中間節點，每種商品都是流量平衡 print（“中間點：{}， 入邊：{}， 出邊：{}”。format（node，G2。in_edges（nbunch=node），G2。out_edges（nbunch=node））） MCFproblem += （sum（fA［edge1］ for edge1 in G2。out_edges（nbunch=node）） - sum（fA［edge2］ for edge2 in G2。in_edges（nbunch=node）） == 0） # 總流出 = 總流入 MCFproblem += （sum（fB［edge1］ for edge1 in G2。out_edges（nbunch=node）） - sum（fB［edge2］ for edge2 in G2。in_edges（nbunch=node）） == 0） # 總流出 = 總流入# （5） 求解線性規劃問題MCFproblem。solve（）# （6） 輸出最佳化結果print（“2。 PuLP 線性規劃（最小費用的最佳化結果）：”） # PuLP 工具包print（MCFproblem） # 輸出問題設定引數和條件print（“Optimization result”） # PuLP 工具包for v in MCFproblem。variables（）： print（v。name， “ = ”， v。varValue） # 輸出每個變數的最優值print（“\n最小運輸費用 = ”， pulp。value（MCFproblem。objective）） # 輸出最優解的目標函式值plt。show（）

5。5 程式執行結果

2。 PuLP 線性規劃（最小費用的最佳化結果）：MultiCommodityFlowProb：MINIMIZE4*FlowA_（‘v0’，_‘v1’） + 4*FlowA_（‘v0’，_‘v2’） + 1*FlowA_（‘v1’，_‘v3’） + 5*FlowA_（‘v2’，_‘v1’） + 4*FlowA_（‘v2’，_‘v4’） + 2*FlowA_（‘v3’，_‘v4’） + 6*FlowA_（‘v3’，_‘v5’） + 6*FlowA_（‘v3’，_‘v6’） + 1*FlowA_（‘v4’，_‘v1’） + 2*FlowA_（‘v4’，_‘v5’） + 2*FlowA_（‘v4’，_‘v6’） + 4*FlowB_（‘v0’，_‘v1’） + 4*FlowB_（‘v0’，_‘v2’） + 1*FlowB_（‘v1’，_‘v3’） + 5*FlowB_（‘v2’，_‘v1’） + 4*FlowB_（‘v2’，_‘v4’） + 2*FlowB_（‘v3’，_‘v4’） + 6*FlowB_（‘v3’，_‘v5’） + 6*FlowB_（‘v3’，_‘v6’） + 1*FlowB_（‘v4’，_‘v1’） + 2*FlowB_（‘v4’，_‘v5’） + 2*FlowB_（‘v4’，_‘v6’） + 0SUBJECT TO_C1： FlowA_（‘v0’，_‘v1’） + FlowB_（‘v0’，_‘v1’） <= 7_C2： FlowA_（‘v0’，_‘v2’） + FlowB_（‘v0’，_‘v2’） <= 8_C3： FlowA_（‘v1’，_‘v3’） + FlowB_（‘v1’，_‘v3’） <= 9_C4： FlowA_（‘v2’，_‘v1’） + FlowB_（‘v2’，_‘v1’） <= 5_C5： FlowA_（‘v2’，_‘v4’） + FlowB_（‘v2’，_‘v4’） <= 9_C6： FlowA_（‘v3’，_‘v4’） + FlowB_（‘v3’，_‘v4’） <= 6_C7： FlowA_（‘v3’，_‘v5’） + FlowB_（‘v3’，_‘v5’） <= 10_C8： FlowA_（‘v3’，_‘v6’） + FlowB_（‘v3’，_‘v6’） <= 10_C9： FlowA_（‘v4’，_‘v1’） + FlowB_（‘v4’，_‘v1’） <= 2_C10： FlowA_（‘v4’，_‘v5’） + FlowB_（‘v4’，_‘v5’） <= 5_C11： FlowA_（‘v4’，_‘v6’） + FlowB_（‘v4’，_‘v6’） <= 5_C12： FlowA_（‘v0’，_‘v1’） + FlowA_（‘v0’，_‘v2’） <= 6_C13： FlowB_（‘v0’，_‘v1’） + FlowB_（‘v0’，_‘v2’） <= 5_C14： - FlowA_（‘v0’，_‘v1’） + FlowA_（‘v1’，_‘v3’） - FlowA_（‘v2’，_‘v1’） - FlowA_（‘v4’，_‘v1’） = 0_C15： - FlowB_（‘v0’，_‘v1’） + FlowB_（‘v1’，_‘v3’） - FlowB_（‘v2’，_‘v1’） - FlowB_（‘v4’，_‘v1’） = 0_C16： - FlowA_（‘v0’，_‘v2’） + FlowA_（‘v2’，_‘v1’） + FlowA_（‘v2’，_‘v4’） = 0_C17： - FlowB_（‘v0’，_‘v2’） + FlowB_（‘v2’，_‘v1’） + FlowB_（‘v2’，_‘v4’） = 0_C18： - FlowA_（‘v1’，_‘v3’） + FlowA_（‘v3’，_‘v4’） + FlowA_（‘v3’，_‘v5’） + FlowA_（‘v3’，_‘v6’） = 0_C19： - FlowB_（‘v1’，_‘v3’） + FlowB_（‘v3’，_‘v4’） + FlowB_（‘v3’，_‘v5’） + FlowB_（‘v3’，_‘v6’） = 0_C20： - FlowA_（‘v2’，_‘v4’） - FlowA_（‘v3’，_‘v4’） + FlowA_（‘v4’，_‘v1’） + FlowA_（‘v4’，_‘v5’） + FlowA_（‘v4’，_‘v6’） = 0_C21： - FlowB_（‘v2’，_‘v4’） - FlowB_（‘v3’，_‘v4’） + FlowB_（‘v4’，_‘v1’） + FlowB_（‘v4’，_‘v5’） + FlowB_（‘v4’，_‘v6’） = 0_C22： FlowB_（‘v3’，_‘v5’） + FlowB_（‘v4’，_‘v5’） = 5_C23： FlowA_（‘v3’，_‘v6’） + FlowA_（‘v4’，_‘v6’） = 6VARIABLESFlowA_（‘v0’，_‘v1’） <= 10 ContinuousFlowA_（‘v0’，_‘v2’） <= 10 ContinuousFlowA_（‘v1’，_‘v3’） <= 10 ContinuousFlowA_（‘v2’，_‘v1’） <= 10 ContinuousFlowA_（‘v2’，_‘v4’） <= 10 ContinuousFlowA_（‘v3’，_‘v4’） <= 10 ContinuousFlowA_（‘v3’，_‘v5’） <= 10 ContinuousFlowA_（‘v3’，_‘v6’） <= 10 ContinuousFlowA_（‘v4’，_‘v1’） <= 10 ContinuousFlowA_（‘v4’，_‘v5’） <= 10 ContinuousFlowA_（‘v4’，_‘v6’） <= 10 ContinuousFlowB_（‘v0’，_‘v1’） <= 10 ContinuousFlowB_（‘v0’，_‘v2’） <= 10 ContinuousFlowB_（‘v1’，_‘v3’） <= 10 ContinuousFlowB_（‘v2’，_‘v1’） <= 10 ContinuousFlowB_（‘v2’，_‘v4’） <= 10 ContinuousFlowB_（‘v3’，_‘v4’） <= 10 ContinuousFlowB_（‘v3’，_‘v5’） <= 10 ContinuousFlowB_（‘v3’，_‘v6’） <= 10 ContinuousFlowB_（‘v4’，_‘v1’） <= 10 ContinuousFlowB_（‘v4’，_‘v5’） <= 10 ContinuousFlowB_（‘v4’，_‘v6’） <= 10 ContinuousOptimization resultFlowA_（‘v0’，_‘v1’） = 6。0FlowA_（‘v0’，_‘v2’） = -0。0FlowA_（‘v1’，_‘v3’） = 6。0FlowA_（‘v2’，_‘v1’） = 0。0FlowA_（‘v2’，_‘v4’） = 0。0FlowA_（‘v3’，_‘v4’） = 5。0FlowA_（‘v3’，_‘v5’） = 0。0FlowA_（‘v3’，_‘v6’） = 1。0FlowA_（‘v4’，_‘v1’） = 0。0FlowA_（‘v4’，_‘v5’） = 0。0FlowA_（‘v4’，_‘v6’） = 5。0FlowB_（‘v0’，_‘v1’） = 1。0FlowB_（‘v0’，_‘v2’） = 4。0FlowB_（‘v1’，_‘v3’） = 1。0FlowB_（‘v2’，_‘v1’） = 0。0FlowB_（‘v2’，_‘v4’） = 4。0FlowB_（‘v3’，_‘v4’） = 1。0FlowB_（‘v3’，_‘v5’） = 0。0FlowB_（‘v3’，_‘v6’） = 0。0FlowB_（‘v4’，_‘v1’） = 0。0FlowB_（‘v4’，_‘v5’） = 5。0FlowB_（‘v4’，_‘v6’） = 0。0最小運輸費用 = 105。0

【本節完】

————————————————

版權宣告：本文為CSDN博主「youcans」的原創文章，遵循CC 4。0 BY-SA版權協議，轉載請附上原文出處連結及本宣告。

原文連結：https：//blog。csdn。net/youcans/article/details/118882174