上海交通大學管理科學-運籌學課件

1、第5章圖與網(wǎng)絡分析圖論的基本概念引言瑞士數(shù)學歐拉(Euler)在1736年發(fā)表了圖論方面的第一篇論文，題為“依據(jù)幾何位置 的解題方法”，解決了著名的哥尼斯堡七橋問題。哥尼斯堡城中有一條河叫普雷格爾河，該 河上有兩個島，河上有七座橋，如圖 5-1 (a)所示。當時那里的居民熱衷于這樣的問題：- 個散步者能否走過七座橋，且每座橋只走過一次，最后回到出發(fā)點。(b)歐拉用A、B、C、D四點表示河的兩岸和小島，用兩點間的聯(lián)線表示橋，如圖 5-1 (b),該 問題可歸結為：能否從任一點出發(fā)，通過每條邊一次且僅一次， 再回到該點？即一筆畫問題。 歐拉證明了這是不可能的，因為圖中每點都只與奇數(shù)條線相連。這是古

2、典圖論中的一個著名問題。運籌學中的“中國郵遞員問題”：一個郵遞員從郵局出發(fā)要走遍他所負責的每條街道去送信，問應如何選擇適當?shù)穆肪€可使所走的總路程最短。這個總是就與歐拉回路有密切的關系。圖論的第一本專著是匈牙利數(shù)學家 O.Konig著的“有限圖與無限圖的理論”，發(fā)表于1936 年。隨著科學技術的發(fā)展及電子計算機的出現(xiàn)和廣泛應用，圖論得到進一步發(fā)展， 廣泛應用于管理科學、計算機科學、心理學及工程技術管理中，并取得了豐碩的成果?；靖拍钭匀唤绾腿祟惿鐣校罅康氖挛镆约笆挛镏g的關系，?？梢杂脠D形來表示。如為了反映城市之間有沒有航班，我們可用圖5-2來示意。甲城與乙城，乙城與丙城有飛機到達，而甲、丙

3、兩城沒有直飛航班。 再如工作分配問題，我們可以用點表示每人與需要完成的工作，點間連線表示每個人可以勝任哪些工作如圖5-3所示。 TOC o 1-5 h z 圖5-2圖5-3在上面的例子中，我們關心圖中有多少個點，點與點之間有無連線。 這種圖是反映對象之間關系的一種工具。圖可分為無向圖和有向圖。兩點之間不帶箭頭的聯(lián)線為邊，兩點之間帶箭頭的聯(lián)線為弧。由點、邊構成的圖是無向圖，記GV,E由點、弧構成的圖是有向圖，記D V,A圖5-4圖5-5圖5-4 是一一個無向圖VVi,V2,V3,V4 ， E ei,e2,e3,e4 5,，7其中，eVi,V2,2Vi,V2,QV2,V364V3,V4,e5MM

4、（v1，v3）,e7v4,V4圖5-5是一個有向圖VVi ,V2,V3,V4,V5 ,V6 ,V7 ， aa1，a2,a3, a1其中，ai,，丫2,a2MM3Y3N2, a4Na ,a Y2N4 ,a6V4, V5,a7V4,V6,%V5M,a9V5,V4 ,aio丫5”6 , aii ”,V7給定一個圖G V,E , 一個點、邊的交錯序列丫口島，vi2 ,ei2, ,vik 1 ,eik 1 ,vik，如果滿足aVitMt1, t1, 2,HI，k1，則稱為一條聯(lián)結M1和Vik的鏈，記為Vi1,Vi2,Mk。對于有向圖D V,A ,從D中去掉所有弧上的箭頭，應得到一個無向圖，稱為 D的基礎

5、圖，記為G D。設Vi1,ai1,Vi2,ai2,Mk1 ,aik 1,Mk是D中的一個點弧交錯序列，如果這個序列在基礎圖G D中所對應的點邊序列是一條鏈，則稱這個點弧交錯序列是D的一條鏈。在實際問題中，往往只用圖來描述的所研究對象之間的關系還是不夠的，與圖聯(lián)系在一起的，通常還有與點或邊有關的某些數(shù)量指標，稱為“權”，權可以代表如距離、費用、通過能力（容量）等等。這種點或邊帶有某種數(shù)量指標的圖稱為網(wǎng)絡（即賦權圖）。圖的矩陣表示用矩陣表示圖對研究圖的性質及應用常是比較方便的，圖的矩陣表示方法有權矩陣、鄰定義1 網(wǎng)絡G接矩陣、關聯(lián)矩陣、回路矩陣等，這里只介紹其中兩種常用矩陣。V ,E ,其邊是vi

6、 ,vj有權wj ,構造矩陣Aaij n n其中，a。Wj0orVi,VjE其他稱矩陣A為網(wǎng)絡G的權矩陣。圖5-6表示圖的權矩陣為0924790340A 2 3 0 8 54480670560定義2 對于圖G V,E ,構造一個矩陣 A aH ,其中, ij n n aaijVi,Vj其他則稱矩陣A為圖G的鄰接矩陣。圖5-7所示圖的鄰接矩陣 A為圖5-7 TOC o 1-5 h z Vi01010V210110A v300000V400001V501100當G為無向圖時，鄰接矩陣為對稱矩陣。最短路問題最短路問題是網(wǎng)絡理論中應用最廣泛的問題之一。許多優(yōu)化問題可以使用這個模型，如設備更新、管道鋪設

7、、線路安排、廠區(qū)布局等。問題表述：給定一個賦權有向圖D V ,A ,對每一弧 aijvi,vj ,相應地有權wajWj ,又有兩點Vs,Vt V ,設p是D中Vs到Vt的一條路，路p的權是p中所有弧的權之和，記為 w p 。最短路問題就是求從 vs到vt的路中一條權最小的路 p0,w p0min w p 。pDijkstra 算法該算法是由Dijkstra于1959年提出來，用于求解指定兩點 vs、vt之間的最短路，或從 指定點Vs到其余各點的最短路，目前被認為是求wj 0情形下最短路問題的最好方法。算法的基本思路基于以下原理：若p是從Vs到vt的最短路，Vi是p中的一個點，那么從Vs沿p到V

8、i的路是從Vs到Vi的最短路。采用標號法：T標號與P標號。T標號為試探性標號，P為永久性標號。給vi點一個P 標號時，表示從Vs到Vi點的最短路權，Vi點的標號不再改變。給 Vi點一個T標號時，表示 從Vs到Vi點的估計最短路權的上界， 是一種臨時標號。凡沒有得到P標號的點都有T標號。 算法每一步都把某一點的 T標號改為P標號，當終點vt得到P標號時，全部計算結束。Dijkstra算法基本步驟:給vs以P標號,P Vs0,其余各點均給T標號，T Vi若Vi點為剛得到P標號的點，考慮Vj ,Vi ,Vj A且vj為T標號。對Vj的T標號進行如下的更改:T vj min Tvj,P Vi wj比較

9、所有具有T標號的點，把最小者 Vi改為P標號，即P vi min TVi當存在兩個以上最小者時，可同時改為P標號。若全部點均為P標號則停止。否則用V代替Vi轉回。例5.1用Dijkstra算法求圖5-8中從V1V7的最短路:首先給V1以P標號，0,給其余所有點T標號Vi,i 2, ,7由于 V1 ,V2 ,Vi,V3 ，Vi,V4A,且V2,V3,V4是T標號點，所以修改T標號為:T V2min T v2,P ViW12min,022T V3min T v3,P ViW13min,055T V4min T v4,P ViW14min,0332最小，于是令P V22。在所有T標號中，T V2V2

10、是剛得到P標號的點，故考察V2。因為V2,V3，V2,V6A,且v3 ,v6是T標號,故V3,V6新的T標號為:T V3T V6min T V3 ,P V2min T v6 , P v2W23minW26min,2,2在所有T標號中，T v43最小，故令P V43。考察v4,因v4 ,v5A，T V5在所有T標號中，T v3考察V3, V3,V5 ,T V5T V6在所有T標號中，T v5考察V5, V5,V6 ,T V6T V7在所有T標號中，T v6考察V6, V6,V7T V7min T v5 ,P v44最小，令P v34V3,V6A,min T v5 ,P v3min T v6 ,P

11、 v37最小，令P V57V5,V7A,min T v6 , P v5min T v7 , P v58最小，故令P V6Amin T v7 , P v6w45min,358ow35min8,437w36min9,459ow56min 9,7 18w57min ,7 7148。w67min 14,8 513令P V713,所有點都標上P標號，計算結束。從vV7之最短路是：V1V2V3V5V6V7 ,路長13,同時得到必到其余各點的最短路。5.2.2逐次逼近算法Dijkstra算法只適用于所有 w00的情形，當賦權有向圖中存在負權時，則算法失效。例如在圖5-9所示的賦權有向圖中，用 Dijkstr

12、a算法彳#到V1到v3最短路的權是5,但這里顯然不對；因為V1到v3的最短路是圖5-9V1V2V3,權為 3。在存在負權時，我們采取逐次逼近算法來求解最短路。為方便起見，不妨設從任一點vi到任一點Vj都有一條弧，如果在 D中，Vi,Vj A,則添加弧 Vi,Vj ,令wij。顯然，從Vs到Vj的最短路總是從Vs出發(fā)，沿著一條路到某點Vi ,再沿V ,Vj到Vj的，所以,從Vs到Vi的這條路必定是從 Vs到Vi的最短路。故有 Vs ,Vj的距離d Vs,Vj必滿足如下方程:d Vs ,Vjmin d Vs ,Vi iWij解:為了求解這個方程的解d Vs,必，d1dVs ,VjVs,V2 , ,

13、d Vs,VpWsjj 1,2,p為D的點數(shù)，令d t Vs,Vj若第k步,則 d k Vs,min d對所有j1Vs,ViWij ，1,2, ,p ,有t為迭代步數(shù)。kk 1dVs,VjdVs ,VjVj為Vs到任一點Vj的最短路權。例5-2求圖5-10所示賦權有向圖中從 V1到各點的最短路。迭代初始條件為:d1Vs,VjV1,V2V1 ,V4V1 ,V6V1 ,V8V1,V10d 1 V1 ,V321d MM1dV1 $。用表5-1表示全部計算過程。表5-1 （表中空格為）WijD(V1,Vj)V1V2V3V4V5V6V7V8t 1t 2t 3t 4V10-1-230000V2602-1-

14、5-5-5V3-30-51-2-2-2-2V48023-7-7-7V5-101-3-3V61017-1-1-1V7-105-5-5V8-3-5066當t 4時，發(fā)現(xiàn)d4V1,Vjd 3 V1,Vj j 1,2, ,8 ,表明已得到到各點Vj的最短路的權，即表中最舟-列數(shù)。如果需要知道 V1點到各點的最短路徑，可以采用“反向追蹤”的辦法。如已知，dV1,V86 ,因 dv1,V6 W6817 d v1，V8 故記下 V6,V8。 因dV1,V3W36d V1 ,V6,記下V3 ,V6,從而從V1到V8的最短路徑是V1V3V6V8。遞推公式中dt v1 ,vj實際意義為從v1到Vj點，至多含有t

15、1個中間點的最短路權。所以在含有n個點的圖中，如果不含有總權小于零的回路，求從v1到任一點的最短路權，用上述算法最多經(jīng)過 n-1次迭代必定收斂。 顯然，如果圖中含有總權小于零的回路，最短路權沒有下界。應用舉例例5-3 設備更新問題。某企業(yè)使用一臺設備，在每年年初，都要決定是否更新。若購置新設備，要付購買費；若繼續(xù)使用舊設備，則支付維修費用。試制定一個5年更新計劃，使總支出最少。若已知設備在各年的購買費及不同機器役齡時的殘值和維修費，如表5-2所示。表5-2第1年第2年第3年第4年第5年購買費1112131414機器役齡0-11-22-33-44-5維修費5681118殘值43210解：把這個問

16、題化為最短路問題用Vi表示第i年初購進一臺新設備，虛設一個點V6,表示第5年底；用弧Vi,Vj表示年年底；弧 M,Vj上的數(shù)字表示第i年初購進設備，一直使用到第j年底所需支付的購買、維修的全部費用。例如，v1,v4弧上的28是第1年初購買費11加上3年的 維修費5, 6, 8,減去了 3年役齡機器的殘值2; v2M4弧上的20 是第2年初購買費12減去機器殘 值3與使用2年維修費5,6之和，見圖5-11。V11259281940132030V4圖 5-11151522這樣設備更新問題就變?yōu)椋呵髲?V1到V6的最短路，計算結果表明V1V3V6為最短路，路長為 49。即在第1年、第3年初各購買一臺

17、新設備為最優(yōu)決策，這時5年的總費用為49。圖 5-125.3最大流問題最大流問題是一類應用極為廣泛的問題。例如在交通運輸網(wǎng)絡中有人流、車流、貨物流;第i初購的設備一直使用到第 j供水網(wǎng)絡中有水流；金融系統(tǒng)中有現(xiàn)金流；通訊系統(tǒng)中有信息流；等等。 20 世紀 50 年代Ford ， Fulkerson 建立的“網(wǎng)絡流理論”是網(wǎng)絡應用的重要組成部分。圖5-12是輸油管道網(wǎng)，Vs為起點，Vt是終點，Vi,V2,V3,V4為中轉站，弧上的數(shù)表示該管道的最大輸油能力，問應如何安排各管道輸油量，才能使從vs 到 vt 的總輸油量最大？5.3.1 基本概念與基本定理網(wǎng)絡與流定義 給一個有向圖D V,A，在V中

18、指定一點Vs為發(fā)點，另一點Vt為收點，其余的點叫中間點。對于每一個弧Vi ,Vj A ，對應有一個c Vi ,Vj 0 (簡寫為cij ) ，稱為弧的容量。這樣的 D 叫做網(wǎng)絡，記作D V,A,C 。所謂網(wǎng)絡上的流，是指定義在弧集合A上的一個函數(shù)ffVi,Vj，并稱fVi,Vj為弧 Vi ,Vj 上的流量，簡記作fij ?？尚辛髋c最大流容量限制條件：每一弧 vi,vj A0 fij cij平衡條件：對于中間點 Vi ,有fijfki(Vi ,Vj ) A(Vk ,Vi ) A對于發(fā)點 Vs ，收點Vt ，有fsifitV f(Vs,Vi ) A(Vi ,Vt ) Af 稱為這個可行流的流量?？?/p>

19、行流總是存在的， 如零流， fij 0 ， V f 0 。 所謂最大流問題， 就是求一個流f ij ，使其流量 V f 達到最大，并且滿足以上容量限制條件和平衡條件。其實最大流問題是一個特殊的線性規(guī)劃問題， 但是利用它與圖的緊密關系求解， 更為直觀簡便。增廣鏈若 是網(wǎng)絡中聯(lián)結發(fā)點Vs和收點Vt的一條鏈，且鏈的方向是從Vs到V一則與鏈的方向致的弧叫前向弧，表示前向弧的集合；與鏈的方向相反的弧叫后向弧，表示后向弧的集合。定義 設f是一個可行流,是從Vs到Vt的一條鏈，若 滿足下列條件，是可行流的一條增廣鏈?；i ,Vj上，0fijCij ,即中每一弧是非飽和弧?；i ,Vj上，0fijCij

20、,即中每一弧是非零流弧。截集與截量設S,T V,S T，我們把始點在 S,終點在T中的所有弧構成的集合，記為S,T定義給網(wǎng)絡D V,A,C ,若點集V被剖分為兩個非空集合V1和V1 ,V1 V2 V,V1 V2,使VsVi,VtVi,則把弧集Vi ,Vi稱為分離Vs,Vt的截集。從定義可知截集是從Vs到Vt的必經(jīng)之道。定義 給一截集Vi,Vi ，把截集Vi,Vi中所有弧的容量之和稱為這個截集的容量，記作 cV1 ,V1cj,Vj ViVi不難證明，任何一個可行流的流量Vf都不會超過任一截量的容量，即v fc V1 ,V1。顯然，若對于一個可行流f ,網(wǎng)絡中有一個截集 V1 V1 , v fcV

21、1 ,V1 ，則f必是最大流，而 Vi ,V1必定是D的所有截集中容量最小的一個，即最小截量。最大流量最小截量定理：任一個網(wǎng)絡D中，從Vs到Vt的最大流的流量等于分離 Vs, Vt的最小截集的容量。定理1可行流f是最大流，當且僅當不存在關于f的增廣鏈。證明 若f是最大流，設 D中存在關于f的增廣鏈 ，令min min cj fj , minfj由增廣鏈的定義，可知0,令fjfijfjfj不難驗證fj是一個可行流，且 v f 矛盾。Vi ,VjVi ,VjVi ,Vj 一v f v f ,這與f是最大流假設現(xiàn)在設D中不存在關于f的增廣鏈，證明f是最大流。令 VsVi,若ViVi ,且 fjcj,

22、則令 vjV1；若ViVi,且 與 0,則令vjV1 o因為不存在關于f的增廣鏈，故vt V1。記V1V/Vi ,于是得到一個截集 Vi ,V1 ,顯然必有CijVi,VjVi ,Vifij-0Vi,VjVi ,Vi所以，v fcVi ,Vi 。于是f必是最大流，定理得證。定理i為我們提供了尋求網(wǎng)絡最大流的一個方法。若可行流f中存在增廣鏈，說明還有潛力可挖，只須沿增廣鏈調整流量，得到一個流量增大的新的可行流；否則f是最大流。而判別是否存在增廣鏈，可以根據(jù)vt是否屬于V1來進行。5.3.2 尋求最大流的標號法(Ford , Fulkerson )設已有一個可行流， 標號算法分2步：第i步是標號過

23、程，通過標號來尋找增廣鏈；第2步是調整過程，沿增廣鏈調整f以增加流量。標號過程每個標號點的標號包含兩部分：第i個標號明它的標號從哪一點得到，以便找出增廣鏈;第2個標號是為確定增廣鏈的調整量用的。給發(fā)點vs以標號 ，；選擇一個已標號的點 Vi ,對于Vi的所有未標號的鄰接點 Vj,如果Vi，VjA,且fjcj ,令 l Vj min l Vi ,cj fj,并給 Vj 以標號 Vi ,lVj ；如果Vj ,vA,且fj 0 ,令 l Vjmin l Vi ,cj ,并給 Vj 以標號 vJ Vj 。重復上述步驟，直到 Vt被標上號或不再有頂點可標號為止。如果Vt得到標號，說明存在增廣鏈，轉入調整

24、過程；若Vt未獲得標號，標號過程已無法進行時，說明 f已是最大流。調整過程fijVi ,Vj令 fijfijVi ,VjfijVi,Vj 一調整量 l Vt ,去掉所有標號，對新的可行流fij重新進行標號過程。cij , f ij V圖 5-13例5-4用標號法求圖5-13所示網(wǎng)絡的最大流?；∨缘臄?shù)是解：經(jīng)檢查，網(wǎng)絡中的流是可行流，下面分析是否可以增加流量。（一） 標號過程1、首先給Vs標上 ，；2、檢查 vs ，在弧vs,v1上， fs1 1cs15則v1的標號為v1,lv1，其中l(wèi) v1 min l vs , cs1 fs1 min ,5 14 。在弧vs1 ,v2 上， fs2cs23

25、，不滿足標號條件。3、檢查v1 ，在弧 v1 ,v3 上， f132c13 ，不滿足標號條件。在弧v2,v1 上， TOC o 1-5 h z f211 0 ，則v2的標號為v1 ,lv2， lv2min lv1,f21min 4,11 。檢查v2， 在 弧 v2 ,v4 上 ， f243c244 ， 則 給v4標號v2,lv4，l v4 min l v2 , c24f24min 1,11 。 在 弧 v3 ,v2 上 ，f3210 ， 給 v3 標 號v2, v3， l v3min l v2 , f32min 1,11。5、在v3 ,v4 中任選一個進行檢查，例如，在弧v4 ,vt上，f4t

26、3c4t5 ，給vt 標號v4,l vt ， l vtmin l v4 , c4t f4t min 1, 5 31 。因 vt 有了標號，故轉入調整過程。（二）調整過程按點的第一個標號找到一條增廣鏈，如圖 5-14 中雙箭線所示。則見：vs ,v1 , v2,v4 , v4,vtv2 ,v1按 1 ，在增廣鏈 上調整 f 。 TOC o 1-5 h z f s1f s1112上：f24f 24314f4tf4t314上：f21f21110其余的 fij 不變。調整后得到圖 5-15 所示的可行流，對這個可行流進行標號，尋找增廣鏈。圖 5-15開始給vs標號,檢查vs ,給Vi標以vs,3 ,檢

27、查Vi,弧Vi ,V3上，fi3C13,弧V2,Vi上，f21 0,均不符合條件，標號過程無法繼續(xù)下去，算法結束。這時圖5-15可行流即最大流。最大流為：v ffsi fs2 3 2 5。與此同時可找到最小截集Vi,Vi ,其中Vi為標號點集，即Vvs,vi ,Vi為未標號點集，Viv2 ,v3 ,v4 ,v5 ,截集Vi ,Vivs,v2 , vi ,v3 ,最小截量為 5。由上述可見，用標號法找增廣鏈找到最大流的同時，得到一個最小截集。最小截集的容量大小影響網(wǎng)絡最大流量。因此為提高總的輸送量，必須首先考慮改善最小截集中各弧的輸送能力。另一方面，一旦最小截集中弧的通過能力被降低，就會使總的輸

28、送量減少。5.4網(wǎng)絡計劃20世紀50年代以來，國外陸續(xù)出現(xiàn)一些計劃管理的新方法，如關鍵路線法（Critical PathMethod ,縮寫為 CPM）,計劃評審方法（Program Evaluation Review Technique，縮寫為 PETR） 等。這些方法都是建立在網(wǎng)絡模型基礎之上，稱為網(wǎng)絡計劃技術，廣泛應用于工業(yè)、農(nóng)業(yè)、 國防、科研等計劃管理中，對縮短工期，節(jié)約人力、物力和財力，提高經(jīng)濟效益發(fā)揮了重要 作用。我國數(shù)學家華羅庚先生將這些方法總結概括為統(tǒng)籌方法，引入中國并推廣應用。 統(tǒng)籌方法的基本原理是：從需要管理的任務的總進度著眼，以任務中各工作所需要的工時為時間因素，按照工作

29、的先后順序和相互關系作出網(wǎng)絡圖，以反映任務全貌，實現(xiàn)管理過程的模型化。然后進行時間參數(shù)計算，找出計劃中的關鍵工作和關鍵路線，對任務的各項工作所需的人、 財、物通過改善網(wǎng)絡計劃作出合理安排，得到最優(yōu)方案并付諸實施。通過對各種評價指標進行定量化分析，在計劃的實施過程中，進行有效的監(jiān)督與控制，以保證任務高質量地完成。網(wǎng)絡圖網(wǎng)絡圖是由節(jié)點、弧及權所構成的有向圖，即有向的賦權圖。節(jié)點表示事項，弧表示工序(活動)。工序是在工藝技術和組織管理上相對獨立的工作或活動，需要一定的時間與資源，而事項則表示一個或若干工序的開始或結束，是相繼工序的分界點。 權表示為完成某個工序所需要的時間或資源等數(shù)據(jù)。例如某工序a可

30、以表示為： 正j,6為箭頭節(jié)點，表示工序 a開始，Q為箭頭尾節(jié)-a -點，表示工序a結束，5為完成本工序所需時間。網(wǎng)絡圖是有向圖，按照工藝流程的順序，規(guī)定工序從左向右排列，再給節(jié)點統(tǒng)一編號，節(jié)點由小到大編號。對任一工序i, j來講，要求j i。始點編號可以從1開始。在繪制網(wǎng)絡圖時，還要注意以下規(guī)則:網(wǎng)絡圖只能有一個總起點事項，一個總終點事項。網(wǎng)絡圖不能有缺口和回路。兩節(jié)點i ,j之間只能有一條弧。正確表示工作之間的前行、后繼關系。如圖5-16表示a,b兩工序結束后，c,d兩工序才開 始。a,b為c,d的緊前工序，c,d為a,b的緊后工序。虛工序的應用。如果a,b,c,d的工序關系是：c必須在a

31、,b均完成后才 能開工，而d只要在b完成后即可開工。 也就是說，a,b是 c的緊前工序，而只有 b是d的緊前工序。這樣必須用圖 5-17來表示，其中一是一個虛工序，只表示、兩 節(jié)點的銜接關系，不需要人力、物力等資源和時間。虛工序還可以用于正確表示平行與交叉作業(yè)。一道工序分為幾道工序同時進行，稱為平行作業(yè)。如圖5-18 (a)中市場調研需12天，如增加人力分為3組同時進行，可以畫為5-18(b)。(a)(b)圖 5-18a與工作b分別為挖溝和埋管子,兩個或兩個以上的工作交叉進行，稱為交叉作業(yè)。如工作 那么它們的關系可以是挖一段，埋一段，不必等溝全部挖好再埋。這樣，我們可用圖5-19來表示交叉作業(yè)

32、。根據(jù)上述規(guī)則繪制網(wǎng)絡圖，是為了保證網(wǎng)絡圖的正 確性。此外，為了使圖面布局合理，層次分明，條理清 楚，還要注意畫圖技巧。避免弧的交叉，盡可能將關鍵 路線布置在中心位置，將聯(lián)系緊密的工序布置在相近的位置。例5-5某項新產(chǎn)品投產(chǎn)前全部準備工作（如表5-3）列示各工序與所需時間以及它們之間的相互關系。要求編制該項工程的網(wǎng)絡計劃。表5-3工序工序內(nèi)容緊前工序工時（周）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根據(jù)以上規(guī)則，繪制的網(wǎng)絡

33、圖如5-20所示。圖 5-215.4.2時間參數(shù)計算計算網(wǎng)絡圖中有關的時間參數(shù)，主要目的是找出關鍵路線，為網(wǎng)絡計劃的優(yōu)化、調整和執(zhí)行提供明確的時間概念。通常把網(wǎng)絡圖中需時最長的路線叫做關鍵路線，如圖 5-21所示網(wǎng)絡中雙箭線表示的為關鍵路線，關鍵路線上的工序稱為關鍵工序。要想使任務按期完或提前完工，就要在關鍵 路線的關鍵工序上想辦法。網(wǎng)絡圖的時間參數(shù)包括工序所需時間、事項最早、最遲時間，工序的最早、最遲時間及 時差等，下面分別敘述。、工序時間t i, j的確定工序i,j的所需時間可記為t i, j ,有以下兩種情況：完成工序所需時間確定，只給出一個時間值。在具備勞動定額資料的條件下，或者在具有

34、類似工序的作業(yè)時間消耗的統(tǒng)計資料時，用對比分析來確定作業(yè)時間。在影響工序因素較多，作業(yè)時間難以準確估計時，可以采用三點時間估計法來確定作業(yè)時間：a最快可能完成時間m 最可能完成時間b 最慢可能完成時間一般情況下，可按下列公式近似計算作業(yè)時間。a 4mb ti，j22 b a 6概率型網(wǎng)絡圖與確定型網(wǎng)絡圖在工時確定后，對其他時間參數(shù)的計算基本相同。二、事項時間參數(shù)事項最早時間tE j事項j的最早時間用tE j表示，它表示以j為始點的各工序最早可能開始的時間，也 表示以j為終點的各工序的最早可能完成時間。 它等于從始點事項起到本事項最長路線的時 間長度。事項最早時間可用下列遞推公式，按照事項編號從

35、小到大順序逐個計算。tE 10tE j max t E i t i, ji式中，tE i為事項j相鄰的各緊前事項的最早時間。事項的最遲時間tL i事項i的最遲時間用tL i表示，它表明在不影響任務總工期條件下，以它為始點的工序的最遲必須開始時間，或以它為終點的各工作的最遲必須完成時間。在一般情況下，把任務的最早完工時間作為任務的總工期，所示事項最遲時間的計算方法如下：tL n tE nn為終點事項tL imjn 1 j t i,jtL i為事項i相鄰的各緊后事項的最遲時間，它的計算從終點事項開始，按編號由大到小的順序逐個計算。三、工序的時間參數(shù)工序的最早可能開始時間和最早可能完工時間一個工序i

36、,j的最早可能開工時間用tESi,j表示，任何一個工序都必須在其所有緊前工序全部完工后才能開始。工序i,j的最早可能完工時間用tEF i ,j表示，它表示工作按最早開工時間開始所能達到的完工時間，計算公式如下：tES 1,j0tES i, jmax tES k,it k,iktEF i,jtES i,jt i,j工序 i , j 的最早可能開工時間 tES i , j 等于事項最早時間 t E i 。工序的最遲必須開工時間與最遲必須完工時間一個工序 i , j 的最遲必須開工時間用 tLS i , j 表示，它是工序i ,j 在不影響整個任務如期完成的前提下， 必須開始的最晚時間。 工序 i

37、, j 最遲必須完工時間用 t LF i , j 表示， 它表示工作 i , j 按最遲時間開工，所能達到的完工時間。tLF i,n tE ntLS i,j min tLS j,k t j ,kktLF i,j tLS i,j t i,j工序 i , j 最遲必須完工時間tLF i , j 等于事項的最遲時間 t L j四、時差。工序的時差，又稱為工序的機動時間，工序時差分兩種：工序總時差R i , j在不影響工程最早結束時間的條件下，工序最早開始（或結束）時間可以推遲的時間：Ri,j tLF i,j tEF i,j工序單時差r i , j不影響緊后工序最早開始時間的條件下，工序最早結束時間可

38、以推遲的時間：r i ,j tES j,k tEF i, j式中， tES j ,k 為工序 i , j 的緊后工序的最早開始時間。總時差為零的工序， 開始和結束的時間沒有一點機動的余地， 由這些工序所組成的路線就是網(wǎng)絡中的關鍵路線，這些工序就是關鍵工序。例 5-6 ：確定圖 5-20 所示網(wǎng)絡的關鍵路線。解：先用圖上計算法求解，再用表上計算法驗證。根據(jù)圖5-20的資料，先計算各事項的時間參數(shù)。事項時間如總開工事項，tE 10 ,將結果填入圖中編號上方空格匚口的左邊。逐個計算事項最早時間，得到思元工事項，tE 1032 ,說明整個工作需要再從后面開文臺計算各事項最遲時間，如總完工事項的tL 1

39、0tL 7 min tL 9 t 7,9 ,tL 8 t 7,8 min 31將結果填入編號上方空格 匚口右邊。工序時間工序時間內(nèi) 4 種：tES i, j ,tEF i,j ,tLS i,j ,tLF i,j ,用圖標 表示在圖5-22上。(H(3N|20211047232周的時間完成。32 ,事項的8,26 223他表不，計算結果奉或3132林(3秘0K2L 1聲八 社5 k263y小石、B323/ 13 圖 5-22時差根據(jù)圖5-22中的結果，可以求出各工序的總時差。即：一一一一一一一一，總工期為x-T-xH 飛軍口M42V由總時差為0的工序組成關鍵路線，32周。表5-4用來計算網(wǎng)絡時間

40、，并標示出關鍵工序。表5-4工序t i,jtES i，jtEF i , jtLS i,jtLF i,jR i,j關鍵工序A404040VB10010132313xC347151811xD64104100VE8101810180VF2182018200VC3202320230V虛工序0232323230VH2232524261xI8233123310VJ5233026311xK2252529316xL1313231320V5.4.3網(wǎng)絡優(yōu)化繪制網(wǎng)絡圖，計算網(wǎng)絡時間和確定關鍵路線，得到一個初始的計劃方案。從工期、成本、 資源等方面對初步方案進一步的改善和調整，以求得最佳效果，就是網(wǎng)絡優(yōu)化。目前尚未

41、有能全面反映工期、成本、 資源的綜合數(shù)學模型，因此，網(wǎng)絡優(yōu)化問題是根據(jù)實際情況分為時 間優(yōu)化、時間-資源優(yōu)化和時間-費用優(yōu)化。1、時間優(yōu)化根據(jù)對計劃進度的要求， 縮短工程完工時間。 可以采取措施：把串聯(lián)工序改為平行或交 叉工序，縮短關鍵工序的作業(yè)時間； 充分利用非關鍵工序的時差， 減少這些作業(yè)的人力、資 源用于關鍵工序，縮短關鍵工序的作業(yè)時間。2、時間-資源優(yōu)化在編制網(wǎng)絡計劃安排工程進度時，考慮時間優(yōu)化的同時，盡量合理地利用有限的資源。具體的要求和做法是：優(yōu)先安排關鍵工序所需要的資源；利用非關鍵工序的總時差，錯開各工序的開始時間，拉平資源需要量的高峰；綜合考慮資源和時間，必要時，可適當?shù)赝七t工

42、程完工時間。在優(yōu)化時，通常將計劃的各主要資源需要量按日程排出，再按以上方法，使各主要資源的日負荷相對平衡。 但是由于一項工程所包含的工序繁多，涉及到的資源利用情況復雜， 需 要多次綜合平衡，才能得到在時間進度和資源利用等方面都比較合理的計劃方案。3、時間-費用優(yōu)化時間-費用優(yōu)化要研究和解決的問題是決定合理的工程完工時間，使費用最省，或者以合理的費用代價完成趕工作任務。工程費用包括兩大類:直接費用是完成各項工作直接所需人力、資源設備費用；為縮短工序的作業(yè)時間，需要采取一定的技術組織措施，相應會增加一部分直接費用。間接費用是指管理費、辦工費等，常按施工時間長短分攤。完成工程項目的直接費用、間接費用、總費用與工程完工時間的關系,般情況下如圖5-23所示。顯然，在網(wǎng)絡計劃中，最低成本日程具有重要意義。因此要計算網(wǎng)絡計劃的不同完工期相應的總費用，以求得成本最低的日程安排，即最低成本日程。下面舉例說明最低成本日程計劃。例5-7:已知網(wǎng)絡計劃各工序的正常工時、極限工時及相應費用如表5-5,網(wǎng)絡圖如圖 5-24。表5-5工序正常工時極限工時成本斜率 （元/天）時間（天）費用（元）時間（天）費用（元）一245000167000250一3090001810200100一224000184800200一26100002410300150一248000209000250一1854