运筹08(第7章PERT)运筹学第五版课件(历史上最好的,最全面的课件)

2023/2/11运筹学

OPERATIONSRESEARCH

2023/2/12第七章计划评审技术和关键路线法

（ProgramEvaluationandReviewTechnique，

CriticalPathMethod）§

1．PERT网络图§3．关键路线和网络计划的优化§4．完成作业的期望时间和在规定时间内实现事件的概率§

2．PERT网络图的计算2023/2/13网络计划技术：又称统筹法，是综合运用计划评审技术和关键路线法的一种计划管理方法。计划评审技术（PERT）：是对计划项目进行核算、评价，然后选定最优计划方案的一种技术。

能直观清晰的反映计划各部门或各项工作之间的相互联系和制约； 反映某一部门或某项工作在全局中的地位和影响，便于发现薄弱环节以采取措施；关键路线法（CRM）：是在计划项目的各项错综复杂的工作中，抓住其中的关键路线进行计划安排的一种方法。研究费用与工期的相互关系。2023/2/14§7.1PERT网络图一、基本概念1、作业：任何消耗时间或资源的行动。（箭线表示，（i,j))

2、事件：作业开始或结束的标志。（圈中加数字或字母表示）

作业的起点事件、终点事件；（i,j)

最初事件、最终事件（唯一）；紧前作业，紧后作业

（事件本身不消耗时间或资源，或相对于作业，消耗量可忽略不计）2145361h4h5h2h3h3h2h2023/2/153、路线：PERT网络图中由最初事件到最终事件的各项作业连贯组成的一条路。路的长度：完成该路上各项作业持续时间的长度和。

关键路线：由最初事件到最终事件的各项作业累计时间最长的路。路线1，2，5，68小时路线1，3，5，611小时关键路线路线1，4，5，67小时2023/2/16二、建立PERT网络图的准则和注意事项1、作业（i,j)用唯一箭线表示，起点事件（箭尾事件）编号小于终点事件（箭头事件）的编号。2、两个事件之间只能用一条箭线表示一项作业，具有相同开始和结束的不同作业，需引进虚事件和虚作业。21515虚箭线表示虚活动，不消耗资源，不占用时间2023/2/173、各项作业间的几种关系及图上表示方法（1）作业a结束后可以开始b,c；（2）作业c在a,b

结束后才可以开始；（3）作业a,b结束后可以开始

c,d

；（4）作业c在a结束后即可以开始，d在a,b

结束后才可以开始。2143abc2143abc52143abcd(1)

(2)

(3)52143abcd6(4)2023/2/184、PERT网络图中不允许出现回路。5、PERT网络图的布局一般是从左到右，从上到下，尽量避免箭线交叉。三、PERT网络图的合并与简化若干局部网络图合并成一个大的全局网络图合并后的网络图需简化2023/2/193E12467835A2B8C4D1L5F3H7G2I60091011作业ABCDEFGHIJ紧前作业//ABBACEFDFGHI作业时间2341832765四、绘制PERT网络图2023/2/110§7.2PERT网络图的计算一、网络时间的计算作业最早开始时间作业最早结束时间作业最迟结束时间作业最迟开始时间2023/2/111例：某项工程由11项作业组成，其计划完成时间及作业间相互关系如表。绘制箭线式网络图计算各项时间作业计划完成时间/天紧前作业作业计划完成时间/天紧前作业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）最早开始和最早结束时间假设最初事件在零时刻实现A(1,2)，B(1,3)，C(1,4)的最早开始时间：A(1,2)，B(1,3)，C(1,4)的最早结束时间：E(2,5)的最早开始和最早结束时间：2023/2/114D(3,4)的最早开始和最早结束时间：虚作业（3，5）的最早开始和最早结束时间：F(4,6)的最早开始和最早结束时间：2023/2/115G(5,6)的最早开始和最早结束时间：I(5,7)的最早开始和最早结束时间：H(5,8)的最早开始和最早结束时间：2023/2/116完成所有作业的最短周期：J(7,8)的最早开始和最早结束时间：虚工序(6，7)的最早开始和最早结束时间：J(6,8)的最早开始和最早结束时间：2023/2/117（2）最迟结束和最迟开始时间假设所有作业在51天内完成H(5,8),J(7,8),K(6,8)的最迟开始时间：H(5,8),J(7,8),K(6,8)的最迟结束时间：2023/2/118F，15C，11A，512367845E，4B，10D，4J，15H，35G，21I，25K，202023/2/119I(5,7)及（6，7）的最迟结束,最迟开始时间：G(5,6)的最迟结束,最迟开始时间：2023/2/120F(4,6)的最迟结束,最迟开始时间：E(2，5)的最迟结束,最迟开始时间：虚(3，5)的最迟结束,最迟开始时间：2023/2/121D(3，4)的最迟结束,最迟开始时间：C(1，4)的最迟结束,最迟开始时间：A(1，2)的最迟结束,最迟开始时间：2023/2/122B(1，3)的最迟结束,最迟开始时间：最初事件1的最迟开始时间：2023/2/123总时差R(i,j)：网络上多于一项作业共同拥有的机动时间。总时差为零的作业是关键作业，没有任何机动时间。自由时差F(i,j)

：不影响作业的各项紧后作业最早开工时间条件下，该作业可以推迟开工时间的最大限度。自由时差〉0的工序，尤其是自由时差较大的作业，可以适当的分流人、财、物给关键作业，可以缩短工期。二、时差的计算2023/2/124作业（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关键路线及网络计划的优化关键路线：由最初事件到最终事件的各项作业累计时间最长的路。F，15C，11A，512367845E，4B，10D，4J，15H，35G，21I，25K，20关键路线上各作业的总时差均为0。2023/2/126关键路线的意义：1、关键路线的持续时间决定了完成全盘计划所必需的最少时间；2、关键路线上的各项作业对计划进度起决定作用，必须投入充分的人、财、物保证各作业按时完工。若想提前完工，必须缩短关键路线上的有关工序的时间。3、次关键路线可能成为关键路线，也要注意。例：要求上例中的工程在49天内完成，可缩短有关工时的作业时间，产生的额外费用如表所示，应如何安排，可使得额增加的费用最小？2023/2/127作业（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、要缩短工期，应缩短关键路线上的B,G,K

作业时间2、额外费用要最小，先考虑K3、缩短1天即会产生新的关键路线，故先缩短1天2023/2/128F，15C，11A，512367845E，4B，10D，4J，15H，35G，21I，25K，194、现有两条关键路线，应缩短关键路线上的B,G,K

，或

B，I，J作业时间5、额外费用要最小，考虑B6、缩短1天即会产生新的关键路线，故缩短1天。已满足要求2023/2/129最优方案的选择时间优化：在人力、材料、设备、资金等资源基本有保证的条件下，寻求最短的工程周期。时间与资源的优化：在合理利用资源的条件下，寻求最短的工程周期。时间与成本的优化对于工期紧迫的工程，则在保证工期最短的情况下，寻求成本较低的方案。对于一般工程，则在成本最低的情况下，寻求合理的工程周期。目的是要找出总成本变动中的成本最低点。2023/2/130网络计划技术的优点减少项目的工期对复杂项目的进一步控制资源的更有效利用能制定非常详细的计划能预测潜在