運籌學(xué)最大流PPT課件

1、網(wǎng)絡(luò)的最大流 基本概念：隊網(wǎng)絡(luò)上的每條弧(vi,vj)都給出一個最大的通過能力，稱為該弧的，簡記為cij。容量網(wǎng)絡(luò)中通常規(guī)定一個(也稱源點，記為s)和一個(也稱匯點，記為t)，網(wǎng)絡(luò)中其他點稱為。st4844122679第1頁/共37頁網(wǎng)絡(luò)的最大流 2. 網(wǎng)絡(luò)的最大流是指網(wǎng)絡(luò)中從發(fā)點到收點之間允許通過的最大流量。3. 流與可行流 流是指加在網(wǎng)絡(luò)各條弧上的實際流量，對加在弧(vi,vj)上的負(fù)載量記為fij。若fij=0，稱為零流。滿足以下條件的一組流稱為可行流。 容量限制條件。容量網(wǎng)絡(luò)上所有的弧滿足：0fijcij 中間點平衡條件。),(0),(),(tsivvfvvfijji 若以v(f)表示

2、網(wǎng)絡(luò)中從st的流量，則有： 0),(),()(tjjsvvfvvffv第2頁/共37頁網(wǎng)絡(luò)的最大流結(jié)論：任何網(wǎng)絡(luò)上一定存在可行流。（零流即是可行流）網(wǎng)絡(luò)最大流問題：指滿足容量限制條件和中間點平衡的條件下，使v(f)值達(dá)到最大。第3頁/共37頁網(wǎng)絡(luò)的最大流 割與割集割是指容量網(wǎng)絡(luò)中的發(fā)點和收點分割開，并使st的流中斷的一組弧的集合。割容量是組成割集合中的各條弧的容量之和，用 表示。),(VVc ),(),(),(),(VVjijivvcVVc如下圖中，AA將網(wǎng)絡(luò)上的點分割成 兩個集合。并有 ，稱弧的集合(v1,v3),(v2,v4)是一個割，且 的流量為18。 VV ,VtVs ,VV 第4頁/

3、共37頁網(wǎng)絡(luò)的最大流v1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(3)7(6)AABB第5頁/共37頁網(wǎng)絡(luò)的最大流 設(shè)網(wǎng)絡(luò)N中一個從 s 到 t 的流 f 的流量為v(f )， (V, V)為任意一個割集，則 v(f ) = f(V, V) f(V, V) 對網(wǎng)絡(luò) N中任意流量v(f )和割集 (V, V)，有v(f ) c(V, V)證明 w= f(V, V) f(V, V) f(V, V) c(V, V) 最大流量v (f )不大于最小割集的容量，即：v (f ) minc(V, V) 在網(wǎng)絡(luò)中st的最大流量等于它的最小割集的容量， 即： v (f ) =

4、c (V, V) 第6頁/共37頁網(wǎng)絡(luò)的最大流在網(wǎng)絡(luò)的發(fā)點和收點之間能找到一條鏈，在該鏈上所有指向為st的弧，稱為前向弧，記作+,存在f0，則稱這樣的鏈為增廣鏈。例如下圖中，sv2v1v3v4t。 網(wǎng)絡(luò)N中的流 f 是最大流當(dāng)且僅當(dāng)N中不包含任何增廣鏈第7頁/共37頁網(wǎng)絡(luò)的最大流v1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(4)7(5)第8頁/共37頁網(wǎng)絡(luò)的最大流 求網(wǎng)絡(luò)最大流的標(biāo)號算法：由一個流開始，系統(tǒng)地搜尋增廣鏈，然后在此鏈上增流，繼續(xù)這個增流過程，直至不存在增廣鏈。(1) 找出第一個可行流，（例如所有弧的流量fij =0。）(2) 用標(biāo)號的方法找一條增廣

5、鏈 首先給發(fā)點s標(biāo)號(),標(biāo)號中的數(shù)字表示允許的最大調(diào)整量。 選擇一個點 vi 已標(biāo)號并且另一端未標(biāo)號的弧沿著某條鏈向收點檢查：第9頁/共37頁網(wǎng)絡(luò)的最大流 如果弧的起點為vi，并且有fij0，則vj標(biāo)號(fji)(3) 重復(fù)第(2)步，可能出現(xiàn)兩種結(jié)局： 標(biāo)號過程中斷，t無法標(biāo)號，說明網(wǎng)絡(luò)中不存在增廣鏈，目前流量為最大流。同時可以確定最小割集，記已標(biāo)號的點集為V,未標(biāo)號的點集合為V,(V,V)為網(wǎng)絡(luò)的最小割。 t得到標(biāo)號，反向追蹤在網(wǎng)絡(luò)中找到一條從s到t得由標(biāo)號點及相應(yīng)的弧連接而成的增廣鏈。繼續(xù)第(4)步第10頁/共37頁網(wǎng)絡(luò)的最大流 所有非增廣鏈上的弧所有非增廣鏈上的弧對增廣鏈上所有后向弧

6、對增廣鏈上所有后向弧對增廣鏈上所有前向弧對增廣鏈上所有前向弧ftftff)()(4) 修改流量。設(shè)原圖可行流為f，令得到網(wǎng)絡(luò)上一個新的可行流f。(5) 擦除圖上所有標(biāo)號，重復(fù)(1)-(4)步，直到圖中找不到任何增廣鏈，計算結(jié)束。第11頁/共37頁網(wǎng)絡(luò)的最大流例6.10 用標(biāo)號算法求下圖中st的最大流量，并找出最小割。v1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)第12頁/共37頁網(wǎng)絡(luò)的最大流 解：(1) 先給s標(biāo)號()v1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()第13頁/共37頁網(wǎng)絡(luò)的最大流v1v3v

7、2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()(2) 檢查與s點相鄰的未標(biāo)號的點，因fs1cs1，故對v1標(biāo)號=min, cs1-fs1=1,)1( (1)第14頁/共37頁網(wǎng)絡(luò)的最大流v1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(6)()(1)(2) 檢查與v1點相鄰的未標(biāo)號的點，因f13c13，故對v3標(biāo)號=min1, c13-f13= min1, 6= 1)3( (1)第15頁/共37頁網(wǎng)絡(luò)的最大流v1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()(1)(1)(3)

8、檢查與v3點相鄰的未標(biāo)號的點，因f3tc3t，故對vt標(biāo)號=min1, c3t-f3t= min1, 1= 1)(t (1)找到一條增廣鏈sv1v3t第16頁/共37頁網(wǎng)絡(luò)的最大流(4) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。v1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(3)7(5)()(1)(1)(1)11 sf113 f13 tf第17頁/共37頁網(wǎng)絡(luò)的最大流(5) 擦除所有標(biāo)號，重復(fù)上述標(biāo)號過程，尋找另外的增廣鏈。v1v3v2v48(8)9(4)5(5)10(8)6(0)2(0)9(9)5(3)7(5)()(1)(1)(1)第18頁/共

9、37頁網(wǎng)絡(luò)的最大流(5) 擦除所有標(biāo)號，重復(fù)上述標(biāo)號過程，尋找另外的增廣鏈。v1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)()(2)(2)=min,2=2(2)(1)=min2,3=2(3)=min2,5=2(2)(1)(4)=min2,1=1(1)(t)=min1,2=1第19頁/共37頁網(wǎng)絡(luò)的最大流(6) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。v1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)()(2)(2)(2)(1)(1)12 sf121 f113 f134 f14 tf第20頁/共

10、37頁網(wǎng)絡(luò)的最大流v1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)()(2)(2)(2)(1)(1)(7) 擦除所有標(biāo)號，重復(fù)上述標(biāo)號過程，尋找另外的增廣鏈。第21頁/共37頁網(wǎng)絡(luò)的最大流v1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)()(1)(1)(1)(7) 擦除所有標(biāo)號，重復(fù)上述標(biāo)號過程，尋找另外的增廣鏈。(2)=min,1=1(1)=min1,2=1(3)=min1,4=1,4321VVtvVvvvsV 最小割為最小割為第22頁/共37頁網(wǎng)絡(luò)的最大流例6.9 求下圖st的最大流，并找出最小割stv1v

11、2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)第23頁/共37頁網(wǎng)絡(luò)的最大流stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)解: (1) 在已知可行流的基礎(chǔ)上，通過標(biāo)號尋找增廣鏈。()(2)=min,6=6(6)(3)=min6,2=2(2)(t)=min2,5=2(2)第24頁/共37頁網(wǎng)絡(luò)的最大流(2) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4

12、(2)2(2)7(6)8(3)()(6)(2)(2)22 sf223 f23 tf第25頁/共37頁網(wǎng)絡(luò)的最大流(3) 擦除原標(biāo)號，重新搜尋增廣鏈。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)()(6)(2)(2)第26頁/共37頁網(wǎng)絡(luò)的最大流(4) 重新搜尋增廣鏈。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)()(2)=min,4=4(4)(1)(5)=min4,1=1(3)=min1,2=1(1)(1)(t)=min1,3=1第27頁/

13、共37頁網(wǎng)絡(luò)的最大流(5) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)()(4)(1)(1)(1)12 sf125 f153 f13 tf第28頁/共37頁網(wǎng)絡(luò)的最大流(6) 擦除原標(biāo)號stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)()(4)(1)(1)(1)第29頁/共37頁網(wǎng)絡(luò)的最大流stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4

14、)2(2)7(6)8(6)()(1)(1)(1)(5)=min,1=1(5)=min1,1=1(5)=min1,2=1(7) 重新搜尋增廣鏈。第30頁/共37頁網(wǎng)絡(luò)的最大流(8) 調(diào)整增廣鏈上的流量，非增廣鏈流量不變，得到新的可行流stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)()(1)(1)(1)15 sf153 f13 tf第31頁/共37頁網(wǎng)絡(luò)的最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)()(1)(1)(1)(9) 擦除原標(biāo)號第

15、32頁/共37頁網(wǎng)絡(luò)的最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)(10) 重新標(biāo)號，搜索增廣鏈()(1)=min,1=1(1)(5)=min1,1=1(1)(4)=min1,1=1(1)(t)=min1,1=1(1)第33頁/共37頁網(wǎng)絡(luò)的最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)()(1)(1)(1)(1)(11) 調(diào)整增廣鏈上的流量，非增廣鏈流量不變，得到新的可行流11 sf115 f154 f14 tf第34頁/共37頁網(wǎng)絡(luò)的最大流stv1v2v3v4v54(4)3(3)10(7)3(3)1(1)4(4)3(3)5(5)4(4)2(2)