運籌學課件：第5章 圖與網(wǎng)絡分析

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