运筹学基础及应用-第7章-计划评审技术和关键路线法

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