道路交通運(yùn)輸系統(tǒng)網(wǎng)絡(luò)技術(shù)

1、學(xué)生：劉洋 楊暖 張凌雪交通運(yùn)輸系統(tǒng)網(wǎng)絡(luò)分析技術(shù)2引例（引例（1 1）哥尼斯堡七橋問題）哥尼斯堡七橋問題C CB BA AD DB BC CA AD D問：從岸上某點(diǎn)出發(fā)，能否恰好經(jīng)過每座橋問：從岸上某點(diǎn)出發(fā)，能否恰好經(jīng)過每座橋一次又回到出發(fā)點(diǎn)？如果可以，路線如何？一次又回到出發(fā)點(diǎn)？如果可以，路線如何？第二節(jié)第二節(jié) 圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念3引例（引例（2 2）鐵路運(yùn)輸網(wǎng)絡(luò)圖）鐵路運(yùn)輸網(wǎng)絡(luò)圖x x1 1x x2 2y y1 1y y2 2v v1 1v v2 2v v3 34一、圖和網(wǎng)絡(luò)圖一、圖和網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖：圖中各邊賦予一定的物理量，這樣的圖網(wǎng)絡(luò)圖：圖中各邊賦予一定的物理量，這樣

2、的圖稱為網(wǎng)絡(luò)圖。稱為網(wǎng)絡(luò)圖。權(quán)：與各邊有關(guān)的物理量稱為該邊的權(quán)。權(quán)：與各邊有關(guān)的物理量稱為該邊的權(quán)。圖：由一個表示事物的圖：由一個表示事物的“點(diǎn)的集合點(diǎn)的集合(V)(V)”和一和一個表示事物之間個表示事物之間關(guān)聯(lián)關(guān)系關(guān)聯(lián)關(guān)系的的“線的集合線的集合(E)(E)”組成的組成的點(diǎn)線圖（點(diǎn)線圖（V V，E E）。權(quán)權(quán)5鏈：在圖中任意兩點(diǎn)之間由頂點(diǎn)和邊相互交替構(gòu)成的一鏈：在圖中任意兩點(diǎn)之間由頂點(diǎn)和邊相互交替構(gòu)成的一個序列。個序列。路：在有向圖中，如果鏈中的每條邊的方向是和鏈的走路：在有向圖中，如果鏈中的每條邊的方向是和鏈的走向一致，則該鏈稱為路。向一致，則該鏈稱為路。閉鏈（圈）：起點(diǎn)和終點(diǎn)相同的閉鏈（圈

3、）：起點(diǎn)和終點(diǎn)相同的鏈鏈?；芈罚浩瘘c(diǎn)和終點(diǎn)相同的回路：起點(diǎn)和終點(diǎn)相同的路路。連通圖：任意兩點(diǎn)之間都有一條鏈相連。連通圖：任意兩點(diǎn)之間都有一條鏈相連。6AEDSTBCe1e2e4e9e11e5e10e13e12e8e7e3e6相鄰相鄰關(guān)聯(lián)關(guān)聯(lián)AEDSTCe1e2e4e6e8e9e7e5e37如果圖中兩點(diǎn)之間的聯(lián)線如果圖中兩點(diǎn)之間的聯(lián)線無方向之別，稱之為無方向之別，稱之為無向邊無向邊，相應(yīng)的圖稱為相應(yīng)的圖稱為無向圖，記為無向圖，記為G=G=（V V，E E）。無向圖與有向圖無向圖與有向圖1 1、無向圖、無向圖V=vV=v1 1, ,v,vn n E=eE=e1 1, ,e,em m e=(u,v)

4、e=(u,v)= =(v,u)(v,u)B BC CA AD D8如果圖中兩點(diǎn)之間的聯(lián)線如果圖中兩點(diǎn)之間的聯(lián)線有方向之別，稱之為有方向之別，稱之為有向邊有向邊（一般用箭頭表示方向），（一般用箭頭表示方向）， 相應(yīng)的圖稱為相應(yīng)的圖稱為有向圖，記為有向圖，記為D=D=（V V，E E）。）。2 2、有向圖、有向圖V=vV=v1 1, ,v,vn n E=eE=e1 1, ,e,em m e=(u,v)e=(u,v) (v,u)(v,u)x x1 1x x2 2y y1 1y y2 2v v1 1v v2 2v v3 39二、樹及其性質(zhì)二、樹及其性質(zhì)（一）樹的概念（一）樹的概念 （1 1）樹：不含圈

5、的連通圖，即無回路且連通的無）樹：不含圈的連通圖，即無回路且連通的無向圖，記為向圖，記為“T T”； （2 2）生成樹：若）生成樹：若T=T=（V V，E E）是無向圖）是無向圖G=G=（V V，E E）的生成子圖，且的生成子圖，且T=T=（V V，E E）是一個樹，則稱是一個樹，則稱T T是是G G的的生成樹。生成樹。 v v2 2v v3 3v v4 4v v5 5e e3 3e e2 2e e4 4e e1 1v v2 2v v1 1v v3 3v v4 4v v5 5e e1 1e e2 2e e3 3e e6 6e e5 5e e7 7e e4 4v v1 110(3)(3)根樹：若

6、有向圖根樹：若有向圖T T中頂點(diǎn)中頂點(diǎn)x x到任意其他頂點(diǎn)到任意其他頂點(diǎn)v v 都恰有一條初等鏈，則都恰有一條初等鏈，則T T為以為以x x為根的根樹。為根的根樹。 (4)(4)有向樹：若有向圖有向樹：若有向圖T T中頂點(diǎn)中頂點(diǎn)x x到任意其他頂點(diǎn)到任意其他頂點(diǎn) v v都恰有一條路徑，則稱都恰有一條路徑，則稱T T為以為以x x為根的有向樹。為根的有向樹。 x xx x11（二）樹的基本性質(zhì)（二）樹的基本性質(zhì) （1 1）T T連通且無回路；連通且無回路； （2 2）T T無回路且有邊；無回路且有邊； （3 3）T T連通且有連通且有(n-1)(n-1)條邊；條邊； （4 4）T T無回路，但不

7、相鄰的兩個頂點(diǎn)聯(lián)以一邊無回路，但不相鄰的兩個頂點(diǎn)聯(lián)以一邊 恰得一個回路；恰得一個回路； （5 5）T T連通，但去掉任意一條邊，連通，但去掉任意一條邊，T T就不連通；就不連通； （6 6）T T的任意頂點(diǎn)之間恰有一條初等鏈。的任意頂點(diǎn)之間恰有一條初等鏈。v v2 2v v3 3v v4 4v v5 5e e3 3e e2 2e e4 4e e1 1v v1 1x x第二節(jié)第二節(jié) 最短路問題最短路問題12v1v4v6v3v7v5v2求最短路問題的基本思路求最短路問題的基本思路13Dijkstra法法 1959年首先提出，稱為標(biāo)號法。常用于年首先提出，稱為標(biāo)號法。常用于計算從某一指定點(diǎn)（起點(diǎn)）到

8、另一指定（終計算從某一指定點(diǎn)（起點(diǎn)）到另一指定（終點(diǎn)）之間的最短路徑。點(diǎn)）之間的最短路徑。14算法思想算法思想 1、首先從起點(diǎn)、首先從起點(diǎn)O開始，給每個節(jié)點(diǎn)一個標(biāo)號，開始，給每個節(jié)點(diǎn)一個標(biāo)號，分別為分別為T標(biāo)號和標(biāo)號和P標(biāo)號；標(biāo)號； T是臨時標(biāo)號，表示從起點(diǎn)是臨時標(biāo)號，表示從起點(diǎn)O到該點(diǎn)的最短路權(quán)到該點(diǎn)的最短路權(quán)的上限；的上限；P是固定標(biāo)號，表示從起點(diǎn)是固定標(biāo)號，表示從起點(diǎn)O到該點(diǎn)的到該點(diǎn)的最短路徑。最短路徑。 2、標(biāo)號過程中，、標(biāo)號過程中，T 標(biāo)號一直在變，標(biāo)號一直在變，P 標(biāo)號不變，標(biāo)號不變，凡沒有標(biāo)上凡沒有標(biāo)上P 標(biāo)號的，都標(biāo)標(biāo)號的，都標(biāo)T 標(biāo)號；標(biāo)號； 3、算法的每一步把某一點(diǎn)的、算法

9、的每一步把某一點(diǎn)的T標(biāo)號改變?yōu)闃?biāo)號改變?yōu)镻標(biāo)標(biāo)號，直到所有的號，直到所有的T標(biāo)號都改為標(biāo)號都改為P標(biāo)號，即得到從標(biāo)號，即得到從始點(diǎn)始點(diǎn)O到其他各點(diǎn)的最短路權(quán)，標(biāo)號過程結(jié)束。到其他各點(diǎn)的最短路權(quán)，標(biāo)號過程結(jié)束。15交通網(wǎng)絡(luò)示意圖交通網(wǎng)絡(luò)示意圖用Dijkstra法計算圖示路網(wǎng)從節(jié)點(diǎn)法計算圖示路網(wǎng)從節(jié)點(diǎn)1到節(jié)點(diǎn)到節(jié)點(diǎn)9的最短路徑。的最短路徑。7698532411222221222221616步驟步驟1 給定起點(diǎn)給定起點(diǎn)1的標(biāo)號的標(biāo)號P1=0，其他節(jié)點(diǎn)標(biāo)上了標(biāo)號：，其他節(jié)點(diǎn)標(biāo)上了標(biāo)號：T1(2)=T1(9)=步驟步驟2 修改修改2、4點(diǎn)的點(diǎn)的T標(biāo)標(biāo)號號 T2(2)=minT1(2)，P(1)+d12

10、=min,0+2=2 T2(4)=minT1(4)，P(1)+d14 =min,0+2=2 在所有的在所有的T標(biāo)號中，找出最小標(biāo)號中，找出最小標(biāo)號。標(biāo)號。2、4均為最小，任選其均為最小，任選其一，如節(jié)點(diǎn)一，如節(jié)點(diǎn)2，即，即P2=2769853241122222122222P1=0P2=2T1(3)=T1(6)=T1(7)=T1(8)=T1(9)=T2(4)=2T1(5)=17步驟步驟3 修改修改3、5點(diǎn)的點(diǎn)的T標(biāo)標(biāo)號號 T3(3)=minT(3)，P(2)+d23 =min,2+2=4 T3(5)=minT(5)，P(2)+d25 =min,2+2=4 在所有的在所有的T標(biāo)號中，找出最標(biāo)號中，

11、找出最小標(biāo)號小標(biāo)號,節(jié)點(diǎn)節(jié)點(diǎn)4為最小，即為最小，即P4=2769853241122222122222P1=0P2=2P4=2T1(6)=T1(7)=T1(8)=T1(9)=T3(5)=4T3(3)=418步驟步驟4 修改修改5、7點(diǎn)的點(diǎn)的T標(biāo)號標(biāo)號 T4(5)=minT (5)，P(4)+d45 =min,2+1=3 T4(7)=minT(7)，P(4)+d47 =min,2+2=4 在所有的在所有的T標(biāo)號中，節(jié)點(diǎn)標(biāo)號中，節(jié)點(diǎn)5為最小，即為最小，即P5=3769853241122222122222P1=0P2=2P4=2P5=3T1(6)=T4(7)=4T1(8)=T1(9)=T3(3)=41

12、9步驟步驟5 修改修改6、8點(diǎn)的點(diǎn)的T標(biāo)號標(biāo)號 T5(6)=minT (6)，P(5)+d56 =min,3+1=4 T5(8)=minT(8)，P(5)+d58 =min,3+2=5 在所有的在所有的T標(biāo)號中，節(jié)點(diǎn)標(biāo)號中，節(jié)點(diǎn)3為最小，即為最小，即P3=4769853241122222122222T4(7)=4T5(8)=5T1(9)=P4=2P5=3T1(6)=4P1=0P2=2P3=420步驟步驟6 修改修改6的的T標(biāo)號標(biāo)號 T6(6)=minT (6)，P(3)+d36 =min4,4+2=4 在所有的在所有的T標(biāo)號中，節(jié)點(diǎn)標(biāo)號中，節(jié)點(diǎn)6為最小，即為最小，即P6=47698532411

13、22222122222T4(7)=4T5(8)=5T1(9)=P4=2P5=3P6=4P1=0P2=2P3=421步驟步驟7 修改修改9的的T標(biāo)號標(biāo)號 T7(9)=minT (9)，P(6)+d69 =min,4+2=6 在所有的在所有的T標(biāo)號中，節(jié)點(diǎn)標(biāo)號中，節(jié)點(diǎn)7為最小，即為最小，即P7=4769853241122222122222P7=4T5(8)=5T7(9)=6P4=2P5=3P6=4P1=0P2=2P3=422步驟步驟8 修改修改8的的T標(biāo)號標(biāo)號 T8(8)=minT (8)，P(7)+d78 =min5,4+2=5 在所有的在所有的T標(biāo)號中，節(jié)點(diǎn)標(biāo)號中，節(jié)點(diǎn)8為最小，即為最小，即P

14、8=5769853241122222122222P7=4P8=5T7(9)=6P4=2P5=3P6=4P1=0P2=2P3=423步驟步驟9 修改修改9的的T標(biāo)號標(biāo)號 T9(9)=minT (9)，P(8)+d89 =min6,5+2=6 在所有的在所有的T標(biāo)號中，節(jié)點(diǎn)標(biāo)號中，節(jié)點(diǎn)8為最小，即為最小，即P9=6769853241122222122222P7=4P8=5P9=6P4=2P5=3P6=4P1=0P2=2P3=424Dijkstra法實際應(yīng)用分析法實際應(yīng)用分析 能夠一次算出從起點(diǎn)到其他各節(jié)點(diǎn)的最短路能夠一次算出從起點(diǎn)到其他各節(jié)點(diǎn)的最短路徑；徑； 計算效率不高，速度較慢，所需存儲空間多

15、，計算效率不高，速度較慢，所需存儲空間多，在大規(guī)模規(guī)劃中受到一定限制。在大規(guī)模規(guī)劃中受到一定限制。25第三節(jié)第三節(jié) 最小生成樹問題最小生成樹問題一、基本概念一、基本概念 （1）設(shè)無向圖）設(shè)無向圖G=（V，E），對），對G中的每條無向中的每條無向邊邊e=(vi, vj),相應(yīng)地賦予一個實數(shù)相應(yīng)地賦予一個實數(shù)W（e)= Wij， W（e） 稱為邊稱為邊e=(vi, vj)的權(quán)，圖的權(quán)，圖G=（V，E）稱為）稱為賦權(quán)無向圖；賦權(quán)無向圖； （2）設(shè)有向圖）設(shè)有向圖D=（V，E），對），對D中的每條有向邊中的每條有向邊e=(vi, vj),相應(yīng)地賦予一個實數(shù)相應(yīng)地賦予一個實數(shù)W（e)= Wij， W（e

16、） 稱為邊稱為邊e=(vi, vj)的權(quán)，圖的權(quán)，圖D=（V，E）稱為）稱為賦權(quán)有向圖；賦權(quán)有向圖； （一）賦權(quán)圖（一）賦權(quán)圖26 （1）設(shè)）設(shè)G=(V,E)是連通賦權(quán)無向圖是連通賦權(quán)無向圖,任意任意e E（G）,賦予非負(fù)權(quán)賦予非負(fù)權(quán)W(e)=Wij 0。若。若T=(V,E)是是G圖圖的一個生成樹，稱的一個生成樹，稱E中所有邊的權(quán)之和中所有邊的權(quán)之和 W（T）=為生成樹為生成樹T的權(quán)。的權(quán)。 （2）如果）如果T*為連通賦權(quán)無向圖為連通賦權(quán)無向圖G的生成樹，且的生成樹，且 W（T*）= minW(T)|T為圖為圖G的生成樹的生成樹 則稱則稱T*為圖為圖G的最小生成樹。的最小生成樹。( )e Ew

17、 e（二）最小生成樹（二）最小生成樹27二、例如要解決這類問題：二、例如要解決這類問題：由于樹的任意兩點(diǎn)之間恰有一條初等鏈連通，由于樹的任意兩點(diǎn)之間恰有一條初等鏈連通，因此問題的目標(biāo)就是在圖因此問題的目標(biāo)就是在圖G G中尋找一個最小生成樹：中尋找一個最小生成樹：（1 1）任意頂點(diǎn)之間有唯一的一條初等鏈相互連通；）任意頂點(diǎn)之間有唯一的一條初等鏈相互連通；（2 2）樹中各邊的權(quán)之和最小。）樹中各邊的權(quán)之和最小。類似的問題：煤氣管道、下水道和公路網(wǎng)的規(guī)類似的問題：煤氣管道、下水道和公路網(wǎng)的規(guī)劃與建設(shè)等。劃與建設(shè)等。 設(shè)無向圖設(shè)無向圖G=G=（V V，E E）中各個頂點(diǎn)表示某區(qū)所屬）中各個頂點(diǎn)表示某區(qū)

18、所屬1010個街道的位置，邊的權(quán)表示兩個街道之間的距離。個街道的位置，邊的權(quán)表示兩個街道之間的距離?，F(xiàn)在計劃建設(shè)連通各個街道的電話網(wǎng)。問如何規(guī)劃現(xiàn)在計劃建設(shè)連通各個街道的電話網(wǎng)。問如何規(guī)劃電話網(wǎng)，既保證任意街道之間可以通話，又使總的電話網(wǎng)，既保證任意街道之間可以通話，又使總的電話線路里程最短？電話線路里程最短？28三、最小生成樹算法三、最小生成樹算法（一）丟邊法（破圈法）（一）丟邊法（破圈法） 1、 在連通的無向圖中，任取一個圈；在連通的無向圖中，任取一個圈； 2、將該圈中權(quán)最大的一條邊去掉；、將該圈中權(quán)最大的一條邊去掉； 3、在余下的圈中重復(fù)這一步驟，直到不含圈為止，、在余下的圈中重復(fù)這一步

19、驟，直到不含圈為止，得到最小樹。得到最小樹。P202 例例6-229v10v1v9v2v3v1v4v5v8v7v63524530v1v9v2v3v1v4v5v8v7v63231v1v9v2v3v1v4v5v8v7v632最小樹（）最小樹（）32v1v9v2v3v1v4v5v8v7v632最小樹（）最小樹（）33（二）加邊法（避圈法）（二）加邊法（避圈法） 對含有對含有n n個點(diǎn)的連通無向圖個點(diǎn)的連通無向圖G G 1 1、從所有邊中選出一條權(quán)最小的邊，并把它納入、從所有邊中選出一條權(quán)最小的邊，并把它納入樹中；樹中； 2 2、在余下的未選邊中，再選出一條權(quán)最小且與已、在余下的未選邊中，再選出一條權(quán)

20、最小且與已選入樹中的邊不構(gòu)成圈的邊，將其納入樹中；選入樹中的邊不構(gòu)成圈的邊，將其納入樹中； 3 3、重復(fù)、重復(fù)2 2，直到樹中含有，直到樹中含有n-n-1 1條邊為止，即構(gòu)成了條邊為止，即構(gòu)成了最小樹。最小樹。 P203 例例6-334V2V7V4V6V5V3V132463746515335V2V7V4V6V5V3V1324341第四節(jié)第四節(jié) 最大流問題最大流問題36問題的提出問題的提出引例：引例： 某大宗物資有某大宗物資有2 2個發(fā)點(diǎn)個發(fā)點(diǎn)A A1 1和和A A2 2，供應(yīng)量分別為，供應(yīng)量分別為120120（t t）和）和240240（t t），有），有2 2個收點(diǎn)個收點(diǎn)B B1 1和和B

21、B2 2，需求量，需求量分別為分別為180180（t t）和）和200200（t t），運(yùn)輸線路如下圖，其），運(yùn)輸線路如下圖，其中中F F1 1，F(xiàn) F2 2，F(xiàn) F3 3為轉(zhuǎn)運(yùn)點(diǎn)，邊旁數(shù)字為該線路允許該為轉(zhuǎn)運(yùn)點(diǎn)，邊旁數(shù)字為該線路允許該物資運(yùn)輸?shù)淖畲罅?。物資運(yùn)輸?shù)淖畲罅俊 A2 2A A1 1F F1 1B B1 1F F3 3B B2 2F F2 2130130150150707070705050100100120120404037問題問題1 1：如何制定運(yùn)輸方案，可以從：如何制定運(yùn)輸方案，可以從A A1 1和和A A2 2，運(yùn)輸最多運(yùn)輸最多 的物資至的物資至收點(diǎn)收點(diǎn)B B1 1和和B B

22、2 2？問題問題2 2：若每噸物資從點(diǎn)：若每噸物資從點(diǎn)V Vi i，經(jīng)邊（，經(jīng)邊（V Vi i，V Vj j）運(yùn)輸至）運(yùn)輸至V Vj j，發(fā)生的費(fèi)用為發(fā)生的費(fèi)用為W Wijij，如何制定運(yùn)輸方案，以最小的如何制定運(yùn)輸方案，以最小的 運(yùn)輸費(fèi)用，從運(yùn)輸費(fèi)用，從A A1 1和和A A2 2運(yùn)輸最多物資至運(yùn)輸最多物資至B B1 1和和B B2 2？A A2 2A A1 1F F1 1B B1 1F F3 3B B2 2F F2 21301301501507070707050501001001201204040源源匯匯7070707013013015015050504040150150120120100

23、100 x x1 1x x2 2y y1 1y y2 2v v1 1v v2 2v v3 3中間點(diǎn)中間點(diǎn)+120+120+240+240-180-180-200-20038問題問題1 1：求源：求源X=X=（x x1 1，x x2 2）到匯）到匯Y=Y=（y y1 1，y y2 2） 的一個的一個最大流；最大流；問題問題2 2：求源：求源X=X=（x x1 1，x x2 2）到匯）到匯Y=Y=（y y1 1，y y2 2） 的一個的一個最小費(fèi)用最大流；最小費(fèi)用最大流；源源匯匯7070707013013015015050504040150150120120100100 x x1 1x x2 2y

24、 y1 1y y2 2v v1 1v v2 2v v3 3中間點(diǎn)中間點(diǎn)+120+120+240+240-180-180-200-20039一、一、 基本概念基本概念（一）運(yùn)輸網(wǎng)絡(luò)（一）運(yùn)輸網(wǎng)絡(luò) 設(shè)有向圖設(shè)有向圖D=D=（V V，A A），對任意?。?，對任意弧a a A A，有相應(yīng)的，有相應(yīng)的非負(fù)權(quán)非負(fù)權(quán)C C（a a）=0=0，稱為，稱為弧弧a a的容量的容量，且，且 X X，Y Y，滿足：滿足：X X，Y Y V V和和X X Y= Y=，則稱，則稱 D=D=（V,A,C,X,YV,A,C,X,Y）為為運(yùn)輸網(wǎng)絡(luò)運(yùn)輸網(wǎng)絡(luò)。707070701301301501505050404015015012

25、0120100100 x x1 1x x2 2y y1 1y y2 2v v1 1v v2 2v v3 340（二）相關(guān)概念（二）相關(guān)概念（1 1）C C（a a）：）： 弧弧a a的容量；的容量；（2 2） x x X X ：網(wǎng)絡(luò)網(wǎng)絡(luò)D D的源；的源；（3 3） y y Y Y ：網(wǎng)絡(luò)網(wǎng)絡(luò)D D的匯；的匯；（4 4） V Vi i I=V-I=V-（X X Y Y）：）：網(wǎng)絡(luò)網(wǎng)絡(luò)D D的中間點(diǎn)；的中間點(diǎn)；源源匯匯7070707013013015015050504040150150120120100100 x x1 1x x2 2y y1 1y y2 2v v1 1v v2 2v v3 3中間

26、點(diǎn)中間點(diǎn)41（三）單源單匯運(yùn)輸網(wǎng)絡(luò)（三）單源單匯運(yùn)輸網(wǎng)絡(luò)7070707013013015015050504040150150120120100100 x x1 1x x2 2y y1 1y y2 2v v1 1v v2 2v v3 3+120+120+240+240-180-180-200-200v v1 17070707013013015015050504040150150120120100100 x x1 1x x2 2y y1 1y y2 2v v2 2v v3 3x x120120240240y y18018020020042（四）零流、最大流、最小費(fèi)用最大流（四）零流、最大流、最小費(fèi)

27、用最大流 （1）零流零流f0： 任意（任意（vi,vj） A, f（vi,vj）=0；（2） 最大流最大流f*： Val f*=MaxValf|f為為D中網(wǎng)絡(luò)流中網(wǎng)絡(luò)流（3） 最小費(fèi)用最大流最小費(fèi)用最大流f*w： 設(shè)設(shè)W(vi,vj)為弧為弧(vi,vj)上單位流量所需的上單位流量所需的 費(fèi)用費(fèi)用,W(f)= f(vi,vj)* W(vi,vj)|(vi,vj) A,稱為網(wǎng)絡(luò)流稱為網(wǎng)絡(luò)流f的總費(fèi)用；的總費(fèi)用； 最小費(fèi)用最大流最小費(fèi)用最大流f*w ： W(f*w)=Min W(f*)|f*為為D中最大流中最大流 43( (五五) )最大流與最小割最大流與最小割(1)(1)割的概念割的概念 對于網(wǎng)

28、絡(luò)對于網(wǎng)絡(luò)D=(V,A,C,x,y),D=(V,A,C,x,y),若若S S V,SV,S=V-S,=V-S,而且而且x x S,yS,y S S, ,則則 K=(S,SK=(S,S) )表示表示D D中起點(diǎn)在中起點(diǎn)在S,S,終點(diǎn)在終點(diǎn)在S S的的全體弧的集合全體弧的集合: K=S,S: K=S,S=(u,v)|u=(u,v)|u S,vS,v S S ；一般；一般, ,稱稱K K為網(wǎng)絡(luò)為網(wǎng)絡(luò)D D的一個的一個割割,CapK=,CapK= C(a)|aC(a)|a K K為為割的容量。割的容量。(2)(2)最小割最小割K K* *指網(wǎng)絡(luò)指網(wǎng)絡(luò)D D中容量最小的割，即中容量最小的割，即 CapK

29、CapK* *=MinCapK|K=MinCapK|K為網(wǎng)絡(luò)為網(wǎng)絡(luò)D D的割的割 （3,33,3）（5,35,3）（2,12,1）X XY YV V1 1V V2 2V V3 3V V4 4（5,15,1）（1,11,1）（1,11,1）（4,34,3）（3,03,0）（2,22,2）P20544v1v3v5v2v4231523445（六）增流鏈與可行鏈的調(diào)整（六）增流鏈與可行鏈的調(diào)整設(shè)設(shè)f f為網(wǎng)絡(luò)為網(wǎng)絡(luò)D D上一個流，對任意上一個流，對任意a a A A，若，若f(a)=C(a),f(a)=C(a),稱稱a a為為飽和弧飽和弧; ;若若f(a)C(a),f(a)0,f(a)0,稱稱a a為

30、為非零流弧非零流弧。設(shè)設(shè)Q=xQ=xuvuvt t為網(wǎng)絡(luò)為網(wǎng)絡(luò)D D中由中由x x至至t t的一條初等鏈，的一條初等鏈，若若 (u,v)(u,v) A,A,稱稱(u,v)(u,v)為為Q Q的的前向弧前向弧; ;若若 (v,u)(v,u) A,A,稱稱(v,u)(v,u)為為Q Q的的后向弧后向弧;Q(u;Q(u+ +) )為為Q Q的的前向弧的集合前向弧的集合;Q(u;Q(u- -) )為為Q Q的的后向弧的集合后向弧的集合。X XY YV V1 1V V2 2V V3 3V V4 410108 84 45 53 35 56 63 311111717（3 3）（5 5）（1 1）（1 1）（

31、2 2）（2 2）（6 6）（3 3）（2 2）（3 3）（1 1）飽和弧和零?。╋柡突『土慊?6設(shè)設(shè)f f為網(wǎng)絡(luò)為網(wǎng)絡(luò)D D上一個流，上一個流，Q=xQ=xuvuvt t為網(wǎng)絡(luò)為網(wǎng)絡(luò)D D中中由由x x至至t t的一條初等鏈，如果滿足以下條件：的一條初等鏈，如果滿足以下條件： 0=f(a)C(a),a0=f(a)C(a),a Q(uQ(u+ +) )；0f(a)=C(a),a0f(a)=C(a),a Q(uQ(u- -) )則稱則稱Q Q為為不飽和鏈不飽和鏈, ,否則稱為否則稱為飽和鏈飽和鏈; ;設(shè)設(shè)Q=xQ=xuvuvt t為為D D中由中由x x至至t t的一條初等鏈，則稱的一條初等鏈，

32、則稱 l(Q)=Minminl(Q)=Minmin（C(a)-f(a)C(a)-f(a)）; min; min f(a) f(a) a a Q(uQ(u+ +) ) a a Q(uQ(u- -) )為鏈為鏈Q(jìng) Q的的不飽和量不飽和量。X XY YV V1 1V V2 2V V3 3V V4 410108 84 45 53 35 56 63 311111717（3 3）（5 5）（1 1）（1 1）（2 2）（2 2）（6 6）（3 3）（2 2）（3 3）47（2 2）增流鏈與調(diào)整流）增流鏈與調(diào)整流若從源若從源x x至匯至匯y y的鏈的鏈Q(jìng)=xQ=xuvuvy y為不飽和鏈，為不飽和鏈，則稱則

33、稱Q Q為網(wǎng)絡(luò)為網(wǎng)絡(luò)D D關(guān)于流關(guān)于流f f的的增流鏈，記為增流鏈，記為Q Qy y。設(shè)設(shè)Q Qy y為網(wǎng)絡(luò)為網(wǎng)絡(luò)D D關(guān)于流關(guān)于流f f的一條增流鏈的一條增流鏈, ,對流對流f f作如下作如下調(diào)整后調(diào)整后, ,可得調(diào)整流可得調(diào)整流f f, ,且且ValfValf=Valf+l(Q)=Valf+l(Q) f f(a) =f(a)+l(Q)|a(a) =f(a)+l(Q)|a Q(uQ(u+ +); ); f f(a)=(a)= f(a)-l(Q)|af(a)-l(Q)|a Q(uQ(u- -);); f f(a)=f(a)|a(a)=f(a)|a A(A(Q).Q).X XY YV V1 1V

34、 V2 2V V3 3V V4 410108 84 45 53 35 56 63 311111717（3 3）（5 5）（1 1）（1 1）（2 2）（2 2）（6 6）（3 3）（2 2）（3 3）48（2 2）基本思想）基本思想迭代尋優(yōu)法迭代尋優(yōu)法二、最大流算法思想二、最大流算法思想流流f f為網(wǎng)絡(luò)為網(wǎng)絡(luò)D D的最大流的充要條件：的最大流的充要條件： D D中不存在關(guān)于中不存在關(guān)于f f的增流鏈的增流鏈Q(jìng)yQy（1 1）基本定理）基本定理第第1 1步：尋找初始流（步：尋找初始流（f f）；）； 第第2 2步：步：判斷判斷D D中有無基于中有無基于f f的增流鏈的增流鏈Q(jìng)yQy；第第3 3步

35、：若步：若QyQy不存在，則不存在，則f f為最大流；否則，為最大流；否則， 可得可得f f基于基于QyQy的調(diào)整流的調(diào)整流f f, , ValfValf=Valf+l(Qy)=Valf+l(Qy)；第第4 4步：令步：令f f=f=f，轉(zhuǎn)（，轉(zhuǎn)（2 2）；）；P206 例例6-4第五節(jié)第五節(jié) 網(wǎng)絡(luò)計劃技術(shù)網(wǎng)絡(luò)計劃技術(shù)49一、網(wǎng)絡(luò)圖一、網(wǎng)絡(luò)圖ij事項事項 i事項事項 j工作工作At (i, j)二、二、 網(wǎng)絡(luò)圖的繪制網(wǎng)絡(luò)圖的繪制50系統(tǒng)的工作（工序）有哪些系統(tǒng)的工作（工序）有哪些工作與工作之間的關(guān)系工作與工作之間的關(guān)系完成每項工作的時間完成每項工作的時間 網(wǎng)絡(luò)圖的繪制分為三個步驟：網(wǎng)絡(luò)圖的繪制

36、分為三個步驟： 1 1、任務(wù)的分解、任務(wù)的分解 2 2、作圖、作圖 3 3、編號、編號 511 1、任務(wù)的分解、任務(wù)的分解 （1）將任務(wù)分解為工作將任務(wù)分解為工作 按分解的粗細(xì)，網(wǎng)絡(luò)圖可分為：按分解的粗細(xì)，網(wǎng)絡(luò)圖可分為：總網(wǎng)絡(luò)圖總網(wǎng)絡(luò)圖分網(wǎng)絡(luò)圖分網(wǎng)絡(luò)圖 基層網(wǎng)絡(luò)圖基層網(wǎng)絡(luò)圖52（2） 確定各個工作之間相互聯(lián)系和相互制約的關(guān)系確定各個工作之間相互聯(lián)系和相互制約的關(guān)系 緊前工作緊前工作 緊后工作緊后工作 平行工作平行工作53（3） 估計完成每個工作所需要的時間估計完成每個工作所需要的時間 te 估計作業(yè)時間有兩種方法：估計作業(yè)時間有兩種方法：一點(diǎn)估計法一點(diǎn)估計法三點(diǎn)估計法三點(diǎn)估計法64平均作 業(yè)均

37、作bmate54（4） 將分解結(jié)果匯總列表將分解結(jié)果匯總列表2 2、作圖、作圖（1 1） 網(wǎng)絡(luò)圖是網(wǎng)絡(luò)圖是有向的有向的55ABCABC從左向右，不循環(huán)從左向右，不循環(huán)56（2 2） 一個一個網(wǎng)絡(luò)圖只能有網(wǎng)絡(luò)圖只能有一個一個總開始事項和總開始事項和一個一個總總結(jié)束事項結(jié)束事項ADBC（3） 要合理運(yùn)用要合理運(yùn)用虛工作虛工作57ABCDE58CABFEGD3 3、編號、編號59編號規(guī)則如下：編號規(guī)則如下：（1） 每個事項均有一個編號，不能重復(fù)；每個事項均有一個編號，不能重復(fù)；（2）編號順序是自左向右，逐列編號，每列自）編號順序是自左向右，逐列編號，每列自上而下或自下而上；上而下或自下而上；（3）

38、一個工作的兩個相關(guān)事項，一般要求箭尾一個工作的兩個相關(guān)事項，一般要求箭尾事項的編號小于箭頭事項的編號。事項的編號小于箭頭事項的編號。三、三、 網(wǎng)絡(luò)圖時間參數(shù)的計算網(wǎng)絡(luò)圖時間參數(shù)的計算60計算的內(nèi)容計算的內(nèi)容t事項時間參數(shù)的計算事項時間參數(shù)的計算t工作時間參數(shù)的計算工作時間參數(shù)的計算t線路時間參數(shù)的計算線路時間參數(shù)的計算計算的方法計算的方法t公式計算法公式計算法t圖上計算法圖上計算法t表格計算法表格計算法（一）事項時間參數(shù)的計算（一）事項時間參數(shù)的計算1. 事項的最早開始時間事項的最早開始時間即：從始點(diǎn)起到此事項的最長路線的時間和。即：從始點(diǎn)起到此事項的最長路線的時間和。計算順序：計算順序：從始

39、點(diǎn)開始，自左至右，逐個計算，從始點(diǎn)開始，自左至右，逐個計算，直至終點(diǎn)。直至終點(diǎn)。計算公式：計算公式：),()()()(jititmaxjt01tEjiEE) j (tE612. 事項的最遲結(jié)束時間事項的最遲結(jié)束時間即：在這個時間里該事項必須完成，若不能完即：在這個時間里該事項必須完成，若不能完成，就要影響緊后各項工作按時開始。成，就要影響緊后各項工作按時開始。計算順序：計算順序：從終點(diǎn)開始，自右向左，逐個計算，從終點(diǎn)開始，自右向左，逐個計算，直至始點(diǎn)。直至始點(diǎn)。計算公式：計算公式：) j , i ( t) j (tmin) i (t)n(t)n(tLLEL) i (tL623. 事項的時差事項的時差即：事項最遲結(jié)束時間即：事項最遲結(jié)束時間 和最早開始時間和最早開始時間 之差。之差。計算順序：自左至右，或自右至左。計算順序：自左至右，或自右至左。計算公式：計算公式：j)(t) j (t) j (Si)(t) i (t) i (SELEL) j (S) i (S或63) i (tL) j (tE（二）工作時間參數(shù)的計算（二）工作時間參數(shù)的計算1