期间的全部费用。
v2 15 40 21
29
29
15 21
v3
30
22
16
v1
55
40
23
17
v4
v6
18
v5
求解得v1到v6得最短路径为： v1-v3-v6，最短路长为51。 第三年初购置一台新设备，使用到第五年末，总费用为51。
设备更新的计划是：第一年初购置一台新设备，使用到第二年末，
例4.房屋设计问题
月份 正常生 产能力 加班生 产能力 需求量 单位产品正 单位产品加 常生产成本 班生产成本
1 2 3
30 40 20
15 15 10
30 30 30
50 60 55
55 65 62
解：构造网络图如下
X1 ——工厂处于正常生产状态
X2 ——工厂处于加班生产状态 Vj ——第j个月生产产品的存储与供货点。 增设起点S和终点T。这样问题就转化为求从S到T的最小费用最大流问题。
8 3 5 2 10 6 5 1 4 5
7
4
7
7
9 8 12
解：求各边相通且总费用最少的方案，实际上求最小树， 保证了各点之间连通且费用最少。
3
5 2
5
4
7
1
4
其总费用为：31千元
例3.设备更新问题
某单位使用一台生产设备，在每年年底，单位领导都要决 策下年度是购买新设备还是继续使用旧设备。
若购置新设备，需要支付一笔购置费；如果继续使用旧的， 则要支付一定的维修费用。 一般说来，维修费随设备使用年限的延长而增加。根据以 往的统计资料，已经估算出设备在各年年初的价格和不同 使用年限的年维修费用，分别示于表1和表2。
40 50 5 20
20 20 100
A2
A3 需求量
用点A1，A2，A3表示三个仓库；点B1，B2，B3，B4表示四个市 场；若仓库与市场间有线路可通，则在对应点间连一条弧， 弧的容量就是线路的容量。
增设一发点S，连接S与Ai，容量为Ai的供应量；增设一收点T， 连接Bi与T，容量为Bi的需求量，得到如下的网络。 问题转化成求S到T的最大流问题。 A1 A2 30 10 40 S 10 50 B1 B2
2 2
3 3 4 4
2
3 4
2
3 4
2
3 4
2
3 4
D0=
3
C0= 3
V
4
V
4
6 8
V
5

6
3
0
V
5
5 5
6 6
5
6
5
6
5
6
5
6
V
6
V
6 迭代得到最短距离矩阵D0和相应的中间点矩阵 C0如下：
V
1
V
V1 V2 V3 V4 V5 V6
1
V1 V2
V3
V4
V5 V6
V
2
0 2 6 7 8
D
E
G F
令所有边的权为1，为了使开的门尽可能少，就要使这个连 通子图的生成子图的边尽可能少，即求图的最小生成树。 对应的开门方案如图所 示，共开10个门。 J B C D E I H G F
开门方案
B
C H D
I
J
A E
最小生成树
G
F
K
A
K
例5：选址问题 有六个居民点v1，v2，v3，v4，v5，v6，拟定建一夜校，已知 各点参加学习的人数为25、20、30、10、35、45人，其道路 如图所示，试确定学校位于哪一个居民点，才能使学习者 所走的总路程最少？（图中边旁的数字为路段长度） v2 2 v1 7 v3 4 8
§4.7 应 用 举 例
例1：比赛安排问题 有五名运动员参加游泳比赛，下表给出了每位运动员参加的 比赛项目，问如何安排比赛，才能使每位运动员都不连续地 参加比赛？
运动员 50m仰泳 A B 50m蛙泳 100m蝶泳 100m自由泳 200m自由泳
* * * * *
C
D E
*
*
* * *
解： 用顶点v1，v2，v3，v4，v5表示五项比赛项目 如果两项比赛没有同一名运动员参加，把这两项紧排在一起 用一条边把代表这两个项目 的顶点连接起来。这样得到 下图 为了解决这个问题，只需 找到一条包含所有顶点的 初等链。 v2 v1
由最大流最小割定理，分离A和F的最小割容量等于由A到F的 最大流量 A(0,+) 2,1 (B,1) C 1,0 1,1 F 由上图得知：已标号点为A，B，C，而D，E，F不能获得标号， 从而知道该最大流对应的最小割为{（A，E），（C，D）， （C，F）}因此，切断AE，CD，CF三座桥梁，即可阻止对方 部队过河。 D 2,0 2,0
A2
S 1 1 A3 A4 A5 1
B4
B5
A1 A2
1,0
B1 B2 B3 1,1 1,0 1,1 T
S
1,1 1,1 A3 A4 A5 1,1
B4
1,1
B5
fmax=4，知道最多能有4架飞机同时出航。 分配方案为：
A2 - B1；A3 - B4 ; A4 - B2；A5 - B5
例9：桥梁切断问题 如下图A、B、C、D、E、F分别表示陆地和岛屿，若河的两岸 分别被敌对两方部队占领，问至少切断哪几座桥梁才能阻止对 方部队过河？
A
B
C
D
E
F
陆地、河流及桥梁示意图
解： 将A，B，C，D，E，F分别用一个点表示，相互之间有桥相连 的连一条弧；弧的容量就是两点间的桥梁数；设一个方向，得 到网络图如下： A 2 B 2 C 1 F 1 1 1 2 1 D 2 2
2
E
割是分离A和F的弧的集合,若切断一个割的所有弧对应的桥梁, 就可切断A和F之间的线路。切断最小割包含的弧对应的桥梁， 是切断A和F之间线路的桥梁数最少的方法。
6
v4
1 1 3
6 v6
3
v5
解：首先计算各点对间的最短路，每个学习者为使所走的路 程最短，应走最短路。 V
V
1
V1 V2 V3
V4 V5 V6
1
V
2
0 2 7
2 0 4
7 4 0 1 3
6 1 0 1
பைடு நூலகம் 8 3 1 0 6 3
V
2
V1 V2 V3 V6
V4 V5
1 1
1
1
1
1
V
V
V1 +,2 S
+,0
X1
40,60
V2 +,2
30,0
T
X2
10,62
V3
结 束！
年份 购置费 使用年限 维修费
1 10 0 -1 5
2 10 1- 2 6
3 11 2- 3 8
4 12 3- 4 11
5 13 4- 5 15
表1
表2
解：为解决好这一问题，建立下述网络模型，并用最短路 法求解。 令： vi — 第 i 年年初购进一台新设备，i=1 , 2 , 3 , 4 , 5 , 6 v6 指第五年年末。 （vi，vj）— 第 i年年初引进新设备一直使用到第 j 年年初。 Wij— 第 i 年年初购进的新设备一直使用到第 j 年年初这段
例8：分派问题
某飞行队有5名正驾驶员和5名副驾驶员。由于种种原因，某些 正、副驾驶员不能同时飞行，某些则可以，如下表所示，（* 表示可同机飞行）每架飞机出航时需要正、副驾驶员各一人， 问最多能有几架飞机同时出航？应如何安排正、副驾驶员？
副 正 A1 B1 B2 B3 B4 B5
A2
A3
* * * *
V5…….V4： V5 - V4 V6…….V4： V6- V5 - V4
495 405 225 180 135 0
D = [1065 835 535 520 525 750]
最短路程为520，即夜校应设在v4点，由
C6得到相应路径。
例 6：网络运输容量问题
有三个仓库运送某种产品到四个市场上去，仓库的供应量
* * *
*
A4
A5
用顶点A1，A2，A3，A4，A5表示5位副驾驶员； B1，B2，B3，B4，B5表示5位正驾驶员； 若正、副驾驶员可同机飞行，则在对应的点之间连一条弧， 方向由A指向B； 增设一个起点S和终点T，得到下图，各弧的容量均为1。 则问题转化成求S到T的最大流问题。
A1
1
B1
B2 B3 1 1 1 T 1
v3
v5
v4
如：{v4，v1，v2，v3，v5}是一条初等链，对应的比赛是：
100m自由泳，50m仰泳，50m蛙泳，100m碟泳，200m自由泳。 此问题的方案不唯一。
例 2.线路铺设问题
下图是一个城镇的地图，现在要在该城镇的各地点铺设 管道，已知各点相互之间的铺设费用（单位：千元）， 如何设计铺设线路，使各地互通的总铺设费用最少？
B (A,1)
E
例11:生产计划问题 某工厂与客户签定合同,当月起连续三个月每月末向客户提 供某种产品。该厂三个月的生产能力、单位产品生产成本及 客户需求见下表。 已知单位产品每积压一个月需支付存储费2元。在签定合同 时，工厂有该产品的库存量5个，工厂希望在第三个月末完 成合同后还能存储该产品10个。问工厂应如何安排生产计划， 使在满足上述条件的情况下，总的费用最小？
下图是某建筑物的平面图，要求在建筑物的内部从每一房间 都能走到别的所有房间，问至少要在墙上开多少门？试给出 一个开门的方案。
C B D
I H
J