数学建模社区-数学中国

标题: 计划评审方法和关键路线法【PERT/CPM、统筹方法】 [打印本页]

作者: 浅夏110 时间: 2020-5-20 17:34
标题: 计划评审方法和关键路线法【PERT/CPM、统筹方法】
计划评审方法（program evaluation and review technique, PERT）和关键路线法（critical path method, CPM）是网络分析的重要组成部分，它广泛地用于系统分析和项目管理。计划评审与关键路线方法是在 20 世纪 50 年代提出并发展起来的，1956 年，美国杜邦公司为了协调企业不同业务部门的系统规划，提出了关键路线法。1958 年，美国海军武装部在研制“北极星”导弹计划时，由于导弹的研制系统过于庞大、复杂，为找到一种有效的管理方法，设计了计划评审方法。由于 PERT 与 CPM 既有着相同的目标应用，又有很多相同的术语，这两种方法已合并为一种方法，在国外称为 PERT/CPM，在国内称为统筹方法（scheduling method）。

1 计划网络图
例 20 某项目工程由 11 项作业组成（分别用代号 A, B,...., J , K 表示），其计划完成时间及作业间相互关系如表 9 所示，求完成该项目的最短时间。

例 20 就是计划评审方法或关键路线法需要解决的问题。

1.1 计划网络图的概念
【定义】称任何消耗时间或资源的行动称为作业。称作业的开始或结束为事件，事件本身不消耗资源。在计划网络图中通常用圆圈表示事件，用箭线表示工作，如图 9 所示，1，2，3 表示事件， A, B 表示作业。由这种方法画出的网络图称为计划网络图。

虚工作用虚箭线“”表示。它表示工时为零，不消耗任何资源的虚构工作。其作用只是为了正确表示工作的前行后继关系。定义在计划网络图中，称从初始事件到最终事件的由各项工作连贯组成的一条路为路线。具有累计作业时间最长的路线称为关键路线。

由此看来，例 20 就是求相应的计划网络图中的关键路线。

1.2 建立计划网络图应注意的问题
（1）任何作业在网络中用唯一的箭线表示，任何作业其终点事件的编号必须大于其起点事件。

（2）两个事件之间只能画一条箭线，表示一项作业。对于具有相同开始和结束事件的两项以上的作业，要引进虚事件和虚作业。

（3）任何计划网络图应有唯一的最初事件和唯一的最终事件。

（4）计划网络图不允许出现回路。

（5）计划网络图的画法一般是从左到右，从上到下，尽量作到清晰美观，避免箭头交叉。

2 时间参数
2.1 事件时间参数
（1）事件的最早时间
事件 j 的最早时间用表示，它表明以它为始点的各工作最早可能开始的时间，也表示以它为终点的各工作的最早可能完成时间，它等于从始点事件到该事件的最长路线上所有工作的工时总和。事件最早时间可用下列递推公式，按照事件编号从小到大的顺序逐个计算。

设事件编号为1,2,..., n ，则

其中 $t_E (i)$ 是与事件 j 相邻的各紧前事件的最早时间，t(i, j) 是作业(i, j) 所需的工时。终点事件的最早时间显然就是整个工程的总最早完工期，即

= 总最早完工期（7）

（2）事件的最迟时间
事件i 的最迟时间用表示，它表明在不影响任务总工期条件下，以它为始点的工作的最迟必须开始时间，或以它为终点的各工作的最迟必须完成时间。由于一般情况下，我们都把任务的最早完工时间作为任务的总工期，所以事件最迟时间的计算公式为：

其中是与事件i 相邻的各紧后事件的最迟时间。

公式（8）也是递推公式，但与（6）相反，是从终点事件开始，按编号由大至小的顺序逐个由后向前计算。

2.2 工作的时间参数
（1）工作的最早可能开工时间与工作的最早可能完工时间
一个工作(i, j) 的最早可能开工时间用表示。任何一件工作都必须在其所有紧前工作全部完工后才能开始。

工作(i, j) 的最早可能完工时间用表示。它表示工作按最早开工时间开始所能达到的完工时间。它们的计算公式为：

这组公式也是递推公式。即所有从总开工事件出发的工作(1, j)，其最早可能开工时间为零；任一工作(i, j) 的最早开工时间要由它的所有紧前工作(k,i) 的最早开工时间决定；工作(i, j) 的最早完工时间显然等于其最早开工时间与工时之和。

（2）工作的最迟必须开工时间与工作的最迟必须完工时间
一个工作(i, j) 的最迟开工时间用表示。它表示工作(i, j) 在不影响整个任务如期完成的前提下，必须开始的最晚时间。

工作(i, j) 的最迟必须完工时间用表示。它表示工作(i, j) 按最迟时间开工，所能达到的完工时间。它们的计算公式为：

这组公式是按工作的最迟必须开工时间由终点向始点逐个递推的公式。凡是进入总完工事件 n 的工作(i, n) ，其最迟完工时间必须等于预定总工期或等于这个工作的最早可能完工时间。任一工作(i, j) 的最迟必须开工时间由它的所有紧后工作( j, k) 的最迟开工时间确定。而工作(i, j) 的最迟完工时间显然等于本工作的最迟开工时间与工时的和。

由于任一个事件i （除去始点事件和终点事件），既表示某些工作的开始又表示某些工作的结束。所以从事件与工作的关系考虑，用公式（9），公式（10）求得的有关工作的时间参数也可以通过事件的时间参数公式（6），公式（8）来计算。如工作(i, j) 的最早可能开工时间 $t_{ ES} (i, j)$ 就等于事件i 的最早时间。工作(i, j) 的最迟必须完工时间等于事件 j 的最迟时间。

2.3 时差
工作的时差又叫工作的机动时间或富裕时间，常用的时差有两种。

（1）工作的总时差
在不影响任务总工期的条件下，某工作(i, j) 可以延迟其开工时间的最大幅度，叫做该工作的总时差，用 R(i, j) 表示。其计算公式为：

即工作(i, j) 的总时差等于它的最迟完工时间与最早完工时间的差。显然 R(i, j) 也等于该工作的最迟开工时间与最早开工时间之差。

（2）工作的单时差
工作的单时差是指在不影响紧后工作的最早开工时间条件下，此工作可以延迟其开工时间的最大幅度，用 r(i, j) 表示。其计算公式为：

即单时差等于其紧后工作的最早开工时间与本工作的最早完工时间之差。

3 计划网络图的计算
以例 20 的求解过程为例介绍计划网络图的计算方法。

3.1 建立计划网络图
首先建立计划网络图。按照上述规则，建立例 20 的计划网络图，如图 10 所示。

3.2 写出相应的规划问题

3.3 问题求解
用 LINGO 软件求解例 20。编写 LINGO 程序如下：

model:
sets:
events/1..8/:x;
operate(events,events)/1 2,1 3,1 4,2 5,3 4,3 5,4 6,5 6,
5 7,5 8,6 7,6 8,7 8/:t;
endsets
data:
t=5 10 11 4 4 0 15 21 25 35 0 20 15;
enddata
min=x(8)-x(1);
@for(operate(i,j):x(j)>x(i)+t(i,j));
end

计算结果给出了各个项目的开工时间，如 x1 = 0 ，则作业 A, B,C 的开工时间均是第 0 天； x2 = 5，作业 E 的开工时间是第 5 天； x3 = 10，则作业 D 的开工时间是第 10 天；等等。每个作业只要按规定的时间开工，整个项目的最短工期为 51 天。

尽管上述 LINGO 程序给出相应的开工时间和整个项目的最短工期，但统筹方法中许多有用的信息并没有得到，如项目的关键路径、每个作业的最早开工时间、最迟开工时间等。

例 21（续例 20）求例 20 中每个作业的最早开工时间、最迟开工时间和作业的关键路径。

编写 LINGO 程序如下：

model:
sets:
events/1..8/:x,z;
operate(events,events)/1 2,1 3,1 4,2 5,3 4,3 5,4 6,5 6,
5 7,5 8,6 7,6 8,7 8/:s,t,m,c,y;
endsets
data:
t=5 10 11 4 4 0 15 21 25 35 0 20 15;
m=5 8 8 3 4 0 15 16 22 30 0 16 12;
c=0 700 400 450 0 0 0 600 300 500 0 500 400;
d=49;
@text(txt2.txt)=x,z;
enddata
min=mincost+sumx;
mincost=@sum(operate:c*y);
sumx=@sum(events:x);
@for(operate(i,j):s(i,j)=x(j)-x(i)+y(i,j)-t(i,j));
n=@size(events);
x(1)=0;
x(n)<d;
@for(operate

bnd(0,y,t-m));
z(n)=x(n);
@for(events(i)|i#lt#n:z(i)=@min(operate(i,j):z(j)-t(i,j)+y(i,j)));
end

最迟开工时间的分析需要用到松弛变量 sij ，当 sij > 0时，说明还有剩余时间，对应作业的工期可以推迟 sij 。例如，s78 = 1，作业（7，8）（ J ）的开工时间可以推迟 1 天，即开工时间为 36。再如 s46 = 2 ，作业（4，6）（ F ）可以推迟 2 天开始， 3 s14 = ，作业（1，4）（C ）可以推迟 3 天开始，但由于作业（4，6）（ F ）已能够推迟 2 天，所以，作业（1，4）（C ）最多可推迟 5 天。由此，可以得到所有作业的最早开工时间和最迟开工时间，如下表所示，方括号中第 1 个数字是最早开工时间，第 2 个数字是最迟开工时间。

从上表可以看出，当最早开工时间与最迟开工时间相同时，对应的作业在关键路线上，因此可以画出计划网络图中的关键路线，如图 11 粗线所示。关键路线为 1→3→ 5→6→8。

3.4 将关键路线看成最长路

如果将关键路线看成最长路，则可以按照求最短路的方法（将求极小改为求极大）求出关键路线。

例 22 用最长路的方法，求解例 20。按上述数学规划问题写出相应的 LINGO 程序。

model:
sets:
events/1..8/:d;
operate(events,events)/1 2,1 3,1 4,2 5,3 4,3 5,4 6,5 6,
5 7,5 8,6 7,6 8,7 8/:t,x;
endsets
data:
t=5 10 11 4 4 0 15 21 25 35 0 20 15;
d=1 0 0 0 0 0 0 -1;
enddata
max=@sum(operate:t*x);
@for(events(i)

sum(operate(i,j):x(i,j))-@sum(operate(j,i):x(j,i))=d(i));
end

得工期需要 51 天，关键路线为 1→3→5→6→8。

4 关键路线与计划网络的优化
例 23（关键路线与计划网络的优化）假设例 20 中所列的工程要求在 49 天内完成。为提前完成工程，有些作业需要加快进度，缩短工期，而加快进度需要额外增加费用。下表列出例 20 中可缩短工期的所有作业和缩短一天工期额外增加的费用。现在的问题是，如何安排作业才能使额外增加的总费用最少。

例 23 所涉及的问题就是计划网络的优化问题，这时需要压缩关键路径来减少最短工期。

4.1 计划网络优化的数学表达式

4.2 计划网络优化的求解

用 LINGO 软件求解例 23，程序如下：

model:
sets:
events/1..8/:x;
operate(events,events)/1 2,1 3,1 4,2 5,3 4,3 5,4 6,5 6,
5 7,5 8,6 7,6 8,7 8/:t,m,c,y;
endsets
data:
t=5 10 11 4 4 0 15 21 25 35 0 20 15;
m=5 8 8 3 4 0 15 16 22 30 0 16 12;
c=0 700 400 450 0 0 0 600 300 500 0 500 400;
d=49;
enddata
min=@sum(operate:c*y);
@for(operate(i,j):x(j)-x(i)+y(i,j)>t(i,j));
n=@size(events);
x(n)-x(1)<d;
@for(operate

bnd(0,y,t-m));
end

作业(1,3)(B) 压缩 1 天的工期，作业(6,8)(K) 压缩 1 天工期，这样可以在 49 天完工，需要多花费 1200 元。如果需要知道压缩工期后的关键路径，则需要稍复杂一点的计算。

例 24 （续例 23）用 LINGO 软件求解例 23，并求出相应的关键路径、各作业的最早开工时间和最迟开工时间。解为了得到作业的最早开工时间，仍在目标函数中加入，记 zi 表示事件i 的最迟开工时间，其它处理方法与前面相同。写出相应的 LINGO 程序如下：

model:
sets:
events/1..8/:x,z;
operate(events,events)/1 2,1 3,1 4,2 5,3 4,3 5,4 6,5 6,
5 7,5 8,6 7,6 8,7 8/:s,t,m,c,y;
endsets
data:
t=5 10 11 4 4 0 15 21 25 35 0 20 15;
m=5 8 8 3 4 0 15 16 22 30 0 16 12;
c=0 700 400 450 0 0 0 600 300 500 0 500 400;
d=49;
@text(txt2.txt)=x,z;
enddata
min=mincost+sumx;
mincost=@sum(operate:c*y);
sumx=@sum(events:x);
@for(operate(i,j):s(i,j)=x(j)-x(i)+y(i,j)-t(i,j));
n=@size(events);
x(1)=0;
x(n)<d;
@for(operate

bnd(0,y,t-m));
z(n)=x(n);
@for(events(i)|i#lt#n:z(i)=@min(operate(i,j):z(j)-t(i,j)+y(i,j)));
end

计算出所有作业的最早开工时间和最迟开工时间，见表 12。

当最早开工时间与最迟开工时间相同时，对应的作业就在关键路线上，图 12 中的粗线表示优化后的关键路线。从图 5-10 可以看到，关键路线不止一条。

5 完成作业期望和实现事件的概率
在例 20 中，每项作业完成的时间均看成固定的，但在实际应用中，每一工作的完成会受到一些意外因素的干扰，一般不可能是完全确定的，往往只能凭借经验和过去完成类似工作需要的时间进行估计。通常情况下，对完成一项作业可以给出三个时间上的估计值：最乐观值的估计值（ a ），最悲观的估计值（b ）和最可能的估计值（ m ）。

设是完成作业(i, j) 的实际时间（是一随机变量），通常用下面的方法计算相应的数学期望和方差。

例 25 已知例 20 中各项作业完成的三个估计时间如下表所示。如果规定时间为 52 天，求在规定时间内完成全部作业的概率。进一步，如果完成全部作业的概率大于等于 95％，那么工期至少需要多少天？

解对于这个问题采用最长路的编写方法。按公式（13）和公式（14）计算出各作业的期望值与方差，再由期望时间计算出关键路线。从而由公式（16）和公式（17）得到关键路线的期望与方差的估计值，再利用分布函数@psn(x)，计算出完成作业的概率与完成整个项目的时间。写出相应的 LINGO 程序如下：

model:
sets:
events/1..8/:d;
operate(events,events)/1 2,1 3,1 4,2 5,3 4,3 5,4 6,5 6,
5 7,5 8,6 7,6 8,7 8/:a,m,b,et,dt,x;
endsets
data:
a=3 8 8 3 2 0 8 18 18 26 0 11 12;
m= 5 9 11 4 4 0 16 20 25 33 0 21 15;
b=7 16 14 5 6 0 18 28 32 52 0 25 18;
d=1 0 0 0 0 0 0 -1;
limit=52;
enddata
@for(operate:et=(a+4*m+b)/6;dt=(b-a)^2/36);
max=tbar;
tbar=@sum(operate:et*x);
@for(events(i)

sum(operate(i,j):x(i,j))-@sum(operate(j,i):x(j,i))=d(i));
s^2=@sum(operate:dt*x);
p=@psn((limit-tbar)/s);
@psn((days-tbar)/s)=0.95;
end

求得关键路线的时间期望为 51 天，标准差为 3.16，在 52 天完成全部作业的概率为 62.4%，如果完成全部作业的概率大于等于 95％，那么工期至少需要 56.2 天。

版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_29831163/article/details/89787727

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)