《计划评审方法和关键路线法.ppt》由会员分享，可在线阅读，更多相关《计划评审方法和关键路线法.ppt（60页珍藏版）》请在三一办公上搜索。
1、7.4 计划评审方法和关键路线法,本节内容导航 本节概述计划网络图计划网络图的计算关键路线与计划网络图优化7.4.4 完成作业期望和实现事件概率,本节内容概述 计划评审方法（Program Evaluation and Review Technique,简写为PERT）和关键路线法（Critial Path Method,简写为CPM）是网络分析的重要组成部分，它广泛用系统分析和项目管理.计划评审与关键路线方法是在20世纪50年代提出并发展起来的，1956年，美国杜邦公司为了协调企业不同业务部门的系统规划，提出了关键路线法.1958年，美国海军武装部在研制“北极星”导弹计划时，由于导弹的研制系
2、统过于庞大、复杂，为找到一种有效的管理方法，设计了计划评审方法.由于PERT与CPM即有着相同的目标应用，又有很多相同的术语，这两种方法已合并为一种方法，在国外称为PERT/CPM，在国内称为统筹方法(Scheduling Method).,返回导航,计划网络图,例7.19 某项目工程由11项作业组成（分别用代号A,B,J,K表示），其计划完成时间及作业间相互关系如表7-8所示，求完成该项目的最短时间.,例7.19就是计划评审方法或关键路线法需要解决的问题.,返回导航,1.计划网络图的概念,定义 7.11 称任何消耗时间或资源的行动为作业.称作业的开始或结束为事件，事件本身不消耗资源.在计划网
3、络图中通常用圆圈表示事件，用箭线表示事件，如图7-12所示，1,2,3表示事件，A,B表示作业.由这种方法画出的网络图称为计划网络图.,定义7.12 在计划网络图中，称从是初始事件到最终事件的由各项作业连贯组成的一条路为路线。具有累计作业时间最长的路线称为关键路线。由此看来，例7.19就是求相应的计划网络图中的关键路线。,2.建立计划网络图应注意的问题,(1)任何作业在网络中用唯一的箭线表示，任何作业其终点事件的编号必须大于其起点事件.,(2)两个事件之间只能画一条箭线，表示一项作业.对于具有相同开始和结束事件的两项以上作业，要引进虚事件和虚作业.(3)任何计划网络图应有唯一的最初事件和唯一的
4、最终事件.(4)计划网络图不允许出现回路.(5)计划网络图的画法一般是从左到右，从上到下，尽量作到清晰美观，避免箭头交叉.,计划网络图的计算,以例7-19的求解过程介绍计划网络图的计算方法.1.建立计划网络图首先建立计划网络图.按照上述规则，建立例7.19的计划网络图，如图7-13所示.,返回导航,2.写出相应的规划问题,设是事件的开始时间，为最初事件，为最终事件.希望总的工期最短，即极小化.设是作业 的计划时间，因此，对于事件 与事件 有不等式：,由此得到相应的数学规划问题,3.问题求解,例7.20(继例7.19)用LINDO软件求解例7.19 解：按照数学规划问题（7.37）-（7.39）
5、编写INDO程序，程序名：,exam0720.ltxmin x8-x1subject to2)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软件的计算结果如下：,LP OPTIMUM FOUND AT STEP 9 OBJECTIVE FUNCTION VALUE 1)51.00000 VARIABLE VALUE REDUCED COST X8 51.000000
6、0.000000 X1 0.000000 0.000000 X2 5.000000 0.000000 X3 10.000000 0.000000 X4 14.000000 0.000000 X5 10.000000 0.000000 X6 31.000000 0.000000 X7 36.000000 0.000000,ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 0.000000 3)0.000000-1.000000 4)3.000000 0.000000 5)1.000000 0.000000 6)0.000000 0.000000 7)0.00
7、0000-1.000000 8)2.000000 0.000000 9)0.000000-1.000000 10)1.000000 0.000000 11)6.000000 0.000000 12)5.000000 0.000000 13)0.000000-1.000000 14)0.000000 0.000000 NO.ITERATIONS=9,计算结果给出了各个项目的开工时间，如,则作业A、B、C的开工时间均是第0天;作业E的开工时间是第5天;则作业D的开工时间是第10天;等等.每个作业只要按规定的时间开工，整个项目的最短工期为51天.,尽管上述LINDO程序给出相应的开工时间和整个项目的
8、最短工期，但统筹方法中许多有用的信息并没有得到，如项目的关键路径、每个作业的最早开工时间、最迟开工时间等.因此，我们希望将程序编写的稍微复杂一些，为我们提供更多的信息.,下面利用LINGO软件完成此项工作.,例7.21 用LINGO软件求解例7.19.,解：按 照数 学规 划问题(7.37)-(7.39)编 写LINGO程序只有得到整,编写相应的Lingo程序，程序名：exam0721.lg4,MODEL:1sets:2 events/1.8/: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,
9、8 6,8 5/:s,t;6endsets 7data:8 t=5 10 11 4 4 0 15 21 35 25 0 15 20;9enddata 10min=sum(events:x);11for(operate(i,j):s(i,j)=x(j)-x(i)-t(i,j);END,计算得到（只列出非零解）:Variable Value Reduced Cost X(2)5.000000 0.000000 X(3)10.00000 0.000000 X(4)14.00000 0.000000 X(5)10.00000 0.000000 X(6)31.00000 0.000000 X(7)35.
10、00000 0.000000 X(8)51.00000 0.000000 S(1,4)3.000000 0.000000 S(2,5)1.000000 0.000000 S(4,6)2.000000 0.000000 S(5,8)6.000000 0.000000 S(6,7)4.000000 0.000000 S(7,8)1.000000 0.000000,由此，可以得到所有作业的最早开工时间和最迟开工时间，如表7-9所示，方括号中第1个数字是最早开工时间，第2个数字是最迟开工时间.,从上述表可以看出，当最早开工时间与最迟开工时间相同时，对应的作业在关键路线上，因此可以画出计划网络图中的关键
11、路线，如图7-14粗线所示.关键路线为 13568.,4 将关键路线看成最长路,如果将关键路线看成最长路，则可以按照求最短路的方法（将求极小改为求极大）求出关键路线.,设为 变量，当作业 位于关键路线上取1;否则取0.数学规划问题写成:,例7.22 用最长路的方法求解例7.19.,解：按数学规划(7.40)-(7.42)写出相应的INGO程序，程序名：exam0722.lg4.,MODEL:1sets:2 events/1.8/: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,8 5/
12、:t,x;6endsets 7data:,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;10enddata 11max=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.00000 Variable Value Reduced Cost X(1,3)1.000000 0.000000 X(3,5)1.000000
13、0.000000 X(5,6)1.000000 0.000000 X(6,8)1.000000 0.000000,即工期需要51天，关键路线为13568.从上述计算过程可以看到，在两种LINGO程序中，第二个程序计算在计算最短工期、关键路线均比第一个程序方便，但在某些情况下，例如，需要优化计划网络时，第一种程序的编写方法可以更好地发挥出其优点.,7.4.3 关键路线与计划网络的优化,例7.23（关键路线与计划网络的优化）假设例7.19中所列的工程要求在49天内完成.为提前完成工期，有些作业需要加快进度、缩短工期，而加快进度需要额外增加费用.表7-10列出例7-19中可缩短工期的所有作业和缩短一
14、天额外增加的费用.现在的问题是，如何安排作业才能使额外增加的总费用最少.,返回导航,例7.23所涉及的问题就是计划网络的优化问题，这时需要压缩关键路径来减少最短工期.,1.计划网络优化的数学表达式,设 是事件 的开始时间，是作业 的计划时间,是完成作业 的最短时间，是作业 可能减少的时间，因此有,设 是要求完成的天数，为最初事件，为最 终事件,所以有 而问题的总目标是使额外增加的费用最小，即目标函数为.由此得到相应的数学规划问题,2.计划网络优化的求解,例7.24 用LINDO软件求解例7.23 解：按照数学规划问题(7.43)-(7.47)编写LINDO程序，程序名：exam0724.ltx
15、.,min 700 y13+400 y14+450 y25+600 y56+300 y57+500 y58+500 y68+400 y78 subject to2)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=49endsub y13 2sub y14 3 sub y25 1sub y56 5sub y5
16、7 3sub y58 5sub y68 4sub y78 3,LINDO软件的计算结果如下：,LP OPTIMUM FOUND AT STEP 23 OBJECTIVE FUNCTION VALUE 1)1200.000 VARIABLE VALUE REDUCED COST Y13 1.000000 0.000000 Y14 0.000000 400.000000 Y25 0.000000 450.000000 Y56 0.000000 100.000000 Y57 0.000000 100.000000 Y58 0.000000 500.000000 Y68 1.000000 0.0000
17、00 Y78 0.000000 200.000000,X2 5.000000 0.000000 X1 0.000000 0.000000 X3 9.000000 0.000000 X4 13.000000 0.000000 X5 9.000000 0.000000 X6 30.000000 0.000000 X7 34.000000 0.000000 X8 49.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 0.000000 3)0.000000-700.000000 4)2.000000 0.000000 5)0.00
18、0000 0.000000,6)0.000000 0.000000 7)0.000000-700.000000 8)2.000000 0.000000 9)0.000000-500.000000 10)0.000000-200.000000 11)5.000000 0.000000 12)4.000000 0.000000 13)0.000000-500.000000 14)0.000000-200.000000 15)0.000000 700.000000 NO.ITERATIONS=23,作业(1,3)(B)压缩一天的工期，作业(6,8)(K)压缩一天工期，这样可以在49天完工，需要多花费
19、1200元.如果需要知道压缩工期后的关键路径，则需要稍复杂一点的计算.,例7.25 用LINGO软件求解例7.23,并求出相应的关键路径、各作业的最早开工时间和最迟开工时间.解：为了得到作业的最早开工时间，仍在目标函数中加入,其他处理方法与前面相同.,写出相应的LINGO程序，程序名：exam0725.lg4.,MODEL:1sets:2 events/1.8/:x;3 operate(events,events)/4!A B C D E 0 F G H I 0 J K;5 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,8 6/:s,t,m
20、,c,y;7endsets 8data:9 t=5 10 11 4 4 0 15 21 35 25 0 15 20;,10 m=5 8 8 4 3 0 15 16 30 22 0 12 16;11 c=0 700 400 0 450 0 0 600 500 300 0 400 500;12 d=49;13enddata 14min=mincost+sumx;15mincost=sum(operate:c*y);16sumx=sum(events:x);17for(operate(i,j):s(i,j)=x(j)-x(i)+y(i,j)-t(i,j);18n=size(events);19x(n
21、)-x(1)=d;20for(operate:bnd(0,y,t-m);END,计算结果得到（只列出非零解）:,Variable Value Reduced Cost MINCOST 1200.000 0.000000 SUMX 149.0000 0.000000 X(2)5.000000 0.000000 X(3)9.000000 0.000000 X(4)13.00000 0.000000 X(5)9.000000 0.000000 X(6)30.00000 0.000000 X(7)34.00000 0.000000 X(8)49.00000 0.000000 S(1,4)2.00000
22、0 0.000000,S(4,6)2.000000 0.000000 S(5,8)5.000000 0.000000 S(6,7)4.000000 0.000000 Y(1,3)1.000000 0.000000 Y(6,8)1.000000 0.000000,计算结果与LINDO相同.作业(1,3)（B）减少一天,作业(6,8)(K)减少一天，最小增加费用为1200元.按照前面的方法，计算出所有作业的最早开工时间和最迟开工时间，见表7-11所示.,当最早开工时间与最迟开工时间相同时，对应的作业就在关键路线上，图7-15中的粗线表示优化后的关键路线.从图7-15可能看到，关键路线不只一条.,7
23、.4.4 完成作业期望和实现事件的概率,在例7.19中，每项作业完成的时间均看成固定的,但在实际应用中，每一作业的完成会受到一些意外因素的干扰，一般不可能是完全确定的，往往只能凭借经验过去完成类似工作需要的时间来进行估计.通常情况下，对完成一项作业可以给出三个时间上的估计值：最乐观的估计值（a），最悲观的估计值(b)和最可能的估计值（m）.,设 完成作业 的实际时间（是一随机变量），通常用下面的方法计算相应的数学期望与方差.,返回导航,设T为最短工期，即:,由中心极限定理，可以假设T服从正态分布，并且期望值与方差满足,设规定的工期为d,则在规定的工期内完成整个项目的概率为:,psn(x)是LI
24、NGO软件提供了标准正态分布函数（见第三章的节），即:,例7.26 已知例7.16中各项作业完成的三个估计时间，由表7-12所示.如果规定时间为52天，求在规定时间内完成全部作业的概率.进一步，如果完成全部作业的概率大于等于95%，那么工期至少需要多少天？,解：对于这个问题采用最长路的编写方法较为方便.,公式（7.48)和公式(7.49)计算出各作业的期望值与方差，再由期望时间计算出关键路线.从而由公式(7.51)和公式(7.52)得到关键路线的期望与方差的估计值，再利用分布函数,计算出完成作业的概率与完成整个项目的时间.写出相应的LINGO程序，程序名：xam0726.lg4.,MODEL:
25、1sets:2 events/1.8/:d;3 operate(events,events)/4!A B C D E 0 F G H I 0 J K;,46,5 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,8 6/:a,m,b,et,dt,x;7endsets 8data:9 a=3 8 8 2 3 0 8 18 26 18 0 12 11;10 m=5 9 11 4 4 0 16 20 33 25 0 15 21;11 b=7 16 14 6 5 0 18 28 52 32 0 18 25;12 d=1 0 0 0 0 0 0-1;13
26、 limit=52;14enddata 15for(operate:16 et=(a+4*m+b)/6;17 dt=(b-a)2/36;,47,18);19max=Tbar;20Tbar=sum(operate:et*x);21for(events(i):22 sum(operate(i,j):x(i,j)-sum(operate(j,i):x(j,i)23=d(i);24);25S2=sum(operate:dt*x);26p=psn(limit-Tbar)/S);27psn(days-Tbar)/S)=0.95;END,程序的第20行计算关键路径的时间数学期 第25行计算关键路径的时间方差
27、,第26行计算在规定时间内完成全部作业的概率,第 27行计算在95%概率完成全部作业的时间(days).,LINGO软件的计算结果（只列出非零解）如下：,Variable Value Reduced Cost TBAR 51.00000 0.000000 S 3.162276 0.000000 P 0.6240861 0.000000 DAYS 56.20148 0.000000,即关键路线的期望时间为51天，标准差为3.16，在52天完全部作业的概率为62.4%，如果在规定的工期内，完成全部作业的概率大于等于95%，那么工期至少需要56.2天.,习题 七,本节内容导航 习题:7.1 习题:7
28、.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项工作，每个人做每项工作的效率表7-13所示.问：应如何安排每个人的工作，使总工作效率最大？,返回导航,7.3 在图7-16中，A、B
29、为发点，分别有50和40单位物资往外运，D、E为收点，分别需要物资30和60单位，C为中转点，图中括号的第一个数字为弧的容量，第二个数字为单位费用.求满足上述收发条件的最小费用流.,图 7-16,返回导航,7.4 求图7-17从到的最短路.,图 7-17,返回导航,7.5 单位计划购买一台设备在今后4年内使用.可以在第一年初购买该设备，连续使用4年，也可以在任何一年末将设备卖掉，于下年初更换新设备.表1-14和表7-15给出各年初购置新设备的价格，设备的维护费，及卖掉旧设备的回收费.问如何确定设备的更新策略，使4年内的总费用最少？,表 7-14 年初设备购置价格,表 7-15 设备维修和设备折
30、旧费,返回导航,7.6 求下列网络的最大流（见图7-18）.,(a),(b),图 7-18,返回导航,7.7 求下列网络的最小费用最大流，其中括号中第一个数字是容量，第二个数字是单位费用（见图7-19）.,图 7-19,返回导航,7.8 已知世界六大城市:北京(B)、纽约(N)、巴黎(P)、伦敦(L)、东京(T)、墨西哥(M).试由下表确定的交通网络中确定最优生成树.,表 7-16 单位:百英尺,返回导航,7.9 已知世界六大城市:北京(B)、纽约(N)、巴黎(P)、伦敦(L)、东京(T)、墨西哥(M).试由表7-16确定的交通网络中确定最优Hamilton 回路.,7.10 某公司计划推出一种新型产品，需要完成的作业由7-17所示.,表 7-17,返回导航,(1)画出产品的计划网络图；(2)求完成新产品的最短时间，列出各项作业的最早开始时间、最迟开始时间和计划网络的关键路线；(3)假定现在距春节还有12周，公司计划在春节期间推出该产品，各项作业的最短时间和缩短1周的费用由上表所示，求产品在春节上市的最小费用;(4)如果各项作业的完成时间并不能完全确定，而根据以往的经验估计出来的，其估计值如表7-18所示。试计算出产品在21周内上市的概率，和以95%的概率完成新产品上市所需的周数。,返回导航,表 7-18,返回导航,
