運籌學(xué)課件 第四節(jié) 最大流問題.ppt

1、第四節(jié) 最大流問題,理解最大流問題的概念、最大流-最小割定理。 掌握求最大流問題的標(biāo)號算法。,引言 在許多實際的網(wǎng)絡(luò)系統(tǒng)中都存在著流量和最大流問題。例如鐵路運輸系統(tǒng)中的車輛流，城市給排水系統(tǒng)的水流問題等等。而網(wǎng)絡(luò)系統(tǒng)流最大流問題是圖與網(wǎng)絡(luò)流理論中十分重要的最優(yōu)化問題，它對于解決生產(chǎn)實際問題起著十分重要的作用。,圖是聯(lián)結(jié)某個起始地vs和目的地vt的交通運輸網(wǎng)，每一條弧vi 旁邊的權(quán)cij表示這段運輸線的最大通過能力，貨物從vs運送到vt.要求指定一個運輸方案，使得從vs到vt的貨運量最大，這個問題就是尋求網(wǎng)絡(luò)系統(tǒng)的最大流問題。,一、最大流有關(guān)概念 連通網(wǎng)絡(luò) G(V, E) 有 m 個節(jié)點, n條

2、弧, 弧 eij 上的流量上界為 cij, 求從起始節(jié)點 vs 到終點 vt 的最大流量。,定義20 設(shè)一個賦權(quán)有向圖G=（V,E）,對于G中的每一個邊（?。╲i ,vj）E,都有一個非負(fù)數(shù)cij叫做邊的容量。在V 中一個入次為零的點稱為發(fā)點vs，一個出次為零的點稱為收點vt ,其它的點叫做中間點。我們把這樣的圖G叫做一個容量網(wǎng)絡(luò)，記做G=（V，E，C）。 網(wǎng)絡(luò)G上的流，是指定義在邊(vi ,vj)上有流量fij，稱集合f=fij 為網(wǎng)絡(luò)G上的一個流， f為可行流。,網(wǎng)絡(luò)上的一個流f 叫做可行流，如果f 滿足以下條件： （1）容量條件：對于每一個?。╲i ,vj）E,有 0 fij cij

3、. （2）平衡條件：,對于發(fā)點vs,收點vt有,對于中間點，有,任意一個網(wǎng)絡(luò)上的可行流總是存在的。例如零流w(f)=0,就是滿足以上條件的可行流。 網(wǎng)絡(luò)系統(tǒng)中最大流問題就是在給定的網(wǎng)絡(luò)上尋求一個可行流f,其流量w(f)達(dá)到最大值。 設(shè)流f =fij是網(wǎng)絡(luò)G上的一個可行流。我們把G中fij=cij的弧叫做飽和弧，fij0的弧為非零流弧，fij=0的弧叫做零流弧 . 最大流問題實際是個線性規(guī)劃問題。,其中發(fā)點的總流量（或收點的總流量） w 叫做這個可行流的總流量。,網(wǎng)絡(luò)上的一個流（運輸方案），每一個弧上的流量fij就是運輸量。例如fs1=5 , fs2=3 , f13=2 等等。,定義21 設(shè)一個

4、網(wǎng)絡(luò)G=（V，E，C），vs、vt為發(fā)和收點，邊集 為E的子集，將G分成2個子圖G1,G2;其頂點集合分別為: ,發(fā)點vsS,收點vt /S ,滿足 1.G=（V，E- ）不連通； 2. 為 的真子集，而G=（V，E- ）連通； 那么 為G的割集，記為 =(S, )。 割集 (S, )所有始點在S，終點在 的容量之和，稱為(S, )的割集容量，記為C(S, ) 。,vt,vs,v1,v2,v3,v4,4,2,4,4,3,3,2,2,2,3,1,邊集(vs,v1),(vs,v3),(vs,v4) 邊集(vs,v1),(v1,v3),(v2,v3),(v3,vt) 為圖的割集，割集容量分別為11，

5、9,二、最大流-最小割定理 定理10：設(shè)f為網(wǎng)絡(luò)G=（V，E，C）的任一個可行流，流量為W, (S, )是分離vs vt的任一個割集，則有W C(S, ) . 定理11：最大流-最小割定理:任一個網(wǎng)絡(luò)G=（V，E，C）,從vs到vt的最大流的流量等于分離vs vt的最小割的容量。,定義22：設(shè)是網(wǎng)絡(luò)G中連接發(fā)點s和收點vt的一條鏈。定義鏈的方向是從s到 vt ，于是鏈上的邊被分為兩類：一類是邊的方向與鏈的方向相同，叫做前向邊，前向邊的集合記做+。二類是邊的方向與鏈的方向相反，叫做后向邊，后向邊的集合記做。,如果鏈滿足以下條件： 1在邊（vi ,vj）+上，有0fijcij。 2在邊（vi,vj

6、）上，有0fijcij,。 則稱為從s到 vt可增廣鏈。 在鏈（vs,v1,v2,v3,v4,vt)中，+ = (vs,v1 ),(v1,v2),(v2,v3),(v4,vt), = (v4 ,v3).,vt,vs,v1,v2,v3,v4,4,2,4,4,3,3,2,2,2,3,1,定理11提供了一個尋求網(wǎng)絡(luò)系統(tǒng)最大流的方法。如果網(wǎng)絡(luò)G中有一個可行流 f，只要判斷網(wǎng)絡(luò)是否存在關(guān)于可行流 f 的增廣鏈 。如果沒有增廣鏈，那么f一定是最大流。如有增廣鏈，那么可以按照定理中必要性，不斷改進(jìn)和增大可行流f 的流量，最終可以得到網(wǎng)絡(luò)G中的一個最大流。,推論： 網(wǎng)絡(luò)中的一個可行流f*是最大流的充分必要條件

7、是，不存在關(guān)于f*的增廣鏈。 在一個網(wǎng)絡(luò)G中，最大流的流量等于分離vs 和vt 的最小割集的割量。,三、標(biāo)號法 從網(wǎng)絡(luò)中的一個可行流f 出發(fā)（如果G中沒有 f，可以令f 是零流），運用標(biāo)號法，經(jīng)過標(biāo)號過程和調(diào)整過程，可以得到網(wǎng)絡(luò)中的一個最大流。 如果vt有了標(biāo)號，表示存在一條關(guān)于f 的增廣鏈。如果標(biāo)號過程無法進(jìn)行下去，并且vt未被標(biāo)號，則表示不存在關(guān)于f 的增廣鏈。這樣，就得到了網(wǎng)絡(luò)中的一個最大流和最小割集。,1 標(biāo)號過程 在標(biāo)號過程中，網(wǎng)絡(luò)中的每個標(biāo)號點的標(biāo)號包含兩部分：第一個標(biāo)號表示這個標(biāo)號是從那一點得到的，以便找出增廣鏈；第二個標(biāo)號是為了用來確定增廣鏈上的調(diào)整量 。 標(biāo)號過程開始，先給v

8、s 標(biāo)號（ ，+），一般地，取一個標(biāo)號頂點vi，對vi所有未標(biāo)號的鄰接點vj按照下面條件進(jìn)行處理：,（1）如果在弧（vi ,vj）上，fij 0,那么給vj標(biāo)號（-vi , (vj) ）.其中 (vj)=minfji , (vi) 。 重復(fù)以上步驟，如果收點Vt被標(biāo)號或不再有頂點可標(biāo)號為止，則標(biāo)號法結(jié)束。這時的可行流就是最大流。,2.調(diào)整過程 令,但是，如果vt 被標(biāo)上號，表示得到一條增廣鏈，轉(zhuǎn)入下一步調(diào)整過程。,3.再去掉所有的標(biāo)號，對新的可行流f =f ij,重新進(jìn)行標(biāo)號過程，直到找到網(wǎng)絡(luò)G的最大流為止。,例 求圖的網(wǎng)絡(luò)最大流，弧旁的權(quán) 數(shù)表示（cij , fij）。,解：用標(biāo)號法。 1.

9、標(biāo)號過程。 （1）首先給vs標(biāo)號（ ，+） （2）檢查vs鄰接點v1,v2,v3: v2點滿足（ vs,v2) E,且fs2=2cs2=4, v2=min2,+ =2,給v2以標(biāo)號(+ vs,2); v3點滿足（ vs,v3) E,且fs3=2cs3=3, v3=min1,+ =1,給v3以標(biāo)號(+vs,1);,( ，+),(+ vs,2),(+ vs,1),（3）檢查v2鄰接點v5,v6: v5點滿足（ v2,v5) E,且f25=0c25=3, v5=min3,2=2,給v5以標(biāo)號(+ v2,2);,( ，+),(+ vs,2),(+ vs,1),(+ v2,2),（4）檢查v5鄰接點v1

10、,vt: v1點滿足（ v1,v5) E,且f15=3c15=0, v1=min3,2=2,給v1以標(biāo)號(- v5,2);,( ，+),(+ vs,2),(+ vs,1),(+ v2,2),(- v5,2),（5）檢查v1鄰接點v4: v4點滿足（ v1,v4) E,且f14=2c14=5, v4=min3,2=2,給v4以標(biāo)號(+ v1,2);,( ，+),(+ vs,2),(+ vs,1),(+ v2,2),(- v5,2),(+ v1,2),（6）檢查v4鄰接點vt: vt點滿足（ v4,vt) E,且f4t=2c4t=4, vt=min2,2=2,給vt以標(biāo)號(+ v4,2); Vt得

11、到標(biāo)號，說明已經(jīng)得到一條可增廣鏈，標(biāo)號過程結(jié)束。,( ，+),(+ vs,2),(+ vs,1),(+ v2,2),(- v5,2),(+ v1,2),(+ v4,2),開始調(diào)整,(+ v4,2),2.調(diào)整過程 從vt開始，按照標(biāo)號點的第一個標(biāo)號，用反向追蹤的方法，找出一條從vs到vt的增廣鏈，如圖G中虛線所示。不難看出,+=(vs ,v2), (v1 ,v4),(v4 ,vt), =(v5 ,v1) ,取 = vt = 2 ，在上調(diào)整f ，得到,vs,v2,v5,vt,v4,v1,v6,v3,(5,5),(3,2),(3,1),(4,4),(5,4),(3,3),(2,2),(5,4),(4

12、,4),(2,2),（ ，+）,（ +vs ，1）,(3,2),重新開始標(biāo)號，尋找可增廣鏈，當(dāng)標(biāo)到V3，與VS,V3相連的V1,V2,V6不滿足標(biāo)號條件，標(biāo)號無法進(jìn)行，vt得不到標(biāo)號。 流量：w=fs1+ fs2+ fs3= f4t+ f5t+ f6t=11 得到一個最小割，標(biāo)點號集合：S=vs,v3 非標(biāo)點號集合：/S=v1,v2， v4,v5 ， v6,vt 此時割集（s,/s）=(vs,v1),(vs,v2),(v3,v6), 割集容量C(s,/s)=Cs1+ Cs2+ C36=5+4+2=11,( ，+),(+ vs,2),(+ vs,1),(+ v2,2),(- v5,2),(+ v1,2),(+ v4,2),4),