上海交通大学管理科学运筹学课件

　上海交通大学管理科学运筹学课件

　 5.1 图论的差不多概念

　 5.1.1 引言

　 瑞士数学欧拉（Euler）在 1736 年发表了图论方面的第一篇论文，题为“依据几何位置的解题方法”，解决了闻名的哥尼斯堡七桥咨询题。哥尼斯堡城中有一条河叫普雷格尔河，该河上有两个岛，河上有七座桥，如图 5-1（a）所示。当时那儿的居民热衷于如此的咨询题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到动身点。

　 A B C D （a）

　A C B D （b）

　图 5-1 · · · ·

　欧拉用 A、B、C、D 四点表示河的两岸和小岛，用两点间的联线表示桥，如图 5-1（b），该咨询题可归结为：能否从任一点动身，通过每条边一次且仅一次，再回到该点？即一笔画咨询题。欧拉证明了这是不可能的，因为图中每点都只与奇数条线相连。这是古典图论中的一个闻名咨询题。

　运筹学中的“中国邮递员咨询题”：一个邮递员从邮局动身要走遍他所负责的每条街道去送信，咨询应如何选择适当的路线可使所走的总路程最短。那个总是就与欧拉回路有紧密的关系。

　图论的第一本专著是匈牙利数学家 O.Konig 著的“有限图与无限图的理论”，发表于 1936 年。随着科学技术的进展及电子运算机的显现和广泛应用，图论得到进一步进展，广泛应用于治理科学、运算机科学、心理学及工程技术治理中，并取得了丰硕的成果。

　5.1.2 差不多概念

　 自然界和人类社会中，大量的事物以及事物之间的关系，常能够用图形来表示。如为了反映都市之间有没有航班，我们可用图 5-2 来示意。甲城与乙城，乙城与丙城有飞机到达，而甲、丙两城没有直飞航班。再如工作分配咨询题，我们能够用点表示每人与需要完成的工作，点间连线表示每个人能够胜任哪些工作如图 5-3 所示。

　 甲 乙 丙 图 5-2 甲 乙 丙 工人 A B C D 工作 图 5-3 · · · · · · · · · ·

　在上面的例子中，我们关怀图中有多少个点，点与点之间有无连线。这种图是反映对象之间关系的一种工具。

　图可分为无向图和有向图。两点之间不带箭头的联线为边，两点之间带箭头的联线为弧。

　由点、边构成的图是无向图，记   E , V G 

　由点、弧构成的图是有向图，记   A , V D 

　 1v

　2v

　3v

　4v 1e

　2e

　3e 4e 5e

　6e 7e

　图 5-4 1v 2v 3v

　 1a 2a

　3a 4a 5a

　6a 7a

　8a 9a 10a 11a

　图 5-5 · · · · · · · · · · · 图 5-4是一个无向图

　 4 3 2 1v , v , v , v V  ，  7 6 5 4 3 2 1e , e , e , e , e , e , e E 

　其中，

　           1 1 2 2 1 2 3 2 3 4 3 4 5 1 4 6 1 3 7 4 4, , , , , , , , , , ( , ), , e v v e v v e v v e v v e v v e v v e v v        图5-5 是一个有向图

　 7 6 5 4 3 2 1v , v , v , v , v , v , v V  ，  11 3 2 1a , , a , a , a A  

　其中，

　                    1 1 2 2 1 3 3 3 2 4 3 4 5 2 4 6 4 57 4 6 8 5 3 9 5 4 10 5 6 11 6 7, , , , , , , , , , , ,, , , , , , , , ,a v v a v v a v v a v v a v v a v va v v a v v a v v a v v a v v          给定一个图   E , V G  ，一个点、边的交错序列  ik ik ik i i i iv , e , v , , e , v , e , v1 1 2 2 1 1   ，假如满足  1 it it itv , v e ，   1,2, , 1 t k   ，则称为一条联结1 iv 和ikv 的链，记为 ik i iv , , v , v 2 1。

　关于有向图   A , V D  ，从 D 中去掉所有弧上的箭头，应得到一个无向图，称为 D 的基础图，记为   D G 。

　设  ik ik ik i i i iv , a , v , , a , v , a , v1 1 2 2 1 1   是 D 中的一个点弧交错序列，假如那个序列在基础图   D G 中所对应的点边序列是一条链，则称那个点弧交错序列是D 的一条链。

　在实际咨询题中，往往只用图来描述的所研究对象之间的关系依旧不够的，与图联系在一起的，通常还有与点或边有关的某些数量指标，称为“权”，权能够代表如距离、费用、通过能力（容量）等等。这种点或边带有某种数量指标的图称为网络（即赋权图）。

　5.1.3 图的矩阵表示

　 用矩阵表示图对研究图的性质及应用常是比较方便的，图的矩阵表示方法有权矩阵、邻接矩阵、关联矩阵、回路矩阵等，那个地点只介绍其中两种常用矩阵。

　定义 1 网络   E , V G  ，其边是  j iv , v 有权ijw ，构造矩阵  n nija A

　其中， ,0ij i jijw v v Eaor      其他 称矩阵 A 为网络 G 的权矩 阵。

　图 5-6 表示图的权矩阵为

　0 6 5 0 76 0 8 4 45 8 0 3 20 4 3 0 97 4 2 9 0A

　定义 2 关于图   E , V G  ， 构造一个矩阵  n nija A ，其中，

　  其他 01 E v , vaj iij 则称矩阵 A 为图 G 的邻接 矩阵。

　图5-7所示图的邻接矩阵 A 为

　0 0 1 1 01 0 0 0 00 0 0 0 00 1 1 0 10 1 0 1 054321vvvvvA

　当 G 为无向图时，邻接矩阵为 对称矩阵。

　5.2 最短路咨询题

　 最短路咨询题是网络理论中 应用最广泛的咨询题之一。许多优化咨询题能够使用那个模型，如设备更新、管道铺设、线路安排、厂区布局等。

　咨询题表述：给定一个赋权有向图   A , V D  ，对每一弧  j i ijv , v a  ，相应地有权  ij ijw a w  ，又有两点 V v , vt s ，设 p 是 D 中sv 到tv 的一条路，路 p 的权是 p 中所有弧的权之和，记为   p w 。最短路咨询题确实是求从sv 到tv 的路中一条权最小的路0p ，

　    p w p wpmin0 。

　5.2.1 Dijkstra 算法

　 该算法是由 Dijkstra 于 1959 年提出来，用于求解指定两点sv 、tv 之间的最短路，或从指定点sv 到其余各点的最短路，目前被认为是求 0 ijw 情形下最短路咨询题的最好方法。算法的差不多思路基于以下原理：若 p 是从sv到tv 的最短路，iv 是 p 中的一个点，那么从sv 沿 p 到iv 的路是从sv 到iv 的最短路。

　 2 4 7 6 3 5 4 8 1v

　2v

　3v 4v

　5v

　9 图 5-6 • • • • •

　1v

　2v

　3v 4v

　5v

　图 5-7 • • • • •

　采纳标号法：

　T 标号与 P 标号。

　T 标号为试探性标号， P 为永久性标号。给iv 点一个 P 标号时，表示从sv 到iv 点的最短路权，iv 点的标号不再改变。给iv 点一个 T 标号时，表示从sv 到iv 点的估量最短路权的上界，是一种临时标号。凡没有得到 P 标号的点都有 T 标号。算法每一步都把某一点的 T 标号改为 P 标号，当终点tv 得到 P 标号时，全部运算终止。

　Dijkstra 算法差不多步骤：

　⑪给sv 以 P 标号，   0 sv P ，其余各点均给 T 标号，    iv T 。

　⑫若iv 点为刚得到 P 标号的点，考虑jv ，   A v , vj i 且jv 为 T 标号。对jv 的T 标号进行如下的更换：

　       ij i j jw v P , v T v T   min

　⑬比较所有具有 T 标号的点，把最小者iv 改为 P 标号，即

　     i iv T v P min 

　当存在两个以上最小者时，可同时改为 P 标号。

　⑭若全部点均为 P 标号则停止。否则用iv 代替iv 转回⑫。

　例 5.1 用 Dijkstra 算法 求图 5-8 中从7 1v v  的最短路

　解：⑪第一给1v 以 P 标 号，  01 v P ，给其余所有点 T 标号

　   iv T ，   7 2 , , i  

　⑫由于  2 1v , v ，  3 1v , v ，  A v , v 4 1，且4 3 2v , v , v 是 T 标 号点，因此修改 T 标号为：

　                            3 3 0 min min5 5 0 min min2 2 0 min min14 1 4 413 1 3 312 1 2 2               , w v P , v T v T, w v P , v T v T, w v P , v T v T 在所有 T 标号中，   22 v T 最小，因此令   22 v P 。

　⑬2v 是刚得到 P 标号的点，故考察2v 。因为  3 2v , v ，   A v , v 6 2，且6 3v , v 是T 标号，故6 3v , v 新的 T 标号为：

　                   9 7 2 min min4 2 2 min min26 2 6 623 2 3 3          , w v P , v T v T, w v P , v T v T 在所有 T 标号中，   34 v T 最小，故令   34 v P 。

　⑭考察4v ，因   A v , v 5 4，

　 1 2 2 3 5 2 5 2 3 2 5 7 7 5 1v 2v

　3v

　4v 5v 6v

　 1 图 5-8 • • • • • •

　          8 5 3 min min45 4 5 5      , w v P , v T v T

　在所有 T 标号中，   43 v T 最小，令   43 v P 。

　⑮考察3v ，  5 3v , v ，   A v , v 6 3，

　                   9 5 4 9 min min7 3 4 8 min min36 3 6 635 3 5 5        , w v P , v T v T, w v P , v T v T 在所有 T 标号中，   75 v T 最小，令   75 v P 。

　⑯考察5v ，  6 5v , v ，   A v , v 7 5，

　                   14 7 7 min min8 1 7 9 min min57 5 7 756 5 6 6         , w v P , v T v T, w v P , v T v T 在所有 T 标号中，   86 v T 最小，故令   86 v P 。

　⑰考察6v ，   A v , v 7 6           13 5 8 14 min min67 6 7 7     , w v P , v T v T

　令   137 v P ，所有点都标上 P 标号，运算终止。

　从7 1v v  之最短路是：7 6 5 3 2 1v v v v v v      ，路长 13，同时得到1v到其余各点的最短路。

　5.2.2 逐次靠近算法

　 Dijkstra 算法只适用于所有 0 ijw 的情 形，当赋权有向图中存在负权时，则算法失效。例 如在图5-9 所示的赋权有向图中，用 Dijkstra 算法 得到1v到3v 最短路的权是 5，但那个地点明显不 对；因为1v 到3v 的最短路是3 2 1v v v   ，权为 3。

　在存在负权时，我们采取逐次靠近算 法来求解最短路。为方便起见，不妨设从任一点iv 到任一点jv 都有一条弧，假如在D 中，   A v , vj i ，则添加弧  j iv , v ，令  ijw 。明显，从sv 到jv 的最短路总是从sv 动身，沿着一条路到某点iv ，再沿  j iv , v 到jv 的，因此，从sv 到iv 的这条路必定是从sv 到iv 的最短路。故有sv ，jv 的距离  j sv , v d 必满足如下方程：

　     ij i sij sw v , v d v , v d   min

　为了求解那个方程的解  1v , v ds，    p s sv , v d , , v , v d 2， p 为 D 的点数，令

　  sj j sw v , v d 1

　  p , , , j  2 1 

　      ij i stij stw v , v d min v , v d  1， t 为迭代步数。

　若第 k 步，对所有 p , , , j  2 1  ，有

　 7 5 -4 1v

　2v

　3v

　图 5-9

　    j skj skv , v d v , v d1 

　则  j skv , v d 为sv 到任一点jv 的最短路权。

　例 5-2 求图 5-10 所示赋权有向图中从1v 到各点的最短路。

　解：迭代初始条件为：

　  sj j sw v , v d 1 有   01 11 v , v d ，   12 11  v , v d ，   23 11  v , v d ，   34 11 v , v d ，    5 11v , v d ，    6 11v , v d ，    7 11v , v d ，    8 11v , v d 。用表 5-1 表示 全部运算过程。

　 1 1 -1 -1 -1 -2 -3 -3 -5 6 3 1 8 -5 2 7 2 1v

　4v 2v

　5v

　8v 7v 图 5-10 • • • • • • •

　表 5-1

　（表中空格为   ）

　j i

　 w ij D (t) (v 1 ,v j ) V 1 V 2 V 3 V 4 V 5 V 6 V 7 V 8 1  t

　2  t

　3  t

　4  t

　V 1 0 -1 -2 3

　 0 0 0 0 V 2 6 0

　 2

　-1 -5 -5 -5 V 3

　 -3 0 -5

　1

　 -2 -2 -2 -2 V 4 8

　 0

　 2

　3 -7 -7 -7 V 5

　-1

　 0

　 1 -3 -3 V 6

　 1 0 1 7

　-1 -1 -1 V 7

　-1

　 0

　 5 -5 -5 V 8

　 -3

　-5 0

　 6 6

　当 4  t 时，发觉       8 2 11314, , , j v , v d v , v dj j   ，讲明已得到1v 到各点jv 的最短路的权，即表中最后一列数。

　假如需要明白1v 点到各点的最短路径，能够采纳“反向追踪”的方法。如已知，   68 1 v , v d ，因      8 1 68 6 17 1 v , v d w v , v d      故记下  8 6v , v 。因   6 1 36 3 1v , v d w v , v d   ，记下  6 3v , v ，从而从1v 到8v 的最短路径是8 6 3 1v v v v    。

　递推公式中  jtv , v d1实际意义为从1v 到jv 点，至多含有 1  t 个中间点的最短路权。因此在含有 n 个点的图中，假如不含有总权小于零的回路，求从1v 到任一点的最短路权，用上述算法最多通过 n -1 次迭代必定收敛。明显，假如图中含有总权小于零的回路，最短路权没有下界。

　应用举例

　例 5-3 设备更新咨询题。某企业使用一台设备，在每年年初，都要决定是否更新。若购置新设备，要付购买费；若连续使用旧设备，则支付修理费用。试制定一个 5 年更新打算，使总支出最少。

　若已知设备在各年的购买费及不同机器役龄时的残值和修理费，如表 5-2 所示。

　表 5-2

　 第 1 年 第 2 年 第 3 年 第 4 年 第 5 年 购买费 11 12 13 14 14 机器役龄 0-1 1-2 2-3 3-4 4-5 修理费 5 6 8 11 18 残值 4 3 2 1 0 解：把那个咨询题化为最短路咨询题

　用iv 表示第 i 年初购进一台新设备，虚设一个点6v ，表示第 5 年底；用弧  j iv , v 表示第 i 初购的设备一直使用到第 j 年年底；弧  j iv , v 上的数字表示第 i 年初购进设备，一直 使用到第 j 年底所需支付的购 买、修理的全部费用。例如， 4 1v , v 弧上的 28 是第 1 年 初购买费 11 加上 3 年的修理 费 5，6，8，减去了 3 年役龄机 器的残值 2；  4 2v , v 弧上的 20 是第2年初购买费12减去机器 残值3 与使用 2 年修理费 5，6 之和，见图 5-11。

　如此设备更新咨询题就变为：求从1v 到6v 的最短路，运算结果讲明6 3 1v v v   为最短路，路长为 49。即在第 1年、第 3 年初各购买一台新设备为最优决策，这时 5 年的总费用为 49。

　 3 24 4 2 3 2 4 2 1

　sv4v1v

　2v3v图 5-12 • • • • • •

　19 40 59 12 13 14 15 21 30 15 28 41 29 22 20 1v

　2v3v6v图 5-11 4v5v

　5.3 最大流咨询题

　 最大流咨询题是一类应用极为广泛的咨询题。例如在交通运输网络中有人流、车流、物资流；供水网络中有水流；金融系统中有现金流；通讯系统中有信息流；等等。20 世纪 50 年代 Ford ，Fulkerson 建立的“网络流理论”是网络应用的重要组成部分。

　图 5-12 是输油管道网，sv 为起点，tv 是终点，4 3 2 1v , v , v , v 为中转站，弧上的数表示该管道的最大输油能力，咨询应如何安排各管道输油量，才能使从sv 到tv 的总输油量最大？

　5.3.1 差不多概念与差不多定理

　 ⑪网络与流

　定义 给一个有向图   A , V D  ，在 V 中指定一点sv 为发点，另一点tv 为收点，其余的点叫中间点。关于每一个弧   A v , vj i ，对应有一个   0 j iv , v c （简写为ijc ），称为弧的容量。如此的 D 叫做网络，记作   C , A , V D  。

　所谓网络上的流，是指定义在弧集合 A 上的一个函数    j iv , v f f  ，并称 j iv , v f 为弧  j iv , v 上的流量，简记作ijf 。

　⑫可行流与最大流

　①容量限制条件：每一弧   A v , vj i

　ij ijc f   0

　②平稳条件：关于中间点iv ，有

　( , ) ( , )i j k iij kiv v A v v Af f   关于发点sv ，收点tv ，有

　 ( , ) ( , )s i i tsi itv v A v v Af f v f      f v 称为那个可行流的流量。

　可行流总是存在的，如零流， 0 ijf ，   0  f v 。所谓最大流咨询题，确实是求一个流  ijf ，使其流量   f v 达到最大，同时满足以上容量限制条件和平稳条件。

　事实上最大流咨询题是一个专门的线性规划咨询题，然而利用它与图的紧密关系求解，更为直观简便。

　⑬增广链

　若  是网络中联结发点sv 和收点tv 的一条链，且链的方向是从sv 到tv ，则与链的方向一致的弧叫前向弧， 表示前向弧的集合；与链的方向相反的弧叫后向弧， 表示后向弧的集合。

　定义 设 f 是一个可行流，  是从sv 到tv 的一条链，若  满足下列条件， 是可行流的一条增广链。

　弧   j iv , v 上，ij ijc f   0 ，即 中每一弧是非饱和弧。

　弧   j iv , v 上，ij ijc f   0 ，即 中每一弧是非零流弧。

　⑭截集与截量

　设     T S , V T , S ，我们把始点在 S ，终点在 T 中的所有弧构成的集合，记为   T , S 。

　定义 给网络   C , A , V D  ，若点集 V 被剖分为两个非空集合1V 和1V ，1 2 1 2, V V V V V    

　 ，使1 1V v , V vt S  ，则把弧集  1 1V , V 称为分离sv ，tv 的截集。

　从定义可知截集是从sv 到tv 的必经之道。

　定义 给一截集  1 1V , V ，把截集  1 1V , V 中所有弧的容量之和称为那个截集的容量，记作     1 11 1V , V v , vijj ic V , V c

　不难证明，任何一个可行流的流量   f v 都可不能超过任一截量的容量，即    1 1V , V c f v  。

　明显，若关于一个可行流f ，网络中有一个截集   1 1V , V ，      1 1V , V c f v ，则f 必是最大流，而   1 1V , V 必定是 D 的所有截集中容量最小的一个，即最小截量。

　最大流量最小截量定理：任一个网络 D 中，从sv 到tv 的最大流的流量等于分离sv ，tv 的最小截集的容量。

　定理 1 可行流f 是最大流，当且仅当不存在关于f 的增广链。

　证明 若f 是最大流，设 D 中存在关于f 的增广链  ，令

　     ij ij ijf , f c min min min

　由增广链的定义，可知 0   ，令

　          j i ijj i ijj i ijijv , v fv , v fv , v ff

　不难验证   ijf 是一个可行流，且            f v f v f v  ，这与f 是最大流假设矛盾。

　现在设 D 中不存在关于f 的增广链，证明f 是最大流。

　令1V v s ，若1V v i ，且ij ijc f ，则令1V v j ；若1V v i ，且 0 jif ，则令1V v j 。

　因为不存在关于f 的增广链，故1V v t 。

　记 1 1V V V ，因此得到一个截集   1 1V , V ，明显必有

　         1 11 10 V , V v , vV , V v , v cfj ij i ijij 因此，      1 1V , V c f v 。因此f 必是最大流，定理得证。

　定理 1 为我们提供了寻求网络最大流的一个方法。若可行流 f 中存在增广链，讲明还有潜力可挖，只须沿增广链调整流量，得到一个流量增大的新的可行流；否则 f 是最大流。而判不是否存在增广链，能够依照tv 是否属于1V 来进行。

　5.3.2 寻求最大流的标号法（Ford，Fulkerson）

　 设已有一个可行流，标号算法分 2 步：第 1 步是标号过程，通过标号来查找增广链；第 2 步是调整过程，沿增广链调整 f 以增加流量。

　⑪标号过程

　每个标号点的标号包含两部分：第 1 个标号明它的标号从哪一点得到，以便找出增广链；第 2 个标号是为确定增广链的调整量  用的。

　给发点sv 以标号    ,  ；

　选择一个已标号的点iv ，关于iv 的所有未标号的邻接点jv ，假如  A v , vj i ，且ij ijc f  ，令      ij ij i jf c , v l v l   min ，并给jv 以标号    j iv l , v  ；假如   A v , vi j ，且 0 ijf ，令      ij i jc , v l v l min  ，并给jv 以标号    j iv l , v  。

　重复上述步骤，直到tv 被标上号或不再有顶点可标号为止。假如tv 得到标号，讲明存在增广链，转入调整过程；若tv 未获得标号，标号过程已无法进行时，讲明 f 已是最大流。

　⑫调整过程

　令        j i ijj i ijj i ijijv , v fv , v fv , v ff

　调整量  tv l   ，去掉所有标号，对新的可行流  ijf 重新进行标号过程。

　例 5-4 用标号法求图 5-13 所示网络的最大流。弧旁的数是  ij ijf , c 。

　 （2，2）

　（2，1）

　（5，3）

　（4，3）

　（3，3）

　（5，1）

　  41, v vs   11 2  , v v

　  12 3, v v 

　  12 4, v v

　sv

　    , 

　（3，0）

　（1，1）

　（1，1）

　图 5-13   14 ,v

　• • • • •

　 （2，2）

　（2，1）

　（5，3）

　（4，3）

　（3，3）

　（5，1）

　  41, v vs   11 2  , v v

　  12 3, v v 

　  12 4, v v

　sv

　    , 

　（3，0）

　（1，1）

　（1，1）

　图 5-14   14 ,v

　 解：经检查，网络中的流是可行流，下面分析是否能够增加流量。

　标号过程

　第一给sv 标上    ,  ；

　2、检查sv ，在弧  1v , v s 上， 5 11 1  s sc f 则1v 的标号为    1 1v l , v ，其中         4 1 5 min min1 1 1       , f c , v l v ls s s。在弧  2 1v , v s 上， 32 2 s sc f ，不满足标号条件。

　3、检查1v ，在弧  3 1v , v 上，13 132 c f   ，不满足标号条件。在弧  1 2v , v 上，0 121  f ，则2v 的标号为    2 1v l , v  ，         1 1 421 1 2   , min f , v l min v l 。

　4、检查2v ，在弧  4 2v , v 上， 4 324 24   c f ，则给4v 标号    4 2v l , v ，         1 1 1 min min24 24 2 4    , f c , v l v l 。在弧  2 3v , v 上， 0 132  f ，给3v 标号   3 2v , v  ，         1 1 1 min min32 2 3   , f , v l v l 。

　5、在4 3v , v 中任选一个进行检查，例如，在弧  tv , v 4

　上， 5 34 4  t tc f ，给tv 标号    tv l , v 4 ，            1 3 5 1 min min4 4 4     , f c , v l v lt t t。

　因tv 有了标号，故转入调整过程。

　（二）调整过程

　按点的第一个标号找到一条增广链，如图 5-14 中双箭线所示。

　则见：

　          1 24 4 2 1v , vv , v , v , v , v , vt s 按 1   ，在增广链  上调整 f 。

　 上：4 1 34 1 32 1 14 424 241 1               t ts sf ff ff f  上：

　0 1 121 21       f f

　其余的ijf 不变。

　调整后得到图 5-15 所示的可行流，对那个可行流进行标号，查找增广链。

　 （2，2）

　（2，1）

　（5，4）

　（4，4）

　（3，3）

　（5，2）

　1v 2v

　3v

　4v

　sv

　    ,    3 , v s

　（3，0）

　（1，1）

　（1，0）

　图 5-15 1v

　1v

　开始给sv 标号    ,  ，检查sv ，给1v 标以   3 , v s ，检查1v ，弧  3 1v , v 上，13 13c f  ，弧  1 2v , v 上， 021 f ，均不符合条件，标号过程无法连续下去，算法终止。这时图 5-15 可行流即最大流。

　最大流为：

　  5 2 32 1    s sf f f v 。与此同时可找到最小截集  1 1V , V ，其中1V 为标号点集，即  1 1v , v Vs ，1V 为未标号点集，  5 4 3 2 1v , v , v , v V  ，截集      3 1 2 1 1v , v , v , v V , Vs ，最小截量为 5。

　由上述可见，用标号法找增广链找到最大流的同时，得到一个最小截集。最小截集的容量大小阻碍网络最大流量。因此为提高总的输送量，必须第一考虑改善最小截集中各弧的输送能力。另一方面，一旦最小截集中弧的通过能力被 降低，就会使总的输送量减少。

　5.4 网络打算

　 20 世纪 50 年代以来，国外连续显现一些打算治理的新方法，如关键路线法（Critical Path Method，缩写为 CPM），打算评审方法（Program Evaluation Review Technique，缩写为 PETR）等。这些方法差不多上建立在网络模型基础之上，称为网络打算技术，广泛应用于工业、农业、国防、科研等打算治理中，对缩短工期，节约人力、物力和财力，提高经济效益发挥了重要作用。

　我国数学家华罗庚先生将这些方法总结概括为统筹方法，引入中国并推广应用。统筹方法的差不多原理是：从需要治理的任务的总进度着眼，以任务中各工作所需要的工时为时刻因素，按照工作的先后顺序和相互关系作出网络图，以反映任务全貌，实现治理过程的模型化。然后进行时刻参数运算，找出打算中的关键工作和关键路线，对任务的各项工作所需的人、财、物通过改善网络打算作出合理安排，得到最优方案并付诸实施。通过对各种评判指标进行定量化分析，在打算的实施过程中，进行有效的监督与操纵，以保证任务高质量地完成。

　5.4.1 网络图

　 网络图是由节点、弧及权所构成的有向图，即有向的赋权图。节点表示事项，弧表示工序（活动）。工序是在工艺技术和组织治理上相对独立的工作或活动，需要一定的时刻与资源，而事项则表示一个或若干工序的开

　始或终止，是相继工序的分界点。权表示为完成某个工序所需要的时刻或资源等数据。

　例如某工序 a 能够表示为：

　jai5， i 为箭头节点，表示工序 a 开始， j 为箭头尾节点，表示工序 a 终止，5 为完成本工序所需时刻。

　网络图是有向图，按照工艺流程的顺序，规定工序从左向右排列，再给节点统一编号，节点由小到大编号。对任一工序   j , i 来讲，要求 i j  。始点编号能够从 1 开始。

　在绘制网络图时，还要注意以下规则：

　⑪网络图只能有一个总起点事项，一个 总终点事项。

　⑫网络图不能有缺口和回路。

　⑬两节点 j , i 之间只能有一条弧。

　⑭正确表示工作之间的前行、后继关 系。

　如图 5-16 表示 b , a 两工序终止后， d , c 两工序才开始。

　b , a 为 d , c 的紧前工序， d , c 为 b , a 的紧后工序。

　⑮虚工序的应用。

　假如 d , c , b , a 的工序关系是：

　c 必须在 b , a 均 完成后才能开工，而 d 只要在 b 完成后即可开工。

　也确实是讲， b , a 是 c 的紧前工序，而只有 b 是 d 的 紧前工序。如此必须用图 5-17 来表示，其中③→ ④是一个虚工序，只表示③、④两节点的衔接关 系，不需要人力、物力等资源和时刻。

　虚工序还能够用于正确表示平行与交叉作业。一道工序分为几道工序同时进行，称为平行作业。如图 5-18（a）中市场调研需 12 天，如增加人力分为 3 组同时进行，能够画为 5-18（b）。

　 1 2 3 4 市场调研 12 （a）

　1 2 5 6 6 3 5 3 4 （b）

　图 5-18

　两个或两个以上的工作交叉进行，称为交叉作业。如工作 a 与工作 b 分不为挖沟和埋管子，那么它们的关系能够是挖一段，埋一段，不必等沟全部挖好再 1 3 3 5 6 4 图 5-19 7 1b

　2b

　3b 1a

　2a

　3a

　3 2 1 4 5 a b

　d 图 5-16

　2 1 4 5 a

　b

　c

　d 图 5-17 3 6

　埋。如此，我们可用图 5-19 来表示交叉作业。

　依照上述规则绘制网络图，是为了保证网络图的正确性。此外，为了使图面布局合理，层次分明，条理清晰，还要注意画图技巧。幸免弧的交叉，尽可能将关键路线布置在中心位置，将联系紧密的工序布置在相近的位置。

　例 5-5 某项新产品投产前全部预备工作（如表 5-3）列示各工序与所需时刻以及它们之间的相互关系。要求编制该项工程的网络打算。

　表 5-3

　工序 工序内容 紧前工序 工时（周）

　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 依照以上规则，绘制的网络图如 5-20 所示。

　 1 图 5-20 2 3 4 5 6 7 9 8 10 1 2 3 2 3 10 6 5 2 A B C D E F G H I J K L 8 4 8

　5.4.2 时刻参数运算

　 运算网络图中有关的时刻参 数，要紧目的是找出关键路线，为网络打 算的优化、调整和执行提供明确的时刻概 念。

　通常把网络图中需时最长的 路线叫做关键路线，如图 5-21 所示网络 中双箭线表示的为关键路线，关键路线上的工序称为关键工序。要想使任务按期完或提早完工，就要在关键路线的关键工序上想方法。

　 1 3 2 5 4 6 4 5 3 7 3 4 2 2 图 5-21

　网络图的时刻参数包括工序所需时刻、事项最早、最迟时刻，工序的最早、最迟时刻及时差等，下面分不叙述。

　工序时刻   j , i t 的确定

　工序   j , i 的所需时刻可记为   j , i t ，有以下两种情形：

　⑪完成工序所需时刻确定，只给出一个时刻值。在具备劳动定额资料的条件下，或者在具有类似工序的作业时刻消耗的统计资料时，用对比分析来确定作业时刻。

　⑫在阻碍工序因素较多，作业时刻难以准确估量时，能够采纳三点时刻估量法来确定作业时刻：

　a ——最快可能完成时刻

　m ——最可能完成时刻

　b ——最慢可能完成时刻

　一样情形下，可按下列公式近似运算作业时刻。

　 224,66a m bt i jb a      概率型网络图与确定型网络图在工时确定后，对其他时刻参数的运算差不多相同。

　事项时刻参数

　⑪事项最早时刻   j t E

　事项 j 的最早时刻用   j t E 表示，它表示以 j 为始点的各工序最早可能开始的时刻，也表示以 j 为终点的各工序的最早可能完成时刻。它等于从始点事项起到本领项最长路线的时刻长度。事项最早时刻可用下列递推公式，按照事项编号从小到大顺序逐个运算。

　          j , i t i t x j ttEiEEma0 1 式中，   i t E 为事项 j 相邻的各紧前事项的最早时刻。

　⑫事项的最迟时刻   i t L

　事项 i 的最迟时刻用   i t L 表示，它讲明在不阻碍任务总工期条件下，以它为始点的工序的最迟必须开始时刻，或以它为终点的各工作的最迟必须完成时刻。在一样情形下，把任务的最早完工时刻作为任务的总工期，所示事项最迟时刻的运算方法如下：

　             j , i t j t i tn n t n tLjLE Lmin为终点事项   i t L 为事项 i 相邻的各紧后事项的最迟时刻，它的运算从终点事项开始，按编号由大到小的顺序逐个运算。

　工序的时刻参数

　⑪工序的最早可能开始时刻和最早可能完工时刻

　一个工序   j , i 的最早可能开工时刻用   j , i t ES 表示，任何一个工序都必须在其所有紧前工序全部完工后才能开始。工序   j , i 的最早可能完工时刻用  j , i t EF 表示，它表示工作按最早开工时刻开始所能达到的完工时刻，运算公式如下：

　             1, 0, max , ,, , ,ESES ESkEF ESt jt i j t k i t k it i j t i j t i j         工序   j , i 的最早可能开工时刻   j , i t ES 等于事项最早时刻  Et i 。

　⑫工序的最迟必须开工时刻与最迟必须完工时刻

　一个工序   j , i 的最迟必须开工时刻用   j , i t LS 表示，它是工序   j , i 在不阻碍整个任务如期完成的前提下，必须开始的最晚时刻。工序   j , i 最迟必须完工时刻用   j , i t LF 表示，它表示工作   j , i 按最迟时刻开工，所能达到的完工时刻。

　                 j , i t j , i t j , i tk , j t k , j t min j , i tn t n , i tLS LFLSkLSE LF 工序   j , i 最迟必须完工时刻   j , i t LF 等于事项的最迟时刻  Lt j

　四、时差。

　工序的时差，又称为工序的机动时刻，工序时差分两种：

　⑪工序总时差   j , i R

　在不阻碍工程最早终止时刻的条件下，工序最早开始（或终止）时刻能够推迟的时刻：

　      j , i t j , i t j , i REF LF 

　⑫工序单时差   j , i r

　不阻碍紧后工序最早开始时刻的条件下，工序最早终止时刻能够推迟的时刻：

　      j , i t k , j t j , i rEF ES 

　式中，   k , j t ES 为工序   j , i 的紧后工序的最早开始时刻。

　总时差为零的工序，开始和终止的时刻没有一点机动的余地，由这些工序所组成的路线确实是网络中的关键路线，这些工序确实是关键工序。

　例 5-6：确定图 5-20 所示网络的关键路线。

　解：先用图上运算法求解，再用表上运算法验证。

　 图 5-21 10 10 0 25 26 1 2 3 4 5 6 7 9 8 10 1 2 3 2 3 10 6 5 2 A B C D E F G H I J K L 0 4 4 18 18 20 20 23 23 31 31 32 32 23 23 8 4 8 依照图 5-20 的资料，先运算各事项的时刻参数。

　⑪事项时刻

　如总开工事项①，   0 1 Et ，将结果填入图中编号上方空格

　的左边。逐个运算事项最早时刻，得到总完工事项⑩，   32 10 Et ，讲明整个工作需要 32 周的时刻完成。

　再从后面开始运算各事项最迟时刻，如总完工事项⑩的   32 10 Lt ，事项⑦的

　              23 2 26 8 31 8 7 8 9 7 9 7        , min , t t , , t t min tL L L 将结果填入编号上方空格

　右边。

　⑫工序时刻

　工序时刻有 4 种：

　        j , i t , j , i t , j , i t , j , i tLF LS EF ES，用图标

　表示，运算结果表示在图 5-22 上。

　 1 10 0 4 0 4 0 10 18 10 18 0 23 25 24 26 1 25 30 26 31 1 图 5-22 2 3 4 5 6 7 9 8 4 10 4 10 0 4 7 15 18 11 0 20 13 23 13 18 20 18 20 0 20 23 20 23 0 23 23 23 23

　23 25 29 31 6 0 31 32 31 32 0 0 20 13 23 0 1 2 3 2 3 10 6 5 2 A B C D E F G H I J K L 4 8 8 ⑬时差

　依照图 5-22 中的结果，能够求出各工序的总时差。由总时差为 0 的工序组成关键路线，即：①→②→③→④→⑤→⑥→⑦→⑨→⑩，总工期为 32 周。

　表 5-4 用来运算网络时刻，并标示出关键工序。

　表 5-4

　工序   j , i t

　  j , i t ES

　  j , i t EF

　  j , i t LS

　  j , i t LF

　  j , i R

　关键工序 A 4 0 4 0 4 0 √ B 10 0 10 13 23 13 × C 3 4 7 15 18 11 × D 6 4 10 4 10 0 √ E 8 10 18 10 18 0 √ ESt EFt LSt LFt

　F 2 18 20 18 20 0 √ C 3 20 23 20 23 0 √ 虚工序 0 23 23 23 23 0 √ H 2 23 25 24 26 1 × I 8 23 31 23 31 0 √ J 5 23 30 26 31 1 × K 2 25 25 29 31 6 × L 1 31 32 31 32 0 √

　 5.4.3 网络优化

　 绘制网络图，运算网络时刻和确定关键路线，得到一个初始的打算方案。从工期、成本、资源等方面对初步方案进一步的改善和调整，以求得最佳成效，确实是网络优化。目前尚未有能全面反映工期、成本、资源的综合数学模型，因此，网络优化咨询题是依照实际情形分为时刻优化、时刻-资源优化和时刻-费用优化。

　时刻优化

　依照对打算进度的要求，缩短工程完工时刻。能够采取措施：把串联工序改为平行或交叉工序，缩短关键工序的作业时刻；充分利用非关键工序的时差，减少这些作业的人力、资源用于关键工序，缩短关键工序的作业时刻。

　时刻-资源优化

　在编制网络打算安排工程进度时，考虑时刻优化的同时，尽量合理地利用有限的资源。具体的要求和做法是：

　⑪优先安排关键工序所需要的资源；

　⑫利用非关键工序的总时差，错开各工序的开始时刻，拉平资源需要量的高峰；

　⑬综合考虑资源和时刻，必要时，可适当地推迟工程完工时刻。

　在优化时，通常将打算的各要紧资源需要量按日程排出，再按以上方法，使各要紧资源的日负荷相对平稳。然而由于一项工程所包含的工序繁多，涉及到的资源利用情形复杂，需要多次综合平稳，才能得到在时刻进度和资源利用等方面都比较合理的打算方案。

　时刻-费用优化

　时刻-费用优化要研究和解决的咨询题是决定合理的工程完工时刻，使费用最省，或者以合理的费用代价 完成赶工作任务。

　工程费用包括两大类：

　⑪直截了当费用是完成各项 工作直截了当所需人力、资源设备费 用；为缩短工序的作业时刻，需要采取 一定的技术组织措施，相应会增加一 部分直截了当费用。

　⑫间接费用是指治理费、办工费等，常按施工时刻长短分摊。

　完成工程项目的直截了当费用、间接费用、总费用与工程完工时刻的关系，一样情形下如图 5-23 所示。

　明显，在网络打算中，最低成本日程具有重要意义。因此要运算网络打算的不同完工期相应的总费用，以求得成本最低的日程安排，即最低成本日程。

　下面举例讲明最低成本日程打算。

　例 5-7：已知网络打算各工序的正常工时、极限工时及相应费用如表 5-5，网络图如图 5-24。

　表 5-5

　工序 正常工时 极限工时 成本斜率 （元/天）

　时刻（天）

　费用（元）

　时刻（天）

　费用（元）

　①→② 24 5

　 0 ①→③ 3

　 0 100 ②→④ 22 4

　 0 ③→④ 26 1

　 150 ③→⑤ 24 8

　 0 ④→⑥ 18 5400 18 5400 / ⑤→⑥

　0 50 按正常工时运算出总工期 74 天，关键路线①→③→④→⑥，总直截了当费用为 47800 元。设正常工时下任务总间接费用为 18000 元，工期每缩短一天，间接费用可节约 330 元，求最低成本日程。

　 工程费用 总费用 直接费用 间接费用 最低成本日程 工期 图 5-23

　解：按下列步骤进行运算。

　从关键工作中选出缩短工时所需直截了当费用最少的方案及天数；

　按照新工时，重新运算网络打算 的关键路线及关键工作；

　运算由于缩短工时总费用的变 化。

　重复以上三个步骤，直到工期 不能再缩短为止。

　在图 5-24 上，选择关键路线中 成本斜率最小者①→③，最多可缩短 1 2天，即①→③新工时为 18 天。重新运算网络时刻参数，如图 5-25（a）所示，关键路线为①→②→④→⑥，工期为 64 天，实际只缩短 10 天，这意味着①→③工序的工时为 20 天。重新运算结果如图 5-25（b），总工期 64天，有两条关键路线①→②→④→⑥，①→③→④→⑥，直截了当费用增 10×100 元，间接费用减 10×330 元。

　 1 2 3 4 5 6 26 24 18 18 20 22 图 5-25 64  T 64  T 1 2 3 4 5 6 24 20 26 24 18 18

　重复上述步骤，将①→③，②→④的工时缩短为：18，20 天，重新运算网络时刻参数，结果如图 5-26。关键路线不变。增加直截了当费用 2×（100+200）=600 元，减少间接费用 2×330=660 元。

　 1 2 3 4 5 6 24 18 26 24 18 18 20 图 5-26 20 图 5-27 60  T 62  T 1 2 3 4 5 6 24 18 24 24 18 18

　第三次调整，在②→④，③→④工序上多缩短 2 天，重新运算网络时刻参数，结果如图 5-27，有三条关键路线，总工期 60 天，直截了当费用增加 2×350=700 元，间接费用减少 2×330=660 元。由于一条关键路线①→③→④→⑥上各工序工时不能缩短，运算终止。

　最低成日程为 62 天，总成本 63440 元。

　 习题：

　 74  T 1 2 3 4 5 6 24 30 26 24 18 18 22 图 5-24

　5.1 有 9 个都市9 2 1v , v , v  ，其公路网如图 5-28 所示。弧旁数字是该段公路的长度，有一批物资从1v 到9v ，咨询走哪条路最短？

　 • • • • • • • • • 3 3 3 3 3 4 4 4 2 2 2 5 3v2v1v

　4v5v6v7v8v9v图 5-28 2

　2

　5.2 用 DijKstra 方法求图 5-29 中从1v 到各点的最短路。

　 1v • • • • • • • • 3 3 4 4 2 2 2 5 3v2v4v5v6v7v8v图 5-29 2 8 7 1 9 1

　5.3 求图 5-30 网络中各顶点间的最短路。

　 20 16 14 10 12 18 9 20 1v

　-5 2v

　3v 4v 图 5-30 • • • • •

　5.4 某设备今后 5 年的价格推测分不是（5，5，6，7，8），若该设备连续使用，其第 j 年的修理费分不为（1，2，3，5，6）。某单位今年购进一台，咨询如何确定更新方案可使 5 年里总支出最小（不管设备使用了多青年，其残值为 0）。

　5.5 在如图 5-31 所示的网络中，每弧旁的数字是  ij ijf , c 。

　确定所有的截集；

　求最小截集的容量；

　证明指出的流是最大流。

　 • • • • • （4，3）

　（2，2）

　（5，2）

　（3，3）

　（3，1）

　（1，0）

　（2，2）

　1v

　 sv

　2v 图 5-31

　5.6 求如图 5-32 所示的网络的最大流，弧上数为  ij ijf , c 。

　 3，2 3，2 10，4 4，3 1，1 4，2 5，3 5v sv3v1v

　4v3v图 5-32 • • • • • • 3，2 8，3 7，6 2，2 4，3

　 5.7 如图 5-33，发点2 1s , s 分不可供应 10 和 15 个单位，收点2 1t , t 能够接收 10 和 25 个单位，求最大流，弧上数为ijc 。

　 • 2 2 3 3 7 6 7 7 3 4 1v

　 2v

　1s

　2s 图 5-33 • • • •

　5-8 试画出表 5-6 所表示项目的网络图。

　表 5-6

　工作 工时（d）

　紧前工序 工作 工时（d）

　紧前工序 A 15 -- F 5 D，E B 10 -- G 20 C，F C 10 A，B H 10 D，E D 10 A，B I 15 G，H E 5 B

　5-9 设有如图 5-34 网络图，用图上运算法运算时刻参数，并求出关键路线。

　 1 2 4 3 5 6 8 9 7 10 11 12 4 4 5 8 6 10 2 0 6 13 7 3 9 8 5 图 5-34

　5-10 绘 制表 5-7 所示的网络图，并用表上运算法运算工作的各项时刻参数，确定关键路线。

　表 5-7

　工作 工时（d）

　紧前工序 工作 工时（d）

　紧前工序 A 5 -- F 4 B，C B 8 A，C G 8 C C 3 A H 2 F，G D 6 C I 4 E，H E 10 B，C J 5 F，G

　 5-11 已知下列资料

　表 5-8

　活动 作业时刻（d）

　紧前活动 正常完成进度的直截了当费用（百元）

　赶进度 1 天所需费用（百元）

　A 4 -- 20 5 B 8 -- 30 4 C 6 B 15 3 D 3 A 5 2 E 5 A 18 4 F 7 A 40 7 G 4 B，D 10 3 H 3 E，F，G 15 6 工程的间接费 5（百元/天），求出该项工程的最低成本日程。