第十章網(wǎng)絡(luò)計劃技術(shù)網(wǎng)絡(luò)分析

網(wǎng)絡(luò)分析方法是五十年代中期發(fā)展起來的一種科學(xué)計劃管理技術(shù)，是運籌學(xué)的組成部分，也是系統(tǒng)工程中一種重要方法。網(wǎng)絡(luò)分析方法在國外稱為計劃評審技術(shù)（PERT）和關(guān)鍵路徑法（CPM）國內(nèi)稱為統(tǒng)籌方法。阿波羅登月計劃（1958-1969年）

阿波羅登月計劃的全部任務(wù)分別由地面、空間和登月三部分組成，是一項復(fù)雜龐大的工程項目，它不僅涉及到火箭技術(shù)、電力技術(shù)、冶金和化工等多種技術(shù)，為把人安全地送上月球，還需要了解宇宙空間的物理環(huán)境以及月球本身的構(gòu)造和形狀，它耗資300億美圓，研制零件有幾百萬種，共有二萬家企業(yè)參與，涉及42萬人，歷時11年之久，為完成這項工作，除了考慮每個部門之間的配合和協(xié)調(diào)工作外，還要估計各種未知因素可能帶來的種種影響，面對這些千頭萬緒的工作，千變?nèi)f化的情況，就要求有一個總體規(guī)劃部門運用一種科學(xué)的組織管理方法，綜合考慮，統(tǒng)籌安排來解決。飛行中控制誤差精度達到極高程度（時間上比原計劃相差一分鐘）。特點：

PERT屬于非肯定型，工作時間采用“三個估計值”（最樂觀時間、最可能時間、最悲觀時間）適用于科研項目和一次性計劃，它著重考慮時間因素，主要用于控制進度。特點：

CPM屬于肯定型，工作時間采用“一個估計值”（最可能時間），它適用于工程建設(shè)項目，它往往兼顧時間和費用兩大因素，力求用最低費用去確定工期，在時間和費用兩個方面作出決擇。網(wǎng)絡(luò)圖——用圓圈和箭線表示研究對象之間的相互關(guān)系的網(wǎng)狀圖。例10-1：有一部影片需要分上、下兩集在甲、乙兩個部隊交替放映，中間有一個傳片人，放映順序先甲部隊后乙部隊，部隊到達影院和返回各需要30分鐘，上、下兩集各需要50分鐘，傳片人從甲部隊到乙部隊或從乙部隊到甲部隊各需40分鐘。工作項目：（甲部隊）到影院A：30分鐘放上集B：50分鐘放下集C：50分鐘返回D：

30分鐘工作項目：（傳片人）送上集E：40分鐘返回甲部隊F：40分鐘送下集G：

40分鐘工作項目：（乙部隊）到影院H：30分鐘放上集I：50分鐘放下集J：50分鐘返回K：30分FGIJKDEHBC3050505050303030404040網(wǎng)絡(luò)圖從細部看由工作和結(jié)點組成網(wǎng)絡(luò)圖從整體看由線路和目標(biāo)組成定義（工作）消耗時間和資源的活動稱為工作（工序、作業(yè)）。工作的概念是廣義的：工程項目中混凝土養(yǎng)護，油漆后的干燥，軍事行動中的行軍休息等，雖不消耗資源，但要消耗時間的等待過程也稱為工作。定義（虛工作）延續(xù)時間為零的假定工作，稱為虛工作。用虛箭線表示。定義（緊前工作）緊接在該工作前面的工作，稱為該工作的緊前工作。定義（緊后工作）緊接在該工作后面的工作，稱為該工作的緊后工作。定義（結(jié)點）緊前工作與緊后工作的交接點稱為結(jié)點（節(jié)點、事項）。結(jié)點功能——銜接前后工作和控制工作進程。結(jié)點特征——瞬時性。結(jié)點實現(xiàn)不占用時間。結(jié)點分類——一般性結(jié)點和強制性結(jié)點。強制性結(jié)點——對整個任務(wù)具有生命價值，且它的實現(xiàn)因受外界因素的影響而有一個限制時間結(jié)點。（如修水庫的堤壩合攏；渡江河時間；大橋合攏時間等）定義（線路）從最初結(jié)點到最終結(jié)點連貫的工作序列稱為線路。定義（線路的長度）線路上各工作的延續(xù)時間之和，稱為線路的長度。定義（關(guān)鍵線路）網(wǎng)絡(luò)中所有線路中最長的線路稱為關(guān)鍵線路。關(guān)鍵線路有著特別重要的地位，正是它控制著整個計劃的工期FGIJKDEHBC305050505030303040404013456789102AFGIJKDEHBC305050505030303040404013456789102AFGIJKDEHBC305050505030303040404013456789102AFGIJKDEHBC305050505030303040404013456789102AFGIJKDEHBC305050505030303040404013456789102AFGIJKDEHBC305050505030303040404013456789102AFGIJKDEHBC3050505050303030404040關(guān)鍵線路：1-2-3-4-7-8-9-10關(guān)鍵線路長度=280目標(biāo)目標(biāo)就是為完成預(yù)定的任務(wù)所要達到的根據(jù)客觀實際而確定的主要任務(wù)（或綜合）功能數(shù)量指標(biāo)。大多數(shù)情況下，是以完成任務(wù)的時限作為目標(biāo)。任務(wù)實現(xiàn)的目的只有一個，而其目標(biāo)可能有多個（時間,成本,資源等）相互關(guān)系邏輯關(guān)系——兩件工作之間相互聯(lián)系是客觀固有的，不能隨意改變的。（如電影的上下集之間）組織關(guān)系——工作之間關(guān)系是人為的關(guān)系。它體現(xiàn)了人的主觀能動作用，它的確定主要考慮到效果,時間，資源和經(jīng)濟原則等因素。（如甲乙部隊之間）網(wǎng)絡(luò)計劃的編制（建模）步驟：1將任務(wù)細化2確定工作項目及其關(guān)系3估計工作的延續(xù)時間4繪制網(wǎng)絡(luò)圖5簡化或合并網(wǎng)絡(luò)圖網(wǎng)絡(luò)計劃的時間參數(shù)計算一、控制性參數(shù)最早時間：結(jié)點的最早可能實現(xiàn)時間（ET）工作的最早可能開始時間（ES）工作的最早可能結(jié)束時間（EF）網(wǎng)絡(luò)計劃的時間參數(shù)計算一、控制性參數(shù)最遲時間：結(jié)點的最遲必須實現(xiàn)時間（LT）工作的最遲必須開始時間（LS）工作的最遲必須結(jié)束時間（LF）網(wǎng)絡(luò)計劃的時間參數(shù)計算二、協(xié)調(diào)性參數(shù)工作的總機動時間（TF）工作的局部機動時間（FF）第一類局部機動時間（FF’）第二類局部機動時間（FF’’）網(wǎng)絡(luò)計劃的時間參數(shù)計算公式最早時間：ETS=0ETj=max（ETi+tij）ESij=ETiEFij=ETi+tij網(wǎng)絡(luò)計劃的時間參數(shù)計算公式最遲時間：LTT=D（指令工期，通常D=T）LTi=min（LTj+tij）LFij=LTiLSij=LTj

-tij網(wǎng)絡(luò)計劃的時間參數(shù)計算公式協(xié)調(diào)性參數(shù)：TFij=LTj

-ETi

-tijFF’ij=ETj

-ETi

-tijFF’’ij=LTj

-LTi

-tij

TFFF凡是TF=0的工作便是關(guān)鍵工作，組成的線路便是關(guān)鍵線路。關(guān)鍵線路上的關(guān)鍵結(jié)點必有ET=LT，但不充分。唯一的判斷是TF=0。圖算法——一種簡單有效的方法步驟：1計算結(jié)點最早實現(xiàn)時間（順向計算）2計算結(jié)點最遲實現(xiàn)時間（逆向計算）3確定關(guān)鍵線路（ET=LT）4計算工作的總機動時間（非關(guān)鍵線路）

12345610545101010順向計算最早時間ET012345610545101010順向計算最早時間ET051012345610545101010順向計算最早時間ET05102012345610545101010順向計算最早時間ET05102030123456105451010100510203040計算工期T=40順向計算最早時間ET12345610545101010逆向計算最遲時間LT0510203040令D=T=40123456105451010100510203040令D=T=4040逆向計算最遲時間LT123456105451010100510203040令D=T=404030逆向計算最遲時間LT123456105451010100510203040令D=T=40203040逆向計算最遲時間LT123456105451010100510203040令D=T=4020304010逆向計算最遲時間LT123456105451010100510203040令D=T=402030401026逆向計算最遲時間LT123456105451010100510203040令D=T=4020304010260逆向計算最遲時間LT12345610545101010確定關(guān)鍵線路（ET=LT）05102030402030401026012345610545101010051020304020304010260確定關(guān)鍵線路（ET=LT）12345610545101010051020304020304010260確定關(guān)鍵線路（ET=LT）12345610545101010051020304020304010260確定關(guān)鍵線路（ET=LT）12345610545101010計算總機動時間TF=LTj-Eti-tij051020304020304010260TF35=30-5-4=212112345610545101010051020304020304010260TF25=30-10-5=152115計算總機動時間TF=LTj-Eti-tij12345610545101010051020304020304010260TF13=26-0-5=21211521計算總機動時間TF=LTj-Eti-tij12345610545101010051020304020304010260211521計算總機動時間TF=LTj-Eti-tij網(wǎng)絡(luò)計劃的費用優(yōu)化工作的費用分成直接費用和間接費用。任務(wù)的總費用包括直接費用和間接費用。網(wǎng)絡(luò)計劃的費用優(yōu)化一般任務(wù)的直接費用是隨著工期的縮短而增加一般任務(wù)的間接費用是隨著工期的縮短而減少?？偞嬖谝粋€總費用最少的最優(yōu)工期。時間費用TPCP間接費用曲線直接費用曲線總費用曲線費用斜率K

在線性假定下，工作延續(xù)時間每縮短一個單位時間所增加的費用稱為費用斜率KK=（CM-CN）/（TN-TM）費用斜率K例11-2：某一個工作正常時間為7天，費用為360元，最短時間為4天，費用450元，則K=（450-360）/（7-4）=30元/天直接費用優(yōu)化原理核心：力求以最小的費用去縮短工期，最后求出一個費用最低的最快進度。12345672-25-44-37-45-38-54-27-42-15-24-25-340010007008005001600100090010007001400ijKTN-TM例：任務(wù)如圖1234567243435241223第一步：按工作的最快時間求出最快進度。假定所有工作按最短時間完成。最快進度（直接費用最多）T=16天1234567254758472545第二步：令最快進度為指令工期D=16天。求出正常時間，計算工期T=23天。01234567254758472545第二步：令最快進度為指令工期D=16天。求出正常時間，計算工期T=23天。027111618231234567254758472545第二步：令最快進度為指令工期D=16天。求出正常時間，計算工期T=23天。0271116182316111140-5-712345672-75-74-77-75-78-44127225-2415-5第二步：求出總機動時間TF212345672-75-74-77-75-78-45-25-5第三步：把具有負機動時間子圖分離出來1234567205-14-17-35-28-35-35-2第四步：運用優(yōu)化原理進行優(yōu)化費用斜率正常時間可壓縮時間4008005001000700160014001234567205-14-17-35-28-35-35-2進度1：一條關(guān)鍵線路最小斜率（2，3）可壓縮1天，費用400元，T1=22天。費用斜率正常時間可壓縮時間400800500100070016001400123456720404-17-35-28-35-35-2進度1：一條關(guān)鍵線路最小斜率（2，3）可壓縮1天，費用400元，T1=22天。800500100070016001400123456720404-17-35-28-35-35-2進度2：關(guān)鍵線路沒變，最小斜率（6，7）可壓縮2天，費用700元，T2=20天。800500100070016001400123456720404-17-3308-35-35-2進度2：關(guān)鍵線路沒變，最小斜率（6，7）可壓縮2天，費用700元，T2=20天。800500100016001400123456720404-17-3308-35-35-2進度3：關(guān)鍵線路二條，最小斜率（3，4)可壓縮1天，費用800元，T3=19天。80050010001600140012345672040307-3308-35-35-2進度3：關(guān)鍵線路二條，最小斜率（3，4）可壓縮1天，費用800元，T3=19天。50010001600140012345672040305-1308-33-15-2進度4：關(guān)鍵線路二條，最小斜率截集（4，5）（4，6）可壓縮3天，但最優(yōu)壓縮時間只有2天，費用斜率1500元，T4=17天。50010001600140012345672040305-1308-33-15-2進度5：關(guān)鍵線路三條，最小斜率截集（4，5）（4，6）（3，6）可壓縮1天，費用3100元，T5=16天。5001000160014001234567204030403070205-2進度5：關(guān)鍵線路三條，最小斜率截集（4，5）（4，6）（3，6）可壓縮1天，費用3100元，T5=16天。123456724343725進度5：T5=16天，費用最省的最快進度，共增加400*1+700*2+800*1+1500*2+3100*1=8700元總費用最低的最優(yōu)工期

工期與直接費用成反比，與間接費用成正比，因而存在一個總費用最低的最優(yōu)工期。設(shè)工期每壓縮一天可節(jié)省間接費用1000元。

總費用最低的最優(yōu)工期為進度3，比正常進度節(jié)省4天，增加直接費用2600元，減少間接費用4000元，結(jié)果凈節(jié)省費用1400元。計劃評審技術(shù)

在一類如科研項目、大型的復(fù)雜工程項目、新產(chǎn)品的試制等任務(wù)中，工作的延續(xù)時間有很大的不確定性，屬于隨機變量，這就是非肯定型問題，工作的延續(xù)時間需給出一組時間估計值，通常有三個：最樂觀時間、最可能時間和最悲觀時間。計劃評審技術(shù)

這一類問題的提法：整個任務(wù)預(yù)期在什么時間完成？在指令工期內(nèi)完成整個任務(wù)的可能性（概率）多大？需要延長多少時間才有把握地完成整個任務(wù)？工作的期望時間和方差

最樂觀時間(a)是指在最順利的情況下，完成該工作可能的最短時間（通常情況下取1%概率的那個最短時間）；最可能時間(m)是指在正常的情況下，完成該工作最可能需要的時間；最悲觀時間(b)是指在最不順利的情況下，完成該工作可能的最長時間（通常情況下取1%概率的那個最長時間）。工作的期望時間和方差

工作的期望時間：te=工作的方差和均方差：，

任務(wù)的期望工期和方差

任務(wù)的期望工期（Te）等于網(wǎng)絡(luò)中關(guān)鍵線路上所有工作的期望時間之和：Te=∑te任務(wù)的期望工期方差等于網(wǎng)絡(luò)中關(guān)鍵線路上所有工作的方差之和：注：當(dāng)存在兩條以上關(guān)鍵線路時，任務(wù)的期望工期的方差應(yīng)等于這數(shù)條關(guān)鍵線路方差中的最大值。

，

⑤

①②④⑦⑧

③⑥工作ambte(1-2)8101510.51.4(1-3)4121711.54.7(2-4)6121511.52.3(2-5)47127.31.8(3-4)6101710.53.4(3-6)58168.83.4(4-5)48107.71(4-7)101622164(5-8)2453.80.25(6-8)41214112.8(7-8)81720164解:有二條關(guān)鍵線路:(1-2-4-7-8)（1-3-4-7-8）。對關(guān)鍵線路（1-2-4-7-8）：任務(wù)的期望工期（Te）：Te=10.5+11.5+16+16=54(天)；任務(wù)的期望工期的方差：=1.4+2.3+4+4=1