《运筹学》课程教学课件（PPT讲稿）第七章 计划评审技术和关键路线法（Program Evaluation and Review Technique，Critical Path Method）

第七章计划评审技术和关键路线法 (Program Evaluation and Review Technique,Critical Path Method §1.PERT网络图 §2.PERT网络图的计算 §3.关键路线和网络计划的优化 §4.完成作业的期望时间和 在规定时间内实现事件的概率 2025/4/6

2025/4/6 2 第七章 计划评审技术和关键路线法 （Program Evaluation and Review Technique， Critical Path Method ） § 1． PERT 网络图 § 3．关键路线和网络计划的优化 § 4．完成作业的期望时间和 在规定时间内实现事件的概率 § 2． PERT 网络图的计算

网络计划技术：又称统筹法，是综合运用计划评审技术 和关键路线法的一种比较先进的计划管理方法。 口计划评审技术(PERT):是对计划项目进行核算、评 价，然后选定最优计划方案的一种技术。 能直观清晰的反映计划各部门或各项工作之间的相互联系和制 约； 反映某一部门或某项工作在全局中的地位和影响，便于发现薄 弱环节以采取措施； o关键路线法(CRM):是在计划项目的各项错综复杂的工 作中，抓住其中的关键路线进行计划安排的一种方法。研究 费用与工期的相互关系。 2025/4/6

2025/4/6 3 ◼ 网络计划技术：又称统筹法，是综合运用计划评审技术 和关键路线法的一种比较先进的计划管理方法。 ❑计划评审技术（PERT）：是对计划项目进行核算、评 价，然后选定最优计划方案的一种技术。 能直观清晰的反映计划各部门或各项工作之间的相互联系和制 约； 反映某一部门或某项工作在全局中的地位和影响，便于发现薄 弱环节以采取措施； ❑关键路线法（CRM）：是在计划项目的各项错综复杂的工 作中，抓住其中的关键路线进行计划安排的一种方法。研究 费用与工期的相互关系

§7.1 PERT 网络图 、 基本概念 1、作业：任何消耗时间或资源的行动。（箭线表示，（i,) 2、事件：作业开始或结束的标志。（圈中加数字或字母表示) 作业的起点事件、终点事件；，（切) 最初事件、最终事件（唯一)；紧前作业，紧后作业 注意：（事件本身不消耗时间或资源，或相对于作业，消耗量可忽略不计） 4h 1h 5h 3h 3h 2h 2h 2025/4/6

2025/4/6 4 §7.1 PERT 网络图 一、 基本概念 1、作业：任何消耗时间或资源的行动。（箭线表示，（i,j)) 2、事件：作业开始或结束的标志。（圈中加数字或字母表示） 作业的起点事件、终点事件； ，（i,j ) 最初事件、最终事件（唯一）； 紧前作业，紧后作业 注意:（事件本身不消耗时间或资源，或相对于作业，消耗量可忽略不计） 2 1 4 3 5 6 1h 4h 5h 2h 3h 3h 2h

3、路线：PERT网络图中由最初事件到最终事件的各项作 业连贯组成的一条路。 路的长度：完成该路上各项作业持续时间的长度和。 关键路线：由最初事件到最终事件的各项作业累计时间最 长的路。 路线1,2,5,6 8小时 路线1,3,5,6 11小时 关键路线 路线1,4,5,67小时 2025/4/6

2025/4/6 5 3、路线：PERT 网络图中由最初事件到最终事件的各项作 业连贯组成的一条路。 路的长度：完成该路上各项作业持续时间的长度和。 关键路线：由最初事件到最终事件的各项作业累计时间最 长的路。 路线1，2，5，6 8小时 路线1，3，5，6 11小时 关键路线 路线1，4，5，6 7小时

二、 建立PERT网络图的准则和注意事须 1、作业（1，j)用唯一箭线表示，起点事件（箭尾事件)编号 小于终点事件（箭头事件)的编号。 2、两个事件之间只能用一条箭线表示一项作业，具有相同开 始和结束的不同作业，需引进虚事件和虚作业。 】 5 2025/4/6

2025/4/6 6 二、建立 PERT 网络图的准则和注意事项 1、作业（i,j)用唯一箭线表示，起点事件（箭尾事件）编号 小于终点事件（箭头事件）的编号。 2、两个事件之间只能用一条箭线表示一项作业，具有相同开 始和结束的不同作业，需引进虚事件和虚作业。 2 1 5 1 5

3、各项作业间的几种关系及图上表示方法 (1)作业a结束后可以开始b,c: b a (2)作业c在a,b结束后才可以开始； (3)作业a,b结束后可以开始c,d； (4)作业c在a结束后即可以开始，d在a,b结束后才 可以开始。 a a b 5 2 3 6 (3) 3 5 虚箭线表示虚活动，不 消耗资源，不占用时间 6 2025/4/6

2025/4/6 7 3、各项作业间的几种关系及图上表示方法 （1）作业 a 结束后可以开始 b, c ； （2）作业 c 在 a,b 结束后才可以开始； （3）作业 a,b 结束后可以开始 c,d ； （4）作业 c 在 a 结束后即可以开始， d 在 a,b 结束后才 可以开始。 2 1 4 3 a b c 2 1 4 3 a b c 5 2 1 4 3 a b c d (1) (2) (3) 5 2 1 4 3 a b c d 6 (4) 虚箭线表示虚活动，不 消耗资源，不占用时间

4、PERT网络图中不允许出现回路。 5、PERT网络图的布局一般是从左到右，从上到下，尽量避 免箭线交叉。 6.PERT网络图中有唯一的最初事件和最终事件， 7.确定最初时间可以考虑没有紧前作业的多个事件拥有共同 的开始事件. 三、PERT网络图的合并与简化 若干局部网络图合并成一个大的全局网络图 合并后的网络图需简化 2025/4/6

2025/4/6 8 4、PERT 网络图中不允许出现回路。 5、PERT 网络图的布局一般是从左到右，从上到下，尽量避 免箭线交叉。 6. PERT 网络图中有唯一的最初事件和最终事件. 7.确定最初时间可以考虑没有紧前作业的多个事件拥有共同 的开始事件. 三、PERT 网络图的合并与简化 若干局部网络图合并成一个大的全局网络图 合并后的网络图需简化

四、 绘制PERT 网络图 作业 A B C D E F G H 紧前作业 AB B A C EF DF GH 作业时间 2 3 4 1 8 3 2 7 6 5 E 8 G B 8 3 2025/4/6 9

2025/4/6 9 3 E 1 2 4 6 7 3 8 5 A 2 B 8 C 4 D 1 L 5 F 3 H 7 G2 I 6 9 10 11 作业 A B C D E F G H I J 紧前作业 / / AB B A C EF DF GH I 作业时间 2 3 4 1 8 3 2 7 6 5 四、绘制 PERT 网络图

请做课后习题7.1b)(c)和P204-表7-1 自测 2025/4/6 o

请做课后习题7.1(b)(c)和P204-表7-1 自测 2025/4/6 10

§7.2 PERT网络图的计算 网络时间的计算 1.作业最早开始时间ts(位，)=max er(k,)} 作业最早结束时间 ter(i,j)=tes(i,j)+t(i,j) 2.作业最迟结束时间tF(亿，)=min{tzs(j,k)} 作业最迟开始时间 tis(i,j)=tir(i,j)-t(i,j) 2025/4/6 12

2025/4/6 12 §7.2 PERT 网络图的计算 一、网络时间的计算 t (i, j) t (i, j) t(i, j) EF = ES + 1.作业最早开始时间 作业最早结束时间 2.作业最迟结束时间 作业最迟开始时间 t (i, j) t (i, j) t(i, j) LS = LF − t (i, j) maxt EF (k,i) k E S = t (i, j) min t LS ( j, k) k LF =