第5章圖與網(wǎng)絡

1第5章圖與網(wǎng)絡分析

圖論的基本概念

最小支撐樹

最短路問題

最大流問題

網(wǎng)絡計劃2一、引言

圖論是由瑞士數(shù)學家歐拉（Euler）于1736年創(chuàng)始的，當時有一個世界難題，叫“哥尼斯堡七橋問題”。哥尼斯堡城中有一條河，叫普雷格爾河，河中有兩個島，河上有七座橋，如圖所示。當時那里的居民熱衷于這樣的問題：一個散步者能否走過七座橋，但每座橋只走過一次，最后回到出發(fā)點。5.1圖論的基本概念ABCD3歐拉用A、B、C、D四點表示河的兩岸和小島，用兩點間的聯(lián)線表示橋，如右下圖所示，該問題可歸結為：能否從某一點出發(fā)，一筆畫出這個圖形，最后回到出發(fā)點而不重復？即一筆畫問題。

ACBDBCDA歐拉在1786年發(fā)表了題為“依據(jù)幾何位置的解題方法”的論文，解決了著名的哥尼斯堡七橋問題．歐拉證明了上述圖形一筆劃是不可能的，因為圖中每一個點都只和奇數(shù)條線相關聯(lián)．

他的結論是：圖形能一筆畫的充要條件是圖形的奇頂點（連接奇數(shù)條線的頂點）的個數(shù)為零4二、圖的定義

在自然界和人類的實際生活中，常用點和點與點之間的聯(lián)線所構成的圖，來反映某些研究對象和對象之間的某種特定的關系。如：為了反映城市之間有沒有航班，我們可用右圖表示。甲城與乙城，乙城與丙城有飛機到達，而甲、丙兩城沒有直飛航班。對于工作分配問題，我們可能用點表示工人與需要完成的工作，點間連線表示每個工人可以勝任哪些工作如右圖所示。

甲乙丙甲乙丙工人ABC工作Ｄ5圖的定義：所謂圖，就是頂點（簡稱點）和一些點之間的連線（不帶箭頭或者帶箭頭）所組成的集合。為區(qū)別起見，不帶箭頭的連線稱為邊，帶箭頭的連線稱為弧。如果一個圖是由點和邊所構成的，則稱之為無向圖（也簡稱為圖），記作，其中V表示圖G的非空的頂點集合，E表示G的邊的集合。連接頂點和的邊記為；如果一個圖是由點和弧所構成的，則稱之為有向圖，記作，其中V仍表示有向圖D的非空的頂點集合，A表示D的弧集合。一條方向從指向的弧記為。6

如無向圖：Ｖ1Ｖ4Ｖ3Ｖ2e1e5e6e4e3e2e77如有向圖：Ｖ1Ｖ3Ｖ2Ｖ4Ｖ5Ｖ6Ｖ7a1a2a3a4a6a5a7a8a9a10a118三、基本概念點和邊的相關概念：（1）頂點數(shù)和邊數(shù)：給定圖，集合V的元素的個數(shù)，稱為圖G的頂點數(shù)，記作；集合E的元素的個數(shù)，稱為圖G的邊數(shù)，記作。（2）端點和關聯(lián)邊：若，則稱頂點是的端點，是的關聯(lián)邊。（3）相鄰點和相鄰邊：若頂點和與同一條邊相關聯(lián)，則稱點和為相鄰點；若邊和有一個共同的端點，則稱其為相鄰邊。（4）環(huán)和多重邊：若邊的兩個端點屬同一頂點，則稱該邊為環(huán)；若兩個端點之間多于一條邊，則稱這些邊為多重邊。（5）多重圖和簡單圖：含多重邊的圖稱為多重圖，無環(huán)也無多重邊的圖稱為簡單圖。9（6）次和孤立點：與點關聯(lián)的邊的條數(shù)，稱為點的次，記作；次數(shù)為零的點為孤立點。（7）懸掛點和懸掛邊：次為1的點稱為懸掛點；懸掛點的關聯(lián)邊稱為懸掛邊。（8）奇點和偶點：次為奇數(shù)的點稱為奇點；次為偶數(shù)的點為偶點。定理1圖中，所有頂點的次之和等于所有邊數(shù)的2倍，即鏈的概念：（1）給定一個圖，一個點、邊的交錯序列，如果滿足。這樣的序列稱為一條聯(lián)結和的鏈，記作。10（2）開鏈和閉鏈：如果，則該鏈稱為開鏈；如果，則該鏈稱為閉鏈（或稱為圈）。（3）簡單鏈和初等鏈：如鏈內所含的邊均不相同，稱之為簡單鏈；如鏈內所含的點均不相同，稱之為初等鏈。如：是簡單鏈，是初等鏈，是初等圈，是簡單圈，Ｖ1Ｖ2Ｖ4Ｖ3Ｖ5Ｖ6Ｖ7e1e2e3e8e4e7e6e5e911（4）基礎圖和路：若把一個有向圖D的方向去掉，即每一弧都用相應得無向邊代替，所得到的一個無向圖，稱為該有向圖D的基礎圖，記為G（D）；基礎圖G（D）中的鏈（或圈）恢復無向邊的方向后，稱為有向圖D的鏈（或圈）。若交替序列是有向圖G的一條鏈，且滿足，即鏈中每一條弧的箭頭方向都和鏈的方向一致，那么該鏈稱為有向圖D的一條從到的路，簡記。又若，則稱μ為圖D中的回路。對無向圖G來說，鏈和路（閉鏈和回路）這兩個概念是一致的。但有向圖D中的鏈不一定是路，因為有向圖的鏈可能存在和鏈的方向不一致的反向弧，但按定義，它們仍是有向圖中的鏈。12連通圖和網(wǎng)絡圖的概念：（1）連通圖：在一個圖G中，若任意兩點之間至少存在一條鏈，則稱該圖G為連通圖，否則稱之為不連通圖。如：Ｖ3Ｖ6Ｖ5Ｖ2Ｖ4Ｖ1a2a3a1a4a5左圖為不連通圖。因為在頂點Ｖ1，V2，V3，V4和V5，V6之間不存在任何一條鏈將它們相連接。Ｖ1Ｖ2Ｖ3Ｖ4Ｖ5右圖為有向連通圖13（2）連通分圖：若G是不連通圖，那么它的每一個連通部分稱為圖G的連通分圖。（3）子圖和支撐子圖：設圖，若有，使，則稱是的子圖；若，則稱是的支撐子圖。如，以下右圖是左圖的支撐子圖。v1v3v5v4e5v3v5v4v2e2e1e3e4e5e6e7e8v2e1e3e4v1e614（4）賦權圖：設圖，若對其邊集E定義了一個實值函數(shù)，則稱該圖為一個賦權圖。記作。稱為邊的權。如某工廠內連接六個車間的道路網(wǎng)如入所示，已知每條路長，要求沿道路架設連接六個車間的電話線路，使電話總長最短。Ｖ1Ｖ2Ｖ3Ｖ4Ｖ5Ｖ6652715344左圖為一賦權圖最優(yōu)解：如紅線所示，電話總長15個單位。紅線所示為圖Ｇ的最小支撐樹15（5）網(wǎng)絡圖，若為一賦權圖，并在其頂點集合V中指定了起點（或稱發(fā)點）和終點（或稱收點），其余的點為中間點，這樣的賦權圖稱為網(wǎng)絡圖（簡稱網(wǎng)絡）。記作。網(wǎng)絡一般是連通的賦權圖。

若一個網(wǎng)絡圖中的每條邊都是有向的弧，則稱之為有向網(wǎng)絡，記作

16四、圖的矩陣表示距離矩陣：設圖，為邊上的權，表示點到之間的距離，則可構造距離矩陣，其中如：以下無向賦權圖中的權表示點與點之間距離其他Ｖ1247635489Ｖ2Ｖ3Ｖ4Ｖ5或

對有向賦權圖，則定義時將改為。17鄰接矩陣：

設圖，則鄰接矩陣的元素可定義如下其他對有向賦權圖，則定義時將改為如Ｖ1Ｖ2Ｖ3Ｖ4Ｖ518一、樹及其性質樹的定義：設，若G連通，并且沒有圈，則稱G為樹，記作。比如有六個頂點的樹有6種，5.2最小支撐樹··19定理2

以下關于樹T的六種描述是等價的，（1）無圈連通圖；（2）無圈，(即圖有條邊，是圖中的頂點數(shù))；（3）連通，；（4）無圈，但增加一條邊可得唯一一個圈；（5）連通，但舍棄一條邊則不連通；（6）每一對頂點之間有一條且僅有一條鏈。上述六個等價命題可以使用循環(huán)證明法，即由命題（1）推得命題（2），再由命題（2）推得命題（3），……，依次類推，最后由命題（6）回推到命題（1），完成以上推導過程即證明了六個命題是等價的。20二、圖的支撐樹支撐樹的定義：假設圖是圖的支撐子圖，如果圖是一個樹，則稱T是G的支撐樹。如下圖中，（b）圖是(a)圖的支撐樹定理3

圖G有支撐樹的充分必要條件是圖G是連通的V1V2V3V4V5V6V2V3V4V5V6（a）（b）21三、最小支撐樹定義設賦權圖，它的每條邊有非負權，是G的一個支撐樹，中所有邊的權之和如果，則稱是G的最小支撐樹。定理4

設賦權圖，若把E分割成兩個不相交的非空子集和，那么連接這兩個子集的最小邊一定包含在G的最小支撐樹內。由定理4可以引出求最小支撐樹的方法22求最小支撐樹的方法。（1）避圈法。步驟如下：①從賦權圖G中任選一點，令，；②從連接和的邊中選擇權最小的邊，不妨假設為，由定理4，它必包含在最小支撐樹內；③令，；④若，則停止計算，已選出的各條邊已構成最小支撐樹，否則回到②。例1

某工廠聯(lián)結六個車間的道路網(wǎng)如下圖所示，已知每條道路長，要求沿道路架設聯(lián)結六個車間的電話網(wǎng)，使電話線的總長最短。V1V2V4V3V5V661557234423至此，停止計算，

V1V2V4V3V5V6615572344解：這是求最小支撐樹的問題，由避圈法的步驟，在圖G的六個頂點中任選其中一點作為S，比如選，則，聯(lián)結和一共有3條邊，取最短邊，并令，依次類推…

，最短電話線路的總長為15個單位。24（2）破圈法。步驟是：在圖中任取一個圈，從圈中除去權最大的一條邊（圈中存在兩條以上最大權的邊，可任選其中一條），在余下的支撐子圖中重復這個步驟，一直得到一個不含圈的支撐子圖為止，這時的圖就是原賦權圖的最小支撐樹。例2，用破圈法求例1中的賦權圖的最小支撐樹。V1V3V5V6615572344

，最短電話線路的總長為15個單位。25最短路問題表述：給定一個賦權圖，對每一邊相應地有權，又有兩點，設Ｐ是Ｇ中從到的一條路，路Ｐ的權是Ｐ中所有邊的權之和，記為。最短路問題就是求從到的路中一條權最小的路Ｐ0，使上述定義中，若是有向賦權圖，則任一邊改為任一弧，其他相同。此時從到的路應是沿弧的箭頭方向首尾相接的路。5.3最短路問題26一、Dijkstra算法

狄克斯拉算法是由Dijkstra于1959年提出來，用于求解指定兩點，cc之間的最短路，或從指定點到其余各點的最短路，目前被認為是求情形下最短路問題的最好方法?；舅悸坊谝韵略恚喝簦惺菑牡降淖疃搪罚牵兄械囊粋€點，那么從到的最短路就是從沿Ｐ到的那條路。采用標號法：Ｔ標號與Ｐ標號。Ｔ標號為試探性標號，Ｐ為永久性標號。給點一個Ｐ標號時，該標號表示從到點的最短路權，點的標號不再改變。給點一個Ｔ標號時，Ｔ標號表示從到點的最短路權的上界，是一種臨時標號。凡沒有得到Ｐ標號的點都有Ｔ標號。算法每一步都把某一點的Ｔ標號改為Ｐ標號，當終點得到Ｐ標號時，全部計算結束。27Dijkstra算法基本步驟：⑴給以Ｐ標號，其余各點均給Ｔ標號，。⑵若點為得到Ｐ標號的點，考慮且為Ｔ標號。對的Ｔ標號進行如下的更改：⑶比較所有具有Ｔ標號的點，若則把最小值對應的點改為Ｐ標號，即當存在兩個以上最小者時，可同時改為Ｐ標號。若全部點均為Ｐ標號則停止。否則轉回⑵。步驟(3)，當給頂點Ｐ標號時，可以在圖的對應頂點旁標上一個記號（，），其中為從到的最短路上與鄰接的頂點，為從到的最短路長。的記號?。ǎ埃?8例2

用Dijkstra算法求圖中從的最短路12235535775１1４２３５６７解：⑴首先給以P標號給其余所有點Ｔ標號

(2)考察，由于且是Ｔ標號點，所以修改Ｔ標號為：(v1,0)在所有Ｔ標號中，，于是給Ｐ標號令，并標上（，２）。(v1,2)2912235535775１1４２３５６７(v1,0)在所有Ｔ標號中，最小，于是給Ｐ標號令，并標上（，3）。(3)考察，因且是Ｔ標號，故修改對應的Ｔ標號：(v1,3)(v1,2)30(4)考察，因且是Ｔ標號，故修改對應的Ｔ標號為：在所有Ｔ標號中，最小，于是給Ｐ標號令

，并標上（，4）。12235535775１1４２３５６７(v1,0)(v1,3)(v2,4)(v1,2)31在所有Ｔ標號中，最小，于是給Ｐ標號令

，標上（，7）。(5)考察，因且是Ｔ標號，故修改對應的Ｔ標號為：12235535775１1４２３５６７(v1,0)(v1,3)(v2,4)(v3,7)(v1,2)32在所有Ｔ標號中，最小，于是給Ｐ標號令，標上（，8）。12235535775１1４２３５６７(6)考察，因且是Ｔ標號，故修改對應的Ｔ標號為：(v1,0)(v1,3)(v2,4)(v3,7)(v5,8)(v1,2)33(7)考察，因且是Ｔ標號，故修改對應的Ｔ標號為：由于只剩最后一個Ｔ標號，所以給Ｐ標號。令，標上（，13）。由于所有頂點都標上了Ｔ標號所以計算結束。(v６,13)從到的最短路：最短路長13.12235535775１1４２３５６７(v1,0)(v1,3)(v2,4)(v3,7)(v5,8)(v1,2)34例3

設備更新問題。某企業(yè)使用一臺設備，在每年年初，都要決定是否更新。若購置新設備，要付購買費；若繼續(xù)使用舊設備，則支付維修費用。試制定一個5年更新計劃，使總支出最少。若已知設備在各年的購買費及不同機器役齡時的殘值和維修費，如下表所示：第1年第2年第3年第4年第5年購買費1112131414機器役齡0-11-22-33-44-5維修費5681118殘值4321035解：把這個問題化為最短路問題用表示第i年初購進一臺新設備，虛設一個點表示第5年底；用弧表示第i年初購的設備一直使用到第j年年初（第j-1年年低）；弧旁的數(shù)字表示第i年初購進設備，一直使用到第j年初所需支付的購買、維修的全部費用。這樣設備更新問題就變?yōu)椋呵髲牡降淖疃搪?第1年第2年第3年第4年第5年購買費1112131414機器役齡0-11-22-33-44-5維修費5681118殘值4321036第1年第2年第3年第4年第5年購買費1112131414機器役齡0-11-22-33-44-5維修費5681118殘值43210194059121314152130152841292220123456購買維修殘值費用１→２１１５４１２１→３１１１１３１９１→４１１１９２２８１→５１１３０１４０１→６１１４８０５９２→３１２５４１３２→４１２１１３２０２→５１２１９２２９２→６１２３０１４１３→４１３５４１４３→５１３１１３２１３→６１３１９２３０４→５１４５４１５４→６１４１１３２２５→６１４５４１５37

計算結果表明為最短路，路長為49。即在第1年、第3年初各購買一臺新設備為最優(yōu)決策，這時5年的總費用為49。194059121314152130152841292220123456(v1,0)(v1,12)(v1,19)(v1,28)(v3,40)(v3,49)ＴＴＴＴＴＴV1０V2∞12V3∞1919V4∞282828V5∞40404040V6∞5953494949相鄰點V1V1V1

V1V3V3Ｐ標號38右圖是輸油管道網(wǎng)，為起點，是終點，為中轉站，邊上的數(shù)表示該管道的最大輸油能力，問：（1）應如何安排各管道輸油量，才能使從到的總輸油量最大？

最大流問題是網(wǎng)絡分析中一類應用極為廣泛的問題。在交通運輸網(wǎng)絡中有人流、車流、貨物流；供水網(wǎng)絡中有水流；金融系統(tǒng)中有現(xiàn)金流；通訊系統(tǒng)中有信息流；等等。20世紀50年代Ford，F(xiàn)ulkerson建立的“網(wǎng)絡流理論”是網(wǎng)絡應用的重要組成部分。5.4最大流問題254311２１４３Ｓt352（2）如果要增加管道網(wǎng)的最大輸油量，應該優(yōu)先增加哪個管道的輸油能力?39一、基本概念網(wǎng)絡與流：我們已經(jīng)給出了網(wǎng)絡圖的概念，網(wǎng)絡圖是一種無向或有向賦權圖，在其頂點集合中指定了起點和終點，其余的點為中間點。在最大流問題中，我們所討論的網(wǎng)絡都是有向連通賦權圖，記作，稱V中的起點為發(fā)點，終點為收點，其余的點仍為中間點。對于每一個弧，對應有一個權，稱為弧的容量，簡記。所謂網(wǎng)絡上的流，是指定義在弧集合A上的一個函數(shù)，并稱為弧上的流量，簡記作。40可行流：滿足下列條件的流成為可行流：①容量限制條件：每一?、谄胶鈼l件：對于中間點，有對于發(fā)點，收點，有并稱為這個可行流的流量。可行流總是存在的，如零流，。

（2，1）（5，3）（4，3）（3，0）（1，1）（1，1）２１４３Ｓt（3，3）（5，1）（2，2）41最大流：所謂最大流問題，就是求一個流，使其流量達到最大，并且滿足以上容量限制條件和平衡條件。最大流問題是一個特殊的線性規(guī)劃問題．（2，1）（5，4）（4，４）（3，0）（1，1）（1，0）２１４３Ｓt（3，3）（5，2）（2，2）42增廣鏈：若是網(wǎng)絡中聯(lián)結發(fā)點和收點的一條鏈，且鏈的方向是從到，則與鏈的方向一致的弧叫前向弧，表示前向弧的集合；與鏈的方向相反的弧叫后向弧，表示后向弧的集合。定義1

設是一個可行流，是從到的一條鏈，若滿足下列條件，則是可行流的一條增廣鏈：①

前向弧上，，即中每一弧是非飽和弧，②

后向弧上，，即中每一弧是非零流弧。定理5

可行流是最大流，當且僅當不存在關于的增廣鏈。43（2，1）（5，3）（4，3）（3，0）（1，1）（1，1）２１４３Ｓt（3，3）（5，1）（2，2）44二、Ford-Fulkerson算法福特－富克遜算法又稱尋求最大流的標號法。前提是已有一個可行流，標號算法分2步。第1步：給頂點的標號過程。通過頂點的標號來尋找增廣鏈；第2步是調整過程，沿增廣鏈調整ｆ以增加流量。⑴標號過程每個頂點的標號包含兩部分：第1部分表明它的標號是從哪一個頂點得到，以便找出增廣鏈；第2部分是為確定增廣鏈的調整量用的。①給發(fā)點以標號；②選擇一個已標號的點，對于的所有未標號的鄰接點，如果，且，令，并給以標號；如果，且，令，并給以標號。45重復上述步驟②，直到被標上號或不再有頂點可標號為止。如果得到標號，說明存在增廣鏈，轉入調整過程；如果未獲得標號，標號過程已無法進行時，說明ｆ已是最大流。⑵調整過程令其中調整量．調整后去掉所有標號，對新的可行流重新進行標號過程。調整過程為：在增廣鏈的前向弧上加上調整量θ，后向弧上減去調整量θ，其他弧的流量不變．這樣可使總流量增加θ，即46找可行流ｆ給ＶS標號(ＶS，＋∞)Ｖt是否已

標號

是否存在已標號但未檢查的點

倒向追蹤找出增廣鏈μ

令調整量求改進的可行流不存在關于ｆ的增廣鏈ｆ即為最大流Ｖi已

標號,但未檢查．

對Ｖi

進行檢查，并對Ｖj標號:

若，且，對Ｖj標號:

，若，且，對Ｖj標號:

，是否47例4

用標號法求所示網(wǎng)絡圖的最大流?；∨缘臄?shù)是。弧不滿足標號條件．（2，2）（2，1）（5，3）（4，3）（3，3）（5，1）（3，0）（1，1）（1，1）解：經(jīng)檢查，網(wǎng)絡中的流是可行流，下面分析是否可以增加流量。（１）標號過程：①先給標號；②檢查，在弧上，所以

則的標號２１４3Ｓt（ＶＳ,+∞)（ＶＳ,4)．弧不滿足標號條件．③檢查，在弧上，所以則的標號（－Ｖ１,１）48（Ｖ4,１）（2，2）（2，1）（5，3）（4，3）（3，3）（5，1）（3，0）（1，1）（1，1）④檢查，在弧上，

給標號

２１４３Ｓt（ＶＳ,+∞)（ＶＳ,4)

在弧上．給標號⑤檢查，在弧上，所以

,

給標號．因已經(jīng)標號，故進入調整過程．（－Ｖ１,１）（Ｖ２,１）（－Ｖ2,１）49（5，1）（Ｖ4,１）（2，2）（2，1）（5，3）（4，3）（3，3）（3，0）（1，1）（1，1）２１４３Ｓt（ＶＳ,4)（－Ｖ１,１）（Ｖ２,１）（－Ｖ2,１）（ＶＳ,+∞)（2）調整過程：取定增廣鏈．前向弧上流量增加１，后向弧上流量減去１，其他不變，得可行流在進入新的循環(huán)：①給標號檢查給標號檢查，標號過程無法進行下去．所以為最大流，（2，2）（3，3）（5，2）（ＶＳ,+∞)（2，1）（5，4）（4，４）（3，0）（1，1）（1，0）２１４３Ｓt（ＶＳ,3)問題（1）：應如何安排各管道輸油量，才能使從到的總輸油量最大？答：fs1=2、fs2=3、f13=2、f24=4、f32=1、f4t=4、f3t=1.（2，1）（5，4）（4，４）（3，0）（1，1）（1，0）２１４３Ｓt（3，3）（5，2）（2，2）51截集與截量：設，我們把始點在Ｓ，終點在Ｔ中的所有弧構成的集合，記為。定義１：設網(wǎng)絡，若點集Ｖ被剖分為兩個非空集合和，使，則把弧集稱為分離，的截集。截集是從到的必徑之道。定義2

給定一截集，把截集中所有弧的容量之和稱為這個截集的容量（或稱截量），記作任何一個可行流的流量都不會超過任一截量的容量，即若對于一個可行流，網(wǎng)絡中有一個截集，使則必是最大流，而必定是網(wǎng)絡的所有截集中容量最小的一個，稱為最小截量。52

最大流量最小截量定理：任一個網(wǎng)絡中，從到的最大流的流量等于分離，的最小截集的容量。

53由上述可見，用標號法找增廣鏈找到最大流的同時，得到一個最小截集。最小截集的容量大小影響網(wǎng)絡最大流量。因此為提高總的輸送量，必須首先考慮改善最小截集中各弧的輸送能力。另一方面，一旦最小截集中弧的通過能力被降低，就會使總的輸送量減少。（2，1）（5，4）（4，４）（3，0）（1，1）（1，0）２１４３Ｓt（ＶＳ,3)（ＶＳ,+∞)（3，3）（5，2）（2，2）問題（2）：如果要增加管道網(wǎng)的最大輸油量，應該優(yōu)先增加哪個管道的輸油能力?答：cs2、c21、c13.（2，1）（5，4）（4，４）（3，0）（1，1）（1，0）２１４３Ｓt（3，3）（5，2）（2，2）練習用Dijkstra標號法求網(wǎng)絡圖起點VS到終點Vt的最短路徑，結果如下圖示：由結果之間的關系，可以知A=

，B=

，C=

，D=

。起點VS到終點Vt的最短路程為

，最短路徑為：

。起點VS到點V5的最短路程為

，最短路徑為：

。練習如下圖所示的網(wǎng)絡圖，弧上數(shù)為（）。為了使f為可行流，則f23=

；f31=

；f14=

；f4t=

。找一條增廣鏈：

；為使可行流流量增加，如何改進行可行流：

。（5，1）（3，3）（1，1）（2，f31）（4，f14）（2，f23）（2，1）（5，f4t）（3，0）s1324t575.5網(wǎng)絡計劃

20世紀50年代以來，國外陸續(xù)出現(xiàn)一些計劃管理的新方法，如關鍵路線法（CriticalPathMethod，縮寫為CPM），計劃評審方法（ProgramEvaluationReviewTechnique，縮寫為PETR）等。這些方法都是建立在網(wǎng)絡模型基礎之上，稱為網(wǎng)絡計劃技術。網(wǎng)絡計劃技術被地廣泛應用于工業(yè)、農業(yè)、國防、科研等計劃管理中，對縮短工期，節(jié)約人力、物力和財力，提高經(jīng)濟效益發(fā)揮了重要作用。我國數(shù)學家華羅庚先生將這些方法總結概括為統(tǒng)籌方法，引入中國并推廣應用。統(tǒng)籌方法的基本原理是：從任務的總進度著眼，以任務中各工作所需要的工時為時間因素；按照工作的先后順序和相互關系作出網(wǎng)絡圖，以反映任務全貌，實現(xiàn)管理過程的模型化。然后進行時間參數(shù)計算，找出計劃中的關鍵工作和關鍵路線，對任務的各項工作所需的人、財、物通過改善網(wǎng)絡計劃作出合理安排，得到最優(yōu)方案并付諸實施。通過對各種評價指標進行定量化分析，在計劃的實施過程中，進行有效的監(jiān)督與控制，以保證任務高質量地完成。58例5

某項新產(chǎn)品投產(chǎn)前全部準備工作如下表，表中列示了各工序所需時間以及它們之間的相互關系。工序工序內容緊前工序工時（周）A市場調整/4B資金籌措/10C需求分析A3D產(chǎn)品設計A6E產(chǎn)品研制D8F制定成本計劃C，E2G制定生產(chǎn)計劃F3H籌備設備B，G2I原材料準備B，G8J安裝設備H5K人員準備G2L準備開工投產(chǎn)I，J，K1問：（1）該新產(chǎn)品投產(chǎn)前全部準備工作的最短工期需要多長時間？（2）如果要提早完成工期，優(yōu)先考慮壓縮哪些工序的工作時間？60一、網(wǎng)絡圖的繪制什么是網(wǎng)絡圖：網(wǎng)絡圖是由節(jié)點、弧及權所構成的有向賦權圖。(1)用一個箭頭（弧）表示一個工序．多道工序就有多個箭頭。(2)把各個箭頭按工序間的相互制約關系，依流程方向從左向右聯(lián)系起來。(3)相鄰工序交接處畫上圓圈（節(jié)點），每個節(jié)點編上循序號，表示工序的事項。節(jié)點在箭尾表示工序的開始，節(jié)點在箭頭表示工序的完成。(4)把每道工序所需要的時間（權）標在對應的箭頭旁．２４３１６５７８４３２５５６３５５２61網(wǎng)絡圖的組成：（1）工序：指一項有具體內容，需要一定人力，物力，經(jīng)過一定時間才能完成的生產(chǎn)過程或活動過程．虛工序：不消耗資源，不需要時間，僅用以表示一個工序和另一工序之間相互依存的制約關系，是虛設的工序，用虛箭頭表示。工序代號緊前工序ＡＢＣＤ－－Ａ，ＢＢＡＢＣＤ（2）事項：指工序的開始（即開工事件）和工序的結束（完工事件）一個事項對它的前工序是完工事件，對它的后工序是開工事件。

②是工序Ａ的完工事件，是Ｂ的開工事件只有一個總的開工事件，一個總的完工事件。ＡＢ１２３62（3）路線：指網(wǎng)絡圖中從起點開始順箭頭所指方向，連續(xù)不斷到達終點為止的一條路。關鍵路線：指完成各個工序需要時間最長的路線，也稱主要矛盾線．繪制網(wǎng)絡圖的規(guī)則：(１)每個工序只出現(xiàn)一次。(２)只能有一個總起始頂點，一個總終止頂點。(３)不能有回路。(４)兩個頂點之間只能有一條弧。(５)正確表示工序之間的前行、后繼關系。(６)每一工序起始頂點編號小于終止頂點編號，所有編號從１連續(xù)編號。２４３１６５７８４３２５５６３５５２63例5

某項新產(chǎn)品投產(chǎn)前全部準備工作如下表，表中列示了各工序所需時間以及它們之間的相互關系。要求編制該項工程的網(wǎng)絡計劃。工序工序內容緊前工序工時（周）A市場調整/4B資金籌措/10C需求分析A3D產(chǎn)品設計A6E產(chǎn)品研制D8F制定成本計劃C，E2G制定生產(chǎn)計劃F3H籌備設備B，G2I原材料準備B，G8J安裝設備H5K人員準備G2L準備開工投產(chǎn)I，J，K164工序緊前工序工時（周）工序緊前工序工時（周）A/4GF3B/10HB，G2CA3IB，G8DA6JH5ED8KG2FC，E2LI，J，K1AＢＣＤＥＦＧＨＩＫＪＬ４11３６８２３２８２５１１２３４５６７８９1065二、時間參數(shù)和關鍵路線計算

計算網(wǎng)絡圖中有關的時間參數(shù)，主要目的是找出關鍵路線，為網(wǎng)絡計劃的優(yōu)化、調整和執(zhí)行提供明確的時間概念。通常把網(wǎng)絡圖中需時最長的路線叫做關鍵路線，如右圖所示網(wǎng)絡中雙箭線表示的為關鍵路線，關鍵路線上的工序稱為關鍵工序。要想使任務按期完或提前完工，就要在關鍵路線的關鍵工序上想辦法。

網(wǎng)絡圖的時間參數(shù)包括工序所需時間、事項最早、最遲時間，工序的最早、最遲時間及時差等，下面分別敘述。1234564537223466工序時間的確定工序的所需時間可記為，有以下兩種情況：⑴完成每道工序所需時間確定，在具備勞動定額資料，或者具有類似工序作業(yè)時間消耗的統(tǒng)計資料時，用對比分析來確定作業(yè)時間。⑵影響工序因素較多，作業(yè)時間難以確定，可以采用三點時間估計法來確定作業(yè)時間：a——最快可能完成時間b——最可能完成時間c——最慢可能完成時間一般情況下，可按下列公式近似計算作業(yè)時間。67

事項時間參數(shù)⑴事項最早時間事項ｊ的最早時間用表示，它表示以ｊ為始點的各工序最早可能開工的時間，也表示以ｊ為終點的各工序的最早可能完工時間。它等于從始點事項到本事項最長路線的時間長度。事項最早時間可用下列遞推公式，按照事項編號從小到大（自左向右）順序逐個計算。其中，為與事項ｊ相鄰的各緊前事項的最早時間。是工序的工時，Ａ為網(wǎng)絡圖?。üば颍┑娜w，為邊界條件．68例5中的事項最早時間：1０AＢＣＤＥＦＧＨＩＫＪＬ４３６８２３２８２５１１２３４５６７８９10８

０４182０23313223251０問（1）該新產(chǎn)品投產(chǎn)前全部準備工作的最短工期需要多長時間？答：最短工期需要32周。70⑵事項的最遲時間事項ｉ的最遲時間用表示，它表明在不影響總工期條件下，以它為終點的各工作的最遲必須完工時間，或以它為始點的工序的最遲必須開工時間。在一般情況下，把任務的最早完工時間作為任務的總工期，所示事項