管 理 运 筹 学 1
第十一章 图与网络模型
§ 1 图与网络的基本概念
§ 2 最短路问题
§ 3 最小生成树问题
§ 4 最大流问题
§ 5 最小费用最大流问题管 理 运 筹 学 2
§ 1 图与网络的基本概念图论中图是由点和边构成，可以反映一些对象之间的关系。
例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图 11-1就是一个表示这种关系的图。
(v1)
赵
(v2)钱
(v3)孙
(v4)
李
(v5)
周 (v6)吴
(v7)陈
e2
e1 e
3
e4
e5
图 11-1
管 理 运 筹 学 3
§ 1 图与网络的基本概念当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以用图 11-2来表示，
可见图论中的图与几何图、工程图是不一样的。
(v1)
赵 (v
2)钱 孙 (v3) 李 (v4) 周 (v5) 吴 (v6) 陈 (v7)
e2
e1 e3 e4 e5
图 11-2
管 理 运 筹 学 4
§ 1 图与网络的基本概念
a1
a2
a3
a4
a14
a7
a8
a9
a6a5
a10
a12
a11
a13
a15(v1)赵
(v2)钱
(v3)孙
(v4)
李
(v5)
周
(v6)吴
(v7)陈图 11-3
如果我们把上面例子中的“相互认识”关系改为“认识”
的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图 11-3就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。
管 理 运 筹 学 5
§ 1 图与网络的基本概念
无向图：
由点和边构成的图，记作 G=（ V,E）。
有向图：
由点和弧构成的图，记作 D=（ V,A）。
连通图,
对无向图 G，若任何两个不同的点之间，至少存在一条链，则 G为连通图。
回路：
若路的第一个点和最后一个点相同，则该路为回路。
赋权图：
对一个无向图 G的每一条边 (vi,vj)，相应地有一个数 wij，则称图 G
为赋权图,wij称为边 (vi,vj)上的权。
网络：
在赋权的有向图 D中指定一点，称为发点，指定另一点称为收点，
其它点称为中间点，并把 D中的每一条弧的赋权数称为弧的容量,D就称为网络。
管 理 运 筹 学 6
§ 2 最短路问题最短路问题在实际中具有广泛的应用,如管道铺设,线路选择等问题,还有些如设备更新,投资等问题也可以归结为求最短路问题求最短路有两种算法：
一是求从某一点至其它各点之间最短离的 狄克斯屈拉
(Dijkstra)算法另一种是求网络图上任意两点之间最短路的 Floyd(弗洛伊德 )
矩阵算法 。
最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路
6.2.1最短路问题的网络模型管 理 运 筹 学 7
§ 2 最短路问题
最短路问题：对一个赋权的有向图 D中的指定的两个点 Vs和 Vt找到一条从 Vs 到 Vt 的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从 Vs到 Vt的最短路。这条路上所有弧的权数的总和被称为从 Vs到 Vt
的距离。
一、求解最短路的 Dijkstra算法 (双标号法）
步骤：
1.给出点 V1以标号 (0,s)
2.找出已标号的点的集合 I，没标号的点的集合 J以及弧的集合
3,如果上述弧的集合是空集，则计算结束。如果 vt已标号（ lt,kt），则 vs
到 vt的距离为 lt，而从 vs到 vt的最短路径，则可以从 kt 反向追踪到起点
vs 而得到。如果 vt 未标号，则可以断言不存在从 vs到 vt的有向路。如果上述的弧的集合不是空集，则转下一步。
4,对上述弧的集合中的每一条弧，计算 sij=li+cij 。在所有的 sij中，找到其值为最小的弧。不妨设此弧为（ Vc,Vd），则给此弧的终点以双标号
（ scd,c）,返回步骤 2。
{ (,) |,}i j i jv v v I v J
管 理 运 筹 学 8
§ 2 最短路问题例 1 求下图中 v1到 v6的最短路解：采用 Dijkstra算法，可解得最短路径为 v1 v3 v4 v6
各点的标号图如下：
v2
3
5 2
7
5
3 1
5
12
v1
v6
v5v
3
v4
(3,1)v
2
3
5 2
7
5
3 1
5
12
V1
（ 0,s)
v5
(8,4)v
6
(2,1)v
3
(3,3)v
4
管 理 运 筹 学 9
§ 2 最短路问题
②
③
④
⑤
⑥
⑦
6
10
12
3 2
14
67
5
8
11
16
5
图 6－ 6
9
0,0
6
10
12
9
20
9,2
18
6,1
①
16
12,1 17 16,3
24
32
18,3
29
29,5
【 例 】 用 Dijkstra算法求图 6－ 6 所示 v1到 v7的最短路及最短路长
v1 到 v7的最短路为,p17=｛ v1,v2,v3,v5,v7｝，最短路长为 L17=29
14
管 理 运 筹 学 10
【 例 】 求图 6-10所示 v1到各点的最短路及最短距离
①
②
③
④
⑤
⑥
⑦
⑧
4
5
2
6
1
7
8
3
9
3
2
6
12
16
18
0,0
4
5
2
2,1
3
10
3,4
9 6
12
6
4,1 11 6,3
6,3
18
8
12
24
8,5 24 18,5
所有点都已标号，点上的标号就是 v1到该点的最短距离，最短路线就是红色的链。
图 6-10
§ 2 最短路问题管 理 运 筹 学 11
§ 2 最短路问题例 2 电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。
解：这是一个求无向图的最短路的问题。可以把无向图的每一边
（ vi,vj）都用方向相反的两条弧（ vi,vj）和（ vj,vi）代替，就化为有向图，即可用 Dijkstra算法来求解。也可直接在无向图中用 Dijkstra算法来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。
V1
（甲地）
15
17
6
24
4
3
10
6
5v2
V7 （乙地）
v3
v4
v5
v6
管 理 运 筹 学 12
§ 2 最短路问题例 2最终解得：
最短路径 v1 v3 v5 v6 v7，每点的标号见下图
（ 0,s）
V1
（甲地）
15
17
6
24
4
3
10
6
5
(13,3)v
2
(22,6)
V7 （乙地）
V5(14,3)
V6(16,5)
V3(10,1)
V4(18,5)
管 理 运 筹 学 13
§ 2 最短路问题例 3 设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。
已知：设备每年年初的价格表设备维修费如下表年份 1 2 3 4 5
年初价格 11 11 12 12 13
使用年数 0-1 1-2 2-3 3-4 4-5
每年维修费用
5 6 8 11 18
管 理 运 筹 学 14
§ 2 最短路问题例 3的解：
将问题转化为最短路问题，如下图：
用 vi表示“第 i年年初购进一台新设备”,弧（ vi,vj）表示第 i年年初购进的设备一直使用到第 j年年初。
把所有弧的权数计算如下表：
v1 v2 v3 v4 v5 v6
1 2 3 4 5 6
1 16 22 30 41 59
2 16 22 30 41
3 17 23 31
4 17 23
5 18
6
管 理 运 筹 学 15
§ 2 最短路问题
(继上页 ) 把权数赋到图中，再用 Dijkstra算法求最短路。
最终得到下图，可知,v1到 v6的距离是 53，最短路径有两条：
v1 v3 v6和 v1 v4 v6
v1 v2 v3 v4 v5 v616
22 30
41
59
16
22
30
41
3123
17 1817
23
V1
（ 0,s） v3 v4 (41,1)
v5
v6
22 30
41
59
16
(22,1)
30
41
3123
17 1817
23
V2
（ 16,1）
16
(30,1)
(53,3)
(53,4)
管 理 运 筹 学 16
§ 2 最短路问题
6.2.4 最短路应用举例
【 例 】 设备更新问题。企业在使用某设备时，每年年初可购置新设备，也可以使用一年或几年后卖掉重新购置新设备。已知 4
年年初购置新设备的价格分别为 2.5,2.6,2.8和 3.1万元。设备使用了 1～ 4年后设备的残值分别为 2,1.6,1.3和 1.1万元，使用时间在 1～ 4年内的维修保养费用分别为 0.3,0.8,1.5和 2.0万元。
试确定一个设备更新策略，在下例两种情形下使 4年的设备购置和维护总费用最小。
（ 1）第 4年年末设备一定处理掉；
（ 2）第 4年年末设备不处理。
【 解 】 画网络图。用点 (1,i,…,j)表示第 1年年初购置设备使用到第
i年年初更新，经过若干次更新使用到第 j年年初，第 1年年初和第 5年年初分别用①及⑤表示。使用过程用弧连接起来，弧上的权表示总费用 (购置费＋维护费－残值 )，如图 6－ 16所示管 理 运 筹 学 17
§ 2 最短路问题
① ⑤6
图 6－ 16
(1,2,3)
(1,4)
(1,3,4)
(1,2,4)
(1,2,3,4)
(1,2)
(1,3)
第一年 第二年 第三年 第四年
5.1
0.9
1.5
0.7
3.6
2.8
1.7 -0.2
1.9
1.1
2.1
0.3
-0.6
-0.6
网络图 6－ 16说明：如图中点 (1,3)表示第 1年购置设备使用两年到第 3年年初更新购置新设备，这时有 2种更新方案，使用 1年到第 4年年初、使用 2年到第 5年年初,更新方案用弧表示，点（ 1,2,3）表示第 1年购置设备使用一年到第二年年初又更新，使用一年到第三年初再更新，这时仍然有 2种更新方案，使用 1年到第
4年年初和使用 2年到第 5年年初。
管 理 运 筹 学 18
§ 2 最短路问题点（ 1,3）和点（ 1,2,3）不能合并成一个点，虽然都是第三年年初购置新设备，购置费用相同，但残值不同。点 (1,3)的残值等于 1.6(使用了两年 )，点 (1,2,3)的残值等于 2(使用了一年 )。点
（ 1,3）到点（ 1,3,4）的总费用为第三年的购置费＋第一年的维护费－设备使用两年后的残值
＝ 2.8+0.3－ 1.6=1.5
点（ 1,3）到点⑤的总费用为第三年的购置费＋第一年的维护费＋第二年的维护费－设备使用两年后的残值－第四年末的残值
＝ 2.8+0.3+0.8－ 1.6－ 1.6=0.7。
管 理 运 筹 学 19
§ 2 最短路问题
① ⑤6
图 6－ 16
(1,2,3)
(1,4)
(1,3,4)
(1,2,4)
(1,2,3,4)
(1,2)
(1,3)
第一年 第二年 第三年 第四年
5.1
0.9
1.5
0.7
3.6
2.8
1.7 -0.2
1.9
1.1
2.1
0.3
-0.6
-0.6
（ 1）第四年末处理设备,求点①到点⑤的最短路。用 Dijkstra
算法得到最短路线为：
① → (1,2)→(1,2,3)→ ⑤,最短路长为 4。
4年总费用最小的设备更新方案是：第 1年购置设备使用 1年，
第 2年更新设备使用 1年后卖掉，第 3年购置设备使用 2年到第 4年年末,4年的总费用为 4万元。
管 理 运 筹 学 20
§ 3 最小生成树问题
树是图论中的重要概念，所谓树就是一个无圈的连通图。
图 11-11中,(a)就是一个树，而 (b)因为图中有圈所以就不是树,(c)因为不连通所以也不是树。
图 11-11
v1
v2 v
3
v4v5v
6
v7
v8 v9
v1
v2 v3
v5
v8
v7
v6
v4
v1
v2
v3
v4
v5
v7 v6
v8
v9
(a) (b) (c)
管 理 运 筹 学 21
可以证明：
（ 1）一棵树的边数等于点数减 1；
（ 2）在树中任意两个点之间添加一条边就形成圈；
（ 3）在树中去掉任意一条边图就变为不连通。
§ 3 最小生成树问题管 理 运 筹 学 22
§ 3 最小生成树问题给了一个无向图 G=(V,E)，我们保留 G的所有点，而删掉部分 G的边或者说保留一部分 G的边，所获得的图 G，称之为 G的生成子图。在图 11-12中，
(b)和 (c)都是 (a)的生成子图。
如果图 G的一个生成子图还是一个树，则称这个生成子图为生成树，
在图 11-12中,(c)就是 (a)的生成树。
最小生成树问题就是指在一个赋权的连通的无向图 G中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。
图 11-12
(a) (b) (c)
管 理 运 筹 学 23
§ 3 最小生成树问题一、求解最小生成树的破圈算法算法的步骤：
1、在给定的赋权的连通图上任找一个圈。
2、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。
3、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第 1步。
管 理 运 筹 学 24
5
v1
v2
v3
v4
v5
v6
8
4
3
7
5
2
6
18
图 6－ 1
【 例 】 用破圈法求图 6－ 1的最小树。
图 6－ 4
图 6－ 4就是图 6－ 1的最小部分树，最小树长为
C(T)=4+3+5+2+1=15。
当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同
§ 3 最小生成树问题管 理 运 筹 学 25
§ 3 最小生成树问题例 4 用破圈算法求图（ a）中的一个最小生成树
v1 3
3
1
7
2
85410 3
4
v7
v6 v5
v4
v2
v1 3
3
1
7
2
8543
4
v7
v6 v5
v4
v2
v1 3
3 7
2
543
4
v7
v6 v5
v4
v2
v3 v3
v31
v1 3
3 7
2
4
3
4
v7
v6 v5
v4
v2 v31
v1 3
3 7
2
3
4
v7
v6 v5
v4
v2 v31
v1 3
3 7
2
3
v7
v6 v5
v4
v2 v31
(a) (b)
(c) (d)
(e) (f)图 11-13
管 理 运 筹 学 26
加边法,取图 G的 n个孤立点 ｛ v1,v2,…,vn}作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有
n－ 1条边）
v1
v2
v3
v4
v5
v6
4
3
5
2 1
图 6－ 5
在图 6－ 5中，如果添加边 [v1,v2]就形成圈｛ v1,v2,v4｝，这时就应避开添加边 [v1,v2]，添加下一条最短边 [v3,v6]。破圈法和加边法得到树的形状可能不一样，但最小树的长度相等
5
v1 v3 v5
15
v2 v4 v6
8
4
3
7
5
2
6
8×
Min C(T)=15
§ 3 最小生成树问题管 理 运 筹 学 27
§ 3 最小生成树问题例 5、某大学准备对其所属的 7个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中 v1,…,v 7 表示 7个学院办公室，请设计一个网络能联通 7个学院办公室，并使总的线路长度为最短。
解：此问题实际上是求图 11-14的最小生成树，这在例 4中已经求得，
也即按照图 11-13的 (f)设计，可使此网络的总的线路长度为最短，为 19
百米。
“管理运筹学软件”有专门的子程序可以解决最小生成树问题。
v1 3
3
1
7
2
85
4
10 3
4
v7
v6 v5
v4
v2 v3
图 11-14
管 理 运 筹 学 28
§ 4 最大流问题
6.3.1 基本概念
①
②
③
④
⑤
⑥
8
14
5
6
3
3
8
10
7
6
⑦
3
图 6－ 18
4
图 6－ 18所示的网络图中定义了一个 发点 v1，称为源 (source,supply
node），定义了一个 收点 v7，称为汇（ sink,demand node），其余点 v2,v3,…,v6为 中间点,称为 转运点 (transshipment nodes)。如果有多个发点和收点，则虚设发点和收点转化成一个发点和收点。图中的权是该弧在单位时间内的最大通过能力，称为弧的 容量 (capacity)。
最大流问题是在单位时间内安排一个运送方案，将发点的物质沿着弧的方向运送到收点，使总运输量最大。
管 理 运 筹 学 29
§ 4 最大流问题设 cij为弧（ i,j）的容量,fij为弧（ i,j）的流量。
容量是弧（ i,j）单位时间内的 最大通过能力,流量是弧（ i,j）
单位时间内的 实际通过量,流量的集合 f={fij}称为网络的流。发点到收点的总流量记为 v=val(f),v也是网络的 流量 。
图 6－ 18最大流问题的线性规划数学模型为
),(0
0
0
m a x
6747571312
1312
jicf
vff
fffff
ffv
ijij
m
v
mj
v
im
mm
所有弧所有中间点管 理 运 筹 学 30
§ 4 最大流问题满足下例 3个条件的流 fij 的集合 f ={ fij }称为可行流
1 ) 0 (,)i j i jf c i j（ 所 有 弧
( 3 )
st
s j it
vv
v f f
发点 vs流出的总流量等于流入收点 vt的总流量
(2 )
mm
i m m j m
vv
f f v 所 有 中 间 点管 理 运 筹 学 31
§ 4 最大流问题链,从发点到收点的一条路线（弧的方向不一定都同向）称为链。
从发点到收点的方向规定为链的方向。
前向弧,与链的方向相同的弧称为前向弧。
后向弧,与链的方向相反的弧称为后向弧。
增广链,设 f 是一个可行流，如果存在一条从 vs到 vt的链，满足：
1.所有前向弧上 fij<Cij
2.所有后向弧上 fij>0
则该链称为增广链
①
②
③
④
⑤
⑥前向弧后向弧容量流量这是一条增广链
8
4
4
6
9（ 5）
(2)
(3)
(4)
(6)
管 理 运 筹 学 32
§ 4 最大流问题步骤如下：
第二步：对点进行标号找一条增广链。
（ 1）发点标号 （ ∞）
（ 2）选一个点 vi 已标号并且另一端未标号的弧沿着某条链向收点检查：
A．如果弧的方向向前（前向弧）并且有 fij<cij，则 vj标号,
θj＝ cij－ fij
B,如果弧的方向指向 vi（后向弧）并且有 fji>0，则 vj标号,
θj＝ fji
当收点已得到标号时，说明已找到增广链，依据 vi 的标号反向跟踪得到一条增广链。当收点不能得到标号时，说明不存在增广链，计算结束。
第一步,找出第一个可行流，例如所有弧的流量 fij =0
6.3.2 Ford-Fulkerson标号算法管 理 运 筹 学 33
§ 4 最大流问题第三步：调整流量
（ 1）求增广链上点 vi 的标号的最小值，得到调整量
m in jj
（ 2）调整流量
),(
),(
),(
1
jif
jif
jif
f
ij
ij
ij
得到新的可行流 f1，去掉所有标号，返回到第二步从发点重新标号寻找增广链，直到收点不能标号为止
【 定理 6.1】 可行流 f是最大流的充分必要条件是不存在发点到收点的增广链管 理 运 筹 学 34
§ 4 最大流问题
①
②
③
④
⑤
⑥
8
14
5
6
3
3
8
10
7
6
⑦
3
图 6－ 19
(10)
(6)
(3)
(6)
(3)
(7)
(0) (6)(1)
4
(3)(1)
(7)
【 例 】 求图 6－ 18发点 v1到收点 v7的最大流及最大流量
【 解 】 给定初始可行流，见图 6-19
管 理 运 筹 学 35
§ 4 最大流问题
①
②
③
④
⑤
⑥
8
14
5
6
3
3
8
10
7
6
⑦
3
图 6－ 20(b)
(10)
(6)
(3)
(6)
(3)
(7)
(0) (6)(1)
4
(3)(1)
(7)
∞
2
3
3
7
第一轮标号：
c12>f12,v2标号 2
cij=fij,v4,v5不能标号后向弧 f32>0,
v3标号 θ3=f32
增广链 μ＝ {(1,2),(3,2),(3,4),(4,7) },μ+={(1,2),(3,4)，
(4,7)},μ－ ={(3,2)}，调整量为增广链上点标号的最小值
θ＝ min{∞,2,3,3,7}＝ 2
管 理 运 筹 学 36
§ 4 最大流问题
①
②
③
④
⑤
⑥
8
14
5
6
3
3
8
10
7
6
⑦
3
图 6－ 21
(10)
(8)
(1)
(6)
(3)
(7)
(2) (6)(1)
4
(5)(1)
(7)
调整后的可行流：
管 理 运 筹 学 37
§ 4 最大流问题
①
②
③
④
⑤
⑥
8
14
5
6
3
3
8
10
7
6
⑦
3
图 6－ 22
(10)
(8)
(1)
(6)
(3)
(7)
(2) (6)(1)
4
(5)(1)
(7)
∞
4
4
1
5
第二轮标号,Cij=fij,v4,v5不能标号，返回到 v3
增广链 μ＝ μ＋ ＝ {(1,3),(3,4),(4,7) }，调整量为
θ＝ min{∞,4,1,5}＝ 1
管 理 运 筹 学 38
§ 4 最大流问题
①
②
③
④
⑤
⑥
8
14
5
6
3
3
8
10
7
6
⑦
3
图 6－ 23
(11)
(8)
(1)
(6)
(3)
(7)
(3) (6)(1)
4
(6)(1)
(7)
调整后得到可行流：
管 理 运 筹 学 39
§ 4 最大流问题
①
②
③
④
⑤
⑥
8
14
5
6
3
3
8
10
7
6
⑦
3
图 6－ 22
(11)
(8)
(1)
(6)
(3)
(7)
(3) (6)(1)
4
(6)(1)
(7)
∞
3 1
4
第三轮标号：
增广链 μ＝ μ＋ ＝ {(1,3),(3,6),(6,4),(4,7) }，调整量为
θ＝ min{∞,3,1,2,4}＝ 1
2
管 理 运 筹 学 40
§ 4 最大流问题
①
②
③
④
⑤
⑥
8
14
5
6
3
3
8
10
7
6
⑦
3
图 6－ 25
(12)
(8)
(1)
(6)
(3)
(8)
(3) (6)(2)
4
(7)(1)
(7)
调整后得到可行流：
管 理 运 筹 学 41
§ 4 最大流问题
①
②
③
④
⑤
⑥
8
14
5
6
3
3
8
10
7
6
⑦
3
图 6－ 22
(12)
(8)
(1)
(6)
(3)
(8)
(3) (6)(2)
4
(7)(1)
(7)
∞
2
第四轮标号：
v7得不到标号，不存在 v1到 v7的增广链，图 6-22所示的可行流是最大流，最大流量为
v＝ f12+f13＝ 8+12=20
Cij=fij,v4,v5不能标号
Cij=fij,v4,v6不能标号
4
管 理 运 筹 学 42
§ 4 最大流问题无向图最大流标号算法无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端 vi
已标号另一端 vj未标号的边只要满足 Cij－ fij>0 则 vj就可标号
（ Cij－ fij）
【 例 】 求下图 v1到则 v7标的最大流
7
①
②
③
④
⑤
⑥
⑦
12
9
20
8
5
14
8 6
9
13
16
(10)
(6)
(10)
(8)
(2)
(3)
(7)
(6)
(5)
(13)
(0)
(13)
∞
2
3
9
9
3
2
管 理 运 筹 学 43
§ 4 最大流问题
7
①
②
③
④
⑤
⑥
⑦
12
9
20
8
5
14
8 6
9
13
16
(12)
(6)
(10)
(8)
(4)
(3)
(7)
(6)
(7)
(13)
(2)
(15)
∞
3
7
7
1
1
7
①
②
③
④
⑤
⑥
⑦
12
9
20
8
5
14
8 6
9
13
16
(12)
(7)
(10)
(8)
(4)
(3)
(7)
(6)
(8)
(13)
(3)
(16)
V=29
∞
10
5
6
6
1
管 理 运 筹 学 44
§ 4 最大流问题截集 将图 G＝（ V,E）的点集分割成两部分
〕，的弧集合（箭头在，则箭尾在及 1__11__11__1 VVVVVvVv ts
并且,1__1 VV
称为一个截集，截集中所有弧的容量之和称为截集的截量。
①
②
③
④
⑤
⑥
6
8
4
4
1
2
2
6
7
9
6
4
1
1
3 2
2
3
0
6
下图所示的截集为)5,3(),4,3(),2,1(),( 11?VV
10226),( 11VVC截量管 理 运 筹 学 45
§ 4 最大流问题
①
②
③
④
⑤
⑥
6
8
4
4
1
2
2
6
7
9
6
4
0
1
3 2
2
1
0
6
又如下图所示的截集为)6,5()4,5(),4,3(),4,2(),( 11,?VV
219624),( 11VVC截量上图所示的截集为
)5,3(),4,3(),5,2(),4,2(),( 11?VV 92214),( 11VVC截量所有截量中此截量最小且等于最大流量，此截集称为最小截集。
【 定理 】 最大流量等于最小截集的截量。
管 理 运 筹 学 46
§ 4 最大流问题
最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，
在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。
一、最大流的数学模型例 6 某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（ vi,vj）的流量 cij（容量）也是不一样的。 cij的单位为万加仑 /小时。如果使用这个网络系统从采地 v1向销地 v7运送石油，问每小时能运送多少加仑石油？
v5
6
3 5
2 2
2 4
1
2
6 3
v1
v2
v7
v4
v3
v6
图 11-26
管 理 运 筹 学 47
§ 4 最大流问题我们可以为此例题建立线性规划数学模型：
设弧 (vi,vj)上流量为 fij，网络上的总的流量为 F，则有：
14
1 2 2 3 2 5
1 4 4 3 4 6 4 7
2 3 4 3 3 5 3 6
2 5 3 5 5 7
3 6 4 6 6 7
5 7 6 7 4 7 1 2 1 4
,1,2,,6 ; 1,2,7
0,1,2,,6 ; 1,2,7
12
ij ij
ij
m a x F = f f
f f f
f f f f
f f f f
f f f
f f f
f f f f f
f c i j
f i j
目 标 函 数,
约 束 条 件,
管 理 运 筹 学 48
§ 4 最大流问题在这个线性规划模型中，其约束条件中的前 6个方程表示了网络中的流量必须满足守恒条件，发点的流出量必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必须等于总流出量。其后面几个约束条件表示对每一条弧
(vi,vj)的流量 fij要满足流量的可行条件，应小于等于弧 (vi,vj)
的容量 cij，并大于等于零，即 0≤ fij≤ cij。我们把满足守恒条件及流量可行条件的一组网络流 {fij}称之为可行流，
（即线性规划的可行解），可行流中一组流量最大（也即发出点总流出量最大）的称之为最大流（即线性规划的最优解）。
我们把例 6的数据代入以上线性规划模型，用“管理运筹学软件”，马上得到以下的结果,f12=5,f14=5,f23=2，
f25=3,f43=2,f46=1,f47=2,f35=2,f36=2,f57=5,f67=3。最优值（最大流量） =10。
管 理 运 筹 学 49
§ 4 最大流问题二、最大流问题网络图论的解法对网络上弧的容量的表示作改进。为省去弧的方向，如下图,(a)和
(b),(c)和 (d)的意义相同。
用以上方法对例 6的图的容量标号作改进，得下图
vi vj vi vj
cij 0
（ a） （ b）
cij
cij
vi vj（ c
ji） （ c） vi vj
cij cji
（ d）
6
3 52
2 2 4
1 2
6
3
v1
v2
v5
v7
v4
v3
v6
0
0
0 00 0
0
0
0
0
0
管 理 运 筹 学 50
§ 4 最大流问题求最大流的基本算法
（ 1）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。
（ 2）找出这条路上各条弧的最小的顺流的容量 pf，通过这条路增加网络的流量 pf。
（ 3）在这条路上，减少每一条弧的顺流容量 pf,同时增加这些弧的逆流容量 pf，返回步骤（ 1）。
用此方法对例 6求解：
第一次迭代：选择路为 v1 v4 v7 。弧（ v4,v7 ）的顺流容量为 2，
决定了 pf=2，改进的网络流量图如下图：
6
3 52
2 2 4
1 2
6
3
v1
v2
v5
v7
v4
v3
v6
0
0
0 00
0
0
0
0
0
04
2
02
管 理 运 筹 学 51
§ 4 最大流问题第二次迭代：选择路为 v1 v2 v5 v7 。弧（ v2,v5 ）的顺流容量为
3，决定了 pf=3，改进的网络流量图如下图：
第三次迭代：选择路为 v1 v4 v6 v7 。弧（ v4,v6 ）的顺流容量为
1，决定了 pf=1，改进的网络流量图如下图：
6
3 52
2 2 4
13
v1
v2
v5
v7
v4
v3
v6
0
0 0
0
0
0
0
04
2
02
20 3
3
3
0
3
2
2 2 4
13
v1
v2
v5
v7
v4
v3
v6
0
0 0
0
0
04
2
02
20 3
3
3
3
3
0
1
3
管 理 运 筹 学 52
第四次迭代：选择路为 v1 v4 v3 v6 v7 。弧（ v3,v6 ）的顺流容量为 2，决定了 pf=2，改进的网络流量图如下图：
第五次迭代：选择路为 v1 v2 v3 v5 v7 。弧（ v2,v3 ）的顺流容量为 2，决定了 pf=2，改进的网络流量图如下图：
2
2 2 4
3
v1
v2
v5
v7
v4
v3
v6
1
0
0
0
01 2
03
20 3
3
3
5
0
3
1
2
0
02 3 13
2
2
v1
v2
v5
v7
v4
v3
v6
1
0
1 2
0
20 3
3
3
5 01
2
0 2 3 1
31 5
0 0
2
0
2 0 5
§ 4 最大流问题管 理 运 筹 学 53
经过第五次迭代后在图中已经找不到从发点到收点的一条路，路上的每一条弧顺流容量都大于零，运算停止。得到最大流量为 10。
最大流量图如下图：
2
2
v1
v2 v5
v7
v4
v3
v6
1
2
3
5
2
2 35
5
§ 4 最大流问题
“管理运筹学软件”中还有专门的子程序用于解决最大流问题。
管 理 运 筹 学 54
§ 4 最大流问题最大流应用举例
【 例 6.12】 某公司需要招聘 5个专业的毕业生各一个，通过本人报名和筛选，公司最后认为有 6人都达到录取条件。这 6人所学专业见表 6-10,表中打,√”表示该生所学专业。公司应招聘哪几位毕业生，如何分配他们的工作毕业生 A.市场 营销 B.工程管理 C.管理信息 D.计算机 E.企业管理
1 √ √
2 √ √
3 √ √
4 √ √
5 √ √
6 √ √
表 6-10
管 理 运 筹 学 55
§ 4 最大流问题
①
②
③
④
⑤
⑥
A
B
C
D
E
s t
(1)
(1)
(1)
(1)
(1)
(1)
(1)
(1)
(1)
(1)
(1)
(1)
(1)
(1)
(1)
图 6－ 32
【 解 】 画出一个图，虚设一个发点和一收点，每条弧上的容量等于 1，问题为求发点到收点的最大流，求解结果之一见图 6－
32。公司录取第 2～ 6号毕业生，安排的工作依次为管理信息、
企业管理、市场营销、工程管理和计算机。
管 理 运 筹 学 56
§ 4 最大流问题
【 例 】 某市政工程公司在未来 5～ 8月份内需完成 4项工程,A.修建一条地下通道,B.修建一座人行天桥,C.新建一条道路及 D.
道路维修。工期和所需劳动力见表 6-11。该公司共有劳动力 120
人，任一项工程在一个月内的劳动力投入不能超过 80人，问公司如何分配劳动力完成所有工程，是否能按期完成工期 需要劳动力（人月）
A,地下通道 5～ 7月 100
B,人行天桥 6～ 7月 80
C,新建道路 5～ 8月 200
D,道路维修 8月 80
表 6-12
【 解 】 将工程计划用网络图 6－ 33表示。设点 v5,v6,v7,v8分别表示 5～ 8月份,Ai,Bi,Ci,Di表示工程在第 i个月内完成的部分，用弧表示某月完成某项工程的状态，弧的容量为劳动力限制。就是求图 6－ 33从发点到收点的最大流问题。
管 理 运 筹 学 57
§ 4 最大流问题
⑤
⑥
⑦
⑧
A5
B6
C7
D8
s t
图 6－ 33
A6
C5
A7
C6
B7
C8
A
B
C
D
120
120
120
120
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
100
80
200
80
(100)
(120)
(120)
(120)
(20)
(80)
(40)
(80)
(0)
(40)
(80)
(0)
(40)
(80)
(20)
(80) (80)
(40)
(80)
(80)
(40)
(0)
(40)
(80)
(100)
(80)
(200)
(80)
管 理 运 筹 学 58
§ 4 最大流问题标号算法求解得到图 6－ 33，括号内的数字为弧的流量。每个月的劳动力分配见表 6-13。 5月份有剩余劳动力 20人,4项工程恰好按期完成表 6-13
月份 投入劳动力 项目 A(人 ) 项目 B(人 ) 项目 C(人 ) 项目 D(人 )
5 100 20 80
6 120 40 80
7 120 80 40
8 120 40 80
合计 (人 ) 460 100 80 200 80
管 理 运 筹 学 59
§ 5 最小费用最大流问题
最小费用最大流问题：给了一个带收发点的网络，对每一条弧
（ vi,vj），除了给出容量 cij外，还给出了这条弧的单位流量的费用 bij，要求一个最大流 F，并使得总运送费用最小。
一、最小费用最大流的数学模型例 7 由于输油管道的长短不一，所以在例 6中每段管道（ vi,vj ）除了有不同的流量限制 cij外，还有不同的单位流量的费用 bij,cij的单位为万加仑 /小时,bij的单位为百元 /万加仑。如图。从采地 v1向销地 v7运送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流量和最小费用。
(6,6)
(3,4) (5,7)
(2,5)
(2,4)
（ 2,3） (4,4)
(1,3)
(2,8)（ 3,2）
v1
v2
v5
v7
v4
v3
v6
(6,3)
管 理 运 筹 学 60
§ 5 最小费用最大流问题这个最小费用最大流问题也是一个线性规划的问题。
解：我们用线性规划来求解此题，可以分两步走。
第一步，先求出此网络图中的最大流量 F，这已在例 6中建立了线性规划的模型，通过管理运筹学软件已经获得结果。
第二步，在最大流量 F的所有解中，找出一个最小费用的解，我们来建立第二步中的线性规划模型如下：
仍然设弧（ vi,vj）上的流量为 fij，这时已知网络中最大流量为 F，只要在例 6的约束条件上，再加上总流量必须等于 F的约束条件,f12=f14=F,即得此线性规划的约束条件，此线性规划的目标函数显然是求其流量的最小费用 。
由此得到线性规划模型如下,(,)ij
ij ij
v v A
fb
管 理 运 筹 学 61
§ 5 最小费用最大流问题
12 14 25 23 43
(,)
35 57 36 46 47 67
12 14
12 23 25
14 43 46 47
23 43 35 36
25 35 57
36 46 67
57 67 47 12 14
m i n 6 3 4 5 2
4 7 3 3 8 4
..
10,
,
,
,
,
,
,
,( 1,2,,6 ;
ij
ij ij
v v A
ij ij
f b f f f f f
f f f f f f
st
f f F
f f f
f f f f
f f f f
f f f
f f f
f f f f f
f c i j
2,3,7 ),
0,( 1,2,,6 ; 2,3,7 ),
ij
f i j
管 理 运 筹 学 62
§ 5 最小费用最大流问题用管理运筹学软件，可求得如下结果,f12=4,f14=6,
f25=3,f23=1,f43=3,F57=5,f36=2,f46=1,f47=2,f67=3,f35=2。其最优值 (最小费用 )=145。对照前面例 6的结果，可对最小费用最大流的概念有一个深刻的理解。
如果我们把例 7的问题改为：每小时运送 6万加仑的石油从采地 v1到销地 v7最小费用是多少？应怎样运送？这就变成了一个最小费用流的问题。一般来说，所谓最小费用流的问题就是：在给定了收点和发点并对每条弧 (vi,vj)赋权以容量 cij
及单位费用 bij的网络中，求一个给定值 f的流量的最小费用，
这个给定值 f的流量应小于等于最大流量 F，否则无解。求最小费用流的问题的线性规划的模型只要把最小费用最大流模型中的约束条件中的发点流量 F改为 f即可。在例 6中只要把
f12+f14=F改为 f12+f14=f=6得到了最小费用流的线性规划的模型了。
管 理 运 筹 学 63
§ 5 最小费用最大流问题二、最小费用最大流的网络图解法
对网络上弧（ vi,vj）的（ cij,bij）的表示作如下改动，用 (b)来表示 (a)。
用上述方法对例 7中的图形进行改进，得图如下页：
vi vj vi vj
（ cij,bij ） （ 0,-bij ）
（ a） （ b）
（ cij,bij ）
（ cij,bij ）
vi vj
（ cji,bji ）
（ cij,bij ）
vi vj
（ cji,bji ）
（ 0,-bji)
（ 0,-bji)
（ c） （ d）
管 理 运 筹 学 64
§ 5 最小费用最大流问题
求最小费用最大流的基本算法在对弧的标号作了改进的网络图上求最小费用最大流的基本算法与求最大流的基本算法完全一样，不同的只是在步骤（ 1）中要选择一条总的单位费用最小的路，而不是包含边数最小的路。
(6,6)
(3,4) (5,7)
(2,5) (0,-4)
（ 2,3） (4,4)
(1,3)
(2,8)
（ 3,2）
v1
v2
v5
v7
v4
v3
v6
(6,3)
(0,-3)
(0,-8)(0,-3)（ 0,-2）
(0,-6)
(0,-4)
(0,-5)（ 2,4） (0,-7)(0,-4)（ 0,-3）
图 11-28
管 理 运 筹 学 65
§ 5 最小费用最大流问题用上述方法对例 7求解：
第一次迭代：找到最短路 v1 v4 v6 v7。 第一次迭代后总流量为 1，总费用 10。
v5
(6,6)
(3,4) (5,7)
(2,5) (0,-4)
（ 2,3） (3,4)
(0,3)
(2,8)
（ 3,2）
v1
v2
v7
v4
v3
v6
(5,3)
(1,-3)
(0,-8)(1,-3)（ 0,-2）
(0,-6)
(0,-4)
(0,-5)（ 2,4） (0,-7)(1,-4)（ 0,-3）
图 11-29
管 理 运 筹 学 66
§ 5 最小费用最大流问题
第二次迭代：找到最短路 v1 v4 v7。 第二次迭代后总流量为 3，总费用
32。
(6,6)
(3,4) (5,7)
(2,5) (0,-4)
（ 2,3） (3,4)
(0,3)
(0,8)
（ 3,2）
v1
v2
v5
v7
v4
v3
v6
(3,3)
(3,-3)
(2,-8)(1,-3)（ 0,-2）
(0,-6)
(0,-4)
(0,-5)（ 2,4） (0,-7)(1,-4)（ 0,-3）
图 11-30
管 理 运 筹 学 67
§ 5 最小费用最大流问题
第三次迭代：找到最短路 v1 v4 v3 v6 v7 。 第三次迭代后总流量为
5，总费用 56。
(6,6)
(3,4) (5,7)
(2,5) (0,-4)
（ 0,3） (1,4)
(0,3)
(0,8)
（ 1,2）
v1
v2
v5
v7
v4
v3
v6
(1,3)
(5,-3)
(2,-8)(1,-3)（ 2,-2）
(0,-6)
(0,-4)
(0,-5)（ 2,4） (0,-7)(3,-4)（ 2,-3）
图 11-31
管 理 运 筹 学 68
§ 5 最小费用最大流问题
第四次迭代：找到最短路 v1 v4 v3 v5 v7 。 第四次迭代后总流量为
6，总费用 72。
(6,6)
(3,4) (4,7)
(2,5) (1,-4)
（ 0,3） (1,4)
(0,3)
(0,8)
（ 0,2）
v1
v2
v5
v7
v4
v3
v6
(0,3)
(6,-3)
(2,-8)(1,-3)（ 3,-2）
(0,-6)
(0,-4)
(0,-5)（ 1,4） (1,-7)(3,-4)（ 2,-3）
图 11-32
管 理 运 筹 学 69
§ 5 最小费用最大流问题
第五次迭代：找到最短路 v1 v2 v5 v7 。 第五次迭代后总流量为 9，总费用 123。
(3,6)
(0,4) (1,7)
(2,5) (1,-4)
（ 0,3） (1,4)
(0,3)
(0,8)
（ 0,2）
v1
v2
v5
v7
v4
v3
v6
(0,3)
(6,-3)
(2,-8)(1,-3)（ 3,-2）
(3,-6)
(3,-4)
(0,-5)（ 1,4） (4,-7)(3,-4)（ 2,-3）
图 11-33
管 理 运 筹 学 70
§ 5 最小费用最大流问题
第六次迭代：找到最短路 v1 v2 v3 v5 v7 。 第六次迭代后总流量为
10，总费用 145。已经找不到从 v1到 v7的每条弧容量都大于零的路了，故已求得最小费用最大流了。
(3,6)
(0,4) (1,7)
(2,5) (1,-4)
（ 0,3） (1,4)
(0,3)
(0,8)
（ 0,2）
v1
v2
v5
v7
v4
v3
v6
(0,3)
(6,-3)
(2,-8)(1,-3)（ 3,-2）
(3,-6)
(3,-4)
(0,-5)（ 1,4） (4,-7)(3,-4)（ 2,-3）
图 11-34
管 理 运 筹 学 71
§ 5 最小费用最大流问题如果对例 7求一个最小费用流的问题：每小时运送 6万加仑石油从 v1到
v7的最小费用是多少，或者每小时运送 7万加仑呢？我们可以从第四次迭代及图 11-32即可得到运送 6万加仑最小费用 72百元，其运送方式通过比较图 11-28及图 11-32即得图 11-36所示。
至于每小时运送 7万加仑，我们可以在图 11-36的基础上，再按第五次迭代所选的最短路运送 1万加仑即得最小费用,72+1*17=89百元，其运送方式如图 11-37所示。
3 5
1
2 3
1 2
6
v1
v2
v5
v4
v3
v6
10
3
4 2 v7 10
第六次迭代后总流量图 11-35
管 理 运 筹 学 72
§ 5 最小费用最大流问题
1
2 3
1 2
6
v1
v2
v5
v4
v3
v6
6
3
1 v7
图 11-36
1 2
2 3
1 2
6
v1
v2
v5
v4
v3
v6
3
1 1 v7
图 11-37
注：,管理运筹学软件,有专门的子程序用于解决这类问题。
第十一章 图与网络模型
§ 1 图与网络的基本概念
§ 2 最短路问题
§ 3 最小生成树问题
§ 4 最大流问题
§ 5 最小费用最大流问题管 理 运 筹 学 2
§ 1 图与网络的基本概念图论中图是由点和边构成，可以反映一些对象之间的关系。
例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图 11-1就是一个表示这种关系的图。
(v1)
赵
(v2)钱
(v3)孙
(v4)
李
(v5)
周 (v6)吴
(v7)陈
e2
e1 e
3
e4
e5
图 11-1
管 理 运 筹 学 3
§ 1 图与网络的基本概念当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以用图 11-2来表示，
可见图论中的图与几何图、工程图是不一样的。
(v1)
赵 (v
2)钱 孙 (v3) 李 (v4) 周 (v5) 吴 (v6) 陈 (v7)
e2
e1 e3 e4 e5
图 11-2
管 理 运 筹 学 4
§ 1 图与网络的基本概念
a1
a2
a3
a4
a14
a7
a8
a9
a6a5
a10
a12
a11
a13
a15(v1)赵
(v2)钱
(v3)孙
(v4)
李
(v5)
周
(v6)吴
(v7)陈图 11-3
如果我们把上面例子中的“相互认识”关系改为“认识”
的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图 11-3就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。
管 理 运 筹 学 5
§ 1 图与网络的基本概念
无向图：
由点和边构成的图，记作 G=（ V,E）。
有向图：
由点和弧构成的图，记作 D=（ V,A）。
连通图,
对无向图 G，若任何两个不同的点之间，至少存在一条链，则 G为连通图。
回路：
若路的第一个点和最后一个点相同，则该路为回路。
赋权图：
对一个无向图 G的每一条边 (vi,vj)，相应地有一个数 wij，则称图 G
为赋权图,wij称为边 (vi,vj)上的权。
网络：
在赋权的有向图 D中指定一点，称为发点，指定另一点称为收点，
其它点称为中间点，并把 D中的每一条弧的赋权数称为弧的容量,D就称为网络。
管 理 运 筹 学 6
§ 2 最短路问题最短路问题在实际中具有广泛的应用,如管道铺设,线路选择等问题,还有些如设备更新,投资等问题也可以归结为求最短路问题求最短路有两种算法：
一是求从某一点至其它各点之间最短离的 狄克斯屈拉
(Dijkstra)算法另一种是求网络图上任意两点之间最短路的 Floyd(弗洛伊德 )
矩阵算法 。
最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路
6.2.1最短路问题的网络模型管 理 运 筹 学 7
§ 2 最短路问题
最短路问题：对一个赋权的有向图 D中的指定的两个点 Vs和 Vt找到一条从 Vs 到 Vt 的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从 Vs到 Vt的最短路。这条路上所有弧的权数的总和被称为从 Vs到 Vt
的距离。
一、求解最短路的 Dijkstra算法 (双标号法）
步骤：
1.给出点 V1以标号 (0,s)
2.找出已标号的点的集合 I，没标号的点的集合 J以及弧的集合
3,如果上述弧的集合是空集，则计算结束。如果 vt已标号（ lt,kt），则 vs
到 vt的距离为 lt，而从 vs到 vt的最短路径，则可以从 kt 反向追踪到起点
vs 而得到。如果 vt 未标号，则可以断言不存在从 vs到 vt的有向路。如果上述的弧的集合不是空集，则转下一步。
4,对上述弧的集合中的每一条弧，计算 sij=li+cij 。在所有的 sij中，找到其值为最小的弧。不妨设此弧为（ Vc,Vd），则给此弧的终点以双标号
（ scd,c）,返回步骤 2。
{ (,) |,}i j i jv v v I v J
管 理 运 筹 学 8
§ 2 最短路问题例 1 求下图中 v1到 v6的最短路解：采用 Dijkstra算法，可解得最短路径为 v1 v3 v4 v6
各点的标号图如下：
v2
3
5 2
7
5
3 1
5
12
v1
v6
v5v
3
v4
(3,1)v
2
3
5 2
7
5
3 1
5
12
V1
（ 0,s)
v5
(8,4)v
6
(2,1)v
3
(3,3)v
4
管 理 运 筹 学 9
§ 2 最短路问题
②
③
④
⑤
⑥
⑦
6
10
12
3 2
14
67
5
8
11
16
5
图 6－ 6
9
0,0
6
10
12
9
20
9,2
18
6,1
①
16
12,1 17 16,3
24
32
18,3
29
29,5
【 例 】 用 Dijkstra算法求图 6－ 6 所示 v1到 v7的最短路及最短路长
v1 到 v7的最短路为,p17=｛ v1,v2,v3,v5,v7｝，最短路长为 L17=29
14
管 理 运 筹 学 10
【 例 】 求图 6-10所示 v1到各点的最短路及最短距离
①
②
③
④
⑤
⑥
⑦
⑧
4
5
2
6
1
7
8
3
9
3
2
6
12
16
18
0,0
4
5
2
2,1
3
10
3,4
9 6
12
6
4,1 11 6,3
6,3
18
8
12
24
8,5 24 18,5
所有点都已标号，点上的标号就是 v1到该点的最短距离，最短路线就是红色的链。
图 6-10
§ 2 最短路问题管 理 运 筹 学 11
§ 2 最短路问题例 2 电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。
解：这是一个求无向图的最短路的问题。可以把无向图的每一边
（ vi,vj）都用方向相反的两条弧（ vi,vj）和（ vj,vi）代替，就化为有向图，即可用 Dijkstra算法来求解。也可直接在无向图中用 Dijkstra算法来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。
V1
（甲地）
15
17
6
24
4
3
10
6
5v2
V7 （乙地）
v3
v4
v5
v6
管 理 运 筹 学 12
§ 2 最短路问题例 2最终解得：
最短路径 v1 v3 v5 v6 v7，每点的标号见下图
（ 0,s）
V1
（甲地）
15
17
6
24
4
3
10
6
5
(13,3)v
2
(22,6)
V7 （乙地）
V5(14,3)
V6(16,5)
V3(10,1)
V4(18,5)
管 理 运 筹 学 13
§ 2 最短路问题例 3 设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。
已知：设备每年年初的价格表设备维修费如下表年份 1 2 3 4 5
年初价格 11 11 12 12 13
使用年数 0-1 1-2 2-3 3-4 4-5
每年维修费用
5 6 8 11 18
管 理 运 筹 学 14
§ 2 最短路问题例 3的解：
将问题转化为最短路问题，如下图：
用 vi表示“第 i年年初购进一台新设备”,弧（ vi,vj）表示第 i年年初购进的设备一直使用到第 j年年初。
把所有弧的权数计算如下表：
v1 v2 v3 v4 v5 v6
1 2 3 4 5 6
1 16 22 30 41 59
2 16 22 30 41
3 17 23 31
4 17 23
5 18
6
管 理 运 筹 学 15
§ 2 最短路问题
(继上页 ) 把权数赋到图中，再用 Dijkstra算法求最短路。
最终得到下图，可知,v1到 v6的距离是 53，最短路径有两条：
v1 v3 v6和 v1 v4 v6
v1 v2 v3 v4 v5 v616
22 30
41
59
16
22
30
41
3123
17 1817
23
V1
（ 0,s） v3 v4 (41,1)
v5
v6
22 30
41
59
16
(22,1)
30
41
3123
17 1817
23
V2
（ 16,1）
16
(30,1)
(53,3)
(53,4)
管 理 运 筹 学 16
§ 2 最短路问题
6.2.4 最短路应用举例
【 例 】 设备更新问题。企业在使用某设备时，每年年初可购置新设备，也可以使用一年或几年后卖掉重新购置新设备。已知 4
年年初购置新设备的价格分别为 2.5,2.6,2.8和 3.1万元。设备使用了 1～ 4年后设备的残值分别为 2,1.6,1.3和 1.1万元，使用时间在 1～ 4年内的维修保养费用分别为 0.3,0.8,1.5和 2.0万元。
试确定一个设备更新策略，在下例两种情形下使 4年的设备购置和维护总费用最小。
（ 1）第 4年年末设备一定处理掉；
（ 2）第 4年年末设备不处理。
【 解 】 画网络图。用点 (1,i,…,j)表示第 1年年初购置设备使用到第
i年年初更新，经过若干次更新使用到第 j年年初，第 1年年初和第 5年年初分别用①及⑤表示。使用过程用弧连接起来，弧上的权表示总费用 (购置费＋维护费－残值 )，如图 6－ 16所示管 理 运 筹 学 17
§ 2 最短路问题
① ⑤6
图 6－ 16
(1,2,3)
(1,4)
(1,3,4)
(1,2,4)
(1,2,3,4)
(1,2)
(1,3)
第一年 第二年 第三年 第四年
5.1
0.9
1.5
0.7
3.6
2.8
1.7 -0.2
1.9
1.1
2.1
0.3
-0.6
-0.6
网络图 6－ 16说明：如图中点 (1,3)表示第 1年购置设备使用两年到第 3年年初更新购置新设备，这时有 2种更新方案，使用 1年到第 4年年初、使用 2年到第 5年年初,更新方案用弧表示，点（ 1,2,3）表示第 1年购置设备使用一年到第二年年初又更新，使用一年到第三年初再更新，这时仍然有 2种更新方案，使用 1年到第
4年年初和使用 2年到第 5年年初。
管 理 运 筹 学 18
§ 2 最短路问题点（ 1,3）和点（ 1,2,3）不能合并成一个点，虽然都是第三年年初购置新设备，购置费用相同，但残值不同。点 (1,3)的残值等于 1.6(使用了两年 )，点 (1,2,3)的残值等于 2(使用了一年 )。点
（ 1,3）到点（ 1,3,4）的总费用为第三年的购置费＋第一年的维护费－设备使用两年后的残值
＝ 2.8+0.3－ 1.6=1.5
点（ 1,3）到点⑤的总费用为第三年的购置费＋第一年的维护费＋第二年的维护费－设备使用两年后的残值－第四年末的残值
＝ 2.8+0.3+0.8－ 1.6－ 1.6=0.7。
管 理 运 筹 学 19
§ 2 最短路问题
① ⑤6
图 6－ 16
(1,2,3)
(1,4)
(1,3,4)
(1,2,4)
(1,2,3,4)
(1,2)
(1,3)
第一年 第二年 第三年 第四年
5.1
0.9
1.5
0.7
3.6
2.8
1.7 -0.2
1.9
1.1
2.1
0.3
-0.6
-0.6
（ 1）第四年末处理设备,求点①到点⑤的最短路。用 Dijkstra
算法得到最短路线为：
① → (1,2)→(1,2,3)→ ⑤,最短路长为 4。
4年总费用最小的设备更新方案是：第 1年购置设备使用 1年，
第 2年更新设备使用 1年后卖掉，第 3年购置设备使用 2年到第 4年年末,4年的总费用为 4万元。
管 理 运 筹 学 20
§ 3 最小生成树问题
树是图论中的重要概念，所谓树就是一个无圈的连通图。
图 11-11中,(a)就是一个树，而 (b)因为图中有圈所以就不是树,(c)因为不连通所以也不是树。
图 11-11
v1
v2 v
3
v4v5v
6
v7
v8 v9
v1
v2 v3
v5
v8
v7
v6
v4
v1
v2
v3
v4
v5
v7 v6
v8
v9
(a) (b) (c)
管 理 运 筹 学 21
可以证明：
（ 1）一棵树的边数等于点数减 1；
（ 2）在树中任意两个点之间添加一条边就形成圈；
（ 3）在树中去掉任意一条边图就变为不连通。
§ 3 最小生成树问题管 理 运 筹 学 22
§ 3 最小生成树问题给了一个无向图 G=(V,E)，我们保留 G的所有点，而删掉部分 G的边或者说保留一部分 G的边，所获得的图 G，称之为 G的生成子图。在图 11-12中，
(b)和 (c)都是 (a)的生成子图。
如果图 G的一个生成子图还是一个树，则称这个生成子图为生成树，
在图 11-12中,(c)就是 (a)的生成树。
最小生成树问题就是指在一个赋权的连通的无向图 G中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。
图 11-12
(a) (b) (c)
管 理 运 筹 学 23
§ 3 最小生成树问题一、求解最小生成树的破圈算法算法的步骤：
1、在给定的赋权的连通图上任找一个圈。
2、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。
3、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第 1步。
管 理 运 筹 学 24
5
v1
v2
v3
v4
v5
v6
8
4
3
7
5
2
6
18
图 6－ 1
【 例 】 用破圈法求图 6－ 1的最小树。
图 6－ 4
图 6－ 4就是图 6－ 1的最小部分树，最小树长为
C(T)=4+3+5+2+1=15。
当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同
§ 3 最小生成树问题管 理 运 筹 学 25
§ 3 最小生成树问题例 4 用破圈算法求图（ a）中的一个最小生成树
v1 3
3
1
7
2
85410 3
4
v7
v6 v5
v4
v2
v1 3
3
1
7
2
8543
4
v7
v6 v5
v4
v2
v1 3
3 7
2
543
4
v7
v6 v5
v4
v2
v3 v3
v31
v1 3
3 7
2
4
3
4
v7
v6 v5
v4
v2 v31
v1 3
3 7
2
3
4
v7
v6 v5
v4
v2 v31
v1 3
3 7
2
3
v7
v6 v5
v4
v2 v31
(a) (b)
(c) (d)
(e) (f)图 11-13
管 理 运 筹 学 26
加边法,取图 G的 n个孤立点 ｛ v1,v2,…,vn}作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有
n－ 1条边）
v1
v2
v3
v4
v5
v6
4
3
5
2 1
图 6－ 5
在图 6－ 5中，如果添加边 [v1,v2]就形成圈｛ v1,v2,v4｝，这时就应避开添加边 [v1,v2]，添加下一条最短边 [v3,v6]。破圈法和加边法得到树的形状可能不一样，但最小树的长度相等
5
v1 v3 v5
15
v2 v4 v6
8
4
3
7
5
2
6
8×
Min C(T)=15
§ 3 最小生成树问题管 理 运 筹 学 27
§ 3 最小生成树问题例 5、某大学准备对其所属的 7个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中 v1,…,v 7 表示 7个学院办公室，请设计一个网络能联通 7个学院办公室，并使总的线路长度为最短。
解：此问题实际上是求图 11-14的最小生成树，这在例 4中已经求得，
也即按照图 11-13的 (f)设计，可使此网络的总的线路长度为最短，为 19
百米。
“管理运筹学软件”有专门的子程序可以解决最小生成树问题。
v1 3
3
1
7
2
85
4
10 3
4
v7
v6 v5
v4
v2 v3
图 11-14
管 理 运 筹 学 28
§ 4 最大流问题
6.3.1 基本概念
①
②
③
④
⑤
⑥
8
14
5
6
3
3
8
10
7
6
⑦
3
图 6－ 18
4
图 6－ 18所示的网络图中定义了一个 发点 v1，称为源 (source,supply
node），定义了一个 收点 v7，称为汇（ sink,demand node），其余点 v2,v3,…,v6为 中间点,称为 转运点 (transshipment nodes)。如果有多个发点和收点，则虚设发点和收点转化成一个发点和收点。图中的权是该弧在单位时间内的最大通过能力，称为弧的 容量 (capacity)。
最大流问题是在单位时间内安排一个运送方案，将发点的物质沿着弧的方向运送到收点，使总运输量最大。
管 理 运 筹 学 29
§ 4 最大流问题设 cij为弧（ i,j）的容量,fij为弧（ i,j）的流量。
容量是弧（ i,j）单位时间内的 最大通过能力,流量是弧（ i,j）
单位时间内的 实际通过量,流量的集合 f={fij}称为网络的流。发点到收点的总流量记为 v=val(f),v也是网络的 流量 。
图 6－ 18最大流问题的线性规划数学模型为
),(0
0
0
m a x
6747571312
1312
jicf
vff
fffff
ffv
ijij
m
v
mj
v
im
mm
所有弧所有中间点管 理 运 筹 学 30
§ 4 最大流问题满足下例 3个条件的流 fij 的集合 f ={ fij }称为可行流
1 ) 0 (,)i j i jf c i j（ 所 有 弧
( 3 )
st
s j it
vv
v f f
发点 vs流出的总流量等于流入收点 vt的总流量
(2 )
mm
i m m j m
vv
f f v 所 有 中 间 点管 理 运 筹 学 31
§ 4 最大流问题链,从发点到收点的一条路线（弧的方向不一定都同向）称为链。
从发点到收点的方向规定为链的方向。
前向弧,与链的方向相同的弧称为前向弧。
后向弧,与链的方向相反的弧称为后向弧。
增广链,设 f 是一个可行流，如果存在一条从 vs到 vt的链，满足：
1.所有前向弧上 fij<Cij
2.所有后向弧上 fij>0
则该链称为增广链
①
②
③
④
⑤
⑥前向弧后向弧容量流量这是一条增广链
8
4
4
6
9（ 5）
(2)
(3)
(4)
(6)
管 理 运 筹 学 32
§ 4 最大流问题步骤如下：
第二步：对点进行标号找一条增广链。
（ 1）发点标号 （ ∞）
（ 2）选一个点 vi 已标号并且另一端未标号的弧沿着某条链向收点检查：
A．如果弧的方向向前（前向弧）并且有 fij<cij，则 vj标号,
θj＝ cij－ fij
B,如果弧的方向指向 vi（后向弧）并且有 fji>0，则 vj标号,
θj＝ fji
当收点已得到标号时，说明已找到增广链，依据 vi 的标号反向跟踪得到一条增广链。当收点不能得到标号时，说明不存在增广链，计算结束。
第一步,找出第一个可行流，例如所有弧的流量 fij =0
6.3.2 Ford-Fulkerson标号算法管 理 运 筹 学 33
§ 4 最大流问题第三步：调整流量
（ 1）求增广链上点 vi 的标号的最小值，得到调整量
m in jj
（ 2）调整流量
),(
),(
),(
1
jif
jif
jif
f
ij
ij
ij
得到新的可行流 f1，去掉所有标号，返回到第二步从发点重新标号寻找增广链，直到收点不能标号为止
【 定理 6.1】 可行流 f是最大流的充分必要条件是不存在发点到收点的增广链管 理 运 筹 学 34
§ 4 最大流问题
①
②
③
④
⑤
⑥
8
14
5
6
3
3
8
10
7
6
⑦
3
图 6－ 19
(10)
(6)
(3)
(6)
(3)
(7)
(0) (6)(1)
4
(3)(1)
(7)
【 例 】 求图 6－ 18发点 v1到收点 v7的最大流及最大流量
【 解 】 给定初始可行流，见图 6-19
管 理 运 筹 学 35
§ 4 最大流问题
①
②
③
④
⑤
⑥
8
14
5
6
3
3
8
10
7
6
⑦
3
图 6－ 20(b)
(10)
(6)
(3)
(6)
(3)
(7)
(0) (6)(1)
4
(3)(1)
(7)
∞
2
3
3
7
第一轮标号：
c12>f12,v2标号 2
cij=fij,v4,v5不能标号后向弧 f32>0,
v3标号 θ3=f32
增广链 μ＝ {(1,2),(3,2),(3,4),(4,7) },μ+={(1,2),(3,4)，
(4,7)},μ－ ={(3,2)}，调整量为增广链上点标号的最小值
θ＝ min{∞,2,3,3,7}＝ 2
管 理 运 筹 学 36
§ 4 最大流问题
①
②
③
④
⑤
⑥
8
14
5
6
3
3
8
10
7
6
⑦
3
图 6－ 21
(10)
(8)
(1)
(6)
(3)
(7)
(2) (6)(1)
4
(5)(1)
(7)
调整后的可行流：
管 理 运 筹 学 37
§ 4 最大流问题
①
②
③
④
⑤
⑥
8
14
5
6
3
3
8
10
7
6
⑦
3
图 6－ 22
(10)
(8)
(1)
(6)
(3)
(7)
(2) (6)(1)
4
(5)(1)
(7)
∞
4
4
1
5
第二轮标号,Cij=fij,v4,v5不能标号，返回到 v3
增广链 μ＝ μ＋ ＝ {(1,3),(3,4),(4,7) }，调整量为
θ＝ min{∞,4,1,5}＝ 1
管 理 运 筹 学 38
§ 4 最大流问题
①
②
③
④
⑤
⑥
8
14
5
6
3
3
8
10
7
6
⑦
3
图 6－ 23
(11)
(8)
(1)
(6)
(3)
(7)
(3) (6)(1)
4
(6)(1)
(7)
调整后得到可行流：
管 理 运 筹 学 39
§ 4 最大流问题
①
②
③
④
⑤
⑥
8
14
5
6
3
3
8
10
7
6
⑦
3
图 6－ 22
(11)
(8)
(1)
(6)
(3)
(7)
(3) (6)(1)
4
(6)(1)
(7)
∞
3 1
4
第三轮标号：
增广链 μ＝ μ＋ ＝ {(1,3),(3,6),(6,4),(4,7) }，调整量为
θ＝ min{∞,3,1,2,4}＝ 1
2
管 理 运 筹 学 40
§ 4 最大流问题
①
②
③
④
⑤
⑥
8
14
5
6
3
3
8
10
7
6
⑦
3
图 6－ 25
(12)
(8)
(1)
(6)
(3)
(8)
(3) (6)(2)
4
(7)(1)
(7)
调整后得到可行流：
管 理 运 筹 学 41
§ 4 最大流问题
①
②
③
④
⑤
⑥
8
14
5
6
3
3
8
10
7
6
⑦
3
图 6－ 22
(12)
(8)
(1)
(6)
(3)
(8)
(3) (6)(2)
4
(7)(1)
(7)
∞
2
第四轮标号：
v7得不到标号，不存在 v1到 v7的增广链，图 6-22所示的可行流是最大流，最大流量为
v＝ f12+f13＝ 8+12=20
Cij=fij,v4,v5不能标号
Cij=fij,v4,v6不能标号
4
管 理 运 筹 学 42
§ 4 最大流问题无向图最大流标号算法无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端 vi
已标号另一端 vj未标号的边只要满足 Cij－ fij>0 则 vj就可标号
（ Cij－ fij）
【 例 】 求下图 v1到则 v7标的最大流
7
①
②
③
④
⑤
⑥
⑦
12
9
20
8
5
14
8 6
9
13
16
(10)
(6)
(10)
(8)
(2)
(3)
(7)
(6)
(5)
(13)
(0)
(13)
∞
2
3
9
9
3
2
管 理 运 筹 学 43
§ 4 最大流问题
7
①
②
③
④
⑤
⑥
⑦
12
9
20
8
5
14
8 6
9
13
16
(12)
(6)
(10)
(8)
(4)
(3)
(7)
(6)
(7)
(13)
(2)
(15)
∞
3
7
7
1
1
7
①
②
③
④
⑤
⑥
⑦
12
9
20
8
5
14
8 6
9
13
16
(12)
(7)
(10)
(8)
(4)
(3)
(7)
(6)
(8)
(13)
(3)
(16)
V=29
∞
10
5
6
6
1
管 理 运 筹 学 44
§ 4 最大流问题截集 将图 G＝（ V,E）的点集分割成两部分
〕，的弧集合（箭头在，则箭尾在及 1__11__11__1 VVVVVvVv ts
并且,1__1 VV
称为一个截集，截集中所有弧的容量之和称为截集的截量。
①
②
③
④
⑤
⑥
6
8
4
4
1
2
2
6
7
9
6
4
1
1
3 2
2
3
0
6
下图所示的截集为)5,3(),4,3(),2,1(),( 11?VV
10226),( 11VVC截量管 理 运 筹 学 45
§ 4 最大流问题
①
②
③
④
⑤
⑥
6
8
4
4
1
2
2
6
7
9
6
4
0
1
3 2
2
1
0
6
又如下图所示的截集为)6,5()4,5(),4,3(),4,2(),( 11,?VV
219624),( 11VVC截量上图所示的截集为
)5,3(),4,3(),5,2(),4,2(),( 11?VV 92214),( 11VVC截量所有截量中此截量最小且等于最大流量，此截集称为最小截集。
【 定理 】 最大流量等于最小截集的截量。
管 理 运 筹 学 46
§ 4 最大流问题
最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，
在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。
一、最大流的数学模型例 6 某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（ vi,vj）的流量 cij（容量）也是不一样的。 cij的单位为万加仑 /小时。如果使用这个网络系统从采地 v1向销地 v7运送石油，问每小时能运送多少加仑石油？
v5
6
3 5
2 2
2 4
1
2
6 3
v1
v2
v7
v4
v3
v6
图 11-26
管 理 运 筹 学 47
§ 4 最大流问题我们可以为此例题建立线性规划数学模型：
设弧 (vi,vj)上流量为 fij，网络上的总的流量为 F，则有：
14
1 2 2 3 2 5
1 4 4 3 4 6 4 7
2 3 4 3 3 5 3 6
2 5 3 5 5 7
3 6 4 6 6 7
5 7 6 7 4 7 1 2 1 4
,1,2,,6 ; 1,2,7
0,1,2,,6 ; 1,2,7
12
ij ij
ij
m a x F = f f
f f f
f f f f
f f f f
f f f
f f f
f f f f f
f c i j
f i j
目 标 函 数,
约 束 条 件,
管 理 运 筹 学 48
§ 4 最大流问题在这个线性规划模型中，其约束条件中的前 6个方程表示了网络中的流量必须满足守恒条件，发点的流出量必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必须等于总流出量。其后面几个约束条件表示对每一条弧
(vi,vj)的流量 fij要满足流量的可行条件，应小于等于弧 (vi,vj)
的容量 cij，并大于等于零，即 0≤ fij≤ cij。我们把满足守恒条件及流量可行条件的一组网络流 {fij}称之为可行流，
（即线性规划的可行解），可行流中一组流量最大（也即发出点总流出量最大）的称之为最大流（即线性规划的最优解）。
我们把例 6的数据代入以上线性规划模型，用“管理运筹学软件”，马上得到以下的结果,f12=5,f14=5,f23=2，
f25=3,f43=2,f46=1,f47=2,f35=2,f36=2,f57=5,f67=3。最优值（最大流量） =10。
管 理 运 筹 学 49
§ 4 最大流问题二、最大流问题网络图论的解法对网络上弧的容量的表示作改进。为省去弧的方向，如下图,(a)和
(b),(c)和 (d)的意义相同。
用以上方法对例 6的图的容量标号作改进，得下图
vi vj vi vj
cij 0
（ a） （ b）
cij
cij
vi vj（ c
ji） （ c） vi vj
cij cji
（ d）
6
3 52
2 2 4
1 2
6
3
v1
v2
v5
v7
v4
v3
v6
0
0
0 00 0
0
0
0
0
0
管 理 运 筹 学 50
§ 4 最大流问题求最大流的基本算法
（ 1）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。
（ 2）找出这条路上各条弧的最小的顺流的容量 pf，通过这条路增加网络的流量 pf。
（ 3）在这条路上，减少每一条弧的顺流容量 pf,同时增加这些弧的逆流容量 pf，返回步骤（ 1）。
用此方法对例 6求解：
第一次迭代：选择路为 v1 v4 v7 。弧（ v4,v7 ）的顺流容量为 2，
决定了 pf=2，改进的网络流量图如下图：
6
3 52
2 2 4
1 2
6
3
v1
v2
v5
v7
v4
v3
v6
0
0
0 00
0
0
0
0
0
04
2
02
管 理 运 筹 学 51
§ 4 最大流问题第二次迭代：选择路为 v1 v2 v5 v7 。弧（ v2,v5 ）的顺流容量为
3，决定了 pf=3，改进的网络流量图如下图：
第三次迭代：选择路为 v1 v4 v6 v7 。弧（ v4,v6 ）的顺流容量为
1，决定了 pf=1，改进的网络流量图如下图：
6
3 52
2 2 4
13
v1
v2
v5
v7
v4
v3
v6
0
0 0
0
0
0
0
04
2
02
20 3
3
3
0
3
2
2 2 4
13
v1
v2
v5
v7
v4
v3
v6
0
0 0
0
0
04
2
02
20 3
3
3
3
3
0
1
3
管 理 运 筹 学 52
第四次迭代：选择路为 v1 v4 v3 v6 v7 。弧（ v3,v6 ）的顺流容量为 2，决定了 pf=2，改进的网络流量图如下图：
第五次迭代：选择路为 v1 v2 v3 v5 v7 。弧（ v2,v3 ）的顺流容量为 2，决定了 pf=2，改进的网络流量图如下图：
2
2 2 4
3
v1
v2
v5
v7
v4
v3
v6
1
0
0
0
01 2
03
20 3
3
3
5
0
3
1
2
0
02 3 13
2
2
v1
v2
v5
v7
v4
v3
v6
1
0
1 2
0
20 3
3
3
5 01
2
0 2 3 1
31 5
0 0
2
0
2 0 5
§ 4 最大流问题管 理 运 筹 学 53
经过第五次迭代后在图中已经找不到从发点到收点的一条路，路上的每一条弧顺流容量都大于零，运算停止。得到最大流量为 10。
最大流量图如下图：
2
2
v1
v2 v5
v7
v4
v3
v6
1
2
3
5
2
2 35
5
§ 4 最大流问题
“管理运筹学软件”中还有专门的子程序用于解决最大流问题。
管 理 运 筹 学 54
§ 4 最大流问题最大流应用举例
【 例 6.12】 某公司需要招聘 5个专业的毕业生各一个，通过本人报名和筛选，公司最后认为有 6人都达到录取条件。这 6人所学专业见表 6-10,表中打,√”表示该生所学专业。公司应招聘哪几位毕业生，如何分配他们的工作毕业生 A.市场 营销 B.工程管理 C.管理信息 D.计算机 E.企业管理
1 √ √
2 √ √
3 √ √
4 √ √
5 √ √
6 √ √
表 6-10
管 理 运 筹 学 55
§ 4 最大流问题
①
②
③
④
⑤
⑥
A
B
C
D
E
s t
(1)
(1)
(1)
(1)
(1)
(1)
(1)
(1)
(1)
(1)
(1)
(1)
(1)
(1)
(1)
图 6－ 32
【 解 】 画出一个图，虚设一个发点和一收点，每条弧上的容量等于 1，问题为求发点到收点的最大流，求解结果之一见图 6－
32。公司录取第 2～ 6号毕业生，安排的工作依次为管理信息、
企业管理、市场营销、工程管理和计算机。
管 理 运 筹 学 56
§ 4 最大流问题
【 例 】 某市政工程公司在未来 5～ 8月份内需完成 4项工程,A.修建一条地下通道,B.修建一座人行天桥,C.新建一条道路及 D.
道路维修。工期和所需劳动力见表 6-11。该公司共有劳动力 120
人，任一项工程在一个月内的劳动力投入不能超过 80人，问公司如何分配劳动力完成所有工程，是否能按期完成工期 需要劳动力（人月）
A,地下通道 5～ 7月 100
B,人行天桥 6～ 7月 80
C,新建道路 5～ 8月 200
D,道路维修 8月 80
表 6-12
【 解 】 将工程计划用网络图 6－ 33表示。设点 v5,v6,v7,v8分别表示 5～ 8月份,Ai,Bi,Ci,Di表示工程在第 i个月内完成的部分，用弧表示某月完成某项工程的状态，弧的容量为劳动力限制。就是求图 6－ 33从发点到收点的最大流问题。
管 理 运 筹 学 57
§ 4 最大流问题
⑤
⑥
⑦
⑧
A5
B6
C7
D8
s t
图 6－ 33
A6
C5
A7
C6
B7
C8
A
B
C
D
120
120
120
120
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
100
80
200
80
(100)
(120)
(120)
(120)
(20)
(80)
(40)
(80)
(0)
(40)
(80)
(0)
(40)
(80)
(20)
(80) (80)
(40)
(80)
(80)
(40)
(0)
(40)
(80)
(100)
(80)
(200)
(80)
管 理 运 筹 学 58
§ 4 最大流问题标号算法求解得到图 6－ 33，括号内的数字为弧的流量。每个月的劳动力分配见表 6-13。 5月份有剩余劳动力 20人,4项工程恰好按期完成表 6-13
月份 投入劳动力 项目 A(人 ) 项目 B(人 ) 项目 C(人 ) 项目 D(人 )
5 100 20 80
6 120 40 80
7 120 80 40
8 120 40 80
合计 (人 ) 460 100 80 200 80
管 理 运 筹 学 59
§ 5 最小费用最大流问题
最小费用最大流问题：给了一个带收发点的网络，对每一条弧
（ vi,vj），除了给出容量 cij外，还给出了这条弧的单位流量的费用 bij，要求一个最大流 F，并使得总运送费用最小。
一、最小费用最大流的数学模型例 7 由于输油管道的长短不一，所以在例 6中每段管道（ vi,vj ）除了有不同的流量限制 cij外，还有不同的单位流量的费用 bij,cij的单位为万加仑 /小时,bij的单位为百元 /万加仑。如图。从采地 v1向销地 v7运送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流量和最小费用。
(6,6)
(3,4) (5,7)
(2,5)
(2,4)
（ 2,3） (4,4)
(1,3)
(2,8)（ 3,2）
v1
v2
v5
v7
v4
v3
v6
(6,3)
管 理 运 筹 学 60
§ 5 最小费用最大流问题这个最小费用最大流问题也是一个线性规划的问题。
解：我们用线性规划来求解此题，可以分两步走。
第一步，先求出此网络图中的最大流量 F，这已在例 6中建立了线性规划的模型，通过管理运筹学软件已经获得结果。
第二步，在最大流量 F的所有解中，找出一个最小费用的解，我们来建立第二步中的线性规划模型如下：
仍然设弧（ vi,vj）上的流量为 fij，这时已知网络中最大流量为 F，只要在例 6的约束条件上，再加上总流量必须等于 F的约束条件,f12=f14=F,即得此线性规划的约束条件，此线性规划的目标函数显然是求其流量的最小费用 。
由此得到线性规划模型如下,(,)ij
ij ij
v v A
fb
管 理 运 筹 学 61
§ 5 最小费用最大流问题
12 14 25 23 43
(,)
35 57 36 46 47 67
12 14
12 23 25
14 43 46 47
23 43 35 36
25 35 57
36 46 67
57 67 47 12 14
m i n 6 3 4 5 2
4 7 3 3 8 4
..
10,
,
,
,
,
,
,
,( 1,2,,6 ;
ij
ij ij
v v A
ij ij
f b f f f f f
f f f f f f
st
f f F
f f f
f f f f
f f f f
f f f
f f f
f f f f f
f c i j
2,3,7 ),
0,( 1,2,,6 ; 2,3,7 ),
ij
f i j
管 理 运 筹 学 62
§ 5 最小费用最大流问题用管理运筹学软件，可求得如下结果,f12=4,f14=6,
f25=3,f23=1,f43=3,F57=5,f36=2,f46=1,f47=2,f67=3,f35=2。其最优值 (最小费用 )=145。对照前面例 6的结果，可对最小费用最大流的概念有一个深刻的理解。
如果我们把例 7的问题改为：每小时运送 6万加仑的石油从采地 v1到销地 v7最小费用是多少？应怎样运送？这就变成了一个最小费用流的问题。一般来说，所谓最小费用流的问题就是：在给定了收点和发点并对每条弧 (vi,vj)赋权以容量 cij
及单位费用 bij的网络中，求一个给定值 f的流量的最小费用，
这个给定值 f的流量应小于等于最大流量 F，否则无解。求最小费用流的问题的线性规划的模型只要把最小费用最大流模型中的约束条件中的发点流量 F改为 f即可。在例 6中只要把
f12+f14=F改为 f12+f14=f=6得到了最小费用流的线性规划的模型了。
管 理 运 筹 学 63
§ 5 最小费用最大流问题二、最小费用最大流的网络图解法
对网络上弧（ vi,vj）的（ cij,bij）的表示作如下改动，用 (b)来表示 (a)。
用上述方法对例 7中的图形进行改进，得图如下页：
vi vj vi vj
（ cij,bij ） （ 0,-bij ）
（ a） （ b）
（ cij,bij ）
（ cij,bij ）
vi vj
（ cji,bji ）
（ cij,bij ）
vi vj
（ cji,bji ）
（ 0,-bji)
（ 0,-bji)
（ c） （ d）
管 理 运 筹 学 64
§ 5 最小费用最大流问题
求最小费用最大流的基本算法在对弧的标号作了改进的网络图上求最小费用最大流的基本算法与求最大流的基本算法完全一样，不同的只是在步骤（ 1）中要选择一条总的单位费用最小的路，而不是包含边数最小的路。
(6,6)
(3,4) (5,7)
(2,5) (0,-4)
（ 2,3） (4,4)
(1,3)
(2,8)
（ 3,2）
v1
v2
v5
v7
v4
v3
v6
(6,3)
(0,-3)
(0,-8)(0,-3)（ 0,-2）
(0,-6)
(0,-4)
(0,-5)（ 2,4） (0,-7)(0,-4)（ 0,-3）
图 11-28
管 理 运 筹 学 65
§ 5 最小费用最大流问题用上述方法对例 7求解：
第一次迭代：找到最短路 v1 v4 v6 v7。 第一次迭代后总流量为 1，总费用 10。
v5
(6,6)
(3,4) (5,7)
(2,5) (0,-4)
（ 2,3） (3,4)
(0,3)
(2,8)
（ 3,2）
v1
v2
v7
v4
v3
v6
(5,3)
(1,-3)
(0,-8)(1,-3)（ 0,-2）
(0,-6)
(0,-4)
(0,-5)（ 2,4） (0,-7)(1,-4)（ 0,-3）
图 11-29
管 理 运 筹 学 66
§ 5 最小费用最大流问题
第二次迭代：找到最短路 v1 v4 v7。 第二次迭代后总流量为 3，总费用
32。
(6,6)
(3,4) (5,7)
(2,5) (0,-4)
（ 2,3） (3,4)
(0,3)
(0,8)
（ 3,2）
v1
v2
v5
v7
v4
v3
v6
(3,3)
(3,-3)
(2,-8)(1,-3)（ 0,-2）
(0,-6)
(0,-4)
(0,-5)（ 2,4） (0,-7)(1,-4)（ 0,-3）
图 11-30
管 理 运 筹 学 67
§ 5 最小费用最大流问题
第三次迭代：找到最短路 v1 v4 v3 v6 v7 。 第三次迭代后总流量为
5，总费用 56。
(6,6)
(3,4) (5,7)
(2,5) (0,-4)
（ 0,3） (1,4)
(0,3)
(0,8)
（ 1,2）
v1
v2
v5
v7
v4
v3
v6
(1,3)
(5,-3)
(2,-8)(1,-3)（ 2,-2）
(0,-6)
(0,-4)
(0,-5)（ 2,4） (0,-7)(3,-4)（ 2,-3）
图 11-31
管 理 运 筹 学 68
§ 5 最小费用最大流问题
第四次迭代：找到最短路 v1 v4 v3 v5 v7 。 第四次迭代后总流量为
6，总费用 72。
(6,6)
(3,4) (4,7)
(2,5) (1,-4)
（ 0,3） (1,4)
(0,3)
(0,8)
（ 0,2）
v1
v2
v5
v7
v4
v3
v6
(0,3)
(6,-3)
(2,-8)(1,-3)（ 3,-2）
(0,-6)
(0,-4)
(0,-5)（ 1,4） (1,-7)(3,-4)（ 2,-3）
图 11-32
管 理 运 筹 学 69
§ 5 最小费用最大流问题
第五次迭代：找到最短路 v1 v2 v5 v7 。 第五次迭代后总流量为 9，总费用 123。
(3,6)
(0,4) (1,7)
(2,5) (1,-4)
（ 0,3） (1,4)
(0,3)
(0,8)
（ 0,2）
v1
v2
v5
v7
v4
v3
v6
(0,3)
(6,-3)
(2,-8)(1,-3)（ 3,-2）
(3,-6)
(3,-4)
(0,-5)（ 1,4） (4,-7)(3,-4)（ 2,-3）
图 11-33
管 理 运 筹 学 70
§ 5 最小费用最大流问题
第六次迭代：找到最短路 v1 v2 v3 v5 v7 。 第六次迭代后总流量为
10，总费用 145。已经找不到从 v1到 v7的每条弧容量都大于零的路了，故已求得最小费用最大流了。
(3,6)
(0,4) (1,7)
(2,5) (1,-4)
（ 0,3） (1,4)
(0,3)
(0,8)
（ 0,2）
v1
v2
v5
v7
v4
v3
v6
(0,3)
(6,-3)
(2,-8)(1,-3)（ 3,-2）
(3,-6)
(3,-4)
(0,-5)（ 1,4） (4,-7)(3,-4)（ 2,-3）
图 11-34
管 理 运 筹 学 71
§ 5 最小费用最大流问题如果对例 7求一个最小费用流的问题：每小时运送 6万加仑石油从 v1到
v7的最小费用是多少，或者每小时运送 7万加仑呢？我们可以从第四次迭代及图 11-32即可得到运送 6万加仑最小费用 72百元，其运送方式通过比较图 11-28及图 11-32即得图 11-36所示。
至于每小时运送 7万加仑，我们可以在图 11-36的基础上，再按第五次迭代所选的最短路运送 1万加仑即得最小费用,72+1*17=89百元，其运送方式如图 11-37所示。
3 5
1
2 3
1 2
6
v1
v2
v5
v4
v3
v6
10
3
4 2 v7 10
第六次迭代后总流量图 11-35
管 理 运 筹 学 72
§ 5 最小费用最大流问题
1
2 3
1 2
6
v1
v2
v5
v4
v3
v6
6
3
1 v7
图 11-36
1 2
2 3
1 2
6
v1
v2
v5
v4
v3
v6
3
1 1 v7
图 11-37
注：,管理运筹学软件,有专门的子程序用于解决这类问题。
