運籌學PPT完整版

1、運籌學運籌學Page 21.最大流的問題描述；最大流的問題描述；2.基本概念；基本概念；3.割與割集的介紹；割與割集的介紹；4.增廣鏈的基本定義；增廣鏈的基本定義；5.網(wǎng)絡最大流的標號算法；網(wǎng)絡最大流的標號算法；Page 3如何制定一個運輸計劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。如何制定一個運輸計劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。這就是一個網(wǎng)絡最大流問題。這就是一個網(wǎng)絡最大流問題。Page 4基本概念：基本概念：網(wǎng)絡上網(wǎng)絡上的每條弧的每條弧(vi,vj)都給出一個最大的通都給出一個最大的通過能力，稱為該弧的過能力，稱為該弧的，簡記為，簡記為cij。容量網(wǎng)絡中通常規(guī)定。容量網(wǎng)絡中通常規(guī)定一個一個

2、(也稱源點，記為也稱源點，記為s)和一個和一個(也稱匯點，記為也稱匯點，記為t)，網(wǎng)絡中其他點稱為網(wǎng)絡中其他點稱為。st4844122679Page 52. 網(wǎng)絡的最大流網(wǎng)絡的最大流是指網(wǎng)絡中從發(fā)點到收點之間允許通過的最大流量。是指網(wǎng)絡中從發(fā)點到收點之間允許通過的最大流量。3. 流與可行流流與可行流 流流是指加在網(wǎng)絡各條弧上的實際流量，對加在弧是指加在網(wǎng)絡各條弧上的實際流量，對加在弧(vi,vj)上上的負載量記為的負載量記為fij。若。若fij=0，稱為零流。，稱為零流。滿足以下條件的一組流稱為滿足以下條件的一組流稱為可行流可行流。 容量限制條件。容量網(wǎng)絡上所有的弧滿足：容量限制條件。容量網(wǎng)絡

3、上所有的弧滿足：0fijcij 中間點平衡條件。中間點平衡條件。),(0),(),(tsivvfvvfijji 若以若以v(f)表示網(wǎng)絡中從表示網(wǎng)絡中從st的流量，則有：的流量，則有： 0),(),()(tjjsvvfvvffvPage 6結論：任何網(wǎng)絡上一定存在可行流。（零流即是結論：任何網(wǎng)絡上一定存在可行流。（零流即是可行流）可行流）網(wǎng)絡最大流問題：網(wǎng)絡最大流問題：指滿足容量限制條件和中間點平衡的條件下，使指滿足容量限制條件和中間點平衡的條件下，使v(f)值達到最大。值達到最大。Page 7 割與割集割與割集割是指容量網(wǎng)絡中的發(fā)點和收點分割開，并使割是指容量網(wǎng)絡中的發(fā)點和收點分割開，并使s

4、t的流中斷的流中斷的一組弧的集合。割容量是組成割集合中的各條弧的容量之的一組弧的集合。割容量是組成割集合中的各條弧的容量之和，用和，用 表示。表示。),(VVc ),(),(),(),(VVjijivvcVVc如下圖中，如下圖中，AA將網(wǎng)絡上的點分割成將網(wǎng)絡上的點分割成 兩個集合。并兩個集合。并有有 ，稱弧的集合，稱弧的集合(v1,v3),(v2,v4)是一個割，且是一個割，且 的流量為的流量為14。 VV ,VtVs ,VV Page 8v1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(3)7(6)AABBPage 9 設網(wǎng)絡設網(wǎng)絡N中一個從中一個從 s 到到 t

5、 的流的流 f 的流量為的流量為v(f )， (V, V )為任意一個割集，則為任意一個割集，則 v(f ) = f(V, V ) f(V , V) 對網(wǎng)絡對網(wǎng)絡 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)絡中在網(wǎng)絡中st的最大流量等于它的最小割集的容量，的最大流量等于它的最小割集的容量，即：即： v (f ) = c (V, V )

6、 Page 10在網(wǎng)絡的發(fā)點和收點之間能找到一條鏈，在該鏈上所有在網(wǎng)絡的發(fā)點和收點之間能找到一條鏈，在該鏈上所有指向為指向為st的弧，稱為前向弧，記作的弧，稱為前向弧，記作+,存在存在f0，則稱這樣的鏈為，則稱這樣的鏈為增廣鏈。例如下圖中，增廣鏈。例如下圖中，sv2v1v3v4t。 網(wǎng)絡網(wǎng)絡N中的流中的流 f 是最大流當且僅當是最大流當且僅當N中不包含任何增廣中不包含任何增廣鏈鏈Page 11v1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(4)7(5)Page 12求網(wǎng)絡最大流的標號算法：求網(wǎng)絡最大流的標號算法：由一個流開始，系統(tǒng)地搜尋增廣鏈，然后在此鏈上增流，由

7、一個流開始，系統(tǒng)地搜尋增廣鏈，然后在此鏈上增流，繼續(xù)這個增流過程，直至不存在增廣鏈。繼續(xù)這個增流過程，直至不存在增廣鏈。找出第一個可行流，（例如所有弧的流量找出第一個可行流，（例如所有弧的流量fij =0。）。）用標號的方法找一條增廣鏈用標號的方法找一條增廣鏈 首先給發(fā)點首先給發(fā)點s標號標號(),標號中的數(shù)字表示允許的最大調整量。標號中的數(shù)字表示允許的最大調整量。 選擇一個點選擇一個點 vi 已標號并且另一端未標號的弧沿著某條鏈向已標號并且另一端未標號的弧沿著某條鏈向收點檢查：收點檢查：Page 13 如果弧的起點為如果弧的起點為vi，并且有，并且有fij0，則，則vj標號標號(fji)(3)

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

9、上所有后向弧對增廣鏈上所有后向弧對增廣鏈上所有前向弧對增廣鏈上所有前向弧ftftff)()(4) 修改流量。設原圖可行流為修改流量。設原圖可行流為f，令，令得到網(wǎng)絡上一個新的可行流得到網(wǎng)絡上一個新的可行流f。(5) 擦除圖上所有標號，重復擦除圖上所有標號，重復(1)-(4)步，直到圖中找不到任何步，直到圖中找不到任何增廣鏈，計算結束。增廣鏈，計算結束。Page 15例例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 16stv1v2v3v4v5

10、4(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)解解: (1) 在已知可行流的基礎上，通過標號尋找增廣鏈。在已知可行流的基礎上，通過標號尋找增廣鏈。()(2)=min,6=6(6)(3)=min6,2=2(2)(t)=min2,5=2(2)Page 17(2) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流?？尚辛?。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 t

11、fPage 18(3) 擦除原標號，重新搜尋增廣鏈。擦除原標號，重新搜尋增廣鏈。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 19(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=1Page 20(5) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可修改

12、增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。行流。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 21(6) 擦除原標號擦除原標號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 22(8) 調整增廣鏈上的流量，非增廣鏈流量不變，得到新的可行流調整增廣鏈上的流量，非增廣鏈流量不變，得到新的可行流stv1v2v3v4v54(3)

13、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 23stv1v2v3v4v54(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(3)=min1,1=1(t)=min1,2=1(7) 重新搜尋增廣鏈。重新搜尋增廣鏈。Page 24stv1v2v3v4v54(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) 擦除原標號擦除原標號Pa

14、ge 25stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)(10) 重新標號，搜索增廣鏈重新標號，搜索增廣鏈()(1)=min,1=1(1)(5)=min1,1=1(1)(4)=min1,1=1(1)(t)=min1,1=1(1)Page 26stv1v2v3v4v54(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) 調整增廣鏈上的流量，非增廣鏈流量不變，得到新的可行流調整增廣鏈上的流量，非增廣鏈流量不變，得到新的可行流11 sf115 f154 f14 tfPage 27stv1v2v3v4v54(4)3(3)10(7)3(3)1(1)4(4)3(3)5(5)4(4)2(2)7(7)8(7)()(1)(1)(1)(1)(11) 擦除標號，在新的可行流上重新標號。擦除標號，在新的可行流上重新標號。Page 28stv1v2v3v4v54(4)3(3)10(