《運籌學(xué)》8關(guān)鍵路線法解讀課件

第八章計劃評審方法和關(guān)鍵路線方法第八章1網(wǎng)絡(luò)計劃方法的產(chǎn)生起源：網(wǎng)絡(luò)計劃方法是項目計劃管理的重要方法。它起源于美國。當(dāng)時，有兩種網(wǎng)絡(luò)計劃方法：關(guān)鍵路線法和計劃評審技術(shù)。1957年，美國杜邦化學(xué)公司用關(guān)鍵路線法(CriticalPathMethod)。當(dāng)年就節(jié)約100萬美元，為該公司用于該項目研究費用的5倍以上。1958年，美國海軍當(dāng)局在研制北極星導(dǎo)彈潛艇時，第一次采用了BuzzAllen提出的計劃評審技術(shù)(ProgramEvaluationandReviewTechnique),主要承包商200多家，轉(zhuǎn)包商10000家。23個系統(tǒng)網(wǎng)絡(luò)，每兩周檢查一次，原定6年，提前兩年完成，節(jié)約經(jīng)費10—15％。60年代耗時11年阿波羅登月計劃3000億$,42萬人,2萬家公司,120所大學(xué),600臺計算機,700萬零件,終于在1969年7月，阿波羅11號船長阿姆斯特朗登上月球。網(wǎng)絡(luò)計劃方法的產(chǎn)生起源：網(wǎng)絡(luò)計劃方法是項目計劃管理的重要方法260-70年代我國開始應(yīng)用和推廣。錢學(xué)森、華羅庚等都曾為此做了大量工作。華羅庚的例子：有客來訪，要請他飲茶，于是要做幾件事：洗茶杯、洗杯蓋、燒開水、泡茶到端茶。60-70年代我國開始應(yīng)用和推廣。錢學(xué)森、華羅庚等都曾為此做3客來沏茶本問題的幾道“工序”有次序,洗杯蓋端茶燒水泡茶洗杯虛時間:251020.5客來沏茶本問題的幾道“工序”有次序,洗杯蓋4第一節(jié)PERT網(wǎng)絡(luò)圖第一節(jié)PERT網(wǎng)絡(luò)圖5網(wǎng)絡(luò)圖由三大要素構(gòu)成：節(jié)點(事件)、箭線（作業(yè)）和路線。132一、網(wǎng)絡(luò)圖構(gòu)成網(wǎng)絡(luò)圖由三大要素構(gòu)成：節(jié)點(事件)、箭線（作業(yè)）和路線。136箭線:

1、代表計劃中的一項作業(yè)或工序，包括人力、財力、物力的付出。2、作業(yè)的內(nèi)容可大可小，可多可少。3、箭尾表示作業(yè)開始，箭頭表示作業(yè)結(jié)束4、通常把作業(yè)的代號和作業(yè)所耗時間標(biāo)在箭線的上下。5、虛箭線：不占用時間和空間，不消耗任何資源。只是為了明確活動的相互之間的邏輯關(guān)系。

3445A

10AijA：作業(yè)活動代號3445AAijA：作業(yè)活動代號7結(jié)點（表示事件）：

網(wǎng)絡(luò)圖中兩條或兩條以上的箭線的交接點就是結(jié)點，結(jié)點代表的作業(yè)開始和結(jié)束。用圓圈加上數(shù)字表示。

路線：從網(wǎng)絡(luò)圖的始點事件開始到終點事件為止，由一系列首尾相連的箭線和結(jié)點所代表的作業(yè)和事件所組成的通道。網(wǎng)絡(luò)圖一般有多條路線。其中最長的我們稱之為關(guān)鍵路線，關(guān)鍵路線上的工序為關(guān)鍵工序。結(jié)點（表示事件）：8（錯誤）135624正確135624PERT圖的開始節(jié)點與結(jié)束節(jié)點均應(yīng)是唯一的。二、繪制PERT圖的原則如果在實際工作中發(fā)生不吻合時，應(yīng)將沒有緊前作業(yè)的結(jié)點用虛箭頭線同網(wǎng)絡(luò)始點事項連接起來，將沒有后續(xù)事項的結(jié)點用虛箭頭同終點事項邊接起來。（錯誤）135624正確135624PERT圖的開始節(jié)點與結(jié)9錯誤正確在相鄰的兩個節(jié)點之間，最多只能有一條箭線相連。進(jìn)入某一個結(jié)點的箭線可以有多條，但其它任何結(jié)點直接連接該結(jié)點的箭線只能有一條。兩個相鄰結(jié)點間只允許有一條箭線直接相連。若有平行活動，可引入虛線以保證這一規(guī)則不被破壞。錯誤正確在相鄰的兩個節(jié)點之間，最多只能有一條箭線相連。進(jìn)入某10錯誤網(wǎng)絡(luò)圖中不能出現(xiàn)循環(huán)回路錯誤網(wǎng)絡(luò)圖中不能出現(xiàn)循環(huán)回路11

節(jié)點編號時，按照矢線箭頭的指向，升序排號，保證節(jié)點序號先后關(guān)系保持一致。應(yīng)將各作業(yè)的工時數(shù)據(jù)標(biāo)注在表示該作業(yè)的矢線的下面。

正確使用虛工序（不消耗資源，一般表示平行工作關(guān)系）節(jié)點編號時，按照矢線箭頭的指向，升序排號，保證節(jié)點序號先后12三、PERT圖的繪制步驟先畫草圖，再修改后變成規(guī)范圖，步驟如下：@根據(jù)活動清單中規(guī)定的關(guān)系，將活動代號欄所有的活動逐次地畫在網(wǎng)絡(luò)圖上，從左到右@理順活動的緊前、緊后關(guān)系，沒有緊后活動的活動所對應(yīng)的箭線匯集在終止結(jié)點上@草圖繪制完成后，將序號標(biāo)在結(jié)點上，將活動代號和時間標(biāo)在箭線上@檢查無誤后，將草圖繪制成規(guī)范圖

三、PERT圖的繪制步驟先畫草圖，再修改后變成規(guī)范圖，步驟如13作業(yè)名稱ABCDEFGHI緊前作業(yè)AAB，CBDDE，GF，H作業(yè)時間D15151410661308例：某項工程任務(wù)經(jīng)分解后，確定由9項作業(yè)構(gòu)成，各項作業(yè)的代號、緊前作業(yè)及作業(yè)時間如表所示，畫出網(wǎng)絡(luò)圖作業(yè)名稱ABCDEFGHI緊前作業(yè)AAB，CBDDE，GF，141412346578A15B15CE6D10G1H30F6I81412346578A15B15CE6D10G1H30F6I15序號施工項目所需時間（月）工序代號緊前項目12345678清理地面打地基砌墻安裝電線粉刷畫圖案室內(nèi)工程上屋頂14434645ABCDEF

G

HA

BDD，HCEC例：建筑一幢房屋，施工順序如上表所示，要求計算工程周期及關(guān)鍵路線序號施工項目所需時間（月）工序代號緊前項目1清理地面1A例：16E51 2346785ABCDG144H344E51 2346785ABCDG144H3417活動代號活動描述緊后活動活動時間（周）ABCDEFGHIJKL系統(tǒng)分析和總體設(shè)計輸入和輸出設(shè)計模塊1詳細(xì)設(shè)計輸入和輸出程序設(shè)計模塊1程序設(shè)計模塊2詳細(xì)設(shè)計輸入和輸出及模塊1測試模塊2程序設(shè)計模塊1測試系統(tǒng)總調(diào)試穩(wěn)當(dāng)編寫系統(tǒng)測試B,CDE,FG,IG,IHJI,KJL無無346885363583某機械廠管理信息系統(tǒng)開發(fā)活動清單例活動代號活動描述緊后活動活動時間（周）A系統(tǒng)分析和總體設(shè)計B1812346109857A3B4

C6D8E8F5H6G3J5L3K8I312346109857AB4CDEFHGJLKI319四、PERT圖的分類（1）按工時估計的性質(zhì)：A：確定型網(wǎng)絡(luò)，每個工作的預(yù)計工時只估一個值，即，這些工作的實際完成情況一般地可按預(yù)計工時達(dá)到，也即實現(xiàn)的概率等于或近似等于1。B：概率型網(wǎng)絡(luò)，每個工作按三種情況下給定工時，最快可能完成工時，最可能完成工時，最慢可能完成工時。四、PERT圖的分類（1）按工時估計的性質(zhì)：20五、PERT圖的計算1.工作時間tij的確定:確定型:利用已知的工時定額資料給出。概率型：對于開發(fā)性任務(wù)，或?qū)ぷ魉璧墓r難以準(zhǔn)確估計時，可采用三點時間法來確定工作的工時。

五、PERT圖的計算1.工作時間tij的確定:21則實際計算中，完成一項作業(yè)的期望工時t(i,j)按如下公式計算：設(shè)：a是最樂觀的時間估計值，m是最可能的估計值，b是最悲觀的時間估計值方差為：則實際計算中，完成一項作業(yè)的期望工時t(i,j)按如下公式計222.結(jié)點（事項）的時間參數(shù)確定：（1）節(jié)點的最早時間：它表明以它為始點的各工作最早可能開始的時間，也表明以它為終點的各工作的最早可能完成時間。等于從始點結(jié)點到該結(jié)點的最長路線上所有工作的工時總和。遞推公式：：整個工程的總最早完工期2.結(jié)點（事項）的時間參數(shù)確定：（1）節(jié)點的最早時間：它表23（2）節(jié)點的最遲時間：它表明在不影響任務(wù)總工期的條件下，以它為始點的各工作最遲必須開始的時間，也表明以它為終點的各工作的最遲必須完成時間。由于，一般都把任務(wù)的最早完工時間作為任務(wù)的總工期，所以結(jié)點的最遲時間遞推公式為：（2）節(jié)點的最遲時間：它表明在不影響任務(wù)總工期的條件下，以它243.工作的時間參數(shù)確定：1。作業(yè)的最早可能開始時間（ES）是指作業(yè)最早可能開始的時間，是它的各項緊前作業(yè)最早結(jié)束的時間中最大的一個。2。作業(yè)的最早可能結(jié)束時間（EF）

是指作業(yè)按最早開工時間開始所能達(dá)到的完工時間。3.工作的時間參數(shù)確定：1。作業(yè)的最早可能開始時間（ES）253.作業(yè)的最遲必須開工時間（LS）是指作業(yè)（i,j）在不影響整個任務(wù)如期完工的前提下，必須開始的最晚時間。

4.作業(yè)的最遲必須結(jié)束時間（LF）

是指作業(yè)（i,j）按最遲時間開工，所能達(dá)到的完工時間。3.作業(yè)的最遲必須開工時間（LS）264.時差：按性質(zhì)可以分為作業(yè)的總時差R（i,j）和作業(yè)的自由時差F（i,j）?？倳r差：在不影響任務(wù)總工期的條件下，某工作（i,j）可以延遲其開工時間的最大幅度。這是網(wǎng)絡(luò)上多于一項作業(yè)共同擁有的機動時間，并非為某項作業(yè)單獨擁有。工作（i,j）的總時差等于它的最遲完工時間與最早完工時間的差，也等于它的最遲開工時間與最早開工時間的差。4.時差：總時差：在不影響任務(wù)總工期的條件下，某工作（i,27自由時差：不影響它的各項緊后作業(yè)最早開工時間條件下，該項作業(yè)可以推遲的開工時間的最大限度，它是一項作業(yè)獨自擁有的機動時間。即自由時差等于其緊后作業(yè)的最早開工時間與本工作的最早完工時間的差。自由時差：不影響它的各項緊后作業(yè)最早開工時間條件下，該項作業(yè)28下圖是一個工程施工圖，請依次求出各時間參數(shù)。

時間參數(shù)計算舉例下圖是一個工程施工圖，請依次求出各時間參數(shù)。291。結(jié)點時間參數(shù)：方括號－最早時間，三角－最晚時間1。結(jié)點時間參數(shù)：方括號－最早時間，三角－最晚時間302。作業(yè)時間參數(shù)：方括號－最早開工時間，三角－最晚開工時間02。作業(yè)時間參數(shù)：方括號－最早開工時間，三角－最313。總時差，自由時差：中括號－總時差，園括號－自由時差3?？倳r差，自由時差：中括號－總時差，園括號－自由時差32說明：1，由關(guān)鍵路線的意義知，這條線在時間上沒有回旋余地，即每個關(guān)鍵工作應(yīng)滿足“最早開工時間＝最遲必須開工時間”，而非關(guān)鍵路線則有富裕時間。所以，總時差為0的工作鏈就是關(guān)鍵路線。此處為2，比較總時差和自由時差的關(guān)系：工作（1，7）有自由時差13，若把它拖至13周開工，對它后面的工作的最早開工時間及時差等都沒有影響，對整個工期也沒有影響。而只有總時差沒有自由時差的工作則不然，若工作（7，8），總時差為1，自由時差為0，如果讓它推遲1周開工，雖然總工期不受影響，但其后面的工作最早時間及時差都要受影響。所以使用時差來調(diào)整工作時，應(yīng)盡量先用自由時差。說明：1，由關(guān)鍵路線的意義知，這條線在時間上沒有回旋余地，即33第二節(jié)關(guān)鍵路線與網(wǎng)絡(luò)計劃的優(yōu)化路線時間最長的網(wǎng)絡(luò)路線為關(guān)鍵路線關(guān)鍵路線上的工序稱為關(guān)鍵工序不在關(guān)鍵路線上的工序為非關(guān)鍵工序第二節(jié)關(guān)鍵路線與網(wǎng)絡(luò)計劃的優(yōu)化路線時間最長的網(wǎng)絡(luò)路線為關(guān)34網(wǎng)絡(luò)圖的優(yōu)化與調(diào)整

通過繪制網(wǎng)絡(luò)圖、計算時間參數(shù)、確定關(guān)鍵路線，得到的僅是一個初步計劃方案．為了得到從各方面都較好的方案，一般一項工程或任務(wù)的網(wǎng)絡(luò)計劃，往往要根據(jù)項目的要求綜合考慮時間、資源和費用等目標(biāo)，對初始方案進(jìn)一步改善和調(diào)整，進(jìn)行網(wǎng)絡(luò)優(yōu)化，確定最優(yōu)的方案,求得最佳效果。但目前還沒有一個能全面反映這些指標(biāo)的模型，所以，一般只是按照某一個或兩個指標(biāo)來衡量計劃的優(yōu)劣。如：網(wǎng)絡(luò)圖的優(yōu)化與調(diào)整通過繪制網(wǎng)絡(luò)圖、計算時間參數(shù)、確定354.工期不變的條件下，如何使所用資源最少（資源優(yōu)化）。1.縮短網(wǎng)絡(luò)計劃工期(時間優(yōu)化)；2.降低人力使用高峰，使其符合人力供應(yīng)能力，并使各工種人員中的使用連續(xù)均衡，且工期最短（時間—資源優(yōu)化）；3.縮短工期并使費用增加最少（時間費用優(yōu)化）

；4.工期不變的條件下，如何使所用資源最少1.縮短網(wǎng)絡(luò)計劃36

在網(wǎng)絡(luò)系統(tǒng)中，關(guān)鍵線路決定總工期。當(dāng)規(guī)定的工期大于關(guān)鍵線路上工序時間總和時，關(guān)鍵線路上各工序的總時差就會出現(xiàn)正值，說明完成該項任務(wù)的時間較寬余，必要時可適當(dāng)延長某些工序的時間，以便減少資源或節(jié)省費用。反之，任務(wù)比較急時，規(guī)定的工期會小于總工期，則需對網(wǎng)絡(luò)進(jìn)行調(diào)整。對超過規(guī)定工期的各條線路上的某些工序，通常在組織上和技術(shù)上可采用的方法有如下幾種：1.時間優(yōu)化--縮短網(wǎng)絡(luò)計劃工期在網(wǎng)絡(luò)系統(tǒng)中，關(guān)鍵線路決定總工期。當(dāng)規(guī)定的工期大37(a)

在關(guān)鍵線路上尋找最有利的工序來縮短其作業(yè)時間。(b)

可能條件下采取平行交叉工序縮短工期。(c)

搞技術(shù)改造，或增加人力、物質(zhì)設(shè)備等多種措施，縮短某些工序的延續(xù)時間。(d)

利用時差，從非關(guān)鍵線路上抽調(diào)適當(dāng)?shù)娜肆?、物力集中于關(guān)鍵路線，以縮短關(guān)鍵路線的持續(xù)時間。

以上幾種縮短工期方法在使用過程中，會隨時引起網(wǎng)絡(luò)計劃的改變，每次改變后都要重新計算網(wǎng)絡(luò)時間和確定關(guān)鍵路線，直到求得最短周期為止。(a)

在關(guān)鍵線路上尋找最有利的工序來縮短其作業(yè)時間。38

例圖1是某工程的網(wǎng)絡(luò)圖，初始方案計劃時間為19周完成，現(xiàn)因特殊情況，上級要求提前3周完工，即總工期壓縮為16周，試對網(wǎng)絡(luò)進(jìn)行調(diào)整。

例圖1是某工程的網(wǎng)絡(luò)圖，初始方案計劃時間為1939解

（1）計算工序的時間參數(shù)，找出關(guān)鍵線路。如圖1，雙箭線的工序組成的線路為關(guān)鍵線路：①→②→③→⑤→⑨→⑩注：方括號內(nèi)：作業(yè)最早開始時間；三角內(nèi)：最遲開始時間解（1）計算工序的時間參數(shù)，找出關(guān)鍵線路。40

（2）縮短工期的計算：首先將終點事項⑩的最遲結(jié)束時間定為16周，從右向左逐個求出各工序的最遲開始時間tLS，標(biāo)在圖2相應(yīng)箭線下方的“△”內(nèi)，同時求出各工序總時差，用[]括起來放于相應(yīng)工序下方。（2）縮短工期的計算：首先將終點事項⑩的最遲結(jié)束時間定為141《運籌學(xué)》8關(guān)鍵路線法解讀課件42

圖中方括號內(nèi)的數(shù)字為總工期16周時，各工序的總時差，從計劃的結(jié)果可看出，在原先的關(guān)鍵路線上各工序的總時差為（-3），這意味著原來的關(guān)鍵路線上應(yīng)縮短3周。而其他非關(guān)鍵線路上也出現(xiàn)負(fù)時差，即在這些線路上也要進(jìn)行日期的縮短。圖中方括號內(nèi)的數(shù)字為總工期16周時，各工序的總時差，43需要縮短日期的線路和工序有：線路

時差

（1）①→②→③→⑤→⑨→⑩-3（2）②→④→⑦→⑧→⑨-2（3）⑦→⑨ -1需要縮短日期的線路和工序有：線路44

首先考慮關(guān)鍵線路即線路①→②→③→⑤→⑨→⑩上縮短3周，不妨在②→③?③→⑤?⑨→⑩上各縮1周，縮短后，通過網(wǎng)絡(luò)時間參數(shù)的計算，其結(jié)果如圖所示。

53壓縮為26壓縮為53壓縮為2首先考慮關(guān)鍵線路即線路①→②→③→⑤→⑨→⑩上縮短45由上圖可知：絕對值最大的負(fù)時差線路為：①→②→④→⑦→⑧→⑨→⑩，現(xiàn)在其中任一工序上壓縮1周，比如⑧→⑨改為5周。由上圖可知：絕對值最大的負(fù)時差線路為：①→②→④→⑦→⑧→⑨46

再計算時間參數(shù)，可知負(fù)時差已全部消滅，如圖所示6壓縮為5這時總時差為0的線路有三條：①→②→③→⑤→⑨→⑩?①→②→④→⑦→⑨→⑩和①→②→④→⑦→⑧→⑨→⑩。它們均是關(guān)鍵線路，總工期為16周，符合規(guī)定的要求。再計算時間參數(shù)，可知負(fù)時差已全部消滅，如圖所示6壓縮為47網(wǎng)絡(luò)計劃的時間—資源優(yōu)化，是指對時間和其他資源進(jìn)行統(tǒng)籌安排，達(dá)到特定的工程要求．往往要求在有限的資源條件下合理分配資源，既滿足各項活動對計劃的需求，又確保整個工程項目在盡可能短的時間內(nèi)完成．包括以下幾個方面：2.時間—資源優(yōu)化（主要優(yōu)化資源）1．先安排關(guān)鍵工程所需資源；2．錯開非關(guān)鍵工序的開始時間，使工程各時段對資源的需求趨于平衡；3．為達(dá)到總體效益最佳，必要時可適當(dāng)延長總工期．網(wǎng)絡(luò)計劃的時間—資源優(yōu)化，是指對時間和其他資48

例

某市防疫站從下屬單位抽調(diào)部分人員，進(jìn)行一項疫情調(diào)查，整個工作可分許多階段(工序)，各階段所需的時間和人員數(shù)量不等，具體見表1，問各階段工作應(yīng)如何合理安排，才可以使人力的使用最合理?例某市防疫站從下屬單位抽調(diào)部分人員，進(jìn)行一項49表1各工序所需的時間和人員數(shù)量工序工期需人員數(shù)緊前工序a①→②27—b①→③24—c①→④25—d①→⑥410—e②→③28af③→⑤33b,eg④→⑤39ch⑤→⑥42f，gi⑥→⑦312d，h表1各工序所需的時間和人員數(shù)量工序工期需人員數(shù)緊前工序a①501764325abcdefghi442222333此時，關(guān)鍵路線為：aefhi,時間為14天。如果不做任何調(diào)整，按照正常的時間安排工作，則1－2天做a,b,c,d，需要26人；3－4天做d,e,g，需要27人；第5天做f,g，需要12人；6－7天做f，需要3人；8－11天做h，需要2人；12－14天做i需要12人，結(jié)果見下圖1764325abcdefghi442222333此時，關(guān)鍵511764325abcdefghi442222333人數(shù)74510839212abcdefghi1764325abcdefghi442222333人數(shù)74552考慮時差，可調(diào)整d的工作，讓它延遲到第8天開工，人數(shù)安排變?yōu)椋嚎紤]時差，可調(diào)整d的工作，讓它延遲到第8天開工，人數(shù)安排變?yōu)?3繼續(xù)調(diào)整g的工作，讓它延遲到第5天開工，人數(shù)安排變?yōu)椋豪^續(xù)調(diào)整g的工作，讓它延遲到第5天開工，人數(shù)安排變?yōu)椋?4繼續(xù)調(diào)整b的工作，讓它延遲到第3天開工，人數(shù)安排變?yōu)椋航Y(jié)論：最少安排12人。繼續(xù)調(diào)整b的工作，讓它延遲到第3天開工，人數(shù)安排變?yōu)椋航Y(jié)論：55工程所需時間與工程所需費用是一對矛盾．一般情況下，縮短一道工序時間，就要采取一些措施，如加班，增加設(shè)備等，需要增加一定費用，同時也會得到一些收益，如節(jié)約了管理費用等．要想縮短整個工程的工期，必須從兩方面考慮：（1）要分析縮短工期所需代價；（2）要分析縮短工期帶來得收益．在一定條件下，滿足工程時間要求以期達(dá)到工程費用的最低的網(wǎng)絡(luò)計劃安排稱為最低成本日程

3.時間—費用優(yōu)化（主要是費用優(yōu)化）工程所需時間與工程所需費用是一對矛盾．56(1)費用與時間的關(guān)系工程所需費用，基本上分為兩大部分：

直接費用——完成工序直接有關(guān)的費用，如人力、機械、原材料等費用．工序直接費用和所需工時常假定為直線關(guān)系。

間接費用——管理費、設(shè)備租金等，是根據(jù)各道工序時間按比例分?jǐn)偟模ば驎r間越少，間接費用就越少；反之，工序時間越多，間接費用就越多．

工程總費用W就是直接費用U與間接費用V的總和，即：W＝U＋V(1)費用與時間的關(guān)系工程總費用W就是直接費用U57工程費用與完工期之間的關(guān)系可用下圖表示．總費用直接費用正常時間間接費用完工時間最優(yōu)時間最短時間費用從圖中可看出，在正常工期和最短工期(縮短工期的最低限度，也簡稱趕工時間)之間，存在著一個最優(yōu)工期，此時總費用最少．這個時間稱為最低成本日程．從關(guān)鍵路線入手，找出最少工程費日程的方法，就是關(guān)鍵路線法(CPM)．工程費用與完工期之間的關(guān)系可用下圖表示．總費用直接費用正常時58假設(shè)工序的直接費用與工序時間是線性關(guān)系，設(shè)工序k每趕一天進(jìn)度所需要增加的費用為q（k），則式中q（k）為費用斜率,c為趕工所需費用,n為正常完工所需費用,nt為正常完工所需時間,ct為趕工時間．(2)時間—費用優(yōu)化的計算顯然，費用斜率越大的工序，每縮短一天，花的費用就越多．在考慮縮短工程工期時，當(dāng)然是要縮短各關(guān)鍵工序中的某一道或某幾道工序的工期，而選擇縮短哪道工序要以總費用最省為根據(jù)．假設(shè)工序的直接費用與工序時間是線性關(guān)系，設(shè)工序k每趕一天59時間—費用優(yōu)化的計算

首先應(yīng)確定工期與直接費用的關(guān)系。即先對全部工序按正常時間計算參數(shù)，求出網(wǎng)絡(luò)圖的關(guān)鍵路線、工程周期和相應(yīng)的直接費用。工程項目的總費用=正常完工的直接費用+趕工增加的費用+間接費用其次逐次壓縮費用增長率q最小的關(guān)鍵工序延續(xù)時間，使直接費用的增加最小。壓縮網(wǎng)絡(luò)時，按下面原則進(jìn)行：時間—費用優(yōu)化的計算首先應(yīng)確定工期與直接費用的關(guān)系。60(a)

壓縮關(guān)鍵線路上費用增長率最小的工序時間，以增加最少的費用來縮短工期。(b)

在選擇壓縮某項工序的延續(xù)時間時，既要滿足工序費用一時間變化關(guān)系的限制，又要考慮網(wǎng)絡(luò)中和該作業(yè)并列的各工序時差數(shù)的限制，應(yīng)取這兩個限制的最小值。(c)

當(dāng)網(wǎng)絡(luò)圖不斷壓縮出現(xiàn)數(shù)條關(guān)鍵路線時，繼續(xù)壓縮工期，需要同時縮短這數(shù)條路線，僅縮短一條線路不會達(dá)到縮短工期的目的。(a)

壓縮關(guān)鍵線路上費用增長率最小的工序時間，61

下面以例子說明通過縮短關(guān)鍵路線上工序時間來尋求最少工程費日程的方法.

例某項工程根據(jù)有關(guān)資料，計算出了費用斜率如表2，試制定該工程的最少工程費計劃方案．下面以例子說明通過縮短關(guān)鍵路線上工序時間來尋求最62表2工程的有關(guān)資料及費用斜率

工序緊前工序正常完工時間（天）正常完工直接費用（百元）趕工時間（天）費用斜率（百元）a/103074b/51042cb31522da,c42033ea,c52533fd63235ge5821hf,g5944合計

149

間接費用5（百元/天）表2工程的有關(guān)資料及費用斜率工序緊前正常完工正常完工直63圖1（a）

解根據(jù)表2，可繪出統(tǒng)籌圖1（a）:按正常時間完工需25天，所需總費用為:Ｗ＝14900+500×25＝27400元圖1（a）解根據(jù)表2，可繪出統(tǒng)籌圖1（a）:按正常時64圖1（b）

若使工程工期最短，即將所有工序時間都壓縮到其可能的最短時間，看其費用情況如何．這時，統(tǒng)籌圖如圖1（b）所示．

工程完工期為17天，其趕工增加費用(c－n)為:3×400＋1×200＋1×200＋1×300＋2×300＋3×500＋3×100+1×400＝4700元.總費用Ｗ＝14900+4700+500×17＝28100元.顯然費用太大，不是最優(yōu)．

圖1（b）若使工程工期最短，即將所有工序時間都壓縮到其可能65分析按正常時間完工的計劃方案，找出最少工程費方案．由圖2（a）可以看出，在按正常時間完工的統(tǒng)籌圖中，有兩條關(guān)鍵路線：①→③→④→⑥→⑦，①→③→⑤→⑥→⑦。

圖2（a）

分析按正常時間完工的計劃方案，找出最少工程費方案．由圖66要縮短工期，就要縮短關(guān)鍵工序的時間.

首先考慮壓縮關(guān)鍵線路上費用增長率最小的工序時間，以增加最少的費用來縮短工期。在上述兩條關(guān)鍵路線的情況下，縮短哪道關(guān)鍵工序，分析如下：圖1（a）

要縮短工期，就要縮短關(guān)鍵工序的時間.

首先考慮壓縮關(guān)67兩條關(guān)鍵路線在結(jié)點3和結(jié)點6之間有并聯(lián)部分，關(guān)鍵工序為a、d、e、f、g和h，其中工序a、h為兩條關(guān)鍵路線所共有．要縮短工期，在費用最小的情況下，首先考慮縮短共有的關(guān)鍵工序．其次考慮結(jié)點3和結(jié)點6之間的各關(guān)鍵工序d、e、f和g，因為它們之間是并聯(lián)的，所以要想縮短工程的工期，必須在d、f中和e、g中，各壓縮一道工序的時間．這樣，它們就有4種可能的組合。綜合以上組合及費用情況可通過下表考慮選擇：兩條關(guān)鍵路線在結(jié)點3和結(jié)點6之間有并聯(lián)部分，關(guān)鍵工序68從上表比較可知，費用增長率最小的工序或工序組合為a、h、d和g，這三者中首先考慮縮短兩條關(guān)鍵路線所共有的關(guān)鍵工序a、h．不妨先縮短關(guān)鍵工序h，每縮短1天，需增加費用400元，但節(jié)省間接費500元，凈省費用100元．因此，把工序h壓縮到最低限度4天．同時，總費用減為27300元．

表3幾種可能縮短的工序或工序組合工序趕工一天增加的費用趕工一天間接費用減少總費用凈變化a45-1h45-1d和e3+3=65+1d和g3+1=45-1f和e5+3=85+3f和g5+1=65+1從上表比較可知，費用增長率最小的工序或工序組合為a、h69然后再考慮壓縮工序a，與壓縮工序h一樣，每壓縮1天，總費用凈省100元．但此處需注意，工序a不能壓縮到其最低時間限度7天，因為當(dāng)工序壓縮2天時，工序時間為8天，這時工序b和工序c就都變成了關(guān)鍵工序．這樣，在結(jié)點1和結(jié)點3之間，也出現(xiàn)了并聯(lián)的關(guān)鍵路線部分．繼續(xù)單獨壓縮工序a，已不能縮短整個工程的工期．因此，只能把工序a壓縮為8天．總費用減為27100元．

最后，將工序d和工序g各壓縮1天，總費用減為27000元.由于工序d的限制，不能進(jìn)一步壓縮了．

然后再考慮壓縮工序a，與壓縮工序h一樣，每壓縮1天，70綜合起來，最少工程費計劃方案，按下列要求去做：將工序a壓縮為8天，將工序d壓縮為3天，將工序g壓縮為4天，將工序h壓縮為4天，其它工序b、c、e和f仍按正常時間進(jìn)行，這樣得到的最少工程費日程為21天，總費用為27000元，其統(tǒng)籌圖如圖1（c）所示．

圖1（c）

#綜合起來，最少工程費計劃方案，按下列要求去做：將工71第三節(jié)概率型網(wǎng)絡(luò)、完成作業(yè)的期望時間、在規(guī)定時間內(nèi)實現(xiàn)事件的概率第三節(jié)概率型網(wǎng)絡(luò)、完成作業(yè)的期望時間、在規(guī)定時間內(nèi)實72對于概率型網(wǎng)絡(luò)，在實際計算中，完成一項作業(yè)的期望時間Et(i,j)按如下公式計算：其中：a是最樂觀的時間估計值，m是最可能的估計值，b是最悲觀的時間估計值對于概率型網(wǎng)絡(luò)，在實際計算中，完成一項作業(yè)的期望時間Et(i73我們知道，當(dāng)上述的時間參數(shù)求出后，概率型網(wǎng)絡(luò)就可用同確定型網(wǎng)絡(luò)一樣的方法可計算出其它相應(yīng)的所有參數(shù)。但由于他們的工作工時本身包含隨機因素，所以，整個任務(wù)的總完工期也是個期望工期。它是關(guān)鍵路線上各道工作的平均工時之和，所以總完工工期的方差就是關(guān)鍵路線上所有工序的方差之和。若工作足夠多，每一件工作的工時對整個任務(wù)的完成工時影響不是很明顯的話，由中心極限定理，總完工期服從上述均值和方差為參數(shù)的正態(tài)分布。我們知道，當(dāng)上述的時間參數(shù)求出后，概率型網(wǎng)絡(luò)就可用同確定型網(wǎng)74為達(dá)到嚴(yán)格控制工期，確保任務(wù)在計劃期內(nèi)完成的目的，我們可以計算在給定的工期前完工的概率。實際問題中，可以通過計算多個不同的完工期內(nèi)能完成的概率，最終找到一個符合概率要求的完工期，將它作為項目總工期。為達(dá)到嚴(yán)格控制工期，確保任務(wù)在計劃期內(nèi)完成的目的，我們可以計75例：一項工程項目由9個作業(yè)組成，各作業(yè)間的邏輯關(guān)系以及工期信息見表。 (1)繪制相應(yīng)的網(wǎng)絡(luò)。 (2)用表格計算法找出關(guān)鍵線路，并預(yù)測該項目的總工期。

例：一項工程項目由9個作業(yè)組成，各作業(yè)間的邏輯關(guān)系以及工期信76《運籌學(xué)》8關(guān)鍵路線法解讀課件77解：（1）繪制相應(yīng)的網(wǎng)絡(luò)圖見圖1234567A4B6C3D5H6E6F2G6I5(4+5*4+6)/6(2+4*4+6)/6(5+6*4+7)/6(4+6*4+8)/6計算出工期的均值，如下表中的工期ET解：（1）繪制相應(yīng)的網(wǎng)絡(luò)圖見圖1234567AB6C78作業(yè)名稱ABCDEFGHI樂觀工期252341354最可能工期463562665悲觀工期674783976工期ET463562665工期方差0.440.110.110.440.440.110.250.110.11關(guān)鍵作業(yè)

作業(yè)ABCDEFGHI樂觀252341354最可463562791234567A4B6C3D5H6E6F2G6I50471312241907418241913計算時間，得下圖。找出關(guān)鍵線路，預(yù)測該項目的總工期為24周。也可以用后面的表表示。1234567AB6C3DHEFGI5047180作業(yè)名稱ABCDEFGHI樂觀工期252341354最可能工期463562665悲觀工期674783976工期ET463562665工期方差0.440.110.110.440.440.110.250.110.11關(guān)鍵作業(yè)#

#

#

#

#作業(yè)ABCDEFGHI樂觀252341354最可46356281如果該項目的計劃工期為26周，則按期完工的可能性有多大？如果該項目的計劃工期為26周，則按期完工82為計算方便，我們假定每個事件的最早實現(xiàn)時間服從正態(tài)分布（此假定對最終事件的完成時間是基本正確的），即事件3的正態(tài)分布的中心為方差為計算方便，我們假定每個事件的最早實現(xiàn)時間服從正態(tài)分布（此假83假定事件k的最早實現(xiàn)時間的期望和方差已知，則事件k的實現(xiàn)時間Tk小于規(guī)定期限Tdk的概率為假定事件k的最早實現(xiàn)時間的期望和方差已知，則事件k的實現(xiàn)時間84《運籌學(xué)》8關(guān)鍵路線法解讀課件85

第八章計劃評審方法和關(guān)鍵路線方法第八章86網(wǎng)絡(luò)計劃方法的產(chǎn)生起源：網(wǎng)絡(luò)計劃方法是項目計劃管理的重要方法。它起源于美國。當(dāng)時，有兩種網(wǎng)絡(luò)計劃方法：關(guān)鍵路線法和計劃評審技術(shù)。1957年，美國杜邦化學(xué)公司用關(guān)鍵路線法(CriticalPathMethod)。當(dāng)年就節(jié)約100萬美元，為該公司用于該項目研究費用的5倍以上。1958年，美國海軍當(dāng)局在研制北極星導(dǎo)彈潛艇時，第一次采用了BuzzAllen提出的計劃評審技術(shù)(ProgramEvaluationandReviewTechnique),主要承包商200多家，轉(zhuǎn)包商10000家。23個系統(tǒng)網(wǎng)絡(luò)，每兩周檢查一次，原定6年，提前兩年完成，節(jié)約經(jīng)費10—15％。60年代耗時11年阿波羅登月計劃3000億$,42萬人,2萬家公司,120所大學(xué),600臺計算機,700萬零件,終于在1969年7月，阿波羅11號船長阿姆斯特朗登上月球。網(wǎng)絡(luò)計劃方法的產(chǎn)生起源：網(wǎng)絡(luò)計劃方法是項目計劃管理的重要方法8760-70年代我國開始應(yīng)用和推廣。錢學(xué)森、華羅庚等都曾為此做了大量工作。華羅庚的例子：有客來訪，要請他飲茶，于是要做幾件事：洗茶杯、洗杯蓋、燒開水、泡茶到端茶。60-70年代我國開始應(yīng)用和推廣。錢學(xué)森、華羅庚等都曾為此做88客來沏茶本問題的幾道“工序”有次序,洗杯蓋端茶燒水泡茶洗杯虛時間:251020.5客來沏茶本問題的幾道“工序”有次序,洗杯蓋89第一節(jié)PERT網(wǎng)絡(luò)圖第一節(jié)PERT網(wǎng)絡(luò)圖90網(wǎng)絡(luò)圖由三大要素構(gòu)成：節(jié)點(事件)、箭線（作業(yè)）和路線。132一、網(wǎng)絡(luò)圖構(gòu)成網(wǎng)絡(luò)圖由三大要素構(gòu)成：節(jié)點(事件)、箭線（作業(yè)）和路線。1391箭線:

1、代表計劃中的一項作業(yè)或工序，包括人力、財力、物力的付出。2、作業(yè)的內(nèi)容可大可小，可多可少。3、箭尾表示作業(yè)開始，箭頭表示作業(yè)結(jié)束4、通常把作業(yè)的代號和作業(yè)所耗時間標(biāo)在箭線的上下。5、虛箭線：不占用時間和空間，不消耗任何資源。只是為了明確活動的相互之間的邏輯關(guān)系。

3445A

10AijA：作業(yè)活動代號3445AAijA：作業(yè)活動代號92結(jié)點（表示事件）：

網(wǎng)絡(luò)圖中兩條或兩條以上的箭線的交接點就是結(jié)點，結(jié)點代表的作業(yè)開始和結(jié)束。用圓圈加上數(shù)字表示。

路線：從網(wǎng)絡(luò)圖的始點事件開始到終點事件為止，由一系列首尾相連的箭線和結(jié)點所代表的作業(yè)和事件所組成的通道。網(wǎng)絡(luò)圖一般有多條路線。其中最長的我們稱之為關(guān)鍵路線，關(guān)鍵路線上的工序為關(guān)鍵工序。結(jié)點（表示事件）：93（錯誤）135624正確135624PERT圖的開始節(jié)點與結(jié)束節(jié)點均應(yīng)是唯一的。二、繪制PERT圖的原則如果在實際工作中發(fā)生不吻合時，應(yīng)將沒有緊前作業(yè)的結(jié)點用虛箭頭線同網(wǎng)絡(luò)始點事項連接起來，將沒有后續(xù)事項的結(jié)點用虛箭頭同終點事項邊接起來。（錯誤）135624正確135624PERT圖的開始節(jié)點與結(jié)94錯誤正確在相鄰的兩個節(jié)點之間，最多只能有一條箭線相連。進(jìn)入某一個結(jié)點的箭線可以有多條，但其它任何結(jié)點直接連接該結(jié)點的箭線只能有一條。兩個相鄰結(jié)點間只允許有一條箭線直接相連。若有平行活動，可引入虛線以保證這一規(guī)則不被破壞。錯誤正確在相鄰的兩個節(jié)點之間，最多只能有一條箭線相連。進(jìn)入某95錯誤網(wǎng)絡(luò)圖中不能出現(xiàn)循環(huán)回路錯誤網(wǎng)絡(luò)圖中不能出現(xiàn)循環(huán)回路96

節(jié)點編號時，按照矢線箭頭的指向，升序排號，保證節(jié)點序號先后關(guān)系保持一致。應(yīng)將各作業(yè)的工時數(shù)據(jù)標(biāo)注在表示該作業(yè)的矢線的下面。

正確使用虛工序（不消耗資源，一般表示平行工作關(guān)系）節(jié)點編號時，按照矢線箭頭的指向，升序排號，保證節(jié)點序號先后97三、PERT圖的繪制步驟先畫草圖，再修改后變成規(guī)范圖，步驟如下：@根據(jù)活動清單中規(guī)定的關(guān)系，將活動代號欄所有的活動逐次地畫在網(wǎng)絡(luò)圖上，從左到右@理順活動的緊前、緊后關(guān)系，沒有緊后活動的活動所對應(yīng)的箭線匯集在終止結(jié)點上@草圖繪制完成后，將序號標(biāo)在結(jié)點上，將活動代號和時間標(biāo)在箭線上@檢查無誤后，將草圖繪制成規(guī)范圖

三、PERT圖的繪制步驟先畫草圖，再修改后變成規(guī)范圖，步驟如98作業(yè)名稱ABCDEFGHI緊前作業(yè)AAB，CBDDE，GF，H作業(yè)時間D15151410661308例：某項工程任務(wù)經(jīng)分解后，確定由9項作業(yè)構(gòu)成，各項作業(yè)的代號、緊前作業(yè)及作業(yè)時間如表所示，畫出網(wǎng)絡(luò)圖作業(yè)名稱ABCDEFGHI緊前作業(yè)AAB，CBDDE，GF，991412346578A15B15CE6D10G1H30F6I81412346578A15B15CE6D10G1H30F6I100序號施工項目所需時間（月）工序代號緊前項目12345678清理地面打地基砌墻安裝電線粉刷畫圖案室內(nèi)工程上屋頂14434645ABCDEF

G

HA

BDD，HCEC例：建筑一幢房屋，施工順序如上表所示，要求計算工程周期及關(guān)鍵路線序號施工項目所需時間（月）工序代號緊前項目1清理地面1A例：101E51 2346785ABCDG144H344E51 2346785ABCDG144H34102活動代號活動描述緊后活動活動時間（周）ABCDEFGHIJKL系統(tǒng)分析和總體設(shè)計輸入和輸出設(shè)計模塊1詳細(xì)設(shè)計輸入和輸出程序設(shè)計模塊1程序設(shè)計模塊2詳細(xì)設(shè)計輸入和輸出及模塊1測試模塊2程序設(shè)計模塊1測試系統(tǒng)總調(diào)試穩(wěn)當(dāng)編寫系統(tǒng)測試B,CDE,FG,IG,IHJI,KJL無無346885363583某機械廠管理信息系統(tǒng)開發(fā)活動清單例活動代號活動描述緊后活動活動時間（周）A系統(tǒng)分析和總體設(shè)計B10312346109857A3B4

C6D8E8F5H6G3J5L3K8I312346109857AB4CDEFHGJLKI3104四、PERT圖的分類（1）按工時估計的性質(zhì)：A：確定型網(wǎng)絡(luò)，每個工作的預(yù)計工時只估一個值，即，這些工作的實際完成情況一般地可按預(yù)計工時達(dá)到，也即實現(xiàn)的概率等于或近似等于1。B：概率型網(wǎng)絡(luò)，每個工作按三種情況下給定工時，最快可能完成工時，最可能完成工時，最慢可能完成工時。四、PERT圖的分類（1）按工時估計的性質(zhì)：105五、PERT圖的計算1.工作時間tij的確定:確定型:利用已知的工時定額資料給出。概率型：對于開發(fā)性任務(wù)，或?qū)ぷ魉璧墓r難以準(zhǔn)確估計時，可采用三點時間法來確定工作的工時。

五、PERT圖的計算1.工作時間tij的確定:106則實際計算中，完成一項作業(yè)的期望工時t(i,j)按如下公式計算：設(shè)：a是最樂觀的時間估計值，m是最可能的估計值，b是最悲觀的時間估計值方差為：則實際計算中，完成一項作業(yè)的期望工時t(i,j)按如下公式計1072.結(jié)點（事項）的時間參數(shù)確定：（1）節(jié)點的最早時間：它表明以它為始點的各工作最早可能開始的時間，也表明以它為終點的各工作的最早可能完成時間。等于從始點結(jié)點到該結(jié)點的最長路線上所有工作的工時總和。遞推公式：：整個工程的總最早完工期2.結(jié)點（事項）的時間參數(shù)確定：（1）節(jié)點的最早時間：它表108（2）節(jié)點的最遲時間：它表明在不影響任務(wù)總工期的條件下，以它為始點的各工作最遲必須開始的時間，也表明以它為終點的各工作的最遲必須完成時間。由于，一般都把任務(wù)的最早完工時間作為任務(wù)的總工期，所以結(jié)點的最遲時間遞推公式為：（2）節(jié)點的最遲時間：它表明在不影響任務(wù)總工期的條件下，以它1093.工作的時間參數(shù)確定：1。作業(yè)的最早可能開始時間（ES）是指作業(yè)最早可能開始的時間，是它的各項緊前作業(yè)最早結(jié)束的時間中最大的一個。2。作業(yè)的最早可能結(jié)束時間（EF）

是指作業(yè)按最早開工時間開始所能達(dá)到的完工時間。3.工作的時間參數(shù)確定：1。作業(yè)的最早可能開始時間（ES）1103.作業(yè)的最遲必須開工時間（LS）是指作業(yè)（i,j）在不影響整個任務(wù)如期完工的前提下，必須開始的最晚時間。

4.作業(yè)的最遲必須結(jié)束時間（LF）

是指作業(yè)（i,j）按最遲時間開工，所能達(dá)到的完工時間。3.作業(yè)的最遲必須開工時間（LS）1114.時差：按性質(zhì)可以分為作業(yè)的總時差R（i,j）和作業(yè)的自由時差F（i,j）?？倳r差：在不影響任務(wù)總工期的條件下，某工作（i,j）可以延遲其開工時間的最大幅度。這是網(wǎng)絡(luò)上多于一項作業(yè)共同擁有的機動時間，并非為某項作業(yè)單獨擁有。工作（i,j）的總時差等于它的最遲完工時間與最早完工時間的差，也等于它的最遲開工時間與最早開工時間的差。4.時差：總時差：在不影響任務(wù)總工期的條件下，某工作（i,112自由時差：不影響它的各項緊后作業(yè)最早開工時間條件下，該項作業(yè)可以推遲的開工時間的最大限度，它是一項作業(yè)獨自擁有的機動時間。即自由時差等于其緊后作業(yè)的最早開工時間與本工作的最早完工時間的差。自由時差：不影響它的各項緊后作業(yè)最早開工時間條件下，該項作業(yè)113下圖是一個工程施工圖，請依次求出各時間參數(shù)。

時間參數(shù)計算舉例下圖是一個工程施工圖，請依次求出各時間參數(shù)。1141。結(jié)點時間參數(shù)：方括號－最早時間，三角－最晚時間1。結(jié)點時間參數(shù)：方括號－最早時間，三角－最晚時間1152。作業(yè)時間參數(shù)：方括號－最早開工時間，三角－最晚開工時間02。作業(yè)時間參數(shù)：方括號－最早開工時間，三角－最1163?？倳r差，自由時差：中括號－總時差，園括號－自由時差3。總時差，自由時差：中括號－總時差，園括號－自由時差117說明：1，由關(guān)鍵路線的意義知，這條線在時間上沒有回旋余地，即每個關(guān)鍵工作應(yīng)滿足“最早開工時間＝最遲必須開工時間”，而非關(guān)鍵路線則有富裕時間。所以，總時差為0的工作鏈就是關(guān)鍵路線。此處為2，比較總時差和自由時差的關(guān)系：工作（1，7）有自由時差13，若把它拖至13周開工，對它后面的工作的最早開工時間及時差等都沒有影響，對整個工期也沒有影響。而只有總時差沒有自由時差的工作則不然，若工作（7，8），總時差為1，自由時差為0，如果讓它推遲1周開工，雖然總工期不受影響，但其后面的工作最早時間及時差都要受影響。所以使用時差來調(diào)整工作時，應(yīng)盡量先用自由時差。說明：1，由關(guān)鍵路線的意義知，這條線在時間上沒有回旋余地，即118第二節(jié)關(guān)鍵路線與網(wǎng)絡(luò)計劃的優(yōu)化路線時間最長的網(wǎng)絡(luò)路線為關(guān)鍵路線關(guān)鍵路線上的工序稱為關(guān)鍵工序不在關(guān)鍵路線上的工序為非關(guān)鍵工序第二節(jié)關(guān)鍵路線與網(wǎng)絡(luò)計劃的優(yōu)化路線時間最長的網(wǎng)絡(luò)路線為關(guān)119網(wǎng)絡(luò)圖的優(yōu)化與調(diào)整

通過繪制網(wǎng)絡(luò)圖、計算時間參數(shù)、確定關(guān)鍵路線，得到的僅是一個初步計劃方案．為了得到從各方面都較好的方案，一般一項工程或任務(wù)的網(wǎng)絡(luò)計劃，往往要根據(jù)項目的要求綜合考慮時間、資源和費用等目標(biāo)，對初始方案進(jìn)一步改善和調(diào)整，進(jìn)行網(wǎng)絡(luò)優(yōu)化，確定最優(yōu)的方案,求得最佳效果。但目前還沒有一個能全面反映這些指標(biāo)的模型，所以，一般只是按照某一個或兩個指標(biāo)來衡量計劃的優(yōu)劣。如：網(wǎng)絡(luò)圖的優(yōu)化與調(diào)整通過繪制網(wǎng)絡(luò)圖、計算時間參數(shù)、確定1204.工期不變的條件下，如何使所用資源最少（資源優(yōu)化）。1.縮短網(wǎng)絡(luò)計劃工期(時間優(yōu)化)；2.降低人力使用高峰，使其符合人力供應(yīng)能力，并使各工種人員中的使用連續(xù)均衡，且工期最短（時間—資源優(yōu)化）；3.縮短工期并使費用增加最少（時間費用優(yōu)化）

；4.工期不變的條件下，如何使所用資源最少1.縮短網(wǎng)絡(luò)計劃121

在網(wǎng)絡(luò)系統(tǒng)中，關(guān)鍵線路決定總工期。當(dāng)規(guī)定的工期大于關(guān)鍵線路上工序時間總和時，關(guān)鍵線路上各工序的總時差就會出現(xiàn)正值，說明完成該項任務(wù)的時間較寬余，必要時可適當(dāng)延長某些工序的時間，以便減少資源或節(jié)省費用。反之，任務(wù)比較急時，規(guī)定的工期會小于總工期，則需對網(wǎng)絡(luò)進(jìn)行調(diào)整。對超過規(guī)定工期的各條線路上的某些工序，通常在組織上和技術(shù)上可采用的方法有如下幾種：1.時間優(yōu)化--縮短網(wǎng)絡(luò)計劃工期在網(wǎng)絡(luò)系統(tǒng)中，關(guān)鍵線路決定總工期。當(dāng)規(guī)定的工期大122(a)

在關(guān)鍵線路上尋找最有利的工序來縮短其作業(yè)時間。(b)

可能條件下采取平行交叉工序縮短工期。(c)

搞技術(shù)改造，或增加人力、物質(zhì)設(shè)備等多種措施，縮短某些工序的延續(xù)時間。(d)

利用時差，從非關(guān)鍵線路上抽調(diào)適當(dāng)?shù)娜肆Α⑽锪杏陉P(guān)鍵路線，以縮短關(guān)鍵路線的持續(xù)時間。

以上幾種縮短工期方法在使用過程中，會隨時引起網(wǎng)絡(luò)計劃的改變，每次改變后都要重新計算網(wǎng)絡(luò)時間和確定關(guān)鍵路線，直到求得最短周期為止。(a)

在關(guān)鍵線路上尋找最有利的工序來縮短其作業(yè)時間。123

例圖1是某工程的網(wǎng)絡(luò)圖，初始方案計劃時間為19周完成，現(xiàn)因特殊情況，上級要求提前3周完工，即總工期壓縮為16周，試對網(wǎng)絡(luò)進(jìn)行調(diào)整。

例圖1是某工程的網(wǎng)絡(luò)圖，初始方案計劃時間為19124解

（1）計算工序的時間參數(shù)，找出關(guān)鍵線路。如圖1，雙箭線的工序組成的線路為關(guān)鍵線路：①→②→③→⑤→⑨→⑩注：方括號內(nèi)：作業(yè)最早開始時間；三角內(nèi)：最遲開始時間解（1）計算工序的時間參數(shù)，找出關(guān)鍵線路。125

（2）縮短工期的計算：首先將終點事項⑩的最遲結(jié)束時間定為16周，從右向左逐個求出各工序的最遲開始時間tLS，標(biāo)在圖2相應(yīng)箭線下方的“△”內(nèi)，同時求出各工序總時差，用[]括起來放于相應(yīng)工序下方。（2）縮短工期的計算：首先將終點事項⑩的最遲結(jié)束時間定為1126《運籌學(xué)》8關(guān)鍵路線法解讀課件127

圖中方括號內(nèi)的數(shù)字為總工期16周時，各工序的總時差，從計劃的結(jié)果可看出，在原先的關(guān)鍵路線上各工序的總時差為（-3），這意味著原來的關(guān)鍵路線上應(yīng)縮短3周。而其他非關(guān)鍵線路上也出現(xiàn)負(fù)時差，即在這些線路上也要進(jìn)行日期的縮短。圖中方括號內(nèi)的數(shù)字為總工期16周時，各工序的總時差，128需要縮短日期的線路和工序有：線路

時差

（1）①→②→③→⑤→⑨→⑩-3（2）②→④→⑦→⑧→⑨-2（3）⑦→⑨ -1需要縮短日期的線路和工序有：線路129

首先考慮關(guān)鍵線路即線路①→②→③→⑤→⑨→⑩上縮短3周，不妨在②→③?③→⑤?⑨→⑩上各縮1周，縮短后，通過網(wǎng)絡(luò)時間參數(shù)的計算，其結(jié)果如圖所示。

53壓縮為26壓縮為53壓縮為2首先考慮關(guān)鍵線路即線路①→②→③→⑤→⑨→⑩上縮短130由上圖可知：絕對值最大的負(fù)時差線路為：①→②→④→⑦→⑧→⑨→⑩，現(xiàn)在其中任一工序上壓縮1周，比如⑧→⑨改為5周。由上圖可知：絕對值最大的負(fù)時差線路為：①→②→④→⑦→⑧→⑨131

再計算時間參數(shù)，可知負(fù)時差已全部消滅，如圖所示6壓縮為5這時總時差為0的線路有三條：①→②→③→⑤→⑨→⑩?①→②→④→⑦→⑨→⑩和①→②→④→⑦→⑧→⑨→⑩。它們均是關(guān)鍵線路，總工期為16周，符合規(guī)定的要求。再計算時間參數(shù)，可知負(fù)時差已全部消滅，如圖所示6壓縮為132網(wǎng)絡(luò)計劃的時間—資源優(yōu)化，是指對時間和其他資源進(jìn)行統(tǒng)籌安排，達(dá)到特定的工程要求．往往要求在有限的資源條件下合理分配資源，既滿足各項活動對計劃的需求，又確保整個工程項目在盡可能短的時間內(nèi)完成．包括以下幾個方面：2.時間—資源優(yōu)化（主要優(yōu)化資源）1．先安排關(guān)鍵工程所需資源；2．錯開非關(guān)鍵工序的開始時間，使工程各時段對資源的需求趨于平衡；3．為達(dá)到總體效益最佳，必要時可適當(dāng)延長總工期．網(wǎng)絡(luò)計劃的時間—資源優(yōu)化，是指對時間和其他資133

例

某市防疫站從下屬單位抽調(diào)部分人員，進(jìn)行一項疫情調(diào)查，整個工作可分許多階段(工序)，各階段所需的時間和人員數(shù)量不等，具體見表1，問各階段工作應(yīng)如何合理安排，才可以使人力的使用最合理?例某市防疫站從下屬單位抽調(diào)部分人員，進(jìn)行一項134表1各工序所需的時間和人員數(shù)量工序工期需人員數(shù)緊前工序a①→②27—b①→③24—c①→④25—d①→⑥410—e②→③28af③→⑤33b,eg④→⑤39ch⑤→⑥42f，gi⑥→⑦312d，h表1各工序所需的時間和人員數(shù)量工序工期需人員數(shù)緊前工序a①1351764325abcdefghi442222333此時，關(guān)鍵路線為：aefhi,時間為14天。如果不做任何調(diào)整，按照正常的時間安排工作，則1－2天做a,b,c,d，需要26人；3－4天做d,e,g，需要27人；第5天做f,g，需要12人；6－7天做f，需要3人；8－11天做h，需要2人；12－14天做i需要12人，結(jié)果見下圖1764325abcdefghi442222333此時，關(guān)鍵1361764325abcdefghi442222333人數(shù)74510839212abcdefghi1764325abcdefghi442222333人數(shù)745137考慮時差，可調(diào)整d的工作，讓它延遲到第8天開工，人數(shù)安排變?yōu)椋嚎紤]時差，可調(diào)整d的工作，讓它延遲到第8天開工，人數(shù)安排變?yōu)?38繼續(xù)調(diào)整g的工作，讓它延遲到第5天開工，人數(shù)安排變?yōu)椋豪^續(xù)調(diào)整g的工作，讓它延遲到第5天開工，人數(shù)安排變?yōu)椋?39繼續(xù)調(diào)整b的工作，讓它延遲到第3天開工，人數(shù)安排變?yōu)椋航Y(jié)論：最少安排12人。繼續(xù)調(diào)整b的工作，讓它延遲到第3天開工，人數(shù)安排變?yōu)椋航Y(jié)論：140工程所需時間與工程所需費用是一對矛盾．一般情況下，縮短一道工序時間，就要采取一些措施，如加班，增加設(shè)備等，需要增加一定費用，同時也會得到一些收益，如節(jié)約了管理費用等．要想縮短整個工程的工期，必須從兩方面考慮：（1）要分析縮短工期所需代價；（2）要分析縮短工期帶來得收益．在一定條件下，滿足工程時間要求以期達(dá)到工程費用的最低的網(wǎng)絡(luò)計劃安排稱為最低成本日程

3.時間—費用優(yōu)化（主要是費用優(yōu)化）工程所需時間與工程所需費用是一對矛盾．141(1)費用與時間的關(guān)系工程所需費用，基本上分為兩大部分：

直接費用——完成工序直接有關(guān)的費用，如人力、機械、原材料等費用．工序直接費用和所需工時常假定為直線關(guān)系。

間接費用——管理費、設(shè)備租金等，是根據(jù)各道工序時間按比例分?jǐn)偟模ば驎r間越少，間接費用就越少；反之，工序時間越多，間接費用就越多．

工程總費用W就是直接費用U與間接費用V的總和，即：W＝U＋V(1)費用與時間的關(guān)系工程總費用W就是直接費用U142工程費用與完工期之間的關(guān)系可用下圖表示．總費用直接費用正常時間間接費用完工時間最優(yōu)時間最短時間費用從圖中可看出，在正常工期和最短工期(縮短工期的最低限度，也簡稱趕工時間)之間，存在著一個最優(yōu)工期，此時總費用最少．這個時間稱為最低成本日程．從關(guān)鍵路線入手，找出最少工程費日程的方法，就是關(guān)鍵路線法(CPM)．工程費用與完工期之間的關(guān)系可用下圖表示．總費用直接費用正常時143假設(shè)工序的直接費用與工序時間是線性關(guān)系，設(shè)工序k每趕一天進(jìn)度所需要增加的費用為q（k），則式中q（k）為費用斜率,c為趕工所需費用,n為正常完工所需費用,nt為正常完工所需時間,ct為趕工時間．(2)時間—費用優(yōu)化的計算顯然，費用斜率越大的工序，每縮短一天，花的費用就越多．在考慮縮短工程工期時，當(dāng)然是要縮短各關(guān)鍵工序中的某一道或某幾道工序的工期，而選擇縮短哪道工序要以總費用最省為根據(jù)．假設(shè)工序的直接費用與工序時間是線性關(guān)系，設(shè)工序k每趕一天144時間—費用優(yōu)化的計算

首先應(yīng)確定工期與直接費用的關(guān)系。即先對全部工序按正常時間計算參數(shù)，求出網(wǎng)絡(luò)圖的關(guān)鍵路線、工程周期和相應(yīng)的直接費用。工程項目的總費用=正常完工的直接費用+趕工增加的費用+間接費用其次逐次壓縮費用增長率q最小的關(guān)鍵工序延續(xù)時間，使直接費用的增加最小。壓縮網(wǎng)絡(luò)時，按下面原則進(jìn)行：時間—費用優(yōu)化的計算首先應(yīng)確定工期與直接費用的關(guān)系。145(a)

壓縮關(guān)鍵線路上費用增長率最小的工序時間，以增加最少的費用來縮短工期。(b)

在選擇壓縮某項工序的延續(xù)時間時，既要滿足工序費用一時間變化關(guān)系的限制，又要考慮網(wǎng)絡(luò)中和該作業(yè)并列的各工序時差數(shù)的限制，應(yīng)取這兩個限制的最小值。(c)

當(dāng)網(wǎng)絡(luò)圖不斷壓縮出現(xiàn)數(shù)條關(guān)鍵路線時，繼續(xù)壓縮工期，需要同時縮短這數(shù)條路線，僅縮短一條線路不會達(dá)到縮短工期的目的。(a)

壓縮關(guān)鍵線路上費用增長率最小的工序時間，146

下面以例子說明通過縮短關(guān)鍵路線上工序時間來尋求最少工程費日程的方法.

例某項工程根據(jù)有關(guān)資料，計算出了費用斜率如表2，試制定該工程的最少工程費計劃方案．下面以例子說明通過縮短關(guān)鍵路線上工序時間來尋求最147表2工程的有關(guān)資料及費用斜率

工序緊前工序正常完工時間（天）正常完工直接費用（百元）趕工時間（天）費用斜率（百元）a/103074b/51042cb31522da,c42033ea,c52533fd63235ge5821hf,g5944合計

149

間接費用5（百元/天）表2工程的有關(guān)資料及費用斜率工序緊前正常完工正常完工直148圖1（a）

解根據(jù)表2，可繪出統(tǒng)籌圖1（a）:按正常時間完工需25天，所需總費用為:Ｗ＝14900+500×25＝27400元圖1（a）解根據(jù)表2，可繪出統(tǒng)籌圖1（a）:按正常時149圖1（b）

若使工程工期最短，即將所有工序時間都壓縮到其可能的最短時間，看其費用情況如何．這時，統(tǒng)籌圖如圖1（b）所示．

工程完工期為17天，其趕工增加費用(c－n)為:3×400＋1×200＋1×200＋1×300＋2×300＋3×500＋3×100+1×400＝4700元.總費用Ｗ＝14900+4700+500×17＝28100元.顯然費用太大，不是最優(yōu)．

圖1（b）若使工程工期最短，即將所有工序時間都壓縮到其可能150分析按正常時間完工的計劃方案，找出最少工程費方案．由圖2（a）可以看出，在按正常時間完工的統(tǒng)籌圖中，有兩條關(guān)鍵路線：①→③→④→⑥→⑦，①→③→⑤→⑥→⑦。

圖2（a）

分析按正常時間完工的計劃方案，找出最少工程費方案．由圖151要縮短工期，就要縮短關(guān)鍵工序的時間.

首先考慮壓縮關(guān)鍵線路上費用增長率最小的工序時間，以增加最少的費用來縮短工期。在上述兩條關(guān)鍵路線的情況下，縮短哪道關(guān)鍵工序，分析如下：圖1（a）

要縮短工期，就要縮短關(guān)鍵工序的時間.

首先考慮壓縮關(guān)152兩條關(guān)鍵路線在結(jié)點3和結(jié)點6之間有并聯(lián)部分，關(guān)鍵工序為a、d、e、f、g和h，其中工序a、h為兩條關(guān)鍵路線所共有．要縮短工期，在費用最小的情況下，首先考慮縮短共有的關(guān)鍵工序．其次考慮結(jié)點3和結(jié)點6之間的各關(guān)鍵工序d、e、f和g，因為它們之間是并聯(lián)的，所以要想縮短工程的