運(yùn)籌學(xué)最大流推薦課件

1、Page 12021/8/22如何制定一個(gè)運(yùn)輸計(jì)劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。如何制定一個(gè)運(yùn)輸計(jì)劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。這就是一個(gè)網(wǎng)絡(luò)最大流問題。這就是一個(gè)網(wǎng)絡(luò)最大流問題。Page 22021/8/22基本概念：基本概念：隊(duì)網(wǎng)絡(luò)上的每條弧隊(duì)網(wǎng)絡(luò)上的每條弧(vi,vj)都給出一個(gè)最大的通都給出一個(gè)最大的通過能力，稱為該弧的過能力，稱為該弧的，簡(jiǎn)記為，簡(jiǎn)記為cij。容量網(wǎng)絡(luò)中通常規(guī)定。容量網(wǎng)絡(luò)中通常規(guī)定一個(gè)一個(gè)(也稱源點(diǎn)，記為也稱源點(diǎn)，記為s)和一個(gè)和一個(gè)(也稱匯點(diǎn)，記為也稱匯點(diǎn)，記為t)，網(wǎng)絡(luò)中其他點(diǎn)稱為網(wǎng)絡(luò)中其他點(diǎn)稱為。st4844122679Page 32021/8/222

2、. 網(wǎng)絡(luò)的最大流網(wǎng)絡(luò)的最大流是指網(wǎng)絡(luò)中從發(fā)點(diǎn)到收點(diǎn)之間允許通過的最大流量。是指網(wǎng)絡(luò)中從發(fā)點(diǎn)到收點(diǎn)之間允許通過的最大流量。3. 流與可行流流與可行流 流流是指加在網(wǎng)絡(luò)各條弧上的實(shí)際流量，對(duì)加在弧是指加在網(wǎng)絡(luò)各條弧上的實(shí)際流量，對(duì)加在弧(vi,vj)上上的負(fù)載量記為的負(fù)載量記為fij。若。若fij=0，稱為零流。，稱為零流。滿足以下條件的一組流稱為滿足以下條件的一組流稱為可行流可行流。 容量限制條件。容量網(wǎng)絡(luò)上所有的弧滿足：容量限制條件。容量網(wǎng)絡(luò)上所有的弧滿足：0fijcij 中間點(diǎn)平衡條件。中間點(diǎn)平衡條件。),(0),(),(tsivvfvvfijji 若以若以v(f)表示網(wǎng)絡(luò)中從表示網(wǎng)絡(luò)中從s

3、t的流量，則有：的流量，則有： 0),(),()(tjjsvvfvvffvPage 42021/8/22結(jié)論：任何網(wǎng)絡(luò)上一定存在可行流。（零流即是結(jié)論：任何網(wǎng)絡(luò)上一定存在可行流。（零流即是可行流）可行流）網(wǎng)絡(luò)最大流問題：網(wǎng)絡(luò)最大流問題：指滿足容量限制條件和中間點(diǎn)平衡的條件下，使指滿足容量限制條件和中間點(diǎn)平衡的條件下，使v(f)值達(dá)到最大。值達(dá)到最大。Page 52021/8/22 割與割集割與割集割是指容量網(wǎng)絡(luò)中的發(fā)點(diǎn)和收點(diǎn)分割開，并使割是指容量網(wǎng)絡(luò)中的發(fā)點(diǎn)和收點(diǎn)分割開，并使st的流中斷的流中斷的一組弧的集合。割容量是組成割集合中的各條弧的容量之的一組弧的集合。割容量是組成割集合中的各條弧的容

4、量之和，用和，用 表示。表示。),(VVc ),(),(),(),(VVjijivvcVVc如下圖中，如下圖中，AA將網(wǎng)絡(luò)上的點(diǎn)分割成將網(wǎng)絡(luò)上的點(diǎn)分割成 兩個(gè)集合。并兩個(gè)集合。并有有 ，稱弧的集合，稱弧的集合(v1,v3),(v2,v4)是一個(gè)割，且是一個(gè)割，且 的流量為的流量為18。 VV ,VtVs ,VV Page 62021/8/22v1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(3)7(6)AABBPage 72021/8/22 設(shè)網(wǎng)絡(luò)設(shè)網(wǎng)絡(luò)N中一個(gè)從中一個(gè)從 s 到到 t 的流的流 f 的流量為的流量為v(f )， (V, V )為任意一個(gè)割集，則為任

5、意一個(gè)割集，則 v(f ) = f(V, V ) f(V , V) 對(duì)網(wǎng)絡(luò)對(duì)網(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ò)中在網(wǎng)絡(luò)中st的最大流量等于它的最小割集的容量，的最大流量等于它的最小割集的容量，即：即： v (f ) = c (V, V ) Page 82021/8/22在網(wǎng)絡(luò)的發(fā)點(diǎn)和收點(diǎn)之間能找到一條鏈，在該鏈上所在網(wǎng)

6、絡(luò)的發(fā)點(diǎn)和收點(diǎn)之間能找到一條鏈，在該鏈上所有指向?yàn)橛兄赶驗(yàn)閟t的弧，稱為前向弧，記作的弧，稱為前向弧，記作+,存在存在f0，則稱這樣的鏈，則稱這樣的鏈為增廣鏈。例如下圖中，為增廣鏈。例如下圖中，sv2v1v3v4t。 網(wǎng)絡(luò)網(wǎng)絡(luò)N中的流中的流 f 是最大流當(dāng)且僅當(dāng)是最大流當(dāng)且僅當(dāng)N中不包含任何增廣中不包含任何增廣鏈鏈Page 92021/8/22v1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(4)7(5)Page 102021/8/22求網(wǎng)絡(luò)最大流的標(biāo)號(hào)算法：求網(wǎng)絡(luò)最大流的標(biāo)號(hào)算法：由一個(gè)流開始，系統(tǒng)地搜尋增廣鏈，然后在此鏈上增由一個(gè)流開始，系統(tǒng)地搜尋增廣鏈，然后在

7、此鏈上增流，繼續(xù)這個(gè)增流過程，直至不存在增廣鏈。流，繼續(xù)這個(gè)增流過程，直至不存在增廣鏈。找出第一個(gè)可行流，（例如所有弧的流量找出第一個(gè)可行流，（例如所有弧的流量fij =0。）。）用標(biāo)號(hào)的方法找一條增廣鏈用標(biāo)號(hào)的方法找一條增廣鏈 首先給發(fā)點(diǎn)首先給發(fā)點(diǎn)s標(biāo)號(hào)標(biāo)號(hào)(),標(biāo)號(hào)中的數(shù)字表示允許的最大調(diào)整量。標(biāo)號(hào)中的數(shù)字表示允許的最大調(diào)整量。 選擇一個(gè)點(diǎn)選擇一個(gè)點(diǎn) vi 已標(biāo)號(hào)并且另一端未標(biāo)號(hào)的弧沿著某條鏈向已標(biāo)號(hào)并且另一端未標(biāo)號(hào)的弧沿著某條鏈向收點(diǎn)檢查：收點(diǎn)檢查：Page 112021/8/22 如果弧的起點(diǎn)為如果弧的起點(diǎn)為vi，并且有，并且有fij0，則，則vj標(biāo)號(hào)標(biāo)號(hào)(fji)(3) 重復(fù)第重復(fù)第

8、(2)步，可能出現(xiàn)兩種結(jié)局：步，可能出現(xiàn)兩種結(jié)局： 標(biāo)號(hào)過程中斷，標(biāo)號(hào)過程中斷，t無法標(biāo)號(hào)，說明網(wǎng)絡(luò)中不存在增廣鏈，目無法標(biāo)號(hào)，說明網(wǎng)絡(luò)中不存在增廣鏈，目前流量為最大流。同時(shí)可以確定最小割集，前流量為最大流。同時(shí)可以確定最小割集，記已標(biāo)號(hào)的點(diǎn)集記已標(biāo)號(hào)的點(diǎn)集為為V,未標(biāo)號(hào)的點(diǎn)集合為未標(biāo)號(hào)的點(diǎn)集合為V,(V,V)為網(wǎng)絡(luò)的最小割。為網(wǎng)絡(luò)的最小割。 t得到標(biāo)號(hào)，反向追蹤在網(wǎng)絡(luò)中找到一條從得到標(biāo)號(hào)，反向追蹤在網(wǎng)絡(luò)中找到一條從s到到t得由標(biāo)號(hào)點(diǎn)得由標(biāo)號(hào)點(diǎn)及相應(yīng)的弧連接而成的增廣鏈。繼續(xù)第及相應(yīng)的弧連接而成的增廣鏈。繼續(xù)第(4)步步Page 122021/8/22 所所有有非非增增廣廣鏈鏈上上的的弧弧對(duì)對(duì)

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

10、2021/8/22解：解：(1) 先給先給s標(biāo)號(hào)標(biāo)號(hào)()v1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()Page 152021/8/22v1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()(2) 檢查與檢查與s點(diǎn)相鄰的未標(biāo)號(hào)的點(diǎn)，因點(diǎn)相鄰的未標(biāo)號(hào)的點(diǎn)，因fs1cs1，故對(duì)，故對(duì)v1標(biāo)號(hào)標(biāo)號(hào)=min, cs1-fs1=1,)1( (1)Page 162021/8/22v1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(6)()(1)(2) 檢查與檢查與v1點(diǎn)相鄰的未標(biāo)號(hào)的點(diǎn)，

11、因點(diǎn)相鄰的未標(biāo)號(hào)的點(diǎn)，因f13c13，故對(duì)，故對(duì)v3標(biāo)號(hào)標(biāo)號(hào)=min1, c13-f13= min1, 6= 1)3( (1)Page 172021/8/22v1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()(1)(1)(3) 檢查與檢查與v3點(diǎn)相鄰的未標(biāo)號(hào)的點(diǎn)，因點(diǎn)相鄰的未標(biāo)號(hào)的點(diǎn)，因f3tc3t，故對(duì)，故對(duì)vt標(biāo)號(hào)標(biāo)號(hào)=min1, c3t-f3t= min1, 1= 1)(t (1)找到一條增廣鏈找到一條增廣鏈sv1v3tPage 182021/8/22(4) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的修改增廣鏈上的流量，非增廣鏈上的流量

12、不變，得到新的可行流?？尚辛鳌1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(3)7(5)()(1)(1)(1)11 sf113 f13 tfPage 192021/8/22(5) 擦除所有標(biāo)號(hào)，重復(fù)上述標(biāo)號(hào)過程，尋找另外的增廣鏈。擦除所有標(biāo)號(hào)，重復(fù)上述標(biāo)號(hào)過程，尋找另外的增廣鏈。v1v3v2v48(8)9(4)5(5)10(8)6(0)2(0)9(9)5(3)7(5)()(1)(1)(1)Page 202021/8/22(5) 擦除所有標(biāo)號(hào)，重復(fù)上述標(biāo)號(hào)過程，尋找另外的增廣鏈。擦除所有標(biāo)號(hào)，重復(fù)上述標(biāo)號(hào)過程，尋找另外的增廣鏈。v1v3v2v48(8)9(4)5(

13、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=1Page 212021/8/22(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 tfPage 222021/8/22v1v3v2v48(8)9(5)

14、5(5)10(9)6(0)2(0)9(9)5(2)7(6)()(2)(2)(2)(1)(1)(7) 擦除所有標(biāo)號(hào)，重復(fù)上述標(biāo)號(hào)過程，尋找另外的增廣鏈。擦除所有標(biāo)號(hào)，重復(fù)上述標(biāo)號(hào)過程，尋找另外的增廣鏈。Page 232021/8/22v1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)()(1)(1)(1)(7) 擦除所有標(biāo)號(hào)，重復(fù)上述標(biāo)號(hào)過程，尋找另外的增廣鏈。擦除所有標(biāo)號(hào)，重復(fù)上述標(biāo)號(hào)過程，尋找另外的增廣鏈。(2)=min,1=1(1)=min1,2=1(3)=min1,4=1,4321VVtvVvvvsV 最小割為最小割為Page 242021/8/2

15、2例例6.9 求下圖求下圖st的最大流，并找出最小割的最大流，并找出最小割stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)Page 252021/8/22stv1v2v3v4v54(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)號(hào)尋找增廣鏈。在已知可行流的基礎(chǔ)上，通過標(biāo)號(hào)尋找增廣鏈。()(2)=min,6=6(6)(3)=min6,2=2(2)(t)=min2,5=2(2)Page 262021/8/22(2) 修改增廣鏈上的流量

16、，非增廣鏈上的流量不變，得到新的修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流?？尚辛?。stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)()(6)(2)(2)22 sf223 f23 tfPage 272021/8/22(3) 擦除原標(biāo)號(hào)，重新搜尋增廣鏈。擦除原標(biāo)號(hà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)Page 282021/8/22(4) 重新搜尋增廣鏈。重新搜尋增廣鏈。stv1v2v3

17、v4v54(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=1Page 292021/8/22(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 tfPage 302021/8

18、/22(6) 擦除原標(biāo)號(hào)擦除原標(biāo)號(hà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)Page 312021/8/22stv1v2v3v4v54(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)(5)=min,1=1(5)=min1,1=1(5)=min1,2=1(7) 重新搜尋增廣鏈。重新搜尋增廣鏈。Page 322021/8/22(8) 調(diào)整增廣鏈上的流量，非增廣鏈流量不變，得到新的可行流調(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 tfPage 332021/8/22stv1v2v3v4v54(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)號(hào)擦除原標(biāo)號(hào)Page 342021/8/22stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)