運(yùn)籌學(xué)第7章計(jì)劃評(píng)審方法和關(guān)鍵路線法課件

1、第七章計(jì)劃評(píng)審方法和關(guān)鍵路徑法PERT:Program evaluation and review techniqueCPM:Critical path method第七章計(jì)劃評(píng)審方法和關(guān)鍵路徑法PERT:工程計(jì)劃的網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖的時(shí)間參數(shù)網(wǎng)絡(luò)圖的分析工序與事項(xiàng)網(wǎng)絡(luò)圖事項(xiàng)的參數(shù)工序的參數(shù)參數(shù)計(jì)算一覽網(wǎng)絡(luò)計(jì)劃的參數(shù)匯總表關(guān)鍵工序與關(guān)鍵路線網(wǎng)絡(luò)分析1 PERT網(wǎng)絡(luò)圖工程計(jì)劃的網(wǎng)絡(luò)圖工序與事項(xiàng)事項(xiàng)的參數(shù)網(wǎng)絡(luò)計(jì)劃的參數(shù)匯總表1 建造一座汽車庫及引道的工程項(xiàng)目，從施工開始到全部結(jié)束需要多少時(shí)間？把整個(gè)工程分解成若干個(gè)環(huán)節(jié)-工序；估算出每個(gè)環(huán)節(jié)所需要的時(shí)間-工時(shí)；確定各個(gè)環(huán)節(jié)之間的相互聯(lián)系，先做什么，后做什

2、么，哪些可以同時(shí)施工-緊前、緊后、平行關(guān)系；匯總上述各點(diǎn)予以具體分析，計(jì)算，得總工期。 將工序及所需要時(shí)間、各工序之間的關(guān)系整理成表-工序清單。這是應(yīng)用網(wǎng)絡(luò)技術(shù)的第一步。引例 建造一座汽車庫及引道的工程項(xiàng)目，從施工開始到代號(hào)工序名稱工時(shí)（天）緊前工序a清理現(xiàn)場(chǎng)8-b備料10-c車庫地面施工6a , bd預(yù)制墻及房頂?shù)蔫旒?6be車庫混凝土地面保養(yǎng)24cf立墻架4d , eg立房頂桁架4fh裝窗及邊墻10fi裝門4fj裝天花板12gk油漆16h , i , jl引道混凝土施工8cm引道混凝土保養(yǎng)24ln清理現(xiàn)場(chǎng)，交工驗(yàn)收4k ,m代號(hào)工序名稱工時(shí)（天）緊前工序a清理現(xiàn)場(chǎng)8-b備料10-總工期多少

3、天？必須在75天內(nèi)完成，要不要采取措施？應(yīng)從哪些方面采取措施？施工過程中，工序 c 拖后5天完成，工程會(huì)拖期？施工過程中，工序 d 提早2天完成，工程會(huì)提早？整個(gè)施工過程中，為確保工程如期完成，應(yīng)把關(guān)注的重心放在那幾道工序上？具體問題：引例總工期多少天？具體問題：引例網(wǎng)絡(luò)計(jì)劃例1 建立網(wǎng)絡(luò)圖工序工序代號(hào)所需時(shí)間緊后工序產(chǎn)品設(shè)計(jì)與工藝設(shè)計(jì)a60b,c,d,e外購配套件b45l下料、鍛件c10f工裝制造1d20g,h木模、鑄件e40h機(jī)械加工1f18l工裝制造2g30k機(jī)械加工2h15l機(jī)械加工3k25l裝配調(diào)試l35-網(wǎng)絡(luò)計(jì)劃例1 建立網(wǎng)絡(luò)圖工序工序代號(hào)所需時(shí)間緊后工序產(chǎn)品設(shè)17654328a設(shè)

4、計(jì) 60D工造1 20G工造2 30K加工3 25E木模、鑄件 40H加工2 15L裝試 35B外購配套件 45C下料 10F加工1 60網(wǎng)絡(luò)計(jì)劃17654328a設(shè)計(jì)D工造1G工造2K加工3E木模、鑄件H一、工序與事項(xiàng)工序 工程的組成部分稱為工序。 工時(shí) 完成工序所需要的持續(xù)時(shí)間雙代號(hào)法（箭桿式）：清理現(xiàn)場(chǎng)8（天）a8（天）或（i ,j ）tijiji j工序需要人力、物力投入，經(jīng)過一定時(shí)間才能完成。實(shí)工序：需要時(shí)間的工序?？赡懿恍枰肆Α⑽锪?。網(wǎng)絡(luò)圖的基本概念一、工序與事項(xiàng)工序 工程的組成部分稱為工序。雙代號(hào)虛工序：工時(shí)為0 的工序。不需要人力、物力，不存在。表明工序間的邏輯關(guān)系。2. 事

5、項(xiàng) 工序都有兩個(gè)事項(xiàng)-開工事項(xiàng)、完工事項(xiàng)。（i ,j ）tijij工序（i , j）的開工事項(xiàng)工序（i , j）的完工事項(xiàng) 任一工序有且僅有兩個(gè)事項(xiàng)；直接連結(jié)兩個(gè)事項(xiàng)的箭桿只能有一根。jbaiaijib網(wǎng)絡(luò)圖的基本概念虛工序：工時(shí)為0 的工序。不需要人力、物力，不存在。表明工序工序間的基本邏輯關(guān)系 對(duì)工序（i, j）：緊前工序、緊后工序、平行工序。ij平行緊前緊后4 . 舉例（1）工序c，d，e是平行工序，它們的緊前工序都是a與b。abedc網(wǎng)絡(luò)圖的基本概念工序間的基本邏輯關(guān)系ij平行緊前緊后4 . 舉例（1）工序c（2）工序a有緊后工序c與d，工序d有緊前工序b與a。abdc（3）工序a有緊

6、后工序b與c，工序d有緊前工序b與c。adcb網(wǎng)絡(luò)圖的基本概念（2）工序a有緊后工序c與d，工序d有緊前工序b與a。abd（4）工序a有緊后工序b與d，工序c有緊后工序d與e。adcbe網(wǎng)絡(luò)圖的基本概念（4）工序a有緊后工序b與d，工序c有緊后工序d與e。adc利用公式期望時(shí)間=5. 工時(shí)確定單一時(shí)間確定法：以前多次執(zhí)行過的、有可靠的生產(chǎn)定額值的，可以一個(gè)確定的時(shí)間作為它的工時(shí)。三種時(shí)間確定法：初次執(zhí)行，無資料可循。a=最樂觀時(shí)間、b=最保守時(shí)間、m=最可能時(shí)間估計(jì)網(wǎng)絡(luò)圖的基本概念利用公式期望時(shí)間=5. 工時(shí)確定單一時(shí)間確定法：以前多次執(zhí)行 對(duì)承擔(dān)的工程經(jīng)過工序分解、工時(shí)確定，根據(jù)生產(chǎn)工藝、生

7、產(chǎn)組織的制約確定出各工序間的邏輯關(guān)系后，可以用一張網(wǎng)絡(luò)圖把上述各點(diǎn)統(tǒng)一反映出來，借以形象地表達(dá)工程計(jì)劃方案的編制。繪制網(wǎng)絡(luò)圖：前進(jìn)法、后退法、任意法。草圖逐步調(diào)整（盡量消除箭桿的交叉）（正確運(yùn)用虛工序）排列整齊、完整準(zhǔn)確反映工程計(jì)劃編制的網(wǎng)絡(luò)圖。注意：1. 總開工、總完工事項(xiàng)都是唯一的；2. 編號(hào)：總開工事項(xiàng)1，各事項(xiàng)編號(hào)不重復(fù)，任一工序完工事項(xiàng)編號(hào)大于開工事項(xiàng)編號(hào)，總完工事項(xiàng)為n.網(wǎng)絡(luò)圖的建立 對(duì)承擔(dān)的工程經(jīng)過工序分解、工時(shí)確定，根據(jù)生產(chǎn)工藝、生前表對(duì)應(yīng)的網(wǎng)絡(luò)圖。adcbeflgijkmnh101044424824166832141612654798101112網(wǎng)絡(luò)圖的建立前表對(duì)應(yīng)的網(wǎng)絡(luò)圖。

8、adcbeflgijkmnh10104441 事項(xiàng)的參數(shù)1) 事項(xiàng)的最早（可能）開始時(shí)刻-E 事項(xiàng) i 的最早（可能）開始時(shí)刻：在此之前，事項(xiàng)i 不可能開始?？傞_工事項(xiàng)，最早可能開始時(shí)刻=0，即E1=0。EiL計(jì)算：從總開工事項(xiàng)起。從左至右 地對(duì)其余事項(xiàng)予以計(jì)算。adcb8107454321221815802 PERT網(wǎng)絡(luò)圖時(shí)間參數(shù)的計(jì)算1 事項(xiàng)的參數(shù)1) 事項(xiàng)的最早（可能）開始時(shí)刻-E adcbefl104824166854321671010016402444484824gijkmnh10442441612910876111244608076adcbefl104824166854321671

9、010012) 最遲（必須）結(jié)束時(shí)刻-L 事項(xiàng) j 的最遲（必須）結(jié)束時(shí)刻：在此之后，事項(xiàng)j 不結(jié)束，就會(huì)造成工程拖期?？偼旯な马?xiàng)，最遲（必須）結(jié)束時(shí)刻L n=En=總工期EiL484824gijkmnh104424416129108761112446080762 PERT網(wǎng)絡(luò)圖時(shí)間參數(shù)的計(jì)算2) 最遲（必須）結(jié)束時(shí)刻-L 事項(xiàng) j 的最遲484824gijkmnh1044244161291087611124460807601010164052446048607680adcbefl1048241668543216710100164024445244網(wǎng)絡(luò)圖的時(shí)間參數(shù)484824gijkmnh10

10、442441612910876162. 工序的參數(shù)工序的最早可能開工時(shí)刻、最遲必須完工時(shí)刻、總時(shí)差1) 工序的最早可能開工時(shí)刻-ES 以事項(xiàng) i 為開工事項(xiàng)的所有工序，最早可能開工時(shí)刻都相同，ESij=Ei010101640adcbefl1048 241668543216710100164024445244Li（i ,j）tiijiEiEjLjESij00101016402 PERT網(wǎng)絡(luò)圖時(shí)間參數(shù)的計(jì)算162. 工序的參數(shù)工序的最早可能開工時(shí)刻、最遲必須完工時(shí)刻484824gijkmnh104424416129108761112446080765244604860768024444444486

11、076網(wǎng)絡(luò)圖的時(shí)間參數(shù)484824gijkmnh104424416129108762) 工序的最遲必須完工時(shí)刻-LF 以事項(xiàng) j為完工事項(xiàng)的所有工序，最遲必須完工時(shí)刻都相同，LFij=Lj484824gijkmnh10442441612910876111244608076524460486076802444444448607680767660604860網(wǎng)絡(luò)圖的時(shí)間參數(shù)2) 工序的最遲必須完工時(shí)刻-LF 以5216010101640adcbefl1048 24166854321671010016402444524400101016404440401610103. 工序的總時(shí)差-TF 每一道工序

12、都有兩個(gè)時(shí)刻-最遲必須完工時(shí)刻與最早可能開工時(shí)刻，兩者之差即為該工序的最大可用時(shí)間。 如果這一時(shí)間比工序的工時(shí)大-機(jī)動(dòng)時(shí)間，稱為工序（i , j ）的總時(shí)差。網(wǎng)絡(luò)圖的時(shí)間參數(shù)5216010101640adcbefl1048 24166工序的總時(shí)差記為Tfij Tfij=Lj-Ei-Ti,jLi（i ,j）tijjiEiEjLjESijLFijTfijtij網(wǎng)絡(luò)圖的時(shí)間參數(shù)工序的總時(shí)差記為TfijLi（i ,j）tijjiEiEjL1.關(guān)鍵工序與關(guān)鍵線路關(guān)鍵工序：總時(shí)差為0的工序。關(guān)鍵路線：由關(guān)鍵工序組成的從總開工到總完工事項(xiàng) 的一條路線。非關(guān)鍵工序：總時(shí)差大于0 的工序。2.網(wǎng)絡(luò)圖優(yōu)化的原則1

13、) 向非關(guān)鍵工序要資源；2) 向關(guān)鍵工序要時(shí)間3 網(wǎng)絡(luò)圖的優(yōu)化分析1.關(guān)鍵工序與關(guān)鍵線路關(guān)鍵工序：總時(shí)差為0的工序。2.網(wǎng)絡(luò)圖 3. 網(wǎng)絡(luò)圖優(yōu)化 （1）時(shí)間優(yōu)化 （2） 時(shí)間資源優(yōu)化 （3）時(shí)間費(fèi)用優(yōu)化網(wǎng)絡(luò)圖的優(yōu)化分析 3. 網(wǎng)絡(luò)圖優(yōu)化 網(wǎng)絡(luò)圖的優(yōu)化分析5216010101640adcbefl1048 2416685432167101001640244452440010101640444040161010484824gijkmnh10442441612910876111244608076524460486076802444444448607680767660604860如工期壓縮為75天，應(yīng)壓

14、縮那些工序的工時(shí)？關(guān)鍵工序。1、 時(shí)間優(yōu)化5216010101640adcbefl1048 24166 網(wǎng)絡(luò)圖優(yōu)化 （1）時(shí)間優(yōu)化壓縮關(guān)鍵工序的工時(shí)。 原非關(guān)鍵工序可能變成關(guān)鍵工序。需要重新調(diào)整網(wǎng)絡(luò)圖。網(wǎng)絡(luò)圖的優(yōu)化分析 網(wǎng)絡(luò)圖優(yōu)化 原非關(guān)鍵工序可5216010101640adcbefl1048 2416685432167101001640244452440010101640444040161010484824gijkmnh10442441612910876111244608076524460486076802444444448607680767660604860如工期工序g1天，壓縮j6天，網(wǎng)

15、絡(luò)圖變?yōu)?216010101640adcbefl1048 241665216010101640adcbefl1048 2416685432167101001640244452440010101640444040161010484724gijkmnh1043244166910876111244547470524454485470742444444447547074767054544854如工期定為73天，壓縮工序g1天，工序j6天，網(wǎng)絡(luò)圖如圖。關(guān)鍵工序有所變化。但未達(dá)到工期73天的要求。在其他的關(guān)鍵工序上再壓縮1天。在工序g或j上可少壓縮1天。5216010101640adcbefl1048 2

16、4166 （2）時(shí)間資源優(yōu)化。 盡量合理地利用現(xiàn)有的資源，并縮短工程周期。 優(yōu)先安排關(guān)鍵工序和視察較小的工序所需要的資源； 均衡地使用人力、設(shè)備等資源，利用非關(guān)鍵工序的總時(shí)差，錯(cuò)開各工序的開始時(shí)間，拉平資源需要量的高峰； 在確實(shí)受到資源限制，或在考慮綜合經(jīng)濟(jì)效益的前提下，可適當(dāng)推遲工程完工時(shí)間。網(wǎng)絡(luò)圖的優(yōu)化分析 （2）時(shí)間資源優(yōu)化。網(wǎng)絡(luò)圖的優(yōu)化分析1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17時(shí)間032146785 資源（人數(shù)）6人3天9人4天7人4天9人3天7人4天4人7天5人3天8人6天6人5天12人2天2人2天ADFGEHIJKCB27 27 31 3

17、2 25 16 19 17 17 17 12 12 10 6 6 6 6虛箭線代表時(shí)差規(guī)定：每天可用人數(shù)不能超過22人。A、B、C中推遲哪一個(gè)？ B是關(guān)鍵工序。 A、 C線路有時(shí)差。1 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17時(shí)間032146785 資源（人數(shù)）6人3天9人4天7人4天9人3天7人4天4人7天5人3天8人6天6人5天12人2天2人2天ADFGEHIJKCB21 21 31 31 24 16 19 19 19 17 17 17 10 6 6 6 6規(guī)定：每天可用人數(shù)不能超過22人。無時(shí)差無時(shí)差F時(shí)差為1，G時(shí)差為4，應(yīng)推遲

18、G；人力：推遲G，人力為9+9+6=24人，超過規(guī)定。推遲F，必須推遲2天。1 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 180321467856人3天9人4天7人4天9人3天7人4天4人7天5人3天8人6天6人5天12人2天2人2天ADFGEHIJKCB21 21 22 22 24 25 20 19 19 17 17 17 12 6 6 6 6 6規(guī)定：每天可用人數(shù)不能超過22人。無時(shí)差E時(shí)差為1，推遲1天.1 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 180321467856

19、人3天9人4天7人4天9人3天7人4天4人7天5人3天8人6天6人5天12人2天2人2天ADFGEHIJKCB21 21 22 22 22 25 22 19 19 17 17 17 12 6 6 6 6 6規(guī)定：每天可用人數(shù)不能超過22人。時(shí)差1D時(shí)差為1，推遲1天.1 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 180321467856人3天9人4天7人4天9人3天7人4天4人7天5人3天8人6天6人5天12人2天2人2天ADFGEHIJKCB21 21 22 22 22 18 22 19 19 19 17 17 17 10 6 6 6

20、 6規(guī)定：每天可用人數(shù)不能超過22人?？偣て?8天1 2 3 4 5 網(wǎng)絡(luò)圖的優(yōu)化分析 （3）時(shí)間成本優(yōu)化。 工程完工時(shí)間短，費(fèi)用少；或保證既定的完工時(shí)間，所需的費(fèi)用最少；或在限制費(fèi)用的條件下，工程完工時(shí)間最短。 費(fèi)用分類：直接費(fèi)用、間接費(fèi)用。正常時(shí)間極限時(shí)間間接費(fèi)用直接費(fèi)用總費(fèi)用工程費(fèi)用 直接費(fèi)用增長率：縮短1天工期的直接費(fèi)用變動(dòng)率。g=極限時(shí)間的費(fèi)用-正常時(shí)間的費(fèi)用正常時(shí)間-極限時(shí)間網(wǎng)絡(luò)圖的優(yōu)化分析 正常時(shí)間極限時(shí)間間接費(fèi)用直接費(fèi)用總費(fèi)用工序 正常時(shí)間（周）極限時(shí)間（周）正常直接費(fèi)用（元）極限直接費(fèi)用（元）直接費(fèi)用增長率（元/周）A1150005000-B325000120007000C7

21、411000170002000D5310000120001000E868500125002000F428500165004000G1150005000-例 某工程按正常時(shí)間繪制的網(wǎng)絡(luò)圖及費(fèi)用數(shù)據(jù)如下試求該工程在可能情況下的最短工期及其費(fèi)用。應(yīng)用舉例工序 正常時(shí)間（周）極限時(shí)間（周）正常直接費(fèi)用（元）極限直接方案1：直接費(fèi)用總和：53000元1 2 3 4 5 6 7 8 9 10 11 12 13 14052143ADCFEB 15000 3-25000 12000G 7-411000 17000 5-310000 12000 8-68500 12500 4-28500 16500 15000

22、增長率A-B7000C2000D1000E2000F4000G-1.壓縮D工序1周 。紅線為關(guān)鍵線路方案1：直接費(fèi)用總和：53000元1 2 方案2：直接費(fèi)用總和：54000元1 2 3 4 5 6 7 8 9 10 11 12 13 14052143ADCFEB 15000 3-25000 12000G 7-411000 17000 4-311000 12000 8-68500 12500 4-28500 16500 15000增長率A-B7000C2000D1000E2000F4000G-1.壓縮D工序1周 。2.壓縮D、C、E工序各1周 。方案2：直接費(fèi)用總和：54000元1 2 方案3：直接費(fèi)用總和：59000元1 2 3 4 5 6 7 8 9 10 11 12 13 14052143ADCFEB 15000 3-25000 12000G 6-413000 17000 312000 7-610500 12500 4-28500 16500 15000增長率A-B7000C2000D1000E2000F4000G-1.壓縮D工序1周 。2.壓縮D、C、E工序各1周 ，費(fèi)用增加5000元。方案3：直接費(fèi)用總和：59000元1 2 方案3：直接費(fèi)用總和：59000元1 2 3 4 5 6 7 8 9 10 11 12 13 14052143ADCFEB 15000 3-2