第3章-圖論初步與物流工程項(xiàng)目計(jì)劃編制

物流運(yùn)籌學(xué)教學(xué)課件第3章圖論初步與物流工程項(xiàng)目計(jì)劃編制圖的基本概念1路徑、回路與連通性2生產(chǎn)加工順序的安排3工程項(xiàng)目計(jì)劃的橫道圖表示法4計(jì)劃評(píng)審方法與關(guān)鍵路線法53.1圖的基本概念3.13.1.1圖定義1

圖G是由非空結(jié)點(diǎn)集合

以及邊集合

所組成。其中每條邊可以用一個(gè)結(jié)點(diǎn)表示，亦即

3.1.1圖定義中的結(jié)點(diǎn)對(duì)可以是有序的，也可以是無(wú)序的。若邊e所對(duì)應(yīng)的結(jié)點(diǎn)對(duì)（a，b）是有序的，則稱(chēng)e是有向邊。

a稱(chēng)為e的起點(diǎn)，

b稱(chēng)為e的終點(diǎn)。若邊e所對(duì)應(yīng)的結(jié)點(diǎn)對(duì)（a，b）是無(wú)序的，則稱(chēng)e是無(wú)向邊。圖中所有邊均是有向邊的圖稱(chēng)為有向圖；圖中所有邊均是無(wú)向邊的圖稱(chēng)為無(wú)向圖；同時(shí)含有有向邊和無(wú)向邊的圖稱(chēng)為混合圖。3.1.1圖例3.1（1）設(shè)無(wú)向圖

其中

，

，

，

.

（2）設(shè)有向圖

，其中

，

，

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

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

設(shè)G=<V，E>是一個(gè)有向圖，以結(jié)點(diǎn)v為起點(diǎn)的邊數(shù)稱(chēng)為結(jié)點(diǎn)v的出度，記為deg（v

）；

以結(jié)點(diǎn)v為終點(diǎn)的邊數(shù)稱(chēng)為結(jié)點(diǎn)v的入度，記為deg（v）；對(duì)G中每個(gè)結(jié)點(diǎn)v，

deg（v

）+deg（v）稱(chēng)為結(jié)點(diǎn)v的度數(shù)，也記為deg（v）。定義4設(shè)G=<V，E>是一個(gè)圖，度數(shù)為奇（偶）數(shù)的結(jié)點(diǎn)稱(chēng)為奇（偶）結(jié)點(diǎn)。

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

v2

，…，

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

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

定義6設(shè)G是有向簡(jiǎn)單圖，若將它的所有邊都代之以無(wú)向邊后成為一個(gè)無(wú)向完全圖，則G稱(chēng)為有向完全圖。

3.1.1圖定理1一個(gè)有n個(gè)結(jié)點(diǎn)的完全圖共有

條邊。推論

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

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

3.1.2圖的同構(gòu)用圖形表示圖的時(shí)候，可能會(huì)有這樣的情形：兩個(gè)看似很不一樣的圖形，實(shí)際上表示的是同一個(gè)圖?；蛘哒f(shuō)，兩個(gè)圖形僅僅是點(diǎn)的名字或位置不同，而作為圖來(lái)講，他們的結(jié)構(gòu)是一樣的。我們把這樣的兩個(gè)圖形所表示的兩個(gè)圖形稱(chēng)為同構(gòu)。3.1.2圖的同構(gòu)定義7

設(shè)G=<V，E>

，

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

當(dāng)且僅當(dāng)

則稱(chēng)G和G’是同構(gòu)的，記作G

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

設(shè)G=<V，E>是無(wú)相圖，

V有n個(gè)結(jié)點(diǎn)，又設(shè)Ek是完全圖Kn的邊集，則一個(gè)由G的點(diǎn)集V和Ek

-E為邊集的圖稱(chēng)為G的補(bǔ)圖，記作

3.1.3補(bǔ)圖與子圖定義9設(shè)有圖G=<V，E>，

G’=<V’，E’>若

和

則稱(chēng)G’為G的子圖。特別是在V=V’而同時(shí)有

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

并且vi-1

,vi分別是邊ei

的起點(diǎn)與終點(diǎn)（

i=1,2，…，k），則稱(chēng)點(diǎn)邊的交錯(cuò)序列L:v1

e1

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

=vk

，則稱(chēng)L為回路。在路徑L中，如果e1e2…ek互不相同，則稱(chēng)L為簡(jiǎn)單路徑。在路徑L中，如果v1v2

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

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

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

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

設(shè)u，v是有向圖的兩個(gè)結(jié)點(diǎn)，若u到v是可達(dá)的，則u到v的一切路徑的長(zhǎng)度的最小值稱(chēng)為u到v的距離，記為d（u，v）。如果u到v是不可達(dá)的，則記

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

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

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

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

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

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

支模2

綁鋼筋1

綁鋼筋2

澆混凝土1

澆混凝土2

3.4工程項(xiàng)目計(jì)劃的橫道圖表示法【例3.7】

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

3.5.2計(jì)劃評(píng)審方法網(wǎng)絡(luò)圖的計(jì)算解:先按表3-8給出的資料畫(huà)出計(jì)劃評(píng)審方法網(wǎng)絡(luò)圖圖中①為整個(gè)網(wǎng)絡(luò)的最初事件，⑧為最終事件。標(biāo)在箭線上面的時(shí)間是完成各項(xiàng)作業(yè)的計(jì)劃時(shí)間。為了對(duì)網(wǎng)絡(luò)圖進(jìn)行分析，需要計(jì)算作業(yè)的最早開(kāi)始時(shí)間、最遲開(kāi)始時(shí)間和作業(yè)的最早結(jié)束時(shí)間、最遲結(jié)束時(shí)間

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

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

3.5.2計(jì)劃評(píng)審方法網(wǎng)絡(luò)圖的計(jì)算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計(jì)劃評(píng)審方法網(wǎng)絡(luò)圖的計(jì)算表的第1欄填寫(xiě)網(wǎng)絡(luò)圖上的全部作業(yè)。從起點(diǎn)事件中編號(hào)相同的作業(yè)，按終點(diǎn)事件編號(hào)由小到大填寫(xiě)；表的第2欄填寫(xiě)各項(xiàng)作業(yè)的計(jì)劃時(shí)間

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

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

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

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

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

假如例3.9所列的工程要求在49d完成。為加快進(jìn)度，表3-10中列出了表3-9中可縮短工時(shí)的所有作業(yè)，表明這些作業(yè)計(jì)劃完成時(shí)間（d）、最短完成時(shí)間（d）以及比原計(jì)劃縮短一天額外增加的費(fèi)用（元/d）。問(wèn)應(yīng)如何安排，使額外增加的總費(fèi)用為最小。作業(yè)代號(hào)計(jì)劃完成時(shí)間/d最短完成時(shí)間/d縮短1d增加的費(fèi)用（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關(guān)鍵路線和網(wǎng)絡(luò)計(jì)劃的優(yōu)化3.5.3關(guān)鍵路線和網(wǎng)絡(luò)計(jì)劃的優(yōu)化本例中關(guān)鍵路線上的作業(yè)有3項(xiàng)：B、G、K，其中作業(yè)K縮短1d的費(fèi)用為最少。工期要求縮短3天，該項(xiàng)作業(yè)最多可縮短4天，但作業(yè)（7，8）的自由時(shí)差只有1天，即工程的工期縮短1天將出現(xiàn)新的關(guān)鍵路線，即有

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

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

。故決定將作業(yè)

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

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

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

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

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

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

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

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

突擊35232860

成本（萬(wàn)元）正常100280502001602302001001320突擊2005201003601603504802002370成本費(fèi)用率1001205080—60140100

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

將總工期壓縮到15天。將關(guān)鍵工作中成本費(fèi)用率最小的工作D壓縮1天，工程的總成本增加80萬(wàn)元，即直接總成本為1400萬(wàn)元。并且關(guān)鍵路徑和關(guān)鍵工作沒(méi)有改變。3.5.3關(guān)鍵路線和網(wǎng)絡(luò)計(jì)劃的優(yōu)化方案2

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

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