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

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

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

3、A, ,都有一個(gè)權(quán)都有一個(gè)權(quán) c cij ij 叫做叫做弧的容量弧的容量。我們把這樣的圖。我們把這樣的圖 D D 叫做一個(gè)叫做一個(gè)網(wǎng)絡(luò)系統(tǒng)網(wǎng)絡(luò)系統(tǒng)，簡(jiǎn)稱(chēng)網(wǎng)，簡(jiǎn)稱(chēng)網(wǎng)絡(luò)，記做絡(luò)，記做D D = =（V V，A A，C C）。）。 網(wǎng) 絡(luò)網(wǎng) 絡(luò)D D上 的 流上 的 流 ， 是 指 定 義 在 弧 集 合， 是 指 定 義 在 弧 集 合 A A 上 的 一 個(gè) 函 數(shù)上 的 一 個(gè) 函 數(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、的最大流問(wèn)題v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）f fijij圖8.24網(wǎng)絡(luò)上的一個(gè)流（運(yùn)輸方案）每一個(gè)弧上的流量fij 就是運(yùn)輸量例如fs1=5,fs2=3,f13=2等等vt 網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題網(wǎng)絡(luò)系統(tǒng)上流流的特點(diǎn)：(1)發(fā)點(diǎn)的總流出量和收點(diǎn)的總流入量必相等；(2)每一個(gè)中間點(diǎn)的流入量與流出量的代數(shù)和等于零；(3)每一個(gè)弧上的流量不能超過(guò)它的最大通過(guò)能力（即容量）。 網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題 定義定義8.6 8.6 網(wǎng)絡(luò)上的一個(gè)流 f 叫做可行流，如果 f 滿足以下條件 （1）容量限制條件容量限制條件：對(duì)每一?。╲i ,vj）A,有 0 0 f f

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

6、0的弧為非非零流弧零流弧，fij=0的弧叫做零流弧零流弧。 網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題 設(shè)是網(wǎng)絡(luò)D中連接發(fā)點(diǎn)s和收點(diǎn)vt的一條鏈。定義鏈的方向是從vs到vt，于是鏈上的弧被分為兩類(lèi)：一是弧的方向與鏈的方向相同，叫做前向弧，前向弧的集合記做+。二是弧的方向與鏈的方向相反，叫做后向弧，后向弧的集合記做-。 在下圖（圖在下圖（圖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èn)題網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題 網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題增廣鏈增廣鏈，如果鏈 滿足以下條件： 1在?。╲i ,vj）+上，有0fijcij,即+中的每一條弧是非飽和弧。 2在?。╲i ,vj）-上，有0fi

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

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

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

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

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

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

14、絡(luò)系統(tǒng)的最大流問(wèn)題 網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題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）。 解：用標(biāo)號(hào)法。 1.標(biāo)號(hào)過(guò)程。 （1）首先給vs標(biāo)號(hào)（0，+） （2）檢查vs :在弧(vs,v2)上,fs2=cs2=3,不具備標(biāo)號(hào)條件。在弧(vs,v1)上,fs 1=10,故給v2標(biāo)號(hào)（-v1, l(v2)）,其中l(wèi)(v2)=minl(v1),f21=min4,1=1. 網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題 （4）檢查v2 :在?。╲2,v4）上，f24

15、=30,故給v3標(biāo)號(hào)（-v2，l(v3),其中l(wèi)(v3)=minl(v2),f32=min1,1=1。 （5）在v3,v4中任意選一個(gè)，比如v3,在?。╲3,vt）上，f3t=1c3t=2,故給vt標(biāo)號(hào)(v3,l(vt),其中l(wèi)(vt)=minl(v3),(c3t-f3t)=min1,1=1.因?yàn)関t 被標(biāo)上號(hào)，根據(jù)標(biāo)號(hào)法，轉(zhuǎn)入調(diào)整過(guò)程。 網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題 2.調(diào)整過(guò)程。 從vt 開(kāi)始，按照標(biāo)號(hào)點(diǎn)的第一個(gè)標(biāo)號(hào)，用反向追蹤的方法，找出一條從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èn)題 網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題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所示，再對(duì)這個(gè)可行流重新進(jìn)行標(biāo)號(hào)過(guò)程，尋找增廣鏈： 首先給vs標(biāo)號(hào)（0，+），檢查vs ,給

17、v1標(biāo)號(hào)（vs ,3）。檢查v1,在?。╲1,v3）上，f13=c13 ,弧（v2 ,v1）上，f21=0,均不符合標(biāo)號(hào)過(guò)程(1)的條件。因此標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行下去，不存在從VS到Vt的增廣鏈，算法結(jié)束。 這時(shí)，網(wǎng)絡(luò)中的可行流f*即是最大流，最大流的流量V(f*)=fs1+fs2=5.同時(shí)，也找出D的最小截集（V1，V1），其中V1是標(biāo)號(hào)的集合，V1是未標(biāo)號(hào)的集合。 網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題 網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題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）四、最小費(fèi)用最大流問(wèn)題 在

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

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

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

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

22、vj)- f(k-1)ij ， 當(dāng)(vi ,vj)| 得到一個(gè)新的可行流f(k)，在對(duì)f(k)重復(fù)以上的步驟，直到D中找不到相對(duì)應(yīng)的增廣鏈時(shí)為止。網(wǎng)絡(luò)系統(tǒng)的最小費(fèi)用最大流問(wèn)題 例8.9 求圖8-24 所示網(wǎng)絡(luò)中的最小費(fèi)用最大流，弧旁的權(quán)是（bij,cij）.網(wǎng)絡(luò)系統(tǒng)的最小費(fèi)用最大流問(wèn)題(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)的最小費(fèi)用最大流問(wèn)題(1)V

23、tV3V2VsV1(3)(2)(6)(1)(4)(2)W(f (0)圖8.25a （2）在原網(wǎng)絡(luò)D中，與這條最短路相對(duì)應(yīng)的增廣鏈為=（vs,v2,v1,vt）。 （3）在上對(duì)f(0)=0進(jìn)行調(diào)整，取=5，得到新可行流f(1)。類(lèi)似地，按照以上的算法，依次類(lèi)推，可以得到f(1)，f(2)，f(3)，f(4)，流量分別為5，7，10，11，并且分別構(gòu)造相對(duì)應(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是最小費(fèi)用最大流。網(wǎng)絡(luò)系統(tǒng)的最小費(fèi)用最大流問(wèn)題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 次次 迭迭 代代原圖全部是零流弧原圖全部是零流弧, ,保持原邊不變保持原邊不變, ,單位費(fèi)用為權(quán)；單位費(fèi)用為權(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最小費(fèi)用增廣鏈的費(fèi)用最小費(fèi)用增廣鏈的費(fèi)用bb

25、ijij=1+2+1=4=1+2+1=4總費(fèi)用總費(fèi)用C C1 1=4=45=205=20 (容量費(fèi)用圖容量費(fèi)用圖(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)有向圖并求出最短路求出最短路: :恰也是最小費(fèi)用增廣鏈恰也是最小費(fèi)用增廣鏈。 流量調(diào)整量流量調(diào)整量2 2=min10-0,7-5=2=min10-0,7-5=2，總流量總流量= =原流量原流量+ +新增流量新增流量 =5+2=7=5+2=7；最小費(fèi)用增廣鏈的費(fèi)用最小費(fèi)用增廣鏈的費(fèi)用 bbijij=4+1=5=4+1=5總費(fèi)用總費(fèi)用C C2 2= =原費(fèi)用原費(fèi)用+ +新增費(fèi)用新增費(fèi)用=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)有向圖并求出最短路: :恰也是最小費(fèi)用增廣鏈。恰也是最小費(fèi)用增廣鏈。流量調(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；最小費(fèi)用增廣鏈的費(fèi)用最小費(fèi)用增廣鏈的費(fèi)用 bbijij=1+3+2=6=1+3+2=6總費(fèi)用總費(fèi)用C C3 3=

28、 =原費(fèi)用原費(fèi)用+ +新增費(fèi)用新增費(fèi)用=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、路: : 對(duì)應(yīng)的最小費(fèi)用增廣鏈?zhǔn)菍?duì)應(yīng)的最小費(fèi)用增廣鏈?zhǔn)莟svvvvv321tsvvvvv 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；最小費(fèi)用增廣鏈的費(fèi)用最小費(fèi)用增廣鏈的費(fèi)用 bbijij=4-2+3+2=7=4-2+3+2=7總費(fèi)用總費(fèi)用C C4 4= =原費(fèi)用原費(fèi)用+ +新增費(fèi)用新增費(fèi)用 =48+7=48+71=551=55。由于總流量由于總流量1111已達(dá)到最大流量，故停已達(dá)到最大流量，故停止迭代，止迭代，當(dāng)前的可行流圖即最大流圖

30、。當(dāng)前的可行流圖即最大流圖。第第 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)為該弧的費(fèi)用，反向弧、所有正向弧的權(quán)為該弧的費(fèi)用，反向弧的權(quán)為該弧費(fèi)用的相反數(shù)。的權(quán)為該弧費(fèi)用的相反數(shù)。求最小費(fèi)用求最小費(fèi)用-最大流問(wèn)題最大流問(wèn)題求下圖中網(wǎng)絡(luò)從 到 的最小費(fèi)用最大流，圖中弧上的數(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由前面計(jì)算知， 。 將0流作為初始可行流。擴(kuò)展費(fèi)用網(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)整流量：在增廣鏈上