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

《计划评审方法和关键路线法课件》由会员分享，可在线阅读，更多相关《计划评审方法和关键路线法课件（60页珍藏版）》请在金锄头文库上搜索。

1、优优 化化 建建 模模7.4 7.4 计划评审方法和关键路线法计划评审方法和关键路线法 本节内容导航本节内容导航 本节概述本节概述7.4.1计划网络图计划网络图7.4.2计划网络图的计算计划网络图的计算7.4.3关键路线与计划网络图优化关键路线与计划网络图优化7.4.4 完成作业期望和实现事件概率完成作业期望和实现事件概率计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模 本节内容概述本节内容概述 计划评审方法（计划评审方法（Program Evaluation and Review Technique, 简写为简写为PERT）和关键路线法（）和关键路线法（Critial

2、Path Method, 简写为简写为CPM）是网络分析的重要组成部分，）是网络分析的重要组成部分，它广泛用系统分析和项目管理它广泛用系统分析和项目管理.计划评审与关键路线方计划评审与关键路线方法是在法是在20世纪世纪50年代提出并发展起来的，年代提出并发展起来的，1956年，美国年，美国杜邦公司为了协调企业不同业务部门的系统规划，提出杜邦公司为了协调企业不同业务部门的系统规划，提出了关键路线法了关键路线法.1958年，美国海军武装部在研制年，美国海军武装部在研制“北极北极星星”导弹计划时，由于导弹的研制系统过于庞大、复杂，导弹计划时，由于导弹的研制系统过于庞大、复杂，为找到一种有效的管理方法

3、，设计了计划评审方法为找到一种有效的管理方法，设计了计划评审方法.由由于于PERT与与CPM即有着相同的目标应用，又有很多相同即有着相同的目标应用，又有很多相同的术语，这两种方法已合并为一种方法，在国外称为的术语，这两种方法已合并为一种方法，在国外称为PERT/CPM，在国内称为统筹方法，在国内称为统筹方法(Scheduling Method).返回导航计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模7.4.1计划网络图计划网络图 例例7.19 某项目工程由某项目工程由11项作业组成（分别用项作业组成（分别用代号代号A, B, , J, K表示），其计划完成时间及作业表示

4、），其计划完成时间及作业间相互关系如表间相互关系如表7-8所示，求完成该项目的最短时所示，求完成该项目的最短时间间.例例7.19就是计划评审方法或关键路线法需要解决的问题就是计划评审方法或关键路线法需要解决的问题.返回导航计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模1. 计划网络图的概念计划网络图的概念 定义定义 7.11 称任何消耗时间或资源的行动为作称任何消耗时间或资源的行动为作业业.称作业的开始或结束为事件，事件本身不消耗称作业的开始或结束为事件，事件本身不消耗资源资源. 在计划网络图中通常用圆圈表示事件，用箭在计划网络图中通常用圆圈表示事件，用箭线表示事件，如

5、图线表示事件，如图7-12所示，所示，1, 2, 3表示事件，表示事件，A, B表示作业表示作业.由这种方法画出的网络图称为计划由这种方法画出的网络图称为计划网络图网络图.计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模定义定义7.12 在计划网络图中，称从是初始事在计划网络图中，称从是初始事件到最终事件的由各项作业连贯组成的一条路为件到最终事件的由各项作业连贯组成的一条路为路线。具有累计作业时间最长的路线称为关键路路线。具有累计作业时间最长的路线称为关键路线。线。由此看来，例由此看来，例7.19就是求相应的计划网络图就是求相应的计划网络图中的关键路线。中的关键路线。2.

6、 建立计划网络图应注意的问题建立计划网络图应注意的问题(1) 任何作业在网络中用唯一的箭线表示，任何作业任何作业在网络中用唯一的箭线表示，任何作业其终点事件的编号必须大于其起点事件其终点事件的编号必须大于其起点事件.计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模 (2) 两个事件之间只能画一条箭线，表示一两个事件之间只能画一条箭线，表示一项作业项作业.对于具有相同开始和结束事件的两项以上对于具有相同开始和结束事件的两项以上作业，要引进虚事件和虚作业作业，要引进虚事件和虚作业.(3) 任何计划网络图应有唯一的最初事件和唯任何计划网络图应有唯一的最初事件和唯一的最终事件一的

7、最终事件.(4) 计划网络图不允许出现回路计划网络图不允许出现回路.(5) 计划网络图的画法一般是从左到右，从上计划网络图的画法一般是从左到右，从上到下，尽量作到清晰美观，避免箭头交叉到下，尽量作到清晰美观，避免箭头交叉.计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模7.4.2计划网络图的计算计划网络图的计算以例以例7-19的求解过程介绍计划网络图的计算的求解过程介绍计划网络图的计算方法方法.1. 建立计划网络图建立计划网络图首先建立计划网络图首先建立计划网络图.按照上述规则，建立例按照上述规则，建立例7.19的计划网络图，如图的计划网络图，如图7-13所示所示.返回导

8、航计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模2. 写出相应的规划问题写出相应的规划问题 设是事件的开始时间，设是事件的开始时间， 为最初事件，为为最初事件，为最终事件最终事件.希望总的工期最短，即极小化希望总的工期最短，即极小化 .设设是作业是作业 的计划时间，因此，对于事件的计划时间，因此，对于事件 与事件与事件 有不等式：有不等式： 由此得到相应的数学规划问题由此得到相应的数学规划问题计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模 3. 问题求解问题求解 例例7.20(继例继例7.19) 用用LINDO软件求解例软件求解例7.19 解：解

9、： 按照数学规划问题（按照数学规划问题（7.37）-（7.39）编写）编写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 =

10、2014) x8 - x7 = 15end计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模LINDO软件的计算结果如下：软件的计算结果如下：LP OPTIMUM FOUND AT STEP 9 OBJECTIVE FUNCTION VALUE 1) 51.00000 VARIABLE VALUE REDUCED COST X8 51.000000 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.0000

11、00 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.000000 -1.000000 8) 2.000000 0.000000 9) 0.000000 -1.000000 10) 1.000000 0.

12、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天天; 等等等等.每个作业只要按规定的时间开工，整个项每个作业只要

13、按规定的时间开工，整个项目的最短工期为目的最短工期为51天天. 尽管上述尽管上述LINDO程序给出相应的开工时间和整个程序给出相应的开工时间和整个项目的最短工期，但统筹方法中许多有用的信息并没项目的最短工期，但统筹方法中许多有用的信息并没有得到，如项目的关键路径、每个作业的最早开工时有得到，如项目的关键路径、每个作业的最早开工时间、最迟开工时间等间、最迟开工时间等.因此，我们希望将程序编写的因此，我们希望将程序编写的稍微复杂一些，为我们提供更多的信息稍微复杂一些，为我们提供更多的信息.计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模下面利用下面利用LINGO软件完成此项工

14、作软件完成此项工作.例例7.21 用用LINGO软件求解例软件求解例7.19. 解：解： 按按 照数照数 学规学规 划问题划问题(7.37)-(7.39) 编编 写写LINGO程序只有得程序只有得到整到整 计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模编写相应的编写相应的Lingo程序，程序名：程序，程序名： exam0721.lg4MODEL: 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,8 6,8 5 /: s,

15、 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.00000

16、0 X( 5) 10.00000 0.000000 X( 6) 31.00000 0.000000 X( 7) 35.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计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模 由此，可以

17、得到所有作业的最早开工时间和最迟由此，可以得到所有作业的最早开工时间和最迟开工时间，如表开工时间，如表7-9所示，方括号中第所示，方括号中第1个数字是最早个数字是最早开工时间，第开工时间，第2个数字是最迟开工时间个数字是最迟开工时间.计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模 从上述表可以看出，当最早开工时间与最迟开从上述表可以看出，当最早开工时间与最迟开工时间相同时，对应的作业在关键路线上，因此可工时间相同时，对应的作业在关键路线上，因此可以画出计划网络图中的关键路线，如图以画出计划网络图中的关

18、键路线，如图7-14粗线所粗线所示示.关键路线为关键路线为 13568.计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模4 将关键路线看成最长路将关键路线看成最长路 如果将关键路线看成最长路，则可以按照求最短如果将关键路线看成最长路，则可以按照求最短路的方法（将求极小改为求极大）求出关键路线路的方法（将求极小改为求极大）求出关键路线 .设为设为 变量，当作业变量，当作业 位于关键路线上取位于关键路线上取1;否则否则取取0. 数学规划问题写成数学规划问题写成:计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模例例7.22 用最长路的方法求解例用最长路的方

19、法求解例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 /: t, x; 6endsets 7data:计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模 8 t = 5 10 11 4 4 0 15 21 35 25 0 15 20; 9 d =

20、 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.0000

21、00 0.000000 X( 5, 6) 1.000000 0.000000 X( 6, 8) 1.000000 0.000000 即工期需要即工期需要51天，关键路线为天，关键路线为13568. 从上述计算过程可以看到，在两种从上述计算过程可以看到，在两种LINGO程序中，第二程序中，第二个程序计算在计算最短工期、关键路线均比第一个程序方便，个程序计算在计算最短工期、关键路线均比第一个程序方便，但在某些情况下，例如，需要优化计划网络时，第一种程序但在某些情况下，例如，需要优化计划网络时，第一种程序的编写方法可以更好地发挥出其优点的编写方法可以更好地发挥出其优点.计划评审方法和关键路线法计划评

22、审方法和关键路线法优优 化化 建建 模模7.4.3 关键路线与计划网络的优化关键路线与计划网络的优化 例例7.23 （关键路线与计划网络的优化）假设例（关键路线与计划网络的优化）假设例7.19中所列的工程要求在中所列的工程要求在49天内完成天内完成.为提前完成工为提前完成工期，有些作业需要加快进度、缩短工期，而加快进期，有些作业需要加快进度、缩短工期，而加快进度需要额外增加费用度需要额外增加费用.表表7-10列出例列出例7-19中可缩短工中可缩短工期的所有作业和缩短一天额外增加的费用期的所有作业和缩短一天额外增加的费用.现在的问现在的问题是，如何安排作业才能使额外增加的总费用最少题是，如何安排

23、作业才能使额外增加的总费用最少.返回导航计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模 例例7.23所涉及的问题就是计划网络的优化问题，所涉及的问题就是计划网络的优化问题，这时需要压缩关键路径来减少最短工期这时需要压缩关键路径来减少最短工期.计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模1. 计划网络优化的数学表达式计划网络优化的数学表达式 设设 是事件是事件 的开始时间，的开始时间， 是作业是作业 的计划时的计划时间间, 是完成作业是完成作业 的最短时间，的最短时间， 是作业是作业 可可能减少的时间，因此有能减少的时间，因此有 设设 是要求完成

24、的天数，是要求完成的天数， 为最初事件，为最初事件， 为最为最 终事件终事件,所以有所以有 而问题的总目标是使额外增而问题的总目标是使额外增加的费用最小，即目标函数为加的费用最小，即目标函数为 . 由此得到相应由此得到相应的数学规划问题的数学规划问题计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模2. 计划网络优化的求解计划网络优化的求解 例例7.24 用用LINDO软件求解例软件求解例7.23 解：解：按照数学规划问题按照数学规划问题(7.43)-(7.47)编写编写LINDO程序，程序名：程序，程序名：exam0724.ltx.计划评审方法和关键路线法计划评审方法和关

25、键路线法优优 化化 建建 模模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计划评审方法和关键

26、路线法计划评审方法和关键路线法优优 化化 建建 模模12) x7 - x6 = 013) x8 - x6 + y68 = 2014) x8 - x7 + y78 = 1515) x8 - x1 = 49endsub y13 2sub y14 3 sub y25 1sub y56 5sub y57 3sub y58 5sub y68 4sub y78 3计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模LINDO软件的计算结果如下：软件的计算结果如下：LP OPTIMUM FOUND AT STEP 23 OBJECTIVE FUNCTION VALUE 1) 1200.00

27、0 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.000000 Y78 0.000000 200.000000计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模 X2 5.000000 0.000000 X1 0.000000 0.000000 X3 9.

28、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.000000 0.000000计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模 6) 0.000000 0.000000

29、 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)压缩一天的工期，作业压缩一天的工期，作业(

30、6,8)(K)压压缩一天工期，这样可以在缩一天工期，这样可以在49天完工，需要多花费天完工，需要多花费1200元元. 如果需要知道压缩工期后的关键路径，则需要如果需要知道压缩工期后的关键路径，则需要稍复杂一点的计算稍复杂一点的计算. 例例7.25 用用LINGO软件求解例软件求解例7.23, 并求出相应并求出相应的关键路径、各作业的最早开工时间和最迟开工时的关键路径、各作业的最早开工时间和最迟开工时间间. 解：解： 为了得到作业的最早开工时间，仍在目标为了得到作业的最早开工时间，仍在目标函数中加入函数中加入 , 其他处理方法与前面相同其他处理方法与前面相同.计划评审方法和关键路线法计划评审方法

31、和关键路线法优优 化化 建建 模模写出相应的写出相应的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, c, y; 7endsets 8data: 9 t = 5 10 11 4 4 0 15 21 35 25 0 15 20;计划评审方法和关键路线法计划评审方法和

32、关键路线法优优 化化 建建 模模 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)-x(1)=d; 20for(operate:bn

33、d(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

34、X( 8) 49.00000 0.000000 S( 1, 4) 2.000000 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)减少一天，最小增加费用为减少一天，最小增加费用为12

35、00元元. 按照前面的方法，计算出所有作业的最早开工按照前面的方法，计算出所有作业的最早开工时间和最迟开工时间，见表时间和最迟开工时间，见表7-11所示所示.计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模 当最早开工时间与最迟开工时间相同时，对应当最早开工时间与最迟开工时间相同时，对应的作业就在关键路线上，图的作业就在关键路线上，图7-15中的粗线表示优化中的粗线表示优化后的关键路线后的关键路线.从图从图7-15可能看到，关键路线不只一可能看到，关键路线不只一条条.计划评审方法和关键路线法计划评审方法

36、和关键路线法优优 化化 建建 模模7.4.4 完成作业期望和实现事件的概率完成作业期望和实现事件的概率 在例在例7.19中，每项作业完成的时间均看成固定的中，每项作业完成的时间均看成固定的,但在实际应用中，每一作业的完成会受到一些意外但在实际应用中，每一作业的完成会受到一些意外因素的干扰，一般不可能是完全确定的，往往只能因素的干扰，一般不可能是完全确定的，往往只能凭借经验过去完成类似工作需要的时间来进行估计凭借经验过去完成类似工作需要的时间来进行估计.通常情况下，对完成一项作业可以给出三个时间上通常情况下，对完成一项作业可以给出三个时间上的估计值：最乐观的估计值（的估计值：最乐观的估计值（a）

37、，最悲观的估计值），最悲观的估计值(b)和最可能的估计值（和最可能的估计值（m）. 设设 完完成成作作业业 的的实实际际时时间间（是是一一随随机机变变量量），通常用下面的方法计算相应的数学期望与方差通常用下面的方法计算相应的数学期望与方差.返回导航计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模设设T为最短工期，即为最短工期，即:计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模由中心极限定理，可以假设由中心极限定理，可以假设T服从正态分布，并服从正态分布，并且期望值与方差满足且期望值与方差满足 设规定的工期为设规定的工期为d, 则在规定的工期内完成整

38、个则在规定的工期内完成整个项目的概率为项目的概率为:计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模 psn(x)是是LINGO软件提供了标准正态分布软件提供了标准正态分布函数（见第三章的函数（见第三章的3.3.7节），即节），即: 例例7.26 已知例已知例7.16中各项作业完成的三个估计中各项作业完成的三个估计时间，由表时间，由表7-12所示所示.如果规定时间为如果规定时间为52天，求在天，求在规定时间内完成全部作业的概率规定时间内完成全部作业的概率.进一步，如果完进一步，如果完成全部作业的概率大于等于成全部作业的概率大于等于95%，那么工期至少需，那么工期至少需要多

39、少天？要多少天？计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模 解：解：对于这个问题采用最长路的编写方法较为方对于这个问题采用最长路的编写方法较为方便便.计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模 公式（公式（7.48)和公式和公式(7.49)计算出各作业的期望计算出各作业的期望值与方差，再由期望时间计算出关键路线值与方差，再由期望时间计算出关键路线.从而由公从而由公式式(7.51)和公式和公式(7.52)得到关键路线的期望与方差得到关键路线的期望与方差的估计值，再利用分布函数的估计值，再利用分布函数 ,计算出完成作计算出完成作业的概率与完成

40、整个项目的时间业的概率与完成整个项目的时间. 写出相应的写出相应的LINGO程序，程序名：程序，程序名：xam0726.lg4.MODEL: 1sets: 2 events/1.8/: d; 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 /: a, m, b, et, dt, x; 7endsets 8data: 9 a = 3 8 8 2 3

41、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 limit = 52; 14enddata 15for(operate: 16 et = (a+4*m+b)/6; 17 dt = (b-a)2/36;8/1/20248/1/20244646计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模 18); 19max = Tbar; 20Tbar = sum(ope

42、rate: 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; END8/1/20248/1/20244747计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模 程序的第程序的第20行计算关键路径的时间数学期行计算关键路径的时间数学期 第第25行计行计算关键路径的时间方差算关键路

43、径的时间方差 , 第第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天

44、天完全部作业的概率为完全部作业的概率为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, 每

45、月分别进煤不小于每月分别进煤不小于60吨、吨、100吨吨, 它们担负供应三个居民区用煤任务它们担负供应三个居民区用煤任务, 这三个这三个居民区每月需用煤分别为居民区每月需用煤分别为45吨、吨、75吨和吨和40吨吨, A厂厂离这三居民区分别是离这三居民区分别是10公里、公里、5公里和公里和6公里公里, B厂厂离这三居民区分别为离这三居民区分别为4公里、公里、8公里和公里和15公里公里, 问这问这两煤厂如何分配供煤两煤厂如何分配供煤, 才使运量最小才使运量最小? 返回导航计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模 7.2 已知有已知有6个人（个人（1，2，3，4，5，6

46、），可以做），可以做6项工项工作作 ，每个人做每项工作的效率表，每个人做每项工作的效率表7-13所示所示.问：应如何安排每个人的工作，使总工作效率最大？问：应如何安排每个人的工作，使总工作效率最大？返回导航计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模 7.3 在图在图7-16中，中，A、B为发点，分别有为发点，分别有50和和40单位物资单位物资往外运，往外运，D、E为收点，分别需要物资为收点，分别需要物资30和和60单位，单位， C为中为中转点，图中括号的第一个数字为弧的容量，第二个数字为转点，图中括号的第一个数字为弧的容量，第二个数字为单位费用单位费用.求满足上述收

47、发条件的最小费用流求满足上述收发条件的最小费用流. 图 7-16返回导航计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模 7.4 求图求图7-17从到的最短路从到的最短路.图 7-17返回导航计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模 7.5 单位计划购买一台设备在今后单位计划购买一台设备在今后4年内使用年内使用.可以在可以在第一年初购买该设备，连续使用第一年初购买该设备，连续使用4年，也可以在任何一年年，也可以在任何一年末将设备卖掉，于下年初更换新设备末将设备卖掉，于下年初更换新设备.表表1-14和表和表7-15给出给出各年初购置新设备的价格

48、，设备的维护费，及卖掉旧设备各年初购置新设备的价格，设备的维护费，及卖掉旧设备的回收费的回收费.问如何确定设备的更新策略，使问如何确定设备的更新策略，使4年内的总费用年内的总费用最少？最少？表表 7-14 年初设备购置价格年初设备购置价格表表 7-15 设备维修和设备折旧费设备维修和设备折旧费返回导航计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模 7.6 求下列网络的最大流（见图求下列网络的最大流（见图7-18）.(a)(b)图 7-18返回导航计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模 7.7 求下列网络的最小费用最大流，其中括号中第一个求

49、下列网络的最小费用最大流，其中括号中第一个数字是容量，第二个数字是单位费用（见图数字是容量，第二个数字是单位费用（见图7-19）. 图图 7-19返回导航计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模 7.8 已知世界六大城市已知世界六大城市: 北京北京(B)、纽约、纽约(N)、巴黎、巴黎(P)、伦敦伦敦(L)、东京、东京(T)、墨西哥、墨西哥(M). 试由下表确定的交通网络试由下表确定的交通网络中确定最优生成树中确定最优生成树. 表表 7-16 单位单位:百英百英尺尺城市城市城市城市B BT TP PMMNNL LB B- -13135151777768685050T

50、 T1313- -6060707067675959P P51516060- -575736362 2MM777770705757- -20205555NN6868676736362020- -3434L L505059592 255553434- -返回导航计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模 7.9 已知世界六大城市已知世界六大城市: 北京北京(B)、纽约、纽约(N)、巴黎、巴黎(P)、伦敦伦敦(L)、东京、东京(T)、墨西哥、墨西哥(M).试由表试由表7-16确定的交通网络确定的交通网络中确定最优中确定最优Hamilton 回路回路. 7.10 某公司计划

51、推出一种新型产品，需要完成的作业某公司计划推出一种新型产品，需要完成的作业由由7-17所示所示.作业作业作业作业名称名称名称名称计划完成时计划完成时计划完成时计划完成时间间间间/ /周周周周紧前作业紧前作业紧前作业紧前作业最短完成时最短完成时最短完成时最短完成时间间间间/ /周周周周缩短缩短缩短缩短1 1周的费周的费周的费周的费用用用用/ /元元元元A A设计产品设计产品设计产品设计产品6 6- -4 4800800B B市场调查市场调查市场调查市场调查5 5- -3 3600600C C原材料定货原材料定货原材料定货原材料定货3 3A A1 1300300DD原材料收购原材料收购原材料收购原

52、材料收购2 2C C1 1600600E E建立产品设建立产品设建立产品设建立产品设计规范计规范计规范计规范3 3A,DA,D1 1400400F F产品广告宣产品广告宣产品广告宣产品广告宣传传传传2 2B B1 1300300G G建立产品生建立产品生建立产品生建立产品生产基地产基地产基地产基地4 4E E2 2200200HH产品运输到产品运输到产品运输到产品运输到库库库库2 2G,FG,F2 2- -表 7-17返回导航计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模 (1) 画出产品的计划网络图；画出产品的计划网络图； (2) 求完成新产品的最短时间，列出各项作业

53、的最早开求完成新产品的最短时间，列出各项作业的最早开始时间、最迟开始时间和计划网络的关键路线；始时间、最迟开始时间和计划网络的关键路线； (3) 假定现在距春节还有假定现在距春节还有12周，公司计划在春节期间推周，公司计划在春节期间推出该产品，各项作业的最短时间和缩短出该产品，各项作业的最短时间和缩短1周的费用由上表所周的费用由上表所示，求产品在春节上市的最小费用示，求产品在春节上市的最小费用; (4) 如果各项作业的完成时间并不能完全确定，而根据如果各项作业的完成时间并不能完全确定，而根据以往的经验估计出来的，其估计值如表以往的经验估计出来的，其估计值如表7-18所示。试计算所示。试计算出产

54、品在出产品在21周内上市的概率，和以周内上市的概率，和以95%的概率完成新产品的概率完成新产品上市所需的周数。上市所需的周数。返回导航计划评审方法和关键路线法计划评审方法和关键路线法优优 化化 建建 模模表表 7-18作业作业作业作业A AB BC CDDE EF FG GHH最乐观最乐观最乐观最乐观的的的的估估估估计计计计2 24 42 21 11 13 32 20 0最可能最可能最可能最可能的的的的估估估估计计计计6 65 53 32 23 34 44 42 2最悲观最悲观最悲观最悲观的的的的估估估估计计计计10106 64 43 35 55 56 64 4返回导航计划评审方法和关键路线法计划评审方法和关键路线法