运筹学基础及应用第五PERT.pptx

2024/11/12 周二1运筹学运筹学OPERATIONS RESEARCH2024/11/12 周二2第七章第七章 计划评审技术和关键路线法计划评审技术和关键路线法（Program Evaluation and Review Technique，Critical Path Method）1 PERT PERT 网络图网络图 3关键路线和网络计划的优化关键路线和网络计划的优化 4完成作业的期望时间和完成作业的期望时间和 在规定时间内实现事件的概率在规定时间内实现事件的概率 2 PERT PERT 网络图的计算网络图的计算2024/11/12 周二3n网络计划技术：又称统筹法，是综合运用计划评审技术网络计划技术：又称统筹法，是综合运用计划评审技术和关键路线法的一种比较先进的计划管理方法。和关键路线法的一种比较先进的计划管理方法。q计划评审技术（计划评审技术（PERTPERT）：是对计划项目进行核算、评）：是对计划项目进行核算、评价，然后选定最优计划方案的一种技术。价，然后选定最优计划方案的一种技术。能直观清晰的反映计划各部门或各项工作之间的相互联系和制能直观清晰的反映计划各部门或各项工作之间的相互联系和制约；约；反映某一部门或某项工作在全局中的地位和影响，便于发现薄反映某一部门或某项工作在全局中的地位和影响，便于发现薄弱环节以采取措施；弱环节以采取措施；q关键路线法（关键路线法（CRMCRM）：是在计划项目的各项错综复杂的工）：是在计划项目的各项错综复杂的工作中，抓住其中的关键路线进行计划安排的一种方法。研究作中，抓住其中的关键路线进行计划安排的一种方法。研究费用与工期的相互关系。费用与工期的相互关系。2024/11/12 周二47.1 PERT 7.1 PERT 网络图网络图一、一、基本概念基本概念1 1、作业：任何消耗时间或资源的行动。、作业：任何消耗时间或资源的行动。（箭线表示，（箭线表示，（i,j)i,j)2 2、事件：作业开始或结束的标志。、事件：作业开始或结束的标志。（圈中加数字或字母表示）（圈中加数字或字母表示）作业的起点事件、终点事件；作业的起点事件、终点事件；，（，（i,j)i,j)最初事件、最终事件最初事件、最终事件（唯一）；唯一）；紧前作业，紧后作业紧前作业，紧后作业 （事件本身不消耗时间或资源，或相对于作业，消耗量可忽略不计）（事件本身不消耗时间或资源，或相对于作业，消耗量可忽略不计）2145361h4h5h2h3h3h2h2024/11/12 周二53 3、路线：路线：PERT PERT 网络图中由最初事件到最终事件的各项作网络图中由最初事件到最终事件的各项作 业连贯组成的一条路。业连贯组成的一条路。路的长度：完成该路上各项作业持续时间的长度和。路的长度：完成该路上各项作业持续时间的长度和。关键路线：由最初事件到最终事件的各项作业累计时间最关键路线：由最初事件到最终事件的各项作业累计时间最 长的路。长的路。路线路线1 1，2 2，5 5，6 86 8小时小时路线路线1 1，3 3，5 5，6 116 11小时小时 关键路线关键路线路线路线1 1，4 4，5 5，6 76 7小时小时2024/11/12 周二6二、建立二、建立 PERT PERT 网络图的准则和注意事项网络图的准则和注意事项1 1、作业、作业（i,j)i,j)用唯一箭线表示，起点事件（箭尾事件）编号用唯一箭线表示，起点事件（箭尾事件）编号 小于终点事件（箭头事件）的编号。小于终点事件（箭头事件）的编号。2 2、两个事件之间只能用一条箭线表示一项作业，具有相同开、两个事件之间只能用一条箭线表示一项作业，具有相同开 始和结束的不同作业，需引进虚事件和虚作业。始和结束的不同作业，需引进虚事件和虚作业。215152024/11/12 周二73 3、各项作业、各项作业间的几种关系及图上表示方法间的几种关系及图上表示方法（1 1）作业）作业 a a 结束后可以开始结束后可以开始 b,c b,c；（2 2）作业作业 c c 在在 a,b a,b 结束后才可以开始；结束后才可以开始；（3 3）作业）作业 a,ba,b 结束后可以开始结束后可以开始 c,d c,d；（4 4）作业）作业 c c 在在 a a 结束后即可以开始，结束后即可以开始，d d 在在 a,b a,b 结束后才结束后才 可以开始。可以开始。2143abc2143abc52143abcd(1)(2)(3)52143abcd6(4)虚箭线表示虚活动，不虚箭线表示虚活动，不消耗资源，不占用时间消耗资源，不占用时间2024/11/12 周二84 4、PERT PERT 网络图中不允许出现回路。网络图中不允许出现回路。5 5、PERT PERT 网络图的布局一般是从左到右，从上到下，尽量避网络图的布局一般是从左到右，从上到下，尽量避 免箭线交叉。免箭线交叉。三、三、PERT PERT 网络图的合并与简化网络图的合并与简化若干局部网络图合并成一个大的全局网络图若干局部网络图合并成一个大的全局网络图合并后的网络图需简化合并后的网络图需简化 2024/11/12 周二93E12467835A2B8C4D1L5F3H7G2I60091011作业ABCD EFGHIJ紧前作业/ABB ACEFDFGHI作业时间2341832765四、绘制四、绘制 PERT PERT 网络图网络图2024/11/12 周二107.2 PERT 7.2 PERT 网络图的计算网络图的计算一、网络时间的计算一、网络时间的计算作业最早开始时间作业最早开始时间作业最早结束时间作业最早结束时间作业最迟结束时间作业最迟结束时间作业最迟开始时间作业最迟开始时间2024/11/12 周二11例：例：某项工程由某项工程由1111项作业组成，其计划完成时间及作业间相项作业组成，其计划完成时间及作业间相 互关系如表。互关系如表。绘制箭线式网络图绘制箭线式网络图计算各项时间计算各项时间作业作业计划完成计划完成时间时间/天天紧前作业紧前作业作业作业计划完成计划完成时间时间/天天紧前作业紧前作业A3-G21B，EB10-H35B，EC11-I25B，ED4BJ15F，G，IE4AK20F，GF15C，D2024/11/12 周二12F，15C，11A，512367845E，4B，10D，4J，15H，35G，21I，25K，20 虚箭线表示虚活动，不消耗资源，不占用时间。虚箭线表示虚活动，不消耗资源，不占用时间。2024/11/12 周二13计算各项时间计算各项时间:（1 1）最早开始和最早结束时间）最早开始和最早结束时间 假设最初事件在零时刻实现假设最初事件在零时刻实现A(1,2)A(1,2)，B(1,3)B(1,3)，C(1,4)C(1,4)的最早开始时间：的最早开始时间：A(1,2)A(1,2)，B(1,3)B(1,3)，C(1,4)C(1,4)的最早结束时间：的最早结束时间：E(2,5)E(2,5)的最早开始和最早结束时间：的最早开始和最早结束时间：2024/11/12 周二14D(3,4)D(3,4)的最早开始和最早结束时间：的最早开始和最早结束时间：虚作业（虚作业（3 3，5 5）的最早开始和最早结束时间：）的最早开始和最早结束时间：F(4,6)F(4,6)的最早开始和最早结束时间：的最早开始和最早结束时间：2024/11/12 周二15G(5,6)G(5,6)的最早开始和最早结束时间：的最早开始和最早结束时间：I(5,7)I(5,7)的最早开始和最早结束时间：的最早开始和最早结束时间：H(5,8)H(5,8)的最早开始和最早结束时间：的最早开始和最早结束时间：2024/11/12 周二16完成所有作业的最短周期：完成所有作业的最短周期：J(7,8)J(7,8)的最早开始和最早结束时间：的最早开始和最早结束时间：虚工序虚工序(6(6，7)7)的最早开始和最早结束时间：的最早开始和最早结束时间：J(6,8)J(6,8)的最早开始和最早结束时间：的最早开始和最早结束时间：2024/11/12 周二17（2 2）最迟结束和最迟开始时间）最迟结束和最迟开始时间假设所有作业在假设所有作业在5151天内完成天内完成H(5,8),J(7,8),K(6,8)H(5,8),J(7,8),K(6,8)的最迟开始时间：的最迟开始时间：H(5,8),J(7,8),K(6,8)H(5,8),J(7,8),K(6,8)的最迟结束时间：的最迟结束时间：2024/11/12 周二18F，15C，11A，512367845E，4B，10D，4J，15H，35G，21I，25K，20 2024/11/12 周二19I(5,7)I(5,7)及（及（6 6，7 7）的最迟结束）的最迟结束,最迟开始时间：最迟开始时间：G(5,6)G(5,6)的最迟结束的最迟结束,最迟开始时间：最迟开始时间：2024/11/12 周二20F(4,6)F(4,6)的最迟结束的最迟结束,最迟开始时间：最迟开始时间：E(2E(2，5)5)的最迟结束的最迟结束,最迟开始时间：最迟开始时间：虚虚(3(3，5)5)的最迟结束的最迟结束,最迟开始时间：最迟开始时间：2024/11/12 周二21D(3D(3，4)4)的最迟结束的最迟结束,最迟开始时间：最迟开始时间：C(1C(1，4)4)的最迟结束的最迟结束,最迟开始时间：最迟开始时间：A(1A(1，2)2)的最迟结束的最迟结束,最迟开始时间：最迟开始时间：2024/11/12 周二22B(1B(1，3)3)的最迟结束的最迟结束,最迟开始时间：最迟开始时间：最初事件最初事件1 1的最迟开始时间：的最迟开始时间：2024/11/12 周二23总时差总时差R(i,j)R(i,j)：网络上多于一项作业共同拥有的机动时间。网络上多于一项作业共同拥有的机动时间。总时差为零的作业是关键作业，没有任何机动时间。总时差为零的作业是关键作业，没有任何机动时间。自由时差自由时差F(i,j)F(i,j)：不影响作业的各项紧后作业最早开工时不影响作业的各项紧后作业最早开工时 间条件下，该作业可以推迟开工时间的最大限度。间条件下，该作业可以推迟开工时间的最大限度。自由时差自由时差0 0的工序，尤其是自由时差较大的作业，可以适当的工序，尤其是自由时差较大的作业，可以适当的分流人、财、物给关键作业，可以缩短工期。的分流人、财、物给关键作业，可以缩短工期。二、时差的计算二、时差的计算2024/11/12 周二24作业（作业（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)1535503651112024/11/12 周二257.3 7.3 关键路线及网络计划的优化关键路线及网络计划的优化关键路线：由最初事件到最终事件的各项作业累计关键路线：由最初事件到最终事件的各项作业累计 时间最长的路。时间最长的路。F，15C，11A，512367845E，4B，10D，4J，15H，35G，21I，25K，20 关键路线上各作业的总时差均为关键路线上各作业的总时差均为0 0。2024/11/12 周二26关键路线的意义：关键路线的意义：1 1、关键路线的持续时间决定了完成全盘计划所必需的最、关键路线的持续时间决定了完成全盘计划所必需的最 少时间；少时间；2 2、关键路线上的各项作业对计划进度起决定作用，必须、关键路线上的各项作业对计划进度起决定作用，必须 投入充分的人、财、物保证各作业按时完工。若想提投入充分的人、财、物保证各作业按时完工。若想提 前完工，必须缩短关键路线上的有关工序的时间。前完工，必须缩短关键路线上的有关工序的时间。3 3、次关键路线可能成为关键路线，也要注意。、次关键路线可能成为关键路线，也要注意。例：例：要求上例中的工程在要求上例中的工程在4949天内完成，可缩短有关工时的作天内完成，可缩短有关工时的作 业时间，产生的额外费用如表所示，应如何安排，可使业时间，产生的额外费用如表所示，应如何安排，可使 得额增加的费用最小？得额增加的费用最小？2024/11/12 周二27作业（作业（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 1、要缩短工期，应缩短关键路线上的要缩短工期，应缩短关键路线上的 B,G,KB,G,K 作业时间作业时间2 2、额外费用要最小，先考虑、额外费用要最小，先考虑 K K 3 3、缩短缩短1 1天即会产生新的关键路线，故先缩短天即会产生新的关键路线，故先缩短1 1天天2024/11/12 周二28F，15C，11A，512367845E，4B，10D，4J，15H，35G，21I，25K，19 4 4、现有两条关键路线，、现有两条关键路线，应缩短关键路线上的应缩短关键路线上的 B,G,KB,G,K ，或，或 B B，I I，J J作业时间作业时间5 5、额外费用要最小，考虑、额外费用要最小，考虑 B B6 6、缩短缩短1 1天即会产生新的关键路线，故缩短天即会产生新的关键路线，故缩短1 1天。已满足要求天。已满足要求2024/11/12 周二29n最优方案的选择最优方案的选择时间优化：在人力、材料、设备、资金等资源时间优化：在人力、材料、设备、资金等资源基本有保证的条件下，寻求最短的工程周期。基本有保证的条件下，寻求最短的工程周期。时间与资源的优化：在合理利用资源的条件下，时间与资源的优化：在合理利用资源的条件下，寻求最短的工程周期。寻求最短的工程周期。时间与成本的优化时间与成本的优化n对于工期紧迫的工程，则在保证工期最短的情况下，对于工期紧迫的工程，则在保证工期最短的情况下，寻求成本较低的方案。对于一般工程，则在成本最寻求成本较低的方案。对于一般工程，则在成本最低的情况下，寻求合理的工程周期。低的情况下，寻求合理的工程周期。n目的是要找出总成本变动中的成本最低点。目的是要找出总成本变动中的成本最低点。2024/11/12 周二30n网络计划技术的优点网络计划技术的优点减少项目的工期减少项目的工期对复杂项目的进一步控制对复杂项目的进一步控制资源的更有效利用资源的更有效利用能制定非常详细的计划能制定非常详细的计划能预测潜在的瓶颈问题能预测潜在的瓶颈问题能找出关键活动能找出关键活动重视各活动之间的内在关系重视各活动之间的内在关系2024/11/12 周二317.4 7.4 完成作业的期望时间和完成作业的期望时间和 在规定时间内实现事件的概率在规定时间内实现事件的概率 完成作业的时间估计：完成作业的时间估计：1 1、最乐观估计：、最乐观估计：a a2 2、最悲观估计：、最悲观估计：b b3 3、最可能估计：、最可能估计：m m完成作业的完成作业的期望时间及方差：期望时间及方差：2024/11/12 周二32例：书例：书 P190P190，例，例3 31 1、完成各项作业的期望时间和方差：、完成各项作业的期望时间和方差：2 2、假定每事件、假定每事件 k k 的最早完成时间服从的最早完成时间服从正态分布，正态分布，期望和方差是期望和方差是3 3、事件、事件 k k 在规定时间在规定时间 内完成的概率：内完成的概率：