運(yùn)籌學(xué)：教案_圖論4

1、 第四節(jié)第四節(jié) 網(wǎng)絡(luò)最大流問題網(wǎng)絡(luò)最大流問題例例 連接某產(chǎn)品產(chǎn)地連接某產(chǎn)品產(chǎn)地v1和銷地和銷地v6的交通網(wǎng)如下：的交通網(wǎng)如下：v2v5348v3v1v4v65106111735?。ɑ。╲i，vj）：從）：從vi到到vj的運(yùn)輸線，的運(yùn)輸線，弧旁數(shù)字：這條運(yùn)輸線的最大通過能力弧旁數(shù)字：這條運(yùn)輸線的最大通過能力,制定一個運(yùn)輸方案，使從制定一個運(yùn)輸方案，使從v1到到v6的產(chǎn)品數(shù)量最多。的產(chǎn)品數(shù)量最多。弧旁數(shù)字：弧旁數(shù)字：運(yùn)輸能力運(yùn)輸能力。問題：這個運(yùn)輸網(wǎng)絡(luò)中，從問題：這個運(yùn)輸網(wǎng)絡(luò)中，從v1到到v6的最大輸送量是多少？的最大輸送量是多少？v2v5313v3v1v4v61536222一、基本概念與定理一、

2、基本概念與定理1. 網(wǎng)絡(luò)與流網(wǎng)絡(luò)與流定義定義1 給定一個有向圖給定一個有向圖D=（V，A），在），在V中指定中指定 一點(diǎn)一點(diǎn)vs 稱為發(fā)點(diǎn)，指定另一點(diǎn)稱為發(fā)點(diǎn)，指定另一點(diǎn)vt 稱為收點(diǎn)，稱為收點(diǎn)， 其余點(diǎn)稱中間點(diǎn)。任意弧其余點(diǎn)稱中間點(diǎn)。任意弧(vi ，vj )A，有，有 cij 0，稱為弧的容量。稱，稱為弧的容量。稱D為一個容量網(wǎng)為一個容量網(wǎng) 絡(luò)。記為絡(luò)。記為D=（V，A，C）。）。流流: 定義在弧集定義在弧集A上的一個函數(shù)上的一個函數(shù)f=f(vi ,vj )，并稱，并稱 f(vi ,vj )為弧為弧(vi ,vj )上的流量。簡記上的流量。簡記 f = fi ,j 弧旁數(shù)字：弧旁數(shù)字： 容量

3、容量(a)圖是一個網(wǎng)絡(luò)圖是一個網(wǎng)絡(luò)v2v5348v3v1v4v65106111735v2v5313v3v1v4v61536222弧旁數(shù)字：弧旁數(shù)字： 流量流量 cij fijvivjv2v53.14.08.3v3v1v4v65.010.56.311.617.43.25.32. 可行流與最大流可行流與最大流定義定義2 滿足下述條件的流滿足下述條件的流 f 稱為可行流稱為可行流:1)容量限制條件容量限制條件: 對每一弧對每一弧(vi , vj )A 0fij cij2)平衡條件平衡條件: 對中間點(diǎn)對中間點(diǎn)vi (is,t ),有有 0 A),(A),( ijjivvjivvijff)V( : A)

4、,(A),(fffvsjjsvvjsvvsjs )V( : A),(A),(fffvtjjtvvjtvvtjt V( f ) 稱為可行流稱為可行流 f 的流量的流量,即發(fā)點(diǎn)的凈輸出量。即發(fā)點(diǎn)的凈輸出量。如所有如所有fij=0， 零流。零流。可行流總是可行流總是存在的存在的3. 增廣鏈增廣鏈對可行流對可行流 f = fij ：非飽和?。悍秋柡突。篺ij 0零流弧：零流?。篺ij =0 鏈的方向：若鏈的方向：若是聯(lián)結(jié)是聯(lián)結(jié)vs和和vt的一條鏈，定義鏈的方的一條鏈，定義鏈的方向是從向是從vs到到vt 。 前向?。夯〉姆较蚺c鏈的方向一致，記為前向?。夯〉姆较蚺c鏈的方向一致，記為+。后向弧：弧的方向與鏈

5、的方向相反，記為后向?。夯〉姆较蚺c鏈的方向相反，記為-。v2v53.34.18.3v3v1v4v65.110.56.311.617.23.25.2 = (v1,v2,v3,v4,v5,v6 )+=(v1,v2) ,(v2,v3), (v3 , v4),(v5,v6) - =(v5,v4)v2v53.34.18.3v3v1v4v65.110.56.311.617.23.25.2定義定義3 設(shè)設(shè) f 是一個可行流是一個可行流, 是從是從vs 到到vt 的一條鏈的一條鏈,若若滿滿 足下列條件足下列條件,稱之為稱之為(關(guān)于可行流關(guān)于可行流 f 的的)一條增廣一條增廣 鏈。鏈。(vi , vj ) -

6、0 fij cij 后向弧后向弧 是非零流弧，是非零流弧，(vi , vj ) + 0 fij cij 前向弧是前向弧是 非飽和弧，非飽和弧，v1v2v3v4v5v68.46.06.53.35.44. 截集與截量截集與截量 設(shè)設(shè)S，T V，S T= ，始點(diǎn)在，始點(diǎn)在S，終點(diǎn)在，終點(diǎn)在T中中的所有的所有弧的集合弧的集合，記為（，記為（S，T）。）。ST定義定義4 網(wǎng)絡(luò)網(wǎng)絡(luò)D=(V,A,C）,若點(diǎn)集若點(diǎn)集V被剖分為兩個非空集被剖分為兩個非空集 合合V1和和V1,使使vsV1，vt V1，則把弧集，則把弧集(V1，V1) 稱為是分離稱為是分離vs和和vt的截集。的截集。v2v53.34.18.3v3

7、v1v4v65.110.56.311.617.23.25.2=(v1,v2,v3)V1V1=(v4,v5,v6)定義定義5 給一截集（給一截集（V1，V1），把截集（），把截集（V1，V1）中所）中所 有弧的容量之和稱為這個截集的容量（簡稱為截有弧的容量之和稱為這個截集的容量（簡稱為截 量），記為量），記為C （V1，V1），）， 即即 )V,(V),(1111)V,C(V jivvijc定理定理1 可行流可行流 f *是最大流，當(dāng)且僅當(dāng)不存在關(guān)于是最大流，當(dāng)且僅當(dāng)不存在關(guān)于 f * 的增廣鏈。的增廣鏈。 二、尋求最大流的標(biāo)號法（二、尋求最大流的標(biāo)號法（FordFulkerson） 從任一個可

8、行流從任一個可行流 f 出發(fā)（若網(wǎng)絡(luò)中沒有給定出發(fā)（若網(wǎng)絡(luò)中沒有給定 f ，則從零流開始），經(jīng)過標(biāo)號過程與調(diào)整過程。則從零流開始），經(jīng)過標(biāo)號過程與調(diào)整過程。（一）標(biāo)號過程（一）標(biāo)號過程 未未標(biāo)標(biāo)號號點(diǎn)點(diǎn)未未檢檢查查已已檢檢查查標(biāo)標(biāo)號號點(diǎn)點(diǎn)網(wǎng)網(wǎng)絡(luò)絡(luò)中中的的點(diǎn)點(diǎn)標(biāo)號：（前點(diǎn)標(biāo)記，前點(diǎn)到該點(diǎn)的弧流量可調(diào)整量）標(biāo)號：（前點(diǎn)標(biāo)記，前點(diǎn)到該點(diǎn)的弧流量可調(diào)整量） 開始，開始，vs 標(biāo)上（標(biāo)上（0，），），vs 是標(biāo)號未檢查的點(diǎn)，是標(biāo)號未檢查的點(diǎn)，其余點(diǎn)都是未標(biāo)號點(diǎn)，一般地，取一個標(biāo)號未檢查其余點(diǎn)都是未標(biāo)號點(diǎn)，一般地，取一個標(biāo)號未檢查的點(diǎn)的點(diǎn)vi ，對一切未標(biāo)號的點(diǎn)，對一切未標(biāo)號的點(diǎn)vj 。（1）若?。ǎ┤艋?/p>

9、（vi，vj）上，）上，fij0，則給，則給vj 標(biāo)號標(biāo)號(-i， l (vj)，l (vj)=minl (vi), fji, vj 成為標(biāo)號而未檢查的點(diǎn)。成為標(biāo)號而未檢查的點(diǎn)。fij0vivj(-i , l(vj)l(vj)=minl(vi),fji 重復(fù)上述步驟，一旦重復(fù)上述步驟，一旦vt被標(biāo)號，則得到一條被標(biāo)號，則得到一條vs到到vt的的增廣鏈。若所有標(biāo)號都已檢查過，而增廣鏈。若所有標(biāo)號都已檢查過，而vt尚未標(biāo)號，結(jié)束，尚未標(biāo)號，結(jié)束，這時(shí)可行流，即最大流。這時(shí)可行流，即最大流。（二）調(diào)整過程（二）調(diào)整過程 從從vt 開始，反向追蹤，找出增廣鏈開始，反向追蹤，找出增廣鏈 ，并在，并在上進(jìn)

10、上進(jìn)行流量調(diào)整。行流量調(diào)整。（1）找增廣鏈）找增廣鏈 如如vt 的第一個標(biāo)號為的第一個標(biāo)號為k（或或-k），），則?。▌t弧（vk，vt）（或弧（或?。╲t，vk) )。檢查。檢查vk 的第一個標(biāo)號，若為的第一個標(biāo)號，若為i（或（或-i），則），則(vi,vk) (或或(vk,vi) )。再檢查。再檢查vi 的第一的第一個標(biāo)號個標(biāo)號,依此下去依此下去,直到直到vs 。被找出的弧構(gòu)成了增廣鏈。被找出的弧構(gòu)成了增廣鏈 。（2）流量調(diào)整）流量調(diào)整令調(diào)整量令調(diào)整量 是是 l(vt)，構(gòu)造新的可行流，構(gòu)造新的可行流 f ，令令 uvv fuvvfuvvffjiijjiijjiijij ),( ),( ),

11、( - 去掉所有的標(biāo)號去掉所有的標(biāo)號,對新的可行流對新的可行流 f = fij,重新進(jìn)重新進(jìn)入標(biāo)號過程。入標(biāo)號過程。例例 用標(biāo)號法求下圖網(wǎng)絡(luò)的最大流?；∨缘臄?shù)字是用標(biāo)號法求下圖網(wǎng)絡(luò)的最大流。弧旁的數(shù)字是( cij , fij)。解：（一）標(biāo)號過程。解：（一）標(biāo)號過程。（1）給）給vs標(biāo)上（標(biāo)上（0，）；）；v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0，） 415minmin111 ,)fc(),v( l)v( lsss在弧（在?。╲s，v2）上，）上， fs2=cs2=3, 不滿足標(biāo)號條件不滿足標(biāo)號條件。（2）檢查）檢查

12、vs，在?。?，在?。╲s，v1）上，）上，fs1=1，cs1=5， fs10， 給給v2標(biāo)號標(biāo)號 (-1, l l(v2), ,f),v( l)v( l114minmin2112 在弧（在?。╲1，v3）上，）上，f13=2， c13=2，不滿足標(biāo)號條件。，不滿足標(biāo)號條件。v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0，）（s，4）（-1，1）（4）檢查）檢查v2，在弧（，在?。╲3，v2）上，）上，f32=10， 給給v3標(biāo)號標(biāo)號 (-2, l(v3), 這里這里 , 11 , 1min),(min)(3223fvlvl

13、（-2，1）在弧（在?。╲2，v4）上，）上，f24=3，c24=4，f24c24, 給給v4標(biāo)號標(biāo)號(2, l(v4), 其中其中 ,min)fc(),v( l)v( l111min242424 （5）檢查）檢查v3，在?。?，在?。╲3，vt）上，）上，f3t=1， c3t=2， f3tc3t， 給給vt標(biāo)號標(biāo)號 (3, l(vt), 這里這里 ,min)fc(),v( lmin)v( lttt111333 vt得到標(biāo)號，標(biāo)號過程結(jié)束。得到標(biāo)號，標(biāo)號過程結(jié)束。v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0，）（s，4）（

14、-1，1）（-2，1）(2，1)(3，1)（二）調(diào)整過程（二）調(diào)整過程 ：從：從vt 開始逆向追蹤，找到增廣鏈。開始逆向追蹤，找到增廣鏈。（vs,v1,v2,v3,vt） =1，在在上進(jìn)行流量上進(jìn)行流量 =1的調(diào)整，得的調(diào)整，得可行流可行流 f 如右如右圖所示：圖所示：v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0，）（s，4）（-1，1）（-2，1）(2，1)(3，1)v2v3v1vsv4vt(3，3)(4，3)(1，0)(5，3)(5，2)(2，2)(2，2)(1，0)(3,0)去掉各點(diǎn)標(biāo)號，從去掉各點(diǎn)標(biāo)號，從vs開始

15、，重新標(biāo)號。開始，重新標(biāo)號。點(diǎn)點(diǎn)v1：標(biāo)號過程：標(biāo)號過程無法進(jìn)行，所以無法進(jìn)行，所以f 即為最大流。即為最大流。V（f ）=3+2=5v2v3v1vsv4vt(3，3)(4，3)(1，0)(5，3)(5，2)(2，2)(2，2)(1，0)(3,0)（0，）（s，3）截集：截集：V1，V1=（vs，v2），（），（v1，v3） V（f ）=CV1，V1=5V1=(vs,v1) V1=(v2,v3,v4, vt)問題：問題：(v2,v1)是不是截集是不是截集V1，V1中的??？中的??？例例 1 下圖中，從三口油井下圖中，從三口油井、經(jīng)管道將油輸至經(jīng)管道將油輸至脫水處理廠脫水處理廠和和，中間經(jīng)，中間經(jīng)、三個泵站。已知三個泵站。已知圖中弧旁數(shù)字為各管道通過的最大能力（噸圖中弧旁數(shù)字為各管道通過的最大能力（噸/小時(shí)），小時(shí)），求從油井每小時(shí)能輸送到處理廠的最大流量。求從油井每小時(shí)能輸送到處理廠的最大流量。 87654321201030102015302050102050 多源、多匯的最大流問題多源、多匯的最大流問題單源、單匯。單源、單匯。s208015t6050 xv1v6v2v4v5v3y141694197226125313156例例2v2v5v34931064343482v1v5v4vtvs練習(xí)練習(xí)例例3 某產(chǎn)品從倉庫運(yùn)往市場銷售。已知各倉庫的可供某產(chǎn)品從倉庫運(yùn)往市場銷售。已知