網(wǎng)絡(luò)系統(tǒng)的最小費用最大流問題

1、網(wǎng)絡(luò)中的最小費用最大流問題網(wǎng)絡(luò)中的最小費用最大流問題二、基本概念與基本定理二、基本概念與基本定理三、尋求最大流的標號法三、尋求最大流的標號法四、最小費用最大流問題四、最小費用最大流問題一、引言一、引言 網(wǎng)絡(luò)系統(tǒng)的最大流問題 一、引言 在許多實際的網(wǎng)絡(luò)系統(tǒng)中都存在著流量和最大流問題。例如鐵路運輸系統(tǒng)中的車輛流，城市給排水系統(tǒng)的水流問題等等。而網(wǎng)絡(luò)系統(tǒng)流最大流問題是圖與網(wǎng)絡(luò)流理論中十分重要的最優(yōu)化問題，它對于解決生產(chǎn)實際問題起著十分重要的作用。 網(wǎng)絡(luò)系統(tǒng)的最大流問題圖8.23是一個網(wǎng)絡(luò)vtv3v2v1v4vs1735108611453C Cijij每一個弧旁邊的權(quán)就是對應(yīng)的容量（即最大通過能力）。

2、要求指每一個弧旁邊的權(quán)就是對應(yīng)的容量（即最大通過能力）。要求指定一個運輸方案，使得從定一個運輸方案，使得從v vs s到到v vt t的貨運量最大，這是尋求網(wǎng)絡(luò)系的貨運量最大，這是尋求網(wǎng)絡(luò)系統(tǒng)的最大流問題統(tǒng)的最大流問題。 網(wǎng)絡(luò)系統(tǒng)的最大流問題二、基本概念與基本定理 定義定義8.5 8.5 設(shè)一個賦權(quán)有向圖設(shè)一個賦權(quán)有向圖D D = =（V,AV,A）, ,在在v v中指定一個中指定一個發(fā)發(fā)點（或源點）點（或源點）v vs s和一個和一個收點（或匯點）收點（或匯點）v vt t, ,其他的點叫做其他的點叫做中間中間點點。對于。對于D D中的每一個?。ㄖ械拿恳粋€?。╲ vi i,v,vj j）A

3、A, ,都有一個權(quán)都有一個權(quán) c cij ij 叫做叫做弧的容量弧的容量。我們把這樣的圖。我們把這樣的圖 D D 叫做一個叫做一個網(wǎng)絡(luò)系統(tǒng)網(wǎng)絡(luò)系統(tǒng)，簡稱網(wǎng)，簡稱網(wǎng)絡(luò)，記做絡(luò)，記做D D = =（V V，A A，C C）。）。 網(wǎng) 絡(luò)網(wǎng) 絡(luò)D D上 的 流上 的 流 ， 是 指 定 義 在 弧 集 合， 是 指 定 義 在 弧 集 合 A A 上 的 一 個 函 數(shù)上 的 一 個 函 數(shù)f f=f f( (v vi i,v,vj j)=)=f fijij f f( (v vi i,v,vj j)=)=f fijij叫做弧在叫做弧在( (v vi i,v,vj j) )上的流量上的流量。 網(wǎng)絡(luò)系統(tǒng)

4、的最大流問題v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）f fijij圖8.24網(wǎng)絡(luò)上的一個流（運輸方案）每一個弧上的流量fij 就是運輸量例如fs1=5,fs2=3,f13=2等等vt 網(wǎng)絡(luò)系統(tǒng)的最大流問題網(wǎng)絡(luò)系統(tǒng)上流流的特點：(1)發(fā)點的總流出量和收點的總流入量必相等；(2)每一個中間點的流入量與流出量的代數(shù)和等于零；(3)每一個弧上的流量不能超過它的最大通過能力（即容量）。 網(wǎng)絡(luò)系統(tǒng)的最大流問題 定義定義8.6 8.6 網(wǎng)絡(luò)上的一個流 f 叫做可行流，如果 f 滿足以下條件 （1）容量限制條件容量限制條件：對每一?。╲i ,vj）A,有 0 0 f f

5、ij ij c cijij. . （2）平衡條件平衡條件： 對于發(fā)點vs，有fsj -fjs =v (f ) 對于收點vt，有ftj -fjt =-v(f ) 對于中間點，有fij -fji =0 式中v v( (f f ) )叫做這個可行流的流量叫做這個可行流的流量，即，即發(fā)點的凈輸出量（或收點的凈輸入量） 網(wǎng)絡(luò)系統(tǒng)的最大流問題 任意一個網(wǎng)絡(luò)上的可行流總是存在的。例如零流v(f )=0,就是滿足以上條件的可行流。 網(wǎng)絡(luò)系統(tǒng)中最大流問題就是在給定的網(wǎng)絡(luò)上尋求一個可行流f ,使其流量v(f )達到最大值。 設(shè)流f=fij是網(wǎng)絡(luò)D上的一個可行流，我們把D中fij=cij的弧叫做飽和弧飽和弧，fij

6、0的弧為非非零流弧零流弧，fij=0的弧叫做零流弧零流弧。 網(wǎng)絡(luò)系統(tǒng)的最大流問題 設(shè)是網(wǎng)絡(luò)D中連接發(fā)點s和收點vt的一條鏈。定義鏈的方向是從vs到vt，于是鏈上的弧被分為兩類：一是弧的方向與鏈的方向相同，叫做前向弧，前向弧的集合記做+。二是弧的方向與鏈的方向相反，叫做后向弧，后向弧的集合記做-。 在下圖（圖在下圖（圖8.238.23與與8.248.24合并圖）中，合并圖）中，(v(v4 4,v,v3 3) )是是飽和飽和弧弧，其他的弧是，其他的弧是非飽和弧非飽和弧，并且都是，并且都是非零流弧非零流弧。v3v2v1v4vs（17,2）（3,3）（5,2）（10,5）（8,3）（6,3）（11,6

7、）（4,1）（5,1）（3,2）f fijij如圖，在鏈（v vs s ,v,v1 1 ,v,v2 2 ,v,v3 3 ,v,v4 4 ,v,vt t) )中， + +=(=(v vs s ,v,v1 1),(),(v v1 1,v,v2 2),(),(v v2 2 ,v,v3 3),(),(v v4 4 ,v,vt t),), - -=(=(v v4 4 ,v,v3 3).).vt 網(wǎng)絡(luò)系統(tǒng)的最大流問題網(wǎng)絡(luò)系統(tǒng)的最大流問題 網(wǎng)絡(luò)系統(tǒng)的最大流問題增廣鏈增廣鏈，如果鏈 滿足以下條件： 1在弧（vi ,vj）+上，有0fijcij,即+中的每一條弧是非飽和弧。 2在?。╲i ,vj）-上，有0fi

8、j cij ,即-中的每一條弧是非零流弧。 例如在圖8.24中，鏈=（vs ,v1 ,v2 ,v3 ,v4 ,vt）就是一條增廣鏈。 網(wǎng)絡(luò)系統(tǒng)的最大流問題 定義8.8 設(shè)一個網(wǎng)絡(luò)D=（V，A，C）。如果點集V被剖分為兩個非空集合V1和V1，發(fā)點vsV1,收點vtV1,那么將弧集（V1,V1）叫做是分離vs和vt的截集。 定義8.9 設(shè)一個截集（V1, V1），將截集（V1,V1）中所有的弧的容量的和叫做截集的截量，記做c(V1,V1),亦即c(V1,V1)=cij , (vi ,vj)(V1,V1) 設(shè)圖設(shè)圖D D=(=(V V，A A，C C) )，點集，點集S ,T S ,T V ,S V

9、 ,S T T=中，將中，將起點在起點在S S，終點在，終點在T T 的所有弧構(gòu)成的集合，記做（的所有弧構(gòu)成的集合，記做（S S，T T）。）。 網(wǎng)絡(luò)系統(tǒng)的最大流問題 下面的事實是顯然的：一個網(wǎng)絡(luò)D 中，任何一個可行流f的流量v(f )都小于或等于這個網(wǎng)絡(luò)中任何一個截集(V1,V1)的截量。并且，如果網(wǎng)絡(luò)上的一個可行流f*和網(wǎng)絡(luò)中的一個截集（V1*,V1*），滿足條件v*(f*)=c(V1*,V1*),那么f *一定是D上的最大流，而（V1*,V1*）一定是D的所有的截集中截量最小的一個（即最小截集）。 網(wǎng)絡(luò)系統(tǒng)的最大流問題 定理8.8 網(wǎng)絡(luò)中的一個可行流f*是最大流的充要條件是不存在關(guān)于f

10、* 的增廣鏈。 定理8.9 在一個網(wǎng)絡(luò)D 中，最大流的流量等于分離vs 和vt 的最小截集的截量。 定理定理8.88.8實際上提供了一個實際上提供了一個尋求網(wǎng)絡(luò)系統(tǒng)最大流的方法尋求網(wǎng)絡(luò)系統(tǒng)最大流的方法：如：如果網(wǎng)絡(luò)果網(wǎng)絡(luò)D D 中有一個可行流中有一個可行流f f，只要判斷網(wǎng)絡(luò)是否存在關(guān)于可行流，只要判斷網(wǎng)絡(luò)是否存在關(guān)于可行流f f 的增廣鏈的增廣鏈 。如果沒有增廣鏈，那么。如果沒有增廣鏈，那么f f一定是最大流。如有增廣鏈，一定是最大流。如有增廣鏈，那么可以按照定理那么可以按照定理8.98.9，不斷改進和增大可行流，不斷改進和增大可行流f f的流量，最終可以的流量，最終可以得到網(wǎng)絡(luò)中的一個最大

11、流。得到網(wǎng)絡(luò)中的一個最大流。 網(wǎng)絡(luò)系統(tǒng)的最大流問題三、尋求最大流的標號法 從網(wǎng)絡(luò)中的一個可行流f 出發(fā)（如果D中沒有f，可以令f 是零流），運用標號法，經(jīng)過標號過程和調(diào)整過程，可以得到網(wǎng)絡(luò)中的一個最大流。 用給頂點標號的方法來定義V1*.在標號過程中，有標號的頂點是V1*中的點，沒有標號的點不是V1*中的點。如果vt有了標號，表示存在一條關(guān)于f 的增廣鏈。如果標號過程無法進行下去，并且vt未被標號，則表示不存在關(guān)于f 的增廣鏈。這樣，就得到了網(wǎng)絡(luò)中的一個最大流和最小截集。 網(wǎng)絡(luò)系統(tǒng)的最大流問題 1標號過程 在標號過程中，網(wǎng)絡(luò)中的點或者是標號點（分為已檢查和未檢查兩種）或者是未標號點。每個標號點

12、的標號包含兩部分：第一個標號表示這個標號是從哪一點得到的，以便找出增廣鏈。第二個標號是為了用來確定增廣鏈上的調(diào)整量。 標號過程開始，先給vs標號（0，+）。這時，vs是標號而未檢查的點，其他都是未標號點。一般地，取一個標號未檢查點vi，對一切未標號點vj： 網(wǎng)絡(luò)系統(tǒng)的最大流問題 1) 如果在?。╲i ,vj）上，fi j0,那么給vj標號（-vi , l(vj)）,其中l(wèi)(vj)=minl(vi),fji.這時，vj成為標號未檢查點。(考慮后向弧) 于是vi成為標號已檢查的點。重復以上步驟，如果所有的標號都已經(jīng)檢查過，而標號過程無法進行下去，則標號法結(jié)束。這時的可行流就是最大流。但是，如果vt

13、被標上號，表示得到一條增廣鏈，轉(zhuǎn)入下一步調(diào)整過程。 2. 調(diào)整過程 首先按照vt和其他點的第一個標號，利用“反向追蹤”的辦法，找出增廣鏈。例如，令vt的第一個標號是vk，則?。╲k,vt）在上。再看vk的第一個標號，若是vi，則弧(vi,vk)都在上。依次類推，直到vs為止。這時，所找出的弧就成為網(wǎng)絡(luò)D的一條增廣鏈。取調(diào)整量= l(vt),即vt的第二個標號， 網(wǎng)絡(luò)系統(tǒng)的最大流問題 fij +，當(vi ,vj)+ 令fij = fij -， 當(vi ,vj)- fij , 當(vi ,vj)| 再去掉所有的標號，對新的可行流f=fij ,重新進行標號過程，直到找到網(wǎng)絡(luò)D 的最大流為止。 網(wǎng)

14、絡(luò)系統(tǒng)的最大流問題 網(wǎng)絡(luò)系統(tǒng)的最大流問題V4V1V2V3Vs（2,1）（3,0）（4,3）（3,3）（5,1）（2,2）（5,3）（1,1）（1,1）(Cij,fij)Vt圖8.21例8.8 求圖8.21的網(wǎng)絡(luò)最大流，弧旁的權(quán)數(shù)表示（cij,fij）。 解：用標號法。 1.標號過程。 （1）首先給vs標號（0，+） （2）檢查vs :在弧(vs,v2)上,fs2=cs2=3,不具備標號條件。在弧(vs,v1)上,fs 1=10,故給v2標號（-v1, l(v2)）,其中l(wèi)(v2)=minl(v1),f21=min4,1=1. 網(wǎng)絡(luò)系統(tǒng)的最大流問題 （4）檢查v2 :在?。╲2,v4）上，f24

15、=30,故給v3標號（-v2，l(v3),其中l(wèi)(v3)=minl(v2),f32=min1,1=1。 （5）在v3,v4中任意選一個，比如v3,在?。╲3,vt）上，f3t=1c3t=2,故給vt標號(v3,l(vt),其中l(wèi)(vt)=minl(v3),(c3t-f3t)=min1,1=1.因為vt 被標上號，根據(jù)標號法，轉(zhuǎn)入調(diào)整過程。 網(wǎng)絡(luò)系統(tǒng)的最大流問題 2.調(diào)整過程。 從vt 開始，按照標號點的第一個標號，用反向追蹤的方法，找出一條從vs 到vt 的增廣鏈=vs ,v1,v2 ,v3,vt ，如圖8.22中雙箭線所示。 不難看出, +=(vs ,v1),(v3 ,vt), -=(v2

16、,v1),(v3 ,v2), 取=l(vt)=1，在上調(diào)整f，得到 在+上， fs1+=1+1=2 在+上 ， f3t+=1+1=2 在-上 ， f21 -=1-1=0 在-上 ， f32 -=1-1=0 其他的fij 不變。 網(wǎng)絡(luò)系統(tǒng)的最大流問題 網(wǎng)絡(luò)系統(tǒng)的最大流問題V4V1V2V3Vs（2,1）（3,0）（4,3）（3,3）（5,1）（2,2）（5,3）（1,1）（1,1）(Cij,fij)Vt(v2,1)(0，+)(-v1,1)(vs,4)(-V2,1)圖8.22調(diào)整后的可行流f *，如圖8.23所示，再對這個可行流重新進行標號過程，尋找增廣鏈： 首先給vs標號（0，+），檢查vs ,給

17、v1標號（vs ,3）。檢查v1,在?。╲1,v3）上，f13=c13 ,?。╲2 ,v1）上，f21=0,均不符合標號過程(1)的條件。因此標號過程無法進行下去，不存在從VS到Vt的增廣鏈，算法結(jié)束。 這時，網(wǎng)絡(luò)中的可行流f*即是最大流，最大流的流量V(f*)=fs1+fs2=5.同時，也找出D的最小截集（V1，V1），其中V1是標號的集合，V1是未標號的集合。 網(wǎng)絡(luò)系統(tǒng)的最大流問題 網(wǎng)絡(luò)系統(tǒng)的最大流問題V4V1V2V3Vs（2,1）（3,0）（4,3）（3,3）（5,2）（2,2）（5,3）（1,0）Vt(0，+)(vs,3)圖8.23(Cij,fij)（1,0）四、最小費用最大流問題 在

18、實際的網(wǎng)絡(luò)系統(tǒng)中，當涉及到有關(guān)流的問題的時候，我們往往不僅僅考慮的是流量，還經(jīng)常要考慮費用的問題。比如一個鐵路系統(tǒng)的運輸網(wǎng)絡(luò)流，即要考慮網(wǎng)絡(luò)流的貨運量最大，又要考慮總費用最小。最小費用最大流問題就是要解決這一類問題。 網(wǎng)絡(luò)系統(tǒng)的最小費用最大流問題 設(shè)一個網(wǎng)絡(luò)D=（V，A，C），對于每一個弧(vi,vj)A,給定一個單位流量的費用bij 0，網(wǎng)絡(luò)系統(tǒng)的最小費用最大流問題，是指要尋求一個最大流f，使流的總費用b(f )= bijfij 達到最小。 （Vi,Vj）A 網(wǎng)絡(luò)系統(tǒng)的最小費用最大流問題在一個網(wǎng)絡(luò)D中，當沿可行流f 的一條增廣鏈，以調(diào)整量=1改進f，得到的新可行流f 的流量，有v(f )=v

19、(f )+1，而此時總費用b(f )比b(f )增加了 b(f )-b(f )=bij (fij -fij) - bij (fij-fij)= bij -bij + - + - 將bij -bij 叫做這條增廣鏈的費用。 + -網(wǎng)絡(luò)系統(tǒng)的最小費用最大流問題網(wǎng)絡(luò)系統(tǒng)的最小費用最大流問題 如果可行流在流量為v(f )的所有可行流中的費用最小，并且是關(guān)于f 的所有增廣鏈中的費用最小的增廣鏈，那么沿增廣鏈調(diào)整可行流f，得到的新可行流f，也是流量為v(f )的所有可行流中的最小費用流。 依次類推，當f是最大流時，就是所要求的最小費用最大流。 顯然，零流f=0是流量為0的最小費用流。一般地，尋求最小費用流

20、，總可以從零流f=0開始。下面的問題是：如果已知f是流量為v(f)的最小費用流，那么就要去尋找關(guān)于f 的最小費用增廣鏈。 對此，重新構(gòu)造一個賦權(quán)有向圖W(f )，其頂點是原網(wǎng)絡(luò)D 的頂點，而將D中的每一條弧(vi,vj)變成兩個相反方向的?。╲i,vj）和(vj ,vi)，并且定義W(f )中弧的權(quán)wij為：網(wǎng)絡(luò)系統(tǒng)的最小費用最大流問題 bij , 當fij0wji = + , 當fij=0(將權(quán)為+的弧從W(f)中略去) 即當 0 fij cij 時，成為2條方向相反，權(quán)絕對值相等的弧。否則不變。網(wǎng)絡(luò)系統(tǒng)的最小費用最大流問題 這樣，在網(wǎng)絡(luò)D中尋找關(guān)于f 的最小費用增廣鏈就等于價于在W(f)中

21、尋求從vs到vt的最短路。算法如下： 算法開始，取零流f(0) =0.一般地，如果在第K-1步得到最小費用流f(K-1),則構(gòu)造圖W（f(K-1)）。在圖W（f(K-1)）中，尋求從vs到vt的最短路。如果不存在最短路(即最短路權(quán)是+)，則f(K-1)就是最小費用最大流。如果存在最短路，則在原網(wǎng)絡(luò)D中得到相對應(yīng)（一一對應(yīng)）的增廣鏈 ， 在增廣鏈上對f(K-1)進行調(diào)整，取調(diào)整量 =minmin(cij-f(k-1)ij),min(f(k-1)ij). + - 網(wǎng)絡(luò)系統(tǒng)的最小費用最大流問題令 f(k-1)ij + ， 當(vi ,vj)+ f(k)ij = f(k-1)ij - ， 當(vi ,

22、vj)- f(k-1)ij ， 當(vi ,vj)| 得到一個新的可行流f(k)，在對f(k)重復以上的步驟，直到D中找不到相對應(yīng)的增廣鏈時為止。網(wǎng)絡(luò)系統(tǒng)的最小費用最大流問題 例8.9 求圖8-24 所示網(wǎng)絡(luò)中的最小費用最大流，弧旁的權(quán)是（bij,cij）.網(wǎng)絡(luò)系統(tǒng)的最小費用最大流問題(bij,Cij)(1,8)vtv3v2vsv1(3,10)(2,4)(6,2)(1,7)(4,10)(2,5) 解： （1）取初始可行流為零流f(0)=0,構(gòu)造賦權(quán)有向圖W(f(0),求出從vs到vt 的最短路(vs,v2,v1,vt),如圖8.25a中雙箭頭所示即為最短路。網(wǎng)絡(luò)系統(tǒng)的最小費用最大流問題(1)V

23、tV3V2VsV1(3)(2)(6)(1)(4)(2)W(f (0)圖8.25a （2）在原網(wǎng)絡(luò)D中，與這條最短路相對應(yīng)的增廣鏈為=（vs,v2,v1,vt）。 （3）在上對f(0)=0進行調(diào)整，取=5，得到新可行流f(1)。類似地，按照以上的算法，依次類推，可以得到f(1)，f(2)，f(3)，f(4)，流量分別為5，7，10，11，并且分別構(gòu)造相對應(yīng)的賦權(quán)有向圖W(f(1),W(f(2),W(f(3),W(f(4)。由于在W(f(4) )中已經(jīng)不存在從vs到vt的最短路，因此，可行流f(4)，v(f(1)=11是最小費用最大流。網(wǎng)絡(luò)系統(tǒng)的最小費用最大流問題vsvtv2v3v1(10,4)(

24、7,1)(8,1)(10,3)(4,2)(5,2)(2,6)(5,2,5)(7,1,5)vsvtv2v3v1(10,4,0)(8,1,5)(10,3,0)(4,2,0)(2,6,0)第第 1 次次 迭迭 代代原圖全部是零流弧原圖全部是零流弧, ,保持原邊不變保持原邊不變, ,單位費用為權(quán)；單位費用為權(quán)；所有的權(quán)均大于零，構(gòu)造賦權(quán)有向所有的權(quán)均大于零，構(gòu)造賦權(quán)有向圖并求出最短路：圖并求出最短路：恰也是恰也是。 tsvvvv12流量調(diào)整量流量調(diào)整量1 1=min8-0,5-0,7-0=5=min8-0,5-0,7-0=5 總流量總流量f f1 1=5=5最小費用增廣鏈的費用最小費用增廣鏈的費用bb

25、ijij=1+2+1=4=1+2+1=4總費用總費用C C1 1=4=45=205=20 (容量費用圖容量費用圖(cij,bij) 第第 2 次次 迭迭 代代(3,1)v1vt(5,-2)(2,6)v2v3(10,4)(5,-1)(10,3)(4,2)（2,1）vs（5，-1）(7,1,7)vsvtv2v3v1(10,4,2)(8,1,5)(10,3,0)(4,2,0)(2,6,0)(5,2,5)零流弧保持原邊零流弧保持原邊, ,非飽和弧和非零流弧非飽和弧和非零流弧(v(vs s,v,v2 2) )和和(v(v1 1,v,vt t) )增添反向弧增添反向弧, ,將飽和弧將飽和弧(v(v2 2,

26、v,v1 1) )變成反向??；變成反向??；繼續(xù)繼續(xù)構(gòu)造賦權(quán)有向圖并構(gòu)造賦權(quán)有向圖并求出最短路求出最短路: :恰也是最小費用增廣鏈恰也是最小費用增廣鏈。 流量調(diào)整量流量調(diào)整量2 2=min10-0,7-5=2=min10-0,7-5=2，總流量總流量= =原流量原流量+ +新增流量新增流量 =5+2=7=5+2=7；最小費用增廣鏈的費用最小費用增廣鏈的費用 bbijij=4+1=5=4+1=5總費用總費用C C2 2= =原費用原費用+ +新增費用新增費用=20+5=20+52=30 2=30 tsvvv1vsvtv2v3v1(8,4)（2,-4）(5,-1)(7,-1)(10,3)(4,2)(

27、2,6)(5,-2)(3,1)零流弧保持原邊，此外的非飽和弧增零流弧保持原邊，此外的非飽和弧增添反向弧，飽和弧去掉原邊增添反向虛添反向弧，飽和弧去掉原邊增添反向虛線弧，變成反向弧線弧，變成反向弧繼續(xù)構(gòu)造賦權(quán)有向圖并求出最短路繼續(xù)構(gòu)造賦權(quán)有向圖并求出最短路: :恰也是最小費用增廣鏈。恰也是最小費用增廣鏈。流量調(diào)整量流量調(diào)整量3 3=min8-5,10-0,4-0=3=min8-5,10-0,4-0=3，總流量總流量= =原流量原流量+ +新增流量新增流量 =7+3=10=7+3=10；最小費用增廣鏈的費用最小費用增廣鏈的費用 bbijij=1+3+2=6=1+3+2=6總費用總費用C C3 3=

28、 =原費用原費用+ +新增費用新增費用=30+6=30+63=48 3=48 tsvvvv32第第 3 次次 迭迭 代代(7,1,7)vsvtv2v3v1(10,4,2)(8,1,8)(10,3,3)(4,2,3)(2,6,0)(5,2,5)(2,6)(7,3)(8,4)vsvtv2v3v1(3,-3)(7,-1)(8,-1)(3,-2)（1,2）(2,-4)（5,-2）零流弧保持原邊，此外的非飽零流弧保持原邊，此外的非飽和弧增添反向弧，飽和弧去掉原和弧增添反向弧，飽和弧去掉原邊增添反向虛線弧，變成反向??；邊增添反向虛線弧，變成反向??；繼續(xù)構(gòu)造賦權(quán)有向圖并求出最繼續(xù)構(gòu)造賦權(quán)有向圖并求出最短路短

29、路: : 對應(yīng)的最小費用增廣鏈是對應(yīng)的最小費用增廣鏈是tsvvvvv321tsvvvvv 321流量調(diào)整量流量調(diào)整量4 4=min10-2,5,10-=min10-2,5,10-3,4-3=13,4-3=1，總流量總流量= =原流量原流量+ +新增流量新增流量=10+1=11=10+1=11；最小費用增廣鏈的費用最小費用增廣鏈的費用 bbijij=4-2+3+2=7=4-2+3+2=7總費用總費用C C4 4= =原費用原費用+ +新增費用新增費用 =48+7=48+71=551=55。由于總流量由于總流量1111已達到最大流量，故停已達到最大流量，故停止迭代，止迭代，當前的可行流圖即最大流圖

30、。當前的可行流圖即最大流圖。第第 4 次次 迭迭 代代(7,1,7)vsvtv2v3v1(10,4,3)(8,1,8)(10,3,4)(4,2,4)(2,6,0)(5,2,4)例題總結(jié)：例題總結(jié)：1、將飽和弧反向；、將飽和弧反向；2、將非飽和非零流弧加一反向??；、將非飽和非零流弧加一反向??；3、零流弧不變；、零流弧不變；4、所有正向弧的權(quán)為該弧的費用，反向弧、所有正向弧的權(quán)為該弧的費用，反向弧的權(quán)為該弧費用的相反數(shù)。的權(quán)為該弧費用的相反數(shù)。求最小費用求最小費用-最大流問題最大流問題求下圖中網(wǎng)絡(luò)從 到 的最小費用最大流，圖中弧上的數(shù)字為 。svtv(,)ijijb cvsv2v3v4v5vt(15,2)(9,6)(7,8)(3,3)(6,3)(5,5)(10,1)(4,9)(11,3)vsv2v3v4v5vt(15,2)(9,6)(7,8)(3,3)(6,3)(5,5)(10,1)(4,9)(11,3)(0)求網(wǎng)絡(luò)的最大流量maxfmax20f由前面計算知， 。 將0流作為初始可行流。擴展費用網(wǎng)絡(luò)與原網(wǎng)絡(luò)相同(1)第一次迭代：用Ford算法求最短增廣鏈，路線是vsv3v5vtvsv2v3v4v5vt(15,2,0)(9,6,6)(7,8,0)(3,3,0)(6,3,6)(5,5,0)(10,1,6)(4,9,0)(11,3,0)調(diào)整流量：在增廣鏈上