第5章 圖與網(wǎng)絡(luò)分析5.1 圖論的基本概念5.1.1 引言瑞士數(shù)學(xué)歐拉（Euler）在1736年發(fā)表了圖論方面的第一篇論文，題為“依據(jù)幾何位置的解題方法”，解決了著名的哥尼斯堡七橋問題。哥尼斯堡城中有一條河叫普雷格爾河，該河上有兩個島，河上有七座橋，如圖5-1（a）所示。當(dāng)時那里的居民熱衷于這樣的問題：一個散步者能否走過七座橋，且每座橋只走過一次，最后回到出發(fā)點。歐拉用A、B、C、D四點表示河的兩岸和小島，用兩點間的聯(lián)線表示橋，如圖5-1（b），該問題可歸結(jié)為：能否從任一點出發(fā)，通過每條邊一次且僅一次，再回到該點？即一筆畫問題。歐拉證明了這是不可能的，因為圖中每點都只與奇數(shù)條線相連。這是古典圖論中的一個著名問題。運籌學(xué)中的“中國郵遞員問題”：一個郵遞員從郵局出發(fā)要走遍他所負責(zé)的每條街道去送信，問應(yīng)如何選擇適當(dāng)?shù)穆肪€可使所走的總路程最短。這個總是就與歐拉回路有密切的關(guān)系。圖論的第一本專著是匈牙利數(shù)學(xué)家O.Konig著的“有限圖與無限圖的理論”，發(fā)表于1936年。隨著科學(xué)技術(shù)的發(fā)展及電子計算機的出現(xiàn)和廣泛應(yīng)用，圖論得到進一步發(fā)展，廣泛應(yīng)用于管理科學(xué)、計算機科學(xué)、心理學(xué)及工程技術(shù)管理中，并取得了豐碩的成果。5.1.2 基本概念自然界和人類社會中，大量的事物以及事物之間的關(guān)系，?？梢杂脠D形來表示。如為了反映城市之間有沒有航班，我們可用圖5-2來示意。甲城與乙城，乙城與丙城有飛機到達，而甲、丙兩城沒有直飛航班。再如工作分配問題，我們可以用點表示每人與需要完成的工作，點間連線表示每個人可以勝任哪些工作如圖5-3所示。在上面的例子中，我們關(guān)心圖中有多少個點，點與點之間有無連線。這種圖是反映對象之間關(guān)系的一種工具。圖可分為無向圖和有向圖。兩點之間不帶箭頭的聯(lián)線為邊，兩點之間帶箭頭的聯(lián)線為弧。由點、邊構(gòu)成的圖是無向圖，記由點、弧構(gòu)成的圖是有向圖，記圖5-4是一個無向圖，其中，圖5-5是一個有向圖，其中，給定一個圖，一個點、邊的交錯序列，如果滿足，則稱為一條聯(lián)結(jié)和的鏈，記為。對于有向圖，從中去掉所有弧上的箭頭，應(yīng)得到一個無向圖，稱為的基礎(chǔ)圖，記為。設(shè)是中的一個點弧交錯序列，如果這個序列在基礎(chǔ)圖中所對應(yīng)的點邊序列是一條鏈，則稱這個點弧交錯序列是的一條鏈。在實際問題中，往往只用圖來描述的所研究對象之間的關(guān)系還是不夠的，與圖聯(lián)系在一起的，通常還有與點或邊有關(guān)的某些數(shù)量指標(biāo)，稱為“權(quán)”，權(quán)可以代表如距離、費用、通過能力（容量）等等。這種點或邊帶有某種數(shù)量指標(biāo)的圖稱為網(wǎng)絡(luò)（即賦權(quán)圖）。5.1.3 圖的矩陣表示用矩陣表示圖對研究圖的性質(zhì)及應(yīng)用常是比較方便的，圖的矩陣表示方法有權(quán)矩陣、鄰接矩陣、關(guān)聯(lián)矩陣、回路矩陣等，這里只介紹其中兩種常用矩陣。定義1網(wǎng)絡(luò)，其邊是有權(quán)，構(gòu)造矩陣其中，稱矩陣為網(wǎng)絡(luò)的權(quán)矩陣。圖5-6表示圖的權(quán)矩陣為定義2對于圖，構(gòu)造一個矩陣，其中，則稱矩陣為圖的鄰接矩陣。圖5-7所示圖的鄰接矩陣為當(dāng)為無向圖時，鄰接矩陣為對稱矩陣。5.2 最短路問題最短路問題是網(wǎng)絡(luò)理論中應(yīng)用最廣泛的問題之一。許多優(yōu)化問題可以使用這個模型，如設(shè)備更新、管道鋪設(shè)、線路安排、廠區(qū)布局等。問題表述：給定一個賦權(quán)有向圖，對每一弧，相應(yīng)地有權(quán)，又有兩點，設(shè)是中到的一條路，路的權(quán)是中所有弧的權(quán)之和，記為。最短路問題就是求從到的路中一條權(quán)最小的路，。5.2.1 Dijkstra算法該算法是由Dijkstra于1959年提出來，用于求解指定兩點、之間的最短路，或從指定點到其余各點的最短路，目前被認為是求情形下最短路問題的最好方法。算法的基本思路基于以下原理：若是從到的最短路，是中的一個點，那么從沿到的路是從到的最短路。采用標(biāo)號法：標(biāo)號與標(biāo)號。標(biāo)號為試探性標(biāo)號，為永久性標(biāo)號。給點一個標(biāo)號時，表示從到點的最短路權(quán)，點的標(biāo)號不再改變。給點一個標(biāo)號時，表示從到點的估計最短路權(quán)的上界，是一種臨時標(biāo)號。凡沒有得到標(biāo)號的點都有標(biāo)號。算法每一步都把某一點的標(biāo)號改為標(biāo)號，當(dāng)終點得到標(biāo)號時，全部計算結(jié)束。Dijkstra算法基本步驟：給以標(biāo)號，其余各點均給標(biāo)號，。若點為剛得到標(biāo)號的點，考慮，且為標(biāo)號。對的標(biāo)號進行如下的更改： 比較所有具有標(biāo)號的點，把最小者改為標(biāo)號，即當(dāng)存在兩個以上最小者時，可同時改為標(biāo)號。若全部點均為標(biāo)號則停止。否則用代替轉(zhuǎn)回。例5.1 用Dijkstra算法求圖5-8中從的最短路解：首先給以標(biāo)號，給其余所有點標(biāo)號，由于，且是標(biāo)號點，所以修改標(biāo)號為：在所有標(biāo)號中，最小，于是令。是剛得到標(biāo)號的點，故考察。因為，且是標(biāo)號，故新的標(biāo)號為：在所有標(biāo)號中，最小，故令。考察，因，在所有標(biāo)號中，最小，令?？疾?，在所有標(biāo)號中，最小，令?？疾?，在所有標(biāo)號中，最小，故令。考察，令，所有點都標(biāo)上標(biāo)號，計算結(jié)束。從之最短路是：，路長13，同時得到到其余各點的最短路。5.2.2 逐次逼近算法Dijkstra算法只適用于所有的情形，當(dāng)賦權(quán)有向圖中存在負權(quán)時，則算法失效。例如在圖5-9所示的賦權(quán)有向圖中，用Dijkstra算法得到到最短路的權(quán)是5，但這里顯然不對；因為到的最短路是，權(quán)為3。在存在負權(quán)時，我們采取逐次逼近算法來求解最短路。為方便起見，不妨設(shè)從任一點到任一點都有一條弧，如果在中，則添加弧，令。顯然，從到的最短路總是從出發(fā)，沿著一條路到某點，再沿到的，所以，從到的這條路必定是從到的最短路。故有，的距離必滿足如下方程：為了求解這個方程的解，為的點數(shù)，令，為迭代步數(shù)。若第步，對所有，有則為到任一點的最短路權(quán)。例5-2 求圖5-10所示賦權(quán)有向圖中從到各點的最短路。解：迭代初始條件為：有，。用表5-1表示全部計算過程。表5-1 （表中空格為）ji wijD(t)(v1,vj)V1V2V3V4V5V6V7V8V10-1-230000V2602-1-5-5-5V3-30-51-2-2-2-2V48023-7-7-7V5-101-3-3V61017-1-1-1V7-105-5-5V8-3-5066 當(dāng)時，發(fā)現(xiàn)，表明已得到到各點的最短路的權(quán)，即表中最后一列數(shù)。如果需要知道點到各點的最短路徑，可以采用“反向追蹤”的辦法。如已知，因故記下。因，記下，從而從到的最短路徑是。遞推公式中實際意義為從到點，至多含有個中間點的最短路權(quán)。所以在含有個點的圖中，如果不含有總權(quán)小于零的回路，求從到任一點的最短路權(quán)，用上述算法最多經(jīng)過-1次迭代必定收斂。顯然，如果圖中含有總權(quán)小于零的回路，最短路權(quán)沒有下界。應(yīng)用舉例例5-3設(shè)備更新問題。某企業(yè)使用一臺設(shè)備，在每年年初，都要決定是否更新。若購置新設(shè)備，要付購買費；若繼續(xù)使用舊設(shè)備，則支付維修費用。試制定一個5年更新計劃，使總支出最少。若已知設(shè)備在各年的購買費及不同機器役齡時的殘值和維修費，如表5-2所示。表5-2第1年第2年第3年第4年第5年購買費1112131414機器役齡0-11-22-33-44-5維修費5681118殘值43210解：把這個問題化為最短路問題用表示第年初購進一臺新設(shè)備，虛設(shè)一個點，表示第5年底；用弧表示第初購的設(shè)備一直使用到第年年底；弧上的數(shù)字表示第年初購進設(shè)備，一直使用到第年底所需支付的購買、維修的全部費用。例如，弧上的28是第1年初購買費11加上3年的維修費5，6，8，減去了3年役齡機器的殘值2；弧上的20是第2年初購買費12減去機器殘值3與使用2年維修費5，6之和，見圖5-11。這樣設(shè)備更新問題就變?yōu)椋呵髲牡降淖疃搪?，計算結(jié)果表明為最短路，路長為49。即在第1年、第3年初各購買一臺新設(shè)備為最優(yōu)決策，這時5年的總費用為49。5.3最大流問題最大流問題是一類應(yīng)用極為廣泛的問題。例如在交通運輸網(wǎng)絡(luò)中有人流、車流、貨物流；供水網(wǎng)絡(luò)中有水流；金融系統(tǒng)中有現(xiàn)金流；通訊系統(tǒng)中有信息流；等等。20世紀50年代Ford ，F(xiàn)ulkerson建立的“網(wǎng)絡(luò)流理論”是網(wǎng)絡(luò)應(yīng)用的重要組成部分。圖5-12是輸油管道網(wǎng)，為起點，是終點，為中轉(zhuǎn)站，弧上的數(shù)表示該管道的最大輸油能力，問應(yīng)如何安排各管道輸油量，才能使從到的總輸油量最大？5.3.1 基本概念與基本定理網(wǎng)絡(luò)與流定義給一個有向圖，在中指定一點為發(fā)點，另一點為收點，其余的點叫中間點。對于每一個弧，對應(yīng)有一個（簡寫為），稱為弧的容量。這樣的叫做網(wǎng)絡(luò)，記作。所謂網(wǎng)絡(luò)上的流，是指定義在弧集合上的一個函數(shù)，并稱為弧上的流量，簡記作?？尚辛髋c最大流容量限制條件：每一弧平衡條件：對于中間點，有對于發(fā)點，收點，有稱為這個可行流的流量?？尚辛骺偸谴嬖诘?，如零流，。所謂最大流問題，就是求一個流，使其流量達到最大，并且滿足以上容量限制條件和平衡條件。其實最大流問題是一個特殊的線性規(guī)劃問題，但是利用它與圖的緊密關(guān)系求解，更為直觀簡便。增廣鏈若是網(wǎng)絡(luò)中聯(lián)結(jié)發(fā)點和收點的一條鏈，且鏈的方向是從到，則與鏈的方向一致的弧叫前向弧，表示前向弧的集合；與鏈的方向相反的弧叫后向弧，表示后向弧的集合。定義設(shè)是一個可行流，是從到的一條鏈，若滿足下列條件，是可行流的一條增廣鏈。 弧上，即中每一弧是非飽和弧。 弧上，即中每一弧是非零流弧。截集與截量設(shè)，我們把始點在，終點在中的所有弧構(gòu)成的集合，記為。定義給網(wǎng)絡(luò)，若點集被剖分為兩個非空集合和， ，使，則把弧集稱為分離，的截集。從定義可知截集是從到的必經(jīng)之道。定義給一截集，把截集中所有弧的容量之和稱為這個截集的容量，記作不難證明，任何一個可行流的流量都不會超過任一截量的容量，即。顯然，若對于一個可行流，網(wǎng)絡(luò)中有一個截集，則必是最大流，而必定是的所有截集中容量最小的一個，即最小截量。最大流量最小截量定理：任一個網(wǎng)絡(luò)中，從到的最大流的流量等于分離，的最小截集的容量。定理1可行流是最大流，當(dāng)且僅當(dāng)不存在關(guān)于的增廣鏈。證明若是最大流，設(shè)中存在關(guān)于的增廣鏈，令由增廣鏈的定義，可知，令不難驗證是一個可行流，且，這與是最大流假設(shè)矛盾?，F(xiàn)在設(shè)中不存在關(guān)于的增廣鏈，證明是最大流。令，若，且，則令；若，且，則令。因為不存在關(guān)于的增廣鏈，故。記，于是得到一個截集，顯然必有所以，。于是必是最大流，定理得證。定理1為我們提供了尋求網(wǎng)絡(luò)最大流的一個方法。若可行流中存在增廣鏈，說明還有潛力可挖，只須沿增廣鏈調(diào)整流量，得到一個流量增大的新的可行流；否則是最大流。而判別是否存在增廣鏈，可以根據(jù)是否屬于來進行。5.3.2 尋求最大流的標(biāo)號法（Ford，F(xiàn)ulkerson）設(shè)已有一個可行流，標(biāo)號算法分2步：第1步是標(biāo)號過程，通過標(biāo)號來尋找增廣鏈；第2步是調(diào)整過程，沿增廣鏈調(diào)整以增加流量。標(biāo)號過程每個標(biāo)號點的標(biāo)號包含兩部分：第1個標(biāo)號明它的標(biāo)號從哪一點得到，以便找出增廣鏈；第2個標(biāo)號是為確定增廣鏈的調(diào)整量用的。 給發(fā)點以標(biāo)號； 選擇一個已標(biāo)號的點，對于的所有未標(biāo)號的鄰接點，如果，且，令，并給以標(biāo)號；如果，且，令，并給以標(biāo)號。 重復(fù)上述步驟，直到被標(biāo)上號或不再有頂點可標(biāo)號為止。如果得到標(biāo)號，說明存在增廣鏈，轉(zhuǎn)入調(diào)整過程；若未獲得標(biāo)號，標(biāo)號過程已無法進行時，說明已是最大流。調(diào)整過程令調(diào)整量，去掉所有標(biāo)號，對新的可行流重新進行標(biāo)號過程。例5-4 用標(biāo)號法求圖5-13所示網(wǎng)絡(luò)的最大流。弧旁的數(shù)是。解：經(jīng)檢查，網(wǎng)絡(luò)中的流是可行流，下面分析是否可以增加流量。（一） 標(biāo)號過程1、 首先給標(biāo)上；2、檢查，在弧上，則的標(biāo)號為，其中。在弧上，不滿足標(biāo)號條件。3、檢查，在弧上，不滿足標(biāo)號條件。在弧上，則的標(biāo)號為，。4、檢查，在弧上，則給標(biāo)號，。在弧上，給標(biāo)號，。5、在中任選一個進行檢查，例如，在弧 上，給標(biāo)號，。因有了標(biāo)號，故轉(zhuǎn)入調(diào)整過程。（二）調(diào)整過程按點的第一個標(biāo)號找到一條增廣鏈，如圖5-14中雙箭線所示。則見：按，在增廣鏈上調(diào)整。上：上：其余的不變。調(diào)整后得到圖5-15所示的可行流，對這個可行流進行標(biāo)號，尋找增廣鏈。開始給標(biāo)號，檢查，給標(biāo)以，檢查，弧上，弧上，均不符合條件，標(biāo)號過程無法繼續(xù)下去，算法結(jié)束。這時圖5-15 可行流即最大流。最大流為：。與此同時可找到最小截集，其中為標(biāo)號點集，即，為未標(biāo)號點集，截集，最小截量為5。由上述可見，用標(biāo)號法找增廣鏈找到最大流的同時，得到一個最小截集。最小截集的容量大小影響網(wǎng)絡(luò)最大流量。因此為提高總的輸送量，必須首先考慮改善最小截集中各弧的輸送能力。另一方面，一旦最小截集中弧的通過能力被 降低，就會使總的輸送量減少。5.4 網(wǎng)絡(luò)計劃20世紀50年代以來，國外陸續(xù)出現(xiàn)一些計劃管理的新方法，如關(guān)鍵路線法（Critical Path Method，縮寫為CPM），計劃評審方法（Program Evaluation Review Technique，縮寫為PETR）等。這些方法都是建立在網(wǎng)絡(luò)模型基礎(chǔ)之上，稱為網(wǎng)絡(luò)計劃技術(shù)，廣泛應(yīng)用于工業(yè)、農(nóng)業(yè)、國防、科研等計劃管理中，對縮短工期，節(jié)約人力、物力和財力，提高經(jīng)濟效益發(fā)揮了重要作用。我國數(shù)學(xué)家華羅庚先生將這些方法總結(jié)概括為統(tǒng)籌方法，引入中國并推廣應(yīng)用。統(tǒng)籌方法的基本原理是：從需要管理的任務(wù)的總進度著眼，以任務(wù)中各工作所需要的工時為時間因素，按照工作的先后順序和相互關(guān)系作出網(wǎng)絡(luò)圖，以反映任務(wù)全貌，實現(xiàn)管理過程的模型化。然后進行時間參數(shù)計算，找出計劃中的關(guān)鍵工作和關(guān)鍵路線，對任務(wù)的各項工作所需的人、財、物通過改善網(wǎng)絡(luò)計劃作出合理安排，得到最優(yōu)方案并付諸實施。通過對各種評價指標(biāo)進行定量化分析，在計劃的實施過程中，進行有效的監(jiān)督與控制，以保證任務(wù)高質(zhì)量地完成。5.4.1 網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖是由節(jié)點、弧及權(quán)所構(gòu)成的有向圖，即有向的賦權(quán)圖。節(jié)點表示事項，弧表示工序（活動）。工序是在工藝技術(shù)和組織管理上相對獨立的工作或活動，需要一定的時間與資源，而事項則表示一個或若干工序的開始或結(jié)束，是相繼工序的分界點。權(quán)表示為完成某個工序所需要的時間或資源等數(shù)據(jù)。例如某工序可以表示為：，為箭頭節(jié)點，表示工序開始，為箭頭尾節(jié)點，表示工序結(jié)束，5為完成本工序所需時間。網(wǎng)絡(luò)圖是有向圖，按照工藝流程的順序，規(guī)定工序從左向右排列，再給節(jié)點統(tǒng)一編號，節(jié)點由小到大編號。對任一工序來講，要求。始點編號可以從1開始。在繪制網(wǎng)絡(luò)圖時，還要注意以下規(guī)則：網(wǎng)絡(luò)圖只能有一個總起點事項，一個總終點事項。網(wǎng)絡(luò)圖不能有缺口和回路。兩節(jié)點之間只能有一條弧。正確表示工作之間的前行、后繼關(guān)系。如圖5-16表示兩工序結(jié)束后，兩工序才開始。為的緊前工序，為的緊后工序。虛工序的應(yīng)用。如果的工序關(guān)系是：必須在均完成后才能開工，而只要在完成后即可開工。也就是說，是的緊前工序，而只有是的緊前工序。這樣必須用圖5-17來表示，其中是一個虛工序，只表示、兩節(jié)點的銜接關(guān)系，不需要人力、物力等資源和時間。虛工序還可以用于正確表示平行與交叉作業(yè)。一道工序分為幾道工序同時進行，稱為平行作業(yè)。如圖5-18（a）中市場調(diào)研需12天，如增加人力分為3組同時進行，可以畫為5-18（b）。兩個或兩個以上的工作交叉進行，稱為交叉作業(yè)。如工作與工作分別為挖溝和埋管子，那么它們的關(guān)系可以是挖一段，埋一段，不必等溝全部挖好再埋。這樣，我們可用圖5-19來表示交叉作業(yè)。根據(jù)上述規(guī)則繪制網(wǎng)絡(luò)圖，是為了保證網(wǎng)絡(luò)圖的正確性。此外，為了使圖面布局合理，層次分明，條理清楚，還要注意畫圖技巧。避免弧的交叉，盡可能將關(guān)鍵路線布置在中心位置，將聯(lián)系緊密的工序布置在相近的位置。例5-5 某項新產(chǎn)品投產(chǎn)前全部準備工作（如表5-3）列示各工序與所需時間以及它們之間的相互關(guān)系。要求編制該項工程的網(wǎng)絡(luò)計劃。表5-3工序工序內(nèi)容緊前工序工時（周）A市場調(diào)查/4B資金籌措/10C需求分析A3D產(chǎn)品設(shè)計A6E產(chǎn)品研制D8F制定成本計劃C，E2G制定生產(chǎn)計劃F3H籌備設(shè)備B，G2I原材料準備B，G8J安裝設(shè)備H5K人員準備G2L準備開工投產(chǎn)I，J，K1根據(jù)以上規(guī)則，繪制的網(wǎng)絡(luò)圖如5-20所示。5.4.2 時間參數(shù)計算計算網(wǎng)絡(luò)圖中有關(guān)的時間參數(shù)，主要目的是找出關(guān)鍵路線，為網(wǎng)絡(luò)計劃的優(yōu)化、調(diào)整和執(zhí)行提供明確的時間概念。通常把網(wǎng)絡(luò)圖中需時最長的路線叫做關(guān)鍵路線，如圖5-21所示網(wǎng)絡(luò)中雙箭線表示的為關(guān)鍵路線，關(guān)鍵路線上的工序稱為關(guān)鍵工序。要想使任務(wù)按期完或提前完工，就要在關(guān)鍵路線的關(guān)鍵工序上想辦法。網(wǎng)絡(luò)圖的時間參數(shù)包括工序所需時間、事項最早、最遲時間，工序的最早、最遲時間及時差等，下面分別敘述。一、 工序時間的確定工序的所需時間可記為，有以下兩種情況：完成工序所需時間確定，只給出一個時間值。在具備勞動定額資料的條件下，或者在具有類似工序的作業(yè)時間消耗的統(tǒng)計資料時，用對比分析來確定作業(yè)時間。在影響工序因素較多，作業(yè)時間難以準確估計時，可以采用三點時間估計法來確定作業(yè)時間：最快可能完成時間最可能完成時間最慢可能完成時間一般情況下，可按下列公式近似計算作業(yè)時間。概率型網(wǎng)絡(luò)圖與確定型網(wǎng)絡(luò)圖在工時確定后，對其他時間參數(shù)的計算基本相同。二、 事項時間參數(shù)事項最早時間事項的最早時間用表示，它表示以為始點的各工序最早可能開始的時間，也表示以為終點的各工序的最早可能完成時間。它等于從始點事項起到本事項最長路線的時間長度。事項最早時間可用下列遞推公式，按照事項編號從小到大順序逐個計算。式中，為事項相鄰的各緊前事項的最早時間。事項的最遲時間事項的最遲時間用表示，它表明在不影響任務(wù)總工期條件下，以它為始點的工序的最遲必須開始時間，或以它為終點的各工作的最遲必須完成時間。在一般情況下，把任務(wù)的最早完工時間作為任務(wù)的總工期，所示事項最遲時間的計算方法如下：為事項相鄰的各緊后事項的最遲時間，它的計算從終點事項開始，按編號由大到小的順序逐個計算。三、 工序的時間參數(shù)工序的最早可能開始時間和最早可能完工時間一個工序的最早可能開工時間用表示，任何一個工序都必須在其所有緊前工序全部完工后才能開始。工序的最早可能完工時間用表示，它表示工作按最早開工時間開始所能達到的完工時間，計算公式如下：工序的最早可能開工時間等于事項最早時間。工序的最遲必須開工時間與最遲必須完工時間一個工序的最遲必須開工時間用表示，它是工序在不影響整個任務(wù)如期完成的前提下，必須開始的最晚時間。工序最遲必須完工時間用表示，它表示工作按最遲時間開工，所能達到的完工時間。工序最遲必須完工時間等于事項的最遲時間四、時差。工序的時差，又稱為工序的機動時間，工序時差分兩種：工序總時差在不影響工程最早結(jié)束時間的條件下，工序最早開始（或結(jié)束）時間可以推遲的時間：工序單時差不影響緊后工序最早開始時間的條件下，工序最早結(jié)束時間可以推遲的時間：式中，為工序的緊后工序的最早開始時間?？倳r差為零的工序，開始和結(jié)束的時間沒有一點機動的余地，由這些工序所組成的路線就是網(wǎng)絡(luò)中的關(guān)鍵路線，這些工序就是關(guān)鍵工序。例5-6：確定圖5-20所示網(wǎng)絡(luò)的關(guān)鍵路線。解：先用圖上計算法求解，再用表上計算法驗證。根據(jù)圖5-20的資料，先計算各事項的時間參數(shù)。事項時間如總開工事項，將結(jié)果填入圖中編號上方空格 的左邊。逐個計算事項最早時間，得到總完工事項，說明整個工作需要32周的時間完成。再從后面開始計算各事項最遲時間，如總完工事項的，事項的將結(jié)果填入編號上方空格 右邊。工序時間工序時間有4種：，用圖標(biāo) 表示，計算結(jié)果表示在圖5-22上。時差根據(jù)圖5-22中的結(jié)果，可以求出各工序的總時差。由總時差為0的工序組成關(guān)鍵路線，即：，總工期為32周。表5-4用來計算網(wǎng)絡(luò)時間，并標(biāo)示出關(guān)鍵工序。表5-4工序關(guān)鍵工序A404040B10010132313C347151811D64104100E8101810180F2182018200C3202320230虛工序0232323230H2232524261I8233123310J5233026311K2252529316L13132313205.4.3 網(wǎng)絡(luò)優(yōu)化繪制網(wǎng)絡(luò)圖，計算網(wǎng)絡(luò)時間和確定關(guān)鍵路線，得到一個初始的計劃方案。從工期、成本、資源等方面對初步方案進一步的改善和調(diào)整，以求得最佳效果，就是網(wǎng)絡(luò)優(yōu)化。目前尚未有能全面反映工期、成本、資源的綜合數(shù)學(xué)模型，因此，網(wǎng)絡(luò)優(yōu)化問題是根據(jù)實際情況分為時間優(yōu)化、時間-資源優(yōu)化和時間-費用優(yōu)化。1、 時間優(yōu)化根據(jù)對計劃進度的要求，縮短工程完工時間?？梢圆扇〈胧喊汛?lián)工序改為平行或交叉工序，縮短關(guān)鍵工序的作業(yè)時間；充分利用非關(guān)鍵工序的時差，減少這些作業(yè)的人力、資源用于關(guān)鍵工序，縮短關(guān)鍵工序的作業(yè)時間。2、 時間-資源優(yōu)化在編制網(wǎng)絡(luò)計劃安排工程進度時，考慮時間優(yōu)化的同時，盡量合理地利用有限的資源。具體的要求和做法是：優(yōu)先安排關(guān)鍵工序所需要的資源；利用非關(guān)鍵工序的總時差，錯開各工序的開始時間，拉平資源需要量的高峰；綜合考慮資源和時間，必要時，可適當(dāng)?shù)赝七t工程完工時間。在優(yōu)化時，通常將計劃的各主要資源需要量按日程排出，再按以上方法，使各主要資源的日負荷相對平衡。但是由于一項工程所包含的工序繁多，涉及到的資源利用情況復(fù)雜，需要多次綜合平衡，才能得到在時間進度和資源利用等方面都比較合理的計劃方案。3、 時間-費用優(yōu)化時間-費用優(yōu)化要研究和解決的問題是決定合理的工程完工時間，使費用最省，或者以合理的費用代價完成趕工作任務(wù)。工程費用包括兩大類：直接費用是完成各項工作直接所需人力、資源設(shè)備費用；為縮短工序的作業(yè)時間，需要采取一定的技術(shù)組織措施，相應(yīng)會增加一部分直接費用。間接費用是指管理費、辦工費等，常按施工時間長短分攤。完成工程項目的直接費用、間接費用、總費用與工程完工時間的關(guān)系，一般情況下如圖5-23所示。顯然，在網(wǎng)絡(luò)計劃中，最低成本日程具有重要意義。因此要計算網(wǎng)絡(luò)計劃的不同完工期相應(yīng)的總費用，以求得成本最低的日程安排，即最低成本日程。下面舉例說明最低成本日程計劃。例5-7：已知網(wǎng)絡(luò)計劃各工序的正常工時、極限工時及相應(yīng)費用如表5-5，網(wǎng)絡(luò)圖如圖5-24。表5-5工序正常工時極限工時成本斜率（元/天）時間（天）費用（元）時間（天）費用（元）245000167000250309000181020010022400018480020026100002410300150248000209000250185400185400/18640010680050按正常工時計算出總工期74天，關(guān)鍵路線，總直接費用為47800元。設(shè)正常工時下任務(wù)總間接費用為18000元，工期每縮短一天，間接費用可節(jié)省330元，求最低成本日程。解：按下列步驟進行計算。a） 從關(guān)鍵工作中選出縮短工時所需直接費用最少的方案及天數(shù)；b） 按照新工時，重新計算網(wǎng)絡(luò)計劃的關(guān)鍵路線及關(guān)鍵工作；c） 計算由于縮短工時總費用的變化。重復(fù)以上三個步驟，直到工期不能再縮短為止。在圖5-24上，挑選關(guān)鍵路線中成本斜率最小者，最多可縮短12天，即新工時為18天。重新計算網(wǎng)絡(luò)時間參數(shù)，如圖5-25（a）所示，關(guān)鍵路線為，工期為64天，實際只縮短10天，這意味著工序的工時為20天。重新計算結(jié)果如圖5-25（b），總工期64天，有兩條關(guān)鍵路線，直接費用增10100元，間接費用減10330元。重復(fù)上述步驟，將，的工時縮短為：18，20天，重新計算網(wǎng)絡(luò)時間參數(shù)，結(jié)果如圖5-26。關(guān)鍵路線不變。增加直接費用2（100+200）=600元，減少間接費用2330=660元。第三次調(diào)整，在，工序上多縮短2天，重新計算網(wǎng)絡(luò)時間參數(shù)，結(jié)果如圖5-27，有三條關(guān)鍵路線，總工期60天，直接費用增加2350=700元，間接費用減少2330=660元。由于一條關(guān)鍵路線上各工序工時不能縮短，計算結(jié)束。最低成日程為62天，總成本63440元。習(xí)題：5.1有9個城市，其公路網(wǎng)如圖5-28所示。弧旁數(shù)字是該段公路的長度，有一批貨物從到，問走哪條路最短？5.2用DijKstra方法求圖5-29中從到各點的最短路。5.3求圖5-30網(wǎng)絡(luò)中各頂點間的最短路。5.4某設(shè)備今后5年的價格預(yù)測分別是（5，5，6，7，8），若該設(shè)備連續(xù)使用，其第年的維修費分別為（1，2，3，5，6）。某單位今年購進一臺，問如何確定更新方案可使5年里總支出最?。ú还茉O(shè)備使用了多少年，其殘值為0）。5.5在如圖5-31所示的網(wǎng)絡(luò)中，每弧旁的數(shù)字是。（1） 確定所有的截集；（2） 求最小截集的容量；（3） 證明指出的流是最大流。5.6求如圖5-32所示的網(wǎng)絡(luò)的最大流，弧上數(shù)為。5.7如圖5-33，發(fā)點分別可供應(yīng)10和15個單位，收點可以接收10和25個單位，求最大流，弧上數(shù)為。5-8試畫出表5-6所表示項目的網(wǎng)絡(luò)圖。表5-6工作工時（d）緊前工序工作工時（d）緊前工序A15-F5D，EB10-G20C，F(xiàn)C10A，BH10D，ED10A，BI15G，HE5B5-9設(shè)有如圖5-34網(wǎng)絡(luò)圖，用圖上計算法計算時間參數(shù)，并求出關(guān)鍵路線。5-10繪 制表5-7所示的網(wǎng)絡(luò)圖，并用表上計算法計算工作的各項時間參數(shù)，確定關(guān)鍵路線。表5-7工作工時（d）緊前工序工作工時（d）緊前工序A5-F4B，CB8A，CG8CC3AH2F，GD6CI4E，HE10B，CJ5F，G5-11已知下列資料表5-8活動作業(yè)時間（d）緊前活動正常完成進度的直接費用（百元）趕進度1天所需費用（百元）A4-205B8-304C6B153D3A52E5A184F7A407G4B，D103H3E，F(xiàn)，G156工程的間接費5（百元/天），求出該項工程的最低成本日程。28