文档介绍：网络规划习题六
求图6—104中V1至V10的最短路径和长度
V1 60 V3 30 V5 35 V7 40 V9
30
40 60 30 50 15 25 25 15 30
V2 50 V4 20 V6 15 V8 35 V10
V V1 V2 V3 V4 V5 V6 V7 V8 V9 V10
1 0* M M M M M M M M M
2 40* 60 60 M M M M M M
3 60 60* M M M M M M
4 60* M 80 M M M M
5 90 80* M M M M
6 90* M 95 M M
7 125 95* M M
8 125 110* 130
9 125* 130
10 130*
P1 10*=V1V4V6V8V10=130
d(V1,V10)= d1 10=130
某厂正在制订5年里购买某种设备的计划。表6-53给出从第一年到第五年的设备价格
年号 1 2 3 4 5
购买价格 20 21 23 24 26
(表6—53)
设备寿命(0,1) (1,2) (2,3) (3,4) (4,5)
使用维修费 8 13 19 23 30
表6—54给出设备使用维修费
该工厂可以采用的最优的策略是什么?
V2
28 84 61 42 29
V1 41 V3
113 83 60 63 44 31
V6 45 V4
34 32
V5
V1 V2 V3 V4 V5 V6
1 0* M M M M M
2 28* 41 60 83 113
3 41* 60 83 112
4 60* 83 104
5 83* 104
104*
P1 6*=V1V3V6=104
最短路径为V1V3V6,即第1,3年购买新设备,5年的总费用为104。
L(v)
V1
V2
V3
V4
V5
V6
1
0*
M
M
M
M
M
2
28*
41
60
83
113
3
41*
60
83
112
4
60*
83
104
5
83*
104
6
104*
8、对图6—108求最小生成树和最大生成树
(1)
V2 3 V5
2
1 3 6 3
V6
V1 5 V4 3
1
2 1 7 2
V3 2 V7 5 V8
W(T*)=1+1+1+2+2+2+2=11 (最小生成树)
(2)
V2 3 V5
2
1 3 6 3
V6
V1 5