数学建模_设备更新问题数学建模_设备更新问题.doc

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