運(yùn)籌08(第7章PERT)運(yùn)籌學(xué)第五版課件(歷史上最好的,最全面的課件)

2023/2/11運(yùn)籌學(xué)

OPERATIONSRESEARCH

2023/2/12第七章計(jì)劃評(píng)審技術(shù)和關(guān)鍵路線法

（ProgramEvaluationandReviewTechnique，

CriticalPathMethod）§

1．PERT網(wǎng)絡(luò)圖§3．關(guān)鍵路線和網(wǎng)絡(luò)計(jì)劃的優(yōu)化§4．完成作業(yè)的期望時(shí)間和在規(guī)定時(shí)間內(nèi)實(shí)現(xiàn)事件的概率§

2．PERT網(wǎng)絡(luò)圖的計(jì)算2023/2/13網(wǎng)絡(luò)計(jì)劃技術(shù)：又稱統(tǒng)籌法，是綜合運(yùn)用計(jì)劃評(píng)審技術(shù)和關(guān)鍵路線法的一種計(jì)劃管理方法。計(jì)劃評(píng)審技術(shù)（PERT）：是對(duì)計(jì)劃項(xiàng)目進(jìn)行核算、評(píng)價(jià)，然后選定最優(yōu)計(jì)劃方案的一種技術(shù)。

能直觀清晰的反映計(jì)劃各部門或各項(xiàng)工作之間的相互聯(lián)系和制約； 反映某一部門或某項(xiàng)工作在全局中的地位和影響，便于發(fā)現(xiàn)薄弱環(huán)節(jié)以采取措施；關(guān)鍵路線法（CRM）：是在計(jì)劃項(xiàng)目的各項(xiàng)錯(cuò)綜復(fù)雜的工作中，抓住其中的關(guān)鍵路線進(jìn)行計(jì)劃安排的一種方法。研究費(fèi)用與工期的相互關(guān)系。2023/2/14§7.1PERT網(wǎng)絡(luò)圖一、基本概念1、作業(yè)：任何消耗時(shí)間或資源的行動(dòng)。（箭線表示，（i,j))

2、事件：作業(yè)開始或結(jié)束的標(biāo)志。（圈中加數(shù)字或字母表示）

作業(yè)的起點(diǎn)事件、終點(diǎn)事件；（i,j)

最初事件、最終事件（唯一）；緊前作業(yè)，緊后作業(yè)

（事件本身不消耗時(shí)間或資源，或相對(duì)于作業(yè)，消耗量可忽略不計(jì)）2145361h4h5h2h3h3h2h2023/2/153、路線：PERT網(wǎng)絡(luò)圖中由最初事件到最終事件的各項(xiàng)作業(yè)連貫組成的一條路。路的長(zhǎng)度：完成該路上各項(xiàng)作業(yè)持續(xù)時(shí)間的長(zhǎng)度和。

關(guān)鍵路線：由最初事件到最終事件的各項(xiàng)作業(yè)累計(jì)時(shí)間最長(zhǎng)的路。路線1，2，5，68小時(shí)路線1，3，5，611小時(shí)關(guān)鍵路線路線1，4，5，67小時(shí)2023/2/16二、建立PERT網(wǎng)絡(luò)圖的準(zhǔn)則和注意事項(xiàng)1、作業(yè)（i,j)用唯一箭線表示，起點(diǎn)事件（箭尾事件）編號(hào)小于終點(diǎn)事件（箭頭事件）的編號(hào)。2、兩個(gè)事件之間只能用一條箭線表示一項(xiàng)作業(yè)，具有相同開始和結(jié)束的不同作業(yè)，需引進(jìn)虛事件和虛作業(yè)。21515虛箭線表示虛活動(dòng)，不消耗資源，不占用時(shí)間2023/2/173、各項(xiàng)作業(yè)間的幾種關(guān)系及圖上表示方法（1）作業(yè)a結(jié)束后可以開始b,c；（2）作業(yè)c在a,b

結(jié)束后才可以開始；（3）作業(yè)a,b結(jié)束后可以開始

c,d

；（4）作業(yè)c在a結(jié)束后即可以開始，d在a,b

結(jié)束后才可以開始。2143abc2143abc52143abcd(1)

(2)

(3)52143abcd6(4)2023/2/184、PERT網(wǎng)絡(luò)圖中不允許出現(xiàn)回路。5、PERT網(wǎng)絡(luò)圖的布局一般是從左到右，從上到下，盡量避免箭線交叉。三、PERT網(wǎng)絡(luò)圖的合并與簡(jiǎn)化若干局部網(wǎng)絡(luò)圖合并成一個(gè)大的全局網(wǎng)絡(luò)圖合并后的網(wǎng)絡(luò)圖需簡(jiǎn)化2023/2/193E12467835A2B8C4D1L5F3H7G2I60091011作業(yè)ABCDEFGHIJ緊前作業(yè)//ABBACEFDFGHI作業(yè)時(shí)間2341832765四、繪制PERT網(wǎng)絡(luò)圖2023/2/110§7.2PERT網(wǎng)絡(luò)圖的計(jì)算一、網(wǎng)絡(luò)時(shí)間的計(jì)算作業(yè)最早開始時(shí)間作業(yè)最早結(jié)束時(shí)間作業(yè)最遲結(jié)束時(shí)間作業(yè)最遲開始時(shí)間2023/2/111例：某項(xiàng)工程由11項(xiàng)作業(yè)組成，其計(jì)劃完成時(shí)間及作業(yè)間相互關(guān)系如表。繪制箭線式網(wǎng)絡(luò)圖計(jì)算各項(xiàng)時(shí)間作業(yè)計(jì)劃完成時(shí)間/天緊前作業(yè)作業(yè)計(jì)劃完成時(shí)間/天緊前作業(yè)A3-G21B，EB10-H35B，EC11-I25B，ED4BJ15F，G，IE4AK20F，GF15C，D2023/2/112虛箭線表示虛活動(dòng)，不消耗資源，不占用時(shí)間。F，15C，11A，512367845E，4B，10D，4J，15H，35G，21I，25K，202023/2/113計(jì)算各項(xiàng)時(shí)間:（1）最早開始和最早結(jié)束時(shí)間假設(shè)最初事件在零時(shí)刻實(shí)現(xiàn)A(1,2)，B(1,3)，C(1,4)的最早開始時(shí)間：A(1,2)，B(1,3)，C(1,4)的最早結(jié)束時(shí)間：E(2,5)的最早開始和最早結(jié)束時(shí)間：2023/2/114D(3,4)的最早開始和最早結(jié)束時(shí)間：虛作業(yè)（3，5）的最早開始和最早結(jié)束時(shí)間：F(4,6)的最早開始和最早結(jié)束時(shí)間：2023/2/115G(5,6)的最早開始和最早結(jié)束時(shí)間：I(5,7)的最早開始和最早結(jié)束時(shí)間：H(5,8)的最早開始和最早結(jié)束時(shí)間：2023/2/116完成所有作業(yè)的最短周期：J(7,8)的最早開始和最早結(jié)束時(shí)間：虛工序(6，7)的最早開始和最早結(jié)束時(shí)間：J(6,8)的最早開始和最早結(jié)束時(shí)間：2023/2/117（2）最遲結(jié)束和最遲開始時(shí)間假設(shè)所有作業(yè)在51天內(nèi)完成H(5,8),J(7,8),K(6,8)的最遲開始時(shí)間：H(5,8),J(7,8),K(6,8)的最遲結(jié)束時(shí)間：2023/2/118F，15C，11A，512367845E，4B，10D，4J，15H，35G，21I，25K，202023/2/119I(5,7)及（6，7）的最遲結(jié)束,最遲開始時(shí)間：G(5,6)的最遲結(jié)束,最遲開始時(shí)間：2023/2/120F(4,6)的最遲結(jié)束,最遲開始時(shí)間：E(2，5)的最遲結(jié)束,最遲開始時(shí)間：虛(3，5)的最遲結(jié)束,最遲開始時(shí)間：2023/2/121D(3，4)的最遲結(jié)束,最遲開始時(shí)間：C(1，4)的最遲結(jié)束,最遲開始時(shí)間：A(1，2)的最遲結(jié)束,最遲開始時(shí)間：2023/2/122B(1，3)的最遲結(jié)束,最遲開始時(shí)間：最初事件1的最遲開始時(shí)間：2023/2/123總時(shí)差R(i,j)：網(wǎng)絡(luò)上多于一項(xiàng)作業(yè)共同擁有的機(jī)動(dòng)時(shí)間?？倳r(shí)差為零的作業(yè)是關(guān)鍵作業(yè)，沒有任何機(jī)動(dòng)時(shí)間。自由時(shí)差F(i,j)

：不影響作業(yè)的各項(xiàng)緊后作業(yè)最早開工時(shí)間條件下，該作業(yè)可以推遲開工時(shí)間的最大限度。自由時(shí)差〉0的工序，尤其是自由時(shí)差較大的作業(yè)，可以適當(dāng)?shù)姆至魅?、?cái)、物給關(guān)鍵作業(yè)，可以縮短工期。二、時(shí)差的計(jì)算2023/2/124作業(yè)（i,j)t(i,j)tES(i,j)tEF(i,j)tLS(i,j)tLF(i,j)R(i,j)F(i,j)A(1,2)5051610B(1,3)1001001000C(1,4)1101151653E(2,5)45961011D(3,4)41014121620虛(3,5)01010101000F(4,6)151429163122G(5,6)211031103100I(5,7)251035113610H(5,8)351045165166虛(6,7)03131363654K(6,8)203151315100J(7,8)1535503651112023/2/125§7.3關(guān)鍵路線及網(wǎng)絡(luò)計(jì)劃的優(yōu)化關(guān)鍵路線：由最初事件到最終事件的各項(xiàng)作業(yè)累計(jì)時(shí)間最長(zhǎng)的路。F，15C，11A，512367845E，4B，10D，4J，15H，35G，21I，25K，20關(guān)鍵路線上各作業(yè)的總時(shí)差均為0。2023/2/126關(guān)鍵路線的意義：1、關(guān)鍵路線的持續(xù)時(shí)間決定了完成全盤計(jì)劃所必需的最少時(shí)間；2、關(guān)鍵路線上的各項(xiàng)作業(yè)對(duì)計(jì)劃進(jìn)度起決定作用，必須投入充分的人、財(cái)、物保證各作業(yè)按時(shí)完工。若想提前完工，必須縮短關(guān)鍵路線上的有關(guān)工序的時(shí)間。3、次關(guān)鍵路線可能成為關(guān)鍵路線，也要注意。例：要求上例中的工程在49天內(nèi)完成，可縮短有關(guān)工時(shí)的作業(yè)時(shí)間，產(chǎn)生的額外費(fèi)用如表所示，應(yīng)如何安排，可使得額增加的費(fèi)用最??？2023/2/127作業(yè)（i,j)計(jì)劃完成時(shí)間最短完成時(shí)間縮短1天增加的費(fèi)用B(1,3)108700C(1,4)118400E(2,5)43450G(5,6)2116600H(5,8)3530500I(5,7)2522300J(7,8)1512400K(6,8)20165001、要縮短工期，應(yīng)縮短關(guān)鍵路線上的B,G,K

作業(yè)時(shí)間2、額外費(fèi)用要最小，先考慮K3、縮短1天即會(huì)產(chǎn)生新的關(guān)鍵路線，故先縮短1天2023/2/128F，15C，11A，512367845E，4B，10D，4J，15H，35G，21I，25K，194、現(xiàn)有兩條關(guān)鍵路線，應(yīng)縮短關(guān)鍵路線上的B,G,K

，或

B，I，J作業(yè)時(shí)間5、額外費(fèi)用要最小，考慮B6、縮短1天即會(huì)產(chǎn)生新的關(guān)鍵路線，故縮短1天。已滿足要求2023/2/129最優(yōu)方案的選擇時(shí)間優(yōu)化：在人力、材料、設(shè)備、資金等資源基本有保證的條件下，尋求最短的工程周期。時(shí)間與資源的優(yōu)化：在合理利用資源的條件下，尋求最短的工程周期。時(shí)間與成本的優(yōu)化對(duì)于工期緊迫的工程，則在保證工期最短的情況下，尋求成本較低的方案。對(duì)于一般工程，則在成本最低的情況下，尋求合理的工程周期。目的是要找出總成本變動(dòng)中的成本最低點(diǎn)。2023/2/130網(wǎng)絡(luò)計(jì)劃技術(shù)的優(yōu)點(diǎn)減少項(xiàng)目的工期對(duì)復(fù)雜項(xiàng)目的進(jìn)一步控制資源的更有效利用能制定非常詳細(xì)的計(jì)劃能預(yù)測(cè)潛在