计划评审方法和关键路线法.ppt

7 4计划评审方法和关键路线法 本节内容导航本节概述7 4 1计划网络图7 4 2计划网络图的计算7 4 3关键路线与计划网络图优化7 4 4完成作业期望和实现事件概率 本节内容概述计划评审方法 ProgramEvaluationandReviewTechnique 简写为PERT 和关键路线法 CritialPathMethod 简写为CPM 是网络分析的重要组成部分 它广泛用系统分析和项目管理 计划评审与关键路线方法是在20世纪50年代提出并发展起来的 1956年 美国杜邦公司为了协调企业不同业务部门的系统规划 提出了关键路线法 1958年 美国海军武装部在研制 北极星 导弹计划时 由于导弹的研制系统过于庞大 复杂 为找到一种有效的管理方法 设计了计划评审方法 由于PERT与CPM即有着相同的目标应用 又有很多相同的术语 这两种方法已合并为一种方法 在国外称为PERT CPM 在国内称为统筹方法 SchedulingMethod 返回导航 7 4 1计划网络图 例7 19某项目工程由11项作业组成 分别用代号A B J K表示 其计划完成时间及作业间相互关系如表7 8所示 求完成该项目的最短时间 例7 19就是计划评审方法或关键路线法需要解决的问题 返回导航 1 计划网络图的概念 定义7 11称任何消耗时间或资源的行动为作业 称作业的开始或结束为事件 事件本身不消耗资源 在计划网络图中通常用圆圈表示事件 用箭线表示事件 如图7 12所示 1 2 3表示事件 A B表示作业 由这种方法画出的网络图称为计划网络图 定义7 12在计划网络图中 称从是初始事件到最终事件的由各项作业连贯组成的一条路为路线 具有累计作业时间最长的路线称为关键路线 由此看来 例7 19就是求相应的计划网络图中的关键路线 2 建立计划网络图应注意的问题 1 任何作业在网络中用唯一的箭线表示 任何作业其终点事件的编号必须大于其起点事件 2 两个事件之间只能画一条箭线 表示一项作业 对于具有相同开始和结束事件的两项以上作业 要引进虚事件和虚作业 3 任何计划网络图应有唯一的最初事件和唯一的最终事件 4 计划网络图不允许出现回路 5 计划网络图的画法一般是从左到右 从上到下 尽量作到清晰美观 避免箭头交叉 7 4 2计划网络图的计算 以例7 19的求解过程介绍计划网络图的计算方法 1 建立计划网络图首先建立计划网络图 按照上述规则 建立例7 19的计划网络图 如图7 13所示 返回导航 2 写出相应的规划问题 设是事件的开始时间 为最初事件 为最终事件 希望总的工期最短 即极小化 设是作业的计划时间 因此 对于事件与事件有不等式 由此得到相应的数学规划问题 3 问题求解 例7 20 继例7 19 用LINDO软件求解例7 19解 按照数学规划问题 7 37 7 39 编写INDO程序 程序名 exam0720 ltxminx8 x1subjectto2 x2 x1 53 x3 x1 104 x4 x1 115 x5 x2 4 6 x4 x3 47 x5 x3 08 x6 x4 159 x6 x5 2110 x7 x5 2511 x8 x5 3512 x7 x6 013 x8 x6 2014 x8 x7 15end LINDO软件的计算结果如下 LPOPTIMUMFOUNDATSTEP9OBJECTIVEFUNCTIONVALUE1 51 00000VARIABLEVALUEREDUCEDCOSTX851 0000000 000000X10 0000000 000000X25 0000000 000000X310 0000000 000000X414 0000000 000000X510 0000000 000000X631 0000000 000000X736 0000000 000000 ROWSLACKORSURPLUSDUALPRICES2 0 0000000 0000003 0 000000 1 0000004 3 0000000 0000005 1 0000000 0000006 0 0000000 0000007 0 000000 1 0000008 2 0000000 0000009 0 000000 1 00000010 1 0000000 00000011 6 0000000 00000012 5 0000000 00000013 0 000000 1 00000014 0 0000000 000000NO ITERATIONS 9 计算结果给出了各个项目的开工时间 如 则作业A B C的开工时间均是第0天 作业E的开工时间是第5天 则作业D的开工时间是第10天 等等 每个作业只要按规定的时间开工 整个项目的最短工期为51天 尽管上述LINDO程序给出相应的开工时间和整个项目的最短工期 但统筹方法中许多有用的信息并没有得到 如项目的关键路径 每个作业的最早开工时间 最迟开工时间等 因此 我们希望将程序编写的稍微复杂一些 为我们提供更多的信息 下面利用LINGO软件完成此项工作 例7 21用LINGO软件求解例7 19 解 按照数学规划问题 7 37 7 39 编写LINGO程序只有得到整 编写相应的Lingo程序 程序名 exam0721 lg4 MODEL 1 sets 2 events 1 8 x 3 operate events events 4 1 21 31 43 42 53 54 65 65 85 76 77 86 85 s t 6 endsets7 data 8 t 510114401521352501520 9 enddata10 min sum events x 11 for operate i j s i j x j x i t i j END 计算得到 只列出非零解 VariableValueReducedCostX 2 5 0000000 000000X 3 10 000000 000000X 4 14 000000 000000X 5 10 000000 000000X 6 31 000000 000000X 7 35 000000 000000X 8 51 000000 000000S 1 4 3 0000000 000000S 2 5 1 0000000 000000S 4 6 2 0000000 000000S 5 8 6 0000000 000000S 6 7 4 0000000 000000S 7 8 1 0000000 000000 由此 可以得到所有作业的最早开工时间和最迟开工时间 如表7 9所示 方括号中第1个数字是最早开工时间 第2个数字是最迟开工时间 从上述表可以看出 当最早开工时间与最迟开工时间相同时 对应的作业在关键路线上 因此可以画出计划网络图中的关键路线 如图7 14粗线所示 关键路线为1 3 5 6 8 4将关键路线看成最长路 如果将关键路线看成最长路 则可以按照求最短路的方法 将求极小改为求极大 求出关键路线 设为变量 当作业位于关键路线上取1 否则取0 数学规划问题写成 例7 22用最长路的方法求解例7 19 解 按数学规划 7 40 7 42 写出相应的INGO程序 程序名 exam0722 lg4 MODEL 1 sets 2 events 1 8 d 3 operate events events 4 1 21 31 43 42 53 54 65 65 85 76 77 86 85 t x 6 endsets7 data 8 t 510114401521352501520 9 d 1000000 1 10 enddata11 max sum operate t x 12 for events i 13 sum operate i j x i j sum operate j i x j i 14 d i 15 END 计算得到 只列出非零解 Objectivevalue 51 00000VariableValueReducedCostX 1 3 1 0000000 000000X 3 5 1 0000000 000000X 5 6 1 0000000 000000X 6 8 1 0000000 000000 即工期需要51天 关键路线为1 3 5 6 8 从上述计算过程可以看到 在两种LINGO程序中 第二个程序计算在计算最短工期 关键路线均比第一个程序方便 但在某些情况下 例如 需要优化计划网络时 第一种程序的编写方法可以更好地发挥出其优点 7 4 3关键路线与计划网络的优化 例7 23 关键路线与计划网络的优化 假设例7 19中所列的工程要求在49天内完成 为提前完成工期 有些作业需要加快进度 缩短工期 而加快进度需要额外增加费用 表7 10列出例7 19中可缩短工期的所有作业和缩短一天额外增加的费用 现在的问题是 如何安排作业才能使额外增加的总费用最少 返回导航 例7 23所涉及的问题就是计划网络的优化问题 这时需要压缩关键路径来减少最短工期 1 计划网络优化的数学表达式 设是事件的开始时间 是作业的计划时间 是完成作业的最短时间 是作业可能减少的时间 因此有 设是要求完成的天数 为最初事件 为最终事件 所以有而问题的总目标是使额外增加的费用最小 即目标函数为 由此得到相应的数学规划问题 2 计划网络优化的求解 例7 24用LINDO软件求解例7 23解 按照数学规划问题 7 43 7 47 编写LINDO程序 程序名 exam0724 ltx min700y13 400y14 450y25 600y56 300y57 500y58 500y68 400y78subjectto2 x2 x1 53 x3 x1 y13 104 x4 x1 y14 115 x5 x2 y25 46 x4 x3 47 x5 x3 08 x6 x4 159 x6 x5 y56 2110 x7 x5 y57 2511 x8 x5 y58 35 12 x7 x6 013 x8 x6 y68 2014 x8 x7 y78 1515 x8 x1 49endsuby132suby143suby251suby565suby573suby585suby684suby783 LINDO软件的计算结果如下 LPOPTIMUMFOUNDATSTEP23OBJECTIVEFUNCTIONVALUE1 1200 000VARIABLEVALUEREDUCEDCOSTY131 0000000 000000Y140 000000400 000000Y250 000000450 000000Y560 000000100 000000Y570 000000100 000000Y580 000000500 000000Y681 0000000 000000Y780 000000200 000000 X25 0000000 000000X10 0000000 000000X39 0000000 000000X413 0000000 000000X59 0000000 000000X630 0000000 000000X734 0000000 000000X849 0000000 000000ROWSLACKORSURPLUSDUALPRICES2 0 0000000 0000003 0 000000 700 0000004 2 0000000 0000005 0 0000000 000000 6 0 0000000 0000007 0 000000 700 0000008 2 0000000 0000009 0 000000 500 00000010 0 000000 200 00000011 5 0000000 00000012 4 0000000 00000013 0 000000 500 00000014 0 000000 200 00000015 0 000000700 000000NO ITERATIONS 23 作业 1 3 B 压缩一天的工期 作业 6 8 K 压缩一天工期 这样可以在49天完工 需要多花费1200元 如果需要知道压缩工期后的关键路径 则需要稍复杂一点的计算 例7 25用LINGO软件求解例7 23 并求出相应的关键路径 各作业的最早开工时间和最迟开工时间 解 为了得到作业的最早开工时间 仍在目标函数中加入 其他处理方法与前面相同 写出相应的LINGO程序 程序名 exam0725 lg4 MODEL 1 sets 2 events 1 8 x 3 operate events events 4 ABCDE0FGHI0JK 5 1 21 31 43 42 53 54 65 65 85 76 77 86 86 s t m c y 7 endsets8 data 9 t 510114401521352501520 10 m 5884301516302201216 11 c 07004000450006005003000400500 12 d 49 13 enddata14 min mincost sumx 15 mincost sum operate c y 16 sumx sum events x 17 for operate i j s i j x j x i y i j t i j 18 n size events 19 x n x 1 d 20 for operate bnd 0 y t m END 计算结果得到 只列出非零解 VariableValueReducedCostMINCOST1200 0000 000000SUMX149 00000 000000X 2 5 0000000 000000X 3 9 0000000 000000X 4 13 000000 000000X 5 9 0000000 000000X 6 30 000000 000000X 7 34 000000 000000X 8 49 000000 000000S 1 4 2 0000000 000000 S 4 6 2 0000000 000000S 5 8 5 0000000 000000S 6 7 4 0000000 000000Y 1 3 1 0000000 000000Y 6 8 1 0000000 000000 计算结果与LINDO相同 作业 1 3 B 减少一天 作业 6 8 K 减少一天 最小增加费用为1200元 按照前面的方法 计算出所有作业的最早开工时间和最迟开工时间 见表7 11所示 当最早开工时间与最迟开工时间相同时 对应的作业就在关键路线上 图7 15中的粗线表示优化后的关键路线 从图7 15可能看到 关键路线不只一条 7 4 4完成作业期望和实现事件的概率 在例7 19中 每项作业完成的时间均看成固定的 但在实际应用中 每一作业的完成会受到一些意外因素的干扰 一般不可能是完全确定的 往往只能凭借经验过去完成类似工作需要的时间来进行估计 通常情况下 对完成一项作业可以给出三个时间上的估计值 最乐观的估计值 a 最悲观的估计值 b 和最可能的估计值 m 设完成作业的实际时间 是一随机变量 通常用下面的方法计算相应的数学期望与方差 返回导航 设T为最短工期 即 由中心极限定理 可以假设T服从正态分布 并且期望值与方差满足 设规定的工期为d 则在规定的工期内完成整个项目的概率为 psn x 是LINGO软件提供了标准正态分布函数 见第三章的3 3 7节 即 例7 26已知例7 16中各项作业完成的三个估计时间 由表7 12所示 如果规定时间为52天 求在规定时间内完成全部作业的概率 进一步 如果完成全部作业的概率大于等于95 那么工期至少需要多少天 解 对于这个问题采用最长路的编写方法较为方便 公式 7 48 和公式 7 49 计算出各作业的期望值与方差 再由期望时间计算出关键路线 从而由公式 7 51 和公式 7 52 得到关键路线的期望与方差的估计值 再利用分布函数 计算出完成作业的概率与完成整个项目的时间 写出相应的LINGO程序 程序名 xam0726 lg4 MODEL 1 sets 2 events 1 8 d 3 operate events events 4 ABCDE0FGHI0JK 2020 1 16 46 5 1 21 31 43 42 53 54 65 65 85 76 77 86 86 a m b et dt x 7 endsets8 data 9 a 388230818261801211 10 m 59114401620332501521 11 b 716146501828523201825 12 d 1000000 1 13 limit 52 14 enddata15 for operate 16 et a 4 m b 6 17 dt b a 2 36 2020 1 16 47 18 19 max Tbar 20 Tbar sum operate et x 21 for events i 22 sum operate i j x i j sum operate j i x j i 23 d i 24 25 S 2 sum operate dt x 26 p psn limit Tbar S 27 psn days Tbar S 0 95 END 程序的第20 行计算关键路径的时间数学期第25 行计算关键路径的时间方差 第26 行计算在规定时间内完成全部作业的概率 第27 行计算在95 概率完成全部作业的时间 days LINGO软件的计算结果 只列出非零解 如下 VariableValueReducedCostTBAR51 000000 000000S3 1622760 000000P0 62408610 000000DAYS56 201480 000000 即关键路线的期望时间为51天 标准差为3 16 在52天完全部作业的概率为62 4 如果在规定的工期内 完成全部作业的概率大于等于95 那么工期至少需要56 2天 习题七 本节内容导航习题 7 1习题 7 2习题 7 3习题 7 4习题 7 5习题 7 6习题 7 7习题 7 8习题 7 9习题 7 10 7 1有两个煤厂A B 每月分别进煤不小于60吨 100吨 它们担负供应三个居民区用煤任务 这三个居民区每月需用煤分别为45吨 75吨和40吨 A厂离这三居民区分别是10公里 5公里和6公里 B厂离这三居民区分别为4公里 8公里和15公里 问这两煤厂如何分配供煤 才使运量最小 返回导航 7 2已知有6个人 1 2 3 4 5 6 可以做6项工作 每个人做每项工作的效率