北郵運(yùn)籌學(xué)ch74 最大流問題

1、基本概念4844122679：在某時(shí)期內(nèi)弧(i，j)上的最大通過能力。記為C (i，j)或Cij 在上圖中，C12=4，C138，C234等，怎樣安排運(yùn)輸方案，才能使在某一時(shí)期內(nèi)從v1運(yùn)到v6的物資最多，這樣的問題就是最大流問題，網(wǎng)絡(luò)中所有流起源于一個(gè)叫做發(fā)點(diǎn)的節(jié)點(diǎn)（源） 所有的流終止于一個(gè)叫做收點(diǎn)的節(jié)點(diǎn)其余所有的節(jié)點(diǎn)叫做中間點(diǎn)（轉(zhuǎn)運(yùn)點(diǎn)） 通過每一條弧的流只允許沿著弧的箭頭方向流動(dòng)目標(biāo)是使得從發(fā)點(diǎn)到收點(diǎn)的總流量最大7/20/2022流量：弧(i，j)的實(shí)際通過量，記為f (i，j)或f ij可行流：如果f ij滿足： 1.對于所有弧(i，j)有0f ijCij 2.對于發(fā)點(diǎn)vs有：3.對于收點(diǎn)

2、vt有：則稱流量集合f ij為網(wǎng)絡(luò)的一個(gè)可行流，簡記為 f , v稱為可行流的流量或值，記為v(f).以下假設(shè)網(wǎng)絡(luò)是一個(gè)簡單連通圖。4.對于中間點(diǎn)點(diǎn)vm有：7/20/2022截集 將圖G（V，E）的點(diǎn)集分割成兩部分稱為一個(gè)截集，截集中所有弧的容量之和稱為截集的截量。68441226796411322306下圖所示的截集為請看演示7/20/202268441226796401322106又如下圖所示的截集為上圖所示的截集為所有截量中此截量最小且等于最大流量，此截集稱為最小截集?！径ɡ怼孔畲罅髁康扔谧钚〗丶慕亓?。7/20/2022鏈：從發(fā)點(diǎn)到收點(diǎn)的一條路線（弧的方向不一定都同向）稱為鏈。從發(fā)點(diǎn)到

3、收點(diǎn)的方向規(guī)定為鏈的方向。前向弧：與鏈的方向相同的弧稱為前向弧。后向弧：與鏈的方向相反的弧稱為后向弧。增廣鏈 設(shè) f 是一個(gè)可行流，如果存在一條從vs到vt的鏈，滿足：1.所有前向弧上fij0則該鏈稱為增廣鏈前向弧后向弧8446952346容量流量想一想，這是一條增廣鏈嗎？7/20/2022【定理】設(shè)網(wǎng)絡(luò)G的一個(gè)可行流f，如果存在一條從vs到vt的增廣鏈，那么就可改進(jìn)一個(gè)值更大的可行流f1，并且val f1val f【證】設(shè)val fv對改進(jìn)的可行流f1 ：7/20/2022最大流的標(biāo)號算法步驟 1. 找出第一個(gè)可行流，例如所有弧的流量fij =0 2. 用標(biāo)號的方法找一條增廣鏈 A1：發(fā)點(diǎn)標(biāo)

4、號（）， A2：選一個(gè)點(diǎn) vi 已標(biāo)號并且另一端未標(biāo)號的弧沿著某條鏈向收點(diǎn)檢查： 如果弧的方向向前并且有fij0，則vj標(biāo)號（fji)當(dāng)收點(diǎn)不能得到標(biāo)號時(shí)，說明不存在增廣鏈，計(jì)算結(jié)束。當(dāng)收點(diǎn)已得到標(biāo)號時(shí)，說明已找到增廣鏈?！径ɡ怼靠尚辛魇亲畲罅鳟?dāng)且僅當(dāng)不存在發(fā)點(diǎn)到收點(diǎn)的增廣鏈7/20/20224. 調(diào)整流量 得到新的可行流，去掉所有標(biāo)號，從發(fā)點(diǎn)重新標(biāo)號尋找增廣鏈，直到收點(diǎn)不能標(biāo)號為止。3. 依據(jù)vi 的第一個(gè)標(biāo)號反向跟蹤得到一條增廣鏈； 依據(jù)vi 的第二個(gè)標(biāo)號求最小值得到調(diào)整量進(jìn)入演示和練習(xí)7/20/2022 684412267942202222046217【例】求下圖v1 到v6 的最大流及

5、最大流量【解】1. 通過觀察得到初始可行流2.標(biāo)號3. 得到增廣鏈7/20/2022 68441226794211322304223 得到增廣鏈 4.求調(diào)整量 5.調(diào)整可行流 去掉所有標(biāo)號，重新標(biāo)號 6844122679422022220462177/20/202268441226796411322306 求調(diào)整量 調(diào)整可行流 去掉所有標(biāo)號，重新標(biāo)號5標(biāo)號不能繼續(xù)進(jìn)行，說明不存在從發(fā)點(diǎn)到收點(diǎn)的增廣鏈，得到最大流.最大流量 v=6+3=917/20/2022The End of Chapter 6 作業(yè): 教材P285 T10.11 10.12 10.14下一章：網(wǎng)絡(luò)計(jì)劃Exit1.基本概念 容量、流量、可