运筹学
OPERATIONS RESEARCH
第七章 计划评审技术和关键路线法
（Program Evaluation and Review Technique，Critical Path Method ）
§ 1． PERT 网络图
§ 3．关键路线和网络计划的优化
§ 4．完成作业的期望时间和
在规定时间内实现事件的概率
§ 2． PERT 网络图的计算
甘特图（横道图）
20世纪初，.甘特创造了“甘特法”，
将各项工作任务按其起迄时刻用一条粗线表示在有时间坐标的图表上。
横道图能清楚地表明各项任务的进度安排，对提高管理水平作用明显。
甘特图（横道图）
横道图法的缺点：不能显示各工作之间的内在联系和逻辑关系；不能清晰地显示影响整个工程的关键因素。
本章又叫网络计划技术：又称统筹法，是综合运用计划评审
技术和关键路线法的一种比较先进的计划管理方法。二十世纪
五十年代末发展起来的一种编制大型工程进度计划的有效方法。
关键路线法（CRM）：是在计划项目的各项错综复杂的工作中，抓住其中的关键路线进行计划安排的一种方法。研究费用与工期的相互关系。
1956年，美国杜邦公司在制定企业不同业务部门的系统规划时，制定了第一套网络计划。这种计划借助于网络表示各项工作与所需要的时间，以及各项工作的相互关系，通过网络分析研究工程费用与工期的相互关系，并找出在编制计划时及计划执行过程中的关键路线。这种方法称为关键路线法（Critical Path Method）简称CPM。
计划评审技术（PERT）：是对计划项目进行核算、评
价，然后选定最优计划方案的一种技术。
1958年，美国海军武器部，在制定研制“北极星”导弹计划时，同样地应用了网络分析方法与网络计划。但它注重于对各项工作安排的评价和审查。这种计划称为计划评审方法（Program Evaluation and Review Technique）简称为PERT。能直观清晰的反映计划各部门或各项工作之间的相互联系和制约；反映某一部门或某项工作在全局中的地位和影响，便于发现薄弱环节以采取措施。
鉴于这两种方法的差别，所以，CPM主要应用于以往在类
似工程中已取得一定经验的承包工程；PERT更多地应用于研究
与开发项目。
在这两种方法得到应用推广之后，又陆续出现了类似的最低成本估算计划法、产品分析控制法、人员分配法、物资分配和多种项目计划制定法等等。虽然方法很多，各自側重的目标有所不同。但它们都应用的是CPM和PERT的基本原理和基本方法。
国内外应用网络计划的实践表明，它具有一系列优点，特别适用于生产技术复杂，工作项目繁多、且联系紧密的一些跨部门的工作计划。例如新产品研制开发、大型工程项目、生产技术准备、设备大修等计划。还可以应用在人力、物力、财力等资源的安排，合理组织报表、文件流程等方面。
二十世纪六十年代我国开始应用CPM与PERT，并根据其基本原理与计划的表达形式，称它们为网络技术或网络方法，又按照网络计划的主要特点——统筹安排，把这些方法称为统筹方法，华罗庚先生在这项技术的引进与推广方面作出了很大努力。
§ PERT 网络图
一、基本概念
1、作业（或叫工序、活动）：任何消耗时间或资源的行动。它是指为了完成工程项目,在工艺技术和组织管理上相对独立的工作或活动。一项工程由若干个作业组成，作业可以划分得较粗或较细。
作业用箭线“→”表示。权表示为完成某个工序所需要的时间或资源等数据，通常标注在箭线下面或其它合适的位置上。
与某道工序前面直接相连的工序称为紧前工序；其后直接相连的后继工序为紧后工序。
2
1
4
5
3
6
1h
4h
5h
2h
3h
3h
2h
2、事件（也称事项，结点）：
（1）它是一个或若干个工序的开始或结束的标志，是相邻工序在时间上的分界点。
（2）事件用圆圈和里面的数字表示，数字表示结点的编号，如①，②，…等。箭尾结点表示工序的开始，箭头结点表示工序的完成。
（3）事件本身不消耗时间或资源，或相对于作业，消耗量可忽略不计。
（4）作业的起点事件、终点事件：（i,j )；最初事件、最终事件（唯一）
2
1
4
5
3
6
1h
4h
5h
2h
3h
3h
2h
1
2
5
作业a： （1，2）
事项：1，2
一般如果起点事件为i，终点事件为j，将该作业记为（i,j）
。
i
j
a
3、路线：PERT 网络图中由最初事件到最终事件的各项作
业连贯组成的一条路。
路的长度：完成该路上各项作业持续时间的长度和。
关键路线：由最初事件到最终事件的各项作业累计时间最
长的路。它决定网络图上所有作业需要的最短时间。
路线1，2，5，6 8小时
路线1，3，5，6 11小时 关键路线
路线1，4，5，6 7小时
2
1
4
5
3
6
1h
4h
5h
2h
3h
3h
2h
4.网络图：由工序、事项及时间参数所构成的有向图即为网络图。
比较上一章的网络图。
二、建立 PERT 网络图的准则和注意事项
为正确反映工程中各个工序的相互关系,在绘制网络图时，应
遵循以下准则：
1、作业（i,j)用唯一箭线表示，起点事件（箭尾事件）编号
小于终点事件（箭头事件）的编号。
2、两个事件之间只能用一条箭线表示一项作业，具有相同开
始和结束的不同作业，需引进虚事件和虚作业。
2
1
5
1
5
如图1的画法是错误的，图2的画法是正确的。
1
2
3
1
3
4
2
a
b
c
a
b
c
图1
图2
即一个工序用确定的两个相关事项表示，某两个相邻结点只能是一个工序的相关事项。在计算机上计算各个结点和各个工序的时间参数时，相关事项的两个结点只能表示一道工序，否则将造成逻辑上的混乱。
3、各项作业间的几种关系及图上表示方法
（1）作业 a 结束后可以开始 b, c ；
（2）作业 c 在 a,b 结束后才可以开始；
（3）作业 a,b 结束后可以开始 c,d ；
（4）作业 c 在 a 结束后即可以开始， d 在 a,b 结束后才
可以开始。
2
1
4
3
a
b
c
2
1
4
3
a
b
c
5
2
1
4
3
a
b
c
d
(1)
(2)
(3)
5
2
1
4
3
a
b
c
d
6
(4)
虚箭线表示虚活动，不消耗资源，不占用时间
4、虚工序。为了用来表达相邻工序之间的衔接关系，而实际上并不存在而虚设的工序。虚工序不需要人力、物力等资源和时间。只表示某工序必须在另外一个工序结束后才能开始。用虚箭线┄→表示，表示工时为0。
5、任何PERT网络图有唯一的最初事件和唯一的最终事件
在网络图中，为表示工程的开始和结束，只能有一个最初事件（始点）和一个最终事件（终点）。也就是除始点和终点外，其它各个结点的前后都应有弧相连接，即图中不能有缺口，使网络图从始点经任何路线都可到达终点。否则，将使某些工序失去与其紧后（或紧前）工序应有的联系。
当工程开始时有几个工序平行作业，或在几个工序结束后完工，用一个始点、一个终点表示。若这些工序不能用一个始点或一个终点表示时，可用虚工序把它们与始点或终点连起来。
5
2
1
4
3
a
b
c
d
5
2
1
4
3
a
b
c
d
6
6、网络图中不能有回路。
在本章讨论的网络图中不能有回路，即不可能有循环现象。否则，将使组成回路的工序永远不能结束，工程永远不能完工。在如下网络图中出现的情况，显然是错误的。
1
2
3
4
a
b
c
d
7、方向的规定。PERT 网络图的布局一般是从左到右，从上到下，尽量避免箭线交叉。
因此，事件编号应从始结点开始，从左向右，从上到下排列；箭头标号大于箭尾标号，直到终结点。
8、网络图的步局。在网络图中，尽可能将关键路线布置在中心位置，并尽量将联系紧密的工作布置在相近的位置。为使网络图清楚和便于在图上填写有关的时间数据与其它数据，弧线尽量用斜线或水平线或具有一段水平线的折线。
三、PERT 网络图的合并与简化
若干局部网络图合并成一个大的全局网络图
合并后的网络图需简化
四、绘制 PERT 网络图
绘制网络图的学习方法：
亲自画几个，从易到难，画几个之后，就会知道其中的规律。
例1：
8
4
7
9
5
7
6
6
4
工序时间
G
E、F
C、D
C、D
B
B
A
--
--
紧前工序
I
H
G
F
E
D
C
B
A
工序
A,4
B,6
C,6
D,7
E,5
G,7
F,9
H,4
I,8
8
4
7
9
5
7
6
6
4
工序时间
G
E、F
C、D
C、D
B
B
A
--
--
紧前工序
I
H
G
F
E
D
C
B
A
工序
E、F、G
D
D
D
C
B
A
--
紧前工序
H
G
F
E
D
C
B
A
工序
例2：某工程的工序一览表如下，试绘制网络图。
E、F、G
D
D
D
C
B
A
--
紧前工序
H
G
F
E
D
C
B
A
工序
2
3
4
5
9
8
6
7
1
A
B
C
D
G
F
E
H
b、d、e
f
c
e
a、c
d
--
c
a
b
--
紧前工序
a
工序
例3：
b、d、e
f
c
e
a、c
d
--
c
a
b
--
紧前工序
a
工序
1
2
3
4
5
6
a
c
b
d
e
f
abc
f
ac
e
ab
d
--
c
--
b
--
紧前工序
a
工序
例4：
a,b,c
f
a,c
e
a,b
d
--
c
--
b
--
a
紧前
工序
工序
1
2
3
a
b
c
4
d
e
f
5
6
例5：某工程的工序一览表如下，试绘制网络图。
--
f
f
e
f
d
e
c
d
b
bc
紧后工序
a
工序
例5：某工程的工序一览表如下，试绘制网络图。
--
f
f
e
f
d
e
c
d
b
bc
紧后工序
a
工序
2
3
4
5
6
1
a
b
c
d
f
e
例6：某工程的工序一览表如下，试绘制网络图。
--
f
g
e
g
d
f
c
c,d,e
b
c,d
a
紧后工序
工序
--
f
g
e
g
d
f
c
c,d,e
b
c,d
a
紧后工序
工序
1
3
2
4
5
6
a
b
c
e
f
d
g
例6：某工程的工序一览表如下，试绘制网络图。
例7：某工程的工序一览表如下，试绘制网络图。
--
j
--
i
--
h
j
g
i
f
i
e
h
d
g
c
d,e,f
b
d,e
a
紧后工序
工序
--
j
--
i
--
h
j
g
i
f
i
e
h
d
g
c
d,e,f
b
d,e
a
紧后工序
工序
2
5
6
7
1
b
g
e
3
4
a
c
f
8
h
i
j
d
例7：某工程的工序一览表如下，试绘制网络图。
例8：某工程的工序一览表如下，试绘制网络图。
--
j
--
i
j
h
--
g
j
f
i
e
i
d
h
c
f,g,i
b
e
a
紧后工序
工序
--
j
--
i
j
h
--
g
j
f
i
e
i
d
h
c
f,g,i
b
e
a
紧后工序
工序
2
5
7
1
b
g
e
3
4
a
c
8
i
j
3
d
f
h
例8：某工程的工序一览表如下，试绘制网络图。
3
E
1
2
4
6
7
8
3
5
A
2
B
8
C
4
D
1
J
5
F
3
H
7
G
2
I
6
0
0
9
10
11
5
6
7
2
3
8
1
4
3
2
作业时间
I
GH
DF
EF
C
A
B
AB
/
/
紧前作业
J
I
H
G
F
E
D
C
B
A
作业
例9
例：某项工程由11项作业组成，其计划完成时间及作业间相
互关系如表。
绘制箭线式网络图
计算各项时间
C，D
15
F
F，G
20
K
A
4
E
F，G， I
15
J
B
4
D
B，E
25
I
-
11
C
B，E
35
H
-
10
B
B，E
21
G
-
5
A
紧前作业
计划完成时间/天
作业
紧前作业
计划完成
时间/天
作业
§ PERT 网络图的计算
F，15
C，11
A，5
1
2
3
6
7
8
4
5
E，4
B，10
D，4
J，15
H，35
G，21
I，25
K，20
虚箭线表示虚活动，不消耗资源，不占用时间。
1、作业的最早开始时间TES (i，j)
任何一个工序都必须在其紧前工序结束后才能开始。作业的最早开始时间是它的各项紧前作业最早结束时间中做大的一个值，用TES (i，j)表示。
可以假定最初事件在时刻零实现。
作业的最早结束时间TEF(i，j)是它的做早开始时间加上该作业的计划作业时间的值。
注意：计算的顺序先从结点1开始的作业开始，以结点1开始的作业算完后，再算结点2开始的作业，依次类推。
一、网络时间的计算
计算各项时间:
最早开始和最早结束时间 假设最初事件在零时刻实现
A(1,2)，B(1,3)，C(1,4)的最早开始时间：
A(1,2)，B(1,3)，C(1,4)的最早结束时间：
E(2,5)的最早开始和最早结束时间：
D(3,4)和虚作业（3，5）的最早开始和最早结束时间：
F(4,6)的最早开始和最早结束时间：
G(5,6)、I(5,7)和H(5,8)的最早开始和最早结束时间：
完成所有作业的最短周期：
J(7,8)的最早开始和最早结束时间：
工序(6，7)、(6，8)的最早开始和最早结束时间：
2、作业最迟结束时间 TLF (i，j)。在不影响工程最早结束时间的条件下, 工序最迟必须结束时间，简称为工序最迟结束时间, 是它的各项紧后作业最迟开始时间中最小的一个。
可以假定全部作业在什么时间内结束。
作业最迟开始时间TLS (i，j)。在不影响工程最早结束时间的条件下，工序最迟必须开始的时间。它等于作业的最迟结束时间减去该作业时间。
注意：计算的顺序先从结点8结束的作业开始，以结点7结束的作业算完后，再算结点6结束的作业，依次类推。
最迟结束和最迟开始时间
假设所有作业在51天内完成
H(5,8),J(7,8),K(6,8)的最迟开始时间：
H(5,8),J(7,8),K(6,8)的最迟结束时间：
I(5,7)及虚作业（6，7）的最迟结束、最迟开始时间：
G(5,6)和F(4,6)的最迟结束、最迟开始时间：
E(2，5)和虚(3，5)的最迟结束,最迟开始时间：
D(3，4) 和 C(1，4)的最迟结束,最迟开始时间：
A(1，2)的最迟结束,最迟开始时间：
B(1，3)的最迟结束,最迟开始时间：
最初事件1的最迟开始时间：
R(i，j) = TLF (i，j) TES (i，j) T (i，j)
作业的总时差R(i,j)：网络上多于一项作业共同拥有的机动
时间。也是网络上可以利用的时差总数，或工作的机动时间、
富裕时间。在不影响工程最早结束时间的条件下，工序最早
开始(或结束)时间可以推迟的时间(即工序的完工期可以推迟
的时间)即：
3、时差的计算
工序总时差越大,表明该工序在整个网络中的机动时间越大，
可以在一定范围内将该工序的人力、物力资源利用到关键工
序上去，以达到缩短工程结束时间的目的。
总时差为零的作业是关键作业，没有任何机动时间。
式中，TES (j，k)为工序 i→j 的紧后工序的最早开始时间。
自由时差F(i,j) ：不影响作业的各项紧后作业最早开工时
间条件下，该作业可以推迟开工时间的最大限度。
自由时差0的工序，尤其是自由时差较大的作业，可以适当的分流人、财、物给关键作业，可以缩短工期。
工序 a
工序a 的紧后工序b
工序a 的自由时差
工序a 的总时差
TES TLS TEF TLF
TES TLS TEF TLF
（参考内容）工序总时差、自由时差及其紧后工序的最早开始时间、最迟开始时间的关系如下图所示。
二、各时间参数的图上计算法
标出四个数：
a、TES (i，j) 写在方框内，标在箭尾处，从左向右标，标的顺序同计算顺序；
tES (i，j)=max{tES (h,i)+ thi}
b、TLF (i，j)写在三角形内，标在箭头处，从右向左标，标的顺序同计算顺序；
tLF (i，j)=min{tLF (j,k) - tjk}
c、T( i ，j)标在作业上面；
d、R(i，j)标在作业下面。总时差为零的工序，开始和结束的时间没有一点机动的余地。由这些工序所组成的路线就是网络中的关键路线。这些工序就是关键工序；
特点：方便、简便、直观，但工作数目多，图形复杂时候，容易遗漏和出错，这时可以采用表格法。
F15
C11
1
2
3
6
7
8
4
5
E4
B10
D4
J，15
H，35
G，21
I25
K20
0
0
0
5
10
10
14
10
10
10
31
31
35
51
51
51
36
36
31
31
10
10
16
16
10
6
1
A5
0
5
1
0
2
2
0
1
6
5
0
1
1
1
51
36
50
35
15
J (7,8)
0
0
51
31
51
31
20
K (6,8)
4
5
36
36
31
31
0
虚 (6,7)
6
6
51
16
45
10
35
H (5,8)
0
1
36
11
35
10
25
I (5,7)
0
0
31
10
31
10
21
G (5,6)
2
2
31
16
29
14
15
F (4,6)
0
0
10
10
10
10
0
虚 (3,5)
0
2
16
12
14
10
4
D (3,4)
1
1
10
6
9
5
4
E (2,5)
3
5
16
5
11
0
11
C (1,4)
0
0
10
0
10
0
10
B (1,3)
0
1
6
1
5
0
5
A (1,2)
F(i,j)
R(i,j)
tLF(i,j)
tLS(i,j)
tEF(i,j)
tES(i,j)
t(i,j)
作业（i,j)
三、各时间参数的表格计算法
例：计算时间参数
1
2
3
4
5
6
2
a 4
3
b 3
0
c 6
7
d 5
2
e 8
0
f 10
0
4
6
4
6
16
6
6
6
6
10
f
8
e
5
d
6
c
3
b
4
a
关键
工序
r(i,j)
R(i,j)
tLF(i,j)
tLS(i,j)
tEF(i,j)
tES(i,j)
t(i,j)
工序
6
6
4
0
0
0
16
14
9
6
3
4
16
16
16
6
6
6
6
8
11
0
3
2
0
2
7
0
3
2
0
2
7
0
1
0
f
c
§ 关键路线及网络计划的优化
绘制网络图、计算网络时间和确定关键路线,得到一个初始的计划方案。但通常还要对初始计划方案进行调整和完善。根据计划的要求，综合地考虑进度、资源利用和降低费用等目标，即进行网络优化，确定最优的计划方案。
关键路线：由最初事件到最终事件的各项作业累计
时间最长的路。
F，15
C，11
A，5
1
2
3
6
7
8
4
5
E，4
B，10
D，4
J，15
H，35
G，21
I，25
K，20
关键路线上各作业的总时差均为0。
关键路线的意义：
1、关键路线的持续时间决定了完成全盘计划所必需的最
少时间；
2、关键路线上的各项作业对计划进度起决定作用，必须
投入充分的人、财、物保证各作业按时完工。若想提
前完工，必须缩短关键路线上的有关工序的时间。
3、次关键路线可能成为关键路线，也要注意。
例：要求上例中的工程在49天内完成，可缩短有关工时的作
业时间，产生的额外费用如表所示，应如何安排，可使
得额增加的费用最小？
500
16
20
K (6,8)
400
12
15
J (7,8)
300
22
25
I (5,7)
500
30
35
H (5,8)
600
16
21
G (5,6)
450
3
4
E (2,5)
400
8
11
C (1,4)
700
8
10
B (1,3)
缩短1天增加的费用
最短完成时间
计划完成时间
作业（i,j)
1、要缩短工期，应缩短关键路线上的 B, G, K 作业时间
2、额外费用要最小，先考虑 K
3、缩短1天即会产生新的关键路线，故先缩短1天
F，15
C，11
A，5
1
2
3
6
7
8
4
5
E，4
B，10
D，4
J，15
H，35
G，21
I，25
K，19
4、现有两条关键路线，应缩短关键路线上的 B, G, K ，或
B，I，J作业时间
5、额外费用要最小，考虑 B
6、缩短1天即会产生新的关键路线，故缩短1天。已满足要求
最优方案的选择
时间优化：在人力、材料、设备、资金等资源基本有保证的条件下，寻求最短的工程周期。
时间与资源的优化：在合理利用资源的条件下，寻求最短的工程周期。
时间与成本的优化
对于工期紧迫的工程，则在保证工期最短的情况下，寻求成本较低的方案。对于一般工程，则在成本最低的情况下，寻求合理的工程周期。
目的是要找出总成本变动中的成本最低点。
网 络 优 化:绘制网络图、计算网络时间和确定关键路线,得到一个初始的计划方案。但通常还要对初始计划方案进行调整和完善。根据计划的要求，综合地考虑进度、资源利用和降低费用等目标，即进行网络优化，确定最优的计划方案。
网络计划技术的优点
减少项目的工期
对复杂项目的进一步控制
资源的更有效利用
能制定非常详细的计划
能预测潜在的瓶颈问题
能找出关键活动
重视各活动之间的内在关系
§ 完成作业的期望时间和
在规定时间内实现事件的概率
完成作业的时间估计：
1、最乐观估计：a
2、最悲观估计：b
3、最可能估计： m
完成作业的
期望时间及方差：
例：书 P191，例3
1、完成各项作业的期望时间和方差：
2、假定每事件 k 的最早完成时间服从正态分布，
期望和方差是
3、事件 k 在规定时间
内完成的概率：
课后第4题：
首先绘制网络图如下：
1
3
4
7
8
9
13
14
15
2
5
10
12
6
11
a
10
b
8
c
6
d
16
e
24
l
8
m
24
f
4
g
4
i
4
h
10
j
12
k
16
n
4
解：1）最短周期即总工期为 80 天。
2）因为总时差Rl=28，故l拖期10天对整个工程进度没有影响。
3)可使工期提前4天；
4）tLS=56，即i最迟必须第56天开工
5）需要采取措施，在a、c、e、f、g、j、k、n上共需缩短5天时间。
课后第5题：工序a 可赶工(即提前) 4天, 赶工每天增加费用25元;工序 c 可赶工(即提前) 2天, 赶工每天增加费用20元;工序e 不能赶工(即提前);工序 f 可赶工(即提前) 2天, 赶工每天增加费用30元;工序 g 可赶工(即提前) 2天, 赶工每天增加费用10元;工序 j 可赶工(即提前) 4天, 赶工每天增加费用15元;工序 k 可赶工(即提前) 4天, 赶工每天增加费用30元;工序 n 不能赶工(即提前) ;
根据以上计算所得出的信息我们可知: 若要求该项工程在70天内完工，则我们必须在关键路线上缩短工期10天,并且还要求总费用最省,为此我们给出的方案是:工序g（立房顶桁架）、工序j（装天花板）及工序c（车库地面施工）全部赶工作业。工序a（清理场地，准备施工）5天正常工作，3天赶工作业。其它工序一律按正常施工。
本章知识点小结：
1、绘制网络图；
2、计算时间参数：最早开始、最早结束、最迟开始、最迟结束、总时差；
3、确定关键路线。
表7-8
1
2
3
8
6
9
7
5
4
a1
a3
b3
c1
b2
b1
c2
c3
表7-9，K的紧前作业是D和J
1
3
2
7
4
6
5
9
8
10
A2
B
D
H
E
F
C
J
I
G
K
L
M2
表10
1
2
5
7
9
3
6
8
4
10
B
A
C
E
G
I
H
K
D
F
M2
11
12
J
L
