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

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

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

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

4、網(wǎng)絡(luò)G=（V，E，C），vs、vt為發(fā)和收點(diǎn)，邊集 為E的子集，將G分成2個(gè)子圖G1,G2;其頂點(diǎn)集合分別為: ,發(fā)點(diǎn)vsS,收點(diǎn)vt /S ,滿足 1.G=（V，E- ）不連通； 2. 為 的真子集，而G=（V，E- ）連通； 那么 為G的割集，記為 =(S, )。 割集 (S, )所有始點(diǎn)在S，終點(diǎn)在 的容量之和，稱為(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）的任一個(gè)可行流，流量為W, (S, )是分離vs vt的任一個(gè)割集，則有W C(S, ) . 定理11：最大流-最小割定理:任一個(gè)網(wǎng)絡(luò)G=（V，E，C）,從vs到vt的最大流的流量等于分離vs vt的最小割的容量。,定義22：設(shè)是網(wǎng)絡(luò)G中連接發(fā)點(diǎn)s和收點(diǎn)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提供了一個(gè)尋求網(wǎng)絡(luò)系統(tǒng)最大流的方法。如果網(wǎng)絡(luò)G中有一個(gè)可行流 f，只要判斷網(wǎng)絡(luò)是否存在關(guān)于可行流 f 的增廣鏈 。如果沒有增廣鏈，那么f一定是最大流。如有增廣鏈，那么可以按照定理中必要性，不斷改進(jìn)和增大可行流f 的流量，最終可以得到網(wǎng)絡(luò)G中的一個(gè)最大流。,推論： 網(wǎng)絡(luò)中的一個(gè)可行流f*是最大流的充分必要條件

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

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

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

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

11、到標(biāo)號(hào)，說明已經(jīng)得到一條可增廣鏈，標(biāo)號(hào)過程結(jié)束。,( ，+),(+ vs,2),(+ vs,1),(+ v2,2),(- v5,2),(+ v1,2),(+ v4,2),開始調(diào)整,(+ v4,2),2.調(diào)整過程 從vt開始，按照標(biāo)號(hào)點(diǎn)的第一個(gè)標(biāo)號(hà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)號(hào)，尋找可增廣鏈，當(dāng)標(biāo)到V3，與VS,V3相連的V1,V2,V6不滿足標(biāo)號(hào)條件，標(biāo)號(hào)無法進(jìn)行，vt得不到標(biāo)號(hào)。 流量：w=fs1+ fs2+ fs3= f4t+ f5t+ f6t=11 得到一個(gè)最小割，標(biāo)點(diǎn)號(hào)集合：S=vs,v3 非標(biāo)點(diǎn)號(hào)集合：/S=v1,v2， v4,v5 ， v6,vt 此時(shí)割集（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),