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

1、管管 理理 運(yùn)運(yùn) 籌籌 學(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最小費(fèi)用最大流問題最小費(fèi)用最大流問題管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)24 4最大流問題最大流問題最大流問題：給一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容量，最大流問題：給一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容量，在不超過每條弧的容量的前提下，求出從發(fā)點(diǎn)到收點(diǎn)的最大流量。在不超過每條弧的容量的前提下，求出從發(fā)點(diǎn)到收點(diǎn)的最大流量。一、最大流的數(shù)學(xué)模型一、最大流的數(shù)學(xué)模型 例例6 某石油公司擁有一

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

3、管管 理理 運(yùn)運(yùn) 籌籌 學(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ù)：約束條件：管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)4P9-2 max (5) 0 , (6) 0 (7)ijjijjijijfsu

4、bject tofisxxis tfitxu當(dāng)當(dāng)當(dāng)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)54 4最大流問題最大流問題 在這個(gè)線性規(guī)劃模型中，其約束條件中的前在這個(gè)線性規(guī)劃模型中，其約束條件中的前6 6個(gè)方程表示個(gè)方程表示了網(wǎng)絡(luò)中的流量必須滿足守恒條件，發(fā)點(diǎn)的流出量必須等于了網(wǎng)絡(luò)中的流量必須滿足守恒條件，發(fā)點(diǎn)的流出量必須等于收點(diǎn)的總流入量；其余的點(diǎn)稱之為中間點(diǎn)，它的總流入量必收點(diǎn)的總流入量；其余的點(diǎn)稱之為中間點(diǎn)，它的總流入量必須等于總流出量。其后面幾個(gè)約束條件表示對(duì)每一條弧須等于總流出量。其后面幾個(gè)約束條件表示對(duì)每一條弧(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ā)出點(diǎn)總流規(guī)劃的可行解），可行流中一組流量最大（也即發(fā)出點(diǎn)總流出量最大）的稱之為最大流（即線性規(guī)劃的最優(yōu)解）。出量最大）的稱之為最大流（即線性規(guī)劃的最優(yōu)解）。 我們把例我們把例6 6的數(shù)據(jù)代入以上線性規(guī)劃模型，用的數(shù)據(jù)代入以上線性規(guī)劃模型，用“

6、管理運(yùn)籌管理運(yùn)籌學(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。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)6 4 4最大流問題最大流問題二、最大流問題網(wǎng)絡(luò)圖論的解法二、最大流問題網(wǎng)絡(luò)圖論的解法 對(duì)網(wǎng)絡(luò)上弧的容量的表示作改進(jìn)。為省去弧的方向，如下圖對(duì)網(wǎng)絡(luò)上弧的容量的表示作改進(jìn)。為省去弧的方

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

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

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

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

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

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

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

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

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

18、jijv vAijijfbfffffffffffstffFfffffffffffffffffffffffcij2,3,7),0,(1,2,6;2,3,7),ijfij管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)46( , )P93min (8) - 0 , 0 , (10) ijiji jEijjijjijijc xsubject tof if isxxif is tf if itxui jE管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)475 5最小費(fèi)用最大流問題最小費(fèi)用最大流問題 用管理運(yùn)籌學(xué)軟件，可求得如下結(jié)果：用管理運(yùn)籌學(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)值( (最小費(fèi)用最小費(fèi)用)=145)=145。對(duì)照前面例。對(duì)照前面例6 6的結(jié)果，可對(duì)最小費(fèi)用最的結(jié)果，可對(duì)最小費(fèi)用最大流的概念有一個(gè)深刻的理解。大流的概念有一個(gè)深刻的理解。 如果我們把例如果我們把例7 7的問題改為：每小時(shí)運(yùn)送的問題改為：每小時(shí)運(yùn)送6 6萬加侖的石油萬加侖的石油從采地從采地v v1 1到銷地到銷地v v7 7最小費(fèi)用是多少？應(yīng)怎樣運(yùn)送？這就變成了最小費(fèi)用是多少？應(yīng)怎樣運(yùn)送？

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

21、中的發(fā)點(diǎn)流量型中的約束條件中的發(fā)點(diǎn)流量F F改為改為f f即可。在例即可。在例6 6中只要把中只要把f f1212+f+f1414=F=F改為改為f f1212+f+f1414=f=6=f=6得到了最小費(fèi)用流的線性規(guī)劃的模型得到了最小費(fèi)用流的線性規(guī)劃的模型了。了。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)485 5最小費(fèi)用最大流問題最小費(fèi)用最大流問題二、最小費(fèi)用最大流的網(wǎng)絡(luò)圖論解法二、最小費(fèi)用最大流的網(wǎng)絡(luò)圖論解法對(duì)網(wǎng)絡(luò)上?。▽?duì)網(wǎng)絡(luò)上弧（vi,vj）的（）的（cij,bij）的表示作如下改動(dòng)，用）的表示作如下改動(dòng)，用(b)來表示來表示(a)。用上述方法對(duì)例用上述方法對(duì)例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）管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)495 5最小費(fèi)用最大流問題最小費(fèi)用最大流問題 求最小費(fèi)用最大流的基本算法求最小費(fèi)用最大流的基本算法 在對(duì)弧的標(biāo)號(hào)作了改進(jìn)的網(wǎng)絡(luò)圖上求最小費(fèi)用最大流的基本算法與求在對(duì)弧的標(biāo)號(hào)作了改進(jìn)的網(wǎng)絡(luò)圖上求最小費(fèi)用最大流的基本算法與求最大流的基本算法完全一樣，不同的只是在步驟（最大流的基本算法完全一樣，不同的只是在步驟（1）中要選擇一

23、條總的）中要選擇一條總的單位費(fèi)用最小的路，而不是包含邊數(shù)最小的路。單位費(fèi)用最小的路，而不是包含邊數(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管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)505 5最小費(fèi)用最大流問題最小費(fèi)用最大流問題用上述方法對(duì)例用上述方法對(duì)例7求解：求解： 第一次迭代：找到最短路第一次迭代：找到最短路v1 v4 v6 v7。第一次迭代后

24、總流量為第一次迭代后總流量為1，總，總費(fèi)用費(fèi)用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管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)515 5最小費(fèi)用最大流問題最小費(fèi)用最大流問題第二次迭代：找到最短路第二次迭代：找到最短路v1 v4 v7。第二次迭代后總流量為第二次迭代后總流量為3，總費(fèi)用，總費(fèi)用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管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)525 5最小費(fèi)用最大流問題最小費(fèi)用最大流問題第三次迭代：找到最短路第三次迭代：找到最短路v1 v4 v3 v6 v7 。第三次迭代后總流量為第三次迭代后總流量為5，總費(fèi)用，總費(fèi)用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管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)535 5最小費(fèi)用最大流問題最小費(fèi)用最大流問題第四次迭代：找到最短路第四次迭代：找到最短路v1 v4 v3 v5 v7 。第四次迭代后總流量為第四次迭代后總流量為6，總費(fèi)用，總費(fèi)用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管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)545 5最小費(fèi)用最大流問題最小費(fèi)用最大流問題 第五次迭代：找到最短路第五次迭代：找到最短路v1 v2 v5 v7 。第五次迭代后總流量為第五次迭代后總流量為9，總，總費(fèi)用費(fèi)用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管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)555 5

28、最小費(fèi)用最大流問題最小費(fèi)用最大流問題 第六次迭代：找到最短路第六次迭代：找到最短路v1 v2 v3 v5 v7 。第六次迭代后總流量為第六次迭代后總流量為10，總費(fèi)用，總費(fèi)用145。已經(jīng)找不到從。已經(jīng)找不到從v1到到v7的每條弧容量都大于零的路了，故的每條弧容量都大于零的路了，故已求得最小費(fèi)用最大流了。已求得最小費(fèi)用最大流了。(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管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)565 5最小費(fèi)用最大流問題最小費(fèi)用最大流問題 如果對(duì)例如果對(duì)例7求一個(gè)最小費(fèi)用流的問題：每小時(shí)運(yùn)送求一個(gè)最小費(fèi)用流的問題：每小時(shí)運(yùn)送6萬加侖石油從萬加侖石油從v1到到v7的最小費(fèi)用是多少，或者每小時(shí)運(yùn)送的最小費(fèi)用是多少，或者每小時(shí)運(yùn)送7萬加侖呢？我們可以從第四次迭萬加侖呢？我們可以從第四次迭代及圖代及圖11-32即可得到運(yùn)送即可得到運(yùn)送6萬加侖最小費(fèi)用萬加侖最小費(fèi)用72百元，其運(yùn)送方式通過比較百元，其運(yùn)送方式通過比較圖圖11-28及圖及圖11-32即得圖即得圖11-36所示。所示。 至于每小時(shí)運(yùn)送至于每小時(shí)運(yùn)送7萬加侖，我們可以在圖萬加侖，我們可以在圖11-36的基礎(chǔ)上，再按第五次的基礎(chǔ)上，再按第五次迭代所選的最短路運(yùn)送迭代所選的最短路運(yùn)送1萬加侖即得最小費(fèi)用：萬加侖即得最小費(fèi)用：72+1*17=89百元，其運(yùn)送百元，其運(yùn)送方式如圖方式如圖11-37所示。所示。35123126v1v2v5v4v3v610342v710第六次迭代第六次迭代后總流量后總流量圖圖11-35管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)575 5最小費(fèi)用最大流問題最小費(fèi)用最大流問題 123126v1v2v5v4v3v6631v7圖圖11-3612123126v1v2v5v4v3v6311v7圖圖11-37注：注：“管理運(yùn)籌學(xué)軟