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

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

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

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

4、礎(chǔ)圖中所對(duì)應(yīng)的點(diǎn)邊序列是一條鏈，則稱這個(gè)點(diǎn)弧交錯(cuò)序列是的一條鏈。在實(shí)際問題中，往往只用圖來描述的所研究對(duì)象之間的關(guān)系還是不夠的，與圖聯(lián)系在一起的，通常還有與點(diǎn)或邊有關(guān)的某些數(shù)量指標(biāo)，稱為“權(quán)”，權(quán)可以代表如距離、費(fèi)用、通過能力（容量）等等。這種點(diǎn)或邊帶有某種數(shù)量指標(biāo)的圖稱為網(wǎng)絡(luò)（即賦權(quán)圖）。5.1.3 圖的矩陣表示用矩陣表示圖對(duì)研究圖的性質(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對(duì)于圖，構(gòu)造一個(gè)矩陣，其中，則稱矩陣為圖的鄰接矩陣。圖5-7

5、所示圖的鄰接矩陣為當(dāng)為無向圖時(shí)，鄰接矩陣為對(duì)稱矩陣。5.2 最短路問題最短路問題是網(wǎng)絡(luò)理論中應(yīng)用最廣泛的問題之一。許多優(yōu)化問題可以使用這個(gè)模型，如設(shè)備更新、管道鋪設(shè)、線路安排、廠區(qū)布局等。問題表述：給定一個(gè)賦權(quán)有向圖，對(duì)每一弧，相應(yīng)地有權(quán)，又有兩點(diǎn)，設(shè)是中到的一條路，路的權(quán)是中所有弧的權(quán)之和，記為。最短路問題就是求從到的路中一條權(quán)最小的路，。5.2.1 Dijkstra算法該算法是由Dijkstra于1959年提出來，用于求解指定兩點(diǎn)、之間的最短路，或從指定點(diǎn)到其余各點(diǎn)的最短路，目前被認(rèn)為是求情形下最短路問題的最好方法。算法的基本思路基于以下原理：若是從到的最短路，是中的一個(gè)點(diǎn)，那么從沿到的路

6、是從到的最短路。采用標(biāo)號(hào)法：標(biāo)號(hào)與標(biāo)號(hào)。標(biāo)號(hào)為試探性標(biāo)號(hào)，為永久性標(biāo)號(hào)。給點(diǎn)一個(gè)標(biāo)號(hào)時(shí)，表示從到點(diǎn)的最短路權(quán)，點(diǎn)的標(biāo)號(hào)不再改變。給點(diǎn)一個(gè)標(biāo)號(hào)時(shí)，表示從到點(diǎn)的估計(jì)最短路權(quán)的上界，是一種臨時(shí)標(biāo)號(hào)。凡沒有得到標(biāo)號(hào)的點(diǎn)都有標(biāo)號(hào)。算法每一步都把某一點(diǎn)的標(biāo)號(hào)改為標(biāo)號(hào)，當(dāng)終點(diǎn)得到標(biāo)號(hào)時(shí)，全部計(jì)算結(jié)束。Dijkstra算法基本步驟：給以標(biāo)號(hào)，其余各點(diǎn)均給標(biāo)號(hào)，。若點(diǎn)為剛得到標(biāo)號(hào)的點(diǎn)，考慮，且為標(biāo)號(hào)。對(duì)的標(biāo)號(hào)進(jìn)行如下的更改： 比較所有具有標(biāo)號(hào)的點(diǎn)，把最小者改為標(biāo)號(hào)，即當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為標(biāo)號(hào)。若全部點(diǎn)均為標(biāo)號(hào)則停止。否則用代替轉(zhuǎn)回。例5.1 用Dijkstra算法求圖5-8中從的最短路解：首先給以

7、標(biāo)號(hào)，給其余所有點(diǎn)標(biāo)號(hào)，由于，且是標(biāo)號(hào)點(diǎn)，所以修改標(biāo)號(hào)為：在所有標(biāo)號(hào)中，最小，于是令。是剛得到標(biāo)號(hào)的點(diǎn)，故考察。因?yàn)?，且是?biāo)號(hào)，故新的標(biāo)號(hào)為：在所有標(biāo)號(hào)中，最小，故令。考察，因，在所有標(biāo)號(hào)中，最小，令?？疾?，在所有標(biāo)號(hào)中，最小，令?？疾?，在所有標(biāo)號(hào)中，最小，故令?？疾?，令，所有點(diǎn)都標(biāo)上標(biāo)號(hào)，計(jì)算結(jié)束。從之最短路是：，路長13，同時(shí)得到到其余各點(diǎn)的最短路。5.2.2 逐次逼近算法Dijkstra算法只適用于所有的情形，當(dāng)賦權(quán)有向圖中存在負(fù)權(quán)時(shí)，則算法失效。例如在圖5-9所示的賦權(quán)有向圖中，用Dijkstra算法得到到最短路的權(quán)是5，但這里顯然不對(duì)；因?yàn)榈降淖疃搪肥牵瑱?quán)為3。在存在負(fù)權(quán)時(shí)，我們采取

8、逐次逼近算法來求解最短路。為方便起見，不妨設(shè)從任一點(diǎn)到任一點(diǎn)都有一條弧，如果在中，則添加弧，令。顯然，從到的最短路總是從出發(fā)，沿著一條路到某點(diǎn)，再沿到的，所以，從到的這條路必定是從到的最短路。故有，的距離必滿足如下方程：為了求解這個(gè)方程的解，為的點(diǎn)數(shù)，令，為迭代步數(shù)。若第步，對(duì)所有，有則為到任一點(diǎn)的最短路權(quán)。例5-2 求圖5-10所示賦權(quán)有向圖中從到各點(diǎn)的最短路。解：迭代初始條件為：有，。用表5-1表示全部計(jì)算過程。表5-1 （表中空格為）ji wijD(t)(v1,vj)V1V2V3V4V5V6V7V8V10-1-230000V2602-1-5-5-5V3-30-51-2-2-2-2V480

9、23-7-7-7V5-101-3-3V61017-1-1-1V7-105-5-5V8-3-5066 當(dāng)時(shí)，發(fā)現(xiàn)，表明已得到到各點(diǎn)的最短路的權(quán)，即表中最后一列數(shù)。如果需要知道點(diǎn)到各點(diǎn)的最短路徑，可以采用“反向追蹤”的辦法。如已知，因故記下。因，記下，從而從到的最短路徑是。遞推公式中實(shí)際意義為從到點(diǎn)，至多含有個(gè)中間點(diǎn)的最短路權(quán)。所以在含有個(gè)點(diǎn)的圖中，如果不含有總權(quán)小于零的回路，求從到任一點(diǎn)的最短路權(quán)，用上述算法最多經(jīng)過-1次迭代必定收斂。顯然，如果圖中含有總權(quán)小于零的回路，最短路權(quán)沒有下界。應(yīng)用舉例例5-3設(shè)備更新問題。某企業(yè)使用一臺(tái)設(shè)備，在每年年初，都要決定是否更新。若購置新設(shè)備，要付購買費(fèi)；若

10、繼續(xù)使用舊設(shè)備，則支付維修費(fèi)用。試制定一個(gè)5年更新計(jì)劃，使總支出最少。若已知設(shè)備在各年的購買費(fèi)及不同機(jī)器役齡時(shí)的殘值和維修費(fèi)，如表5-2所示。表5-2第1年第2年第3年第4年第5年購買費(fèi)1112131414機(jī)器役齡0-11-22-33-44-5維修費(fèi)5681118殘值43210解：把這個(gè)問題化為最短路問題用表示第年初購進(jìn)一臺(tái)新設(shè)備，虛設(shè)一個(gè)點(diǎn)，表示第5年底；用弧表示第初購的設(shè)備一直使用到第年年底；弧上的數(shù)字表示第年初購進(jìn)設(shè)備，一直使用到第年底所需支付的購買、維修的全部費(fèi)用。例如，弧上的28是第1年初購買費(fèi)11加上3年的維修費(fèi)5，6，8，減去了3年役齡機(jī)器的殘值2；弧上的20是第2年初購買費(fèi)12

11、減去機(jī)器殘值3與使用2年維修費(fèi)5，6之和，見圖5-11。這樣設(shè)備更新問題就變?yōu)椋呵髲牡降淖疃搪?，?jì)算結(jié)果表明為最短路，路長為49。即在第1年、第3年初各購買一臺(tái)新設(shè)備為最優(yōu)決策，這時(shí)5年的總費(fèi)用為49。5.3最大流問題最大流問題是一類應(yīng)用極為廣泛的問題。例如在交通運(yùn)輸網(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)，為起點(diǎn)，是終點(diǎn)，為中轉(zhuǎn)站，弧上的數(shù)表示該管道的最大輸油能力，問應(yīng)如何安排各管道輸油量，才能使從到的總輸油量最大？5.3.1

12、基本概念與基本定理網(wǎng)絡(luò)與流定義給一個(gè)有向圖，在中指定一點(diǎn)為發(fā)點(diǎn)，另一點(diǎn)為收點(diǎn)，其余的點(diǎn)叫中間點(diǎn)。對(duì)于每一個(gè)弧，對(duì)應(yīng)有一個(gè)（簡寫為），稱為弧的容量。這樣的叫做網(wǎng)絡(luò)，記作。所謂網(wǎng)絡(luò)上的流，是指定義在弧集合上的一個(gè)函數(shù)，并稱為弧上的流量，簡記作?？尚辛髋c最大流容量限制條件：每一弧平衡條件：對(duì)于中間點(diǎn)，有對(duì)于發(fā)點(diǎn)，收點(diǎn)，有稱為這個(gè)可行流的流量?？尚辛骺偸谴嬖诘模缌懔?，。所謂最大流問題，就是求一個(gè)流，使其流量達(dá)到最大，并且滿足以上容量限制條件和平衡條件。其實(shí)最大流問題是一個(gè)特殊的線性規(guī)劃問題，但是利用它與圖的緊密關(guān)系求解，更為直觀簡便。增廣鏈若是網(wǎng)絡(luò)中聯(lián)結(jié)發(fā)點(diǎn)和收點(diǎn)的一條鏈，且鏈的方向是從到，則與鏈的

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

14、個(gè)，即最小截量。最大流量最小截量定理：任一個(gè)網(wǎng)絡(luò)中，從到的最大流的流量等于分離，的最小截集的容量。定理1可行流是最大流，當(dāng)且僅當(dāng)不存在關(guān)于的增廣鏈。證明若是最大流，設(shè)中存在關(guān)于的增廣鏈，令由增廣鏈的定義，可知，令不難驗(yàn)證是一個(gè)可行流，且，這與是最大流假設(shè)矛盾?，F(xiàn)在設(shè)中不存在關(guān)于的增廣鏈，證明是最大流。令，若，且，則令；若，且，則令。因?yàn)椴淮嬖陉P(guān)于的增廣鏈，故。記，于是得到一個(gè)截集，顯然必有所以，。于是必是最大流，定理得證。定理1為我們提供了尋求網(wǎng)絡(luò)最大流的一個(gè)方法。若可行流中存在增廣鏈，說明還有潛力可挖，只須沿增廣鏈調(diào)整流量，得到一個(gè)流量增大的新的可行流；否則是最大流。而判別是否存在增廣鏈，可

15、以根據(jù)是否屬于來進(jìn)行。5.3.2 尋求最大流的標(biāo)號(hào)法（Ford，F(xiàn)ulkerson）設(shè)已有一個(gè)可行流，標(biāo)號(hào)算法分2步：第1步是標(biāo)號(hào)過程，通過標(biāo)號(hào)來尋找增廣鏈；第2步是調(diào)整過程，沿增廣鏈調(diào)整以增加流量。標(biāo)號(hào)過程每個(gè)標(biāo)號(hào)點(diǎn)的標(biāo)號(hào)包含兩部分：第1個(gè)標(biāo)號(hào)明它的標(biāo)號(hào)從哪一點(diǎn)得到，以便找出增廣鏈；第2個(gè)標(biāo)號(hào)是為確定增廣鏈的調(diào)整量用的。 給發(fā)點(diǎn)以標(biāo)號(hào)； 選擇一個(gè)已標(biāo)號(hào)的點(diǎn)，對(duì)于的所有未標(biāo)號(hào)的鄰接點(diǎn)，如果，且，令，并給以標(biāo)號(hào)；如果，且，令，并給以標(biāo)號(hào)。 重復(fù)上述步驟，直到被標(biāo)上號(hào)或不再有頂點(diǎn)可標(biāo)號(hào)為止。如果得到標(biāo)號(hào)，說明存在增廣鏈，轉(zhuǎn)入調(diào)整過程；若未獲得標(biāo)號(hào)，標(biāo)號(hào)過程已無法進(jìn)行時(shí)，說明已是最大流。調(diào)整過程令調(diào)

16、整量，去掉所有標(biāo)號(hào)，對(duì)新的可行流重新進(jìn)行標(biāo)號(hào)過程。例5-4 用標(biāo)號(hào)法求圖5-13所示網(wǎng)絡(luò)的最大流?；∨缘臄?shù)是。解：經(jīng)檢查，網(wǎng)絡(luò)中的流是可行流，下面分析是否可以增加流量。（一） 標(biāo)號(hào)過程1、 首先給標(biāo)上；2、檢查，在弧上，則的標(biāo)號(hào)為，其中。在弧上，不滿足標(biāo)號(hào)條件。3、檢查，在弧上，不滿足標(biāo)號(hào)條件。在弧上，則的標(biāo)號(hào)為，。4、檢查，在弧上，則給標(biāo)號(hào)，。在弧上，給標(biāo)號(hào)，。5、在中任選一個(gè)進(jìn)行檢查，例如，在弧 上，給標(biāo)號(hào)，。因有了標(biāo)號(hào)，故轉(zhuǎn)入調(diào)整過程。（二）調(diào)整過程按點(diǎn)的第一個(gè)標(biāo)號(hào)找到一條增廣鏈，如圖5-14中雙箭線所示。則見：按，在增廣鏈上調(diào)整。上：上：其余的不變。調(diào)整后得到圖5-15所示的可行流，對(duì)

17、這個(gè)可行流進(jìn)行標(biāo)號(hào)，尋找增廣鏈。開始給標(biāo)號(hào)，檢查，給標(biāo)以，檢查，弧上，弧上，均不符合條件，標(biāo)號(hào)過程無法繼續(xù)下去，算法結(jié)束。這時(shí)圖5-15 可行流即最大流。最大流為：。與此同時(shí)可找到最小截集，其中為標(biāo)號(hào)點(diǎn)集，即，為未標(biāo)號(hào)點(diǎn)集，截集，最小截量為5。由上述可見，用標(biāo)號(hào)法找增廣鏈找到最大流的同時(shí)，得到一個(gè)最小截集。最小截集的容量大小影響網(wǎng)絡(luò)最大流量。因此為提高總的輸送量，必須首先考慮改善最小截集中各弧的輸送能力。另一方面，一旦最小截集中弧的通過能力被 降低，就會(huì)使總的輸送量減少。5.4 網(wǎng)絡(luò)計(jì)劃20世紀(jì)50年代以來，國外陸續(xù)出現(xiàn)一些計(jì)劃管理的新方法，如關(guān)鍵路線法（Critical Path Metho

18、d，縮寫為CPM），計(jì)劃評(píng)審方法（Program Evaluation Review Technique，縮寫為PETR）等。這些方法都是建立在網(wǎng)絡(luò)模型基礎(chǔ)之上，稱為網(wǎng)絡(luò)計(jì)劃技術(shù)，廣泛應(yīng)用于工業(yè)、農(nóng)業(yè)、國防、科研等計(jì)劃管理中，對(duì)縮短工期，節(jié)約人力、物力和財(cái)力，提高經(jīng)濟(jì)效益發(fā)揮了重要作用。我國數(shù)學(xué)家華羅庚先生將這些方法總結(jié)概括為統(tǒng)籌方法，引入中國并推廣應(yīng)用。統(tǒng)籌方法的基本原理是：從需要管理的任務(wù)的總進(jìn)度著眼，以任務(wù)中各工作所需要的工時(shí)為時(shí)間因素，按照工作的先后順序和相互關(guān)系作出網(wǎng)絡(luò)圖，以反映任務(wù)全貌，實(shí)現(xiàn)管理過程的模型化。然后進(jìn)行時(shí)間參數(shù)計(jì)算，找出計(jì)劃中的關(guān)鍵工作和關(guān)鍵路線，對(duì)任務(wù)的各項(xiàng)工作所需

19、的人、財(cái)、物通過改善網(wǎng)絡(luò)計(jì)劃作出合理安排，得到最優(yōu)方案并付諸實(shí)施。通過對(duì)各種評(píng)價(jià)指標(biāo)進(jìn)行定量化分析，在計(jì)劃的實(shí)施過程中，進(jìn)行有效的監(jiān)督與控制，以保證任務(wù)高質(zhì)量地完成。5.4.1 網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖是由節(jié)點(diǎn)、弧及權(quán)所構(gòu)成的有向圖，即有向的賦權(quán)圖。節(jié)點(diǎn)表示事項(xiàng)，弧表示工序（活動(dòng)）。工序是在工藝技術(shù)和組織管理上相對(duì)獨(dú)立的工作或活動(dòng)，需要一定的時(shí)間與資源，而事項(xiàng)則表示一個(gè)或若干工序的開始或結(jié)束，是相繼工序的分界點(diǎn)。權(quán)表示為完成某個(gè)工序所需要的時(shí)間或資源等數(shù)據(jù)。例如某工序可以表示為：，為箭頭節(jié)點(diǎn)，表示工序開始，為箭頭尾節(jié)點(diǎn)，表示工序結(jié)束，5為完成本工序所需時(shí)間。網(wǎng)絡(luò)圖是有向圖，按照工藝流程的順序，規(guī)定工序從左

20、向右排列，再給節(jié)點(diǎn)統(tǒng)一編號(hào)，節(jié)點(diǎn)由小到大編號(hào)。對(duì)任一工序來講，要求。始點(diǎn)編號(hào)可以從1開始。在繪制網(wǎng)絡(luò)圖時(shí)，還要注意以下規(guī)則：網(wǎng)絡(luò)圖只能有一個(gè)總起點(diǎn)事項(xiàng)，一個(gè)總終點(diǎn)事項(xiàng)。網(wǎng)絡(luò)圖不能有缺口和回路。兩節(jié)點(diǎn)之間只能有一條弧。正確表示工作之間的前行、后繼關(guān)系。如圖5-16表示兩工序結(jié)束后，兩工序才開始。為的緊前工序，為的緊后工序。虛工序的應(yīng)用。如果的工序關(guān)系是：必須在均完成后才能開工，而只要在完成后即可開工。也就是說，是的緊前工序，而只有是的緊前工序。這樣必須用圖5-17來表示，其中是一個(gè)虛工序，只表示、兩節(jié)點(diǎn)的銜接關(guān)系，不需要人力、物力等資源和時(shí)間。虛工序還可以用于正確表示平行與交叉作業(yè)。一道工序分為

21、幾道工序同時(shí)進(jìn)行，稱為平行作業(yè)。如圖5-18（a）中市場(chǎng)調(diào)研需12天，如增加人力分為3組同時(shí)進(jìn)行，可以畫為5-18（b）。兩個(gè)或兩個(gè)以上的工作交叉進(jìn)行，稱為交叉作業(yè)。如工作與工作分別為挖溝和埋管子，那么它們的關(guān)系可以是挖一段，埋一段，不必等溝全部挖好再埋。這樣，我們可用圖5-19來表示交叉作業(yè)。根據(jù)上述規(guī)則繪制網(wǎng)絡(luò)圖，是為了保證網(wǎng)絡(luò)圖的正確性。此外，為了使圖面布局合理，層次分明，條理清楚，還要注意畫圖技巧。避免弧的交叉，盡可能將關(guān)鍵路線布置在中心位置，將聯(lián)系緊密的工序布置在相近的位置。例5-5 某項(xiàng)新產(chǎn)品投產(chǎn)前全部準(zhǔn)備工作（如表5-3）列示各工序與所需時(shí)間以及它們之間的相互關(guān)系。要求編制該項(xiàng)工

22、程的網(wǎng)絡(luò)計(jì)劃。表5-3工序工序內(nèi)容緊前工序工時(shí)（周）A市場(chǎng)調(diào)查/4B資金籌措/10C需求分析A3D產(chǎn)品設(shè)計(jì)A6E產(chǎn)品研制D8F制定成本計(jì)劃C，E2G制定生產(chǎn)計(jì)劃F3H籌備設(shè)備B，G2I原材料準(zhǔn)備B，G8J安裝設(shè)備H5K人員準(zhǔn)備G2L準(zhǔn)備開工投產(chǎn)I，J，K1根據(jù)以上規(guī)則，繪制的網(wǎng)絡(luò)圖如5-20所示。5.4.2 時(shí)間參數(shù)計(jì)算計(jì)算網(wǎng)絡(luò)圖中有關(guān)的時(shí)間參數(shù)，主要目的是找出關(guān)鍵路線，為網(wǎng)絡(luò)計(jì)劃的優(yōu)化、調(diào)整和執(zhí)行提供明確的時(shí)間概念。通常把網(wǎng)絡(luò)圖中需時(shí)最長的路線叫做關(guān)鍵路線，如圖5-21所示網(wǎng)絡(luò)中雙箭線表示的為關(guān)鍵路線，關(guān)鍵路線上的工序稱為關(guān)鍵工序。要想使任務(wù)按期完或提前完工，就要在關(guān)鍵路線的關(guān)鍵工序上想辦法

23、。網(wǎng)絡(luò)圖的時(shí)間參數(shù)包括工序所需時(shí)間、事項(xiàng)最早、最遲時(shí)間，工序的最早、最遲時(shí)間及時(shí)差等，下面分別敘述。一、 工序時(shí)間的確定工序的所需時(shí)間可記為，有以下兩種情況：完成工序所需時(shí)間確定，只給出一個(gè)時(shí)間值。在具備勞動(dòng)定額資料的條件下，或者在具有類似工序的作業(yè)時(shí)間消耗的統(tǒng)計(jì)資料時(shí)，用對(duì)比分析來確定作業(yè)時(shí)間。在影響工序因素較多，作業(yè)時(shí)間難以準(zhǔn)確估計(jì)時(shí)，可以采用三點(diǎn)時(shí)間估計(jì)法來確定作業(yè)時(shí)間：最快可能完成時(shí)間最可能完成時(shí)間最慢可能完成時(shí)間一般情況下，可按下列公式近似計(jì)算作業(yè)時(shí)間。概率型網(wǎng)絡(luò)圖與確定型網(wǎng)絡(luò)圖在工時(shí)確定后，對(duì)其他時(shí)間參數(shù)的計(jì)算基本相同。二、 事項(xiàng)時(shí)間參數(shù)事項(xiàng)最早時(shí)間事項(xiàng)的最早時(shí)間用表示，它表示以為

24、始點(diǎn)的各工序最早可能開始的時(shí)間，也表示以為終點(diǎn)的各工序的最早可能完成時(shí)間。它等于從始點(diǎn)事項(xiàng)起到本事項(xiàng)最長路線的時(shí)間長度。事項(xiàng)最早時(shí)間可用下列遞推公式，按照事項(xiàng)編號(hào)從小到大順序逐個(gè)計(jì)算。式中，為事項(xiàng)相鄰的各緊前事項(xiàng)的最早時(shí)間。事項(xiàng)的最遲時(shí)間事項(xiàng)的最遲時(shí)間用表示，它表明在不影響任務(wù)總工期條件下，以它為始點(diǎn)的工序的最遲必須開始時(shí)間，或以它為終點(diǎn)的各工作的最遲必須完成時(shí)間。在一般情況下，把任務(wù)的最早完工時(shí)間作為任務(wù)的總工期，所示事項(xiàng)最遲時(shí)間的計(jì)算方法如下：為事項(xiàng)相鄰的各緊后事項(xiàng)的最遲時(shí)間，它的計(jì)算從終點(diǎn)事項(xiàng)開始，按編號(hào)由大到小的順序逐個(gè)計(jì)算。三、 工序的時(shí)間參數(shù)工序的最早可能開始時(shí)間和最早可能完工時(shí)間

25、一個(gè)工序的最早可能開工時(shí)間用表示，任何一個(gè)工序都必須在其所有緊前工序全部完工后才能開始。工序的最早可能完工時(shí)間用表示，它表示工作按最早開工時(shí)間開始所能達(dá)到的完工時(shí)間，計(jì)算公式如下：工序的最早可能開工時(shí)間等于事項(xiàng)最早時(shí)間。工序的最遲必須開工時(shí)間與最遲必須完工時(shí)間一個(gè)工序的最遲必須開工時(shí)間用表示，它是工序在不影響整個(gè)任務(wù)如期完成的前提下，必須開始的最晚時(shí)間。工序最遲必須完工時(shí)間用表示，它表示工作按最遲時(shí)間開工，所能達(dá)到的完工時(shí)間。工序最遲必須完工時(shí)間等于事項(xiàng)的最遲時(shí)間四、時(shí)差。工序的時(shí)差，又稱為工序的機(jī)動(dòng)時(shí)間，工序時(shí)差分兩種：工序總時(shí)差在不影響工程最早結(jié)束時(shí)間的條件下，工序最早開始（或結(jié)束）時(shí)間可

26、以推遲的時(shí)間：工序單時(shí)差不影響緊后工序最早開始時(shí)間的條件下，工序最早結(jié)束時(shí)間可以推遲的時(shí)間：式中，為工序的緊后工序的最早開始時(shí)間。總時(shí)差為零的工序，開始和結(jié)束的時(shí)間沒有一點(diǎn)機(jī)動(dòng)的余地，由這些工序所組成的路線就是網(wǎng)絡(luò)中的關(guān)鍵路線，這些工序就是關(guān)鍵工序。例5-6：確定圖5-20所示網(wǎng)絡(luò)的關(guān)鍵路線。解：先用圖上計(jì)算法求解，再用表上計(jì)算法驗(yàn)證。根據(jù)圖5-20的資料，先計(jì)算各事項(xiàng)的時(shí)間參數(shù)。事項(xiàng)時(shí)間如總開工事項(xiàng)，將結(jié)果填入圖中編號(hào)上方空格 的左邊。逐個(gè)計(jì)算事項(xiàng)最早時(shí)間，得到總完工事項(xiàng)，說明整個(gè)工作需要32周的時(shí)間完成。再從后面開始計(jì)算各事項(xiàng)最遲時(shí)間，如總完工事項(xiàng)的，事項(xiàng)的將結(jié)果填入編號(hào)上方空格 右邊。工

27、序時(shí)間工序時(shí)間有4種：，用圖標(biāo) 表示，計(jì)算結(jié)果表示在圖5-22上。時(shí)差根據(jù)圖5-22中的結(jié)果，可以求出各工序的總時(shí)差。由總時(shí)差為0的工序組成關(guān)鍵路線，即：，總工期為32周。表5-4用來計(jì)算網(wǎng)絡(luò)時(shí)間，并標(biāo)示出關(guān)鍵工序。表5-4工序關(guān)鍵工序A404040B10010132313C347151811D64104100E8101810180F2182018200C3202320230虛工序0232323230H2232524261I8233123310J5233026311K2252529316L13132313205.4.3 網(wǎng)絡(luò)優(yōu)化繪制網(wǎng)絡(luò)圖，計(jì)算網(wǎng)絡(luò)時(shí)間和確定關(guān)鍵路線，得到一個(gè)初始的計(jì)劃方案。從

28、工期、成本、資源等方面對(duì)初步方案進(jìn)一步的改善和調(diào)整，以求得最佳效果，就是網(wǎng)絡(luò)優(yōu)化。目前尚未有能全面反映工期、成本、資源的綜合數(shù)學(xué)模型，因此，網(wǎng)絡(luò)優(yōu)化問題是根據(jù)實(shí)際情況分為時(shí)間優(yōu)化、時(shí)間-資源優(yōu)化和時(shí)間-費(fèi)用優(yōu)化。1、 時(shí)間優(yōu)化根據(jù)對(duì)計(jì)劃進(jìn)度的要求，縮短工程完工時(shí)間?？梢圆扇〈胧喊汛?lián)工序改為平行或交叉工序，縮短關(guān)鍵工序的作業(yè)時(shí)間；充分利用非關(guān)鍵工序的時(shí)差，減少這些作業(yè)的人力、資源用于關(guān)鍵工序，縮短關(guān)鍵工序的作業(yè)時(shí)間。2、 時(shí)間-資源優(yōu)化在編制網(wǎng)絡(luò)計(jì)劃安排工程進(jìn)度時(shí)，考慮時(shí)間優(yōu)化的同時(shí)，盡量合理地利用有限的資源。具體的要求和做法是：優(yōu)先安排關(guān)鍵工序所需要的資源；利用非關(guān)鍵工序的總時(shí)差，錯(cuò)開各工

29、序的開始時(shí)間，拉平資源需要量的高峰；綜合考慮資源和時(shí)間，必要時(shí)，可適當(dāng)?shù)赝七t工程完工時(shí)間。在優(yōu)化時(shí)，通常將計(jì)劃的各主要資源需要量按日程排出，再按以上方法，使各主要資源的日負(fù)荷相對(duì)平衡。但是由于一項(xiàng)工程所包含的工序繁多，涉及到的資源利用情況復(fù)雜，需要多次綜合平衡，才能得到在時(shí)間進(jìn)度和資源利用等方面都比較合理的計(jì)劃方案。3、 時(shí)間-費(fèi)用優(yōu)化時(shí)間-費(fèi)用優(yōu)化要研究和解決的問題是決定合理的工程完工時(shí)間，使費(fèi)用最省，或者以合理的費(fèi)用代價(jià)完成趕工作任務(wù)。工程費(fèi)用包括兩大類：直接費(fèi)用是完成各項(xiàng)工作直接所需人力、資源設(shè)備費(fèi)用；為縮短工序的作業(yè)時(shí)間，需要采取一定的技術(shù)組織措施，相應(yīng)會(huì)增加一部分直接費(fèi)用。間接費(fèi)用是

30、指管理費(fèi)、辦工費(fèi)等，常按施工時(shí)間長短分?jǐn)?。完成工程?xiàng)目的直接費(fèi)用、間接費(fèi)用、總費(fèi)用與工程完工時(shí)間的關(guān)系，一般情況下如圖5-23所示。顯然，在網(wǎng)絡(luò)計(jì)劃中，最低成本日程具有重要意義。因此要計(jì)算網(wǎng)絡(luò)計(jì)劃的不同完工期相應(yīng)的總費(fèi)用，以求得成本最低的日程安排，即最低成本日程。下面舉例說明最低成本日程計(jì)劃。例5-7：已知網(wǎng)絡(luò)計(jì)劃各工序的正常工時(shí)、極限工時(shí)及相應(yīng)費(fèi)用如表5-5，網(wǎng)絡(luò)圖如圖5-24。表5-5工序正常工時(shí)極限工時(shí)成本斜率（元/天）時(shí)間（天）費(fèi)用（元）時(shí)間（天）費(fèi)用（元）24500016700025030900018102001002240001848002002610000241030015024

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

32、，工期為64天，實(shí)際只縮短10天，這意味著工序的工時(shí)為20天。重新計(jì)算結(jié)果如圖5-25（b），總工期64天，有兩條關(guān)鍵路線，直接費(fèi)用增10100元，間接費(fèi)用減10330元。重復(fù)上述步驟，將，的工時(shí)縮短為：18，20天，重新計(jì)算網(wǎng)絡(luò)時(shí)間參數(shù)，結(jié)果如圖5-26。關(guān)鍵路線不變。增加直接費(fèi)用2（100+200）=600元，減少間接費(fèi)用2330=660元。第三次調(diào)整，在，工序上多縮短2天，重新計(jì)算網(wǎng)絡(luò)時(shí)間參數(shù)，結(jié)果如圖5-27，有三條關(guān)鍵路線，總工期60天，直接費(fèi)用增加2350=700元，間接費(fèi)用減少2330=660元。由于一條關(guān)鍵路線上各工序工時(shí)不能縮短，計(jì)算結(jié)束。最低成日程為62天，總成本63440

33、元。習(xí)題：5.1有9個(gè)城市，其公路網(wǎng)如圖5-28所示?；∨詳?shù)字是該段公路的長度，有一批貨物從到，問走哪條路最短？5.2用DijKstra方法求圖5-29中從到各點(diǎn)的最短路。5.3求圖5-30網(wǎng)絡(luò)中各頂點(diǎn)間的最短路。5.4某設(shè)備今后5年的價(jià)格預(yù)測(cè)分別是（5，5，6，7，8），若該設(shè)備連續(xù)使用，其第年的維修費(fèi)分別為（1，2，3，5，6）。某單位今年購進(jìn)一臺(tái)，問如何確定更新方案可使5年里總支出最?。ú还茉O(shè)備使用了多少年，其殘值為0）。5.5在如圖5-31所示的網(wǎng)絡(luò)中，每弧旁的數(shù)字是。（1） 確定所有的截集；（2） 求最小截集的容量；（3） 證明指出的流是最大流。5.6求如圖5-32所示的網(wǎng)絡(luò)的最大流

34、，弧上數(shù)為。5.7如圖5-33，發(fā)點(diǎn)分別可供應(yīng)10和15個(gè)單位，收點(diǎn)可以接收10和25個(gè)單位，求最大流，弧上數(shù)為。5-8試畫出表5-6所表示項(xiàng)目的網(wǎng)絡(luò)圖。表5-6工作工時(shí)（d）緊前工序工作工時(shí)（d）緊前工序A15-F5D，EB10-G20C，F(xiàn)C10A，BH10D，ED10A，BI15G，HE5B5-9設(shè)有如圖5-34網(wǎng)絡(luò)圖，用圖上計(jì)算法計(jì)算時(shí)間參數(shù)，并求出關(guān)鍵路線。5-10繪 制表5-7所示的網(wǎng)絡(luò)圖，并用表上計(jì)算法計(jì)算工作的各項(xiàng)時(shí)間參數(shù)，確定關(guān)鍵路線。表5-7工作工時(shí)（d）緊前工序工作工時(shí)（d）緊前工序A5-F4B，CB8A，CG8CC3AH2F，GD6CI4E，HE10B，CJ5F，G5-11已知下列資料表5-8活動(dòng)作業(yè)時(shí)間（d）緊前活動(dòng)正常完成進(jìn)度的直接費(fèi)用（百元）趕進(jìn)度1天所需費(fèi)用（百元）A4-205B8-304C6B153D3A52E5A184F7A407G4B，D103H3E，F(xiàn)，G156工程的間接費(fèi)5（百元/天），求出該項(xiàng)工程的最低成本日程。28