-
本队分工：
09
数师
2
黄丹萍主管建模，
09
信本郑永祥主管
程序，
09
数师
2
郑
丽
璇
主
管
论
文
说明
：
我们的分工不是很明确的，
我们主要都是一起讨论合作想出解
决此问
题的答案的
设备更新问题
摘
要
本文针对的问题是求解设备更新过程中最小总支出的问题，我们运用了
求最短路径的方法，求出指定两点之间的最短路即最小总支出，我们将第
i
年年初购进一台新设备设为变量
v
i
( (i=1
，
2
，
3
，
4
，
5
，
6)
，其中，
v6
为虚设
点，表示第五年年底购进设备，从
而将该问题转化为求从
v
1
到
v
6
的最短路
径。我们
利用
Dijkstra
算法求解本问题，所用的软件为
matlab
。而后通过计
算机的多次模拟运算
，分析以及检验，验证出我们建立该模型的科学性、合
理性以及正确性。
一、问题的重述：
设备更新问题
某工厂使用一台设备，
每年年初工厂都要作出决定，如果继续使用旧的，要
付维修费；若购买一台新设备，要付
购买费。试制定一个五年的更新计划，
使总支出最少。已知设备在各年的购买费，及不同
机器役龄时的残值与维修
费，如下表所示。
项目
购买费
第一年
11
第二年
12
第三年
13
第四年
14
第五年
14
机器役龄
维修费
残值
0
—
1
5
4
1
—
2
6
3
2
—
3
8
2
3
—
4
11
1
4
—
5
18
0
二、模型假设：
1
、机器在购买
N
年之后维修
费用是固定不变的，不存在人为
的破坏因素使之不能正常运行；
2
、公司有足够的资金支付设备；
<
/p>
3
、公司该设备只使用一台，不存在公司同时用多台机器的现
象
4
、从第一年开始一定要购置一台设备
三、符号说明：
1
< br>、
v
i
表示第
< br>i
年年初购进一台新设备，
虚设一个点
< br>v
6
，
表示第五年年底；
2
、边（
v
i
，
v
j
）表示第
i
年初购进的设备一直使用到第
j
年初（即第
j-1
年
底）；
3
、边（
v
i
，
v
j
）上的数字表示第
i
年初购进设备，
一直使用到第
j
年初
所需支付的购买、
维修的全部费用
四、问题的分析：
为了使问题简化，我们将求最小总支出转化为求最小路径问题，这样，
< br>设备更新问题可简化为求从
v
1
到
v
6
的最短路问题，可由上表得下图
19
40
28
30
21
14
V
3
20
V
4
15
V
5
15
V
6
59
V
1
12
V
2
13
22
29
对于边（
v
1
，
v
2
）有第一年购买的费用
11
加上
一年的维修费用
5
减去
一年役龄机器的
残值
4
得到
12
；
同理：（
v
1
，
v
3
）
11+5+6-3=19
（
v
1
，
v
4
）
11+5+6+8-2=28
（
v<
/p>
1
，
v
5
）
11+5+6+8+11-1=40
（
v
1
，
v
6
）
11+5+6+8+11+18-0=59
（
v
2
，
v
3
）
12+5-4=13
（
v
2
，
v
4
）
12+5+6-3=20
（
v
2
，
v
5
）
12+5+6+8-2=29 <
/p>
（
v
2
，
v
6
）
12+5+6+8+11-1=41
（
v
3
，
v
4
）
13+5-4=14
（
v
3
，
v
5
）
13+5+6-3=21
（
v
3
，
v
6
）
13+5+6+8-2=30 <
/p>
（
v
4
，
v
5
）
14+5-4=15
（
v
4
，
v
6
）
14+5+6-3=22
（
v
5
，
v
6
）
14+5-4=15
由上图，我们就可用
Dijkstra
算法将设备更新的问题算出最小总支出
41
五、模型的建立与求解：
由上述分析可知
Dijkstra
算法中所
对应的结点跟路径，
下面给出其基本
步骤：
采用标号法，
用两种标号：
T
标号
和
P
标号，
T
标号为试探性标号，
P
标号为永久性标号，给
< br>v
i
一个
P
标号时表示从
v
i
到
v
j
的最短路权，
v
i
的标号不再改变。给
v
i
一个
T
标号是表示从
v
i
到
v
j
的最短路权的上界，
是一种临时标号，凡没有得到<
/p>
P
标号的点都有
T
标号。
（
1
）首先给
v
1
以
P
（
v
1
）
=0
，给其余所有点
T
标号，
T(
v
1
)=+
∞（
i=2
，…，
8
）
（
2
）由于（
v<
/p>
1
，
v
2
），（
v
1
，
v
3
）
,
（
v
1
，
v
4
）
,
（
v
1
，
v
5
）
,
（<
/p>
v
1
，
v
6
）边属于
E
，且<
/p>
v
，
v
为
T
标号，所以修改这两个点的标号：
1
2
T(
v
2
)=min[T(
v
2
),P(
v
1
)+
l
12
]=min[+
∞
,0+12]=12
T(
< br>v
3
)=min[T(
v
1
),P(
v
3
)+
l
13
]=m
in[+
∞
,0+19]=19
T(
v
4
)=min[T(
v
1
),P(
v
4
)+
l
14
]=min[+
∞
,0+28]=28
T(
v
5
)=min[T
(
v
1
),P(
v
3
)+
l
15
]=min[+
∞
,0+50]=
50
T(
v
6
)=min[T(
v
1
),P(
v
3
)+
l
16
]=min[+
∞
,0+59]=59
（
3
）比较所
有
T
标号，
T(
v
2
)
最小，所以令
P(
v
2
)=12.
并记录路径（
v
1
，<
/p>
v
2
）。
（
4
）
v
2
为刚得到
P
标号的点
，考察边（
v
2
，
v
3
），（
v
2
，
v
3
），（
v
2
，
v
4
）
,
（<
/p>
v
2
，
v
5
），（
v
2
，
v
6
）的端点
v
1
，
v
2
。
T(
v
3
)=min[T(
v
3
),P(
v
2
)+
l
23
]=min[19
，
12+13]=19
T(
v
4
)=min[T(
v
4
),P(
v
2
)+
l
24
]=min[28
，
12+20]=28
T(
v
5
)=
min[T(
v
5
),P(
v
2
)+
l
25
]=min[40
，
1
2+29]=40
T(
v<
/p>
6
)=min[T(
v
< br>6
),P(
v
2
)+
l
26
]=min[59
，
12+41]=53
（
5
）比较所有
T
标号，<
/p>
T(
v
3
)
最小，所以令
P(
v
3
)=19.
并记录路径（
v
1
，
v
3
）。
（
6
）考虑点
v
3
，有
T(v
4
)=min
[T(
v
3
),P(
< br>v
3
)+
l
34
]=min[28
，
19+1
4]=28
T(
v
5
)=min[T(
v
3
),P
(
v
3
)+
l
35
]=min[40
，
19+21]=40
T(
v
6
)=min[T(
v
3
),P(
v
3
)+
l
36
]=min[53
，
19+30]=53
（
7
）比较所有
T
标号，
T(
v
4
)
最小，所以令
P(
v
4
)=28.
并记录路径（
v
1
，
v
4
）。<
/p>
（
8
）考虑点
v
4
，有
<
/p>
T(
v
5
)=m
in[T(v
4
),P(
v
4
)+
l
45
]=min[40,28+15]=40
T(
v
1
)=min[T(
v
6
),P(
v
4
)+
l
46
]=min[4
9,28+22]=49
（
9
）比较
所有
T
标号，
T(
v
5
)
最小，所以令
P(
v
5
)=40.
并记录路径（
v
1
，
v
5
）。
<
/p>
（
10
）考虑点
v
6
，有
T
(
v
6
)=min[T(
v
6
),P(
v
5
)+
l
56
]=min[49,40+15]=49
（
11
）因只有一个
T
标号
< br>T(
v
6
),
< br>令
P(
v
6
)=49
，记录路径
（
v
3
，
v
6
），计算结束。
由计算
结果可知：
v
1
v
3
v
6
< br>为最短路，路长为
49
，即在第
一年，第三年初各购买一台新设备为最优决策，这时
5
年的总费
用为
49.
全部计算结果如下图所示，同时可得到
v
1
到其他点的最短路径，如下图
中的粗线所示：
40
28
19
12
< br>V
2
（
12
）
59
30
21
14
15
< br>V
4
（
28
）
V
1
（
0
）
13
V
3
（
19
）
15
V
5
（
40
）
V<
/p>
6
（
49
）
20
29
41
22
Matlab
的编程语言如下：