1、運(yùn) 籌 學(xué)“運(yùn)籌學(xué)”課題組6.7 習(xí) 題本章內(nèi)容重點(diǎn) 6.1 圖與網(wǎng)絡(luò)6.2 樹(shù)6.3 最短路問(wèn)題6.4 網(wǎng)絡(luò)最大流問(wèn)題6.5 最小費(fèi)用最大流6.6 案例：網(wǎng)絡(luò)的中心與選址問(wèn)題第六章 網(wǎng)絡(luò)規(guī)劃與網(wǎng)絡(luò)分析概 述圖論是目前運(yùn)用十分廣泛的運(yùn)籌學(xué)分支之一；自1736年著名數(shù)學(xué)家歐拉(Euler)解決了有名的哥尼斯堡七橋問(wèn)題以來(lái)，圖論取得了十分迅速的發(fā)展； 已廣泛應(yīng)用于計(jì)算機(jī)、信息論、經(jīng)濟(jì)科學(xué)等各領(lǐng)域，用以解決各種各樣的決策問(wèn)題。 概 述生活中的許多問(wèn)題都可以運(yùn)用圖論的理論與方法來(lái)解決。例如： 在生產(chǎn)的組織與管理中，為了完成某項(xiàng)生產(chǎn)任務(wù)，各工序之間如何銜接，才能使任務(wù)完成得既快又好？在城市水、電、煤氣供

2、應(yīng)問(wèn)題中，管道與供電線路如何鋪設(shè)，才能做到既滿足要求，又使總費(fèi)用最省？6.1 圖與網(wǎng)絡(luò)自然界和人類社會(huì)中許多事物以及事物之間的關(guān)系，都可以用點(diǎn)和線連接起來(lái)的圖形來(lái)描述。例如用點(diǎn)表示城市，點(diǎn)間聯(lián)線表示城市間的道路，就可描述城市間的交通，哥爾斯保七橋問(wèn)題：哥爾斯保城有一條普雷爾河，該河上有兩個(gè)小島，河上有七座橋?qū)⑦@兩個(gè)小島及島與河岸之間連接起來(lái)。 概 述 問(wèn)題是要從A,B,C,D這四塊陸地中的任何一塊開(kāi)始，通過(guò)所有的橋一次且僅一次，最后回到開(kāi)始出發(fā)的這塊陸地。如果聯(lián)線旁標(biāo)注城市間的距離網(wǎng)絡(luò)圖中稱為權(quán)，形成加權(quán)圖，就稱為網(wǎng)絡(luò)圖，就可進(jìn)一步研究從一個(gè)城市到另一個(gè)城市的最短路徑；或者標(biāo)上單位運(yùn)價(jià)，就可分

3、析運(yùn)費(fèi)最小的運(yùn)輸方案。例6-1圖a表示5個(gè)球隊(duì)之間的賽事關(guān)系。其中點(diǎn) a, b, c, d, e, f 分別表示5個(gè)球隊(duì)，兩點(diǎn)的連接表示兩球隊(duì)之間的賽事關(guān)系。 aedbc從圖中可反映出a球隊(duì)分別與b，c，d 球隊(duì)有賽事；球隊(duì)還與c球隊(duì)，d球隊(duì)還與e球隊(duì)有賽事。圖a 這5個(gè)球隊(duì)之間的關(guān)系也可用圖b)來(lái)反映。圖a)與b)沒(méi)有本質(zhì)的差異 可見(jiàn)表示球隊(duì)間有無(wú)賽事關(guān)系是兩點(diǎn)間的連線，而圖中點(diǎn)的相對(duì)位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長(zhǎng)短曲直，對(duì)反映對(duì)象之間的關(guān)系并不重要。eabdc圖b例 6-2 圖 6-2 是一張管道運(yùn)輸網(wǎng)示意圖，代表7個(gè)城市間物資運(yùn)輸關(guān)系，v1,v2,v3,v4,v5,v6,v7表示7個(gè)城市，

4、箭線旁數(shù)字表示物流的最大容量。現(xiàn)在要求出從v1地到v7地的運(yùn)送的最大流方案。圖 6-2 是由點(diǎn)及帶箭頭的連線所組成的圖形。為區(qū)別起見(jiàn)，把兩點(diǎn)間不帶箭頭的連線稱為邊，帶箭頭的連線稱為弧。 用圖來(lái)描述事物間的聯(lián)系，不僅直觀清晰，且網(wǎng)絡(luò)圖的畫法簡(jiǎn)便，不必拘泥于比例和曲直。這里所講的圖是反映對(duì)象之間關(guān)系的一種工具。電路網(wǎng)絡(luò)、城市規(guī)劃、信息傳遞、物質(zhì)結(jié)構(gòu)、物資調(diào)配等也都可以用點(diǎn)和線連接起來(lái)的圖進(jìn)行模擬。 定義6-1 無(wú)向圖是一個(gè)有序二元組（V，E），記為G=（V,E），其中V=(v1， v2，vp)是p個(gè)點(diǎn)的集合，簡(jiǎn)稱定點(diǎn)集； E=（e1， e2，eq）是條邊的集合，簡(jiǎn)稱邊集合，并且是一個(gè)無(wú)序二元組。記

5、為（1）無(wú)向圖由點(diǎn)和邊組成的圖稱為無(wú)向圖，如圖 6-1。圖 6-3即為無(wú)向圖，圖中：頂點(diǎn)數(shù)：點(diǎn)集V中元素的個(gè)數(shù)稱為圖G的頂點(diǎn)數(shù)，記為 。如圖 6-3，邊數(shù) ：邊集 E中元素的個(gè)數(shù)，記為如圖 6-3，端點(diǎn)：對(duì)于邊，e為vi , vj的關(guān)聯(lián)邊。圖 6-3 中， 為 的端點(diǎn)， 為 的關(guān)聯(lián)邊。稱vi，vj為e的端點(diǎn)。若點(diǎn)vi , vj有邊相連，即則稱vi ,vj 相鄰， vi ,vj 與e關(guān)聯(lián)。如圖6.3 中， v3,v5相鄰， v3,v5與e7關(guān)聯(lián)。圖6.3（2）簡(jiǎn)單圖環(huán)（自回路）：一條邊的兩個(gè)端點(diǎn)如果相同，稱此邊為環(huán)。如圖6-3中的e1。多重邊 ：兩個(gè)點(diǎn)之間多于一條邊的，如圖6-3中的e4， e5

6、.不含環(huán)和多重邊的圖稱為簡(jiǎn)單圖，含有多重邊的圖稱為多重圖。(3) 點(diǎn)的次（度）以點(diǎn)v為端點(diǎn)的邊數(shù)叫做點(diǎn)v的次，記作d(v)。如圖6-3中，d(v1)=4，d(v2)=4。 若，則稱稱為圖G的次序列。 次為 1 的點(diǎn)稱為懸掛點(diǎn)，連接懸掛點(diǎn)的邊稱為懸掛邊。次為 0的點(diǎn)稱為孤立點(diǎn)。次為奇數(shù)的點(diǎn)稱為奇點(diǎn)，次為偶數(shù)的點(diǎn)稱為偶點(diǎn)。定理 6-1 任何圖G =（V,E）中，所有點(diǎn)的次數(shù)之和等于邊數(shù)的2倍。即證：由于每條邊必有兩個(gè)頂點(diǎn)關(guān)聯(lián)，在計(jì)算點(diǎn)的次時(shí)，每條邊均被計(jì)算了兩次，所以頂點(diǎn)次數(shù)之和等于邊數(shù)的2倍。定理 6-2 任何圖G =（V,E）中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。證：設(shè)圖G中奇點(diǎn)與偶點(diǎn)的集合分別為V1和V2

7、， 由定理 6-1 知由于2q(G)為偶數(shù)，而 是若干個(gè)偶數(shù)之和，也為偶數(shù)。所以 必為偶數(shù)，即奇點(diǎn)的個(gè)數(shù) 必為偶數(shù)。（4）鏈鏈：對(duì)于無(wú)向圖G =（V,E）, 稱頂點(diǎn)和邊交替的序列 為連接 的一條鏈，簡(jiǎn)記為 其中 ,稱 為鏈的兩個(gè)端點(diǎn)。圖6-3 中的都是鏈。兩個(gè)端點(diǎn)重合的鏈，稱為圈。在一個(gè)圖中，如果任何兩個(gè)頂點(diǎn)之間都有一條鏈，該圖稱為連通圖。有向圖是一個(gè)有序二元組（V,A），記為D（V,A），其中 是p個(gè)頂點(diǎn)的集合，是q條弧的集合，并且 是一個(gè)有序二元組，記為 并稱 是以vi為始點(diǎn)， vj為終點(diǎn)的弧，i，j的順序不能顛倒，圖中弧的方向用箭頭標(biāo)識(shí)。由點(diǎn)和弧組成的圖稱為有向圖，如圖6-4。圖中：二、

8、有向圖 （1）有向圖 （2）簡(jiǎn)單有向圖兩個(gè)端點(diǎn)重合的弧稱環(huán)。如圖 6-4 中的a1 .圖6-4兩個(gè)端點(diǎn)之間的同向弧數(shù)大于等于2，稱為多重弧。無(wú)環(huán)也無(wú)多重弧的有向圖稱為簡(jiǎn)單有向圖。 （3）點(diǎn)的出次和入次以點(diǎn)v為起點(diǎn)的弧數(shù)叫做點(diǎn)v的出次，記作以點(diǎn)v為終點(diǎn)的弧數(shù)叫做點(diǎn)v的入次，記作稱 為點(diǎn)v的次。 （4）路在有向圖D=(V,A)中，點(diǎn)和弧交替的序列，若有或，則稱P是一條鏈接的有向路 實(shí)際問(wèn)題中，如果在圖中賦予邊一定的數(shù)量指標(biāo)，我們常稱之為“權(quán)”。通常把這種賦權(quán)圖稱為網(wǎng)絡(luò)。 與無(wú)向圖和有向圖相對(duì)應(yīng)，網(wǎng)絡(luò)又分為無(wú)向網(wǎng)絡(luò)和有向網(wǎng)絡(luò)。 三、網(wǎng)絡(luò) 圖的矩陣表示方法：關(guān)聯(lián)矩陣：在圖G=(V,E) 中，V=（v1

9、,v2,vp), E=(e1,e2 ,eq)，見(jiàn)圖6.5,構(gòu)造一個(gè)矩陣 其中圖6.5則稱A為G的關(guān)聯(lián)矩陣。關(guān)聯(lián)指頂點(diǎn)與邊的關(guān)系。圖6.5的關(guān)聯(lián)矩陣鄰接矩陣：在圖G=(V,E) 中，V=（v1,v2,vp), E=(e1,e2 ,eq),見(jiàn)圖6.6構(gòu)造一個(gè)矩陣 其中圖6.6則稱A為G的鄰接矩陣。鄰接指頂點(diǎn)與頂點(diǎn)的關(guān)系。圖6.6的鄰接矩陣權(quán)矩陣 ：在圖G=(V,E) 中，V=(v1,v2,vp),E=(e1,e2 ,eq),其邊vi,vj有權(quán)wij。見(jiàn)圖6.7構(gòu)造一個(gè)矩陣 其中圖6.7則稱A為G的權(quán)矩陣。圖6.7的權(quán)矩陣6.2 樹(shù)樹(shù)是圖論中結(jié)構(gòu)最簡(jiǎn)單但又十分重要的圖，在自然科學(xué)和社會(huì)科學(xué)的許多領(lǐng)域

10、都有廣泛的應(yīng)用。a）b）實(shí)例：已知有 5個(gè)城市，要在它們之間架設(shè)電話線網(wǎng)，要求任何兩個(gè)城市都可以彼此通話（允許通過(guò)其他城市），并且電話線的條數(shù)最少。 用點(diǎn) 分別表示 5個(gè)城市。如果在v1與v5，v1與v2，v3與v4之間各架一條電話線，這個(gè)方案可用圖6.7（a）表示出來(lái)。這個(gè)方案顯然是不滿足要求的，因?yàn)樵谶@樣的電話線網(wǎng)中， v3，v4與v1 ，v2， v5之間就不能通話。圖6.7（a）如果按照?qǐng)D 6.7（b）來(lái)設(shè)計(jì)電話網(wǎng)，雖然方案能滿足不同城市之間通話的要求，但卻不能保證電話線的條數(shù)最少。原因是圖 中含有一個(gè)圈， 如果從這個(gè)圈上，任意去掉一條，并不影響電話網(wǎng)的連通性，同時(shí)又可節(jié)省一條線。因此，

11、滿足要求的電話網(wǎng)必須是：連通的；不含圈的。滿足這兩點(diǎn)要求的圖稱為“樹(shù)”。圖 6.7（b）6.2.1 樹(shù)的基本概念與性質(zhì)定義 ：連通且不含圈的無(wú)向圖稱為樹(shù)。樹(shù)中次為1的頂點(diǎn)稱為樹(shù)葉(懸掛點(diǎn))，次大于 1的頂點(diǎn)稱為分枝點(diǎn)。樹(shù)的性質(zhì)可用下面定理給出： 設(shè)有圖G=(V,E) ，n和m分別為圖G的頂點(diǎn)數(shù)和邊數(shù)，則下列命題是等價(jià)的：（1） G是一個(gè)樹(shù)。（2） G無(wú)圈，且m=n-1 。（3） G連通，且m=n-1 。（4） G無(wú)圈，但每加一條新邊即存在唯一一個(gè)圈。（5） G 連通，但每舍去一條邊就變成不連通。（6） G中任意兩點(diǎn)，有唯一路相連。定義6-7 圖G=(V,E)，若E是E的子集，V是V的子集，且E

12、中的邊僅與V中的頂點(diǎn)相關(guān)聯(lián)，則稱G=(V,E)是G的一個(gè)子圖。特別的，若V=V，則G稱為G的生成子圖（或支撐子圖）定義6-8 若圖G的生成子圖是一棵樹(shù)，則稱該樹(shù)為G的生成樹(shù)，或簡(jiǎn)稱為圖G的樹(shù)。G中屬于生成樹(shù)的邊稱為樹(shù)枝，不在生成樹(shù)中的邊稱為弦。定理 6-4 圖G=(V,E)有生成樹(shù)的充分必要條件為 G是連通圖 。證明：必要性由定義直接可得。充分性的證明過(guò)程如下： 設(shè)圖G是連通的。若G不含圈，則 G就是其自身的一棵生成樹(shù)； 若G含有圈，任取一個(gè)圈，從圈中任意去掉一條邊，得到圖G的一個(gè)生成子圖G1。 如果G1不含圈，那么G1是G的一棵生成樹(shù)； 如果G1仍含有圈，那么從G1中任取一個(gè)圈，從圈中再任意

13、去掉一條邊，得到圖 G的一個(gè)生成子圖G2。 重復(fù)使用此法使每個(gè)圈都受到破壞，最后可以得到G的一個(gè)生成子圖Gk，它是不含圈的生成子圖。 這就是G一棵生成樹(shù)。 上述充分性的證明給出了求生成樹(shù)的一種方法。就是任取一個(gè)圈，從圈中去掉一邊，對(duì)余下的圖重復(fù)這個(gè)步驟，直到不含圈時(shí)為止，即得到一棵生成樹(shù)，稱這種方法為“破圈法”。除“破圈法”外，還有另一種方法可稱為“ 避圈法”。這種方法是在圖 G中，每步選取一條邊使它與已選邊不構(gòu)成圈，直到選夠n-1條邊為止。 6.2.2 最小支撐樹(shù)及其算法（1）構(gòu)造支撐樹(shù)的算法1) 破圈法 破圈法思路：將連通有圈圖逐步刪除邊，變成連通無(wú)圈圖。破圈法步驟： G=(V,E)為連通

14、圖，Gk=(V,Ek)是G的支 撐子圖。 步驟1 開(kāi)始取G0=(V,E)=G，k=0 步驟2 若Gk不含圈，則Gk為支撐樹(shù)；若Gk含圈，取Gk中的任一圈，去掉圈上任一條邊，得Gk+1=(V，Ek+1)， Ek+1=Ekek; 步驟3 若kq(G)-p(G)+1,則重復(fù)步驟 2；否則， Gk+1一定是支撐樹(shù)。 2）避圈法 避圈法思路：將不連通的無(wú)圈圖通過(guò)邊的增加，逐步變成連 通無(wú)圈圖。 避圈法步驟： 為連通圖。步驟1 始取 ；步驟 2 若Gk 連通，則Gk為支撐樹(shù)；若Gk不連通，任選圖G邊集E中的一邊e，使e的兩個(gè)端點(diǎn)分屬兩個(gè)不同的連通分圖，得， ；步驟 3 若 ，則重復(fù)步驟 2；否則，Gk一定

15、是支撐樹(shù)。 支撐樹(shù)的構(gòu)造不涉及邊的權(quán)。將支撐樹(shù)的構(gòu)造與邊權(quán)的選擇結(jié)合，產(chǎn)生最小樹(shù)的概念。最小支撐樹(shù)是網(wǎng)絡(luò)優(yōu)化中一個(gè)重要的概念，它在交通網(wǎng)、電話網(wǎng)、管道網(wǎng)、電力網(wǎng)等設(shè)計(jì)中均有廣泛的應(yīng)用。 （2）最小支撐樹(shù)定義設(shè)有一個(gè)連通圖G=(V,E),每一邊e=vi,vj有一個(gè)權(quán)w(e)=wij，如果是的一個(gè)支撐樹(shù)，稱中所有邊的權(quán)之和為支撐樹(shù)的權(quán)，記為：如果支撐樹(shù)T*的權(quán)W(T*)是G的所有支撐樹(shù)中權(quán)數(shù)最小的，則稱T*是G的最小支撐樹(shù)（也稱最小樹(shù)），即（3）尋找最小支撐樹(shù)的算法 尋找最小支撐樹(shù)也可以用上面介紹的破圈法和避圈法，但要在舍邊和增邊時(shí)，增加一些邊的權(quán)數(shù)的限制。1）破圈法 步驟：從圖G中任取一圈，去掉

16、這個(gè)圈中權(quán)數(shù)最大的一條邊，得一支撐子圖G1。在G1中再任取一圈，再去掉圈中權(quán)數(shù)最大的一條邊，得G2 。如此繼續(xù)下去，一直到剩下的子圖中不再含圈為止。該子圖G1就是的最小支撐樹(shù)T* 。 2）Kruskal算法（避圈法） Kruskal算法是Kruskal于1956年提出的一個(gè)產(chǎn)生最小樹(shù)的算法 算法的基本思想是：每次將一條權(quán)最小的弧加入子圖T 中，并保證不形成圈。即按照邊長(zhǎng)由小到大排序，如果當(dāng)前弧加入后不形成圈，則加入這條弧。當(dāng)弧有 時(shí)，即為最小樹(shù)。 步驟0 按照權(quán)的大小對(duì)邊由小到大排序，即 令 步驟1 判斷 是否含圈。如含圈，轉(zhuǎn)步驟2；否則，轉(zhuǎn)步驟3. 步驟2 令i=i+1 。若im ，轉(zhuǎn)步驟1

17、；否則，結(jié)束，沒(méi)有支撐樹(shù)，G 不聯(lián)通。 步驟3 令 。若j=n-1 ，結(jié)束，T是最小樹(shù)；否則，轉(zhuǎn)步驟1。例6-4 用Kruskal算法求解下圖6.8（a)所示網(wǎng)絡(luò)的最小樹(shù)，每條邊上的數(shù)表示該邊的權(quán)值。圖6.8（a)解：按照破圈法的原則，從圖中任取一圈，去掉這個(gè)圈中權(quán)數(shù)最大的一條邊，得一支撐子圖。在支撐子圖中再任取一圈，再去掉圈中權(quán)數(shù)最大的一條邊。如此繼續(xù)下去，一直到剩下的子圖中不再含圈為止。該子圖就是所求的最小生成樹(shù)。最小生成樹(shù)如圖6.8（b）所示：圖6.8（b）3）Prim算法(邊割法)Prim算法又稱為邊割法，是Prim于1957年提出的求解最小樹(shù)的算法。 算法的核心思想是不斷擴(kuò)展一個(gè)子樹(shù)

18、，使其逐步包含所有的頂點(diǎn)。具體增邊的選擇，是在當(dāng)前子樹(shù)的頂點(diǎn)集合與補(bǔ)集合所形成的邊割中選擇最小的邊。Prim算法：步驟0 從圖中任選一點(diǎn)Vi，讓ViS，圖中其余點(diǎn)均包含在 中；步驟2 從 之間的連線中找出最小邊，這條邊一定包含在 最小支撐樹(shù)內(nèi)，不妨設(shè)最小邊為vi, vj，將vi, vj標(biāo)記成最小支撐樹(shù)內(nèi)的邊； 步驟3 令 步驟4 重復(fù)步驟2、步驟3，一直到圖中所有點(diǎn)均包含在S中為止。 例題6-5 用Prim算法求解圖6.9（a）中的最小樹(shù)。圖6.9（a）解：求解結(jié)果見(jiàn)圖6.9（b）圖6.9（b）例6- 在一個(gè)地區(qū)有一個(gè)公共服務(wù)機(jī)構(gòu)，如飛機(jī)場(chǎng)、醫(yī)院等，圖6.10中O所示。三個(gè)鄉(xiāng)鎮(zhèn)（圖6.10中的

19、v1,v2,v3所示）需要連接到這個(gè)公共服務(wù)機(jī)構(gòu)。鄉(xiāng)鎮(zhèn)與服務(wù)機(jī)構(gòu)之間、鄉(xiāng)鎮(zhèn)與鄉(xiāng)鎮(zhèn)之間的連接高速公路的造價(jià)為邊的權(quán)。問(wèn)如何構(gòu)建這個(gè)連接網(wǎng)絡(luò)并分配建設(shè)費(fèi)用？圖6.10解：這顯然是一個(gè)最小支撐樹(shù)的構(gòu)建和建設(shè)成本分擔(dān)問(wèn)題。 v1,v2,v3分別連接到O的建設(shè)成本為C(v1)9，C(v2)10，C(v3 )11； 將 v1,v2 連接到O的最小樹(shù)的建設(shè)成本為C(v1,v2 )17，同樣，C(v1,v3)18， C(v2,v3)11；將3個(gè)頂點(diǎn)連接到 的最小樹(shù)O的建設(shè)成本C(v1,v2,v3)18 設(shè)分別承擔(dān)的建設(shè)費(fèi)用為x1,x2,x3，則建設(shè)費(fèi)用的分配應(yīng)該滿足：有無(wú)限個(gè)向量滿足上式，每個(gè)向量都可以作為一

20、個(gè)建設(shè)費(fèi)用的分配方案。6.3 最短路問(wèn)題 最短路問(wèn)題是網(wǎng)絡(luò)理論中應(yīng)用最廣泛的問(wèn)題之一。許多優(yōu)化問(wèn)題可以使用這個(gè)模型，如設(shè)備更新、管道鋪設(shè)、線路安排、廠區(qū)布局等。 在上一章中我們?cè)榻B了最短路問(wèn)題的動(dòng)態(tài)規(guī)劃解法，但某些最短路問(wèn)題（如道路不能整齊分段者）構(gòu)造動(dòng)態(tài)規(guī)劃方程比較困難，而圖論方法則比較有效。另外，這個(gè)問(wèn)題相對(duì)比較簡(jiǎn)單，其算法經(jīng)常做為其他問(wèn)題的子算法而調(diào)用。 最短路問(wèn)題是求一條v1vj的路 ，使它是從v1到vj的所有路中總權(quán)最小的路。即：優(yōu)化問(wèn)題6.3.1 基本概念與Bellman方程 最短路問(wèn)題的一般提法是設(shè)N=(V,A,W)為網(wǎng)絡(luò)圖，圖中各邊(vi , vj)有權(quán)wij（wij=表示v

21、i, vj之間沒(méi)有邊）， v1為起始點(diǎn)， vj為圖中任意一點(diǎn)。網(wǎng)絡(luò)中有多條v1vj的路P,每條路的權(quán)是其所有構(gòu)成弧的權(quán)之和。 對(duì)于網(wǎng)絡(luò)中的一個(gè)圈，其權(quán)是其所構(gòu)成邊的權(quán)之和。權(quán)為正的圈稱為正圈；權(quán)為負(fù)的圈稱為負(fù)圈；權(quán)為0的圈稱為零圈。 在一個(gè)沒(méi)有負(fù)圈的網(wǎng)絡(luò)中，求解最短路問(wèn)題比較簡(jiǎn)單，目前的大多數(shù)算法也是面向這種網(wǎng)絡(luò)的。 對(duì)于存在負(fù)圈的網(wǎng)絡(luò)，其最短路的求解問(wèn)題很復(fù)雜，目前還沒(méi)有好的有效算法。令uj表示網(wǎng)絡(luò)中v1vj的最短路的長(zhǎng)度。基于動(dòng)態(tài)規(guī)劃中遞歸方程的思想，得到求解最短路問(wèn)題的遞歸關(guān)系如下：定理 6-5 設(shè)有向網(wǎng)絡(luò)G中只含正圈，并且從點(diǎn)v1到其余點(diǎn) vj都有有限長(zhǎng)度的有向路，那么(6.1)有唯一

22、有限解。定理 6-6 設(shè) 不含圈，則N的頂點(diǎn)可以重新編號(hào)，使Bellman算法的基本思想是： 基于這樣的事實(shí)：從v1到vj的最短路總是沿著該路先到vj前面的某一點(diǎn)vi ，然后再沿著(vi ,vj)到vj 。于是，若v1到vj為最短路，則v1到vj亦為最短路。例6-7 計(jì)算如下網(wǎng)絡(luò)中 各點(diǎn)的最短路。圖6.11解：這是一個(gè)有圈網(wǎng)絡(luò)圖，但v1是起始點(diǎn)，故進(jìn)入v1的弧可以刪去。對(duì)頂點(diǎn)進(jìn)行重新標(biāo)號(hào)，得到網(wǎng)絡(luò)圖，圖6-11(b)。按照ui，求出最短路網(wǎng)絡(luò)，圖6-11(c)。Bellman方程的計(jì)算：6.3.2 Dijkstra算法 1959年,E.W.Dijkstra 提出了求正權(quán)網(wǎng)絡(luò)最短路徑的標(biāo)號(hào)法，用

23、給節(jié)點(diǎn)記標(biāo)號(hào)來(lái)逐步形成起點(diǎn)到各點(diǎn)的最短路徑及其距離值，是目前較好的一種算法。 Dijkstra 算法也稱為雙標(biāo)號(hào)法。也就是對(duì)圖中的每個(gè)點(diǎn)vj 賦予兩個(gè)參數(shù)（通常稱為標(biāo)號(hào)） ： 第一個(gè)標(biāo)號(hào)uj表示從起點(diǎn)v1到vj的最短路的長(zhǎng)度，是距離標(biāo)號(hào)； 第二個(gè)標(biāo)號(hào) 稱作前趨標(biāo)號(hào)，是記錄在v1到vj的最短路上， vj 前面一個(gè)鄰點(diǎn)的下標(biāo)，用來(lái)標(biāo)識(shí)最短路路徑，從而可對(duì)終點(diǎn)到始點(diǎn)進(jìn)行反向追蹤，找到v1到vj的最短路。通過(guò)不斷修改這些標(biāo)號(hào)，進(jìn)行迭代計(jì)算。Dijkstra 算法：步驟0 給起點(diǎn)v1標(biāo)號(hào)(0,s)，表示從v1到v1的距離為0，vs為起 點(diǎn)。 步驟1 如果S=V，則uj即為v1到vj的最短路的長(zhǎng)度，最短路

24、可以按照 pred(j )記錄的信息，反向追蹤即可獲得，結(jié)束。 否則，轉(zhuǎn)步驟2。步驟2 求出弧集 。若 ，表明從所有已經(jīng)賦予標(biāo)號(hào)的頂點(diǎn)出發(fā)，不再有這樣的弧，它的另一頂點(diǎn)尚未標(biāo)號(hào)，則計(jì)算結(jié)束。對(duì)于已有標(biāo)號(hào)的頂點(diǎn)，可求得從到達(dá)這個(gè)頂點(diǎn)的最短路，對(duì)于沒(méi)有標(biāo)號(hào)的頂點(diǎn)，則不存在從到達(dá)這個(gè)頂點(diǎn)的路。若弧集，轉(zhuǎn)步驟3。 步驟3 對(duì)弧集A中的每一條弧(vi , vj) ，計(jì)算 則vi 賦予雙標(biāo)號(hào) 其中 。 轉(zhuǎn)步驟 2 經(jīng)上述一個(gè)循環(huán)的計(jì)算，將求出v1到一個(gè)頂點(diǎn)vj的最短路及其長(zhǎng)度，從而使一個(gè)頂點(diǎn)vj得到雙標(biāo)號(hào)。 若圖中總共有n個(gè)頂點(diǎn)，則最多計(jì)算個(gè)(n-1)循環(huán)，即可得到最后結(jié)果。 例6-8 求v1到其余各點(diǎn)的

25、最短路 圖6.12解：（1）給起點(diǎn)V1 標(biāo)號(hào)(0,S) ，表示從V1到V1的距離P(V1)=0,V1為起點(diǎn)。 （2）標(biāo)號(hào)點(diǎn)的集合 ，沒(méi)標(biāo)號(hào)點(diǎn)的集合 ， 弧集 中 ，點(diǎn)V2 對(duì)應(yīng)的是010，點(diǎn)V3對(duì)應(yīng)的是015，點(diǎn)V4對(duì)應(yīng)的是08。點(diǎn)V4最小，故點(diǎn)V4得到雙標(biāo)號(hào)（8，1）。8代表從V1到V4的最短路長(zhǎng)度，1代表前趨點(diǎn)V1。 （3）標(biāo)號(hào)點(diǎn)的集合 ，沒(méi)標(biāo)號(hào)點(diǎn)的集合 ，弧集 中點(diǎn)V2對(duì)應(yīng)的是10，點(diǎn)V3 對(duì)應(yīng)的是15。點(diǎn)V2最小，點(diǎn)V2得到雙標(biāo)號(hào)（10，1）。10代表最短路長(zhǎng)度，1代表前趨點(diǎn)V1。 （4）標(biāo)號(hào)點(diǎn)的集合 ，沒(méi)標(biāo)號(hào)點(diǎn)的集合 ，弧集點(diǎn)V3對(duì)應(yīng)的是102，點(diǎn)V5對(duì)應(yīng)的是106。故點(diǎn)V3得到雙標(biāo)

26、號(hào)（12，2）。（5）標(biāo)號(hào)點(diǎn)的集合 ，沒(méi)標(biāo)號(hào)點(diǎn)的集合 ，弧集點(diǎn)V5對(duì)應(yīng)的仍然是16，點(diǎn)V5得到雙標(biāo)號(hào)（16，2）。（6）標(biāo)號(hào)的點(diǎn)的集合 ，沒(méi)標(biāo)號(hào)的點(diǎn)的集合 ，弧集點(diǎn)V7對(duì)應(yīng)的是1620，點(diǎn)V7得到雙標(biāo)號(hào)（36，5）。（7）標(biāo)號(hào)的點(diǎn)的集合 ，沒(méi)標(biāo)號(hào)的點(diǎn)的集合 ，弧集 計(jì)算結(jié)束。 此時(shí)， ，即點(diǎn)V6 還未標(biāo)號(hào)，說(shuō)明點(diǎn) V1到點(diǎn)V6 沒(méi)有有向路。 圖 6.13至此，自頂點(diǎn) V1至其余頂點(diǎn)的最短路都已求得。如圖 6.13粗線所示。 由上述步驟看出，標(biāo)號(hào)法是一種按標(biāo)號(hào)值從小到大的逐步外探法。只適用于權(quán)值為正實(shí)數(shù)的情況，如果權(quán)值有負(fù)的，算法失效。 6.3.3 Floyd-Warshall算法基本思路： 先

27、給每個(gè)頂點(diǎn)一個(gè)標(biāo)號(hào)，這些標(biāo)號(hào)不一定是最短路的長(zhǎng)度，一般是一個(gè)近似。 然后逐步對(duì)頂點(diǎn)的標(biāo)號(hào)進(jìn)行修正，使標(biāo)號(hào)逐步接近最短路長(zhǎng)度。 當(dāng)算法迭代終止時(shí)，所有的定點(diǎn)標(biāo)號(hào)變成最短路長(zhǎng)度，臨時(shí)標(biāo)號(hào)變成永久標(biāo)號(hào) Floyd-Warshall算法是求網(wǎng)絡(luò)中任意兩點(diǎn)間的最短路的算法，這個(gè)算法的基本思想就是標(biāo)號(hào)修正。 為計(jì)算方便，令網(wǎng)絡(luò)的權(quán)矩陣為 ， 為 到 的距離。FloyWarshall算法用標(biāo)號(hào)修正算法表示如下： 是第k次迭代得到的vi到vj的臨時(shí)性標(biāo)號(hào)，是在到的路中邊數(shù)不超過(guò)k條的路中最短路的長(zhǎng)度，是最短路長(zhǎng)度的近似。 這個(gè)算法在迭代n次后，如果各頂點(diǎn)對(duì)之間存在最短路， 即是vi到vj的最短路長(zhǎng)度，臨時(shí)性標(biāo)

28、號(hào)變成永久性標(biāo)號(hào)。 如果 還沒(méi)有收斂，即存在兩個(gè)頂點(diǎn)vi和vj ，使得 ，這說(shuō)明網(wǎng)絡(luò)中存在負(fù)圈。 例6-9 求如圖6.14所示的網(wǎng)絡(luò)G中任意兩點(diǎn)間的最短路?；∨缘臄?shù)字表示弧的長(zhǎng)度。圖6.14解：用 表示各頂點(diǎn)對(duì)之間通過(guò)不超過(guò)k條弧所能夠到達(dá)的最短路的長(zhǎng)度矩陣，則計(jì)算結(jié)果如下： 首先給出通過(guò)不超過(guò)1條弧即可到達(dá)的長(zhǎng)度矩陣到不超過(guò)2條弧即可到達(dá)的長(zhǎng)度 就是D(1)第一行與它第二列對(duì)應(yīng)元素之和的最小值到不超過(guò)2條弧即可到達(dá)的長(zhǎng)度 就是D(1)第一行與它第三列對(duì)應(yīng)元素之和的最小值到不超過(guò)2條弧即可到達(dá)的長(zhǎng)度 ；其他同樣計(jì)算。就是D(1)第一行與它第四列對(duì)應(yīng)元素之和的最小值 得到各頂點(diǎn)對(duì)之間通過(guò)不超過(guò)2

29、條弧所能夠到達(dá)的最短路的長(zhǎng)度矩陣：各頂點(diǎn)對(duì)之間通過(guò)不超過(guò)k(3,4)條弧所能夠到達(dá)的最短路的長(zhǎng)度矩陣如下：我們看到 則 中的長(zhǎng)度就是最短路長(zhǎng)度。 6.4 網(wǎng)絡(luò)最大流問(wèn)題 最大流問(wèn)題是一類應(yīng)用極為廣泛的問(wèn)題，例如在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車流、貨物流，供水網(wǎng)絡(luò)中有水流，金融系統(tǒng)中有現(xiàn)金流，通信系統(tǒng)中有信息流，等等。 20 世紀(jì) 50 年代,福特（Ford）、富克遜（Fulkerson）建立的“網(wǎng)絡(luò)流理論”是網(wǎng)絡(luò)應(yīng)用的重要組成部分。 最大流量問(wèn)題就是： 給一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)（一般收點(diǎn)用 vt 表示，發(fā)點(diǎn)用 vs 表示，其余為中間點(diǎn)），其每條弧的權(quán)值稱之為容量，在不超過(guò)每條弧的容量的前提下，要求確定每

30、條弧的流量，使得從發(fā)點(diǎn)到收點(diǎn)的流量最大。 6.4.1 基本概念與模型 要把一批貨物從起點(diǎn)v1通過(guò)鐵路網(wǎng)絡(luò)運(yùn)到終點(diǎn)v6去，把鐵路網(wǎng)上的車站看作頂點(diǎn)，兩個(gè)車站間的鐵路線看作弧，而每條鐵路線上運(yùn)送的貨物總量（容量）總是有限的，我們把某線路上的最大可能運(yùn)送量稱為它的容量。考慮：如何安排運(yùn)輸方案，使得從起點(diǎn)v1運(yùn)到終點(diǎn)v6的總運(yùn)量達(dá)到最大？“流”，是指鐵路線（?。┥系膶?shí)際運(yùn)輸量。 每條弧旁的數(shù)字即為該弧的容量cij，弧的方向就是允許流的方向。 把標(biāo)有弧容量的網(wǎng)絡(luò)稱為容量網(wǎng)絡(luò)， 記為實(shí)際通過(guò)各弧的流量，記為 。所有弧上流量的集 稱為該網(wǎng)絡(luò)D的一個(gè)流。 弧旁括號(hào)中的兩個(gè)數(shù)字 ，第一個(gè)數(shù)字表示弧容量，第二個(gè)數(shù)

31、字表示通過(guò)該弧的流量，如弧（vs ,v2）上的(5，1)， 圖616可行流 滿足以下兩個(gè)約束條件： 1) 各弧最大輸送能力約束(容量約束)條件： ，即對(duì)每一條弧(vi,vj)的流量要滿足流量的可行條件，應(yīng)小于等于弧的容量 ，并大于等于零。 （2）可行流與最大流 2）節(jié)點(diǎn)流量平衡條件：網(wǎng)絡(luò)中的流量必須滿足守恒條件，對(duì)收發(fā)點(diǎn)來(lái)說(shuō)，發(fā)點(diǎn)的總流出量=收點(diǎn)的總流入量； 對(duì)中間點(diǎn)v1,v2 ,v3,v4 來(lái)說(shuō)，中間點(diǎn)的總流入量=總流出量。前者是可通過(guò)該弧的最大流量為 5，后者是目前通過(guò)該弧的流量 1。 最大流： 尋求網(wǎng)絡(luò)最大流就是找到一個(gè)可行流 ，使得網(wǎng)絡(luò)發(fā)點(diǎn)到收點(diǎn)的總流量達(dá)到最大。網(wǎng)絡(luò)最大流問(wèn)題的線性規(guī)

32、劃表達(dá)式是（3）增廣鏈 設(shè)網(wǎng)絡(luò)D=(V,A,C)中，有一可行流 按每條弧上流量的多少，可將弧分為 4 種類型： 飽和弧 非飽和弧 零流弧 非零流弧 設(shè) 是網(wǎng)絡(luò)D中從vs 到vt 的一條鏈，沿此方向 上的各弧可分為兩類:前向弧：與鏈的方向一致的弧，前向弧的全體記為 后向弧 : 與鏈的方向相反的弧，后向弧的全體記為增廣鏈：對(duì)于可行流 f， 是一條從 vs 到vt的鏈，如果 中的每條弧均為非飽和弧，且 中的每條弧均為非零流弧，則稱鏈?zhǔn)顷P(guān)于f 的增廣鏈。 如果 是一條增廣鏈，那么在 上可以增加一定的流量，從而增加可行流的流值。 增廣鏈起的作用有兩個(gè)：一是目前的可行流是否是最大流？二如果不是最大流，如何

33、通過(guò)增廣鏈找到更大的可行流？ 如果將網(wǎng)絡(luò)D=(V,A,C)的V剖分為兩部分 ，使 ，則把從 指向弧 的全體稱為分離 的一個(gè)截集，記為 ，即 。 （4）截集和截量 截集 中所有弧的容量之和稱為該截集的截量，記為 ，有 在 D的所有截集中，稱截量最小的截集為最小截集。取 ，則： 截集： 截量： 若取 ， 則： 截集： 截量： 任何一個(gè)可行的流量v(f)都不會(huì)超過(guò)任一截集的截量，即 證明如下：由該結(jié)論可知： 在一個(gè)容量網(wǎng)絡(luò)中，最大流的流量小于等于最小截集的截量。 如果存在一可行流 f*和一個(gè)截量 使得 則 f* 就是最大流，且 是最小截集。 定理6-7 在網(wǎng)絡(luò)D=(V,A,C)中，可行流 f * 是

34、最大流的充分必要條件是網(wǎng)絡(luò)中不存在vs到vt的增廣鏈。最大流最小截集定理：任一容量網(wǎng)絡(luò)中，最大流的流量等于最小截集的截量。判斷一個(gè)可行流是否為最大流，有兩種途徑： 一是能否找出vs到vt的增廣鏈，若能，則說(shuō)明f不是最大流；否則f就是最大流。 二是看V( f )是否等于最小截量。若等，則f就是最大流，否則就不是最大流。6.4.2 Ford-Fulkerson標(biāo)號(hào)算法 標(biāo)號(hào)法的基本思想是： 從一個(gè)可行流 f 出發(fā)，由發(fā)點(diǎn)vs開(kāi)始，對(duì)網(wǎng)絡(luò)D中的每個(gè)頂點(diǎn)進(jìn)行標(biāo)號(hào)，如vt得到標(biāo)號(hào)，這時(shí)可用反向追蹤法在網(wǎng)絡(luò)中找出一條從vs 到 vt 的由標(biāo)號(hào)點(diǎn)及相應(yīng)的弧連接而成的增廣鏈。 若無(wú)，則 f 為所求的最大流；

35、若有，則在增廣鏈上進(jìn)行調(diào)整，改變流量，得一新的可行流 ，繼續(xù)尋找相應(yīng)于該可行流的增廣鏈。 算法的步驟如下： 步驟 1 給出一個(gè)初始可行流； 步驟 2 標(biāo)號(hào)、檢查過(guò)程。 給頂點(diǎn)標(biāo)號(hào)，尋找增廣鏈。凡是標(biāo)號(hào)的點(diǎn)用表示(vi , L(vj)），其中第一個(gè)分量表示該標(biāo)號(hào)是從哪個(gè)點(diǎn)得到的，以便反向追蹤找出增廣鏈 ，第二個(gè)分量是為確定的調(diào)整量用的。 在標(biāo)號(hào)過(guò)程中，每個(gè)點(diǎn)屬于且僅屬于下列集合之一：已標(biāo)號(hào)，但未檢查的點(diǎn)集V0；已標(biāo)號(hào)，已檢查的點(diǎn)集Vs ；未標(biāo)號(hào)的點(diǎn)集 首先給Vs 標(biāo)號(hào)(0，+ )，因Vs是發(fā)點(diǎn)，故括弧中第一個(gè)數(shù)字記為 0。括弧中第二個(gè)數(shù)字表示從上一標(biāo)號(hào)點(diǎn)到這個(gè)標(biāo)號(hào)點(diǎn)的流量的最大允許調(diào)整值。 Vs

36、為發(fā)點(diǎn)，不限允許調(diào)整量，故為+。 此時(shí) 如果V0非空，則反復(fù)按以下，進(jìn)行，否則轉(zhuǎn)第三步。在V0中任選一元素vi ，檢查vi 到 中的點(diǎn)vj的弧(vi, vj )，或 中的點(diǎn)vj 到vi 的弧 ，滿足以下條件的給vj 標(biāo)號(hào)： （a）對(duì)于前向弧(vi, vj ) ，若非飽和，則給點(diǎn) vj 標(biāo)以(vi,l(vj) ），其中 同時(shí)把 vj 從 中除去，歸入V0 。 （b） 對(duì)于后向弧(vj,vi) ，若非零流，則給點(diǎn)vj 標(biāo)以(-vi,l(vj) ） ，其中，同時(shí)把 vj 從 中除去，歸入V0 。 如果 歸入 V0 ，說(shuō)明已找出f 的增廣鏈 ，則轉(zhuǎn)第三步。 把已標(biāo)號(hào)已檢查的點(diǎn)vi歸入 Vs 。 若vt

37、得不到標(biāo)號(hào)，說(shuō)明該網(wǎng)絡(luò)中不存在增廣鏈，給定的可行流即為最大流。轉(zhuǎn)第四步。 步驟 3 調(diào)整過(guò)程 則調(diào)整之后仍為可行流，流值比原來(lái)的可行流流量增大了(0) 。 步驟 4 寫出最小截集 ，最大流 的流量 終止計(jì)算。 例6-10 試用 FordFulkerson 標(biāo)號(hào)法求圖 618所示的網(wǎng)絡(luò)最大流，括號(hào)中，第一個(gè)數(shù)字是容量，第二個(gè)數(shù)字是流量。第二步，首先給Vs標(biāo)以(0，+ )，此時(shí) 。 檢查點(diǎn)Vs： 弧 ，為飽和弧，所以對(duì)V1不標(biāo)號(hào)。弧 ，為非飽和弧，所以給點(diǎn)V2標(biāo)號(hào)， 。其中此時(shí)第一步，圖中已給出可行流f；檢查點(diǎn)V2：弧(V2，V4)， ，為飽和弧，所以對(duì)V4不標(biāo)號(hào)。 弧(V1，V2) ， ，為非零

38、流弧，所以給V1標(biāo)號(hào)， ，其中此時(shí)檢查點(diǎn)V1 ：弧(V1，V3)， ，為非飽和弧，所以對(duì)V3 標(biāo)號(hào)。 ，其中弧(V4，V1) ， ，為非零流弧，所以給V4 標(biāo)號(hào)， ，其中此時(shí)檢查點(diǎn)V3 ：弧(V3，Vt)， ，為非飽和弧，所以對(duì)Vt 標(biāo)號(hào)。 ，其中由于Vt已標(biāo)號(hào)，不需再檢查 V4 。第三步，利用各點(diǎn)已標(biāo)號(hào)的第一個(gè)分量， 從 Vt 反向追蹤得增廣鏈 ，如圖中粗箭頭線所示，其中 ， 由 Vt 標(biāo)號(hào)的第二個(gè)分量知 ，于是在 上進(jìn)行調(diào)整： 調(diào)整后的可行流如圖 6.21所示。對(duì)這個(gè)新的可行流重新在圖中進(jìn)行標(biāo)號(hào)，尋找新的增廣鏈。圖 6.214）再標(biāo)號(hào) 同上述第二步標(biāo)號(hào)，易見(jiàn)，當(dāng)給V2 標(biāo)號(hào) 后，無(wú)法再進(jìn)行

39、下去，此時(shí)， 因此，目前所得到的可行流就是最大流，最小截集為 ，最大流量為 從上例可以看出，最小截集中各弧的容量總和構(gòu)成最大流問(wèn)題的瓶頸，在實(shí)際問(wèn)題中，為提高網(wǎng)絡(luò)中的總流量，必須首先著力改善最小截集中各弧的弧容量。 當(dāng)沿著可行流 f 的一條的增廣鏈 ，以調(diào)整 f ，得到新的可行流 f 時(shí)，b( f ) 比 b( f )增加：6.5 最小費(fèi)用最大流 在上節(jié)最大流問(wèn)題中，每一個(gè)可行流在現(xiàn)實(shí)生活中，還對(duì)應(yīng)著一定的費(fèi)用，許多情況下優(yōu)化目標(biāo)不但要求流量盡可能的大，還要求費(fèi)用盡可能的小。 在一個(gè)網(wǎng)絡(luò)中每條弧都有“容量”和“費(fèi)用”兩個(gè)限制的條件下，尋求vs到 vt 的最大流，使該最大流在所有最大流中費(fèi)用達(dá)到

40、最小。求解最小費(fèi)用最大流問(wèn)題的基本思想是： 在尋求最大流的算法過(guò)程中，不但通過(guò)增廣鏈?zhǔn)沽髁恐鸩皆黾?，還要考慮費(fèi)用的約束，即每次可行流的調(diào)整都使費(fèi)用增加最小。 1時(shí)，費(fèi)用的增加量是 這個(gè)數(shù)值反映了增廣鏈的好壞，這個(gè)數(shù)值越小，這條增廣鏈就越好。 把 稱為增廣鏈的費(fèi)用。 若 f 是流值為v( f )的所有可行流中費(fèi)用最小者，而 是關(guān)于 f 的費(fèi)用最小的增廣鏈，那么沿去調(diào)整可行流 f ，得到可行流 f，新可行流就是流值為v( f ) 的所有可行流中費(fèi)用最小的可行流。 確定一個(gè)最小費(fèi)用可行流,然后找出最小費(fèi)用增廣鏈，按照最小費(fèi)用增廣鏈對(duì)可行流進(jìn)行調(diào)整，一直調(diào)整下去，直到找不出增廣鏈為止，這樣得到的可行流

41、即為最小費(fèi)用最大流。 為了尋找最小費(fèi)用增廣鏈，我們以原可行流 f 為基礎(chǔ)，構(gòu)造一個(gè)新賦權(quán)圖D(f )=(V,A(f), W)。D( f )的頂點(diǎn)為原網(wǎng)絡(luò)D的頂點(diǎn)V ，把D中的每條弧A變?yōu)閮蓷l方向相反的兩條弧，,形成弧集合 A(f)。弧的賦權(quán)原則如下：對(duì)于弧 ，有對(duì)于弧 , 有當(dāng)然，長(zhǎng)度為+的弧可以略去。最小費(fèi)用最大流的算法：（1）取零流為初始最小費(fèi)用可行流，記為f(0) 。（2）若第k步得到最小費(fèi)用可行流f(k) , 則構(gòu)造一個(gè)新賦權(quán)圖D( f(k) ) ,在D( f(k) )中尋求從vsvt 最短路。 若不存在最短路，則目前的可行流F(k)即為網(wǎng)絡(luò)D的最小費(fèi)用最大流；若存在最短路，則在原網(wǎng)絡(luò)

42、D中得到了相應(yīng)的最小費(fèi)用增廣鏈 ，對(duì)F(k)進(jìn)行調(diào)整，調(diào)整量為（3）調(diào)整方法如下： 重復(fù)進(jìn)行上述步驟，直到找不出增廣鏈為止。例6.11 求網(wǎng)絡(luò)（圖6.20）的最小費(fèi)用最大流，弧旁的數(shù)字為圖6.20解：（1）取f(0)=0為初始可行流?；∨缘臄?shù)字為 ,如圖6.21所示圖6.21 在零流中，每條弧只能做前向弧，因此可得新賦權(quán)網(wǎng)絡(luò) ,如圖6.22所示。圖6.22 中最短路見(jiàn)圖6-22中的粗線所示，由此找到最小費(fèi)用增廣鏈，見(jiàn)圖6-21中粗線所示。利用最小費(fèi)用增廣鏈對(duì)可行流進(jìn)行調(diào)整，調(diào)整后的新流見(jiàn)圖6-23。圖6.23（2）繼續(xù)進(jìn)行可行流的調(diào)整： 在圖6-23中 是飽和弧，它們只能作后向弧； 既是非0流

43、弧，又非飽和弧，因此它既作前向弧，也作后向弧，其他弧只是0流弧，只能做前向弧。新賦權(quán)網(wǎng)絡(luò)如圖6.24所示： 圖6.24 圖6-24中的最短路見(jiàn)粗線所示，因此找到最小費(fèi)用增廣鏈，見(jiàn)圖6-23中粗線所示。利用最小費(fèi)用增廣鏈對(duì)可行流進(jìn)行調(diào)整，調(diào)整后的新流見(jiàn)圖6-25。圖6.25（3）繼續(xù)進(jìn)行可行流的調(diào)整： 以圖6.25中的可行流為基礎(chǔ)，得到新賦權(quán)網(wǎng)絡(luò)，如圖6.26。圖6.26 圖6.26已經(jīng)找不到 的路，因此圖6.25也就沒(méi)增廣鏈了，即圖6-25所示的可行流即為最小費(fèi)用最大流，流值v(f )5，其費(fèi)用為31。6.6 網(wǎng)絡(luò)計(jì)劃技術(shù)網(wǎng)絡(luò)圖的繪制網(wǎng)絡(luò)圖的時(shí)間參數(shù)計(jì)算網(wǎng)絡(luò)優(yōu)化 用網(wǎng)絡(luò)分析的方法編制的計(jì)劃稱為

44、網(wǎng)絡(luò)計(jì)劃。它是二十世紀(jì)五十年代末發(fā)展起來(lái)的一種編制大型工程進(jìn)度計(jì)劃的有效方法。1956年，美國(guó)杜邦公司在制定企業(yè)不同業(yè)務(wù)部門的系統(tǒng)規(guī)劃時(shí)，制定了第一套網(wǎng)絡(luò)計(jì)劃。這種計(jì)劃借助于網(wǎng)絡(luò)表示各項(xiàng)工作與所需要的時(shí)間，以及各項(xiàng)工作的相互關(guān)系。通過(guò)網(wǎng)絡(luò)分析研究工程費(fèi)用與工期的相互關(guān)系。并找出在編制計(jì)劃時(shí)及計(jì)劃執(zhí)行過(guò)程中的關(guān)鍵路線。這種方法稱為關(guān)鍵路線法（Critical Path Method）簡(jiǎn)稱CPM。1958年，美國(guó)海軍武器部，在制定研制“北極星”導(dǎo)彈計(jì)劃時(shí)，同樣地應(yīng)用了網(wǎng)絡(luò)分析方法與網(wǎng)絡(luò)計(jì)劃。但它注重于對(duì)各項(xiàng)工作安排的評(píng)價(jià)和審查。這種計(jì)劃稱為計(jì)劃評(píng)審方法（Program Evaluation and

45、 Review Technique）簡(jiǎn)稱為PERT。鑒于這兩種方法的差別，他們應(yīng)用的領(lǐng)域略有差別：CPM主要應(yīng)用于以往在類似工程中已取得一定經(jīng)驗(yàn)的承包工程；PERT更多地應(yīng)用于研究與開(kāi)發(fā)項(xiàng)目。在這兩種方法得到應(yīng)用推廣之后，又陸續(xù)出現(xiàn)了類似的最低成本和估算計(jì)劃法、產(chǎn)品分析控制法、人員分配法、物資分配和多種項(xiàng)目計(jì)劃制定法等等。 雖然方法很多，各自側(cè)重的目標(biāo)有所不同。但它們都應(yīng)用的是CPM和PERT的基本原理和基本方法。二十世紀(jì)六十年代我國(guó)開(kāi)始應(yīng)用CPM與PERT，并根據(jù)其基本原理與計(jì)劃的表達(dá)形式，稱它們?yōu)榫W(wǎng)絡(luò)技術(shù)或網(wǎng)絡(luò)方法，又按照網(wǎng)絡(luò)計(jì)劃的主要特點(diǎn)統(tǒng)籌安排，把這些方法稱為統(tǒng)籌法。 國(guó)內(nèi)外應(yīng)用網(wǎng)絡(luò)計(jì)

46、劃的實(shí)踐表明，它具有一系列優(yōu)點(diǎn)，特別適用于生產(chǎn)技術(shù)復(fù)雜，工作項(xiàng)目繁多、且聯(lián)系緊密的一些跨部門的工作計(jì)劃。例如：新產(chǎn)品研制開(kāi)發(fā)、大型工程項(xiàng)目、生產(chǎn)技術(shù)準(zhǔn)備、設(shè)備大修等計(jì)劃。還可以應(yīng)用在人力、物力、財(cái)力等資源的安排，合理組織報(bào)表、文件流程等方面。編制網(wǎng)絡(luò)計(jì)劃包括繪制網(wǎng)絡(luò)圖，計(jì)算時(shí)間參數(shù)，確定關(guān)鍵路線及網(wǎng)絡(luò)優(yōu)化等環(huán)節(jié)。下面分別討論這些內(nèi)容。 為了編制網(wǎng)絡(luò)計(jì)劃，首先需繪制網(wǎng)絡(luò)圖。網(wǎng)絡(luò)圖是由節(jié)點(diǎn)(點(diǎn))、弧及權(quán)所構(gòu)成的有向圖。即有向的賦權(quán)圖。 一、網(wǎng)絡(luò)圖的繪制節(jié)點(diǎn)表示一個(gè)事項(xiàng)（或事件），它是一個(gè)或若干個(gè)工序的開(kāi)始或結(jié)束，是相鄰工序在時(shí)間上的分界點(diǎn)。節(jié)點(diǎn)用圓圈和里面的數(shù)字表示，數(shù)字表示節(jié)點(diǎn)的編號(hào)，如，等。

47、弧表示一個(gè)工序，工序是指為了完成工程項(xiàng)目,在工藝技術(shù)和組織管理上相對(duì)獨(dú)立的工作或活動(dòng)。一項(xiàng)工程由若干個(gè)工序組成。工序需要一定的人力、物力等資源和時(shí)間。弧用箭線“”表示。 權(quán)表示為完成某個(gè)工序所需要的時(shí)間或資源等數(shù)據(jù)。通常標(biāo)注在箭線下面或其它合適的位置上。 例1 某項(xiàng)研制新產(chǎn)品工程的各個(gè)工序與所需時(shí)間以及它們之間的相互關(guān)系如下表所示。要求編制該項(xiàng)工程的網(wǎng)絡(luò)計(jì)劃。 工 序 工序代號(hào) 所需時(shí)間(天) 緊后工序 產(chǎn)品設(shè)計(jì)與工藝設(shè)計(jì) a60b，c，d，e 外購(gòu)配套件 b45l 下料、鍛件 c10f 工裝制造1 d20g，h 木模、鑄件 e40h 機(jī)械加工1 f18l 工裝制造2 g30k 機(jī)械加工2 h

48、15l 機(jī)械加工3 k25l 裝配調(diào)試 l35根據(jù)上表繪制的網(wǎng)絡(luò),如圖6.28所示。b12467835a6045 c10d20e40f18g30h15k25l350圖6.28在圖6.28中，箭線a、b、 l分別代表10個(gè)工序。 箭線下面的數(shù)字表示為完成該個(gè)工序所需的時(shí)間（天數(shù)）。 結(jié)點(diǎn)、分別表示某一或某些工序的開(kāi)始和結(jié)束。 例如，結(jié)點(diǎn)表示a 工序的結(jié)束和b、c、d、e等工序的開(kāi)始,即a工序結(jié)束后,后四個(gè)工序才能開(kāi)始。 在繪制網(wǎng)絡(luò)圖中，用一條弧和兩個(gè)結(jié)點(diǎn)表示一個(gè)確定的工序。例如，表示一個(gè)確定的工序b。 工序開(kāi)始的結(jié)點(diǎn)稱為箭尾結(jié)點(diǎn),如b工序的； 工序結(jié)束的結(jié)點(diǎn)稱為箭頭結(jié)點(diǎn),如b工序的。 稱為箭尾事

49、項(xiàng)，稱為箭頭事項(xiàng)。工序的箭尾事項(xiàng)與箭頭事項(xiàng)稱為該工序的相關(guān)事項(xiàng)。在一張網(wǎng)絡(luò)圖上只能有始點(diǎn)和終點(diǎn)兩個(gè)結(jié)點(diǎn)，分別表示工程的開(kāi)始和結(jié)束，其它結(jié)點(diǎn)既表示上一個(gè)（或若干個(gè)）工序的結(jié)束，又表示下一個(gè)（或若干個(gè)）工序的開(kāi)始。 為正確反映工程中各個(gè)工序的相互關(guān)系,在繪制網(wǎng)絡(luò)圖時(shí)，應(yīng)遵循以下規(guī)則：(1) 方向、時(shí)序與結(jié)點(diǎn)編號(hào)按照工藝流程的順序，規(guī)定工序從左向右排列。網(wǎng)絡(luò)圖中的各個(gè)結(jié)點(diǎn)都有一個(gè)時(shí)間,一般按各個(gè)結(jié)點(diǎn)的時(shí)間順序編號(hào)。為了便于修改編號(hào)及調(diào)整計(jì)劃,可以在編號(hào)過(guò)程中留出一些編號(hào)。始點(diǎn)編號(hào)可以從1開(kāi)始，也可以從0開(kāi)始。網(wǎng)絡(luò)圖應(yīng)從左向右延伸，編號(hào)應(yīng)從小到大，且不重復(fù)。箭頭事項(xiàng)編號(hào)大于箭尾事項(xiàng)編號(hào)(2)緊前工序與

50、緊后工序 例如,在圖61中,只有在 a 工序結(jié)束以后,b、c、 d、e工序才能開(kāi)始。a工序是b、c、d、e 等工序的緊前工序,而b、c、d、e等工序則是工序a 的緊后工序。(3)虛工序?yàn)榱擞脕?lái)表達(dá)相鄰工序之間的銜接關(guān)系，而實(shí)際上并不存在而虛設(shè)的工序。虛工序不需要人力、物力等資源和時(shí)間。只表示某工序必須在另外一個(gè)工序結(jié)束后才能開(kāi)始。如圖61中，虛工序只表示在 d 工序結(jié)束后，h 工序才能開(kāi)始。(4)相鄰兩個(gè)結(jié)點(diǎn)之間只能有一條弧即一個(gè)工序用確定的兩個(gè)相關(guān)事項(xiàng)表示，某兩個(gè)相鄰結(jié)點(diǎn)只能是一個(gè)工序的相關(guān)事項(xiàng)。在計(jì)算機(jī)上計(jì)算各個(gè)結(jié)點(diǎn)和各個(gè)工序的時(shí)間參數(shù)時(shí)，相關(guān)事項(xiàng)的兩個(gè)結(jié)點(diǎn)只能表示一道工序，否則將造成邏輯

51、上的混亂。 123abc圖6.291342abc圖6.30如圖6.29的畫法是錯(cuò)誤的圖6.30的畫法是正確的。(5)網(wǎng)絡(luò)圖中不能有缺口和回路 在網(wǎng)絡(luò)圖中，除始點(diǎn)和終點(diǎn)外，其它各個(gè)結(jié)點(diǎn)的前后都應(yīng)有弧相連接，即圖中不能有缺口，使網(wǎng)絡(luò)圖從始點(diǎn)經(jīng)任何路線都可到達(dá)終點(diǎn)。否則，將使某些工序失去與其緊后（或緊前）工序應(yīng)有的聯(lián)系。1234abcd圖6.31 在本章討論的網(wǎng)絡(luò)圖中不能有回路，即不可能有循環(huán)現(xiàn)象。否則，將使組成回路的工序永遠(yuǎn)不能結(jié)束，工程永遠(yuǎn)不能完工。在如下網(wǎng)絡(luò)圖6.31中出現(xiàn)的情況，顯然是錯(cuò)誤的。(6) 平行作業(yè)為縮短工程的完工時(shí)間，在工藝流程和生產(chǎn)組織條件允許的情況下，某些工序可以同時(shí)進(jìn)行，即

52、可采用平行作業(yè)的方式。如在圖6.28中，工序b、c、d、e 四個(gè)工序即可平行作業(yè)。在有幾個(gè)工序平行作業(yè)結(jié)束后轉(zhuǎn)入下一道工序的情況下，考慮到便于計(jì)算網(wǎng)絡(luò)時(shí)間和確定關(guān)鍵路線，選擇在平行作業(yè)的幾個(gè)工序中所需時(shí)間最長(zhǎng)的一個(gè)工序，直接與其緊后工序銜接，而其它工序則通過(guò)虛工序與其緊后工序銜接。如在圖6.28中,工序d、e 平行作業(yè),這兩個(gè)工序都結(jié)束后,它們的緊后工序h 才可能開(kāi)始。在工序d、e 中,工序 e 所需的時(shí)間(40天)比工序d 所需時(shí)間(20天)長(zhǎng)，則工序e 直接與工序h 連接，而工序d 則通過(guò)虛工序與工序 h 連接。(7) 交叉作業(yè)對(duì)需要較長(zhǎng)時(shí)間才能完成的一些工序，在工藝流程與生產(chǎn)組織條件允許

53、的情況下，可以不必等待工序全部結(jié)束后再轉(zhuǎn)入其緊后工序，而是分期分批的轉(zhuǎn)入。這種方式稱為交叉作業(yè)。交叉作業(yè)可以縮短工程周期。如在圖6.28中，將工裝制造分為兩批，將一個(gè)工序分為兩個(gè)工序d、g，分別與緊后工序h 、k連接。(8) 始點(diǎn)和終點(diǎn)為表示工程的開(kāi)始和結(jié)束，在網(wǎng)絡(luò)圖中只能有一個(gè)始點(diǎn)和一個(gè)終點(diǎn)。當(dāng)工程開(kāi)始時(shí)有幾個(gè)工序平行作業(yè)，或在幾個(gè)工序結(jié)束后完工，用一個(gè)始點(diǎn)、一個(gè)終點(diǎn)表示。若這些工序不能用一個(gè)始點(diǎn)或一個(gè)終點(diǎn)表示時(shí)，可用虛工序把它們與始點(diǎn)或終點(diǎn)連起來(lái)。 (9) 網(wǎng)絡(luò)圖的分解與綜合根據(jù)網(wǎng)絡(luò)圖的不同需要，一個(gè)工序所包括的工作內(nèi)容可以多一些，即工序綜合程度較高。也可以在一個(gè)工序中所包括的工作內(nèi)容少一

54、些，即工序綜合程度較低。一般情況下，工程總指揮部制定的網(wǎng)絡(luò)計(jì)劃是工序綜合程度較高的網(wǎng)絡(luò)圖（母網(wǎng)絡(luò)圖）而下一級(jí)部門，根據(jù)綜合程度高的網(wǎng)絡(luò)圖的要求，制定本部門的工序綜合程度低的網(wǎng)絡(luò)圖（子網(wǎng)絡(luò)圖）。將母網(wǎng)絡(luò)分解為若干個(gè)子網(wǎng)絡(luò)，稱為網(wǎng)絡(luò)圖的分解。而將若干個(gè)子網(wǎng)絡(luò)綜合為一個(gè)母網(wǎng)絡(luò)，則稱為網(wǎng)絡(luò)圖的綜合。圖6.28視為一個(gè)母網(wǎng)絡(luò)。它可以分解為工序a ，工序b、c、d、e、f、g、h、k ，及工序l 三個(gè)子網(wǎng)絡(luò)。工序 a 和工序 l 都可以再分解為綜合程度較低的若干個(gè)工序。 (10) 網(wǎng)絡(luò)圖的步局在網(wǎng)絡(luò)圖中，盡可能將關(guān)鍵路線布置在中心位置，并盡量將聯(lián)系緊密的工作布置在相近的位置。為使網(wǎng)絡(luò)圖清楚和便于在圖上填寫

55、有關(guān)的時(shí)間數(shù)據(jù)與其它數(shù)據(jù)，弧線盡量用水平線或具有一段水平線的折線。網(wǎng)絡(luò)圖也可以附有時(shí)間進(jìn)度；必要時(shí)也可以按完成各工序的工作單位布置網(wǎng)絡(luò)圖。 (1)、網(wǎng)絡(luò)圖的繪制步驟確定目標(biāo)，做好準(zhǔn)備工作任務(wù)分解和分析繪制網(wǎng)絡(luò)圖二、關(guān)鍵路徑與網(wǎng)絡(luò)圖的編制表 6.2 調(diào)查項(xiàng)目的任務(wù)分解和分析繪制網(wǎng)絡(luò)圖(2) 路線與關(guān)鍵路線在網(wǎng)絡(luò)圖中，從始點(diǎn)開(kāi)始，按照各個(gè)工序的順序，連續(xù)不斷地到達(dá)終點(diǎn)的一條通路稱為路線。如在圖6.28中，共有五條路線，五條路線的組成及所需要的時(shí)間如表62所示。 表62路線 路 線 的 組 成 各工序所需的時(shí)間之和(天) 1 60+45+35=140 2 60+10+18+35=123 3 60+2

56、0+30+25+35=170 4 60+20+15+35=130 5 60+40+15+35=150 在各條路線上，完成各個(gè)工序的時(shí)間之和是不完全相等的。其中，完成各個(gè)工序需要時(shí)間最長(zhǎng)的路線稱為關(guān)鍵路線，或稱為主要矛盾線，在圖中用粗線表示。在圖6.28中，第三條路線就是條關(guān)鍵路線，組成關(guān)鍵路線的工序稱為關(guān)鍵工序。 如果能夠縮短關(guān)鍵工序所需的時(shí)間，就可以縮短工程的完工時(shí)間。而縮短非關(guān)鍵路線上的各個(gè)工序所需要的時(shí)間，卻不能使工程的完工時(shí)間提前。即使在一定范圍內(nèi)適當(dāng)?shù)赝祥L(zhǎng)非關(guān)鍵路線上各個(gè)工序所需要的時(shí)間，也不至于影響工程的完工時(shí)間。編制網(wǎng)絡(luò)計(jì)劃的基本思想是： 在一個(gè)龐大的網(wǎng)絡(luò)圖中找出關(guān)鍵路線。對(duì)關(guān)鍵

57、工序，優(yōu)先安排資源，挖掘潛力，采取相應(yīng)措施，盡量壓縮時(shí)間。而對(duì)非關(guān)鍵路線上的各工序，只要在不影響工程完工時(shí)間的條件下，抽出適當(dāng)?shù)娜肆Α⑽锪Φ荣Y源，用在關(guān)鍵工序上，以達(dá)到縮短工程工期，合理利用資源等目的。在執(zhí)行計(jì)劃過(guò)程中，可以明確工作重點(diǎn)，對(duì)各關(guān)鍵工序加以有效控制和調(diào)度。關(guān)鍵路線是相對(duì)的，也是可以變化的。在采取一定的技術(shù)組織措施之后，關(guān)鍵路線有可能變?yōu)榉顷P(guān)鍵路線。而非關(guān)鍵路線也有可能變?yōu)殛P(guān)鍵路線。網(wǎng)絡(luò)圖的路線以上網(wǎng)絡(luò)圖共有8條路線計(jì)算出8條路線的總時(shí)間，最長(zhǎng)的是16天。關(guān)鍵路線是當(dāng)某些工作的時(shí)間調(diào)整后，可能引起關(guān)鍵路線和工期的變化。例如將E的時(shí)間縮短為2天，則工期縮短為13天，關(guān)鍵路線將變?yōu)?3

58、46BEG5651356BFH553（1）作業(yè)時(shí)間為了編制網(wǎng)絡(luò)計(jì)劃和找出關(guān)鍵路線,要計(jì)算網(wǎng)絡(luò)圖中各個(gè)事項(xiàng)及各個(gè)工序的有關(guān)時(shí)間，稱這些有關(guān)時(shí)間為網(wǎng)絡(luò)時(shí)間。作業(yè)時(shí)間(Tij )：為完成某一工序所需要的時(shí)間稱為該工序的作業(yè)時(shí)間，用Tij表示。三、網(wǎng)絡(luò)時(shí)間參數(shù)的計(jì)算2) 事項(xiàng)時(shí)間： 事項(xiàng)最早時(shí)間TE (j) 通常是按箭頭事項(xiàng)計(jì)算事項(xiàng)最早時(shí)間,用TE (j)表示,它等于從始點(diǎn)事項(xiàng)起到本事項(xiàng)最長(zhǎng)路線的時(shí)間長(zhǎng)度。計(jì)算事項(xiàng)最早時(shí)間是從始點(diǎn)事項(xiàng)開(kāi)始，自左向右逐個(gè)事件向前計(jì)算。 假定始點(diǎn)事項(xiàng)的最早時(shí)間等于零，即TE (1)= 0。 箭頭事項(xiàng)的最早時(shí)間等于箭尾事項(xiàng)最早時(shí)間加上作業(yè)時(shí)間。 當(dāng)同時(shí)有兩個(gè)或若干個(gè)箭線指向

59、箭頭事項(xiàng)時(shí)，選擇各工序的箭尾事項(xiàng)最早時(shí)間與各自工序作業(yè)時(shí)間之和的最大值。即： TE (1) = 0 TE (j) = max TE (i) + T(i，j) ( j = 2，n) 式中： TE (j)為箭頭事項(xiàng)的最早時(shí)間； TE (i) 為箭尾事項(xiàng)的最早時(shí)間例如，在網(wǎng)絡(luò)圖6.28中各事項(xiàng)的最早時(shí)間為：TE (1) = 0TE (2) = TE (1) + T(1，2) = 0 + 60 = 60TE (3) = TE (2) + T(2，3) = 60 + 10 = 70TE (4) = TE (2) + T(2，4) = 60 + 20 = 80TE (5) = max TE (2) + T

60、(2，5) ，TE (4) + T(4，5) = max 60 + 40 ， 80 + 0 = 100TE (6) = TE (4) + T(4，6) = 80 + 30 = 110 TE (7) = max TE (2) + T(2,7)，TE (3) + T(3,7) ，TE (6) + T(6,7)，TE (5) + T(5,7) = max 60 + 45 ,70 + 18 ,110 + 25 ,100 + 15 = 135TE (8) = TE (7)+T(7，8)=135 + 35 = 170將計(jì)算結(jié)果計(jì)入各事項(xiàng)左下方的方框內(nèi)，如圖6.32所示。 事項(xiàng)最遲時(shí)間TL(i) 即箭頭事項(xiàng)