年初。
Wij— 第 i 年年初购进的新设备一直使用到第 j 年年初
这段 期间的全部费用。
精品课件
v2
15
21
15 40 29
30
21
v1
29
40 55
v3
16 22
23
v4
17
v6
18
v5
求解得v1到v6得最短路径为： v1-v3-v6，最短路长为51。 设备更新的计划是：第一年初购置一台新设备，使用到第二年末， 第三年初购置一台新设备，使精用品到课件第五年末，总费用为51。
V5 V6
89 69 25 14 03 30
V V1 V2 V3 V4 V5 V6
1
V 11 2345
2
V
C6= 3
V
4
V
22 23 33 44
2345 3345 4445 4555
5 55 5566
V
6
考虑各点的学习人数，对矩阵D6的每一行乘以相应各点的 人数，得到：
精品课件
0 50 150 175 200 275 40 0 80 100 120 180 180 120 0 30 60 150 D= 70 50 10 0 10 40 280 210 70 35 0 105 495 405 225 180 135 0
2
V
C0= 3
V
22 2 33 3 44 4
222 333 444
4
V 8 3 1 0 3
4
V 55 5 5 5 5
5 6 3 0
5 66 6 6 6 6
V
V0和相应的中间点矩阵C0如下：
精品课件
V
1
V
2
V D6=3V
4
V
5
V
6
V1 V2 V3 V4
02 67 20 45 64 01 75 10 8 621 11 9 5 4
年份
1
购置费
10
使用年限 0 -1
维修费
5
2
3
10
11
1- 2 2- 3
6
8
精品课件
4
5
表1
12 13
3- 4 4- 5 表2 11 15
解：为解决好这一问题，建立下述网络模型，并用最短路
令法：求解vi。— 第 i 年年初购进一台新设备，i=1 , 2 , 3 ,
4,5,6 v6 指第五年年末。
（vi，vj）— 第 i年年初引进新设备一直使用到第 j 年
下图是一个城镇的地图，现在要在该城镇的各地点铺设 管道，已知各点相互之间的铺设费用（单位：千元）， 如何设计铺设线路，使各地互通的总铺设费用最少？
8
3
74
5
10
7
2
6
7 9
8 12
51
5
4
精品课件
解：求各边相通且总费用最少的方案，实际上求最小树， 保证了各点之间连通且费用最少。
3
4
7
5
2
1
4
5
其总费用为：31千元
精品课件
市场 仓库
A1 A2 A3
B1 B2 B3 B4
30 10 0 40 0 0 10 50 20 10 40 5
需 求 量 20 20 60 20
精品课件
例 6：网络运输容量问题
有三个仓库运送某种产品到四个市场上去，仓库的供应量 是20、20和100件，市场需求量是20、20、60和20件。仓库 与市场之间的线路上的容量如下表所示（容量零表示两点 之间无直接的线路可通）。确定现有线路容量是否能满足 市场的需求。若不能，应修改哪条线路的容量。
v2
6
2
1
v1
48
7
v3
3
v4 6
1
v6
3 v5
精品课件
解：首先计算各点对间的最短路，每个学习者为使所走的路 程最短，应走最短路。
V V1 V2 V3 V4 V5 V6
1
V V1 V2 V3 V4 V5
1
V6
V 0 2 7
V 11 1 1 1 1
2
V
D0= 3
V
2 04 6 8 74 0 1 3 6 1 0 1 6
用一条边把代表这两个项目
v2
的顶点连接起来。这样得到
v3
下图
v1
为了解决这个问题，只需
找到一条包含所有顶点的
v4
初等链。
v5
如：{v4，v1，v2，v3，v5}是一条初等链，对应的比赛是： 100m自由泳，50m仰泳，50m蛙泳，100m碟泳，200m自由泳。
此问题的方案不唯一。 精品课件
例 2.线路铺设问题
例4.房屋设计问题
下图是某建筑物的平面图，要求在建筑物的内部从每一房间 都能走到别的所有房间，问至少要在墙上开多少门？试给出 一个开门的方案。
C B
A
D
E
I J
H
K G
F
精品课件
解：
把每一房间看作一个顶点，如果两房间相邻（有共同的隔 墙），则用边把对应的两个顶点连起来，这样就得到一个 无向图，如图。
§4.7 应 用 举 例
例1：比赛安排问题 有五名运动员参加游泳比赛，下表给出了每位运动员参加的 比赛项目，问如何安排比赛，才能使每位运动员都不连续地 参加比赛？
运动员 50m仰泳 50m蛙泳 100m蝶泳 100m自由泳 200m自由泳
A
*
B
*
*
*
C
*
*
D
*
*
E
*
*
精品课件
解：
用顶点v1，v2，v3，v4，v5表示五项比赛项目 如果两项比赛没有同一名运动员参加，把这两项紧排在一起
I H
G F
对应的开门方案如图所 示，共开10个门。
J B C IJ
K A
H D GK
E
F
精品课件
开门方案
例5：选址问题
有六个居民点v1，v2，v3，v4，v5，v6，拟定建一夜校，已知 各点参加学习的人数为25、20、30、10、35、45人，其道路 如图所示，试确定学校位于哪一个居民点，才能使学习者所 走的总路程最少？（图中边旁的数字为路段长度）
从一个房间到另一房间相当于从这个顶点有一条链能到另一 个顶点。
C
I
B
J 图的任意一个连通
H
A
D
G
的生成子图，在它
的所有边对应的隔 K 墙上开门，即可达
到要求。
E
F 精品课件
令所有边的权为1，为了使开的门尽可能少，就要使这个连 通子图的生成子图的边尽可能少，即求图的最小生成树。
B
C
D A
E
最小生成树
D = [1065 835 535 520 525 750]
V1…….V4：V1- V2 - V3 V4
V2…….V4： V2 - V3 - V4 V3…….V4： V3 - V4 V5…….V4： V5 - V4 V6…….V4： V6- V5 - V4
最短路程为520，即夜校应设在v4点，由
C6得到相应路径。
精品课件
例3.设备更新问题
某单位使用一台生产设备，在每年年底，单位领导都要决 策下年度是购买新设备还是继续使用旧设备。
若购置新设备，需要支付一笔购置费；如果继续使用旧的， 则要支付一定的维修费用。
一般说来，维修费随设备使用年限的延长而增加。根据以 往的统计资料，已经估算出设备在各年年初的价格和不同 使用年限的年维修费用，分别示于表1和表2。