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