《建筑系統(tǒng)工程學(xué)》工程系統(tǒng)分析講義4

1、第四章 網(wǎng)絡(luò)模型4-1 網(wǎng)絡(luò)模型及其特征4-2 圖論基礎(chǔ)4-3 最短路模型4-4 最大流模型4-5 最小費(fèi)用流模型4-6 最小樹(shù)模型4-1 網(wǎng)絡(luò)模型及其特征 網(wǎng)絡(luò)模型的構(gòu)成及其分類(lèi) 網(wǎng)絡(luò)模型的特征4-1 網(wǎng)絡(luò)模型及其特征一、網(wǎng)絡(luò)模型的構(gòu)成及其分類(lèi)1.網(wǎng)絡(luò)模型的構(gòu)成（1）節(jié)點(diǎn) 系統(tǒng)的組成要素（2）弧 要素間的關(guān)系（3）流量 要素間關(guān)系的量化a,b,ca,b4-1 網(wǎng)絡(luò)模型及其特征一、網(wǎng)絡(luò)模型的構(gòu)成及其分類(lèi)1.網(wǎng)絡(luò)模型的構(gòu)成2.網(wǎng)絡(luò)模型的分類(lèi)（1）以物質(zhì)為流量4-1 網(wǎng)絡(luò)模型及其特征一、網(wǎng)絡(luò)模型的構(gòu)成及其分類(lèi)1.網(wǎng)絡(luò)模型的構(gòu)成2.網(wǎng)絡(luò)模型的分類(lèi)（1）以物質(zhì)為流量（2）以信息為流量4-1 網(wǎng)絡(luò)模型及

2、其特征一、網(wǎng)絡(luò)模型的構(gòu)成及其分類(lèi)1.網(wǎng)絡(luò)模型的構(gòu)成2.網(wǎng)絡(luò)模型的分類(lèi)（1）以物質(zhì)為流量（2）以信息為流量（3）以能量為流量4-1 網(wǎng)絡(luò)模型及其特征一、網(wǎng)絡(luò)模型的構(gòu)成及其分類(lèi)1.網(wǎng)絡(luò)模型的構(gòu)成2.網(wǎng)絡(luò)模型的分類(lèi)（1）以物質(zhì)為流量（2）以信息為流量（3）以能量為流量（4）以時(shí)間、距離、費(fèi)用等為流量4-1 網(wǎng)絡(luò)模型及其特征一、網(wǎng)絡(luò)模型的構(gòu)成及其分類(lèi)二、網(wǎng)絡(luò)模型的特征1.能夠直觀地反映系統(tǒng)元素及其相互關(guān)系2.以不同的流量表述不同的系統(tǒng)問(wèn)題3.特定流量具有特定的算法4.簡(jiǎn)單直觀，易于掌握4-2 圖論基礎(chǔ) 圖的有關(guān)概念 連通圖與樹(shù)4-2 圖論基礎(chǔ)一、圖的有關(guān)概念1.圖節(jié)點(diǎn)與弧的集合。設(shè)N為節(jié)點(diǎn)的集合，E為

3、弧的集合，則圖G可以表示為：G=N，E1234e1e2e3e4e5e6G=N，EN=n1，n2，n3，n4E=e1，e2，e3，e4 ，e5，e64-2 圖論基礎(chǔ)一、圖的有關(guān)概念1.圖2.自環(huán)首尾均在一個(gè)節(jié)點(diǎn)的弧如 e21234e1e2e3e4e5e64-2 圖論基礎(chǔ)一、圖的有關(guān)概念1.圖2.自環(huán)3.關(guān)聯(lián)與鄰接1234e1e2e3e4e5e6(1)節(jié)點(diǎn)與弧相互關(guān)聯(lián)4-2 圖論基礎(chǔ)一、圖的有關(guān)概念1.圖2.自環(huán)3.關(guān)聯(lián)與鄰接1234e1e2e3e4e5e6(1)節(jié)點(diǎn)與弧相互關(guān)聯(lián)(2)弧與弧相互關(guān)聯(lián)4-2 圖論基礎(chǔ)一、圖的有關(guān)概念1.圖2.自環(huán)3.關(guān)聯(lián)與鄰接1234e1e2e3e4e5e6(1)節(jié)

4、點(diǎn)與弧相互關(guān)聯(lián)(2)弧與弧相互關(guān)聯(lián)(3)節(jié)點(diǎn)的鄰接前導(dǎo)節(jié)點(diǎn)后續(xù)節(jié)點(diǎn)4-2 圖論基礎(chǔ)一、圖的有關(guān)概念1.圖2.自環(huán)3.關(guān)聯(lián)與鄰接4.鏈的有關(guān)概念1234e1e2e3e4e5e6對(duì)于任一節(jié)點(diǎn)序列n1, n2, ,nk+1, ei為ni-1, ni構(gòu)成的弧，則弧的系列e1, e2, ,ek構(gòu)成一條鏈。 n1為鏈的始點(diǎn)， nk+1為鏈的終點(diǎn)，弧的數(shù)目k稱(chēng)為鏈的長(zhǎng)度。（1）鏈例如，節(jié)點(diǎn)序列2,3,4構(gòu)成的鏈234e3e5234e3e6e3234e44-2 圖論基礎(chǔ)一、圖的有關(guān)概念1.圖2.自環(huán)3.關(guān)聯(lián)與鄰接4.鏈的有關(guān)概念1234e1e2e3e4e5e6（1）鏈（2）路全部由同向弧組成的鏈例如，節(jié)點(diǎn)序列

5、2,3,4構(gòu)成的路234e3e5234e3e64-2 圖論基礎(chǔ)一、圖的有關(guān)概念1.圖2.自環(huán)3.關(guān)聯(lián)與鄰接4.鏈的有關(guān)概念1234e1e2e3e4e5e6（1）鏈（2）路（3）圈始點(diǎn)和終點(diǎn)為同一節(jié)點(diǎn)的鏈（閉合鏈）例如，節(jié)點(diǎn)序列2,3,4構(gòu)成的圈e5234e3234e3e6e44-2 圖論基礎(chǔ)一、圖的有關(guān)概念1.圖2.自環(huán)3.關(guān)聯(lián)與鄰接4.鏈的有關(guān)概念1234e1e2e3e4e5e6（1）鏈（2）路（3）圈（4）回路始點(diǎn)和終點(diǎn)為同一節(jié)點(diǎn)的路全部由同向弧組成的圈例如，節(jié)點(diǎn)序列2,3,4構(gòu)成的圈e5234e34-2 圖論基礎(chǔ)一、圖的有關(guān)概念二、連通圖與樹(shù)1.連通圖與不連通圖1234e1e2e3e4e

6、5e6（1）連通圖：圖中任意兩節(jié)點(diǎn)間至少存在一條鏈（2）不連通圖：圖中至少有兩節(jié)點(diǎn)間不存在鏈12345674-2 圖論基礎(chǔ)一、圖的有關(guān)概念二、連通圖與樹(shù)1.連通圖與不連通圖2.子圖1234e1e2e3e4e5e6（1）由節(jié)點(diǎn)子集生成的子圖：包括該節(jié)點(diǎn)子集及兩個(gè)端點(diǎn)都在該節(jié)點(diǎn)子集上的所有弧。例如，由節(jié)點(diǎn)2,3,4生成的子圖234e2e3e4e5e64-2 圖論基礎(chǔ)一、圖的有關(guān)概念二、連通圖與樹(shù)1.連通圖與不連通圖2.子圖1234e1e2e3e4e5e6（2）由弧子集生成的子圖：包括該弧子集及該弧子集的所有端點(diǎn)。例如，由弧e2,e3,e4生成的子圖e2234e3e44-2 圖論基礎(chǔ)一、圖的有關(guān)概念

7、二、連通圖與樹(shù)1.連通圖與不連通圖2.子圖3.樹(shù)1234e1e2e3e4e5e6無(wú)圈的連通圖或子圖234e3e44-2 圖論基礎(chǔ)一、圖的有關(guān)概念二、連通圖與樹(shù)1.連通圖與不連通圖2.子圖3.樹(shù)4.有向圖與無(wú)向圖(1)有向圖：規(guī)定了弧的方向的圖（至少包含一條箭線(xiàn)）(2)無(wú)向圖：未規(guī)定弧的方向的圖（不包含任何箭線(xiàn)）4-3 最短路模型一、問(wèn)題的提出通過(guò)網(wǎng)絡(luò)各邊所需要的時(shí)間、距離或費(fèi)用等為已知時(shí)，欲找出從始點(diǎn)s至終點(diǎn)t的最少時(shí)間、最短路徑或最小費(fèi)用等的路徑問(wèn)題。 設(shè)備更新問(wèn)題 編制生產(chǎn)計(jì)劃問(wèn)題 物資輸送問(wèn)題 新產(chǎn)品試制規(guī)劃問(wèn)題 旅行線(xiàn)路選擇問(wèn)題4-3 最短路模型二、最短路模型的算法1.基本思路Dijk

8、stra算法：假定12 34是14的最短路，則12 3一定是13的最短路， 2 34一定是24的最短路12344-3 最短路模型二、最短路模型的算法1.基本思路2.有關(guān)符號(hào)ijijijb(i,j)b(i,j)b(i,j)s 始點(diǎn)t 終點(diǎn)b(i,j) 節(jié)點(diǎn)i至節(jié)點(diǎn)j的直達(dá)距離T(j) s至j的最短路長(zhǎng)度P(j) s至j為最短路時(shí), j的前導(dǎo)節(jié)點(diǎn)號(hào)k 最新標(biāo)記的節(jié)點(diǎn)號(hào)sjT(j)P(j)4-3 最短路模型二、最短路模型的算法3.算法步驟開(kāi)始對(duì)s標(biāo)記,k=s,T(s)=0,其余T(j)k有未標(biāo)記未計(jì)算的后續(xù)節(jié)點(diǎn)?T(j)=T(k)+b(k,j)P(j)=kYN1NY選擇這樣一個(gè)節(jié)點(diǎn)jT(k)+b(k

9、,j)T(j)?skjT(j)b(k,j)T(k)4-3 最短路模型二、最短路模型的算法3.算法步驟開(kāi)始對(duì)s標(biāo)記,k=s,T(s)=0,其余T(j)k有未標(biāo)記未計(jì)算的后續(xù)節(jié)點(diǎn)?T(j)=T(k)+b(k,j)P(j)=kYN1NY選擇這樣一個(gè)節(jié)點(diǎn)jT(k)+b(k,j)T(j)?1所有未標(biāo)記節(jié)點(diǎn)T(j) ?t標(biāo)記否?結(jié)束中止無(wú)最短路Y選擇未標(biāo)記節(jié)點(diǎn)中minT(j)對(duì)應(yīng)的節(jié)點(diǎn)x,對(duì)x及弧P(x) x進(jìn)行標(biāo)記,令k=xN2N找到最短路Y24-3 最短路模型二、最短路模型的算法4.計(jì)算示例s1223352575245315t74-3 最短路模型二、最短路模型的算法4.計(jì)算示例s12233525752

10、45315t7s12對(duì)S標(biāo)記,k=s,T(s)=0,其余T(j)T(s)+b(s,1)=0+2=2T(1), T(1)=2, P(1)=sT(s)+b(s,2)=0+3=3T(2), T(2)=3, P(2)=sT(s)+b(s,3)=0+5=5T(3), T(3)=5, P(3)=sminT(j)=2, x=1 k=1, 對(duì)節(jié)點(diǎn)1及s1標(biāo)記T(1)+b(1,3)=2+2=4T(3), T(3)=4, P(3)=1T(1)+b(1,5)=2+7=9T(5), T(5)=9, P(5)=1minT(j)=3, x=2 k=2, 對(duì)節(jié)點(diǎn)2及s2標(biāo)記4-3 最短路模型二、最短路模型的算法4.計(jì)算示例

11、s1223352575245315t7s12T(2)+b(2,4)=3+5=8T(4), T(4)=8, P(4)=2minT(j)=4, x=3 k=3, 對(duì)節(jié)點(diǎn)3及13標(biāo)記T(3)+b(3,4)=4+3=7T(4), T(4)=7, P(4)=3T(3)+b(3,5)=4+5=9=T(5)minT(j)=7, x=4 k=4, 對(duì)節(jié)點(diǎn)4及34標(biāo)記T(4)+b(4,5)=7+1=8T(5), T(5)=8, P(5)=4T(4)+b(4,t)=7+7=14T(t), T(t)=14,P(t)=4minT(j)=8, x=5 k=5, 對(duì)節(jié)點(diǎn)5及45標(biāo)記T(5)+b(5,t)=8+5=13T(

12、t), T(t)=13,P(t)=5minT(j)=13, x=t k=t, 對(duì)節(jié)點(diǎn)t及5t標(biāo)記345t4-3 最短路模型三、最短路問(wèn)題構(gòu)模舉例例1 設(shè)備更新問(wèn)題 某建筑公司在第一年開(kāi)始購(gòu)買(mǎi)一臺(tái)新的施工設(shè)備，用了一段時(shí)間后進(jìn)行更新?，F(xiàn)在，希望找到五年內(nèi)的一種最好的更新策略，使得施工機(jī)具的購(gòu)置費(fèi)用和維修費(fèi)之和為最小。施工機(jī)具的購(gòu)置費(fèi)和維修費(fèi)分別如下表所示：第一至第五年施工機(jī)具購(gòu)置費(fèi)年費(fèi)用(萬(wàn)元)1 2 3 4 51.1 1.1 1.2 1.2 1.34-3 最短路模型三、最短路問(wèn)題構(gòu)模舉例例1 設(shè)備更新問(wèn)題 某建筑公司在第一年開(kāi)始購(gòu)買(mǎi)一臺(tái)新的施工設(shè)備，用了一段時(shí)間后進(jìn)行更新?，F(xiàn)在，希望找到五年內(nèi)

13、的一種最好的更新策略，使得施工機(jī)具的購(gòu)置費(fèi)用和維修費(fèi)之和為最小。施工機(jī)具的購(gòu)置費(fèi)和維修費(fèi)分別如下表所示：第一至第五年施工機(jī)具購(gòu)置費(fèi)年費(fèi)用(萬(wàn)元)1 2 3 4 51.1 1.1 1.2 1.2 1.3維修費(fèi)與機(jī)具使用年限的關(guān)系使用年限費(fèi)用(萬(wàn)元)010.5120.6230.8341.1451.84-3 最短路模型三、最短路問(wèn)題構(gòu)模舉例例1 設(shè)備更新問(wèn)題 某建筑公司在第一年開(kāi)始購(gòu)買(mǎi)一臺(tái)新的施工設(shè)備，用了一段時(shí)間后進(jìn)行更新?，F(xiàn)在，希望找到五年內(nèi)的一種最好的更新策略，使得施工機(jī)具的購(gòu)置費(fèi)用和維修費(fèi)之和為最小。施工機(jī)具的購(gòu)置費(fèi)和維修費(fèi)分別如下表所示：第一至第五年施工機(jī)具購(gòu)置費(fèi)年費(fèi)用(萬(wàn)元)1 2 3

14、4 51.1 1.1 1.2 1.2 1.3維修費(fèi)與機(jī)具使用年限的關(guān)系使用年限費(fèi)用(萬(wàn)元)010.5120.6230.8341.1451.811.621.631.751.862.23.04.15.92.23.04.12.31.743.12.34-3 最短路模型三、最短路問(wèn)題構(gòu)模舉例例1 設(shè)備更新問(wèn)題11.621.631.741.751.862.23.04.15.92.23.04.13.12.34-3 最短路模型三、最短路問(wèn)題構(gòu)模舉例例1 設(shè)備更新問(wèn)題11.621.631.741.751.862.23.04.15.92.23.04.13.12.31634501.62.23.04.15.95.75

15、.324-3 最短路模型三、最短路問(wèn)題構(gòu)模舉例例2 施工方案選擇問(wèn)題 某建設(shè)工程還有四個(gè)項(xiàng)目沒(méi)完成，根據(jù)需要希望該工程盡早投入使用。已知這四個(gè)項(xiàng)目在正常施工、采取一般措施施工和采取緊急措施施工情況下需要的時(shí)間和費(fèi)用如下表：時(shí)間（月）項(xiàng) 目1 2 3 4 施工方式正常一般措施緊急措施5423253214-3 最短路模型三、最短路問(wèn)題構(gòu)模舉例例2 施工方案選擇問(wèn)題 某建設(shè)工程還有四個(gè)項(xiàng)目沒(méi)完成，根據(jù)需要希望該工程盡早投入使用。已知這四個(gè)項(xiàng)目在正常施工、采取一般措施施工和采取緊急措施施工情況下需要的時(shí)間和費(fèi)用如下表：時(shí)間（月）項(xiàng) 目1 2 3 4 施工方式正常一般措施緊急措施542325321費(fèi)用（

16、萬(wàn)元）123233412項(xiàng) 目1 2 3 4 施工方式正常一般措施緊急措施 已知這四個(gè)項(xiàng)目必須按順序施工，為完成這四項(xiàng)工程的全部追加投資為10萬(wàn)元，問(wèn)在投資允許范圍內(nèi)，如何安排施工，使全部工程盡早投入使用？4-3 最短路模型三、最短路問(wèn)題構(gòu)模舉例例2 施工方案選擇問(wèn)題s,101,952,843,724,735,6236,5237,428, 459,33510,23511,13512,3213,21214,11215,012t0000最優(yōu)施工方案即為從s至t的最短路徑x-節(jié)點(diǎn)序號(hào)y-剩余的趕工費(fèi)用T-項(xiàng)目持續(xù)時(shí)間xi,yixj,yjT工序2工序1工序3工序44-4 最大流模型一、最大流的有關(guān)概念

17、1.容量網(wǎng)絡(luò)(1) 流將目標(biāo)從一個(gè)地點(diǎn)送至另一個(gè)地點(diǎn)的活動(dòng)網(wǎng)絡(luò)上各條弧的一組負(fù)載量(2) 容量每條弧流的最大通過(guò)能力 c (x,y)(3) 流量通過(guò)弧的流的單位數(shù)量 f (x,y)(4) 最大流網(wǎng)絡(luò)中允許通過(guò)的最大流量4-4 最大流模型一、最大流的有關(guān)概念2.可行流(1) 容量限制條件0f (x,y)C(x,y) (x,y)E(2)中間節(jié)點(diǎn)平衡條件 f (x,y)-f (y,x)=0 (ys,t)(3) 發(fā)點(diǎn)平衡條件滿(mǎn)足下列條件的流稱(chēng)為可行流f (s,y)-f (y,s)=vyf (x,y)f (y,x)(4) 收點(diǎn)平衡條件f (t,y)-f (y,t)= -vsf (y,s)f (s,y)t

18、f (y,t)f (t,y)4-4 最大流模型一、最大流的有關(guān)概念3.弧的分類(lèi)(1) N-流不能有任何增加或減少的弧的集合(2) I-流可以增加的弧的集合 最大增量 i(x,y)=c(x,y)-f(x,y)(3) R-流可以減少的弧的集合 最大減量 r(x,y)=f(x,y)4-4 最大流模型一、最大流的有關(guān)概念4.增值鏈(1) 從st全部由前向弧組成的路P定義前向弧為st方向，I；后向弧為ts方向，Rs123ti(s,1)=2i(1,2)=4i(2,3)=5i(3,t)=34-4 最大流模型一、最大流的有關(guān)概念4.增值鏈(1) 從st全部由前向弧組成的路P(2) 從st全部由后向弧組成的路P

19、定義前向弧為st方向，I；后向弧為ts方向，Rs123tr(s,1)=3r(1,2)=2r(2,3)=4r(3,t)=14-4 最大流模型一、最大流的有關(guān)概念4.增值鏈(1) 從st全部由前向弧組成的路P(2) 從st全部由后向弧組成的路P(3) 從st即有前向弧又有后向弧組成的鏈P定義前向弧為st方向，I；后向弧為ts方向，Rs123tr(s,1)=3i(1,2)=4r(2,3)=4r(3,t)=24-4 最大流模型二、最大流的算法1.基本思路尋找st的增值鏈?zhǔn)欠裼校垦卦撴溦{(diào)整流量Y達(dá)到最大流N4-4 最大流模型二、最大流的算法2.確定增值鏈的方法開(kāi)始有已標(biāo)記未檢查節(jié)點(diǎn)?選擇相鄰未標(biāo)記節(jié)點(diǎn)y

20、YY選擇已標(biāo)記未檢查節(jié)點(diǎn)xX有相鄰未標(biāo)記節(jié)點(diǎn)?N無(wú)增值鏈Nx為已檢查節(jié)點(diǎn)對(duì)s標(biāo)記21結(jié) 束t標(biāo)記?找到增值鏈Y對(duì)y及弧(x,y)標(biāo)記I、R類(lèi)N2(x,y)類(lèi)型?12N類(lèi)結(jié) 束4-4 最大流模型二、最大流的算法3.最大流的標(biāo)號(hào)算法開(kāi)始對(duì)s標(biāo)記為(-, )有已標(biāo)記未檢查節(jié)點(diǎn)?X有相鄰未標(biāo)記節(jié)點(diǎn)?選擇相鄰未標(biāo)記節(jié)點(diǎn)y1YYNN選擇已標(biāo)記未檢查節(jié)點(diǎn)x為最大流中止3=0 x為已檢查節(jié)點(diǎn)2(x,y)類(lèi)型?對(duì)y標(biāo)記為(x+,(y)(y)= min (x),c(x,y)-f(x,y)t標(biāo)記?改變流量(t)= + (t)取消全部標(biāo)記R類(lèi)NY1對(duì)y標(biāo)記為(x-,(y)(y)=min(x),f(x,y)22N類(lèi)I類(lèi)

21、34-4 最大流模型二、最大流的算法3.最大流的標(biāo)號(hào)算法S113429459t41055543654-4 最大流模型二、最大流的算法3.最大流的標(biāo)號(hào)算法S113429459t4105554365S 1 2 3 4 5 t (-,)(s+,13)(1+,5)(4+,5)5(5(5)(54-4 最大流模型二、最大流的算法3.最大流的標(biāo)號(hào)算法S 1 2 3 4 5 t (-,)(s+,13)(1+,5)(4+,5)5S113429459t4105554365(5(5)(5(-,)(s+,8)(1+,6)(3+,4)5+4=9,9(4(4)4-4 最大流模型二、最大流的算法3.最大流的標(biāo)號(hào)算法S 1

22、2 3 4 5 t (-,)(s+,13)(1+,5)(4+,5)5(-,)(s+,8)(1+,6)(3+,4)5+4=9S113429459t4105554365(5(5)(5,9(4(4)(-,)(s+,4)(1+,2)(3+,2)(4+,2)9+2=11,11,6)(2,74-4 最大流模型二、最大流的算法3.最大流的標(biāo)號(hào)算法S 1 2 3 4 5 t (-,)(s+,13)(1+,5)(4+,5)5(-,)(s+,8)(1+,6)(3+,4)5+4=9(-,)(s+,4)(1+,2)(3+,2)(4+,2)9+2=11S113429459t4105554365(5(5)(5,9(4(4

23、),11,6)(2,7(-,)(s+,2)(s+,9)(2+,5)(5+,5)11+5=16(5(5)(54-4 最大流模型二、最大流的算法3.最大流的標(biāo)號(hào)算法S 1 2 3 4 5 t (-,)(s+,13)(1+,5)(4+,5)5(-,)(s+,8)(1+,6)(3+,4)5+4=9(-,)(s+,4)(1+,2)(3+,2)(4+,2)9+2=11(-,)(s+,2)(s+,9)(2+,5)(5+,5)11+5=16S113429459t4105554365(5(5)(5,9(4(4),11,6)(2,7(5(5)(5(-,)(s+,2)(s+,4)(2+,4)(3+,4)16+4=2

24、0(5+,4),9(4(4),9(-,)(s+,2)最大流=204-4 最大流模型三、多收點(diǎn)與多發(fā)點(diǎn)的修正StS1S2t1t2t3S1發(fā)量S2發(fā)量t1收量t2收量t3收量4-4 最大流模型四、最大流量最小截量定理在任一個(gè)網(wǎng)絡(luò)D中,從s至t的最大流流量等于分離s、t的最小截集的容量。S12345t134959410554652220272321242323最小截面=204-4 最大流模型四、最大流量最小截量定理例：某高速公路的線(xiàn)路如下圖，現(xiàn)擬建立足夠數(shù)量的收費(fèi)站，以使從s至t的每輛汽車(chē)至少必須通過(guò)一個(gè)收費(fèi)站。建立收費(fèi)站的費(fèi)用如圖所示，求最小費(fèi)用解。s1234567t468252573843764

25、4-4 最大流模型四、最大流量最小截量定理例：某高速公路的線(xiàn)路如下圖，現(xiàn)擬建立足夠數(shù)量的收費(fèi)站，以使從s至t的每輛汽車(chē)至少必須通過(guò)一個(gè)收費(fèi)站。建立收費(fèi)站的費(fèi)用如圖所示，求最小費(fèi)用解。s1234567t468252573843764(2(2)(2(2,4)(2)(2,4,4)(6)(6(6(1(1,7),7),4,4,5)(3(3最小費(fèi)用=14，在1-4，2-4，2-5間建收費(fèi)站。4-5 最小費(fèi)用流模型一、問(wèn)題的提出在最大可能運(yùn)送的情況下，如何使運(yùn)費(fèi)最?。吭O(shè)a(x,y)-沿弧(x,y)運(yùn)送單位流量的費(fèi)用（正整數(shù)） v-從st運(yùn)送的數(shù)量S.b.4-5 最小費(fèi)用流模型二、最小費(fèi)用流算法1.算法原理逐

26、次找全程單位運(yùn)費(fèi)為0，1，2，的路徑。2.算法步驟開(kāi)始v0=?執(zhí)行最大流算法所有f(x,y)=0,p(x)=0標(biāo)記S,v0=0v0= v0 +結(jié)束YN未標(biāo)記節(jié)點(diǎn)P(x)=p(x)+1計(jì)算總費(fèi)用=v是否達(dá)到最大流其他注意：弧的分類(lèi)作如下規(guī)定I: f(x,y)0 |p(y)-p(x)|=a(x,y)4-5 最小費(fèi)用流模型二、最小費(fèi)用流算法3.算法舉例求圖示網(wǎng)絡(luò) v=7和最大流時(shí)的最小費(fèi)用s123t(4,10)(1,8)(2,5)(3,10)(6,2)(1,7)(2,4)迭代 p(s) p(1) p(2) p(3) p(t) 標(biāo)記節(jié)點(diǎn) 標(biāo)記邊 0 0 0 0 0 0(a,b)容量單位運(yùn)費(fèi)迭代0：所有

27、弧Nss無(wú) 1 0 1 1 1 1迭代1：P(2)-p(s)=1 I2s,2 (s,2)未標(biāo)記節(jié)點(diǎn) p(x)=p(x)+1 (xs,2)未標(biāo)記節(jié)點(diǎn) p(x)=p(x)+1 (xs)2 0 2 1 2 2s,2 (s,2) 迭代2：未標(biāo)記節(jié)點(diǎn) p(x)=p(x)+1 (xs,2)4-5 最小費(fèi)用流模型二、最小費(fèi)用流算法3.算法舉例求圖示網(wǎng)絡(luò) v=7和最大流時(shí)的最小費(fèi)用s123t(4,10)(1,8)(2,5)(3,10)(6,2)(1,7)(2,4)迭代 p(s) p(1) p(2) p(3) p(t) 標(biāo)記節(jié)點(diǎn) 標(biāo)記邊 0 0 0 0 0 0(a,b)容量單位運(yùn)費(fèi)ss無(wú) 1 0 1 1 1 1

28、2s,2 (s,2)2 0 2 1 2 2s,2 (s,2) 迭代3：P(1)-P(2)=2 I 3 0 3 1 3 31未標(biāo)記節(jié)點(diǎn) p(x)=p(x)+1 (xs,1,2)s,2,1 (s,2) (2,1) 4-5 最小費(fèi)用流模型二、最小費(fèi)用流算法3.算法舉例求圖示網(wǎng)絡(luò) v=7和最大流時(shí)的最小費(fèi)用s123t(4,10)(1,8)(2,5)(3,10)(6,2)(1,7)(2,4)迭代 p(s) p(1) p(2) p(3) p(t) 標(biāo)記節(jié)點(diǎn) 標(biāo)記邊 0 0 0 0 0 0(a,b)容量單位運(yùn)費(fèi)ss無(wú) 1 0 1 1 1 12s,2 (s,2)2 0 2 1 2 2s,2 (s,2) 3 0

29、 3 1 3 31s,2,1 (s,2) (2,1) 4 0 3 1 4 4迭代4：P(t)-P(1)=1 I P(3)-P(2)=3 I3t857=5 v0=5 s,2,3 (s,2) (2,3) 未標(biāo)記節(jié)點(diǎn) p(x)=p(x)+1 (xs,2,3)4-5 最小費(fèi)用流模型二、最小費(fèi)用流算法3.算法舉例求圖示網(wǎng)絡(luò) v=7和最大流時(shí)的最小費(fèi)用s123t(4,10)(1,8)(2,5)(3,10)(6,2)(1,7)(2,4)迭代 p(s) p(1) p(2) p(3) p(t) 標(biāo)記節(jié)點(diǎn) 標(biāo)記邊 0 0 0 0 0 0(a,b)容量單位運(yùn)費(fèi)ss無(wú) 1 0 1 1 1 12s,2 (s,2)2 0 2 1 2 2s,2 (s,2) 3 0 3 1 3 3s,2,1 (s,2) (2,1) 4 0 3 1 4 43s,2,3 (s,2) (2,3) 迭代5：P(1)-P(s)=4 I1未標(biāo)記節(jié)點(diǎn) p(x)=p(x)+1 (xs,1,2,3)3t102=2 v0=5+2=7 5 0 4 1 4 5C=54+25=30s,1,2,3 (s,1)(s,2)(2,3)4-5 最小費(fèi)用流模型二、最小費(fèi)用流算法3.算法舉例求圖示網(wǎng)絡(luò) v=7和最大流時(shí)的最小費(fèi)用s123t(4,10)(1,8)(2,5)(3,10)(6,2)(1,7)(2,4)迭代 p(s) p(1) p(2) p(