第11章圖與網(wǎng)絡(luò)模型2

1、管管 理理 運運 籌籌 學(xué)學(xué)1 第十一章圖與網(wǎng)絡(luò)模型第十一章圖與網(wǎng)絡(luò)模型1 1圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念2 2最短路問題最短路問題3 3最小生成樹問題最小生成樹問題4 4最大流問題最大流問題5 5最小費用最大流問題最小費用最大流問題管管 理理 運運 籌籌 學(xué)學(xué)24 4最大流問題最大流問題最大流問題：給一個帶收發(fā)點的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容量，最大流問題：給一個帶收發(fā)點的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容量，在不超過每條弧的容量的前提下，求出從發(fā)點到收點的最大流量。在不超過每條弧的容量的前提下，求出從發(fā)點到收點的最大流量。一、最大流的數(shù)學(xué)模型一、最大流的數(shù)學(xué)模型 例例6 某石油公司擁有一

2、個管道網(wǎng)絡(luò)，使用這個網(wǎng)絡(luò)可以把石油從采地某石油公司擁有一個管道網(wǎng)絡(luò)，使用這個網(wǎng)絡(luò)可以把石油從采地運送到一些銷售點，這個網(wǎng)絡(luò)的一部分如下圖所示。由于管道的直徑運送到一些銷售點，這個網(wǎng)絡(luò)的一部分如下圖所示。由于管道的直徑的變化，它的各段管道（的變化，它的各段管道（vi,vj）的流量）的流量cij（容量）也是不一樣的。（容量）也是不一樣的。cij的的單位為萬加侖單位為萬加侖/小時。如果使用這個網(wǎng)絡(luò)系統(tǒng)從采地小時。如果使用這個網(wǎng)絡(luò)系統(tǒng)從采地 v1向銷地向銷地 v7運送石運送石油，問每小時能運送多少加侖石油？油，問每小時能運送多少加侖石油？v563522241263v1v2v7v4v3v6圖圖11-26

3、管管 理理 運運 籌籌 學(xué)學(xué)34 4最大流問題最大流問題 我們可以為此例題建立線性規(guī)劃數(shù)學(xué)模型：我們可以為此例題建立線性規(guī)劃數(shù)學(xué)模型： 設(shè)弧設(shè)弧(vi,vj)上流量為上流量為fij，網(wǎng)絡(luò)上的總的流量為，網(wǎng)絡(luò)上的總的流量為F，則有：，則有：1412232514434647234335362535573646675767471214,1,2,6;1,2,70,1,2,6;1,2,712ijijijmaxF = fffffffffffffffffffffffffcijfij目標(biāo)函數(shù)：約束條件：管管 理理 運運 籌籌 學(xué)學(xué)4P9-2 max (5) 0 , (6) 0 (7)ijjijjijijfsu

4、bject tofisxxis tfitxu當(dāng)當(dāng)當(dāng)管管 理理 運運 籌籌 學(xué)學(xué)54 4最大流問題最大流問題 在這個線性規(guī)劃模型中，其約束條件中的前在這個線性規(guī)劃模型中，其約束條件中的前6 6個方程表示個方程表示了網(wǎng)絡(luò)中的流量必須滿足守恒條件，發(fā)點的流出量必須等于了網(wǎng)絡(luò)中的流量必須滿足守恒條件，發(fā)點的流出量必須等于收點的總流入量；其余的點稱之為中間點，它的總流入量必收點的總流入量；其余的點稱之為中間點，它的總流入量必須等于總流出量。其后面幾個約束條件表示對每一條弧須等于總流出量。其后面幾個約束條件表示對每一條弧(v(vi i,v,vj j) )的流量的流量fij要滿足流量的可行條件，應(yīng)小于等于弧

5、要滿足流量的可行條件，應(yīng)小于等于弧(v(vi i,v,vj j) )的容的容量量c cijij，并大于等于零，即，并大于等于零，即0f0fijij c cijij。我們把滿足守恒條件。我們把滿足守恒條件及流量可行條件的一組網(wǎng)絡(luò)流及流量可行條件的一組網(wǎng)絡(luò)流 ffijij 稱之為可行流，（即線性稱之為可行流，（即線性規(guī)劃的可行解），可行流中一組流量最大（也即發(fā)出點總流規(guī)劃的可行解），可行流中一組流量最大（也即發(fā)出點總流出量最大）的稱之為最大流（即線性規(guī)劃的最優(yōu)解）。出量最大）的稱之為最大流（即線性規(guī)劃的最優(yōu)解）。 我們把例我們把例6 6的數(shù)據(jù)代入以上線性規(guī)劃模型，用的數(shù)據(jù)代入以上線性規(guī)劃模型，用“

6、管理運籌管理運籌學(xué)軟件學(xué)軟件”，馬上得到以下的結(jié)果：，馬上得到以下的結(jié)果：f f1212=5=5，f f1414=5=5，f f2323=2=2，f f2525=3=3，f f4343=2=2，f f4646=1=1，f f4747=2=2，f f3535=2=2，f f3636=2=2，f f5757=5=5，f f6767=3=3。最優(yōu)值。最優(yōu)值（最大流量）（最大流量）=10=10。管管 理理 運運 籌籌 學(xué)學(xué)6 4 4最大流問題最大流問題二、最大流問題網(wǎng)絡(luò)圖論的解法二、最大流問題網(wǎng)絡(luò)圖論的解法 對網(wǎng)絡(luò)上弧的容量的表示作改進(jìn)。為省去弧的方向，如下圖對網(wǎng)絡(luò)上弧的容量的表示作改進(jìn)。為省去弧的方

7、向，如下圖: (a)和和(b)、(c)和和(d)的意義相同。的意義相同。 用以上方法對例用以上方法對例6的圖的容量標(biāo)號作改進(jìn)，得下圖的圖的容量標(biāo)號作改進(jìn)，得下圖vivjvivjcij0（a）（b） cijcijvivj（cji）（c）vivj cij cji（d）63522241263v1v2v5v7v4v3v600000000000管管 理理 運運 籌籌 學(xué)學(xué)7 4 4最大流問題最大流問題 求最大流的基本算法求最大流的基本算法（1）找出一條從發(fā)點到收點的路，在這條路上的每一條弧順流方向的容）找出一條從發(fā)點到收點的路，在這條路上的每一條弧順流方向的容量都大于零。如果不存在這樣的路，則已經(jīng)求得最

8、大流。量都大于零。如果不存在這樣的路，則已經(jīng)求得最大流。（2）找出這條路上各條弧的最小的順流的容量）找出這條路上各條弧的最小的順流的容量pf，通過這條路增加網(wǎng)絡(luò)，通過這條路增加網(wǎng)絡(luò)的流量的流量pf。（3）在這條路上，減少每一條弧的順流容量）在這條路上，減少每一條弧的順流容量pf ，同時增加這些弧的逆流，同時增加這些弧的逆流容量容量pf，返回步驟（，返回步驟（1）。）。 用此方法對例用此方法對例6求解：求解： 第一次迭代：選擇路為第一次迭代：選擇路為v1 v4 v7 ?；。??；。?v4 , v7 ）的順流容量為）的順流容量為2，決定了決定了pf=2，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：，改進(jìn)的網(wǎng)絡(luò)流量圖如下

9、圖：63522241263v1v2v5v7v4v3v6000000000004202管管 理理 運運 籌籌 學(xué)學(xué)84 4最大流問題最大流問題 第二次迭代：選擇路為第二次迭代：選擇路為v1 v2 v5 v7 ?；。??；。?v2 , v5 ）的順流容量為）的順流容量為3，決定了，決定了pf=3，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖： 第三次迭代：選擇路為第三次迭代：選擇路為v1 v4 v6 v7 ?；。ā；。?v4 , v6 ）的順流容量為）的順流容量為1，決定了，決定了pf=1，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：635222413v1v2v5v7v4v3v600000

10、00042022033303222413v1v2v5v7v4v3v600000042022033333013管管 理理 運運 籌籌 學(xué)學(xué)9 第四次迭代：選擇路為第四次迭代：選擇路為v1 v4 v3 v6 v7 ?；。??；。?v3 , v6 ）的順流容）的順流容量為量為2，決定了，決定了pf=2，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖： 第五次迭代：選擇路為第五次迭代：選擇路為v1 v2 v3 v5 v7 ?；。ā；。?v2 , v3 ）的順流容）的順流容量為量為2，決定了，決定了pf=2，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：22243v1v2v5v7v4v3v61000

11、01203203335031200231322v1v2v5v7v4v3v610120203335012023131500202054 4最大流問題最大流問題管管 理理 運運 籌籌 學(xué)學(xué)10 經(jīng)過第五次迭代后在圖中已經(jīng)找不到從發(fā)點到收點的一條路，路經(jīng)過第五次迭代后在圖中已經(jīng)找不到從發(fā)點到收點的一條路，路上的每一條弧順流容量都大于零，運算停止。得到最大流量為上的每一條弧順流容量都大于零，運算停止。得到最大流量為10。 最大流量圖如下圖：最大流量圖如下圖：22v1v2v5v7v4v3v61235223554 4最大流問題最大流問題 “管理運籌學(xué)軟件管理運籌學(xué)軟件”中還有專門的子程序用于解決最大流問題

12、。中還有專門的子程序用于解決最大流問題。管管 理理 運運 籌籌 學(xué)學(xué)11管管 理理 運運 籌籌 學(xué)學(xué)12管管 理理 運運 籌籌 學(xué)學(xué)13管管 理理 運運 籌籌 學(xué)學(xué)14管管 理理 運運 籌籌 學(xué)學(xué)15管管 理理 運運 籌籌 學(xué)學(xué)16管管 理理 運運 籌籌 學(xué)學(xué)17管管 理理 運運 籌籌 學(xué)學(xué)18管管 理理 運運 籌籌 學(xué)學(xué)19管管 理理 運運 籌籌 學(xué)學(xué)20管管 理理 運運 籌籌 學(xué)學(xué)21管管 理理 運運 籌籌 學(xué)學(xué)22管管 理理 運運 籌籌 學(xué)學(xué)23管管 理理 運運 籌籌 學(xué)學(xué)24管管 理理 運運 籌籌 學(xué)學(xué)25管管 理理 運運 籌籌 學(xué)學(xué)26管管 理理 運運 籌籌 學(xué)學(xué)27管管 理理 運運

13、 籌籌 學(xué)學(xué)28管管 理理 運運 籌籌 學(xué)學(xué)29管管 理理 運運 籌籌 學(xué)學(xué)30管管 理理 運運 籌籌 學(xué)學(xué)31管管 理理 運運 籌籌 學(xué)學(xué)32管管 理理 運運 籌籌 學(xué)學(xué)33管管 理理 運運 籌籌 學(xué)學(xué)34管管 理理 運運 籌籌 學(xué)學(xué)35管管 理理 運運 籌籌 學(xué)學(xué)36管管 理理 運運 籌籌 學(xué)學(xué)37管管 理理 運運 籌籌 學(xué)學(xué)38管管 理理 運運 籌籌 學(xué)學(xué)39管管 理理 運運 籌籌 學(xué)學(xué)40管管 理理 運運 籌籌 學(xué)學(xué)41管管 理理 運運 籌籌 學(xué)學(xué)42管管 理理 運運 籌籌 學(xué)學(xué)435 5最小費用最大流問題最小費用最大流問題 最小費用最大流問題：給了一個帶收發(fā)點的網(wǎng)絡(luò)，對每一條弧最小費

14、用最大流問題：給了一個帶收發(fā)點的網(wǎng)絡(luò)，對每一條?。╲i,vj），除了給出容量），除了給出容量cij外，還給出了這條弧的單位流量的費用外，還給出了這條弧的單位流量的費用bij，要，要求一個最大流求一個最大流F，并使得總運送費用最小。，并使得總運送費用最小。一、最小費用最大流的數(shù)學(xué)模型一、最小費用最大流的數(shù)學(xué)模型 例例7 由于輸油管道的長短不一，所以在例由于輸油管道的長短不一，所以在例6中每段管道（中每段管道（ vi,vj ）除）除了有不同的流量限制了有不同的流量限制cij外，還有不同的單位流量的費用外，還有不同的單位流量的費用bij ，cij的單位為萬的單位為萬加侖加侖/小時，小時， bij的單

15、位為百元的單位為百元/萬加侖。如圖。從采地萬加侖。如圖。從采地 v1向銷地向銷地 v7運送石運送石油，怎樣運送才能運送最多的石油并使得總的運送費用最??？求出最大流油，怎樣運送才能運送最多的石油并使得總的運送費用最??？求出最大流量和最小費用。量和最小費用。(6,6)(3,4)(5,7)(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)管管 理理 運運 籌籌 學(xué)學(xué)445 5最小費用最大流問題最小費用最大流問題 這個最小費用最大流問題也是一個線性規(guī)劃的問題。這個最小費用最大流問題也是一個線性規(guī)劃的問題。 解：我們用線性規(guī)劃來求解此題，可以分兩

16、步走。解：我們用線性規(guī)劃來求解此題，可以分兩步走。 第一步，先求出此網(wǎng)絡(luò)圖中的最大流量第一步，先求出此網(wǎng)絡(luò)圖中的最大流量F，這已在例，這已在例6中建中建立了線性規(guī)劃的模型，通過管理運籌學(xué)軟件已經(jīng)獲得結(jié)果。立了線性規(guī)劃的模型，通過管理運籌學(xué)軟件已經(jīng)獲得結(jié)果。 第二步，在最大流量第二步，在最大流量F的所有解中，找出一個最小費用的的所有解中，找出一個最小費用的解，我們來建立第二步中的線性規(guī)劃模型如下：解，我們來建立第二步中的線性規(guī)劃模型如下： 仍然設(shè)?。ㄈ匀辉O(shè)弧（vi,vj）上的流量為）上的流量為fij，這時已知網(wǎng)絡(luò)中最大流量，這時已知網(wǎng)絡(luò)中最大流量為為F，只要在例，只要在例6的約束條件上，再加上總

17、流量必須等于的約束條件上，再加上總流量必須等于F的約的約束條件：束條件：f12=f14=F,即得此線性規(guī)劃的約束條件，此線性規(guī)劃的即得此線性規(guī)劃的約束條件，此線性規(guī)劃的目標(biāo)函數(shù)顯然是求其流量的最小費用目標(biāo)函數(shù)顯然是求其流量的最小費用 。 由此得到線性規(guī)劃模型如下：由此得到線性規(guī)劃模型如下：(,)ijijijvvAfb管管 理理 運運 籌籌 學(xué)學(xué)455 5最小費用最大流問題最小費用最大流問題 1214252343(,)355736464767121412232514434647234335362535573646675767471214min63452473384. .10,(1,2,6;iji

18、jijv vAijijfbfffffffffffstffFfffffffffffffffffffffffcij2,3,7),0,(1,2,6;2,3,7),ijfij管管 理理 運運 籌籌 學(xué)學(xué)46( , )P93min (8) - 0 , 0 , (10) ijiji jEijjijjijijc xsubject tof if isxxif is tf if itxui jE管管 理理 運運 籌籌 學(xué)學(xué)475 5最小費用最大流問題最小費用最大流問題 用管理運籌學(xué)軟件，可求得如下結(jié)果：用管理運籌學(xué)軟件，可求得如下結(jié)果：f f1212=4,f=4,f1414=6,=6,f f2525=3,f=3

19、,f2323=1,f=1,f4343=3,F=3,F5757=5,f=5,f3636=2,f=2,f4646=1,f=1,f4747=2,f=2,f6767=3,f=3,f3535=2=2。其最。其最優(yōu)值優(yōu)值( (最小費用最小費用)=145)=145。對照前面例。對照前面例6 6的結(jié)果，可對最小費用最的結(jié)果，可對最小費用最大流的概念有一個深刻的理解。大流的概念有一個深刻的理解。 如果我們把例如果我們把例7 7的問題改為：每小時運送的問題改為：每小時運送6 6萬加侖的石油萬加侖的石油從采地從采地v v1 1到銷地到銷地v v7 7最小費用是多少？應(yīng)怎樣運送？這就變成了最小費用是多少？應(yīng)怎樣運送？

20、這就變成了一個最小費用流的問題。一般來說，所謂最小費用流的問題一個最小費用流的問題。一般來說，所謂最小費用流的問題就是：在給定了收點和發(fā)點并對每條弧就是：在給定了收點和發(fā)點并對每條弧(v(vi i,v,vj j) )賦權(quán)以容量賦權(quán)以容量c cijij及單位費用及單位費用b bijij的網(wǎng)絡(luò)中，求一個給定值的網(wǎng)絡(luò)中，求一個給定值f f的流量的最小費用，的流量的最小費用，這個給定值這個給定值f f的流量應(yīng)小于等于最大流量的流量應(yīng)小于等于最大流量F F，否則無解。求最，否則無解。求最小費用流的問題的線性規(guī)劃的模型只要把最小費用最大流模小費用流的問題的線性規(guī)劃的模型只要把最小費用最大流模型中的約束條件

21、中的發(fā)點流量型中的約束條件中的發(fā)點流量F F改為改為f f即可。在例即可。在例6 6中只要把中只要把f f1212+f+f1414=F=F改為改為f f1212+f+f1414=f=6=f=6得到了最小費用流的線性規(guī)劃的模型得到了最小費用流的線性規(guī)劃的模型了。了。管管 理理 運運 籌籌 學(xué)學(xué)485 5最小費用最大流問題最小費用最大流問題二、最小費用最大流的網(wǎng)絡(luò)圖論解法二、最小費用最大流的網(wǎng)絡(luò)圖論解法對網(wǎng)絡(luò)上?。▽W(wǎng)絡(luò)上?。╲i,vj）的（）的（cij,bij）的表示作如下改動，用）的表示作如下改動，用(b)來表示來表示(a)。用上述方法對例用上述方法對例7中的圖形進(jìn)行改進(jìn)，得圖如下頁：中的圖形

22、進(jìn)行改進(jìn)，得圖如下頁：vivjvivj（cij,bij ）（0,-bij ）（a）（b）（cij,bij ）（cij,bij ）vivj（cji,bji ）（cij,bij ）vivj（cji,bji ）（0,-bji)（0,-bji)（c）（d）管管 理理 運運 籌籌 學(xué)學(xué)495 5最小費用最大流問題最小費用最大流問題 求最小費用最大流的基本算法求最小費用最大流的基本算法 在對弧的標(biāo)號作了改進(jìn)的網(wǎng)絡(luò)圖上求最小費用最大流的基本算法與求在對弧的標(biāo)號作了改進(jìn)的網(wǎng)絡(luò)圖上求最小費用最大流的基本算法與求最大流的基本算法完全一樣，不同的只是在步驟（最大流的基本算法完全一樣，不同的只是在步驟（1）中要選擇一

23、條總的）中要選擇一條總的單位費用最小的路，而不是包含邊數(shù)最小的路。單位費用最小的路，而不是包含邊數(shù)最小的路。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)(0,-3)(0,-8)(0,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(0,-4)（0,-3）圖圖11-2811-28管管 理理 運運 籌籌 學(xué)學(xué)505 5最小費用最大流問題最小費用最大流問題用上述方法對例用上述方法對例7求解：求解： 第一次迭代：找到最短路第一次迭代：找到最短路v1 v4 v6 v7。第一次迭代后

24、總流量為第一次迭代后總流量為1，總，總費用費用10。v5(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(2,8)（3,2）v1v2v7v4v3v6(5,3)(1,-3)(0,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）圖圖11-2911-29管管 理理 運運 籌籌 學(xué)學(xué)515 5最小費用最大流問題最小費用最大流問題第二次迭代：找到最短路第二次迭代：找到最短路v1 v4 v7。第二次迭代后總流量為第二次迭代后總流量為3，總費用，總費用32。(6,6)(3,4)(5,7)(2,5)(0,-4)（

25、2,3）(3,4)(0,3)(0,8)（3,2）v1v2v5v7v4v3v6(3,3)(3,-3)(2,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）圖圖11-3011-30管管 理理 運運 籌籌 學(xué)學(xué)525 5最小費用最大流問題最小費用最大流問題第三次迭代：找到最短路第三次迭代：找到最短路v1 v4 v3 v6 v7 。第三次迭代后總流量為第三次迭代后總流量為5，總費用，總費用56。(6,6)(3,4)(5,7)(2,5)(0,-4)（0,3）(1,4)(0,3)(0,8)（1,2）v1v2v5v7v4v3v6(1,3)(5,

26、-3)(2,-8)(1,-3)（2,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(3,-4)（2,-3）圖圖11-3111-31管管 理理 運運 籌籌 學(xué)學(xué)535 5最小費用最大流問題最小費用最大流問題第四次迭代：找到最短路第四次迭代：找到最短路v1 v4 v3 v5 v7 。第四次迭代后總流量為第四次迭代后總流量為6，總費用，總費用72。(6,6)(3,4)(4,7)(2,5)(1,-4)（0,3）(1,4)(0,3)(0,8)（0,2）v1v2v5v7v4v3v6(1,3)(6,-3)(2,-8)(1,-3)（3,-2）(0,-6)(0,-4)(0,-5)（1,4）(1

27、,-7)(3,-4)（2,-3）圖圖11-3211-32管管 理理 運運 籌籌 學(xué)學(xué)545 5最小費用最大流問題最小費用最大流問題 第五次迭代：找到最短路第五次迭代：找到最短路v1 v2 v5 v7 。第五次迭代后總流量為第五次迭代后總流量為9，總，總費用費用123。(3,6)(0,4)(1,7)(2,5)(1,-4)（0,3）(1,4)(0,3)(0,8)（0,2）v1v2v5v7v4v3v6(0,3)(6,-3)(2,-8)(1,-3)（3,-2）(3,-6)(3,-4)(0,-5)（1,4）(4,-7)(3,-4)（2,-3）圖圖11-3311-33管管 理理 運運 籌籌 學(xué)學(xué)555 5

28、最小費用最大流問題最小費用最大流問題 第六次迭代：找到最短路第六次迭代：找到最短路v1 v2 v3 v5 v7 。第六次迭代后總流量為第六次迭代后總流量為10，總費用，總費用145。已經(jīng)找不到從。已經(jīng)找不到從v1到到v7的每條弧容量都大于零的路了，故的每條弧容量都大于零的路了，故已求得最小費用最大流了。已求得最小費用最大流了。(3,6)(0,4)(1,7)(2,5)(1,-4)（0,3）(1,4)(0,3)(0,8)（0,2）v1v2v5v7v4v3v6(0,3)(6,-3)(2,-8)(1,-3)（3,-2）(3,-6)(3,-4)(0,-5)（1,4）(4,-7)(3,-4)（2,-3）圖

29、圖11-3411-34管管 理理 運運 籌籌 學(xué)學(xué)565 5最小費用最大流問題最小費用最大流問題 如果對例如果對例7求一個最小費用流的問題：每小時運送求一個最小費用流的問題：每小時運送6萬加侖石油從萬加侖石油從v1到到v7的最小費用是多少，或者每小時運送的最小費用是多少，或者每小時運送7萬加侖呢？我們可以從第四次迭萬加侖呢？我們可以從第四次迭代及圖代及圖11-32即可得到運送即可得到運送6萬加侖最小費用萬加侖最小費用72百元，其運送方式通過比較百元，其運送方式通過比較圖圖11-28及圖及圖11-32即得圖即得圖11-36所示。所示。 至于每小時運送至于每小時運送7萬加侖，我們可以在圖萬加侖，我們可以在圖11-36的基礎(chǔ)上，再按第五次的基礎(chǔ)上，再按第五次迭代所選的最短路運送迭代所選的最短路運送1萬加侖即得最小費用：萬加侖即得最小費用：72+1*17=89百元，其運送百元，其運送方式如圖方式如圖11-37所示。所示。35123126v1v2v5v4v3v610342v710第六次迭代第六次迭代后總流量后總流量圖圖11-35管管 理理 運運 籌籌 學(xué)學(xué)575 5最小費用最大流問題最小費用最大流問題 123126v1v2v5v4v3v6631v7圖圖11-3612123126v1v2v5v4v3v6311v7圖圖11-37注：注：“管理運籌學(xué)軟