版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、公路系統(tǒng)中的車輛流公路系統(tǒng)中的車輛流 控制系統(tǒng)中的信息流控制系統(tǒng)中的信息流 供水系統(tǒng)中的水流供水系統(tǒng)中的水流 金融系統(tǒng)中的現(xiàn)金流金融系統(tǒng)中的現(xiàn)金流 問題背景問題背景 網(wǎng)絡(luò)最大流問題問題的提出 n網(wǎng)絡(luò)中存在流量限制時,求解一條線路使網(wǎng)絡(luò)中存在流量限制時,求解一條線路使 得從得從起點(diǎn)起點(diǎn)與與終點(diǎn)終點(diǎn)之間可通過的之間可通過的流量最大流量最大。 v1 v2 v3 v4 v5 v6 10 8 4 6 5 3 5 3 11 17 例:上圖為例:上圖為v1到到v6的一交通網(wǎng),權(quán)表示相應(yīng)運(yùn)輸線的最大的一交通網(wǎng),權(quán)表示相應(yīng)運(yùn)輸線的最大 通過能力,制定一方案,使從通過能力,制定一方案,使從v1運(yùn)到運(yùn)到v6的運(yùn)輸產(chǎn)
2、品數(shù)量最的運(yùn)輸產(chǎn)品數(shù)量最 多。多。 設(shè)有網(wǎng)絡(luò)設(shè)有網(wǎng)絡(luò)d=(v, a, c),其中,其中c=cij, cij為弧為弧(vi,vj) 上的上的容量容量,現(xiàn)在,現(xiàn)在d上要通過一個流上要通過一個流f=fij, fij為弧為弧 (vi,vj)上的上的流量流量。 問題:問題:如何安排如何安排fij,可使網(wǎng)絡(luò),可使網(wǎng)絡(luò)d上的總流量最大?上的總流量最大? v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11 6 3 5 3 1 2 2 1 3 3 6 2 一、一般提法:一、一般提法: max v=v(f) ijij cf 0 tsi tifv sifv ff jj jiij ,0 )( )
3、( 容量約束容量約束 平衡約束平衡約束 s.t. v2 vs v3 v4 v5 vt 8 10 4 17 5 5 3 11 6 3 5 3 1 2 2 1 3 3 6 2 注:滿足兩約束條件的流注:滿足兩約束條件的流f稱為可行流,稱為可行流,v(f)稱為該可行流的流量稱為該可行流的流量 v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11 6 3 5 3 1 2 1 1 3 3 6 2 飽和弧飽和弧 fij=cij 非飽和弧非飽和弧 fijcij 零流弧零流弧 fij=0 非零流弧非零流弧 fij0 v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11
4、6 3 5 3 1 2 2 1 3 3 6 2 f為一可行流,為一可行流,u為為vs至至vt的鏈,令的鏈,令 u+=正向弧正向弧, u-=反向弧反向弧。若。若u+中弧中弧 皆非飽和皆非飽和,且,且u-中弧皆非零,則稱中弧皆非零,則稱u為關(guān)于為關(guān)于f 的一條的一條增廣鏈增廣鏈。 v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11 6 3 5 3 1 2 2 1 3 3 6 2 f為一可行流,為一可行流,u為為vs至至vt的鏈,令的鏈,令 u+=正向弧正向弧, u-=反向弧反向弧。若。若u+中弧中弧 皆非飽,且皆非飽,且u-中弧皆非零,則稱中弧皆非零,則稱u為關(guān)于為關(guān)于f的的
5、 一條一條增廣鏈增廣鏈。 v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11 6 3 5 3 1 2 2 1 3 3 6 2 f為一可行流,為一可行流,u為為vs至至vt的鏈,令的鏈,令 u+=正向弧正向弧, u-=反向弧反向弧。若。若u+中弧中弧 皆非飽,且皆非飽,且u-中弧皆非零,則稱中弧皆非零,則稱u為關(guān)于為關(guān)于f的的 一條一條增廣鏈增廣鏈。 v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11 6 3 5 3 1 2 2 1 3 3 6 1 f為一可行流,為一可行流,u為為vs至至vt的鏈,令的鏈,令 u+=正向弧正向弧, u-=反向弧反向弧。
6、若。若u+中弧中弧 皆非飽,且皆非飽,且u-中弧皆非零,則稱中弧皆非零,則稱u為關(guān)于為關(guān)于f的的 一條一條增廣鏈增廣鏈。 v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11 6 3 5 3 3 2 0 1 5 3 6 2 把把v分成兩部分:分成兩部分:va和和vb(va vb= , va vb= v) 且且vs va、 vt vb,則弧集,則弧集(va,vb)稱為稱為d的的截集(割集)截集(割集)。 截集上的容量截集上的容量和稱為和稱為截量(割集容量),記為截量(割集容量),記為c(va,vb) 。 v1 vs v2 v3 v4 vt 8 10 4 17 5 5 3 11
7、 6 3 5 3 1 2 2 1 3 3 6 2 (vs,v2), (v1,v2), (v1,v3), (v1,v4); 截量為:截量為: c(va,vb) =8+4+5+3=20 例例 若若va=vs,v1,則,則 截集為:截集為: 任一可行流的流量都不會超過任一截集的截量任一可行流的流量都不會超過任一截集的截量 即:即:v(f) c (va,vb) 。 v1 vs v2v3 vt (2,2) (4,3) (3,1) (1,0) (3,3) (5,2) (2,2) 最大流最小截定理:最大流最小截定理:網(wǎng)絡(luò)的最大流量等于最小截量。網(wǎng)絡(luò)的最大流量等于最小截量。 (cijfij) v1 vs v2
8、v3 vt (2,2) (4,3) (3,1) (1,0) (3,3) (5,2) (2,2) v1 vs v2v3 vt (2,2) (4,3) (3,1) (1,0) (3,3) (5,2) (2,2) va=vs, (vs,v1), (vs,v2),截量為:,截量為:6 v1 vs v2v3 vt (2,2) (4,3) (3,1) (1,0) (3,3) (5,2) (2,2) va=vs,(vs,v1), (vs,v2),截量為:,截量為:6 va=vs ,v1,(vs,v2), (v1,vt),截量為:,截量為:7 v1 vs v2v3 vt (2,2) (4,3) (3,1) (
9、1,0) (3,3) (5,2) (2,2) va=vs,(vs,v1), (vs,v2),截量為:,截量為:6 va=vs ,v1,(vs,v2), (v1,vt),截量為:,截量為:7 va=vs ,v2,截量為:,截量為:7 v1 vs v2v3 vt (2,2) (4,3) (3,1) (1,0) (3,3) (5,2) (2,2) va=vs,(vs,v1), (vs,v2),截量為:,截量為:6 va=vs ,v1,(vs,v2), (v1,vt),截量為:,截量為:7 va=vs ,v2,截量為:,截量為:7 va=vs ,v3,截量為:,截量為:12 v1 vs v2v3 vt
10、 (2,2) (4,3) (3,1) (1,0) (3,3) (5,2) (2,2) va=vs,(vs,v1), (vs,v2),截量為:,截量為:6 va=vs ,v1,(vs,v2), (v1,vt),截量為:,截量為:7 va=vs ,v2,截量為:,截量為:7 va=vs ,v3,截量為:,截量為:12 va=vs ,v1,v2,截量為:,截量為:5 v1 vs v2v3 vt (2,2) (4,3) (3,1) (1,0) (3,3) (5,2) (2,2) (1)所有的截集:)所有的截集: va=vs,(vs,v1), (vs,v2),截量為:,截量為:6 va=vs ,v1,(
11、vs,v2), (v1,vt),截量為:,截量為:7 va=vs ,v2,截量為:,截量為:7 va=vs ,v3,截量為:,截量為:12 va=vs ,v1,v2,截量為:,截量為:5 v1 vs v2v3 vt (2,2) (4,3) (3,1) (1,0) (3,3) (5,2) (2,2) (2)最小截量最小截量min c (va,vb)= 5; (3)v(f*)=5= min c (va,vb) f*是最大流。是最大流。 理論依據(jù):理論依據(jù):p261,p261,推論推論 不存在關(guān)于不存在關(guān)于f的增廣鏈的增廣鏈可行流可行流f是最大流是最大流 網(wǎng)絡(luò)中的所有點(diǎn):網(wǎng)絡(luò)中的所有點(diǎn):標(biāo)號點(diǎn)和未標(biāo)
12、號點(diǎn)。標(biāo)號點(diǎn)和未標(biāo)號點(diǎn)。 標(biāo)號點(diǎn):標(biāo)號點(diǎn):已檢查和未檢查點(diǎn)。已檢查和未檢查點(diǎn)。 標(biāo)號點(diǎn)包括兩部分標(biāo)號點(diǎn)包括兩部分:第一個標(biāo)號表明它的標(biāo)第一個標(biāo)號表明它的標(biāo) 號的來源,以便找出增廣鏈;第二個標(biāo)號是號的來源,以便找出增廣鏈;第二個標(biāo)號是 為確定增廣鏈的調(diào)整量。為確定增廣鏈的調(diào)整量。 標(biāo)號法的思路 所有點(diǎn)所有點(diǎn) 未標(biāo)號未標(biāo)號 未檢查未檢查 所有所有 標(biāo)號點(diǎn)標(biāo)號點(diǎn) 檢查檢查 注注: 給發(fā)點(diǎn)給發(fā)點(diǎn)vs標(biāo)上(標(biāo)上(0,),則),則vs成為標(biāo)號未檢查成為標(biāo)號未檢查 vi 標(biāo)號標(biāo)號 未檢查未檢查 vi 標(biāo)號標(biāo)號 檢查檢查 vj 標(biāo)號標(biāo)號 未檢查未檢查 考查考查 (vi, vj) 網(wǎng)絡(luò)最大流問題網(wǎng)絡(luò)最大流問題標(biāo)
13、號法標(biāo)號法 1.標(biāo)號過程標(biāo)號過程 n給vs標(biāo)上(0,+),這時vs是標(biāo)號而未檢查點(diǎn),其余為 未標(biāo)號點(diǎn)。 n若在弧(vi,vj)上,fij0,則給vj標(biāo)(-vi,l(vj), 其中 n于是于是vi成為標(biāo)號而已檢查過的點(diǎn),重復(fù)上述步驟,成為標(biāo)號而已檢查過的點(diǎn),重復(fù)上述步驟, 一旦一旦vt被標(biāo)號,表明得到一條從被標(biāo)號,表明得到一條從vs到到vt的增廣鏈,轉(zhuǎn)入的增廣鏈,轉(zhuǎn)入 2.調(diào)整過程調(diào)整過程 n如果所有標(biāo)號已檢查過,而標(biāo)號不能進(jìn)行下去,則算法如果所有標(biāo)號已檢查過,而標(biāo)號不能進(jìn)行下去,則算法 結(jié)束,這時可行流為最大流。結(jié)束,這時可行流為最大流。 min, jiijij l vl vcf min, j
14、iji l vl vf 網(wǎng)絡(luò)最大流問題標(biāo)號法 n1.標(biāo)號過程標(biāo)號過程 n2.調(diào)整過程調(diào)整過程 * * * , , , ij ij ijijijt ij ij v v f ffv vl v f v v 利用反向追蹤法找出增廣鏈。調(diào)整量為利用反向追蹤法找出增廣鏈。調(diào)整量為 = l(vt) 去掉所有的標(biāo)號,對新的可行流去掉所有的標(biāo)號,對新的可行流f*重新進(jìn)行標(biāo)號過程。重新進(jìn)行標(biāo)號過程。 步驟:步驟: (1)給給vs標(biāo)號為標(biāo)號為0,+, 流出未飽和弧流出未飽和弧(vs , vj) ,給給vj標(biāo)號標(biāo)號vs ,j,其中其中j=csj- fsj 或或流入非零弧流入非零弧 (vj , vs) ,給給vj標(biāo)號標(biāo)
15、號-vs, j ,其中其中j=fsj (cijfij),用標(biāo)號法求最大流。,用標(biāo)號法求最大流。 0,+ vs, 4 選與選與vs關(guān)聯(lián)的關(guān)聯(lián)的 v2 vs v1 v4 v3 vt (3,3) (5,1) (1,1) (2,2) (1,1) (5,3) (2,1) (4,3) (3,0) (2)把節(jié)點(diǎn)集把節(jié)點(diǎn)集v分為分為 va:已標(biāo)號點(diǎn)集:已標(biāo)號點(diǎn)集 vb:未標(biāo)號點(diǎn)集:未標(biāo)號點(diǎn)集 v2 vs v1 v4 v3 vt (3,3) (5,1) (1,1) (2,2) (1,1) (5,3) (2,1) (4,3) 0 , + vs, 4 (3,0) 考慮所有弧考慮所有弧(vi , vj)或或(vj ,
16、 vi) ,其中其中vi va, vj vb,若該弧為,若該弧為 流出未飽弧流出未飽弧,則給則給vj標(biāo)號標(biāo)號vi , j,其中其中j=mini, cij- fij 流入非零弧流入非零弧,則給則給vj標(biāo)號標(biāo)號-vi , j ,其中其中j= mini, fij (3) -v1 , 1 v2 vs v1 v4 v3 vt (3,3) (5,1) (1,1) (2,2) (1,1) (5,3) (2,1) (4,3) 0 , + vs , 4 (3,0) (4) v2 vs v1 v4 v3 vt (3,3) (5,1) (1,1) (2,2) (1,1) (5,3) (2,1) (4,3) 0 ,
17、+ vs , 4 -v1 , 1 重復(fù)(重復(fù)(2),(3),依次進(jìn)行的結(jié)局可能為),依次進(jìn)行的結(jié)局可能為 vt已標(biāo)號,得到一條增廣鏈已標(biāo)號,得到一條增廣鏈u(反向追蹤反向追蹤),轉(zhuǎn)(,轉(zhuǎn)(5);); vt未標(biāo)號未標(biāo)號,且無法再標(biāo)號且無法再標(biāo)號,此時的流為此時的流為最大流最大流,此時的截集此時的截集為為最小截最小截。 (3,0) v2 vs v1 v4 v3 vt (3,3) (5,1) (1,1) (2,2) (1,1) (5,3) (2,1) (4,3) 0 , + vs, 4 -v1, 1 (4) 重復(fù)(重復(fù)(2),(3),依次進(jìn)行的結(jié)局可能為),依次進(jìn)行的結(jié)局可能為 vt已標(biāo)號,得到一條
18、增廣鏈已標(biāo)號,得到一條增廣鏈u(反向追蹤反向追蹤),轉(zhuǎn)(,轉(zhuǎn)(5);); vt未標(biāo)號未標(biāo)號,且無法再標(biāo)號且無法再標(biāo)號,此時的流為此時的流為最大流最大流,此時的截集此時的截集為為最小截最小截。 v2 , 1 (3,0) v3 (4) 重復(fù)(重復(fù)(2),(3),依次進(jìn)行的結(jié)局可能為),依次進(jìn)行的結(jié)局可能為 vt已標(biāo)號,得到一條增廣鏈已標(biāo)號,得到一條增廣鏈u(反向追蹤反向追蹤),轉(zhuǎn)(,轉(zhuǎn)(5);); vt未標(biāo)號未標(biāo)號,且無法再標(biāo)號且無法再標(biāo)號,此時的流為此時的流為最大流最大流,此時的截集此時的截集為為最小截最小截。 v2 vs v1 v4 v3 vt (3,3) (5,1) (1,1) (2,2)
19、(1,1) (5,3) (2,1) (4,3) 0, + vs, 4 -v1, 1v2, 1 (3,0) v4, 1 (4) 重復(fù)(重復(fù)(2),(3),依次進(jìn)行的結(jié)局可能為),依次進(jìn)行的結(jié)局可能為 vt已標(biāo)號,得到一條增廣鏈已標(biāo)號,得到一條增廣鏈u(反向追蹤反向追蹤),轉(zhuǎn)(,轉(zhuǎn)(5);); vt未標(biāo)號未標(biāo)號,且無法再標(biāo)號且無法再標(biāo)號,此時的流為此時的流為最大流最大流,此時的截集此時的截集為為最小截最小截。 v2 vs v1 v4 v3 vt (3,3) (5,1) (1,1) (2,2) (1,1) (5,3) (2,1) (4,3) 0, + vs, 4 -v1, 1v2 , 1 (3,0)
20、 v4 , 1 v2 vs v1 v4 v3 vt (3,3) (5,1) (1,1) (2,2) (1,1) (5,3) (2,1) (4,3) 0, + vs, 4 -v1, 1v2, 1 (3,0) -v2, 1 v4 , 1 (5) 調(diào)整。取調(diào)整。取( ) min j tj vu l v ,令,令 uvvf uvvf uvvf f jiij jiij jiij ij ),( ),( ),( ,得新流,得新流 ij f,轉(zhuǎn)轉(zhuǎn)(1)。 v2 vs v1 v4 v3 vt (3,3) (5,1) (1,1) (2,2) (1,1) (5,3) (2,1) (4,3) 0, + vs, 4 -
21、v1, 1-v2, 1 (3,0) -v2, 1 v4, 1 v2 vs v1 v4 v3 vt (3,3) (5,2) (1,0) (2,2) (1,1) (5,4) (2,1) (4,4) (3,0) 調(diào)整調(diào)整 v2 vs v1 v4 v3 vt (3,3) (5,2) (1,0) (2,2) (1,1) (5,4) (2,1) (4,4) (3,0) 0 ,+ vs, 3 v2 vs v1 v4 v3 vt (3,3) (5,2) (1,0) (2,2) (1,1) (5,4) (2,1) (4,4) (3,0) 0, + vs , 3 此時標(biāo)號無法進(jìn)行,當(dāng)前流為最大流,最大流量為此時標(biāo)
22、號無法進(jìn)行,當(dāng)前流為最大流,最大流量為5; 最小截為最小截為(vs,v2), (v1,v3),截量為:,截量為:5 有三個發(fā)電站有三個發(fā)電站v1,v2,v3,發(fā)電能力分別為,發(fā)電能力分別為15、10和和 40兆瓦,經(jīng)輸電網(wǎng)可把電力送到兆瓦,經(jīng)輸電網(wǎng)可把電力送到8號地區(qū),電網(wǎng)能力如號地區(qū),電網(wǎng)能力如 圖所示。求三個發(fā)電站輸?shù)皆摰貐^(qū)的最大電力。圖所示。求三個發(fā)電站輸?shù)皆摰貐^(qū)的最大電力。 v2 v1 v3 v4 v5 v6 v7 v8 40 15 30 15 45 10 15 10 20 v0 10 15 40 10 10 15 15 15 0 10 10 10 10 15 25 課堂練習(xí)課堂練習(xí)
23、例例1、圖中圖中a、b、c、d、e、f分別表示陸地和島嶼,分別表示陸地和島嶼, 表示橋梁及其編號。河兩岸分別互為敵對的雙表示橋梁及其編號。河兩岸分別互為敵對的雙 方部隊(duì)占領(lǐng),問至少應(yīng)切斷幾座橋梁(具體指出編號)才方部隊(duì)占領(lǐng),問至少應(yīng)切斷幾座橋梁(具體指出編號)才 能達(dá)到阻止對方部隊(duì)過河的目的。試用圖論方法進(jìn)行分析。能達(dá)到阻止對方部隊(duì)過河的目的。試用圖論方法進(jìn)行分析。 a b d e f c 實(shí)際應(yīng)用實(shí)際應(yīng)用 分析:轉(zhuǎn)化為一分析:轉(zhuǎn)化為一 個網(wǎng)絡(luò)圖,弧的個網(wǎng)絡(luò)圖,弧的 容量為兩點(diǎn)間的容量為兩點(diǎn)間的 橋梁數(shù)。橋梁數(shù)。 則問題為求最則問題為求最 小截。小截。 a b d e f c a b c d
24、e f 2 1 1 1 1 1 2 2 2 2 2 2 分析:轉(zhuǎn)化為一分析:轉(zhuǎn)化為一 個網(wǎng)絡(luò)圖,弧的個網(wǎng)絡(luò)圖,弧的 容量為兩點(diǎn)間的容量為兩點(diǎn)間的 橋梁數(shù)。橋梁數(shù)。 則問題為求最則問題為求最 小截。小截。 答案:答案:最小截為最小截為ae、 cd、cf a b d e f c a b c d e f 2 1 1 1 1 1 2 2 2 2 2 2 例例2、有一批人從我國有一批人從我國a城赴俄羅斯城赴俄羅斯b城,可能的旅城,可能的旅 行路線如圖:行路線如圖: 邊防隊(duì)擬建立足夠數(shù)量檢查站以便使每輛汽車至少邊防隊(duì)擬建立足夠數(shù)量檢查站以便使每輛汽車至少 必經(jīng)過一個檢查站,建立檢查站的費(fèi)用根據(jù)各路段條必經(jīng)過一個檢查站,建立檢查站的費(fèi)用根據(jù)各路段條 件有所不同(如圖數(shù)字所示),
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 二零二五年度工廠生產(chǎn)安全保衛(wèi)承包合同模板3篇
- 2024版地球衛(wèi)星觀測數(shù)據(jù)共享合同
- 如何將孩子的失敗轉(zhuǎn)化為學(xué)習(xí)的機(jī)會
- 小學(xué)科學(xué)課堂中的情感教育對學(xué)習(xí)興趣的影響
- 2024年美容美發(fā)員工雇傭合同
- 家長如何引導(dǎo)孩子建立學(xué)習(xí)興趣與動力
- 2024綠城物業(yè)服務(wù)公司提供的物業(yè)咨詢服務(wù)合同
- 2024版工廠車間門窗安裝工程專業(yè)分包合同
- 2024版樁基項(xiàng)目資料承攬協(xié)議模板版B版
- 2024房屋抵押協(xié)議書
- 應(yīng)收帳款管理辦法
- 食品安全分享
- 跨境代運(yùn)營合同范例
- 水利水電工程驗(yàn)收實(shí)施細(xì)則模版(3篇)
- 四川雅安文化旅游集團(tuán)有限責(zé)任公司招聘筆試沖刺題2024
- 造價框架協(xié)議合同范例
- 2024-2025學(xué)年 語文二年級上冊 部編版期末測試卷 (含答案)
- 無人機(jī)飛行安全協(xié)議書
- 山西省晉中市2023-2024學(xué)年高一上學(xué)期期末考試 生物 含解析
- DB34T4912-2024二手新能源汽車鑒定評估規(guī)范
- 《商務(wù)溝通(第二版)》 課件全套 第1-4章 商務(wù)溝通概論 -商務(wù)溝通實(shí)務(wù)
評論
0/150
提交評論