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

網(wǎng)絡(luò)的最大流如何制定一個運輸計劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。這就是一個網(wǎng)絡(luò)最大流問題。運籌學(xué)最大流網(wǎng)絡(luò)的最大流基本概念：1.容量網(wǎng)絡(luò)：隊網(wǎng)絡(luò)上的每條弧(vi,vj)都給出一個最大的通過能力，稱為該弧的容量，簡記為cij。容量網(wǎng)絡(luò)中通常規(guī)定一個發(fā)點(也稱源點，記為s)和一個收點(也稱匯點，記為t)，網(wǎng)絡(luò)中其他點稱為中間點。s①②③④t4844122679運籌學(xué)最大流網(wǎng)絡(luò)的最大流2.網(wǎng)絡(luò)的最大流

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

中間點平衡條件。若以v(f)表示網(wǎng)絡(luò)中從s→t的流量，則有：運籌學(xué)最大流網(wǎng)絡(luò)的最大流結(jié)論：任何網(wǎng)絡(luò)上一定存在可行流。（零流即是可行流）網(wǎng)絡(luò)最大流問題： 指滿足容量限制條件和中間點平衡的條件下，使v(f)值達(dá)到最大。運籌學(xué)最大流網(wǎng)絡(luò)的最大流割與割集割是指容量網(wǎng)絡(luò)中的發(fā)點和收點分割開，并使s→t的流中斷的一組弧的集合。割容量是組成割集合中的各條弧的容量之和，用表示。如下圖中，AA′將網(wǎng)絡(luò)上的點分割成兩個集合。并有，稱弧的集合{(v1,v3),(v2,v4)}是一個割，且的流量為18。運籌學(xué)最大流網(wǎng)絡(luò)的最大流●stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(3)7(6)AA’BB’運籌學(xué)最大流網(wǎng)絡(luò)的最大流定理1

設(shè)網(wǎng)絡(luò)N中一個從s到t

的流f的流量為v(f)，(V,V′)為任意一個割集，則v(f)=f(V,V′)

f(V′,V)推論1

對網(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′)推論2

最大流量v＊(f)不大于最小割集的容量，即：v＊(f)min{c(V,V′)}定理2在網(wǎng)絡(luò)中s→t的最大流量等于它的最小割集的容量，即：v＊(f)=c＊(V,V′)運籌學(xué)最大流網(wǎng)絡(luò)的最大流增廣鏈 在網(wǎng)絡(luò)的發(fā)點和收點之間能找到一條鏈，在該鏈上所有指向為s→t的弧，稱為前向弧，記作μ+,存在f<c；所有指向為t→s的弧，稱為后向弧，記做μ－，若f>0，則稱這樣的鏈為增廣鏈。例如下圖中，s→v2→v1→v3→v4→t。定理3網(wǎng)絡(luò)N中的流f是最大流當(dāng)且僅當(dāng)N中不包含任何增廣鏈運籌學(xué)最大流網(wǎng)絡(luò)的最大流●stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(4)7(5)運籌學(xué)最大流網(wǎng)絡(luò)的最大流求網(wǎng)絡(luò)最大流的標(biāo)號算法：[基本思想] 由一個流開始，系統(tǒng)地搜尋增廣鏈，然后在此鏈上增流，繼續(xù)這個增流過程，直至不存在增廣鏈。[基本方法]找出第一個可行流，（例如所有弧的流量fij=0。）用標(biāo)號的方法找一條增廣鏈?zhǔn)紫冉o發(fā)點s標(biāo)號(∞),標(biāo)號中的數(shù)字表示允許的最大調(diào)整量。選擇一個點vi

已標(biāo)號并且另一端未標(biāo)號的弧沿著某條鏈向收點檢查：運籌學(xué)最大流網(wǎng)絡(luò)的最大流如果弧的起點為vi，并且有fij<Cij，則給vj標(biāo)號為(Cij－fij)如果弧的方向指向vi，并且有fji>0，則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)步運籌學(xué)最大流網(wǎng)絡(luò)的最大流(4)修改流量。設(shè)原圖可行流為f，令得到網(wǎng)絡(luò)上一個新的可行流f’。(5)擦除圖上所有標(biāo)號，重復(fù)(1)-(4)步，直到圖中找不到任何增廣鏈，計算結(jié)束。運籌學(xué)最大流網(wǎng)絡(luò)的最大流例6.10用標(biāo)號算法求下圖中s→t的最大流量，并找出最小割?！駍tv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)運籌學(xué)最大流網(wǎng)絡(luò)的最大流解：(1)先給s標(biāo)號(∞)●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)(∞)運籌學(xué)最大流網(wǎng)絡(luò)的最大流●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)(∞)(2)檢查與s點相鄰的未標(biāo)號的點，因fs1<cs1，故對v1標(biāo)號=min{∞,cs1-fs1}=1,(1)運籌學(xué)最大流網(wǎng)絡(luò)的最大流●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(6)(∞)(1)(2)檢查與v1點相鄰的未標(biāo)號的點，因f13<c13，故對v3標(biāo)號=min{1,c13-f13}=min{1,6}=1(1)運籌學(xué)最大流網(wǎng)絡(luò)的最大流●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)(∞)(1)(1)(3)檢查與v3點相鄰的未標(biāo)號的點，因f3t<c3t，故對vt標(biāo)號=min{1,c3t-f3t}=min{1,1}=1(1)找到一條增廣鏈s→v1→v3→t運籌學(xué)最大流網(wǎng)絡(luò)的最大流(4)修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流?！駍tv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(3)7(5)(∞)(1)(1)(1)運籌學(xué)最大流網(wǎng)絡(luò)的最大流(5)擦除所有標(biāo)號，重復(fù)上述標(biāo)號過程，尋找另外的增廣鏈?！駍tv1v3v2v48(8)9(4)5(5)10(8)6(0)2(0)9(9)5(3)7(5)(∞)(1)(1)(1)運籌學(xué)最大流網(wǎng)絡(luò)的最大流(5)擦除所有標(biāo)號，重復(fù)上述標(biāo)號過程，尋找另外的增廣鏈?！駍tv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)(∞)(2)ε(2)=min{∞,2}=2(2)ε(1)=min{2,3}=2ε(3)=min{2,5}=2(2)(1)ε(4)=min{2,1}=1(1)ε(t)=min{1,2}=1運籌學(xué)最大流網(wǎng)絡(luò)的最大流(6)修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流?！駍tv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)(∞)(2)(2)(2)(1)(1)運籌學(xué)最大流網(wǎng)絡(luò)的最大流●stv1v3v2v48(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)號過程，尋找另外的增廣鏈。運籌學(xué)最大流網(wǎng)絡(luò)的最大流●stv1v3v2v48(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)=min{1,2}=1ε(3)=min{1,4}=1運籌學(xué)最大流網(wǎng)絡(luò)的最大流例6.9求下圖s→t的最大流，并找出最小割stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)●運籌學(xué)最大流網(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)=min{6,2}=2(2)ε(t)=min{2,5}=2(2)存在增廣鏈s→v2→v3→t運籌學(xué)最大流網(wǎng)絡(luò)的最大流(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)運籌學(xué)最大流網(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)運籌學(xué)最大流網(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)=min{4,1}=1ε(3)=min{1,2}=1(1)(1)ε(t)=min{1,3}=1存在增廣鏈：s→v2→v5→v3→t運籌學(xué)最大流網(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)運籌學(xué)最大流網(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)運籌學(xué)最大流網(wǎng)絡(luò)的最大流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)ε(5)=min{∞,1}=1ε(5)=min{1,1}=1ε(5)=min{1,2}=1(7)重新搜尋增廣鏈。存在增廣鏈：s→v5→v3→t運籌學(xué)最大流網(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)運籌學(xué)最大流網(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)號運籌學(xué)最大流網(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)號，搜索