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

2023/2/11運籌學

OPERATIONSRESEARCH

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

（ProgramEvaluationandReviewTechnique，

CriticalPathMethod）§

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

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

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

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

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

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

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

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

：不影響作業(yè)的各項緊后作業(yè)最早開工時間條件下，該作業(yè)可以推遲開工時間的最大限度。自由時差〉0的工序，尤其是自由時差較大的作業(yè)，可以適當?shù)姆至魅?、財、物給關(guān)鍵作業(yè)，可以縮短工期。二、時差的計算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)絡計劃的優(yōu)化關(guān)鍵路線：由最初事件到最終事件的各項作業(yè)累計時間最長的路。F，15C，11A，512367845E，4B，10D，4J，15H，35G，21I，25K，20關(guān)鍵路線上各作業(yè)的總時差均為0。2023/2/126關(guān)鍵路線的意義：1、關(guān)鍵路線的持續(xù)時間決定了完成全盤計劃所必需的最少時間；2、關(guān)鍵路線上的各項作業(yè)對計劃進度起決定作用，必須投入充分的人、財、物保證各作業(yè)按時完工。若想提前完工，必須縮短關(guān)鍵路線上的有關(guān)工序的時間。3、次關(guān)鍵路線可能成為關(guān)鍵路線，也要注意。例：要求上例中的工程在49天內(nèi)完成，可縮短有關(guān)工時的作業(yè)時間，產(chǎn)生的額外費用如表所示，應如何安排，可使得額增加的費用最?。?023/2/127作業(yè)（i,j)計劃完成時間最短完成時間縮短1天增加的費用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、要縮短工期，應縮短關(guān)鍵路線上的B,G,K

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

，或

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