第六章网络分析与网络计划
网络分析是图论的一个应用分支．它主要是应用图论的理论与方法来解决具
有网络性质的管理决策问题．在现实生活和生产实践中，网络分析方法有很广泛
的应用．如在企业管理中，如何制订管理计划或设备购置计划，使收益最大或费
用最小；在组织生产中，如何使各工序衔接好，使生产任务完成得既快又好；在
交通网络中，如何使调运的物资数量多且费用最小等．由于网络分析具有图形直
观，方法简便，容易掌握的特点，因此得到迅速的发展，且广泛地应用在各个领
域，成为经济活动中许多管理决策的优化问题的重要手段．
网络计划方法是上世纪 50 年代发展起来的计划控制技术，主要包括计划评
审技术(programme evaluation and review technique，简称 PERT)和关键路径方法
(critical path method 或 critical path analysis，简称 CPM、CPA)．网络计划方法特
别适用于现代管理中的多因素多环节的复杂计划的优化控制，成为管理运筹学的
重要应用分支．
本章在引入有关图的一些基本概念的基础上，介绍最小生成树、网络最短路、
最大流、最小费用最大流等网络分析模型及其解法；并对网络计划图（统筹图）
的制作、作业时间参数计算、关键线路方法和计划评审技术等网络计划基本技术
和方法进行初步介绍．
第一节 图的基本概念
一、图
现实世界中有许多具体事物及关系可以用图形来抽象表示．例如，路线关系、
工序安排、区位规划等都可以用图来表达．
我们先通过几个直观的例子，来认识什么是图．
例 6-1 歌尼斯堡七桥问题
哥尼斯堡(Konigsbergs)城域有一个普雷格尔河系，由新河、旧河及其交汇
而成的大河组成，它把该城分成了一岛三岸共四块陆地，陆地之间有七座桥连
通，如图 6-1(a)所示．当时城内居民在散步时热衷于这样一个问题：从某陆地
出发，能否走遍七桥且每桥只过一次而最终回到原出发地．
图 6-1（a）
图 6-1（b）
欧拉在 1736 年解决了这一问题．他用四个点表示四块陆地，用相应两点间
的边表示桥，从而建立了该问题的图的模型，见图 6-1(b)．于是问题归结为：在
这个连通多重图中，能否找出一条回路，过每边一次且仅仅一次．欧拉在求解该
问题时，把图 6-1（a）所示的实际问题抽象为图 6-1（b）所示图形．
例 6-2 比赛安排问题
5 个球队之间安排赛事．其中 a 球队分别与 b，c，d 球队有赛事；b 球队
还与 c 球队，d 球队还与 e 球队有赛事．综上，这 5 个球队之间的比赛关系可
用图 6-2(a)来表示，也可用图 6-2(b)来反映．
图 6-2（a）
图 6-2（b）
以上两例都忽略了问题的具体细节，而把问题的关键性质或关系抽象为图的
形式．例 6-1 中两岸和岛的形状及桥的曲直都被忽略，但陆地间的关联情况却得
到保持．例 6-2 中把比赛关系抽象为连接关系．简单些说，一个图代表了某些对
象集合之间的关系，而图论是主要研究这些对象在上述表示法中的许多可能的性
质中的某些性质．详细些说，一个图指的是一些点以及连接这些点的一些线的总
体．这种连接方式可以具有许多特征，而图论本质上就是研究这种特征的．注意，
这里所讲的图并不是解析几何与微积分书中常见的图，在那里，点的位置，线的
长度和斜率是它的重要部分．而在图论中，这些都是不重要的，而重要的只是哪
些点之间有线相连．有时，连接的先后次序也是重要的．
二、几个基本概念
1．无向图
一个图 定义为一个有序二元组（ ， ），记为：
＝（ ， ）
其中，V 是一个有限非空的集合，其元素称为 G 的结点或顶点，简称点，
而 V 称为 G 的结点集或顶点集，简称点集，一般表示为：
＝{ ， ，…， }
而 E 称为 G 的边集，表示为：
＝{ ， ，…， }
其中 由 中元素对( ， )所构成．如果( ， )是无序对，则 称为无
向图． 中元素 称为 的无向边，一般表示为
＝( ， )
对于给定的图可以作出其几何图．
例 6-3 无向图 ＝（ ， ），其中点集 ＝{ ， ， ， ， }，
＝{ ， ， ， ， ， ， , }，边与顶点的关联情况由表 6-1 给
出．
表 6-1 边与顶点的关联情况
( ， ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , )
根据表 6-1，可作其几何图，如图 6-3 所示．在作几何图时，仅要求表示
出顶点、边以及它们间的关联关系，而对顶点的位置以及边的曲直、长短都没
有任何规定．
图 6-3
基于无向图 的结构特点，我们给出下列一些术语：
平行边——若两条不同的边 与 具有相同的端点，则称 与 为 的平行
边．图 6-3 中 与 是平行边，因为它们的端点均为 、 ．
G V E
G V E
V 1v 2v nv
E 1e 2e ne
e V iv jv iv jv G
E e G
e iv jv
G V E V 1v 2v 3v 4v 5v
E 1e 2e 3e 4e 5e 6e 7e 8e
e 1e 2e 3e 4e 5e 6e 7e 8e
iv jv 1v 2v 1v 5v 2v 4v 1v 4v 4v 3v 5v 4v 1v 5v 2v 3v
G
e 'e e 'e G
2e 7e 1v 3v
简单图——若 无平行边，则称图 为简单图．
完备图——图 中任两个顶点间恰有一条边相关联， 为完备图．
2．有向图
设顶点的非空集合 ＝（ ， ，…， ），边的集合 ＝（ ， ，…，
）．如果 中任一条边 是 的一个有序元素对( ， )(这里， ≠ )，则称
为有向边集， 中元素 称为有向边或弧，记为
＝( ， )
其中 为 的起点， 为 的终点． 和 组成了一个有向图，记作
＝（ ， ）
例 6-4 给有向图 ＝（ ， ），其中 ＝（ ， ， ， ）， ＝
（ ， ，…， ），边与顶点的关联情况如表 6-2 所给．
表 6-2 边与顶点的关联情况
( ， ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , )
根据表 6-2 也可作出有向图，如图 6-4（a）
图 6-4(a)
图 6-4(b)
图 6-4（c）
有向图区别于无向图的关键，在于它的边（或弧）是有方向的，图 6-4（a）
中边上的箭头所指即边的方向．在有向图中( ， )≠( ， )．
类似于无向图，有向图 也有下列术语：
G G
G G
V 1v 2v nv A 1a 2a
na A ija V iv jv iv jv
A A ija
ija iv jv
iv ija jv ija V A
D V A
D V A V 1v 2v 3v 4v A
1a 2a 7a
a 1a 2a 3a 4a 5a 6a 7a 8a
iv jv 2v 1v 1v 2v 3v 2v 3v 2v 2v 4v 3v 4v 2v 4v 1v 3v
iv jv jv iv
G
平行边——不同的弧 与 ( ， )的起点与终点都相同．图 6-4（a）中
、 是平行边，而 、 却不是， ＝( , )；而 ＝( , )．
简单图——无平行边的有向图称为简单图．
完备图——图中任两个顶点 与 间，恰有两条有向边( ， )及( ， )，
则称该有向图 为完备图．
基本图——把有向图 的每条边除去方向就得到一个相应的无向图 ，称
为 的基本图．例如图 6-4（b）是图 6-4（a）的基本图．
3．同构
对于无向图和有向图，如果图 ＝（ ， ）和 ＝( ， )的顶点集
合 和 ，以及边集 E 和 E 之间在保持关联性质的条件下一 一对应，则图
和 同构．
例如图 6-2(a)、(b)所示的两个图看似不同，其实是同构图．
由于同构的图被认为是相同的，这就给我们在网络规划中建立网络模型带来
许多方便，当我们用几何图来反映和分析实际问题的内在关系而构建网络模型时，
点的位置可以任意布置，边的长短曲直也可任意，故而我们尽量设计那种反映问
题清晰、简练的几何图．
4．链、路和连通性
给定一个无向图 ＝（ ， ），其中的一个点与边的交错序列 ， ，
， ，…， ， ， ，如果序列中所有 都满足 ＝（ ， ），
（ ＝1，2，…， －1），则称交错序列为联结 和 的链，记为
＝（ ， ， ， ，…， ， ， ）
或简记为
（ ， ，…， ， ）和（ ， ，…， ， ）
当 ＞0，且 ＝ ，则链的起点等于终点，称为闭链．闭链中除起点和终
点外没有相同的结点和边，则该闭链称为圈．
a 'a iv jv
3a 4a 1a 2a 1a 2v 1v 2a 1v 2v
iv jv iv jv jv iv
D
D G
G D
G V E G ' V ' E '
V V ' ' G
G '
G V E 1iv 1ie
2iv 2ie 1ikv 1ike ikv ite ite itv 1itv
t k 1iv ikv
1iv 1ie 2iv 2ie 1ikv 1ike ikv
1iv 2iv 1ikv ikv 1ie 2ie 2ike 1ike
k 1iv ikv
当 ≠ ，时称为开链．若开链中所有结点均不相同，称为初等链．
例如图 6-5 中：
图 6-5
1＝（ ， ， ， ， ， ）是闭链，但不是圈；
2＝（ ， ， ， ）是闭链，同时也是圈；
3＝（ ， ， ， ， ）是开链；
4＝（ ， ， ， ）是初等链．
对于有向图 ＝（ ， ），可以通过其相应的基本图来定义它的链．但由
于有向图中弧是有方向的，可能出现链中的弧的方向与链的方向不一致的情
况．如果链中所有弧的方向与链的方向一致，则称该链为单向路，简称路．显然，
在有向图中链和路的概念并不一致，而在无向图中两者没有区别．
如果路的起点和终点相同，则称为回路．对于无向图而言闭链和回路概念
一致．在图 6-4（a）中：
1＝（ ， ， ）是链，但不是路；
2＝（ ， ， ）是链，同时也是路和回路．
在 中任意两个结点 i1 和 ik，从 i1 到 ik 存在路，则称 i1 可达 ik．若
中任意两结点间存在链，则称 为连通图．若 中任意两结点间相互可达，则
称 为强连通图．对于无向图而言连通图等价于强连通图．
例如图 6-4（a）所示的是强连通图，因为 、 、 、 都是相互可达
的．如果我们将图中弧 删去，如图 6-4（c）所示，则成为一般的连通图．因
为这时 、 不能相互可达．
5．网络
一个图连同定义在其边集上的实函数一起称为一个网络．网络一般是连通
图．定义在边集上的实函数称为边的权数记为
＝ ( ， )
1iv ikv
1v 2v 4v 3v 2v 1v
1v 2v 3v 1v
1v 2v 4v 3v 2v
1v 2v 4v 3v
D V A
1a 3a 8a
8a 3a 1a
D v v v v v v D
D D
D
1v 2v 3v 4v
8a
1v 3v
ijw w iv jv
它与边( ， )具有一一对应关系，可以用以表达网络上的各种有关性质，
如路长、流量、费用等等．网络的图解即在每条边旁标上相应的权数．
若一网络的每条边都是无向边，则称为无向网络，记为
＝（ ， ）或 ＝( ， )
若一网络的每条边都是有向边，则称为有向网络，记为
＝（ ， ）或 ＝( ， )
若一网络中既有无向边，也有有向边，则称为混合网络．
所谓网络分析，简单地说，即对网络进行定性和定量分析，以便为实现某
种优化目标而寻求最优方案．这方面的典型问题有：最小树问题，最短路问题，
中心问题，重心问题，最大流问题，最小费用最大流问题，最短回路问题，网络
计划问题，等等．
第二节 最小树问题
一、树的基本概念
1．子图、真子图、生成子图
设有图 ＝( ， )和图 ＝( ， )，如果 ， ，则称
为 的子图，并记为 ，而 则为 的原图．当子图的边集或点集不同
于原图时，即 ≠ 时，称子图 为 的真子图，记为 ．当子图的点
集等于原图的点集时，则称子图 为原图 的生成子图或支撑子图．
在图 6-6 中，（a），（b），（c），（d）均是（a）的子图；（a），（b），（c）是
（a）的真子图；（a），（b），（c）均是（a）的生成子图．由于（d）比（a）少
一个点，所以（d）不是（a）的生成子图．
图 6-6
2．树
无圈且连通的无向图称为树．树一般记为 ．作为树定义还可以有以下几
种表述：
iv jv
N G w N V E
N D w N V A
G V E G ' V ' E ' V ' V E ' E G '
G G ' G G G '
G ' G G ' G G ' G
G ' G
T
(1) 连通且无圈或回路；
(2) 无圈且有 n－1 条边（如果有 n 个结点）；
(3) 连通有 n－1 条边；
(4) 无回路，但不相邻的两个结点之间联以一边，恰得一个圈；
(5) 连通，但去掉 T 的任意一条边， 就不连通了；
(6) 的任意两个结点之间恰有一条初等链．
二、最小生成树及其算法
1．最小生成树
如果 是无向图 的生成子图，同时 又是树，则称 是 的生成树或支撑
树．
例如图 6-7（b），（c）是（a）的生成树．
图 6-7
一个网络图可以有多个生成树．记 N 的所有生成树的集合为：
＝{ | ＝1，2，…，L }
设 ＝（ ， ）是网络图 N＝（ ， ）的一棵生成树，则边集 中所
有边的权数之和称为树 的权数，记为
（ ）＝
若 ∈ ，使
（ ）＝ { （ ）}
则称 为网络 的一棵最小生成树，简称最小树．
2．最小树的求法
T
T
T
T
T T
T
T G T T G
T kT k
iT V kE G w kE
kT
w kT
Eke
ew )(
*T T
w *T
TTk
min w kT
*T N
定理 8-1 如果把网络 的点集 分割成两个不相交的非空集合 和 ，
则联结 和 的最小边必包含于 N 的最小树内．
根据定理 8-1，可以给出求最小树的两种方法，这就是避圈法与破圈法，分
述如下：
(1)避圈法
其计算步骤如下：
∈从网络 中任选一点 ，令 ＝{ }， ＝ \{ }；
∈从联结 与 的边中选取最小边，不妨设为( ， )，则它必包含于最小
树内；
∈令 ∈{ }∈ ， \{ }∈ ；
∈若 ＝ ，则停止，已选出的诸边即给出最小树；否则返∈．
例 6-5 试求图 6-8 所示网络的最小树，各边旁边的数字为各边的权．
图 6-8
解 由题意可知这是一个最小树问题．先按原图画出 7 个点，令 ＝{1}，
＝{2，3，4，5，6，7}．由于联结 与 的边共有三条，其中最短边为(1，2)
故用线把点 1 和 2 连结起来，令 ＝{1，2}， ＝{3，4，5，6，7}，如图 6-8(a)
所示，重复上述步骤，直到 7 个点全都连通为止．具体求解过程如图 6-8（a）
到图 6-8（f）所示，其中图 6-8（f）)即给出本例的最小树 ， ( )＝13．
图 6-8（a）（b）
图 6-8（c）—（f）
(2)破圈法
用破圈法求最小树时，先从图中任取一圈，去掉该圈的一条最大边，然后重
复这一步骤，直到无圈为止．
例 6-6 图 6-9 所示的一赋权连通图是某一具有 9 个居民点的交通网络图，
其中边权表示该段道路的长，现欲沿小区道路架设一联络各个居民点的闭路电
N V S
_
S
S
_
S
N iv S iv
_
S V iv
S
_
S iv jv
S jv S
_
S jv
_
S
_
S
S
_
S S
_
S
S
_
S
*T w *T
视系统，求可使闭路电视系统所架线路总长最短的方案．
图 6-9
解 这是一个求网络最小树的问题．可利用破圈法求解．过程如图 6-9
（a—i）所示．
图 6-9（a——i）
图 6-9（i）所示的是网络最小树 ．按图安排闭路电视系统可使所架线
路总长最短， ( )＝19．
第三节 最短路径问题
在生产实践，运输管理和工程建设的很多活动中，诸如各种工艺路线的安
排、厂区及货场的布局、管道线网的铺设及设备的更新等等问题，都与寻找一个
“图的最短路径”问题(shortest-path problem )密切相关，它是网络规划中的一个最
基本的问题．
一、基本概念
给定一个赋权有向图 ＝( ， )，对每一条弧 ＝( ， )，相应地有权
（ ）＝ ，又有两点 、 ∈V，设 是 中从 到 的一条路，路 的
权是 中所有弧的权之和，记为 ( )．最短路问题就是求从 到 的路中一条
权最小的路 ：
( )＝ ( )
二、最短路问题的算法
1．Dijkstra 算法(Dijkstra algorithm)
该算法是由 Dijkstra 于 1959 年提出来，用于求解指定两点之间的最短路，
或从指定点到其余各点的最短路，目前被认为是求解最短路问题的最好方法．算
法的基本思路基于以下原理.
定理 6-2 若 是从 到 的最短路， 是 中的一个点，那么从 沿
*T
w *T
D V A ija iv jv
w ija ijw sv tv p D sv tv p
p w p sv tv
*p
w *p
p
min w p
p sv tv iv p sv p
到 的路必定是从 到 的最短路．
引理 若 是从 到 的最短路， 是 中的一个点，则从 到 的最短
路必定包含于 之内．
根据定理 6-2 及引理，我们可以从 s 出发试探所有可能到达 t 的下一个结
点 i，取距离最短的一个弧（ ， ），则必然包含于从 到 的最短路中；从
开始对没有试探过的结点进行进一步的试探、推进，直至 ，最终可以找出从
到 的最短路．Dijstra 算法采用（双标号法）T 标号与 P 标号，来实现这一试探、
推进过程．T 标号为试探性标号；P 为永久性标号．给 点一个 P 标号时，表示
从 到 点的最短路权，一旦 点得到 P 标号则意味着从 到 点的最短距离
已经确定，标号不再改变．给 点一个 T 标号时，表示从 到 点的估计最短
路权的上界，这是一种临时标号．凡没有得到 P 标号的点都有 T 标号．算法每
一步都把某一点的 T 标号改为 P 标号，当终点 得到 P 标号时，全部计算结
束．
Dijstra 算法基本步骤：
(1)给 以 P 标号，P( )＝0，其余各点均给 T 号，T( )＝＋∞．
(2)若 点为刚得到 P 标号的点，考虑 ，( ， )∈A 且 为 T 标号．对
的 T 标号进行如下的更改：
T( )＝min[T( )，P( )＋ ] (6-1)
(3)比较所有具有 T 标号的点，把最小者 改为 P 标号，即：
P( )＝min[ T( ) ] (6-2)
当存在两个以上最小者时，可同时改为 P 标号．
(4)若全部点均为 P 标号，则停止计算．否则用 代替 并转至步骤（2）．
例 6-7 用 Dijkstra 算法求图 6-10 中从 到 的最短距离，以及相应的路
线．
iv sv iv
p sv tv iv p sv iv
p
v v
v sv iv sv tv iv
tv sv
tv
iv
sv iv iv sv iv
iv sv iv
tv
sv sv iv
iv jv iv jv jv jv
jv jv iv ijw
'
iv
'
iv iv
'
iv iv
1v 7v
图 6-10
解 （1）首先给 以 P 标号，P（ ）＝ 0，给其余所有点 T 标号，T
（ i）＝＋∞（i = 2，3，… 7）．
（2）考察 ，由于（ ， ），（ ， ），（ ， ）∈A，且 、 、
是 T 标号，所以修改 T 标号为：
T（ ）＝min [ T（ ），P（ ）＋ ]＝min [∞，0＋2]＝2
T（ ）＝min [ T（ ），P（ ）＋ ]＝min [∞，0＋5]＝5
T（ ）＝min [ T（ ），P（ ）＋ ]＝min [∞，0＋3]＝3
在所有 T 标号中，T( )＝2 最小，于是令 P( )＝2．将结果记在图 6-10（a）
上：P 标号以（）形式标在结点旁边，T 标号以不带（）的数字标在结点旁边，
图中没有标号的结点均代表 T（ ）＝＋∞
(3)考察 ．因为（ ， ），（ ， ）∈A，且 、 是 T 标号，故 、
新的 T 标号为：
T（ ）＝min [ T（ ），P（ ）＋ ]＝min [∞，2＋2]＝4
T（ ）＝min [ T（ ），P（ ）＋ ]＝min [∞，2＋7]＝9
在所有 T 标号中，T( )＝3 最小，故令 P( )＝3．图上标号如图 6-10（b）．
(4)考察 ，因（ ， ）∈A，
T（ ）＝min [ T（ ），P（ ）＋ ]＝min [∞，3＋5]＝8
在所有 T 标号中，T( )＝4 最小，令 P( )＝4．图上标号如图 6-10（c）．
(5)考察 ，（ ， ），（ ， ）∈A，
T（ ）＝min [ T（ ），P（ ）＋ ]＝min [∞，4＋3]＝7
T（ ）＝min [ T（ ），P（ ）＋ ]＝min [∞，4＋5]＝9
在所有 T 标号中，T( )＝7 最小，令 P( )＝7．图上标号如图 6-10（d）．
1v 1v
v
1v 1v 2v 1v 3v 1v 4v 2v 3v 4v
2v 2v 1v 12w
3v 3v 1v 13w
4v 4v 1v 14w
2v 2v
iv
2v 2v 3v 2v 6v 3v 6v 3v
6v
3v 3v 2v 23w
6v 6v 2v 26w
4v 4v
4v 4v 5v
5v 5v 4v 45w
3v 3v
3v 3v 5v 3v 6v
5v 5v 3v 35w
6v 6v 3v 36w
5v 5v
(6)考察 ，（ ， ），（ ， ）∈A，
T（ ）＝min [ T（ ），P（ ）＋ ]＝min [∞，7＋1]＝8
T（ ）＝min [ T（ ），P（ ）＋ ]＝min [∞，7＋7]＝14
在所有 T 标号中，T( )＝8 最小，故令 P( )＝8．图上标号如图 6-10
（e）．
(7)考察 ，（ ， ）∈A，
T（ ）＝min [ T（ ），P（ ）＋ ]＝min [14，8＋5]＝13
令 P( )＝13，图上标号如图 6-10（f）．所有点都标上 P 标号，计算结
束．
从 到 的最短路径，可从 开始根据永久性标号数值回溯得到．最短
路径是： → → → → → → ，路长 13．同时得到 到其余各点的
最短路，即各点的永久性标号 P（ i）．
Dijkstra 算法只适用于所有 0 的情形，当赋权有向图中存在负权时，则
算法失效．
图 6-10（a）（b）（c）（d）（e）（f）
2．逐次逼近算法
为方便起见，不妨设从任一点 到任一点 都有一条弧，如果在 中，不
存在弧( ， )，则添加虚设弧( ， )，令 ＝＋∞．从起点 到任意点 的
最短路可以视为一个两阶段过程，如图 6-11 所示：
图 6-11
(1)从 出发，沿着一条路走 －1 步到某点 ，其最短距离表示为
( ， )
5v 5v 6v 5v 7v
6v 6v 5v 56w
7v 7v 6v 57w
6v 6v
6v 6v 7v
7v 7v 6v 67w
7v
1v 7v 7v
1v 2v 3v 4v 5v 6v 7v 1v
v
ijw
iv jv D
iv jv iv jv ijw sv jv
sv k iv
)1( kd sv iv
(2)再从 沿( ， )到 ，其最短距离就是弧( ， )上的权 ．
所以，从 到 的最短距离必满足如下递推公式：
( ， )＝ （ ＝1，2，…，n） （6-3）
( ， )＝ { ( ， )＋ } （6-4）
式（6-3）是任意两点间的一步距离，由前面假设可知其存在，这可以作为
初始条件．式（6-4）是任意两点间的 k 步距离，这是一个递推公式．利用初始
条件和递推公式通过逐步迭代就可以确定网络 中任意点之间经 步到达的最
短距离并得到与之相应的路线．下面以实例来说明迭代过程．
例 6-8 用逐次逼近算法求例 6-6 图 6-10 中从 到各点的最短距离．
解 根据初始条件可知
( ， )＝0 ( ， )＝2 ( ， )＝5
( ， )＝3 ( ， )＝＋∞ ( ， )＝＋∞
( ， )＝＋∞；
初始条件仅仅表达了 从出发到 的一步到达的距离，在有向简单网络中
即为从 到各点的最短距离．
到各点的 步距离由公式（6-4）递推得出．为方便、直观可列表计算如
表 6-3：
表 6-3 到各点的 步距离
( ， )＝
{ ( ， )＋ }
k=1 k=2 k=3 k=4 k=5 k=6
0 2 5 3 0 0 0 0 0 0
0 2 7 2 2 2 2 2 2
iv iv jv jv iv jv ijw
sv jv
）（1d sv jv sjw j
)(kd sv jv imin
)1( kd sv iv ijw
D k
1v
）（1d 1v 1v
）（1d 1v 2v
）（1d 1v 3v
）（1d 1v 4v
）（1d 1v 5v
）（1d 1v 6v
）（1d 1v 7v
1v jv
1v
1v k
1v k
ijw
)(kd sv jv
i
min )1( kd sv iv ijw
1v 2v 3v 4v 5v 6v 7v
1v
2v
jv
jiv
vi
i
0 1 3 5 5 4 4 4 4 4
0 5 3 3 3 3 3 3
0 1 7 8 7 7 7 7
0 5 9 8 8 8
0 14 13 13
∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈
表的左半部是一个 n×n 的关于结点两两之间的一步距离矩阵，由式（6-3）
可知， 到 的一步距离就是弧（ ， ）上的权 ．一步距离矩阵中 0 元
素表示原地踏一步，没有填写数字的空格是∞的省略．表右半部是公式（6-4）
的计算结果．k=h 时，第 h+n 列数据表示 到各点的 h 步最短距离．譬如 k=3
为第 ∈ 列，表示 经 3 步到达各点的最短距离．计算过程如下：
（1）当 k=1 时
( ， )＝
这是初始条件，表示从 出发到各点的一步距离，将其依次列于第 ∈
列．由此推算 ( ， )．
（2）k=2 时
( ， )＝ { ( ， )＋ }
即用表中第 ∈ 列数字与表左边一步距离矩阵中第 列相应数字相加取小，
得到从 出发到各点的二步距离：
（0 ＋ 0）
（∞ ＋ 2）
（∞ ＋ 5）
( ， )＝min （∞ ＋ 3） ＝0
（∞ ＋ ∞）
3v
4v
5v
6v
7v
iv jv iv jv ijw
1v
1v
）（1d 1v jv jw1
1v
）（2d 1v jv
）（2d 1v jv imin
）（1d 1v iv ijw
j
1v
）（2d 1v 1v
（∞ ＋ ∞）
（∞ ＋ ∞）
（2 ＋ 0）
（0 ＋ 2）
（∞ ＋ 5）
( ， )＝min （∞ ＋ 3） ＝2
（∞ ＋ ∞）
（∞ ＋ ∞）
（∞ ＋ ∞）
同理： ( ， )＝4 ( ， )＝3 ( ， )＝8
( ， )＝∞ ( ， )＝∞
得：
0
2
4
( ， )＝ 3
8
∞
∞
将其填入表 6-3 第 ∈ 列
（3）重复上述步骤得到 ( ， )、 ( ， )、 ( ， )、
( ， )；分别填入表 6-3 第 ∈、∈、∈、∈ 列
（4）当 k=6 时，发现 ( ， )＝ ( ， )，说明对于整个有向图
D 而言，继续增加步数已不起作用，即已得到从 到各点的最短距离，即表中
∈ 或 ∈ 列数字：
）（2d 1v 2v
）（2d 1v 3v
）（2d 1v 4v
）（2d 1v 5v
）（2d 1v 6v
）（2d 1v 7v
）（2d 1v jv
）（3d 1v jv
)4(d 1v jv
)5(d 1v jv
)6(d
1v jv
)6(d 1v jv
)5(d 1v jv
1v
＝0；原地一步
＝2；一步到达
＝4；二步到达
＝3；一步到达
＝7；三步到达
＝8；四步到达
＝13；五步到达
从表 6-3 中还可以用回溯方法推知 到各点最短距离的相应最短路线，以
到 为例：
由第∈列 行可知， 到 经 5 步到达，最短距离 13．回溯 13 的来源：
（ ， ）=13
因 （ ， ）＝[ ∈ 列 行 ]＋[ ∈ 列 行 ]
＝ （ ， ）＋ ＝8＋5＝13
故记下（ ， ）．
因 （ ， ）＝ [ ∈ 列 行 ]＋[ ∈ 列 行 ]
＝ （ ， ）＋ ＝7＋1＝8
故记下（ ， ）.
因 （ ， ）＝ [ ∈ 列 行 ]＋[ ∈ 列 行 ]
＝ （ ， ）＋ ＝4＋3＝7
故记下（ ， ）．
因 （ ， ）＝ [ ∈ 列 行 ]＋[ ∈ 列 行 ]
1v 1v
1v 2v
1v 3v
1v 4v
1v 5v
1v 6v
1v 7v
1v
1v 7v
7v 1v 7v
d 1v 7v
d 1v 7v 6v 6v
d 1v 6v 67w
6v 7v
d 1v 6v 5v 5v
d 1v 5v 56w
5v 6v
d 1v 5v 3v 3v
d 1v 3v 35w
3v 5v
d 1v 3v 2v 2v
＝ （ ， ）＋ ＝2＋2＝4
故记下（ ， ）．
因 （ ， ）＝ ＝0＋2＝2，记下（ ， ）．
得到最短路径： ．
当网络图存在负权时，Dijkstra 算法失效，必须采取逐次逼近算法来求解
最短路．
例 6-9 试求网络图 6-12 中 到各点的距离．
图 6-12
解 初始条件： ( ， )＝0 ( ， )＝1
( ， )＝＋∞ ( ， )＝2
( ， )＝＋∞ ( ， )＝＋∞
计算结果如表 6-4 所示：
表 6-4 到各点的距离
( ， )
=1 =2 =3 =4 =5
0 1 2 0 0 0 0 0
0 3 4 1 1 1 -1 -1
-2 0 5 1 4 1 1 1
4 0 -3 2 2 2 2 2
3 3 0 -1 -1 -1 -1
2 0
求得 到各点的最短距离：
d 1v 2v 23w
2v 3v
d 1v 2v 12w 1v 2v
1v 2v 3v 5v 6v 7v
1v
）（1d 1v 1v
）（1d 1v 2v
）（1d 1v 3v
）（1d 1v 4v
）（1d 1v 5v
）（1d 1v 6v
1v
ijw
)(kd sv jv
1v 2v 3v 4v 5v 6v
k k k k k
1v
2v
3v
4v
5v
6v
1v
vj
vi
( ， )＝0；原地一步
( ， )＝-1；四步到达
( ， )＝1；三步到达
( ， )＝2；一步到达
( ， )＝-1；二步到达
( ， )＝∞；无法到达
逐次逼近算法，因其类似于矩阵乘法，在有些书籍表述为距离矩阵摹乘法，
它们的实质一致．这种算法在 n 个结点的网络图中，至多经过 n-1 次迭代必然收
敛．但前提条件是图中不含有总权小于 0 的回路，否则最短路权没有下界．
第四节 最大流问题
网络流(network flow)是一类普遍存在的现象．例如在交通运输网络中有人流、
车流、货物流；供水网络中有水流；金融系统中有现金流；通讯系统中有信息流；
等等．在 20 世纪 50 年代 Ford 和 Fulkerson 建立的“网络流理论”是网络应用的重
要组成部分．
网络最大流问题(max-flow problem)尤为重要．这是因为绝大部分网络流研
究，旨在寻求在一定条件下使网络流达到最大的方法．如图 6-13 是输油管道网，
为起点， 是终点， ， ， ， 为中转站，弧上的数表示该管道的最大
输油能力，问应如何安排各管道输油量，才能使从 到 的总输油量最大?
图 6-13
一、基本概念和基本定理
1．网络流．
）（1d 1v 1v
)4(d 1v 2v 1v 4v 5v 3v 2v
）（3d 1v 3v 1v 4v 5v 3v
）（1d 1v 4v
）（2d 1v 3v 1v 4v 5v
）（kd 1v 6v
sv tv 1v 2v 3v 4v
sv tv
所谓网络流，是指在一定的条件下流过一个网络的某种流在各边上的流量
的集合．表达为
＝{ ( ， )| ( ， )∈ }
所谓一定条件，一般是指如下规定：
(1)网络有一个始点 和一个终点 ，始点是流的源，终点是流的汇；
(2)流具有一定的方向，流经各弧的流，其方向就是相应弧的方向；
(3)对每一弧( ， )∈ ，都赋予一个容量 ( ， ) 0，简记为 ，表
示容许通过该弧的最大流量．并称 ( ， )为通过弧( ， )流，简记为
．
凡做出上述规定的网络都可称为容量网络，记为
＝（ ， ， ）
图 6-13 所示的就是一个容量网络．图中每条弧上的数对为( ， )，标明
了弧的容量以及流经该弧的流量．
2．可行流和最大流
可行流是指满足容量限制条件和平衡条件的流．
(1)容量限制条件：对于任一弧( ， ) ，都有 0 ，即任何弧上
的流量不能超过弧的容量．
(2)平衡条件：对于任一中间点 ，都有
＝
即每个中间点的流出量必须等于流入量，其净流量为 0．
对于始点和终点，有
＝
F f iv jv iv jv A
sv tv
iv jv A r iv jv ijr
f iv jv iv jv
ijf
N V A r
ijr ijf
iv jv A ijf ijr
iv
Avjvi ),(
ijf
Avivk ),(
kif
Avivs ),(
sif
Avtvi ),(
itf
即始点流出量等于终点的流入量，这个流量即是可行流 的流量，记为
（ ）．
所谓最大流问题，就是在可行流恒存在的前提下，满足
max ( )
＝
. . － ＝ 0 ≠ 、
0 ； － ＝
这是一个特殊的线性规划问题，可用单纯形法求解．但用图形方法求解更
为直观和简单．
3．增广链
如果 是网络中联结始点和终点的一条链，且链的方向从 到 ，则与链
方向一致的弧称为前向弧，用 ＋来表示前向弧集合；与链方向相反的弧称为后
向弧，用 －来表示后向弧集合．
如图 6-13 中 ＋＝{( ， )，( ， )，( ， )}
－＝{( ， )，( ， )}
设 是一个可行流， 是一条从 到 的链，若 满足下列条件，则 是
可行流的一条增广链：
（1）在弧( ， )∈ ＋上， 0 ＜ ；
（2）在弧( ， )∈ －上， 0＜
．
这就意味着在增广链上每一个前向弧的流量都没有达到最大容量（即不饱
和前向弧）,而每一个后向弧的流量均不为 0（即非零后向弧）．
如图 6-13 中链 ＝ 、 ＝ 、 ＝ 都
F v
f
v f
f i s
s t
Avjvi ),(
ijf
Avivk ),(
kif i s t
ijf ijr f i t
sv tv
sv 2v 1v 4v 3v tv
1v 2v 3v 4v
f sv tv
iv jv ijf ijr
iv jv ijf ijr
sv 2v 1v 4v 3v tv
' sv 1v 4v 3v tv
'' sv 1v 4v tv
是增广链．可以指出，沿增广链调整各弧的流量可以使网络流量 （ ）增大，
而寻求网络最大流的方法正是以增广链为基础的．
4．截集与截量
在一个网络 ＝( ， )中，若把点集 V 剖分成不相交的两个非空集合
和 ，使 ， ，且 中各点不须经由 中的点而均连通， 中各点也
不须经由 中的点而均连通，则把始点在 中而终点在 中的一切弧所构成的
集合，称为一个分离 和 的截集，记为( ， )．截集实质上是网络 从
到 通路的横截面表达，它反映了网络从 到 的必经之路．一个网络可以有
多个截集，表 6-5 反映了图 6-13 网络的截集集合．
表 6-5 图 6-13 网络的截集集合
S＝{ } ＝{ } 截集(S， )={( ， )} 截量 (S， )
s 1,2,3,4,t (s,1), (s,2) 14
s,1 2,3,4,t (s,2), (1,2), (1,3), (1,4) 15
s,2 1,3,4,t (s,1), (2,4) 14
s,1,2 3,4,t (1,3), (1,4), (2,4) 12
s,1,2,3 2,4,t (s,2),(1,2),(1,4),(3,4),(3,t) 19
s,2,4 1,3,t (s,1), (4,t) 16
s,1,2,3 4,t (1,4), (2,4), (3,4), (3,t) 16
s,1,2,4 3,t (1,3), (4,t) 11
s,1,2,3,4 t (3,t), (4,t) 13
给定一截集( ， )，其中所有弧的容量之和称为这个截集的截量，记为
( ， )＝ [ |（ ， ）∈( ， )]
v f
N V A S
S sv S tv S S S S
S S S
sv tv S S N sv
tv sv tv
iv S jv S iv jv r S
S S
r S S ijr iv jv S S
一个网络可以有多个截集和截量，其中截量最小的截集称为最小截集，记
为( ， )，其截量称为最小截量(min-cut)，记为 ( ， )．
图 6-13 的最小截量由表 6-5 看出为 11，最小截集为( ， )＝{(1,3),
(4,t)}．
二、基本原理
为了介绍一种寻求网络最大流的标号法，这里将阐述其原理．
定理6-3（流量截量定理） 在网络 =( ， ， )中，设 为
一可行流， ( ， )是任一截集，则
（ ）≤ ( ， )
定 理 6-3表 明 ， 网 络 的 任 一 可 行 流 的 流 量 恒 不 超 过 任 一 截 集 的
截 量 ． 因 此 ， 网 络 的 最 大 流 量 也 不 会 超 过 最 小 截 量 ．
定理 6-4（最大流量最小截量定理） 网络中从 s 到 t 的最大流的流
量等于分离 s 和 t 的最小截集的截量．即，
（ ）＝ ( ， )
定理 6-4 实际上是定理 6-3 的推论．
定理 6-5（最大流的充要条件） 设 是网络 ＝( ， ， )的一
个可行流，则 为最大流的充要条件是：网络 中不存在关于 的增广
链 ( )．
定理6-6（增广链调整法） 设 ＝{ }是 ＝(V，A， )的一个可行
流， 是关于f 的一条增广链．令
－ 当 ＋≠
＝
∞ 当 ＋＝
*S
*
S r *S
*
S
*S
*
S
N V A r f
S S
v f r S S
v v
v v
v *f r *S
*
S
*f N V A r
*f N *f
*f
f ijf N r
ijr ijf
1
min
－ 当 ＋≠ （6-5）
＝
∞ 当 ＋＝
＝min（ ， ）
构造一个新的可行流，令
＋ 当（ ， ）∈ ＋
＝ － 当（ ， ）∈
－ （6-6）
当（ ， ）
则 ＝( )也是 的一个可行流，其流量为
（ ）＝ （ ）＋ （6-7）
定理 6-4 表明：只要网络中还存在关于可行流 的增广链 ，则 就非最
大流，起码其流量还能增大 ．这样就给出了一种沿着增广链上的各弧去调整
流量，从而得到一个流量增大 的新可行流 的方法，故称之为增广链调整
法．
三、寻求网络最大流的标号法
这种标号法由福特(Ford)和富尔克逊(Fulkerson)于 1956 年提出，故称为福
特一富尔克逊标号法(Ford- Fulkerson algorithm)．
1．基本算法思想：该法从某一可行流 出发，按一定规则找出一条增广
链 ( )，并按定理 8-6 的方法调整 ，得到一个流量增大 的新可行流 ．对
重复上述做法直到找不出增广链为止，这时就得到一个最大流，同时还得到
一个最小截集．
ijr ijf
2
min
1 2
ijf iv jv
'
ijf ijf iv jv
ijf iv jv
'f 'ijf N
v ijf v ijf
f f
f '
f
f f 'f
'f
2．算法步骤
（1）给出一个初始可行流 ．初始可行流可以是零流或非零流；
（2）标号、检查过程：
给顶点标号，标号用[ ，L( )]表示，其中第一个分量表示该标号是从哪
个点得到的，用以反向追踪找出增广链 ，第二个分量是为确定 的调整量
用的．
∈点 标号(0，∞)，则 已标号待检查；
∈取一个已标号待检查的点 ，所谓检查是对所有与 相邻而未标号的点
依次执行下述 a）、b）两种考察：
a）若联结 与 的弧( ， )为前向弧，则当该弧上的流量小于容量，即
＜ 时给 标号[ ，L( )]，其中 L( )＝min（L( )， 一 ）．这里
L( )表示弧( ， )上流量的最大可调整量．而当弧( ， )上的 ＝ 时，
弧( ， )是饱和前向弧，则不给 标号．
b）若关联 与 弧( ， )为后向弧，则当该弧上的流量大于零，即 ＞
0 时给 标号[- ，L( )]，其中 L( )＝min[L( )， ]．而当 ＝0 时不给
标号．
当所有 与相邻而未标号的点 都完成了 a）、b）两种考察后，给 打√，
表示对它的检查完毕．
∈重复∈，如果终点 得到标号，则可以从 沿标号点回溯到第一个标号，
从而找出一条从 到 的增广链，转至∈；如果所有标号点均已打√，而 t 又未
得标号．这说明不存在关于当前可行流的增广链，由定理 6-3 可知当前可行流
即最大流，算出流量，计算停止．
f
iv jv
sv sv
iv iv
jv
iv jv iv jv
ijf ijr jv iv jv jv iv ijr ijf
jv iv jv iv jv ijf ijr
iv jv jv
iv jv jv iv jif
jv iv jv jv iv jif jif jv
iv jv iv
tv tv
sv tv v
∈取增广链的流量调整量 ＝L（ ），对增广链上的流量进行调整，对增
广链上的前向弧，令
＝ ＋
对增广链上的后向弧，令
＝ －
非增广链上的弧流量不变．
∈删除原有所有标号，返回∈．
例 6-10 用 Ford-Fulkerson 标号法求图 6-14 所示网络的最大流．
图 6-14
解 第一步：图中给出了网络的初始可行流；
第二步：首先给 s 以标号(0，∞)，此时待查点是 ，相邻而未标号的点有
、 ．
检查 ：弧( ， )， ＝ ＝3，为饱和前向弧，所以不对 标号．
弧( ， )， ＜ ，为非饱和前向弧，所以给点 标号[ ，L( )]．其
中 L( )＝min{ L( )， － }＝min{∞，5－1} ＝4.
检查完成，对其打√．此时 有了标号成为待查点，相邻而未标号的点
有 、 ，如图 6-15（a）所示．
检查点 ：弧( ， )， ＝ ，为饱和前向弧，所以不对 标号.
弧( ， )， ＞0，为非零流后向弧，所以给 标号[－ ，L( )]，其
中 L( )＝min{ L( )， 12}＝min{4，1} ＝1.
tv
'
ijf ijf
'
jif jif
v sv
1v 2v
sv sv 1v 1sf 1sr 1v
sv 2v 2sf 2sr 2v sv 2v
2v sv 2sr 2sf
sv 2v
1v 4v
2v 2v 4v 24f 24r 4v
1v 2v 12f 1v 2v 1v
1v 2v f
检查完成，对其打√．此时完成检查的点有 、 ， 因有了标号成为
待查点，相邻而未标号的点有 、 如图 6-15（b）所示．
检查点 ：弧( ， )， ＜ ，为不饱和前向弧，所以给 标号[ ，
L( )]，其中 L( )＝min{ L( )， － }＝min{1，4－3} ＝1.
弧( ， )， ＜ ，为不饱和后向弧，所以给 标号[- ，L( )]，其
中 L( )＝min{ L( )， － }＝min{1，2－1} ＝1.
检查完成，对其打√．此时完成检查的点有 、 、 ， 和 因有了
标号成为待查点，相邻而未标号的点有 ．如图 6-15（c）所示.
检查点 ：弧( ， )， ＜ ，为不饱和前向弧，所以给 标号[ ，
L( )],其中 L( )＝min{ L( )， － }＝min{1，5－3} ＝1.
检查完成，对其打√．由于 已得到标号，已经可以得到一条增广链，
不需再检查 （如果检查 而不检查 可以得到另一条增广链，可自行验
证）,如图 6-15（d）所示．
图 6-15（a）、（b）、（c）、（d）
第三步：利用各点已标号的第一个分量，从 反向追踪得增广链 ＝{ ，
， ， ， }，如图 6-15（d）中粗箭头线所示．其中前向弧 ＋＝{( ，
)、( ， )、( ， )},后向弧 －＝{( ， )}.
由 标号的第二个分量知 ＝1，于是在已知增广链上进行调整：
＝ ＋ ＝1＋1＝2 （ ， ）∈
＋
＝ ＋ ＝3＋1＝4 （ ， ）∈
＋
＝ ＋ ＝3＋1＝4 （ ， ）∈ ＋
2v sv 2v 1v
3v 4v
1v 1v 3v 13f 13r 3v 1v
3v 3v 1v 13r 13f
1v 4v 14f 14r 4v 1v 4v
4v 1v 14r 14f
1v sv 2v 1v 3v 4v
tv
3v 3v tv tf 4 tr4 tv 3v
tv tv 3v tr4 tf 4
3v tv
4v 4v 3v
tv sv
2v 1v 3v tv sv
2v 1v 3v 3v tv 1v 2v
tv
'
2sf 2sf sv 2v
'
13f 13f 1v 3v
'
3tf tf3 3v tv
＝ － ＝1－1＝0 （ ， ）∈
－
＝ （ ， ）
调整后的可行流如图 6-16 所示．对这个新的可行流重新在图中进行标号，
寻找新的增广链．
图 6-16
第四步：再标号
给 以标号(0，∞)，检查 ：弧( ， )为饱和前向弧， 不标号．弧
( ， )为非饱和前向弧， 标号[ ，L( )]，L( )＝3.
检查 ：弧( ， )为零流后向弧， 不标号．弧( ， )为饱和前向弧，
不标号．
此时已标号的点均已打√，而 又未得标号，由算法步骤∈可知网络中不
存在增广链，目前的可行流就是最大流．
第五步：确定最小截集和最大流量
此时已标号且打√的点构成 集，而未标号的点构成 集，最小截集为( ，
)．如图 6-16 所示, ＝{ ， }, ＝（ ， ， ， ）．
最小截量 ( ， )＝最大流量 ＝ ＋ ＝5.
第五节 最小费用流问题
在实践中，人们考虑网络流问题不仅仅考虑流量，还必须考虑流的费用．例
如，在运输网络中，从发点 到收点 所经过的路程，往往因为交通工具不同或
道路本身结构不同而产生各段路程交通费用不同，这时问题就变成了不仅要求
到 的一定运输量，而且要求这种运输方案的总费用最小．这类问题就属于本节
'
12f 12f 1v 2v
'
ijf ijf iv jv
sv sv sv 1v 1v
sv 2v 2v sv 2v 2v
2v 1v 2v 1v 2v 4v
4v
tv
*S
*
S S
S *S sv 2v
*
S 1v 3v 4v tv
r *S
*
S *f 1sf 24f
sv tv
sv
tv
要介绍的最小费用流问题(min-cost-flow)．
一、最小费用流算法
在给定网络 =( ， ， )中，对每条弧( , )∈ ，除已给出弧容量
外，还给出单位流量的费用 0．设 ={ }是 中的可行流，其流量总费用
为 （ ）=∑ ．最小费用流问题是考虑在给定可行流量条件下，使得总费
用 （ ）最低．因此其数学模型为：
( )=min
在最小费用流问题中，有很大一部分是寻求使 （ ）为最小且流量 为
最大流的流量方案．这是最小费用流的特例问题，称为最小费用最大流问题．
1．求最小费用流的基本思想是：从零流（ ）=0 的费用有向图 （ ）
开始，先用一定方法寻找关于 的从 到 的最小费用增广链 ，并对 按
Ford—Fulkerson 标号法进行流量的调整，得到一个新的可行流 ，新的可行流
必是最小费用可行流．如果 ( )达到流量目标要求，则计算终止．否则，重新
构造关于 的费用有向图 N（ ），继续在 （ ）上求出由 到 的最小费用
增广链 ，并在 上进行流量的调整，如此下去，直到求出目标流量为 的可行
流 为止．如果 是最大流的流量，则此最小费用流就是最小费用最大流．由此
可见，求最小费用流的方法就是求最小费用增广链和求最大流方法的综合．
所谓最小费用增广链，即诸多增广链中费用权之和最小的一条增广链．其求
算方法要借助于网络 N 的辅助赋权有向网络 ．
2．辅助赋权有向网络 构造方法
是原图 的辅助图，构造 的目的是为了在 中寻找关于最小费
用可行流 的从 到 的最小费用增广链 ．构造 时，总体上是要将 N 中
A D N S
N V A r iv jv A ijr
ijb f ijf N
b f ijb ijf
b f
*b f
Avjvi ),(
ijb ijf
b f )( fv
0f N 0f
0f sv tv 0 0
1f
v 1f
f 1f N 1f sv tv
1 1 v
f v
)( fL
)( fL
)( fL N )( fL N
f sv tv )( fL
所有可能的弧流量变动特性集中表现于 中，并同时为它们的弧重新赋权，
具体方法如下：
设 L（ ）＝( ， ， ， )，其中的 ， ， ， 分别是网络
的点集，弧集、弧容量和费用集，它与 （ ， ， ， ）的关系如下：
(1)顶点集： （L）＝ （ ），即 的顶点即原有的网络 N 的顶点．
(2)弧集 及方向和赋权方法：
∈A 集中的零流弧：这类弧流量的变动只能增加弧流量，这一流变动特性，
在原图 中已充分体现，因此在 集中，弧的方向与原 中的相同，赋权不
变；
∈ 集中的饱和弧：这类弧流量的变动只能减少流量，因此在 集中，弧
的方向与原 中的相反，赋权： ＝－ ； ＝ ；
∈ 集中的非饱和、非零流弧：这类弧的流量变动，既可增流又可减流．因
此在 集中，点 , 之间，应该有正反两个方向的弧同时存在，其中方向与原
中相同的弧 ( , ) 上 ＝ － ， ＝ ．方向与原 中相反的弧
( , ) 上 ＝ ， ＝－ ．
例 6-11 已知原图 （图 6-17 所示），其弧权的含义为（ ， ， ），
求其辅助赋权网络 ．
图 6-17
解 （1）N 中零流弧只有一条 ，在 L 中该弧的方向、赋权均不
变．
（2） 中饱和流弧也只有一条 ，在 L 中该弧的方向相反，赋权改
变： ＝－ ＝－2， ＝ ＝4．
（3）N 中非饱非零弧有三条 、 、 ，这些弧在 L 中分
别有相应的正、反向两条弧存在，赋权情况：
)( fL
f V ' A ' 'r 'b V ' A ' 'r 'b
)( fL N V A r b
V ' V N )( fL
A '
N A ' N
A A '
N jib ' ijb
'
jir ijf
A
A ' iv jv
N iv jv
' '
ijr ijr ijf
'
ijb ijb N
jv iv
' '
jir ijf
'
ijb ijb
N r f b
)( fL
),( 21 vv
N ),( 31 vv
'
31b 13b
'
31r 13f
),( 23 vv ),( 42 vv ),( 43 vv
： ＝ － ＝5－2＝3； ＝ ＝2
： ＝ ＝2； ＝－ ＝－2
： ＝ － ＝4－2＝2； ＝ ＝2
： ＝ ＝2； ＝－ ＝－2
： ＝ － ＝3－2＝1； ＝ ＝4
： ＝ ＝2； ＝－ ＝－4
综上，构造原图 N 的辅助图 ，如图 6-18 所示弧旁数字为（ ，
）．
图 6-18
在 中找关于 的从 到 的最小费用增广链，就等价于在赋权有向网络
中，找从 到 的最小费用链．这样，就把在 N 中寻找最小费用增广链问
题转化为在 中寻找最小费用链问题，而这在形式上等同于在 中寻找最
短路．
3．最小费用流算法步骤
第 1 步：从一流量为 （ ）的初始最小费用可行流 开始，( 也可以
是零流， =0)，在第 －1 步得到最小费用可行流记为 ．
第 2 步：构造辅助赋权有向网络 L（ ），并在 L（ ）中求 到 的最
小费用链 ，若不存在最小费用链 ，则此时的 即为最小费用最大流
(转第 4 步)；若存在最小费用链 ，则在 中得到相应的最小费用增广链
(转第 3，流调整)．
第 3 步：在最小费用增广链上按照定理 6-6 作调整，得到新的最小费用可行
流 k，若 k 已经达到目标流量转第 4 步，否则转第 2 步，重复．
第 4 步：停止运算，并输出当前最小费用可行流 ，作为 中的最小费
),( 23 vv
' '
32r 32r 32f
'
32b 32b
),( 32 vv
' '
23r 32f
'
23b 32b
),( 42 vv
' '
24r 24r 34f
'
24b 24b
),( 24 vv
' '
42r 24f
'
42b 24b
),( 43 vv
' '
34r 34r 34f
'
34b 34b
),( 34 vv
' '
34r 34f
'
43b 34b
)( fL r
b
N f sv tv
)( fL sv tv
)( fL )( fL
v 0f 0f 0f
0f k 1kf
1kf 1kf sv tv
)1( k )1( k
1kf
)1( k N
)1( k
f f
1kf N
用最大流；或输出当前最小费用可行流 流量作为 中流量 （ ）＝ 的最
小费用流．
二、实例
例 6-12 试求图 6-19 网络 （ ）＝7 的最小费用流和最小费用最大流
（弧旁的数字为（ ， ），其中 表示弧容量， 表示单位物质运费）．
图 6-19
解 （一）求流量为 7 的最小费用流
（1）因为原图流量 ＝0，故先利用 Dijkstra 标号法对图 6-19 的网络求
最小费用链，显然这时的最小费用链即是最小费用增广链：
＝∈ ∈ ∈ ∈ ∈ ∈，如图 6-20（a），
调整量 ＝min{ （ － ）， }={7，5，5，7，5}=5，按照定理 6-6
对 上的各弧进行流量调整，调整后 上各弧流量：
∈ ∈ ∈ ∈ ∈ ∈，
同时 （ ）＝ ＋ ＝0＋5＝5．如图 6-20（b）．
（2）在图 6-20（b）中寻找从∈到∈的最小费用增广链．为此对图 6-20
（b）作辅助赋权有向网络 L（ ）：
A 集中：∈ ∈，∈ ∈，∈ ∈，∈ ∈ 均为零流弧；A 集中相应的弧
不变．
A 集中：∈ ∈，∈ ∈，∈ ∈均为饱和前向弧；A 集中相应的弧方向
反转，赋权－ ．
A 集中：∈ ∈，∈ ∈均为不饱和前向弧；A 集中相应的弧不变，添加
反方向的弧并赋权－ ．得到图 6-20（c）．
图 6-20（c）是图 6-20（b）的辅助赋权有向网络，其构造目的是寻找图
kf N v f kf
v f
ijr ijb ijr ijb
0f
0
min ijr ijf
min ijf
0 0
5 5 5 5 5
v 1f 0f
1f
'
'
ijb
'
ijb
6-20（b）中有关 的从 到 的最小费用增广链 ，我们知道 等价于图
6-20（c）中的从 到 的最小费用链（或最短路）．
求图 6-20（c）的最短路：由于图 6-20（c）含有负权，不能使用 Dijkstra
标号法，可以用逐次逼近法求得图 6-20（c）网络的最小费用链 ：∈ ∈
∈ ∈，如图 6-20（c）中粗线所示； 也是图 6-20（b）中关于 的从 到
的最小费用增广链．
回到图 6-20（b），对 进行调整：
＝min{ （ － ）， ij }
＝ （ － ）
＝min{（7－5），（7－0），（15－0）}
＝2
调整后 上各弧的流量为：∈ ∈ ∈ ∈，同时 （ ）＝ （ ）
＋ ＝5＋2＝7，如图 6-20（d）所示．
（3）作图 6-20（d）的辅助赋权有向网络（如图 6-20（e）所示），其中
不存在负回路，证明图 6-20（d）所示的网络流是 =7 的最小费用可行
流．(这里不加证明地引入 为 中流量为 的最小费用流的判别条件：
为 中流量为 的最小费用流的充要条件是，相应的 中没有负回路．即
中的任意回路 C，有 0)．
（二）求图 6-19 的最小费用最大流
承接以上结果对图 6-20（e）所示网络，求其最小费用链得 为 ∈ ∈
∈ ∈ ∈， ＝5， （ ）＝12．
调整后 上各弧的流量为：∈ ∈ ∈ ∈ ∈，
如图 6-20（f）所示．
对图 6-20（f）所示网络作辅助赋权有向网络如图 6-20（g），求其最小费
1f 1v 6v 1 1
sv tv
1
1
1f 1v 6v
1
1
min ijr ijf min f
min ijr ijf
1
7 2 2 v 2f v 1f
)( fv
f N )( fv f
N )( fv )( fL
)( fL
Cvv
ij
ji
b
),(
2
v 3f
2
5 5 0 7
用链得 为 ∈ ∈ ∈ ∈ ∈， ＝5， （ ）＝17．
调整后 上各弧的流量为：∈ ∈ ∈ ∈ ∈，
得到图 6-20（h）所示网络．
对图 6-20（h）所示网络作辅助赋权有向网络图，其中不存在从 到 的
通路，说明图 6-20（h）所示网络流为最小费用最大流．
图 6-20（a）（b）（c）（d）（e）（f）（g）（h）
第六节 网络计划（统筹方法）
网络计划（Network Planning）是一种计划管理的科学方法，它是编制大型
工程进度计划的有效工具．对于计划人员清楚地掌握整个工程进度，预见可能发
生的问题，协调和控制各项活动，达到合理组织，统筹安排，使工程任务能顺利
地按期或提前完成，起到了重要的作用．已故著名数学家华罗庚先生将这些方法
总结概括为统筹方法．
一、统筹图的基本概念和基本规则
统筹图（project diagram）也可称为工序流程图，它可以直观地反映组成管
理的各项活动及其相互间的内在关系．正确、完备、详尽的统筹图是网络计划工
作必不可少的前提和工具．
(一)工程的分解及工序间的关系
工序：根据工艺技术和组织管理上的需要，将工程划分为按一定顺序执行
而又相对独立的若干项活动，这些活动称为工序．在统筹图上，工序 k 用箭线
“ ”表示．工序 也可以用（ ， ）表示．对于相邻工序，如工序 a 与工序
b、c 相邻，工序 b、c 都需要在工序 a 完工后才能开工，则称工序 a 为工序 b、c
的紧前工序；称工序 b、c 为工序 a 的紧后工序．
事项：表示一道或多道工序的开工或完工的特定时间点称为事项．在统筹
3 v
4f
3
10 0 7 12
1v 6v
k k i j
图上，事项用注有编号的圆圈结点表示．如“∈ ∈”中的 ∈，∈．并规定工
序的开工事项的序号小于完工事项的序号，即 ＜ ．工序的开工事项与完工事
项统称工序的相关事项．
统筹图最左端的结点是始点事项，表示工程开工，它无前导工序．最右端
的结点是终点事项，表示工程完工，它无后继工序．其它事项既表示某一工序的
开工又表示某一工序的完工．
工序时间：完成一道工序所需的时间简称工序时间．
根据上述基本概念，我们在编制工程计划之前，必须通过分析研究，把一项
工程分解为若干道工序，确定出各工序之间的前后顺序及相互关系，以及完成各
道工序所需要的时间．
有了工程经过分解后的工序资料，即可列出工序一览表．有了工序一览表后，
即可绘制统筹图．
（二）统筹图的绘制规则
1．关于工序表示的规定
工序必须用唯一意义的结点组合来表示．即一条箭线和与它相关联的结点，
只能表示一道工序及其开工和完工．任何两道或多道工序不能用同一结点组合表
示．图 6-21（a）的画法错误的，因为（1，2）表示两道工序 a、b．
图 6-21
工序的组合不能形成循环或组成回路，否则组成回路的工序将永远无法完
工．图 6-21（b）的画法中工序 a、b、c 形成了循环，不允许．
2．关于虚工序的规定
虚工序：虚工序是虚设的，即不花时间和资源的非实际工序，只用来表达
相邻工序之间的衔接关系及其它需要．在统筹图上用虚线表示虚工序．
有了虚工序的规定，就能在统筹图中准确地建立起各工序间的逻辑关系．如
a、b、c、d 的工序关系是：c 必须在 d、b 均完成后才能开工，而 d 只要在 b 完
k
i j
成后即可开工．也就是说，a、b 是 c 的紧前工序，而只有 b 是 d 的紧前工序．这
样必须用图 6-22 来表示，其中 ∈ ∈ 是一个虚工序，只表示 ∈、∈ 两节点的
衔接关系，不需要人力、物力等资源和时间．
图 6-22
3．关于始点与终点的规定
始点是表示工程的总开工时间，终点是表示工程的总完工时间，因此，始点
与终点也只能各有一个．除始点与终点外，其它结点必须前后都有箭线连接．在
图 6-23(a)中始点不合要求，可利用虚工序绘作如图 6-23(b)所示．把始点或终点
合并为一个，也是虚工序的作用之一．
图 6-23
4．平行工序
一道工序分为几道工序同时进行，称为平行工序．在统筹图中，利用虚工序
来表示这种关系．图 6-24 所示：工序 b、c 是平行工序．虚工序 e 则表示在工序
b、c 完工后才能进入工序 d．
图 6-24
为便于今后确定关键路线，规定当某一工序的紧前工序是几道工序平行作业
时，选择其中工序时间最长的工序与该工序直接连接，其它工序则通过虚工序与
该工序连接．
5．交叉作业
为了缩短工期，还经常采用交叉作业的方式．对需要较长时间才能完成的相
邻几道工序，采用分段平行作业，即相邻两道工序在前一工序未全部完成就开始
后一工序作业，这就是交叉作业．
两个或两个以上的工作交叉进行，称为交叉作业．如工作 a 与工作 b 分别为
挖沟和埋管子，那么它们的关系可以是挖一段，埋一段，不必等沟全部挖好再
埋．把工序 a 和 b 都分为 3 段，a＝a1＋a2＋a3；b＝b1＋b2＋b3．这样，我们可用
图 6-25 来表示交叉作业．
图 6-25
根据上述规则绘制网络图，是为了保证网络图的正确性．此外，为了使图面
布局合理，层次分明，条理清楚，还要注意画图技巧．避免弧的交叉，尽可能将
关键路线布置在中心位置，将联系紧密的工序布置在相近的位置．
例 6-13 某项新产品投产前全部准备工作如表 8-6 所示（各工序与所需时
间以及它们之间的相互关系）．要求编制该项工程的网络计划．
表 8-6 各工序与所需时间以及它们之间的相互关系
工序 工序内容 紧前工序 时间（周）
A 市场调查 — 4
B 资金筹措 — 10
C 需求分析 A 3
D 产品设计 A 6
E 产品研制 D 8
F 制定成本计划 C，E 2
G 制定生产计划 F 3
H 筹备设备 B，G 2
I 原材料准备 B，G 8
J 安装设备 H 5
K 人员准备 G 2
L 准备开工投产 I，J，K 1
根据以上规则，绘制的网络图如图 6-26 所示．
图 6-26
二、时间参数计算
计算网络图中有关的时间参数，主要目的是找出关键路线，为网络计划的优
化、调整和执行提供明确的时间概念．
网络图的时间参数包括工序所需时间、事项最早、最迟的时间，工序的最早、
最迟时间及时差等，下面分别叙述．
1．工序时间 （ ， ）的确定
工序（ ， ）的所需时间可记为 （ ， ），可以根据 （ ， ）的数据情
况将网络图分为确定型和概率型两种情况：
(1)确定型：完成工序所需时间确定为唯一的时间值．在具备劳动定额资料
的条件下，或者在拥有类似工序的作业时间消耗的统计资料时，完成工序所需的
时间往往是确定的．
(2)概率型：在影响工序因素较多，作业时间难以准确估计时，可以采用三
点时间估计法来确定作业时间：
——最快可能完成的时间
——最可能完成的时间
——最慢可能完成的时间
在一般情况下，可按下列公式近似估算作业时间：
（ ， ）＝ （6-7）
2＝（ ）2 （6-8）
概率型网络图与确定型网络图在工序时间确定后，对其他时间参数的计算基
本相同．
2．事项的时间参数
(1) 事项最早时间：事项 的最早时间用 表示，它表示以 为始点的各
工序最早可能开始的时间，也表示以 为终点的各工序的最早可能完成的时
间．它等于从始点事项起到本事项最长路线的时间长度．事项最早时间可用下列
递推公式，按照事项编号从小到大的顺序逐个计算：
t i j
i j t i j t i j
a
m
b
t i j
6
4 bma
6
ab
j )( jtE j
j
＝0
＝ { ＋ （ ， ）} （6-9）
式中， 为与事项 j 相邻的各紧前事项的最早时间．
(2) 事项的最迟时间：事项 i 的最迟时间用 表示，它表明在不影响任务
总工期的条件下，以它为始点的工序的最迟必须开始时间，或以它为终点的各工
作的最迟必须完成的时间．在一般情况下，把任务的最早完工时间作为任务的总
工期，所示事项最迟时间的计算方法如下：
＝ （ 为终点事项）
（ ）＝ {（ － （ ， ））}
（6-10）
式中 为与事项 相邻的各紧后事项的最迟时间，它的计算从终点事项开始，
按编号由大到小的顺序逐个计算．
3．工序的时间参数
(1) 工序的最早开工的时间和最早完工的时间：—个工序（ ， ）的最早开
工时间用 （ ， ）表示，任何—个工序都必须在其所有紧前工序全部完工后
才能开始．工序（ ， ）的最早完工时间用 （ ， ）表示，它表示工作按
最早开工时间开始所能达到的完工时间．计算公式如下：
（1， ）＝0
（ ， ）＝ { （ ， ）＋ （ ， ）}
（6-11）
（ ， ） ＝ ES （ ， ） ＋ （ ， ）
（6-12）
工序（ ， ）的最早开工时间 （ ， ）等于事项 的最早时间 （ ）．
(2) 工序的最迟开工时间与最迟完工时间：一个工序（ ， ）的最迟开工时
)1(Et
)(itE
i
max )(itE t i j
)(itE
)(itL
)(ntL )(ntE n
Lt i jmin )( jtL t i j
)( jtL i
i j
ESt i j
i j EFt i j
ESt j
ESt i j
k
max ESt k j t k i
EFt i j t i j t i j
i j ESt i j i Et j
i j
间用 （ ， ）表示，它是工序（ ， ）在不影响整个任务如期完成的前提下，
必须开始的最晚时间．工序（ ， ）最迟完工时间用 （ ， ）表示，它表示
工作（ ， ）按最迟时间开工，所能达到的完工时间．
（ ， ）＝ （ ）
（ ， ）＝ { （ ， ）－ （ ， ）} （6-13）
（ ， ）＝ （ ， ）＋ （ ， ）
（6-14）
工序（ ， ）最迟必须完工时间 （ ， ）等于事项 的最迟时间 （ ）．
4．时差
(1)工序总时差 （ ， ）：工序总时差的含义是，在不影响工程最早结束
时间的条件下，工序最早开始或最早结束时间可以推迟的时间：
（ ， ）＝ （ ， ）－ （ ， ）
（6-15）
(2)工序单时差 （ ， ）：工序单时差的含义是，在不影响紧后工序最早
开始时间的条件下，工序最早结束时间可以推迟的时间：
（ ， ）＝ （ ， ）－ （ ， ）
（6-16）
式中， （ ， ）为工序（ ， ）的紧后工序的最早开始时间．
总时差为零的工序，开始和结束时间没有机动余地，称为关键工序，由这些
工序组成的路线在时间上也没有机动余地，构成了整个工程耗时最长的路线．
三、关键路线分析
网络分析的根本任务之一就是找出关键路线(CP)，华罗庚先生称它为主要矛
盾线：二是找出非关键路线各工序的时差；三是利用“向关键路线要时间，向非
关键路线要资源”的指导思想，做出最优或满意的工程计划．
LSt i j i j
i j LFt i j
i j
LSt i n Et n
LSt i j kmin LSt j k t j k
LFt i j LSt i j t i j
i j LFt i j j Lt j
R i j
R i j LFt i j EFt i j
r i j
r i j ESt j k EFt i j
ESt j k i j
在网络计划图（或统筹图）中，最长的路称为关键路线，或称主要矛盾线，
关键路线上的工序称为关键工序．
根据定义可以得到三种寻找关键路线的方法：
（1）从工序时间入手，寻找从起点事件到终点事件累计工序时间最长的工
程路线．这种方法相当于网络最长路问题，实际操作中不常用．
（2）关键路线是有关键工序组成，通过寻找关键工序可以得到关键路线．关
键工序的特征是工序总时差 （ ， ）为零，可以通过时间参数计算找出工序
总时差为零的工序，从而找出关键路线．
（3）关键路线是统筹图上的最长路，这意味着路线上各事项（结点）时间
没有机动余地．所以关键路线上任意事项（结点）的最早时间 （ ）等于该事
项的最晚时间 （ ），称为关键事项（结点）．通过计算关键事项（结点）也可
以找出关键路线．
例 6-14 图 6-27 是一项工程的网络图，箭杆上的数字是表示活动的延续
时间 （ ， ），结点内的数字是表示事项的编号．试求每个事项、工序的开
始时间与结束时间、关键路线及其相应的关键工序，从而给出寻找关键路线的
方法．并求出完成此工程项目所需的最少时间．
图 6-27
解 为了在网络图上方便、有效地表示事项、工序时间，我们规定：
事项时间以双方框标在结点上方，左边方框填写事项最早时间 （ ），右
边方框填写事项最迟时间 （ ）．工序时间用四分圆标在工序箭竿的上方，左
上 ；左下 ；右上 ；右下 ．
（一）事项（结点）时间计算
(1)事项的最早时间 （ ） 它的计算是从始点开始，自左至右逐个结点
向前计算，直至最后一个结点为止．若结点只有一个箭杆进入的话，箭头结点
的最早开始时间等于箭尾结点的最早时间与活动延续时间的和；若结点有数个
箭杆进入的话，则对每个箭杆都做如上计算后，从中选最大值作为该结点的最
早时间，计算结果写入该结点上方框内．
R i j
Et i
Lt i
t i j
Et i
Lt i
ESt LSt EFt LFt
Et i
从结点∈开始
（1）= 0
（2）= （1）+ （1，2）= 0+1=1
（3）= （1）+ （1，3）= 0+8=8
（4）= （1）+ （1，4）= 0+6=6
如果在该结点结束的工序有两个以上，结点最早时间应选取箭尾最早时
间与箭杆时间之和最大者．
图中在结点(事项)∈结束的活动有(2，5)，(4，5)两根箭杆，则计算结果是：
（5）= max{[ （2）+ （2，5）]，[ （4）+ （4，5）] }
= max{[1+2]，[6+5]}=11
在结点∈结束的工序有(3，6)、(4，6)，其结点最早时间是；
（6）= max{[ （3）+ （3，6）]，[ （4）+ （4，6）] }
= max{[8+5]，[6+9]}=15
在结点∈结束的活动(4，7)、(5，7)，(6，7)，其中（6，7）是虚工序，计
算结果是：
（7）= max{[ （4）+ （4，7）]，[ （5）+ （5，7）]，
[ （6）+ t（6，7） ]}
= max{[6+4]，[11+3]，[15+0]}=15
在结点∈结束的活动有(6，8)，(7，8)，其计算结果是：
（8）= max{[ （6）+ （6，8）]，[ （7）+ （7，8）] }
= max{[15+4]，[15+6]}=21
现将计算结果填入网络图各结点的上方双方框的左框，如图 6-28．
(2)事项最迟时间 （ ） 它的计算是从终点(最后的结点)开始，自右向
左逐个结点后退计算，直至最前一个结点(始点)止．
一个箭杆尾部结点的最迟时间，由它的箭头结点的最迟时间减去箭杆时
间来决定．若结点只有一个箭杆尾部，则结点最迟结束时间为箭头结点的最迟
Et
Et Et t
Et Et t
Et Et t
Et Et t Et t
Et Et t Et t
Et Et t Et t
Et
Et Et t Et t
Lt j
结束时间减去箭杆时间，若结点有数个箭尾，对每个箭杆都作如上计算后，取
其中最小的作为该结点的最迟结束时间，计算结果填入结点上方的方框内，具
体计算如下．
因终点的最迟时间就等于最早时间，即 （n）= （n），也就是工程的
总工期最后结点(即终点)编号的时间．在此网络中 （8）= （8）= 21
在结点∈： （7）= （8）－ （7，8）= 21－6 = 15
在结点∈： （6）= min{[ （8）－ （6，8）]，[ （7）－ （6，
7）]}
=min{[21－4]，[15－0]}= 15
在结点∈： （5）= （7）－ （7，5）= 15－3 = 12
在结点∈： （4）= min{[ （5）－ （4，5）]，[ （7）－ （4，
7）]，
[ （6）－ （4，6）]}
=min{[12－5]，[15－4]，[15－9]}= 6
在结点∈； （3）= （6）－ （3，6）= 15－5 = 10
在结点∈； （2）= （5）－ （2，5）= 12－2 = 10
在结点∈(始点)：
（1）= min{[ （2）－ （1，2）]，[ （4）－ （1，4）]，
[ （3）－ （1，3）]}
=min{[10－1]，[6－6]，[10－8]}= 0
将计算结果填入图 6-28 各结点的上方双方框的右框．
图 6-28
(3) 结点的时差 由以上计算得到结点或事项的时间参数 （ ）、 （ ）
Lt Et
Lt Et
Et Lt t
Lt Lt t Lt t
Lt Lt t
Lt Lt t Lt t
Lt t
Lt Lt t
Lt Lt t
Lt Lt t Lt t
Lt t
Lt i Et i
计算结点的时差：
结点 i 的时差＝ （ ）－ （ ）
结点时差表明进入该结点的各活动，在不影响其紧后工序开工的前提下，
最迟可延长多少时间再完工，时差为 0 的结点叫关键结点．图 6-28 得到了关
键结点，按照方法（3）已经得到了关键路线．
（二）工序时间计算
（1）工序最早开始时间 计算是从第一项活动起，自左至右，直到
最后一项活动为止，具体计算如下：
（1，2）= （1）= 0
（1，3）= （1）= 0
（1，4）= （1）= 0
（2，5）= （1，2）+ （1，2）= 0+1=1
（3，6）= （1，3）+ （1，3）= 0+8=8
（4，5）= （1，4）+ （1，4）= 0+6=6
（4，6）= （1，4）+ （1，4）= 0+6=6
（4，7）= （1，4）+ （1，4）= 0+6=6
（5，7）= max{[ （2，5）+ （2，5）]，[ （4，5）+ （4，5）]}
=max{ [1+2]，[6+5]} = 11
（6，7）= max{[ （3，6）+ （3，6）]，[ （4，6）+ （4，6）]}
=max{ [8+5]，[6+9]} = 15
（7，8）= max{[ （5，7）+ （5，7）]，[ （4，7）+ （4，7）]，
[ （6，7）+ （6，7）]}
=max{ [11+3]，[6+4]，[15+0]} = 15
（6，8）= max{[ （4，6）+ （4，6）]，[ （3，6）+ （3，6）]}
Lt i Et i
ESt
ESt Et
ESt Et
ESt Et
ESt Et t
ESt Et t
ESt Et t
ESt Et t
ESt Et t
ESt Et t Et t
ESt Et t Et t
ESt Et t Et t
Et t
ESt Et t Et t
=max{ [6+9]，[8+5]} = 15
数据填入图 6-29 中四分圆的左上格内．
（2）活动的最早结束时间 工序的最早结束时间就等于工序最早开
始时间 （ ， ）加上工序时间 t（ ， ），另外工序最早开始时间等于该活
动箭杆尾部结点的最早时间 tE（ ）．由于前面已经得到了 （ ）和 （ ，
）可以在图上直接填写． 数据填入图 6-29 中四分圆的右上格．
（3）活动最迟开始时间 它等于箭头结点最迟时间 （ ）减去该工
序时间 t（ ， ），也可用紧后工序最迟开始时间减去该活动的延续时间，当
紧后活动有多个时，计算后取其中最小的值．
计算方法是从终点(最后结点)开始，自右向左，逐个活动计算，直至始点
止，具体计算如下：
（8）= （8）= 21
（7，8）= （8）－ （7，8）= 21－6 = 15
（6，8）= （8）－ （6，8）= 21－4 = 17
（5，7）= （7）－ （5，7）= 15－3 = 12
（4，7）= （7）－ （4，7）= 15－4 = 11
（2，5）= （5）－ （2，5）= 12－2 = 10
（4，6）= （6）－ （4，6）= 15－9 = 6
（3，6）= （6）－ （3，6）= 15－5 = 10
（1，4）= min{[ （4，5）－ （1，4）]，[ （4，7）－ （1，4）]，
[ （4，6）－ （1，4）]}
=min{[7－6]，[11－6]}，[6－6]]}=0
（1，2）= （2）－ （1，2）= 10－1 = 9
（1，3）= （3）－ （1，3）= 10－8 = 2
EFt
ESt i j i i
i Et i ESt i
j EFt
LSt Lt i
i j
Lt Et
LSt Lt t
LSt Lt t
LSt Lt t
LSt Lt t
LSt Lt t
LSt Lt t
LSt Lt t
LSt LSt t LSt t
LSt t
LSt Lt t
LSt Lt t
数据填入图 6-29 的四分圆左下格内．
（4）工序最迟结束时间 它等于工序最迟开工时间 （ ， ）加上
工序时间 （ ， ），或者说是等于该工序终了结点的最迟时间 （ ），可在
网络图上直接填写，数据填入图 6-29 中四分图的右下格内．
图 6-29
（三）时差
总时差就是工序的最迟开工与最早开工时间的差值，总时差越大，说明
工序的时间变动潜力越大，可以将用于该工序的资源调去支缓关键工序．总时
差为零的工序是关键工序．可以利用的图 6-29 的结果，计算各工序总时差
（ ， ）：利用公式将图 6-29 各工序上四分圆中左下数字减去左上数字或右
下数字减去右上数字，得到各工序的总时差． （ ， ）=0 的关键工序有：
（1，4）、（4，6）、（6，7）、（7，8）．
（四）确定关键路线和工程所需最少时间
关键路线即关键工序所连成的路线，或各关键结点的连线．从始点到终
点．将各个总时差为零(或结点时差为零)的活动串联起来即得到关键路线．
由图 6-28、图 6-29 结果，从右向左推寻可得到：（1，4）、（4，6）、（6，
7）、（7，8）或 ∈ ∈ ∈ ∈ ∈ 是关键路线．
由于关键路线上时差为零，没有机动时间．整个网络计划所需最少时间
就等于关键路线上各关键工序延续时间之和，有：
工程所需最少时间＝ （1，4）＋ （4，6）＋ （6，7）＋ （7，8）
＝6＋9＋0＋6＝21
这个结果已经反应在图 6-28 和图 6-29 中终点时间参数 （8）以及最后
一道工序时间参数 （7，8）、 （7，8）上了．
四、网络计划的优化
LFt LSt i j
t i j Lt j
R
i j
R i j
t t t t
Lt
LSt LFt
通过绘制网络图，计算网络时间参数，以及确定关键路线，得到的仅是一个
初步计划方案．为了得到一个从各方面都较好的方案，一般一项工程或任务的网
络计划，往往要根据项目的要求综合考虑进度、资源利用和降低费用等目标，进
行调整和改善．综合地考虑时间、资源和费用等目标，进行网络优化，确定最优
的方案．
（一）时间优化
欲对工程项目进行时间优化，必须抓住网络的关键路径，从各项关键活动中
设法提出改进方案．关键路径上各工序如果拖期，就会影响整个工程的如期完成，
若想压缩工程项目的完工期限，也必须从关键路径入手才能奏效，有时甚至要在
初步网络图上修订几次才能达到要求．
时间的调整和优化方法主要有：
1．采取技术措施，主要是利用新技术、新工艺、高质量的原材料，或投入
更多的人力、物力和设备，缩短工程完工时间．
2．在工艺流程许可的情况下，对关键路线上的各道工序组织平行作业或交
叉作业．
3．采取组织措施，充分利用非关键工序的总时差，考虑放慢非关键工序的
进度，合理调配人财物等资源去支援关键工序，缩短关键工序的作业时间．
（二）时间—资源的优化
网络计划的时间—资源优化，是指对时间和其他资源进行统筹安排，达到特
定的工程要求．一般情况下各项工程实施过程中的人员、设备及其他物力，财力
等可供利用的资源是有限制的．往往要求在有限的资源条件下合理分配资源，既
满足各项活动对计划的需求，又确保整个工程项目在尽可能短的时间内完成．
资源合理调配包括以下几个方面：
1．先安排关键工程所需资源；
2．错开非关键工序的开始时间，使工程各时段对资源的需求趋于平衡；
3．为达到总体效益最佳，必要时可适当延长总工期．
例 6-15 某市防疫站从下属单位抽调部分人员，进行一项疫情调查，整
个工作可分许多阶段(工序)，各阶段所需的时间和人员数量不等，具体见表 6-7，
问各阶段工作应如何合理安排，才可以使人力的使用最合理?
表 6-7 各工序所需的时间和人员数量
工序 工期 需人员数 紧前工序
a ∈ ∈ 4 10 —
b ∈ ∈ 2 5 —
c ∈ ∈ 2 7 —
d ∈ ∈ 2 4 —
e ∈ ∈ 3 9 b
f ∈ ∈ 2 8 c
g ∈ ∈ 3 3 f，d
h ∈ ∈ 4 2 e，g
i ∈ ∈ 3 12 a，h
解 （一）先作出网络图 6-30：
图 6-30
（二）根据网络图求解各工序的时间参数 、 、 、 、 （ ， ），
并列入表 6-8：
表 6-8 工序时间参数表
时间参数
工序
工
期
时
差
a ∈ ∈ 4 0 4 7 11 7
b ∈ ∈ 2 0 2 2 4 2
c ∈ ∈ 2 0 2 0 2 0
d ∈ ∈ 2 0 2 2 4 2
e ∈ ∈ 3 2 5 4 7 2
f ∈ ∈ 2 2 4 2 4 0
g ∈ ∈ 3 4 7 4 7 0
h ∈ ∈ 4 7 11 7 11 0
ESt EFt LSt LFt R i j
ESt EFt LSt EFt
i ∈ ∈ 5 11 14 11 14 0
可见关键路线为：∈ ∈ ∈ ∈ ∈ ∈．
为了表述的方便，以带有时间坐标的网络图来表示上述情况，并在图的
下半部分注明各个时间段需要的人员数量．
图 6-31（a）
如图 6-31（a），上下均标有时间坐标，有向弧上的数字为该工序所需人
数．下面直方图中的数字为这段时间内工序所需人数之和．
由图 6-31（a）可见，按以上方案执行，将使人力投放极不合理，前期人
力过于集中，而后期又人员稀少，应设法使整个过程中，人力分布基本均衡，
按本例实际情况，应使每天人数大体在 10 一 13 人之间．因此应该在保持网络
图基本框架不变以及总工期不变的前提下，调整工序的执行时间安排，使人力
投放尽量均匀、合理，其调整原则是：
(1)首先保证各道关键工序的人力需要．
(2)利用非关键路线上各工序的时差，调整非关键工序的开工时间．
本例的非关键工序为 ∈ ∈、∈ ∈、∈ ∈，时差分别为 7，2，2．为
此，调整如下：工序 ∈ ∈ 是非关键工序时差为 7，最有调整潜力，因此先
将它推迟 7 天开工，于是如图 6-31（b）:
图 6-31（b）
图 6-31（b）比图 6-21（a）已大有改进，前期人力过于集中的情况有所
缓解，但中间阶段需要的人员太少，为此将工序 ∈ ∈ 推迟 2 天开工如图 6-31
（c）：
图 6-31（c）
图 6-31（c）比图 6-31（b）又有改进．现再将 ∈ ∈ 推迟 2 天开工，
如图 6-31（d）:
图 6-31(d)
图 6-31（d）实现了人力的均匀安排，在本例中是最佳的资源配置．对于
简单的网络计划可以用本例方法进行资源优化，对于复杂网络应该利用数学规
划方法进行资源优化．
（三）时间—费用优化
工程所需时间与工程所需费用是一对矛盾．一般情况下，缩短一道工序时
间，就要采取一些措施，如加班，增加设备等，需要增加一定费用，同时也会得
到一些收益，如节约了管理费用等．要想缩短整个工程的工期，必须从两方面考
虑：一方面要分析缩短工期所需代价；另一方面要分析缩短工期带来得收益．在
一定条件下，达到工程时间与工程费用的最佳结合是网络计划时间—费用优化工
作的关键．
工程所需费用，基本上分为两大部分：
直接费用——完成工序直接有关的费用，如人力、机械、原材料等费用．
间接费用——管理费、设备租金等，是根据各道工序时间按比例分摊的．工
序时间越少，间接费用就越少；反之，工序时间越多，间接费用就越多．
工程总费用就是直接费用与间接费用的总和，即
W＝U＋V
式中 W 为工程总费用, U 为直接费用, V 为间接费用．
工程费用与完工期之间的关系可用图 6-32 表示．
图 6-32
从图 6-32 中可直观看出，在正常工期和最短工期(缩短工期的最低限度，也
简称赶工时间)之间，存在着一个最优工期，此时总费用最少．这个时间称为最
少工程费日程．从关键路线入手，找出最少工程费日程的方法，就是关键路线法
(CPM)．
为了简便起见，假设工序的直接费用与工序时间是线性关系，设工序 k 每
赶一天进度所需要增加的费用为 q（k），则
q（k）＝ （8-17）
式中 q（k）为费用斜率, c 为赶工所需费用, n 为正常完工所需费用, nt 为正常完
工所需时间, ct 为赶工时间．
显然，费用斜率越大的工序，每缩短一天，花的费用就越多．在考虑缩短
工程工期时，当然是要缩短各关键工序中的某一道或某几道工序的工期，而选择
缩短哪道工序要以总费用最省为根据．在赶进度完工时，其总费用为：
W＝Un＋（c—n）＋V （8-18）
式中 W 为总费用, Un 为正常完工的直接费用, （c—n）为赶工增加的费用, V 为
间接费用．
下面以例 6-16 说明通过缩短关键路线上工序时间来寻求最少工程费日程的
方法.
例 6-16 某项工程根据有关资料，计算出了费用斜率如表 6-9，试制定该
工程的最少工程费计划方案．
表 6-9 工程的有关资料及费用斜率
工序 紧前
工序
正常完工
时间（天）
正常完工直接费
用（百元）
赶工时间
（天）
费用斜率
（百元）
a / 10 30 7 4
b / 5 10 4 2
c b 3 15 2 2
d a,c 4 20 3 3
e a, c 5 25 3 3
f d 6 32 3 5
g e 5 8 2 1
h f, g 5 9 4 4
合计 149
间接费用 5（百元/天）
解 根据表 6-9，可绘出统筹图 6-33（a）:
tt
cn
nc
图 6-33（a）
按正常时间完工需 25 天，所需总费用为: Ｗ＝14900+500×25＝27400
元．
若使工程工期最短，即将所有工序时间都压缩到其可能的最短时间，看
其费用情况如何．这时，统筹图如图 6-33（b）所示．
图 6-33（b）
工程完工期为 17 天，其赶工增加费用(c－n)为:
3×400＋1×200＋1×200＋1×300＋2×300＋3×500＋3×100+1×400
＝4700 元.
总费用Ｗ＝14900+4700+500×17＝28100 元.
显然费用太大，不是最优．
现在，我们通过分析按正常时间完工的计划方案，进而找出最少工程费
方案．由图 6-23（b）可以看出，在按正常时间完工的统筹图中，有两条关键
路线：∈ ∈ ∈ ∈ ∈，∈ ∈ ∈ ∈ ∈，
由此可知，两条关键路线在结点 3 和结点 6 之间有并联部分，关键工序
为 a、d、e、f、g 和 h，其中工序 a、h 为两条关键路线所共有．要缩短工期，
就要缩短关键工序的时间，在上述两条关键路线的情况下，首先考虑缩短共有
的关键工序．本例中，先考虑缩短关键工序 h，每缩短 1 天，需增加费用 400
元，但节省间接费 500 元，净省费用 100 元．因此，把工序 h 压缩到最低限
度 4 天．同时，总费用减为 27300 元．
然后再考虑压缩工序 a，与压缩工序 h 一样，每压缩 1 天，总费用净省 100
元．但此处需注意，工序 a 不能压缩到其最低时间限度 7 天，因为当工序压
缩 2 天时，工序时间为 8 天，这时工序 b 和工序 c 就都变成了关键工序．这样，
在结点 1 和结点 3 之间，也出现了并联的关键路线部分．继续单独压缩工序
a，已不能缩短整个工程的工期．因此，只能把工序 a 压缩为 8 天．总费用减
为 27100 元．
现在，还需继续压缩工期，在还可以压缩的关键工序中，有以下考虑: 若
将工序 a 和工序 b 各缩短 1 天，虽可达到缩短工期的要求，但需增加费用 600
元，大于间接费用节省的 500 元，总费用反而增加，不合要求．同理，同时压
缩工序 a 和工序 c，总费用也要增加．
再来考虑结点 3 和结点 6 之间的各关键工序 d、e、f 和 g，因为它们之间
是并联的，所以要想缩短工程的工期，必须在 d、f 中和 e、g 中，各压缩一道
工序的时间．这样，有下列 4 种可能的组合，如表 6-10 中所列．
表 6-10 4 种可能的组合
工序 赶工一天增加的费用 赶工一天间接费用的减少 总费用净变化
d 和 e 3+3=6 5 +1
d 和 g 3+1=4 5 -1
f 和 e 5+3=8 5 +3
f 和 g 5+1=6 5 +1
从表 6-10 可见，除压缩工序 d 和 g 的组合能使总费用减少外，压缩其它
3 组，均使总费用增加．因此，将工序 d 和工序 g 各压缩 1 天，总费用减为 27000
元.由于工序 d 的限制，不能进一步压缩了．
综合起来，最少工程费计划方案，按下列要求去做：
将工序 a 压缩为 8 天，将工序 d 压缩为 3 天，将工序 g 压缩为 4 天，将
工序 h 压缩为 4 天，其它工序 b、c、e 和 f 仍按正常时间进行，这样得到的最
少工程费日程为 21 天，总费用为 27000 元，其统筹图如图 6-33（c）所示．
图 6-33（c）
还需指出，在编制工程进度计划时，除考虑时间和费用外，还要考虑合理
安排人力、物资设备和能源等有限资源．尤其在资源较紧张时，要合理调配，以
保证急需的关键工序，必要时甚至可以适当推迟工程的完工时间，这些都需要计
划人员或工程负责人全面衡量利弊，根据实际情况灵活掌握．
五、非确定型统筹问题
到目前为止，我们所考虑的工序时间是属于确定型的．也就是说，每道工
序都是以往重复过多次，因此工序时间是确定不疑．但有很多工程则不是这
样．如在研制一种新的发展项目时，许多工序时间几乎没有什么可供参考的资料，
或因干扰因素过多无法确定工序时间，这样就产生了非确定性统筹问题．
解决非确定性统筹问题，需要把不确定型工序时间化为确定的工序时间．这
样，我们就可用前面所讲方法，来编制工程进度计划和绘制统筹图．这就是计划
评审技术(PERT)．
要确定工程进度，首先必须确定全部工序的工序时间．对于非确定型问题的
工序时间，一般采用“三时估计法”．关于“三时估计法”我们已在时间参数计算一
节中做了介绍．对于非确定型统筹问题而言，重要的是这种估计的可靠性如
何．
下面我们讨论这种估计的可靠性．
在工序时间的不确定性条件下，如果已对各工序作了三时估计，得到工序估
计值 [ （ ， ）]，并根据公式算出方差．将估计值 [ （ ， ）]当作实际
工序时间看待，就可绘制出统筹图，找出关键路线．由于工程的总工期，是由所
有关键工序的工序时间之和求得的，但这里的工序时间都是随机变量．因此，总
工期也是随机变量，也存在总工期的期望值 [ ]与方差 [ ]．
由于我们定义的工序是相互独立的，所以总工期 的期望值应该等于关键路
线中所有关键工序的工序时间期望值之和．总工期的 的方差应该等于关键路线
中所有关键工序的工序时间的方差之和．即
（ ）＝ [ （ ， ）]
（8-19）
（ ）＝ σ2[ （ ， ）]
（8-20）
例 6-17 某工程各工序的工序时间的三时估计如表 6-11 所示,试求工程的
（ ）、 （ ）和标准差σ（ ）.
E t i j E t i j
E eT D eT
eT
eT
E eT
关键工序),( ji
E t i j
D eT
关键工序),( ji
t i j
E eT D eT eT
表 6-11 各工序时间的三时估计、E[ （ ， ）]和σ2[ （ ， ）]
时间估计
工序 紧前工序
a m b
E[ （ ， ）] σ2[ （ ， ）]
a / 6 10 15
b / 10 12 14 12
c a 6 7 6 6 0
d a 4 7 8
e a 9 15 20
f b，c 9 11 13 11
g b，c 8 7 10
h d，f 8 10 14 1
i d，f 20 24 28 24
j g，h 6 9 11
解 计算出工序时间的估计值 [ （ ， ）]及工序时间的方差σ2[ （ ，
）]列于表右，再根据表 6-11，绘出统筹图如图 6-34.
图 6-34
计算时间参数并确定关键路线：∈ ∈ ∈ ∈ ∈.
由关键工序 a、c、f 和 i 的工序时间的期望值，求出总工期的期望值:
（ ）＝ [ （1，2）]＋ [ （2，3）] ＋ [ （3，4）]＋ [ （4，6）]
＝＋6＋11＋24＝(天)
总工期的方差:
（ ）＝σ2[ （1，2）]＋σ2[ （2，3）] ＋σ2[ （3，4）]＋σ2[ （4，6）]
＝＋0＋＋＝
总工期的标准差: σ（ ）＝ ＝．
t i j t i j
t i j t i j
E t i j t i
j
a c f i
E eT E t E t E t E t
D eT t t t t
eT )( eTD
在例 6-17 中，如果 服从正态分布，期望值为 ，标准差为 ，由正
态分布知识可知，完工期变化在距期望值一个标准差以内的概率为 ，在距期
望值 3 个标准差之内的概率为 ，即工期在 天区间内完成的可能
性为 68%，工期在 3× 天区间内完成的可能性为 %．如果 满足
＝
服从标准正态分布，同样可以通过查正态表反推 的变化概率分布．
习 题 六
1．已知无向图 ＝{ ， }、 ＝{ ， }、 ＝{ ， }、 ＝
{ ， }，其中：
＝{ ， ， ， ， }， ＝{（ ， ），（ ， ），（ ， ），
（ ， ），（ ， ），（ ， ），（ ， ），（ ， ）}；
＝{ ， ， ， ， }， ＝{（ ， ），（ ， ），（ ， ），
（ ， ），（ ， ），（ ， ）}；
＝{ ， ， ， }， ＝{（ ， ），（ ， ），（ ， ），（ ，
）}；
＝{ ， ， ， ， }， ＝{（ ， ），（ ， ），（ ， ），
（ ， ），（ ， ）}．
（1）试求这四个图的图解，并判断是否连通图．
（2）试问 ， ， 是否 真子图和生成子图．
（3）试判断 中 ＝{ ， ， ， ， }、 ＝{ ， ， ， ，
, ， }、 ＝{ ， ， ， ， ， }、 ＝{ ， ， ， ， ，
eT
eT
'
eT )(
)(
Te
TeETe
'
eT eT
1G 1V 1E 2G 2V 2E 3G 3V 3E 4G
4V 4E
1V 1v 2v 3v 4v 5v 1E 1v 2v 1v 3v 1v 4v
2v 3v 2v 4v 3v 4v 3v 5v 4v 5v
2V 1v 2v 3v 4v 5v 2E 1v 2v 2v 3v 2v 3v
3v 4v 3v 5v 4v 5v
3V 1v 2v 3v 4v 3E 1v 2v 2v 3v 2v 3v 3v
4v
4V 1v 2v 3v 4v 5v 4E 1v 2v 2v 3v 2v 4v
3v 5v 4v 5v
2G 3G 4G 1G
1G 1 1v 2v 3v 4v 5v 2 1v 2v 3v 4v
5v 3v 1v 3 1v 2v 3v 5v 4v 1v 4 1v 3v 2v 4v 3v
}是否为开链、闭链、初等链、圈．
2．有向图 ＝（ ， ），其中： ＝{ ， ， ， ， }， ＝
{（ ， ），（ ， ），（ ， ），（ ， ），（ ， ），（ ， ），（ ，
）}．
（1）试求 D 及其基础图的图解．
（2）试判断 ＝{ ， ， ， ， }、 ＝{ ， ， ， ， }、
＝{ ， ， ， ， , } ＝{ ， ， ， ， ， ， }、 ＝
{ ， ， ， ，}是否为开链、闭链、初等链、路、回路．
3．分别用避圈法和破圈法求下列网络的的最小树:
(1)
图习题 6-3-1
(2)
图习题 6-3-2
(3)
图习题 6-3-3
4．在六个居民小区中建立一个有线电视网，假设各小区有线网建设费用仅
与架线距离有关，六个小区相互间的距离（单位百米）见表 6-12．试选择架线方
案使有线电视网的建设费用最低．
表 6-12 六个小区相互间的距离（单位百米）
A B C D E F
A 0 1
.3
3
.2
4
.3
3
.8
3
.7
B 1 0 3 4 3 3
5v
D V A V 1v 2v 3v 4v 5v A
1v 2v 1v 3v 2v 4v 2v 5v 3v 2v 4v 3v 4v
5v
1 1v 2v 3v 4v 5v 2 2v 5v 4v 3v 2v
3 1v 3v 4v 5v 2v 1v 4 1v 3v 2v 4v 3v 2v 5v 5
2v 4v 3v 2v
.3 .5 .0 .1 .9
C 3
.2
3
.5
0 2
.8
2
.6
1
.0
D 4
.3
4
.0
2
.8
0 2
.1
2
.7
E 3
.8
3
.1
2
.6
2
.1
0 2
.4
F 3
.7
3
.9
1
.0
2
.7
2
.4
0
5．在下列网络中：
（1）用 Dijkstra 标号法求从 S 点到 T 点的最短距离以及最短路；
（2）用逐次逼近法求 S 点到各点的最短距离以及最短路．
图习题 6-5
6．在下列网络中试求 1 到各点的最短距离．
图习题 6-6
7．某零件生产经毛胚、机加工、热处理和检验四道工序，在满足同样的技
术要求前提下，各道工序有不同的实施方案，其费用（元）如表 6-13，试确定一
个生产费用最低的加工方案．
表 6-13 各道工序不同的实施方案及其费用
毛胚 机加工 热处理 检验
方案 费用 方案 费用 方案 费用 费用
1 40 1 40
1
2
30
40
20
10
v
2 50
1
2
40
50
20
10
3 60
1
2
40
50
20
10
1 30
1
2
30
40
20
10
2 20
1
2
40
50
20
10
2 60
3 30
1
2
40
50
20
10
8．在下面网络中，弧旁的括号标注了弧的容量和流量．试求（1）所有的
截集及截量；（2）最大流；（3）最小截集．
图习题 6-8
9．试求下面网络中 （ ）＝4 的最小费用流，图中弧旁数字为（ ，
）．
图习题 6-9
10．试求下面网络的最小费用最大流，图中弧旁数字为（ ， ）．
图习题 6-10
11．表 6-14 给出某运输问题的产销平衡表与单位运价表，将此问题转化为
最小费用最大流问题．画出网络图并进行求解．
表 6-14 某运输问题的产销平衡表与单位运价表
B1 B2 B3 产量
v f ijb
ijr
ijb ijr
销
地产
地
A1 20 24 5 8
A2 30 22 20 7
A3 4 5 6
12．指出下列统筹图的错误，若有可能进行更正．
图习题 6-12（a）（b）（c）（d）
13．根据作业明细表绘制网络图：
(1) 工序明细表见表 6-15:
表 6-15 工序明细表
工序 紧前工序 紧后工序
a / c,d
b / d
c a e
d a,b e
e c,d /
(2) 工序明细表见表 6-16:
表 6-16 工序明细表
工序 紧前工序 紧后工序
a / b,c,d
b a e
c a e
d a e,f
e a,b,c /
f d /
14．已知网络图，计算（1）各结点的最早时间和最迟时间；（2）各工序
的最早开工、最早完工、最迟开工和最迟完工时间．
图习题 6-14-1
图习题 6-14-2
15．已知表 6-17 所列资料，要求：（1）绘制网络图；（2）计算各工序的
最早开工、最早完工、最迟开工、最迟完工时间和总时差；（3）确定关键路
线．
表 6-17 各工序的逻辑关系及时间
工序 紧前工序
工序时间
（天）
工序
紧前
工序
工序时间
（天）
工序
紧前
工序
工序时间
（天）
a / 12 f c 5 x h 3
b / 3 g c 6 p f 7
c b 5 h a,g 4 r n 3
d b 7 n d,e 3 w m 2
e b 8 m e 8 Y x,p,r 2
16．已知一个车库基建工程的作业明细表如表 6-18 所示，要求：（1）工程
从开始施工到全部结束的最短周期；（2）如果工序 l 拖 10 天，对整个工程有何
影响；（3）如果工序 j 的工序时间由 12 天缩短到 8 天，对整个工程进度有何影
响；（4）为保证整个工程进度在最短周期内完成，工序 I 最迟在哪天开工；
（5）如果要求工程在 75 天完工，要不要采取措施？应从哪些方面采取措施？
表 6-18 车库基建工程的作业明细表
工序代号 工序名称 工序时间 紧前工序
a 清理场地，准备施工 10 /
b 备料 8 /
c 车库地面施工 6 a,b
d 预制墙及房顶桁架 16 b
e 车库混凝土地面保养 24 c
f 立墙架 4 d,c
g 立房顶桁架 4 f
h 装窗及边墙 10 f
i 装门 4 f
j 装天花板 12 g
k 油漆 16 h,i,j
l 引道混凝土施工 8 c
m 引道混凝土保养 24 l
n 清理场地，交工验收 4 k,m
17．在第 16 题中，试确定 70 天内完工，又使工程费用最低的施工方案．各
工序的正常进度和赶工进度的工序时间及费用情况如表 6-19．
表 6-19 各工序的正常进度和赶工进度的时间及费用
正常进度 赶工进度
工序代号 工序时间
（天）
每天费用
（元）
工序时间
（天）
每天费用
（元）
a 10 50 6 75
b 8 40 8 40
c 6 40 4 60
d 16 60 12 85
e 24 5 24 5
f 4 40 2 70
g 4 20 2 30
h 10 30 8 40
i 4 30 3 45
j 12 25 8 40
k 16 50 12 80
l 8 40 6 60
m 24 5 24 5
n 4 10 4 10
18．某工程各工序的工序时间及需要人数如表 6-20．现有人数 10 人，试确
定工程完工时间最短的工程进度计划．
表 6-20 各工序的工序时间及需要人数
工序代号 紧前工序 工序时间（天） 需要人数
a / 4 9
b / 2 3
c / 2 6
d / 2 4
e b 3 8
f b 2 7
g f,d 3 2
h e,g 4 1
19．某计划项目的资料如表 6-21，要求：（1）绘制网络图并计算每个工序
的期望时间和方差以及总工期的期望和方差；（2）分别判断总工期提前 3 天完
成以及延迟不超过 5 天完成的可能性大小．
表 6-21 项目的有关资料
需要天数
工序 紧前工序 最乐观的
a
最可能的
m
最悲观的
b
a / 2 5 6
b a 6 9 12
c a 5 14 17
d b 5 8 11
e c,d 3 6 9
f / 3 12 21
g e,f 1 4 7
（姚载善）
