運籌學(xué)課件-7-網(wǎng)絡(luò)計劃技術(shù)

運籌學(xué)7講課教師：XXX運籌學(xué)7講課教師：XXX1第七章網(wǎng)絡(luò)計劃技術(shù)7.1PERT網(wǎng)絡(luò)圖7.2PERT網(wǎng)絡(luò)參數(shù)計算7.3PERT網(wǎng)絡(luò)優(yōu)化7.4

第七章網(wǎng)絡(luò)計劃技術(shù)7.1PERT網(wǎng)絡(luò)圖2

7.1PERT網(wǎng)絡(luò)圖

一、網(wǎng)絡(luò)計劃技術(shù)的基本概念工程計劃與甘特圖不易表現(xiàn)工程全貌不便于對各項工作的安排進(jìn)行籌劃和推敲不能識別影響進(jìn)度的關(guān)鍵工作不能反映一項工作不能按進(jìn)度完成時對工程進(jìn)度的影響計劃評審技術(shù)(PERT)與關(guān)鍵路線法(CPM)系統(tǒng)性和協(xié)調(diào)性動態(tài)性和可控性科學(xué)性

7.1PERT網(wǎng)絡(luò)圖

一、網(wǎng)絡(luò)計劃技術(shù)的基本概念工程3甘特圖甘特圖4上述甘特圖的網(wǎng)絡(luò)圖上述甘特圖的網(wǎng)絡(luò)圖5二、網(wǎng)絡(luò)圖的繪制1.網(wǎng)絡(luò)圖的構(gòu)成作業(yè)（工作、工序、活動），箭頭表示，箭頭之上表示工作名稱，之下表示工作時間。可有虛工作。事項，節(jié)點表示，表示某個工作的結(jié)束和另一工作的開始。二、網(wǎng)絡(luò)圖的繪制1.網(wǎng)絡(luò)圖的構(gòu)成6一個基建項目的網(wǎng)絡(luò)圖一個基建項目的網(wǎng)絡(luò)圖72.路線、關(guān)鍵路線、工程工期從開始節(jié)點到結(jié)束節(jié)點的一條路經(jīng)叫做路線一個網(wǎng)絡(luò)圖的有多條路線，每條路線有一個總時間總時間最長的路線叫做關(guān)鍵路線，關(guān)鍵路線的總時間叫做工期2.路線、關(guān)鍵路線、工程工期從開始節(jié)點到結(jié)束節(jié)點的一條路經(jīng)叫8網(wǎng)絡(luò)圖的路線網(wǎng)絡(luò)圖的路線9以上網(wǎng)絡(luò)圖共有8條路線可以計算出這8條路線的總時間，最長的是16天。關(guān)鍵路線是當(dāng)某些工作的時間調(diào)整后，可能引起關(guān)鍵路線的變化和工期的變化。例如將工作E的時間縮短為4天，則工期縮短為13天，關(guān)鍵路線將變?yōu)?346BEG5651356BFH553以上網(wǎng)絡(luò)圖共有8條路線1346BEG5651356BFH55103.網(wǎng)絡(luò)圖的畫法作業(yè)的串聯(lián)作業(yè)的并聯(lián)3.網(wǎng)絡(luò)圖的畫法作業(yè)的串聯(lián)11作業(yè)的交叉作業(yè)的交叉12作業(yè)的合并作業(yè)的合并134.繪制網(wǎng)絡(luò)圖的基本原則兩事項間只能有一項作業(yè)改為4.繪制網(wǎng)絡(luò)圖的基本原則兩事項間只能有一項作業(yè)改為14網(wǎng)絡(luò)圖應(yīng)從左向右延伸，編號應(yīng)從小到大，且不重復(fù)。箭頭事項編號大于箭尾事項編號網(wǎng)絡(luò)圖只能一個開始節(jié)點，一個終止節(jié)點不能出現(xiàn)循環(huán)路線盡量少交叉，采用暗橋；有層次性。網(wǎng)絡(luò)圖應(yīng)從左向右延伸，編號應(yīng)從小到大，且不重復(fù)。箭頭事項編號15運籌學(xué)課件——7-網(wǎng)絡(luò)計劃技術(shù)16使用暗橋使用暗橋175.網(wǎng)絡(luò)圖的繪制步驟確定目標(biāo)，做好準(zhǔn)備工作任務(wù)分解和分析繪制網(wǎng)絡(luò)圖5.網(wǎng)絡(luò)圖的繪制步驟確定目標(biāo)，做好準(zhǔn)備工作18表7-1調(diào)查項目的任務(wù)分解和分析表7-1調(diào)查項目的任務(wù)分解和分析19試探性繪制法：試探試探性繪制法：試探20試探性繪制法：修改試探性繪制法：修改217.2PERT網(wǎng)絡(luò)時間參數(shù)計算作業(yè)時間的確定事項時間參數(shù)的計算作業(yè)時間參數(shù)的計算關(guān)鍵路線的尋找方法按期完成計劃的概率7.2PERT網(wǎng)絡(luò)時間參數(shù)計算作業(yè)時間的確定22一、作業(yè)時間的確定對具有標(biāo)準(zhǔn)的作業(yè)，采用單一時間估計法對一般性作業(yè)，采用三點時間估計法最樂觀時間：a最可能時間：m最悲觀時間：b計算時間期望值和方差一、作業(yè)時間的確定對具有標(biāo)準(zhǔn)的作業(yè)，采用單一時間估計法23作業(yè)時間計算方法作業(yè)時間計算方法24二、事項參數(shù)的計算事項最早時間事項最遲時間ij二、事項參數(shù)的計算事項最早時間ij25圖上計算法圖上計算法26矩陣法計算事項時間表7-2矩陣法計算事項時間表7-227三、作業(yè)時間參數(shù)的計算作業(yè)最早開始時間作業(yè)最早結(jié)束時間作業(yè)最遲開始時間作業(yè)最遲結(jié)束時間作業(yè)總時差作業(yè)單時差三、作業(yè)時間參數(shù)的計算作業(yè)最早開始時間28作業(yè)最早開始和結(jié)束時間作業(yè)最遲開始和結(jié)束時間作業(yè)最早開始和結(jié)束時間作業(yè)最遲開始和結(jié)束時間29時差總時差單時差時差總時差單時差30時差之間的關(guān)系時差之間的關(guān)系31表7-3作業(yè)時間參數(shù)表上計算法表7-3作業(yè)時間參數(shù)表上計算法32四、關(guān)鍵路線的確定方法總時差為零的作業(yè)即是關(guān)鍵作業(yè)，全部關(guān)鍵作業(yè)構(gòu)成關(guān)鍵路線破圈法也可采用最長路線法。四、關(guān)鍵路線的確定方法總時差為零的作業(yè)即是關(guān)鍵作業(yè)，全部關(guān)鍵33五、按期完成計劃的概率每項作業(yè)的時間是一個隨機(jī)變量，近似服從分布，均質(zhì)和標(biāo)準(zhǔn)差為工程工期也是一個隨機(jī)變量，它的期望值為各關(guān)鍵作業(yè)時間期望之和。五、按期完成計劃的概率每項作業(yè)的時間是一個隨機(jī)變量，近似服從34按期完成計劃的概率當(dāng)作業(yè)數(shù)足夠多時，工期近似服從正態(tài)分布按期完成計劃的概率當(dāng)作業(yè)數(shù)足夠多時，工期近似服從正態(tài)分布35按期完成計劃的概率其中按期完成的概率按期完成計劃的概率其中36圖7-1工期概率分析的例子圖7-1工期概率分析的例子37計算按期完成概率工期的期望值和標(biāo)準(zhǔn)差是分別計算要求20天、21天和19天完成的概率計算按期完成概率工期的期望值和標(biāo)準(zhǔn)差是38計算概率下完工的工期由于所以可根據(jù)要求的概率，查表得到z，在用上式計算TD，例如，要求完工概率為0.9的工期：由得z=1.28，所以計算概率下完工的工期由于397.3網(wǎng)絡(luò)優(yōu)化工期限定，資源需要平衡資源有限，工期希望最短工期縮短，總費用最小7.3網(wǎng)絡(luò)優(yōu)化工期限定，資源需要平衡40一、工期限定，資源需要平衡工期不變，就是關(guān)鍵工作時間不能調(diào)整資源不平衡將導(dǎo)致資源不足利用時差，調(diào)整非關(guān)鍵路線上工作的開始時間，使資源實現(xiàn)平衡。一、工期限定，資源需要平衡工期不變，就是關(guān)鍵工作時間不能調(diào)整41例例42各工作都按最早開始時間開始各工作都按最早開始時間開始43調(diào)整非關(guān)鍵作業(yè)的開始時間調(diào)整非關(guān)鍵作業(yè)的開始時間44二、資源有限，要求工期最短下圖表示的項目只有10人工作二、資源有限，要求工期最短下圖表示的項目只有10人工作45第一次調(diào)整第一次調(diào)整46第二次調(diào)整第二次調(diào)整47三、工期縮短，總費用最少一般情況下，若采取措施縮短工期，則間接費用將減少，直接費用將增加，目標(biāo)是求總費用最低的工程工期。三、工期縮短，總費用最少一般情況下，若采取措施縮短工期，則間48直接成本的處理按線性處理，作業(yè)的費用率為直接成本的處理按線性處理，作業(yè)的費用率為49例圖4-2ij例圖4-2ij50解題思路以正常時間進(jìn)行網(wǎng)絡(luò)分析，求得關(guān)鍵路線在關(guān)鍵路線上，尋找最小費率的工作，縮短其時間，使工期最多到次長路線的長度。縮短工期必須對所有關(guān)鍵路線進(jìn)行，此時應(yīng)選擇費率總和最小的組合方案。解題思路以正常時間進(jìn)行網(wǎng)絡(luò)分析，求得關(guān)鍵路線51第一步求正常關(guān)鍵路線工期=11天第一步求正常關(guān)鍵路線工期=11天52第二步選擇(2,3)縮短工期工期=10天增加費用1第二步選擇(2,3)縮短工期工期=10天53第三步按第Ⅱ方案縮短工期工期=9天增加費用1+2=3第三步按第Ⅱ方案縮短工期工期=9天54第四步再按方案Ⅲ縮短工期工期=8天增加費用3+3=6第四步再按方案Ⅲ縮短工期工期=8天55第五步按第I、II方案共縮短4天工期=4天增加費用6+16=22第五步按第I、II方案共縮短4天工期=4天56第六步調(diào)整(1,2)與(2,3)，并縮短(3,4)工期=3天增加費用22+5=27第六步調(diào)整(1,2)與(2,3)，并縮短(3,4)工期=357第七步繪制直接費用變化圖第七步繪制直接費用變化圖58第八步確定總費用最小的優(yōu)化方案一般應(yīng)考慮間接費用，工期縮短，總的間接費用減少例如，上例中，間接費用率為：4.5/天，則因為最后一步直接費率5/天>4.5/天，因此最后一步的工期不能縮短，工期應(yīng)為4天，此時可節(jié)省費用7x4.5-22=9.5(萬元)。第八步確定總費用最小的優(yōu)化方案一般應(yīng)考慮間接費用，工59習(xí)題P152，7.2;7.3(圖7.13b)習(xí)題P152，7.2;7.3(圖7.13b)60運籌學(xué)7講課教師：XXX運籌學(xué)7講課教師：XXX61第七章網(wǎng)絡(luò)計劃技術(shù)7.1PERT網(wǎng)絡(luò)圖7.2PERT網(wǎng)絡(luò)參數(shù)計算7.3PERT網(wǎng)絡(luò)優(yōu)化7.4

第七章網(wǎng)絡(luò)計劃技術(shù)7.1PERT網(wǎng)絡(luò)圖62

7.1PERT網(wǎng)絡(luò)圖

一、網(wǎng)絡(luò)計劃技術(shù)的基本概念工程計劃與甘特圖不易表現(xiàn)工程全貌不便于對各項工作的安排進(jìn)行籌劃和推敲不能識別影響進(jìn)度的關(guān)鍵工作不能反映一項工作不能按進(jìn)度完成時對工程進(jìn)度的影響計劃評審技術(shù)(PERT)與關(guān)鍵路線法(CPM)系統(tǒng)性和協(xié)調(diào)性動態(tài)性和可控性科學(xué)性

7.1PERT網(wǎng)絡(luò)圖

一、網(wǎng)絡(luò)計劃技術(shù)的基本概念工程63甘特圖甘特圖64上述甘特圖的網(wǎng)絡(luò)圖上述甘特圖的網(wǎng)絡(luò)圖65二、網(wǎng)絡(luò)圖的繪制1.網(wǎng)絡(luò)圖的構(gòu)成作業(yè)（工作、工序、活動），箭頭表示，箭頭之上表示工作名稱，之下表示工作時間。可有虛工作。事項，節(jié)點表示，表示某個工作的結(jié)束和另一工作的開始。二、網(wǎng)絡(luò)圖的繪制1.網(wǎng)絡(luò)圖的構(gòu)成66一個基建項目的網(wǎng)絡(luò)圖一個基建項目的網(wǎng)絡(luò)圖672.路線、關(guān)鍵路線、工程工期從開始節(jié)點到結(jié)束節(jié)點的一條路經(jīng)叫做路線一個網(wǎng)絡(luò)圖的有多條路線，每條路線有一個總時間總時間最長的路線叫做關(guān)鍵路線，關(guān)鍵路線的總時間叫做工期2.路線、關(guān)鍵路線、工程工期從開始節(jié)點到結(jié)束節(jié)點的一條路經(jīng)叫68網(wǎng)絡(luò)圖的路線網(wǎng)絡(luò)圖的路線69以上網(wǎng)絡(luò)圖共有8條路線可以計算出這8條路線的總時間，最長的是16天。關(guān)鍵路線是當(dāng)某些工作的時間調(diào)整后，可能引起關(guān)鍵路線的變化和工期的變化。例如將工作E的時間縮短為4天，則工期縮短為13天，關(guān)鍵路線將變?yōu)?346BEG5651356BFH553以上網(wǎng)絡(luò)圖共有8條路線1346BEG5651356BFH55703.網(wǎng)絡(luò)圖的畫法作業(yè)的串聯(lián)作業(yè)的并聯(lián)3.網(wǎng)絡(luò)圖的畫法作業(yè)的串聯(lián)71作業(yè)的交叉作業(yè)的交叉72作業(yè)的合并作業(yè)的合并734.繪制網(wǎng)絡(luò)圖的基本原則兩事項間只能有一項作業(yè)改為4.繪制網(wǎng)絡(luò)圖的基本原則兩事項間只能有一項作業(yè)改為74網(wǎng)絡(luò)圖應(yīng)從左向右延伸，編號應(yīng)從小到大，且不重復(fù)。箭頭事項編號大于箭尾事項編號網(wǎng)絡(luò)圖只能一個開始節(jié)點，一個終止節(jié)點不能出現(xiàn)循環(huán)路線盡量少交叉，采用暗橋；有層次性。網(wǎng)絡(luò)圖應(yīng)從左向右延伸，編號應(yīng)從小到大，且不重復(fù)。箭頭事項編號75運籌學(xué)課件——7-網(wǎng)絡(luò)計劃技術(shù)76使用暗橋使用暗橋775.網(wǎng)絡(luò)圖的繪制步驟確定目標(biāo)，做好準(zhǔn)備工作任務(wù)分解和分析繪制網(wǎng)絡(luò)圖5.網(wǎng)絡(luò)圖的繪制步驟確定目標(biāo)，做好準(zhǔn)備工作78表7-1調(diào)查項目的任務(wù)分解和分析表7-1調(diào)查項目的任務(wù)分解和分析79試探性繪制法：試探試探性繪制法：試探80試探性繪制法：修改試探性繪制法：修改817.2PERT網(wǎng)絡(luò)時間參數(shù)計算作業(yè)時間的確定事項時間參數(shù)的計算作業(yè)時間參數(shù)的計算關(guān)鍵路線的尋找方法按期完成計劃的概率7.2PERT網(wǎng)絡(luò)時間參數(shù)計算作業(yè)時間的確定82一、作業(yè)時間的確定對具有標(biāo)準(zhǔn)的作業(yè)，采用單一時間估計法對一般性作業(yè)，采用三點時間估計法最樂觀時間：a最可能時間：m最悲觀時間：b計算時間期望值和方差一、作業(yè)時間的確定對具有標(biāo)準(zhǔn)的作業(yè)，采用單一時間估計法83作業(yè)時間計算方法作業(yè)時間計算方法84二、事項參數(shù)的計算事項最早時間事項最遲時間ij二、事項參數(shù)的計算事項最早時間ij85圖上計算法圖上計算法86矩陣法計算事項時間表7-2矩陣法計算事項時間表7-287三、作業(yè)時間參數(shù)的計算作業(yè)最早開始時間作業(yè)最早結(jié)束時間作業(yè)最遲開始時間作業(yè)最遲結(jié)束時間作業(yè)總時差作業(yè)單時差三、作業(yè)時間參數(shù)的計算作業(yè)最早開始時間88作業(yè)最早開始和結(jié)束時間作業(yè)最遲開始和結(jié)束時間作業(yè)最早開始和結(jié)束時間作業(yè)最遲開始和結(jié)束時間89時差總時差單時差時差總時差單時差90時差之間的關(guān)系時差之間的關(guān)系91表7-3作業(yè)時間參數(shù)表上計算法表7-3作業(yè)時間參數(shù)表上計算法92四、關(guān)鍵路線的確定方法總時差為零的作業(yè)即是關(guān)鍵作業(yè)，全部關(guān)鍵作業(yè)構(gòu)成關(guān)鍵路線破圈法也可采用最長路線法。四、關(guān)鍵路線的確定方法總時差為零的作業(yè)即是關(guān)鍵作業(yè)，全部關(guān)鍵93五、按期完成計劃的概率每項作業(yè)的時間是一個隨機(jī)變量，近似服從分布，均質(zhì)和標(biāo)準(zhǔn)差為工程工期也是一個隨機(jī)變量，它的期望值為各關(guān)鍵作業(yè)時間期望之和。五、按期完成計劃的概率每項作業(yè)的時間是一個隨機(jī)變量，近似服從94按期完成計劃的概率當(dāng)作業(yè)數(shù)足夠多時，工期近似服從正態(tài)分布按期完成計劃的概率當(dāng)作業(yè)數(shù)足夠多時，工期近似服從正態(tài)分布95按期完成計劃的概率其中按期完成的概率按期完成計劃的概率其中96圖7-1工期概率分析的例子圖7-1工期概率分析的例子97計算按期完成概率工期的期望值和標(biāo)準(zhǔn)差是分別計算要求20天、21天和19天完成的概率計算按期完成概率工期的期望值和標(biāo)準(zhǔn)差是98計算概率下完工的工期由于所以可根據(jù)要求的概率，查表得到z，在用上式計算TD，例如，要求完工概率為0.9的工期：由得z=1.28，所以計算概率下完工的工期由于997.3網(wǎng)絡(luò)優(yōu)化工期限定，資源需要平衡資源有限，工期希望最短工期縮短，總費用最小7.3網(wǎng)絡(luò)優(yōu)化工期限定，資源需要平衡100一、工期限定，資源需要平衡工期不變，就是關(guān)鍵工作時間不能調(diào)整資源不平衡將導(dǎo)致資源不足利用時差，調(diào)整非關(guān)鍵路線上工作的開始時間，使資源實現(xiàn)平衡。一、工期限定，資源需要平衡工期不變，就是關(guān)鍵工作時間不能調(diào)整101例例102各工作都按最早開始時間開始各工作都按最早開始時間開始103調(diào)整非關(guān)鍵作業(yè)的開始時間調(diào)整非關(guān)鍵作業(yè)的開始時間104二、資源有限，要求工期最短下圖表示的項目只有10人工作二、資源有限，要求工期最短下圖表示的項目只有10人工作105第一次調(diào)整第一次調(diào)整106第二次調(diào)整第二次調(diào)整107三、工期縮短，總費用最少一般情況下，若采取措施縮短工期，則間接費用將減少，直接費用將增加，目標(biāo)是求總費用最低的工程工期。三、工期縮短，總費用最少一般情況下，若采取措施縮短工期，則間108直接成本的處理按線性處理，作業(yè)的費用率為直接成本的處理按線性處理，作業(yè)的費用率為109例圖4-2ij例圖4-2ij110解題思路以正常時間進(jìn)行網(wǎng)絡(luò)分析，求得關(guān)鍵路線在關(guān)鍵路線上，尋找最小費率的工作，縮短其時間，使工期最多到次長路線的長度?？s短工期必須對所