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

1、优 化 建 模7.4 计划评审方法和关键路线法 本节内容导航本节概述 7.4.1 计划网络图 7.4.2 计划网络图的计算 7.4.3 关键路线与计划网络图优化 7.4.4 完成作业期望和实现事件概率优 化 建 模本节内容概述计划评审方法（Program Evaluation and Review Technique, 简写为PERT）和关键路线法（Critial PathMethod, 简写为CPM）是网络分析的重要组成部分， 它广泛用系统分析和项目管理.计划评审与关键路线方 法是在20世纪50年代提出并发展起来的，1956年，美国 杜邦公司为了协调企业不同业务部门的系统规划，提出 了关键路线法.1958年，美国海军武装部在研制“北极星 ”导弹计划时，由于导弹的研制系统过于庞大、复杂， 为找到一种有效的管理方法，设计了计划评审方法.由 于PERT与CPM即有着相同的目标应用，又有很多相同 的术语，这两种方法已合并为一种方法，在国外称为 PERT/CPM，在国内称为统筹方法(Scheduling Method).返 回 导 航优 化 建 模7.4.1计划网络图例7.19 某项目工程由1

2、1项作业组成（分别用 代号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) 任何计划网络图应有唯一的最初事件和唯 一的最终事件

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.ltx min x8 - x1 subject to 2) x2 - x1 = 5 3) x3 - x1 = 10 4) x4 - x1 = 11 5) x5 - x2 = 4优 化 建 模6) x4 - x3 = 4 7) x5 - x3 = 0 8) x6 - x4 = 15 9)

4、 x6 - x5 = 21 10) x7 - x5 = 25 11) x8 - x5 = 35 12) x7 - x6 = 0 13) x8 - x6 = 20 14) x8 - x7 = 15 end优 化 建 模LINDO软件的计算结果如下：LP OPTIMUM FOUND AT STEP 9OBJECTIVE FUNCTION VALUE1) 51.00000VARIABLE VALUE REDUCED COSTX8 51.000000 0.000000X1 0.000000 0.000000X2 5.000000 0.000000X3 10.000000 0.000000X4 14.000000 0.000000X5 10.000000 0.000000X6 31.000000 0.000000X7 36.000000 0.000000优 化 建 模ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 0.0000003) 0.000000 -1.0000004) 3.000000 0.0000005) 1.000000 0.0000006)

5、0.000000 0.0000007) 0.000000 -1.0000008) 2.000000 0.0000009) 0.000000 -1.00000010) 1.000000 0.00000011) 6.000000 0.00000012) 5.000000 0.00000013) 0.000000 -1.00000014) 0.000000 0.000000NO. ITERATIONS= 9优 化 建 模计算结果给出了各个项目的开工时间，如 , 则 作业A、B、C的开工时间均是第0天; 作业E的开 工时间是第5天; 则作业D的开工时间是第10 天; 等等.每个作业只要按规定的时间开工，整个项 目的最短工期为51天.尽管上述LINDO程序给出相应的开工时间和整个项目的最短工期，但统筹方法中许多有用的信息并没 有得到，如项目的关键路径、每个作业的最早开工时 间、最迟开工时间等.因此，我们希望将程序编写的 稍微复杂一些，为我们提供更多的信息.优 化 建 模下面利用LINGO软件完成此项工作.例7.21 用LINGO软件求解例7.19.解： 按 照数 学规 划问题(7.37)-(7.

6、39) 编 写LINGO程序只有得到整 优 化 建 模编写相应的Lingo程序，程序名： exam0721.lg4MODEL:1sets:2 events/18/: x;3 operate(events, events)/4 1,2 1,3 1,4 3,4 2,5 3,5 4,6 5,6 5,8 5,7 6,7 7,8 6,85 /: s, t;6endsets7data:8 t = 5 10 11 4 4 0 15 21 35 25 0 15 20;9enddata10min=sum(events : x);11for(operate(i,j): s(i,j)=x(j)-x(i)-t(i,j);END优 化 建 模计算得到（只列出非零解）:Variable Value Reduced CostX( 2) 5.000000 0.000000X( 3) 10.00000 0.000000X( 4) 14.00000 0.000000X( 5) 10.00000 0.000000X( 6) 31.00000 0.000000X( 7) 35.00000 0.000000X( 8) 51.0

7、0000 0.000000S( 1, 4) 3.000000 0.000000S( 2, 5) 1.000000 0.000000S( 4, 6) 2.000000 0.000000S( 5, 8) 6.000000 0.000000S( 6, 7) 4.000000 0.000000S( 7, 8) 1.000000 0.000000优 化 建 模由此，可以得到所有作业的最早开工时间和最迟 开工时间，如表7-9所示，方括号中第1个数字是最早 开工时间，第2个数字是最迟开工时间.优 化 建 模优 化 建 模从上述表可以看出，当最早开工时间与最迟开 工时间相同时，对应的作业在关键路线上，因此可 以画出计划网络图中的关键路线，如图7-14粗线所 示.关键路线为 13568.优 化 建 模4 将关键路线看成最长路如果将关键路线看成最长路，则可以按照求最短 路的方法（将求极小改为求极大）求出关键路线 .设 为 变量，当作业 位于关键路线上取1;否则 取0. 数学规划问题写成:优 化 建 模例7.22 用最长路的方法求解例7.19. 解： 按数学规划(7.40)-(7.42)写出相应的 INGO

8、程序，程序名：exam0722.lg4.MODEL:1sets:2 events/18/: d;3 operate(events, events)/4 1,2 1,3 1,4 3,4 2,5 3,5 4,6 5,6 5,8 5,7 6,7 7,8 6,85 /: t, x;6endsets7data:优 化 建 模8 t = 5 10 11 4 4 0 15 21 35 25 0 15 20;9 d = 1 0 0 0 0 0 0 -1;10enddata11max=sum(operate : t*x);12for(events(i):13 sum(operate(i,j): x(i,j) - sum(operate(j,i): x(j,i)14 =d(i);15);END优 化 建 模计算得到（只列出非零解):Objective value: 51.00000Variable Value Reduced CostX( 1, 3) 1.000000 0.000000X( 3, 5) 1.000000 0.000000X( 5, 6) 1.000000 0.000000X( 6, 8) 1.000000 0.000000即工期需要51天，关键路线为13568.从

《计划评审方法和关键路线法》由会员wm****3分享，可在线阅读，更多相关《计划评审方法和关键路线法》请在金锄头文库上搜索。