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

最短路法解决设备更新问题某工厂使用一台设备，每年年初工厂都要作出决定，如果继续使用旧的，要付维修费；若购买一台新设备，要付购买费。试制定一个五年的更新计划，使总支出最少。已知设备在各年的购买费，及不同机器役龄时的残值与维修费，如下表所示。项目第一年第二年第三年第四年第五年购买费1112131414机器役龄0112233445维修费5681118残值43210二、模型假设：1、机器在购买N年之后维修费用是固定不变的，不存在人为的破坏因素使之不能正常运行；2、公司有足够的资金支付设备；3、公司该设备只使用一台，不存在公司同时用多台机器的现象4、从第一年开始一定要购置一台设备三、符号说明：1、vi表示第i年年初购进一台新设备，虚设一个点v6，表示第五年年底；2、边（vi，vj）表示第i年初购进的设备一直使用到第j年初（即第j-1年底）；3、边（vi，vj）上的数字表示第i年初购进设备，一直使用到第j年初所需支付的购买、维修的全部费用四、问题的分析：为了使问题简化，我们将求最小总支出转化为求最小路径问题，这样，设备更新问题可简化为求从v1到v6的最短路问题，可由上表得下图5940192830211515141312V1V2V6V5V4V320224129对于边（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由上图，我们就可以算出设备更新的问题算出最小总支出五、模型的建立与求解：下面给出其基本步骤：采用标号法，用两种标号：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)=minT(v2),P(v1)+l12=min+,0+12=12T(v3)=minT(v1),P(v3)+l13=min+,0+19=19T(v4)=minT(v1),P(v4)+l14=min+,0+28=28T(v5)=minT(v1),P(v3)+l15=min+,0+50=50T(v6)=minT(v1),P(v3)+l16=min+,0+59=59（3）比较所有T标号，T(v2)最小，所以令P(v2)=12.并记录路径（v1，v2）。（4）v2为刚得到P标号的点，考察边（v2，v3），（v2，v3），（v2，v4）,（v2，v5），（v2，v6）的端点v1，v2。T(v3)=minT(v3),P(v2)+l23=min19，12+13=19T(v4)=minT(v4),P(v2)+l24=min28，12+20=28T(v5)=minT(v5),P(v2)+l25=min40，12+29=40 T(v6)=minT(v6),P(v2)+l26=min59，12+41=53（5）比较所有T标号，T(v3)最小，所以令P(v3)=19.并记录路径（v1，v3）。（6）考虑点v3，有T(v4)=minT(v3),P(v3)+l34=min28，19+14=28T(v5)=minT(v3),P(v3)+l35=min40，19+21=40T(v6)=minT(v3),P(v3)+l36=min53，19+30=53（7）比较所有T标号，T(v4)最小，所以令P(v4)=28.并记录路径（v1，v4）。（8）考虑点v4，有T(v5)=minT(v4),P(v4)+l45=min40,28+15=40T(v1)=minT(v6),P(v4)+l46=min49,28+22=49（9）比较所有T标号，T(v5)最小，所以令P(v5)=40.并记录路径（v1，v5）。（10）考虑点v6，有T(v6)=minT(v6),P(v5)+l56=min49,40+15=49（11）因只有一个T标号T(v6),令P(v6)=49，记录路径（v3，v6），计算结束。由计算结果可知：v1 v3 v6为最短路，路长为49，即在第一年，第三年初各购买一台新设备为最优决策，这时5年的总费用为49.全部计算结