運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型-資料下載頁(yè)
2025-05-12 15:06本頁(yè)面
【正文】 ????????CvvfCvvffjiijjiijij ),( ),( ??增廣鏈以外各弧流量不變 標(biāo)號(hào)算法 vs v2 v1 v3 vt 3 2 2 2 3 (0,+∞) ?重復(fù)標(biāo)號(hào)過(guò)程 。 ? 給網(wǎng)絡(luò)中的各個(gè)點(diǎn)標(biāo)號(hào)： ● 先給發(fā)點(diǎn) vs標(biāo)上 (0,+∞) 。 ● 檢查 vs給 v2標(biāo)上 (vs,1)，檢查 v2,在弧 (v2,vt)上 ,f2t=C2t=2,不滿足標(biāo)號(hào)條件，在弧 (v1,v2)上， f12=0,也不滿足標(biāo)號(hào)條件，標(biāo)號(hào)無(wú)法繼續(xù)。算法結(jié)束。 4 (vs,1) 2 2 2 0 2 2 如下圖所示，弧上數(shù)字表示該弧的容量，求該網(wǎng)絡(luò)的最大流。 最大流量為從發(fā)點(diǎn)流出的量 422)(21 ????? ss fffv這時(shí)的可行流就是所求的最大流 練習(xí)： 用標(biāo)號(hào)法求圖 87所示網(wǎng)絡(luò)的最大流。 弧旁的數(shù)是 (cij， fij)。 圖 87 解： (1) 標(biāo)號(hào)過(guò)程 ① 首先給 vs標(biāo)上 (0， +∞) ② 檢查 vs，在弧 (vs， v2)上， fs2=cs2=3，不滿足標(biāo)號(hào)條件?；?(vs， v1)上， fs1=1， cs1=5， fs1＜ cs1，則 v1的標(biāo)號(hào)為 (vs， l (v1))，其中 l (v1)=min［ l (vs)， (cs1fs1)］ =min［ +∞， 51］ =4 ③ 檢查 v1，在弧 (v1， v3)上， f13=2， c13=2，不滿足標(biāo)號(hào)條件。 在弧 (v2， v1)上， f21=1＞ 0，則給 v2記下標(biāo)號(hào)為 (v1， l (v2))，這里 l (v2)=min［ l (v1)， f21］ =min［ 4， 1］ =1 ④ 檢查 v2，在弧 (v2， v4)上， f21=3， c24=4， f24＜ c24，則給 v4標(biāo)號(hào) (v2， l (v4))，這里 l (v4)=min［ l (v2)， (c24f24)］ =min［ 1， 1］=1 在弧 (v3， v2)上， f32=1＞ 0，給 v3標(biāo)號(hào)： (v2， l (v3))，這里 l (v3） =min［ l (v2)， f32］ =min［ 1， 1］ =1 ⑤ 在 v3， v4中任選一個(gè)進(jìn)行檢查。例如 在弧 (v3， vt)上， f3t=1， c3t=2， f3t＜ c3t，給 vt標(biāo)號(hào)為 (v3， l (vt))，這里 l (vt)=min［ l (v3)， (c3tf3t)］ =min［ 1， 1］ =1 因 vt有了標(biāo)號(hào)，故轉(zhuǎn)入調(diào)整過(guò)程。 圖 88 (2) 調(diào)整過(guò)程按點(diǎn)的第一個(gè)標(biāo)號(hào)找到一條增廣鏈，如圖 88中雙箭頭線表示。 易見(jiàn) μ+=｛ (vs， v1)， (v3， vt)｝ μ=｛ (v2， v1)， (v3， v2)｝ 按 θ=1在 μ上調(diào)整 f。 μ+上： fs1+θ=1+1=2 f3t+θ=1+1=2 μ上： f21?θ=1?1=0 f32?θ=1?1=0 其余的 fij不變。 1V 11(V ,V ) 調(diào)整后得如下圖所示的可行流，對(duì)這個(gè)可行流進(jìn)入標(biāo)號(hào)過(guò)程，尋找增廣鏈。 開(kāi)始給 vs標(biāo)以 (0， +∞)，于是檢查 vs，給 v1標(biāo)以 (vs,3)，檢查 v1，弧 (v1,v3)上， f13＝ c13，弧 (v2,v1)上， f21=0，均不符號(hào)條件，標(biāo)號(hào)過(guò)程無(wú)法繼續(xù)下去，算法結(jié)束。 這時(shí)的可行流即為所求最大流。最大流量為 v(f)=fs1+fs2=f4t+f3t=5 與此同時(shí)可找到最小截集 ， 其中 V1為標(biāo)號(hào)點(diǎn)集合， 為未標(biāo)號(hào)點(diǎn)集合。弧集合 即為最小截集。 11(V , V ) 從一個(gè)費(fèi)用最小的可行流 出發(fā)（這樣的可行流一定存在，因?yàn)橘M(fèi)用 ，所以 就是一個(gè)流量為 0的最小費(fèi)用流），找出這個(gè)可行流 的費(fèi)用最小的一條增廣鏈 L，沿 L調(diào)整 ，直到找不到費(fèi)用最小的增廣鏈，就得到了最小費(fèi)用最大流。 第五節(jié) 最小費(fèi)用流問(wèn)題 對(duì)于網(wǎng)絡(luò)圖 G中的弧，除標(biāo)明弧的容量 外，還要標(biāo)明流過(guò)該弧單位流量的費(fèi)用 ， G的一個(gè)可行流 ，使得流的總運(yùn)輸費(fèi)用： 達(dá)到最小。 特別，如果可行流是最大流時(shí)，此問(wèn)題就是最小費(fèi)用最大流問(wèn)題。 ijcijb}{ ijff ???? Lji ijij fbfb ),()(}{ ijff ?0?ijb 0?fff最小費(fèi)用流問(wèn)題 最小費(fèi)用最大流的基本思路 ? 例：以圖 86為例，求最小費(fèi)用最大流?；∨詳?shù)字為(bij,cij)。 圖 86 (1) 取 f(0)=0 為初始可行流。 (2) 構(gòu)造賦權(quán)有向圖 W(f(0)) ，并求出從 v s 到 v t 的 最短路 (v s ,v 2 ,v 1 ,v t ) ，如圖 5 3 ( b )( 雙箭頭即為最短路 ) 。 (3) 在原網(wǎng)絡(luò) D 中，與這條最短路相應(yīng)的增廣鏈為 μ ＝ (v s ,v 2 ,v 1 ,v t ) 。 (4) 在 μ 上進(jìn)行調(diào)整， θ ＝ 5 ，得 f(1)( 圖 5 3 ( c )) 。按照上述 算法依次得 f(1),f(2),f(3),f(4)，流量依次為 5 ， 7 ， 10 ， 11 ； 構(gòu)造相應(yīng)的賦權(quán)有向圖為 W(f(1)),W(f(2)),W(f(3)),W(f(4)) ， 注意到 W(f(4)) 中已不存在從 v s 到 v t 的最短路， 所以 f(4)為最小費(fèi)用最大流。 圖 53
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1