運(yùn)籌學(xué)最大流問題PPT課件

1、列出圖示網(wǎng)絡(luò)全部割邊上數(shù)字為 c i j(f i j ) .9(4)sv3v4v1v27(5)2(0)9(9)10(8)8(8)5(5)tVVs,v1, v2,v3,v4ts,v1, v2,v4s,v1, v2,v3s,v2,v4s,v1,v3s,v1, v2s,v2s,v1sv1,v2, v3,v4,tv2, v3,v4,tv1,v3,v4,tv3,v4,tv2,v4,tv1,v3,tv4,tv3,t(s,1)(s,2)(s,2)(1,2)(s,1)(1,3)(s,1)(2,4)(s,2)(4,t)(1,3) (2,4)(4,3)(1,2) (3,2) (3,t)(2,4) (3,t)(4,

2、3) (4,t)(1,3)(3,t)15(4,t)2117181924142515割容量第1頁/共12頁4-3、最大流- -最小割定理定理定理2 (最大流- -最小割定理) ) 任一網(wǎng)絡(luò)G中, 從vs 到 vt 的定義設(shè) f 為網(wǎng)絡(luò)G=(V, E, C)的任一可行流, 流量為W , (S, S )是分離 vs , vt 的任一割集, 則有 WC (S, S ).容量網(wǎng)絡(luò)G, 若為網(wǎng)絡(luò)中從 vs 到 vt 的一條鏈, 給定向?yàn)閺?vs 到 vt , 上的邊凡與同向稱為前向邊, 凡與反向的稱為后向邊，其集合分別用+和-表示, f 是一個可行流, 如果滿足0 f i j 0 (vi , v j )

3、-則稱為從 v s 到 v t 的(關(guān)于 f )的可增廣鏈 .最大流的流量等于分離 vs , vt 的最小割的容量.推論 可行流f是最大流的充要條件是不存在從vs 到 vt 的(關(guān)于f 的)可增廣鏈.第2頁/共12頁4-4、求最大流的標(biāo)號算法若vt得到標(biāo)號, 說明存在一條可增廣鏈, 轉(zhuǎn)(第2步)調(diào)整過程. 給發(fā)點(diǎn)vs以標(biāo)號(0, +). 選擇一個已標(biāo)號的頂點(diǎn) vi , 對于vi ,的所有未給標(biāo)號的鄰(a)若邊(vj ,vi )E, 且 f j i 0 , 則令j =min ( f j i , j ) , 并給 v j 以標(biāo)號( - v i , j ).1. 標(biāo)號過程(b)若邊(vi ,vj )

4、E, 且 f i j c i j 時, 令j =min ( c i j - f i j , i ) , 并給 v j 以標(biāo)號( + v i , j ). 重復(fù)直到收點(diǎn) vt 被標(biāo)號或不再有頂點(diǎn)可標(biāo)號為止. 若vt未得到標(biāo)號, 標(biāo)號過程已無法繼續(xù), 說明 f 已是最大流. 接點(diǎn) vj, 按下列規(guī)則處理: 第3頁/共12頁2. 調(diào)整過程 令 fi j = 去掉所有標(biāo)號, 回到第1步, 對可行流 f 重新標(biāo)號. f i j + t 若(vi , v j )是可增廣鏈上的前向邊 f i j - t 若(vi , v j )是可增廣鏈上的后向邊 f i j 若(vi , v j )不在可增廣鏈上第4頁/

5、共12頁作 業(yè)閱讀 p258 - 265p43 15, 17第5頁/共12頁圖邊集 (vs , v1), (v1 , v3), (v2 , v3), (v3 , vt), (v4 , vt)都是割集.911割集容量2v23434143222v1v4v3vtvs邊集 (vs , v1), (vs , v3), (vs , v4) 第6頁/共12頁例14_A圖中一個網(wǎng)絡(luò)及初始可行流 , 邊上序數(shù)為(c i j , f i j )v2(5,2)v1v4v3vtvsv5v6(4,2)(5,5)(3,0)(3,3)(3,3)(5,4)(2,2)(4,2)(2,2)(3,2)先給 vs 標(biāo)號(, +).檢

6、查 vs 的鄰接點(diǎn)v1, v2, v3 ,邊(vs,v2)E, 且 f s 2 c s 2=4v2令 =min2,+=2, 同理 給 v3 以標(biāo)號+vs,1.檢查v2尚未標(biāo)號鄰接點(diǎn)v5,v6, 邊(v2,v6)E, 且 f25=00,v1令 =min3,2=2, 給 v2 以標(biāo)號+vs,2.v4尚未標(biāo)號與v1鄰接, v4令 =min3,2=2, 給 v4 以標(biāo)號+v1,2.類似給 vt 以標(biāo)號+v4,2.因 vt 得以標(biāo)號， (v1,v4)E且 f14=2|M|, 則稱M為最大匹配. 二部圖中最大匹配問題可以化為最大流問題。 在二部圖中增加發(fā)點(diǎn)和收點(diǎn), 用有向邊與原二部圖中頂點(diǎn)兩條邊都沒有公共端點(diǎn), 則稱M為圖G的一個匹配(對集)相連, 令全部邊上的容量均為1. 當(dāng)此網(wǎng)絡(luò)的流達(dá)到最大時, 即獲最大匹配方案.第10頁/共12頁例15 有5位待業(yè)者，5項工作，他們各自勝任工作情況x5y