第3章-圖論初步與物流工程項目計劃編制

物流運籌學教學課件第3章圖論初步與物流工程項目計劃編制圖的基本概念1路徑、回路與連通性2生產加工順序的安排3工程項目計劃的橫道圖表示法4計劃評審方法與關鍵路線法53.1圖的基本概念3.13.1.1圖定義1

圖G是由非空結點集合

以及邊集合

所組成。其中每條邊可以用一個結點表示，亦即

3.1.1圖定義中的結點對可以是有序的，也可以是無序的。若邊e所對應的結點對（a，b）是有序的，則稱e是有向邊。

a稱為e的起點，

b稱為e的終點。若邊e所對應的結點對（a，b）是無序的，則稱e是無向邊。圖中所有邊均是有向邊的圖稱為有向圖；圖中所有邊均是無向邊的圖稱為無向圖；同時含有有向邊和無向邊的圖稱為混合圖。3.1.1圖例3.1（1）設無向圖

其中

，

，

，

.

（2）設有向圖

，其中

，

，

畫出G與G’的圖形。3.1.1圖圖G圖G’3.1.1圖對于邊ei{vk,vt}不管ei為有向還是無向，都稱邊ei與結點vk及vt相關聯(lián)，而vk與vt稱為鄰接的。若干條邊關聯(lián)于同一個結點，則這些邊稱為鄰接的。一條邊若與兩個相同的結點相關聯(lián)則稱為環(huán)。不與任何結點鄰接的結點稱為孤立點。3.1.1圖一個具有n個結點、m條邊所組成的圖G稱為（n，m）圖，其中結點個數(shù)n稱為圖G的階數(shù)。如果圖G是一個（n，0）圖，則稱G為零圖。在有向圖中，兩結點間（包括結點自身間）若有同起點和終點的幾條邊，則這幾條邊稱為平行邊。在無向圖中，兩結點間（包括結點自身間）若有幾條邊，則這幾條邊稱為平行邊。含有平行邊的圖稱為多重圖。不含平行邊的圖稱為簡單圖。有時在一個圖中，邊的旁側加一些數(shù)字一刻畫某些特征，稱為邊的權。每條邊都有權的圖稱為加權圖。3.1.1圖定義2設G=<V，E>是一個無向圖，結點v所關聯(lián)的邊數(shù)（有環(huán)時計算兩次），稱為

結點v的度數(shù)，記為deg（v）。定義3

設G=<V，E>是一個有向圖，以結點v為起點的邊數(shù)稱為結點v的出度，記為deg（v

）；

以結點v為終點的邊數(shù)稱為結點v的入度，記為deg（v）；對G中每個結點v，

deg（v

）+deg（v）稱為結點v的度數(shù)，也記為deg（v）。定義4設G=<V，E>是一個圖，度數(shù)為奇（偶）數(shù)的結點稱為奇（偶）結點。

3.1.1圖結點的度數(shù)的性質：設G=<V，E>是一個（n，m）圖，它的結點集合為V={v1，

v2

，…，

vn}，則在有向圖中，上式也可以寫成

在（n，m）圖中，奇結點必為偶數(shù)個。在有向圖中，所有結點的出度之和與所有結點的入度之和相等，即3.1.1圖定義5設G是有n個結點的簡單無向圖，若它的任何兩個不同結點之間恰有一條邊，這樣的無向圖稱為無向完全圖，記為Kn

定義6設G是有向簡單圖，若將它的所有邊都代之以無向邊后成為一個無向完全圖，則G稱為有向完全圖。

3.1.1圖定理1一個有n個結點的完全圖共有

條邊。推論

完全圖Kn的每一結點的度數(shù)為n-1,

圖的總度數(shù)為n（n-1）

3.1.2圖的同構用圖形表示圖的時候，可能會有這樣的情形：兩個看似很不一樣的圖形，實際上表示的是同一個圖。或者說，兩個圖形僅僅是點的名字或位置不同，而作為圖來講，他們的結構是一樣的。我們把這樣的兩個圖形所表示的兩個圖形稱為同構。3.1.2圖的同構定義7

設G=<V，E>

，

G’=<V’，E’>是兩個圖，若存在從V到V’的雙射函數(shù)f，使得對任意

當且僅當

則稱G和G’是同構的，記作G

≌G’。3.1.2圖的同構3.1.2圖的同構若兩個圖同構，則結點數(shù)相等；若兩個圖同構，則邊數(shù)相等；若兩個圖同構，則度數(shù)相同的結點數(shù)相等。以上三個條件只是兩個圖同構的必要條件而不是充分條件，利用它們不能判定圖的同構性，它們僅是判定兩個圖不同構的有效方法。3.1.3補圖與子圖定義8

設G=<V，E>是無相圖，

V有n個結點，又設Ek是完全圖Kn的邊集，則一個由G的點集V和Ek

-E為邊集的圖稱為G的補圖，記作

3.1.3補圖與子圖定義9設有圖G=<V，E>，

G’=<V’，E’>若

和

則稱G’為G的子圖。特別是在V=V’而同時有

時，稱G’為G的生成子圖。3.2路徑、回路與連通性3.23.2.1路徑與回路定義1設有向圖G=<V，E>，

并且vi-1

,vi分別是邊ei

的起點與終點（

i=1,2，…，k），則稱點邊的交錯序列L:v1

e1

v2e3…vk-1ekvk為圖中從v0至vk的路徑，K稱為該路徑的長度。3.2.1路徑與回路在路徑L中，如果vi

=vk

，則稱L為回路。在路徑L中，如果e1e2…ek互不相同，則稱L為簡單路徑。在路徑L中，如果v1v2

…vk互不相同，則稱L為基本路徑。3.2.1路徑與回路【例3.2】

圖3-7中所給出的從結點v1出發(fā)而終止于結點v3的一些路徑是：。

基本路徑簡單路徑既不基本，又不簡單3.2.1路徑與回路部分回路基本回路簡單回路既不基本，又不簡單3.2.1路徑與回路定理1一個有向（n，m）圖中任何基本路徑長度均小于或等于n

-1，而任何基本回路長度均小于或等于n。證明在基本路徑中各結點均是不同的，在長度為K的基本路徑中，不同結點的數(shù)目為k-1，因圖中僅有n個不同結點，所以基本路徑的長度不會超過n-1，對于長度為K的基本回路，不同結點的數(shù)目也為k，因圖中僅有n個不同結點，所以基本回路的長度不會超過n。3.2.1路徑與回路定義2設u，v是有向圖的兩個結點，如果存在一條從u到v的路徑，則稱結點u到v是可達的，否則稱在該圖u到v是不可達。約定，圖的任意一結點到它自身是可達的。3.2.1路徑與回路定義3

設u，v是有向圖的兩個結點，若u到v是可達的，則u到v的一切路徑的長度的最小值稱為u到v的距離，記為d（u，v）。如果u到v是不可達的，則記

。約定d（u，v）=03.2.2連通性定義4在無向圖G中，如果它的任何兩結點間均是可達的，則稱圖G為連通圖，否則稱圖G為非連通圖。定義5在無向圖G中，如果忽略其邊的方向后得到的無向圖是連通的，則稱此有向圖G是連通的；否則稱為非連通圖。定義6一個有向連通圖G如果其任何兩結點間是互相可達的，則稱圖G為強連通的；如果其任何兩結點間至少存在一方向是可達的，則稱圖G為單向連通的；如果忽略邊的方向后其無向圖是連通的，則稱圖G是弱連通的。3.2.2連通性連通的無向圖非連通的無向圖強連通的有向圖單連通的有向圖弱連通的有向圖3.2.3哥尼斯堡七橋問題與歐拉回路“七橋問題”：哥尼斯堡（現(xiàn)俄羅斯的加里寧格勒）有一條布勒爾河，其兩個支流在城中心匯成一條大河。河中間有兩個島，河的兩岸與這兩個島之間有七座橋連接。哥尼斯堡大學的學生們傍晚散步時，總想一次走過這七座橋，每座橋只走一遍。可是試來試去總辦不到。于是，有學生寫信去請教歐拉，歐拉回信解答了這個問題。3.2.3哥尼斯堡七橋問題與歐拉回路歐拉把七橋問題中的橋與島、陸地（連接點）之間的關系用點與線組成的圖表示：把橋對應為幾何線，把兩岸和島對應為幾何點，得到如圖3-10所示的圖。問題轉變?yōu)椋簭哪骋稽c開始畫，筆不離開紙，一筆畫成又回到出發(fā)點，且各條線只畫一次。3.2.3哥尼斯堡七橋問題與歐拉回路歐拉的推理如下：凡是一筆畫中出現(xiàn)的交點處，線一出一進總應該通過偶數(shù)條，只有作為起點和終點的兩點才有可能通過奇數(shù)條線。因此，凡是奇點個數(shù)多于兩個的平面圖都不可能一筆畫出。圖中的四個點均為奇點，因此不可能一筆畫出。這樣，歐拉就解答了這個問題。歐拉這種處理問題的方法標志著圖論的誕生。3.2.3哥尼斯堡七橋問題與歐拉回路經過圖中所有邊一次，且訪問每個頂點至少一次的一個回路，稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖。3.2.3哥尼斯堡七橋問題與歐拉回路3.2.3哥尼斯堡七橋問題與歐拉回路定理2

無向連通圖具有一條歐拉路徑的充分必要條件是有零個或兩個次數(shù)為奇數(shù)的結點。由該定理2可知，一個圖是否存在歐拉路徑，主要考察：該圖是否連通；結點的度數(shù)為奇數(shù)的個數(shù)。推論無向連通圖G為歐拉圖的充分必要條件是G的每個結點的度數(shù)均為偶數(shù)。3.2.3哥尼斯堡七橋問題與歐拉回路【例3.3】郵遞員從郵局v1出發(fā)沿郵路投遞信件，其郵路如圖3-12所示。試問是否存在一條投遞路線使郵遞員從郵局出發(fā)通過所有路線而不重復且最后回到3.2.3哥尼斯堡七橋問題與歐拉回路解：此問題即為求證圖3-12是否為歐拉圖。由于圖中每個結點的度數(shù)均為偶數(shù)，故由上述推論可知這樣的一條投遞路線是存在的3.2.3哥尼斯堡七橋問題與歐拉回路【例3.4】甲、乙兩只螞蟻分別位于圖3-13中的a、b兩處，并設圖中的每條長度均相等。甲、乙進行比賽：從它們所在的點出發(fā)，走過圖中的所有邊，最后到達c處。如果它們速度相同，問誰先到達目的地？3.2.3哥尼斯堡七橋問題與歐拉回路解：在圖中，

b、c兩個點的度數(shù)均為奇數(shù)，因而存在從b到c的歐拉路徑，螞蟻乙從b走到c

，只要走一條歐拉路徑，邊數(shù)為9。而螞蟻甲要走完所有的邊到達c，必須先走到b，再走一條歐拉路徑，因而它至少要走10條邊才能到達

。所以乙先到達目的地。3.3生產加工順序的安排3.33.3生產加工順序的安排【例3.5】某車間生產四種產品，都要依次經過甲、乙兩臺設備的加工，假定每種產品都必須在設備甲上加工完畢后，才能進入設備乙上加工，每種產品在每臺設備上所需要的加工時間如表3-1所示。問如何安排這些產品的加工順序，可使總的加工時間最短？1234甲3745乙62733.3生產加工順序的安排在設備甲上一種產品加工完后就馬上可以加工另一種產品，但是，在設備乙上一種產品加工完后，由于后面要加工的產品還在設備甲上未加工完，就要出現(xiàn)設備乙不得不空閑著等待設備甲正加工著的另一種產品的情況。因此，要想使總的加工時間盡可能短，即是要求設備的空閑時間的總和盡可能小。如果安排在兩個設備上的加工順序不一樣的話，我們總可以將其調換成同樣的順序，而不會增加設備乙的空閑時間。如圖3-22所示，將設備乙上的加工順序換成與設備甲上的加工順序一樣后，并不增加設備乙的等待時間，甚至還可縮短等待時間。因此，我們只考慮兩臺設備上加工順序相同的安排，也就是確定一個順序。3.3生產加工順序的安排3.3生產加工順序的安排排好時間表，從中數(shù)最小，屬于第一行，應該盡先排，屬于第二行，次序往尾排，劃掉已排者，剩下照樣辦。3.3生產加工順序的安排1234甲3745乙6273最小數(shù)，位于第二行，安排在最后最小數(shù)，位于第一行，第一個生產3.3生產加工順序的安排3.3生產加工順序的安排【例3.6】某車間生產五種產品，都要依次經過甲、乙兩臺設備的加工，產品都必須在設備甲上加工完畢之后，才能進入設備乙加工。每種產品在每臺設備上加工所需時間如表3-2所示?？扇绾伟才胚@些產品的加工順序使總的加工時間最少？12345甲62734乙374573.3生產加工順序的安排3.4工程項目計劃的橫道圖表示法3.43.4工程項目計劃的橫道圖表示法引例

某建筑工程施工計劃如表3-3：其中緊前工作是指該項工作緊接的前一項工作，要等前一項工作完成后該項工作才能開工，例如工作D的緊前工作是B和C,即B和C完工后D才能開工.工作持續(xù)時間是指工作從開始到完成后所用的時間.問：用什么方法可以將工作計劃直觀表示出來，能讓現(xiàn)場管理人員和施工人員都能理解工作的進度和各項工作之間的先后各項？工作序號工作代號工作名稱緊前工作工作持續(xù)時間1A支模1—42B支模2A43C綁鋼筋1A24D綁鋼筋2B,C25E澆混凝土1C66F澆混凝土2D,E63.4工程項目計劃的橫道圖表示法解:如表3-4，橫向為施工進度，縱向為工作項目.由水平時間刻度中畫出代表工作的橫道，表示出工作的開始與結束時間，橫道的長度表示工作的持續(xù)時間.則結合圖形與表格，就可以清晰地表達各項工作的進度和先后各項.完成該工程的總工期為18天.工作項目施工進度（d）2468101214161820支模1

支模2

綁鋼筋1

綁鋼筋2

澆混凝土1

澆混凝土2

3.4工程項目計劃的橫道圖表示法【例3.7】

建設某重型機器制造廠工程進度計劃如表3-5所示：試指出該工程的總工期，并指出大型機器廠房的開工時間、完工時間及工期.3.4工程項目計劃的橫道圖表示法解:由圖可以看出，工程的開工時間為2008年第3季度初，完工時間為2012年第3季度末，全部工期為4年零3個月.其中大型機器廠房的開工時間委2010年第4季度，完工時間為2012年第2季度，該子項目工期為21個月。3.4工程項目計劃的橫道圖表示法【例3.8】某新產品推銷工作計劃如表3-6：試用橫道圖表示該工作計劃，并計算項目的總工期。工作序號工作代號工作項目緊前工作工作持續(xù)時間1A廣告計劃—22B推銷員培訓計劃A23C商店管理人員培訓計劃B24D電視、報紙廣告發(fā)布A35E廣告拷貝A46F準備推銷資料B77G準備培訓資料B68H廣告后繼續(xù)在新聞機構宣傳D,E49I審查、選撥、訓練管理人員C710J實施訓練計劃K,I311K正式推銷新產品F,H,J43.5計劃評審方法和關鍵路線法3.53.5計劃評審方法和關鍵路線法計劃評審方法（PERT）和關鍵路線法（CPM）是網絡分析的一個組成部分，它廣泛應用于系統(tǒng)分析和項目管理。已廣泛應用于建筑施工和新產品的研制計劃、計算機系統(tǒng)的安裝調試、軍事指揮及各種大型復雜工程的控制管理。3.5.1.1計劃評審方法網絡圖的一些基本概念作業(yè)：指任何消耗時間或資源的行動。如新產品設計中的初步設計、技術設計、工裝制造等。根據需要，作業(yè)可以劃分得粗一些，也可以劃分得細一些。事件：標志作業(yè)的開始或結束，本身不消耗時間或資源，或相對作業(yè)講，消耗量可以小到忽略不計。某個事件的實現(xiàn)，標志著在它前面各項作業(yè)（緊前作業(yè)）的結束，又標志著在它之后的各項作業(yè)（緊后作業(yè)）的開始。如機械制造業(yè)中，只有完成鑄鍛件毛坯后，才能開始機加工；各種零部件都完工后，才能進行總裝等。3.5.1.1計劃評審方法網絡圖的一些基本概念事件①是開始進行初步設計的標志，稱為該項作業(yè)的起點事件；事件②是初步設計的結束標志，稱為該項作業(yè)的終點事件；將初步設計這項作業(yè)標記為（1，2）一般某項作業(yè)若起點事件為i，終點事件為j，將該作業(yè)標記為（i，j）作為整個計劃評審方法網絡圖開始的事件稱最初事件，整個計劃評審方法網絡圖結束的事件稱最終事件。3.5.1.1計劃評審方法網絡圖的一些基本概念路線:指計劃評審方法網絡圖中，從最初事件到最終事件的由各項作業(yè)連貫組成的一條路。圖中從最初事件到最終事件可以有不同的路，路的長度是指完成該路上的各項作業(yè)持續(xù)事件的長度和。各項作業(yè)累計時間最長的那條路，稱為關鍵路線，它決定完成網絡圖上所有作業(yè)需要的最短時間。3.5.1.1計劃評審方法網絡圖的一些基本概念圖中用雙箭線表示的那條路是關鍵路線，需要11小時。3.5.1.2建立計劃評審方法網絡圖的準則和注意事項任何作業(yè)在網絡圖中用惟一的箭線表示，任何作業(yè)其終點事件（箭頭事件）的編號必須大于其起點事件（箭尾事件）的編號。若一項作業(yè)需分段進行，它應細分為不同作業(yè)，并用相應不同的箭線表示。兩個事件之間只能畫一條箭線，表示一項作業(yè)。對具有相同開始和結束事件的兩項以上作業(yè)，要引進虛事件和虛作業(yè)。3.5.1.2建立計劃評審方法網絡圖的準則和注意事項各項作業(yè)之間的關系及它們在計劃評審方法網絡圖上的表達方式如下：作業(yè)a結束后可以開始b和c，見圖（a）；作業(yè)c在a和b均結束后才能開始，見圖（b）；b兩項作業(yè)均結束后可以開始c和d，見圖（c）；作業(yè)c在a結束后即可進行，但作業(yè)d必須同時在a和b結束后才能開始，見圖（d）。3.5.1.2建立計劃評審方法網絡圖的準則和注意事項任何計劃評審方法網絡圖應有惟一的最初事件和惟一的最終事件。計劃評審方法網絡圖中不允許出現(xiàn)回路計劃評審方法網絡圖的畫法一般從左到右，從上到下，同時為了方便計算和做到美觀清晰,計劃評審方法網絡圖中可以通過調整布局，盡量避免箭線之間的交叉3.5.2計劃評審方法網絡圖的計算【例3.9】某項工程由11項作業(yè)組成（分別用代號A，B，…，J，K表示），其計劃完成時間及作業(yè)間相互關系如表3-8所示D計劃完成時間/d緊前作業(yè)作業(yè)計劃完成時間/d緊前作業(yè)A5—G21B，EB10—H35B，EC11—I25B，ED4BJ15F，G，IE4AK20F，GF15C，D

3.5.2計劃評審方法網絡圖的計算解:先按表3-8給出的資料畫出計劃評審方法網絡圖圖中①為整個網絡的最初事件，⑧為最終事件。標在箭線上面的時間是完成各項作業(yè)的計劃時間。為了對網絡圖進行分析，需要計算作業(yè)的最早開始時間、最遲開始時間和作業(yè)的最早結束時間、最遲結束時間

及時差值。3.5.2計劃評審方法網絡圖的計算第一步：作業(yè)的最早開始時間是它的各項緊前作業(yè)最早結束時間中的最大一個值，作業(yè)的最早結束時間是它的最早開始時間加上該作業(yè)的計劃時間t（i，j）的值。用公式表示時有3.5.2計劃評審方法網絡圖的計算3.5.2計劃評審方法網絡圖的計算第二步；作業(yè)的最遲結束時間是它的各項緊后作業(yè)最遲開始時間中的最小一個，各項作業(yè)的緊后作業(yè)的開始時間應以不延誤整個工期為原則。作業(yè)的最遲開始時間是它的最遲結束時間減去該項作業(yè)的時間。用公式來表示時有3.5.2計劃評審方法網絡圖的計算3.5.2計劃評審方法網絡圖的計算事件①是整個網絡的初始事件，以它為起點的有三項作業(yè)。由此事件①的最遲實現(xiàn)時間為3.5.2計劃評審方法網絡圖的計算第三步；時差。按性質可區(qū)分為作業(yè)的總時差R（i，j）和作業(yè)的自由時差F（i，j）。

R（i，j）是指網絡上多于一項作業(yè)共同擁有的機動時間，并非為某項作業(yè)單獨擁有。F（i，j）是指不影響它的各項緊后作業(yè)最早開工時間條件下，該項作業(yè)可以推遲的開工的最大時間限度。它是一項作業(yè)獨自擁有的機動時間3.5.2計劃評審方法網絡圖的計算

3.5.2計劃評審方法網絡圖的計算12345678作業(yè)（i，j）t（i，j）tES（i，j）tEF（i，j）tLS（i，j）tLF（i，j）R（i，j）F（i，j）（1，2）5051610（1，3）1001001000（1，4）1101151653（2，5）45961011（3，4）41014121620（3，5）01010101000（4，6）151429163122（5，6）211031103100（5，7）251035113610（5，8）351045165166（6，7）03131363654（6，8）203151315100（7，8）1535503651113.5.2計劃評審方法網絡圖的計算表的第1欄填寫網絡圖上的全部作業(yè)。從起點事件中編號相同的作業(yè)，按終點事件編號由小到大填寫；表的第2欄填寫各項作業(yè)的計劃時間

；依據公式（3-1）和（3-2）計算得出第3、4兩欄的數(shù)字，其中第4欄數(shù)字為第2、3兩欄數(shù)字之和。計算時假定

；依據公式（3-3）和（3-4）計算第5、6兩欄數(shù)字，其中第5欄數(shù)字為第6欄數(shù)字與第2欄數(shù)字之差。計算時假定

，并從表的最下端往上推算；表中第7欄數(shù)字

按式（3-5）計算，為表中第6欄減去第4欄，或第5欄減去第3欄數(shù)字；表中第8欄數(shù)字

由公式（3-6）計算得到。3.5.3關鍵路線和網絡計劃的優(yōu)化網絡圖中從最初事件到最終事件的不同的路中，作業(yè)總時間延續(xù)最長的一條路稱關鍵路線。在這條路線上所有作業(yè)的總時差為零。3.5.3關鍵路線和網絡計劃的優(yōu)化例3.9中關鍵路線的持續(xù)時間是51d，其他路線均有機動時間。為了縮短整個計劃進程，就要設法縮短關鍵路線的持續(xù)時間，這就是網絡圖的優(yōu)化或改進。檢查關鍵路線上各項作業(yè)的計劃時間是否訂得恰當，如果訂得過長，可適當縮短；將關鍵路線上的作業(yè)進一步分細，盡可能安排多工位或平行作業(yè)；抽調非關鍵路線上的人力、物力支援關鍵路線上的作業(yè)；有時也可通過重新制定工藝流程，也就是用改變網絡圖結構的辦法來達到縮短時間的目的。不過這種方法工作量大，只有對整個工程的持續(xù)時間有十分嚴格的要求，而用其他方法均不能奏效的情況下才采用。3.5.3關鍵路線和網絡計劃的優(yōu)化【例3.10】

假如例3.9所列的工程要求在49d完成。為加快進度，表3-10中列出了表3-9中可縮短工時的所有作業(yè)，表明這些作業(yè)計劃完成時間（d）、最短完成時間（d）以及比原計劃縮短一天額外增加的費用（元/d）。問應如何安排，使額外增加的總費用為最小。作業(yè)代號計劃完成時間/d最短完成時間/d縮短1d增加的費用（1，3）B108700（1，4）C118400（2，5）E43450（5，6）G2116600（5，8）H3530500（5，7）I2522300（7，8）J1512400（6，8）K20165003.5.3關鍵路線和網絡計劃的優(yōu)化3.5.3關鍵路線和網絡計劃的優(yōu)化本例中關鍵路線上的作業(yè)有3項：B、G、K，其中作業(yè)K縮短1d的費用為最少。工期要求縮短3天，該項作業(yè)最多可縮短4天，但作業(yè)（7，8）的自由時差只有1天，即工程的工期縮短1天將出現(xiàn)新的關鍵路線，即有

，故決定先將作業(yè)（6，8）的完成時間縮短至19d，比原計劃額外增加費用500元。3.5.3關鍵路線和網絡計劃的優(yōu)化重復上述步驟，但注意到圖3-26中有兩條關鍵路線，工期均為50d。為進一步縮短工期，或單獨縮短（1，3）工期，或在⑤—⑦—⑧或⑤—⑥—⑧兩條雙箭線上同時縮短工期。由于前者額外增加的費用少，故決定單獨縮短作業(yè)

的工期?，F(xiàn)工期還需縮短1d，該項作業(yè)最多可縮短2d，又工期再縮短1d后還將出現(xiàn)新的關鍵路線，即

。故決定將作業(yè)

縮短1d，再增加額外費用700元。由于已滿足工期要求，就不需要繼續(xù)調整。由此要求在49d完成表3.10所列工程項目，其計劃評審方法網絡圖見圖3-27，同時比正常施工，額外增加費用500+700=1200元。3.5.3關鍵路線和網絡計劃的優(yōu)化3.5.3關鍵路線和網絡計劃的優(yōu)化【例3.11】已知某工程雙代號網絡計劃如圖3-28所示，圖中數(shù)字為工作的正常持續(xù)時間。已知該工程各項工作的優(yōu)選系數(shù)和最短持續(xù)時間如表3-11。其中，優(yōu)選系數(shù)是綜合考慮質量、安全和費用增加情況確定的。選擇關鍵工作壓縮其持續(xù)時間時，應選擇優(yōu)選系數(shù)最小的關鍵工作。若需要同時壓縮多個關鍵工作的持續(xù)時間時，則它們的優(yōu)選系數(shù)之和最小者應優(yōu)先作為壓縮對象。現(xiàn)假設要求工期為15，試對其進行工期優(yōu)化.工作代號ABCDEGHI優(yōu)選系數(shù)28∞545102最短持續(xù)時間341431623.5.3關鍵路線和網絡計劃的優(yōu)化3.5.3關鍵路線和網絡計劃的優(yōu)化確定網絡計劃的關鍵路徑和總工期。圖3-28的關鍵路徑為①—②—④—⑥，總工期為19。計算總工期應縮短的時間。用計劃工期減去要求的工期，得應縮短的工期時間為19﹣15＝4。實施第1次優(yōu)化。因為關鍵工作為A、D、H，且A的優(yōu)選系數(shù)最小，所以先對A優(yōu)化。由于工作A的最短持續(xù)時間為3，因此可以將工作A壓縮2，即由5壓縮至3。但通過計算知，改變后的網絡計劃中工作A變成了非關鍵工作。為了保證A仍為關鍵工作，再將工作A的持續(xù)時間延長為4，得到網絡計劃如圖3-29所示。此時，圖中有兩條關鍵路徑，即①—②—④—⑥和①—②—④—⑤。3.5.3關鍵路線和網絡計劃的優(yōu)化3.5.3關鍵路線和網絡計劃的優(yōu)化實施第2次優(yōu)化。因為總工期為18，仍大于要求工期，所以需要繼續(xù)優(yōu)化。在圖3-29中，有以下5個壓縮方案：方案1

同時壓縮工作A和B，組合優(yōu)選系數(shù)為2＋8＝10。方案2

同時壓縮工作A和E，組合優(yōu)選系數(shù)為2＋4＝6。方案3

同時壓縮工作B和D，組合優(yōu)選系數(shù)為8＋5＝13。方案4

同時壓縮工作D和E，組合優(yōu)選系數(shù)為5＋4＝9。方案5

壓縮工作H，優(yōu)選系數(shù)為10。這五個方案中，由于第二個方案的組合優(yōu)選系數(shù)最小，因此應該選擇同時壓縮工作A和E的方案。將這兩項工作的持續(xù)時間各壓縮1個單位（壓縮至最短），再確定關鍵路徑和計算總工期（圖3-30）。此時，關鍵路徑仍有兩條，即①—②—④—⑥和①—③—④—⑤。3.5.3關鍵路線和網絡計劃的優(yōu)化3.5.3關鍵路線和網絡計劃的優(yōu)化實施第3次優(yōu)化。因為總工期為17，仍大于要求工期，所以需要繼續(xù)優(yōu)化，在圖3-30中，關鍵工作A和E已不能再壓縮，因此只有兩個壓縮方案：方案1

同時壓縮工作B和D，組合優(yōu)選系數(shù)為8＋5＝13。方案2

壓縮工作H，優(yōu)選系數(shù)為10。這兩個方案中，方案2的優(yōu)選系數(shù)最小，因此應選擇壓縮工作H的方案。將工作H的持續(xù)時間縮短2，得到網絡計劃如圖3-31所示。由于關鍵路徑不變，所以總工期為15，已等于要求工期，故該方案為所求的優(yōu)化方案。3.5.3關鍵路線和網絡計劃的優(yōu)化【例3.12】某工程的時間成本如表3-12，工程網絡圖如圖3-32所示。試對該工程網絡計劃的費用進行優(yōu)化。工作代號ABCDEFGH合計時間（d）正常473521072

突擊35232860

成本（萬元）正常100280502001602302001001320突擊2005201003601603504802002370成本費用率1001205080—60140100

3.5.3關鍵路線和網絡計劃的優(yōu)化3.5.3關鍵路線和網絡計劃的優(yōu)化根據正常時間，確定關鍵路徑。由圖3-32，易得網絡計劃的關鍵路徑為①—②—④—⑤；關鍵工作為A、D、G；總工期16天，直接總成本1320萬元。通過壓縮關鍵工作的持續(xù)時間進行費用優(yōu)化。方案1

將總工期壓縮到15天。將關鍵工作中成本費用率最小的工作D壓縮1天，工程的總成本增加80萬元，即直接總成本為1400萬元。并且關鍵路徑和關鍵工作沒有改變。3.5.3關鍵路線和網絡計劃的優(yōu)化方案2

將總工期壓縮到14天。將將關鍵工作中成本費用率最小的工作D再壓縮1天，（圖3-33），直接總成本為1480萬元。這時，圖3-33中有3條關鍵路徑；①—②—⑤，①—②—④—⑤，①—④—⑤。D仍為關鍵工作。3.5.3關鍵路線和網絡計劃的優(yōu)化方案3

將總工期壓縮到13天。由圖3-33可知，要縮短1天工期，必須使3條關鍵路徑都縮短1天。但工作D已達到突擊時間，所以不能再縮短了。比較各工作成本費用率后可知，使3條關鍵路徑都縮短1天的最佳方案是：A、G各縮短1天，D增加1天，成本增加100＋140﹣80＝160（萬元），直接總成本為1640萬元（圖3-34）3.5.3關鍵路線和網絡計劃的優(yōu)化方案4將總工期壓縮到天。最佳方案是：各縮短天，直接總成本為萬元。方案5將總工期壓縮到天。最佳方案是：各縮短天，直接總成本為萬元。3.5.3關鍵路線和網絡計劃的優(yōu)化如果整個工程的決定因素是工期，那么應選擇方案5。如果整個工程的決定因素是成本，那么必須在這六個方案中尋則總成本最低的方案（方案2）?？偣て冢╠）161514131211直接成本（萬元）132014001480164018402100間接成本（萬元）160015001400130012001100總成本（萬元）2920290028882