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

《運籌學(xué)課件：第5章 圖與網(wǎng)絡(luò)分析》由會員分享，可在線閱讀，更多相關(guān)《運籌學(xué)課件：第5章 圖與網(wǎng)絡(luò)分析（28頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第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ù)

2、條線相連。這是古典圖論中的一個著名問題。 運籌學(xué)中的“中國郵遞員問題”：一個郵遞員從郵局出發(fā)要走遍他所負(fù)責(zé)的每條街道去送信，問應(yīng)如何選擇適當(dāng)?shù)穆肪€可使所走的總路程最短。這個總是就與歐拉回路有密切的關(guān)系。 圖論的第一本專著是匈牙利數(shù)學(xué)家O.Konig著的“有限圖與無限圖的理論”，發(fā)表于1936年。隨著科學(xué)技術(shù)的發(fā)展及電子計算機(jī)的出現(xiàn)和廣泛應(yīng)用，圖論得到進(jìn)一步發(fā)展，廣泛應(yīng)用于管理科學(xué)、計算機(jī)科學(xué)、心理學(xué)及工程技術(shù)管理中，并取得了豐碩的成果。 5.1.2 基本概念 自然界和人類社會中，大量的事物以及事物之間的關(guān)系，?？梢杂脠D形來表示。如為了反映城市之間有沒有航班，我們可用圖5-2來示意。甲城

3、與乙城，乙城與丙城有飛機(jī)到達(dá)，而甲、丙兩城沒有直飛航班。再如工作分配問題，我們可以用點表示每人與需要完成的工作，點間連線表示每個人可以勝任哪些工作如圖5-3所示。 在上面的例子中，我們關(guān)心圖中有多少個點，點與點之間有無連線。這種圖是反映對象之間關(guān)系的一種工具。 圖可分為無向圖和有向圖。兩點之間不帶箭頭的聯(lián)線為邊，兩點之間帶箭頭的聯(lián)線為弧。 由點、邊構(gòu)成的圖是無向圖，記 由點、弧構(gòu)成的圖是有向圖，記 圖5-4是一個無向圖 ， 其中， 圖5-5是一個有向圖 ， 其中， 給定一個圖，一個點、邊的交錯序列，如果滿足，，則稱為一條聯(lián)結(jié)和的鏈，記為。 對于有向圖，從中去掉所

4、有弧上的箭頭，應(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)造矩陣

5、 其中， 稱矩陣為網(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于1

6、959年提出來，用于求解指定兩點、之間的最短路，或從指定點到其余各點的最短路，目前被認(rèn)為是求情形下最短路問題的最好方法。算法的基本思路基于以下原理：若是從到的最短路，是中的一個點，那么從沿到的路是從到的最短路。 采用標(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)號

7、。對的標(biāo)號進(jìn)行如下的更改： ⑶比較所有具有標(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)號中，最

8、小，故令。 ⑺考察， 令，所有點都標(biāo)上標(biāo)號，計算結(jié)束。 從之最短路是：，路長13，同時得到到其余各點的最短路。 5.2.2 逐次逼近算法 Dijkstra算法只適用于所有的情形，當(dāng)賦權(quán)有向圖中存在負(fù)權(quán)時，則算法失效。例如在圖5-9所示的賦權(quán)有向圖中，用Dijkstra算法得到到最短路的權(quán)是5，但這里顯然不對；因為到的最短路是，權(quán)為3。 在存在負(fù)權(quán)時，我們采取逐次逼近算法來求解最短路。為方便起見，不妨設(shè)從任一點到任一點都有一條弧，如果在中，，則添加弧，令。顯然，從到的最短路總是從出發(fā)，沿著一條路到某點，再沿到的，所以，從到的這條路必定是從到的最短路。故有，的距離必滿足如下方程

9、： 為了求解這個方程的解，，為的點數(shù)，令 ，為迭代步數(shù)。 若第步，對所有，有 則為到任一點的最短路權(quán)。 例5-2 求圖5-10所示賦權(quán)有向圖中從到各點的最短路。 解：迭代初始條件為： 有，，，，，，，。用表5-1表示全部計算過程。 表5-1 （表中空格為） j i wij D(t)(v1,vj) V1 V2 V3 V4 V5 V6 V7 V8 V1 0 -1 -2 3 0 0 0 0 V2 6 0 2 -1 -5 -5 -5 V3

10、 -3 0 -5 1 -2 -2 -2 -2 V4 8 0 2 3 -7 -7 -7 V5 -1 0 1 -3 -3 V6 1 0 1 7 -1 -1 -1 V7 -1 0 5 -5 -5 V8 -3 -5 0 6 6 當(dāng)時，發(fā)現(xiàn)，表明已得到到各點的最短路的權(quán)，即表中最后一列數(shù)。 如果需要知道點到各點的最短路徑，可以采用“反向追蹤”的辦法。如已知，，因故記下。因，記下，

11、從而從到的最短路徑是。 遞推公式中實際意義為從到點，至多含有個中間點的最短路權(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è)備在各年的購買費及不同機(jī)器役齡時的殘值和維修費，如表5-2所示。 表5-2 第1年 第2年 第3年 第4年 第5年 購買費 11

12、 12 13 14 14 機(jī)器役齡 0-1 1-2 2-3 3-4 4-5 維修費 5 6 8 11 18 殘值 4 3 2 1 0 解：把這個問題化為最短路問題 用表示第年初購進(jìn)一臺新設(shè)備，虛設(shè)一個點，表示第5年底；用弧表示第初購的設(shè)備一直使用到第年年底；弧上的數(shù)字表示第年初購進(jìn)設(shè)備，一直使用到第年底所需支付的購買、維修的全部費用。例如，弧上的28是第1年初購買費11加上3年的維修費5，6，8，減去了3年役齡機(jī)器的殘值2；弧上的20是第2年初購買費12減去機(jī)器殘值3與使用2年維修費5，6之和，見圖5-11。 這樣設(shè)備更新問題就變?yōu)椋呵髲?/p>

13、到的最短路，計算結(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世紀(jì)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ò)與流 定義 給一個有向圖，在中指

14、定一點為發(fā)點，另一點為收點，其余的點叫中間點。對于每一個弧，對應(yīng)有一個（簡寫為），稱為弧的容量。這樣的叫做網(wǎng)絡(luò)，記作。 所謂網(wǎng)絡(luò)上的流，是指定義在弧集合上的一個函數(shù)，并稱為弧上的流量，簡記作。 ⑵可行流與最大流 ①容量限制條件：每一弧 ②平衡條件：對于中間點，有 對于發(fā)點，收點，有 稱為這個可行流的流量。 可行流總是存在的，如零流，，。所謂最大流問題，就是求一個流，使其流量達(dá)到最大，并且滿足以上容量限制條件和平衡條件。 其實最大流問題是一個特殊的線性規(guī)劃問題，但是利用它與圖的緊密關(guān)系求解，更為直觀簡便。 ⑶增廣鏈 若是網(wǎng)絡(luò)中聯(lián)結(jié)發(fā)點和收點的一條鏈，且鏈的方向是從

15、到，則與鏈的方向一致的弧叫前向弧，表示前向弧的集合；與鏈的方向相反的弧叫后向弧，表示后向弧的集合。 定義 設(shè)是一個可行流，是從到的一條鏈，若滿足下列條件，是可行流的一條增廣鏈。 ① 弧上，，即中每一弧是非飽和弧。 ② 弧上，，即中每一弧是非零流弧。 ⑷截集與截量 設(shè)，我們把始點在，終點在中的所有弧構(gòu)成的集合，記為。 定義 給網(wǎng)絡(luò)，若點集被剖分為兩個非空集合和， ，使，則把弧集稱為分離，的截集。 從定義可知截集是從到的必經(jīng)之道。 定義 給一截集，把截集中所有弧的容量之和稱為這個截集的容量，記作 不難證明，任何一個可行流的流量都不會超過任一截量的容量，即。 顯然，若對于一個可

16、行流，網(wǎng)絡(luò)中有一個截集，，則必是最大流，而必定是的所有截集中容量最小的一個，即最小截量。 最大流量最小截量定理：任一個網(wǎng)絡(luò)中，從到的最大流的流量等于分離，的最小截集的容量。 定理1 可行流是最大流，當(dāng)且僅當(dāng)不存在關(guān)于的增廣鏈。 證明 若是最大流，設(shè)中存在關(guān)于的增廣鏈，令 由增廣鏈的定義，可知，令 不難驗證是一個可行流，且，這與是最大流假設(shè)矛盾。 現(xiàn)在設(shè)中不存在關(guān)于的增廣鏈，證明是最大流。 令，若，且，則令；若，且，則令。 因為不存在關(guān)于的增廣鏈，故。 記，于是得到一個截集，顯然必有 所以，。于是必是最大流，定理得證。 定理1為我們提供了尋求網(wǎng)絡(luò)最大流的一個方法

17、。若可行流中存在增廣鏈，說明還有潛力可挖，只須沿增廣鏈調(diào)整流量，得到一個流量增大的新的可行流；否則是最大流。而判別是否存在增廣鏈，可以根據(jù)是否屬于來進(jìn)行。 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)號

18、。 ③ 重復(fù)上述步驟，直到被標(biāo)上號或不再有頂點可標(biāo)號為止。如果得到標(biāo)號，說明存在增廣鏈，轉(zhuǎn)入調(diào)整過程；若未獲得標(biāo)號，標(biāo)號過程已無法進(jìn)行時，說明已是最大流。 ⑵調(diào)整過程 令 調(diào)整量，去掉所有標(biāo)號，對新的可行流重新進(jìn)行標(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

19、、在中任選一個進(jìn)行檢查，例如，在弧 上，，給標(biāo)號，。 因有了標(biāo)號，故轉(zhuǎn)入調(diào)整過程。 （二）調(diào)整過程 按點的第一個標(biāo)號找到一條增廣鏈，如圖5-14中雙箭線所示。 則見： 按，在增廣鏈上調(diào)整。 上： 上： 其余的不變。 調(diào)整后得到圖5-15所示的可行流，對這個可行流進(jìn)行標(biāo)號，尋找增廣鏈。 開始給標(biāo)號，檢查，給標(biāo)以，檢查，弧上，，弧上，，均不符合條件，標(biāo)號過程無法繼續(xù)下去，算法結(jié)束。這時圖5-15 可行流即最大流。 最大流為：。與此同時可找到最小截集，其中為標(biāo)號點集，即，為未標(biāo)號點集，，截集，最小截量為5。 由上述可見，用標(biāo)號法找增廣鏈找到最大流的同時，得到一個最小截

20、集。最小截集的容量大小影響網(wǎng)絡(luò)最大流量。因此為提高總的輸送量，必須首先考慮改善最小截集中各弧的輸送能力。另一方面，一旦最小截集中弧的通過能力被 降低，就會使總的輸送量減少。 5.4 網(wǎng)絡(luò)計劃 20世紀(jì)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)濟(jì)效益發(fā)揮了重要作用。 我國

21、數(shù)學(xué)家華羅庚先生將這些方法總結(jié)概括為統(tǒng)籌方法，引入中國并推廣應(yīng)用。統(tǒng)籌方法的基本原理是：從需要管理的任務(wù)的總進(jìn)度著眼，以任務(wù)中各工作所需要的工時為時間因素，按照工作的先后順序和相互關(guān)系作出網(wǎng)絡(luò)圖，以反映任務(wù)全貌，實現(xiàn)管理過程的模型化。然后進(jìn)行時間參數(shù)計算，找出計劃中的關(guān)鍵工作和關(guān)鍵路線，對任務(wù)的各項工作所需的人、財、物通過改善網(wǎng)絡(luò)計劃作出合理安排，得到最優(yōu)方案并付諸實施。通過對各種評價指標(biāo)進(jìn)行定量化分析，在計劃的實施過程中，進(jìn)行有效的監(jiān)督與控制，以保證任務(wù)高質(zhì)量地完成。 5.4.1 網(wǎng)絡(luò)圖 網(wǎng)絡(luò)圖是由節(jié)點、弧及權(quán)所構(gòu)成的有向圖，即有向的賦權(quán)圖。節(jié)點表示事項，弧表示工序（活動）。工序是在工藝

22、技術(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é)點之間只能有一條弧。 ⑷正確表示工作之間的前行、后繼

23、關(guān)系。 如圖5-16表示兩工序結(jié)束后，兩工序才開始。為的緊前工序，為的緊后工序。 ⑸虛工序的應(yīng)用。 如果的工序關(guān)系是：必須在均完成后才能開工，而只要在完成后即可開工。也就是說，是的緊前工序，而只有是的緊前工序。這樣必須用圖5-17來表示，其中③→④是一個虛工序，只表示③、④兩節(jié)點的銜接關(guān)系，不需要人力、物力等資源和時間。 虛工序還可以用于正確表示平行與交叉作業(yè)。一道工序分為幾道工序同時進(jìn)行，稱為平行作業(yè)。如圖5-18（a）中市場調(diào)研需12天，如增加人力分為3組同時進(jìn)行，可以畫為5-18（b）。 兩個或兩個以上的工作交叉進(jìn)行，稱為交叉作業(yè)。如工作與工作分別為挖溝和埋管子，那

24、么它們的關(guān)系可以是挖一段，埋一段，不必等溝全部挖好再埋。這樣，我們可用圖5-19來表示交叉作業(yè)。 根據(jù)上述規(guī)則繪制網(wǎng)絡(luò)圖，是為了保證網(wǎng)絡(luò)圖的正確性。此外，為了使圖面布局合理，層次分明，條理清楚，還要注意畫圖技巧。避免弧的交叉，盡可能將關(guān)鍵路線布置在中心位置，將聯(lián)系緊密的工序布置在相近的位置。 例5-5 某項新產(chǎn)品投產(chǎn)前全部準(zhǔn)備工作（如表5-3）列示各工序與所需時間以及它們之間的相互關(guān)系。要求編制該項工程的網(wǎng)絡(luò)計劃。 表5-3 工序 工序內(nèi)容 緊前工序 工時（周） A 市場調(diào)查 / 4 B 資金籌措 / 10 C 需求分析 A 3 D 產(chǎn)品設(shè)計 A

25、6 E 產(chǎn)品研制 D 8 F 制定成本計劃 C，E 2 G 制定生產(chǎn)計劃 F 3 H 籌備設(shè)備 B，G 2 I 原材料準(zhǔn)備 B，G 8 J 安裝設(shè)備 H 5 K 人員準(zhǔn)備 G 2 L 準(zhǔn)備開工投產(chǎn) I，J，K 1 根據(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ù)按

26、期完或提前完工，就要在關(guān)鍵路線的關(guān)鍵工序上想辦法。 網(wǎng)絡(luò)圖的時間參數(shù)包括工序所需時間、事項最早、最遲時間，工序的最早、最遲時間及時差等，下面分別敘述。 一、 工序時間的確定 工序的所需時間可記為，有以下兩種情況： ⑴完成工序所需時間確定，只給出一個時間值。在具備勞動定額資料的條件下，或者在具有類似工序的作業(yè)時間消耗的統(tǒng)計資料時，用對比分析來確定作業(yè)時間。 ⑵在影響工序因素較多，作業(yè)時間難以準(zhǔn)確估計時，可以采用三點時間估計法來確定作業(yè)時間： ——最快可能完成時間 ——最可能完成時間 ——最慢可能完成時間 一般情況下，可按下列公式近似計算作業(yè)時間。 概率型網(wǎng)絡(luò)圖與確定型網(wǎng)絡(luò)

27、圖在工時確定后，對其他時間參數(shù)的計算基本相同。 二、 事項時間參數(shù) ⑴事項最早時間 事項的最早時間用表示，它表示以為始點的各工序最早可能開始的時間，也表示以為終點的各工序的最早可能完成時間。它等于從始點事項起到本事項最長路線的時間長度。事項最早時間可用下列遞推公式，按照事項編號從小到大順序逐個計算。 式中，為事項相鄰的各緊前事項的最早時間。 ⑵事項的最遲時間 事項的最遲時間用表示，它表明在不影響任務(wù)總工期條件下，以它為始點的工序的最遲必須開始時間，或以它為終點的各工作的最遲必須完成時間。在一般情況下，把任務(wù)的最早完工時間作為任務(wù)的總工期，所示事項最遲時間的計算方法如下：

28、為事項相鄰的各緊后事項的最遲時間，它的計算從終點事項開始，按編號由大到小的順序逐個計算。 三、 工序的時間參數(shù) ⑴工序的最早可能開始時間和最早可能完工時間 一個工序的最早可能開工時間用表示，任何一個工序都必須在其所有緊前工序全部完工后才能開始。工序的最早可能完工時間用表示，它表示工作按最早開工時間開始所能達(dá)到的完工時間，計算公式如下： 工序的最早可能開工時間等于事項最早時間。 ⑵工序的最遲必須開工時間與最遲必須完工時間 一個工序的最遲必須開工時間用表示，它是工序在不影響整個任務(wù)如期完成的前提下，必須開始的最晚時間。工序最遲必須完工時間用表示，它表示工作按最遲時間開工，所能達(dá)到的

29、完工時間。 工序最遲必須完工時間等于事項的最遲時間 四、時差。 工序的時差，又稱為工序的機(jī)動時間，工序時差分兩種： ⑴工序總時差 在不影響工程最早結(jié)束時間的條件下，工序最早開始（或結(jié)束）時間可以推遲的時間： ⑵工序單時差 不影響緊后工序最早開始時間的條件下，工序最早結(jié)束時間可以推遲的時間： 式中，為工序的緊后工序的最早開始時間。 總時差為零的工序，開始和結(jié)束的時間沒有一點機(jī)動的余地，由這些工序所組成的路線就是網(wǎng)絡(luò)中的關(guān)鍵路線，這些工序就是關(guān)鍵工序。 例5-6：確定圖5-20所示網(wǎng)絡(luò)的關(guān)鍵路線。 解：先用圖上計算法求解，再用表上計算法驗證。 根據(jù)圖5-20的資

30、料，先計算各事項的時間參數(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)鍵工序。 表

31、5-4 工序 關(guān)鍵工序 A 4 0 4 0 4 0 √ B 10 0 10 13 23 13 C 3 4 7 15 18 11 D 6 4 10 4 10 0 √ E 8 10 18 10 18 0 √ F 2 18 20 18 20 0 √ C 3 20 23 20 23 0 √ 虛工序 0 23 23 23 23 0 √ H 2 23 25 24 26 1 I 8 23 31 23 31 0 √

32、J 5 23 30 26 31 1 K 2 25 25 29 31 6 L 1 31 32 31 32 0 √ 5.4.3 網(wǎng)絡(luò)優(yōu)化 繪制網(wǎng)絡(luò)圖，計算網(wǎng)絡(luò)時間和確定關(guān)鍵路線，得到一個初始的計劃方案。從工期、成本、資源等方面對初步方案進(jì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ù)對計劃進(jìn)度的要求，縮短工程完工時間?？梢圆扇〈胧喊汛?lián)工序改為平行或交叉工序，縮短關(guān)鍵工序的作業(yè)時間；

33、充分利用非關(guān)鍵工序的時差，減少這些作業(yè)的人力、資源用于關(guān)鍵工序，縮短關(guān)鍵工序的作業(yè)時間。 2、 時間-資源優(yōu)化 在編制網(wǎng)絡(luò)計劃安排工程進(jìn)度時，考慮時間優(yōu)化的同時，盡量合理地利用有限的資源。具體的要求和做法是： ⑴優(yōu)先安排關(guān)鍵工序所需要的資源； ⑵利用非關(guān)鍵工序的總時差，錯開各工序的開始時間，拉平資源需要量的高峰； ⑶綜合考慮資源和時間，必要時，可適當(dāng)?shù)赝七t工程完工時間。 在優(yōu)化時，通常將計劃的各主要資源需要量按日程排出，再按以上方法，使各主要資源的日負(fù)荷相對平衡。但是由于一項工程所包含的工序繁多，涉及到的資源利用情況復(fù)雜，需要多次綜合平衡，才能得到在時間進(jìn)度和資源利用等方面都比較合

34、理的計劃方案。 3、 時間-費用優(yōu)化 時間-費用優(yōu)化要研究和解決的問題是決定合理的工程完工時間，使費用最省，或者以合理的費用代價完成趕工作任務(wù)。 工程費用包括兩大類： ⑴直接費用是完成各項工作直接所需人力、資源設(shè)備費用；為縮短工序的作業(yè)時間，需要采取一定的技術(shù)組織措施，相應(yīng)會增加一部分直接費用。 ⑵間接費用是指管理費、辦工費等，常按施工時間長短分?jǐn)偂? 完成工程項目的直接費用、間接費用、總費用與工程完工時間的關(guān)系，一般情況下如圖5-23所示。 顯然，在網(wǎng)絡(luò)計劃中，最低成本日程具有重要意義。因此要計算網(wǎng)絡(luò)計劃的不同完工期相應(yīng)的總費用，以求得成本最低的日程安排，即最低成本日程。

35、下面舉例說明最低成本日程計劃。 例5-7：已知網(wǎng)絡(luò)計劃各工序的正常工時、極限工時及相應(yīng)費用如表5-5，網(wǎng)絡(luò)圖如圖5-24。 表5-5 工序 正常工時 極限工時 成本斜率 （元/天） 時間（天） 費用（元） 時間（天） 費用（元） ①→② 24 5000 16 7000 250 ①→③ 30 9000 18 10200 100 ②→④ 22 4000 18 4800 200 ③→④ 26 10000 24 10300 150 ③→⑤ 24 8000 20 9000 250 ④→⑥ 18 5400 18 5

36、400 / ⑤→⑥ 18 6400 10 6800 50 按正常工時計算出總工期74天，關(guān)鍵路線①→③→④→⑥，總直接費用為47800元。設(shè)正常工時下任務(wù)總間接費用為18000元，工期每縮短一天，間接費用可節(jié)省330元，求最低成本日程。 解：按下列步驟進(jìn)行計算。 a） 從關(guān)鍵工作中選出縮短工時所需直接費用最少的方案及天數(shù)； b） 按照新工時，重新計算網(wǎng)絡(luò)計劃的關(guān)鍵路線及關(guān)鍵工作； c） 計算由于縮短工時總費用的變化。 重復(fù)以上三個步驟，直到工期不能再縮短為止。 在圖5-24上，挑選關(guān)鍵路線中成本斜率最小者①→③，最多可縮短12天，即①→③新工時為18天。重新計算

37、網(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天，直接費用增

38、加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）。某單位今年購進(jìn)一臺，問如何確定更新方案可使5年里總支出最

39、?。ú还茉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） 緊前工序 A 15 -- F 5 D，E B 10 -- G 20 C，F(xiàn) C 10 A

40、，B H 10 D，E D 10 A，B I 15 G，H E 5 B 5-9 設(shè)有如圖5-34網(wǎng)絡(luò)圖，用圖上計算法計算時間參數(shù)，并求出關(guān)鍵路線。 5-10 繪 制表5-7所示的網(wǎng)絡(luò)圖，并用表上計算法計算工作的各項時間參數(shù)，確定關(guān)鍵路線。 表5-7 工作 工時（d） 緊前工序 工作 工時（d） 緊前工序 A 5 -- F 4 B，C B 8 A，C G 8 C C 3 A H 2 F，G D 6 C I 4 E，H E 10 B，C J 5 F，G 5-11 已知下列資料 表5-8 活動 作業(yè)時間（d） 緊前活動 正常完成進(jìn)度的直接費用（百元） 趕進(jìn)度1天所需費用（百元） A 4 -- 20 5 B 8 -- 30 4 C 6 B 15 3 D 3 A 5 2 E 5 A 18 4 F 7 A 40 7 G 4 B，D 10 3 H 3 E，F(xiàn)，G 15 6 工程的間接費5（百元/天），求出該項工程的最低成本日程。 28