数学建模设备更新问题

1、本队分工： 09数师 2 黄丹萍主管建模， 09信本郑永祥主管程序， 09 数师 2 郑丽璇主管论文说明： 我们的分工不是很明确的，我们主要都是一起讨论合作想出解 决此问题的答案的设备更新问题摘要本文针对的问题是求解设备更新过程中最小总支出的问题，我们运 用了求最短路径的方法，求出指定两点之间的最短路即最小总支出，我 们将第 i 年年初购进一台新设备设为变量 vi（ （i=1 ，2，3，4，5，6），其 中，v6为虚设点，表示第五年年底购进设备，从而将该问题转化为求从 vi到V6的最短路径。我们利用Dijkstra算法求解本问题，所用的软件为 matlab。而后通过计算机的多次模拟运算，分析以

2、及检验，验证出我们 建立该模型的科学性、合理性以及正确性。一、问题的重述：设备更新问题某工厂使用一台设备，每年年初工厂都要作出决定，如果继续使用 旧的，要付维修费；若购买一台新设备，要付购买费。试制定一个五年 的更新计划，使总支出最少。已知设备在各年的购买费，及不同机器役龄时的残值与维修费，如下表所示项目第一年第二年第三年第四年第五年购买费1112131414机器役龄0 11 223344 5维修费5681118残值43210二、模型假设：1、机器在购买 N年之后维修费用是固定不变的，不存在人为的破坏因素使之不能正常运行；2、公司有足够的资金支付设备；3、公司该设备只使用一台， 不存在公司同时

3、用多台机器的现象4、从第一年开始一定要购置一台设备三、符号说明：1、Vi表示第i年年初购进一台新设备，虚设一个点V6，表示第五年 年底；2、 边（Vi，Vj）表示第i年初购进的设备一直使用到第j年初（即 第j-1年底）；3、 边（Vi，Vj ）上的数字表示第i年初购进设备，一直使用到第j年初所需支付的购买、维修的全部费用 四、问题的分析：为了使问题简化，我们将求最小总支出转化为求最小路径问题，这样，设备更新问题可简化为求从 V1到V6的最短路问题，可由上表得下对于边（Vi， V2）有第一年购买的费用11加上一年的维修费用5减去一年役龄机器的残值4得到12；同理：（Vi，V3）（Vi，V4）（V

4、i，V5）（Vi，V6）（V2，V3）（V2，V4）II+5+6-3=I9II+5+6+8-2=28II+5+6+8+II-1=40II+5+6+8+II + I8-0=5912+5-4=1312+5+6-3=20第5页共13页V2，V5)i2+5+6+8-2=29V2，V6)i2+5+6+8+ii-i=4iV3，V4)i3+5-4=i4V3，V5)i3+5+6-3=2iV3，V6)i3+5+6+8-2=30V4，V5)i4+5-4=i5V4，V6)i4+5+6-3=22V5，V6)i4+5-4=i5由上图，我们就可用 Dijkstra 算法将设备更新的问题算出最小总支出五、模型的建立与求解：

5、由上述分析可知 Dijkstra 算法中所对应的结点跟路径， 下面给出其基本步骤：采用标号法，用两种标号：T标号和P标号，T标号为试 探性标号，P标号为永久性标号，给Vi 个P标号时表示从Vi到Vj 的最短路权， vi 的标号不再改变。给 vi 一个 T 标号是表示从 vi 到 Vj的最短路权的上界，是一种临时标号，凡没有得到 P标号的点都 有T标号。（1）首先给Vi以P（Vi）=0，给其余所有点T标号，T（vi）=+ 乂（ i=2，8）（2）由于（ Vi，V2）， （Vi，V3） ,（Vi，V4） ,（Vi，V5） ,（Vi，V6）边属于E,且Vi, V2为T标号，所以修改这两个点的标号：T

6、(V2)=minT( V2),P( Vi)+I i2=min+ 乂,0+12=12T(V3)=minT( Vi),P( V3)+I i3=min+ 乂,0+19=19T(V4)=minT( Vi),P( V4)+ I i4=min+,0+28=28T(V5)=minT( Vi),P( V3)+ I i5=min+ ,0+50=50 T(V6)=minT( Vi),P( V3)+ I i6=min+ ,0+59=59(3) 比较所有T标号，T(V2)最小，所以令P(V2)=12.并记录路径 (V1，V2)。(4) V2为刚得到P标号的点，考察边(V2, V3), ( V2 , V3), ( V2

7、 , V4), ( V2，V5)，( V2，V6)的端点 VI，V2。T(V3)=minT( V3),P( V2)+I 23=min19 ， 12+13=19 T(V4)=minT( V4),P( V2)+I 24=min28 ， 12+20=28 T(V5)=minT( V5),P( V2)+I 25=min40 ， 12+29=40T(V6)=minT( V6),P( V2)+I 26=min59 ， 12+41=53(5) 比较所有 T 标号， T(V3) 最小，所以令 P(V3)=19. 并记录路径 (V1， V3)。(6) 考虑点V3,有T(V4)=minT( V3),P( V3)+

8、I 34=min28 ， 19+14=28 T(V5)=minT( V3),P( V3)+I 35=min40 ， 19+21=40 T(V6)=minT( V3),P( V3)+I 36=min53 ， 19+30=53 比较所有 T 标号， T(V4) 最小，所以令 P(V4)=28. 并记录路径第 8 页 共 13 页(Vi, V4 )。(7) 考虑点V4,有T(V5)=minT(v 4),P( V4)+ l 45=min40,28+15=40 T(Vi)=minT( V6),P( V4)+ l 46=min49,28+22=49(8) 比较所有T标号，T(V5)最小，所以令P(V5)=

9、40.并记录路径 (Vi，V5 )。(9) 考虑点V6,有T(V6)=minT( V6),P( V5)+ l 56=min49,40+15=49(10) 因只有一个T标号T(V6),令P(V6)=49，记录路径(V3，V6)，计算结束。由计算结果可知：Vi L 3 6为最短路，路长为49,即 在第一年，第三年初各购买一台新设备为最优决策，这时 5年的总费用 为49.全部计算结果如下图所示，同时可得到Vi到其他点的最短路径，如下图中的粗线所示：Matlab的编程语言如下：关于求最小路径的 M函数fun cti onS,D=mi nRoute(i,m,W,opt)%图与网络论中秋最短路径的Dijk

10、stra算法M函数%格式S,D=minroute(I,m,W,opt)%i为最短路径的起始点， m为图定点数 W为图的带权邻接矩阵 不构成边的两顶点之间的权用 inf表示.S的每一列从上到下记 录了从始点到终点的最短路径所经顶点的序号.opt(缺省值)时,S按最短路径值从小到大显示结果 .%D是一行向量，对应记录了S各列所示路径的大小if nargin<4 ,opt=0; enddd=;tt=;ss=;ss(1,1)=i;V=1:m;V(i)=;第9页共13页dd=0;i;kk=2;mdd,ndd=size(dd);while isempty(V)tmpd,j=min(W(i,V);tm

11、pj=V(j);for k=2:nddtmp1,jj=min(dd(1,k)+W(dd(2,k),V);tmp2=V(jj);tt(k-1,:)=tmp1,tmp2,jj;endtmp=tmpd,tmpj,j;tt;tmp3,tmp4=min(tmp(:,1);if tmp3=tmpdss(1:2,kk)=i;tmp(tmp4,2);else tmp5=find(ss(:,tmp4)=0);tmp6=length(tmp5);if dd(2,tmp4)=ss(tmp6,tmp4)ss(1:tmp6+1,kk)=ss(tmp5,tmp4);tmp(tmp4,2);else ss(1:3,kk)=

12、i;dd(2,tmp4);tmp(tmp4,2);endenddd=dd,tmp3;tmp(tmp4,2);V(tmp(tmp4,3)=; mdd,ndd=size(dd);kk=kk+1;endif opt=1tmp,t=sort(dd(2,:);S=ss(:,t);D=dd(1,t);else S=ss;D=dd(1,:);end利用此函数的求解过程>> n=6;>> w=inf*ones(6);>> w(1,2,3,4,5,6)=12,19,28,40,59;>> w(2,3,4,5,6)=13,20,29,41;w(3,4,5,6)=14

13、,21,30;>> w(4,5,6)=15,22;>> w(5,6)=15;>> s,d=minroute(1,n,w)求解所得结果：s =1111110234530000060 12 19 28 40 49六、模型的检验利用常规数学方法求解此题如下： 由题意可知，五年下来最多能每一年用五台，最少要用一 台机器，设总共所用的支出为 y ，( 1) 只用一台设备时： y=11+5+6+8+11+18=59(2) 用两台设备时：a. 第一台使用一年：y=(11+13)+(5+6+5+6+8+11)-(3+2)=53b. 第一台使用两年： y=(11+13)+(5

14、+6+5+6+8)-(3+2)=49c. 第一台使用三年： y=(11+14)+(5+6+8+5+6)-(2+3)=50d. 第一台使用四年：y=(11+14)+(5+6+8+11+5)-(1+4)=55(3) 用三台设备时：a.第一台用一年，第二台用一年：y=(11+12+13)+(5+5+5+6+8)-(4+4+4+2)=55b 第一台用一年，第二台用两年： y=(11+12+14)+(5+5+6+5+6)-(4+3+3)=54C.第一台用一年，第二台用三年：y=(11+12+14)+(5+5+6+8+5)-(4+2+4)=56d 第一台用两年，第二台用一年：y=(11+13+14)+(5

15、+6+5+5+6)-(3+4+3)=55e. 第一台用两年，第二台用两年：y=(11+13+14)+(5+6+5+6+5)-(3+3+4)=55f. 第一台用三年，第二台用一年：y=(11+14+14)+(5+6+8+5+5)-(4+3+3)=584) 用四台设备时：a. 第一台用一年，第二台用一年，第三台用一年：y=(11+12+13+14)+(5+5+5+5+6)-(4+4+4+3)=61b. 第一台用一年，第二台用一年，第三台用两年：y=(11+12+13+14)+(5+5+5+6+5)-(4+4+3+4)=61C. 第一台用一年，第二台用两年，第三台用一年：y=(11+12+14+14

16、)+(5+5+6+5+5)-(4+4+3+4)=62d. 第一台用一年，第二台用一年，第三台用一年：y=(11+12+14+14)+(5+6+5+5+5)-(3+4+4+4)=635) 用五台设备时：此时只有一种情况：y=(11+12+13+14+14)+(5+5+5+5+5)-(4+4+4+4+4)=69 由以上结果可看出，当 y=49 时取得最小值，即最小的总支 出为第一台使用两年， 在第三年初购买新的设备能使总支出 最小，且最小总支出费用为 49 万元，这与计算结果完全吻 合，充分说明了我们所建立的模型的合理性， 可行性以及正 确性！七、模型的评价及改进： 本模型理论上可以用于解决任意有关设备更新的任何问 题，成功的运用 Dijkstra 算法， 该算法简洁明了， 适用于无需 遍布网络中所有点只要求得两定点的最短路径，对解决最小总 支出是很方便而且优越，目前被认为是求无负权网络的最好方 法；我们用计算机软件 matlab 可以成功地求出最小总支出， 容 易操作，具有实用性。我们还可以采用其它数学软件通过程序 的编写运行来求得最优解，如Qsb, C+等,此外，这种算法还可以求从一个城市到另一个城市的最短路径问题，资金周转问 题，聘请员工实现最优化等问题，值得进行社会推广。但是，在本问题的建立过程中，我们舍弃了某些影响因素 的结果，尽