運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型-預(yù)覽頁
【正文】 v7 v6 v5 v4 v2 v3 圖 611 方法一：破圈法 步驟： 在給定的賦權(quán)的連通圖上任找一個(gè)圈。 方法二： (加邊 )避圈法（ Kruskal） ?開始選一條最小權(quán)的邊，以后每一步中，總從未被選中的邊中選一條最小權(quán)的邊，使之與已選的邊不構(gòu)成圈，直到所有的邊都檢驗(yàn)完，即可得最小樹。房屋開發(fā)商應(yīng)怎樣設(shè)計(jì)最佳的管道鋪設(shè)方案，使總工程費(fèi)用最少。 為計(jì)算簡單起見 ， 假設(shè)任何時(shí)間新車的價(jià)格不變均為12021美元 。 Cij=(i,i+1, ? 從節(jié)點(diǎn) 6開始回退，得到最短路。 圖 84 ? 解： 計(jì)算的最后結(jié)果為 ? P(v1)=0， P(v4)=1， P(v3)=3， P(v2)=5， P(v5)=6， P(v9)=8，P(v7)=9， P(v6)=10， P(v8)=11。若購置新設(shè)備，就要支付一定的購置費(fèi)用；若繼續(xù)使用舊設(shè)備，則需支付一定的維修費(fèi)用。于是五年總的支付費(fèi)用為59+25=84。 圖 85 這樣一來，制定一個(gè)最優(yōu)的設(shè)備更新計(jì)劃問題就等價(jià)于尋求從 v1到 v6的最短路的問題。 城市出租車公司在紐約市為出租車司機(jī)已經(jīng)確定了 10個(gè)搭乘車站。 最優(yōu)路線為： 1－５－４－６－７－ 10，最短距離是 25 例：六個(gè)村莊每村上學(xué)人數(shù)見下表，村與村的距離見下圖，現(xiàn)只能在某一個(gè)村建一所小學(xué)，問在哪個(gè)村建校最為合理？ 村莊 A B C D E F 上學(xué)人數(shù) 60 40 50 30 70 100 A B C E F D 6 3 3 6 4 7 2 8 1 第四節(jié) 網(wǎng)絡(luò)最大流問題 ?一、基本概念與基本定理 ?二、尋求最大流的標(biāo)號(hào)法 容量網(wǎng)絡(luò)、可行流 2 4 5 3 1 14 20 10 5 19 15 27 30 流 量 容量 ? 容量網(wǎng)絡(luò)： 標(biāo)有弧容量的網(wǎng)絡(luò)。 可行流與最大流 在運(yùn)輸網(wǎng)絡(luò)的實(shí)際問題中可以看出，對(duì)于流有兩個(gè)明顯的要求： (即弧的容量 )； 。 ( ) A ( ) A0i j j ii j j iv ,v v ,vff??????ssss( ) A ( ) A()jjjjv ,v v ,vf f v f??????tttt( ) A ( ) A()jjjjv ,v v ,vf f v f??? ? ???? 可行流總是存在的。即求一組｛ fij｝，在滿足條件①和②下使 v(f)達(dá)到極大。 割集 2 1 s t 2 8 8 1 1 ? 任給一個(gè)包含收點(diǎn)但不包含發(fā)點(diǎn)的支點(diǎn)集 V*，則稱 i(弧起點(diǎn) )不屬于 V*， j(弧終點(diǎn) )屬于 V*的弧 (i,j)的全體為割集。 ? 任何從發(fā)點(diǎn)到收點(diǎn)的可行流小于等于任何割集的容量。 最大流 最小割集定理 V*={1,t} 割集是 {(s,1)， (2,t)}，容量 2+1=3 支點(diǎn)集 V*={1,2,t} ,割集？ {(s,1)， (s,2)},容量 2+8=10 0?jif jv ))(,( ji vlv? 從一個(gè)可行流 出發(fā)，（若網(wǎng)絡(luò)中沒有給定 f，則可以設(shè) f是零流）需要經(jīng)過標(biāo)號(hào)過程與調(diào)整過程。其余各點(diǎn)標(biāo)號(hào)的規(guī)則是： 設(shè) 是已標(biāo)號(hào)的點(diǎn)，檢查與 點(diǎn)關(guān)聯(lián)的另一頂點(diǎn)未標(biāo)號(hào)的弧： （ 1）如果在弧 上（即前向?。?， ，則給 標(biāo)號(hào) ， 其中 。 重復(fù)上述步驟，直到被 標(biāo)上號(hào)，表明得到一條從 到 的增廣鏈 C，轉(zhuǎn)入調(diào)整過程。直到標(biāo)號(hào)過程中斷。 ● 其余各點(diǎn)標(biāo)號(hào)的規(guī)則是：設(shè) vi是已標(biāo)號(hào)的點(diǎn)，檢查與點(diǎn) vi關(guān)聯(lián)的另一頂點(diǎn)未標(biāo)號(hào)的?。? ●（ 1）如果在弧 (vi,vj)上（即前向?。?，fijcij，則給 vj標(biāo)號(hào) (vi,l(vj))，其中l(wèi)(vj)=min{l(vi),cijfij}。 ? 調(diào)整： ● 按照第一標(biāo)號(hào)找到增廣鏈， ● 按第二標(biāo)號(hào)的最小值調(diào)整可行流，得到新的可行流。 ? 給網(wǎng)絡(luò)中的各個(gè)點(diǎn)標(biāo)號(hào)： ● 先給發(fā)點(diǎn) vs標(biāo)上 (0,+∞) 。 最大流量為從發(fā)點(diǎn)流出的量 422)(21 ????? ss fffv這時(shí)的可行流就是所求的最大流 練習(xí)： 用標(biāo)號(hào)法求圖 87所示網(wǎng)絡(luò)的最大流。 在弧 (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)行檢查。 μ+上： fs1+θ=1+1=2 f3t+θ=1+1=2 μ上： f21?θ=1?1=0 f32?θ=1?1=0 其余的 fij不變。最大流量為 v(f)=fs1+fs2=f4t+f3t=5 與此同時(shí)可找到最小截集 ， 其中 V1為標(biāo)號(hào)點(diǎn)集合， 為未標(biāo)號(hào)點(diǎn)集合。 特別，如果可行流是最大流時(shí)，此問題就是最小費(fèi)用最大流問題。 (2) 構(gòu)造賦權(quán)有向圖 W(f(0)) ，并求出從 v s 到 v t 的 最短路 (v s ,v 2 ,v 1 ,v t ) ，如圖 5 3 ( b )( 雙箭頭即為最短路 ) 。 圖 53
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1