数学建模-设备更新问题

第1页共13页本队分工：09数师2黄丹萍主管建模，09信本郑永祥主管程序，09数师2郑丽璇主管论文说明：我们的分工不是很明确的，我们主要都是一起讨论合作想出解决此问题的答案的设备更新问题摘要本文针对的问题是求解设备更新过程中最小总支出的问题，我们运用了求最短路径的方法，求出指定两点之间的最短路即最小总支出，我们将第i年年初购进一台新设备设为变量vi((i=1，2，3，4，5，6)，其中，v6为虚设点，表示第五年年底购进设备，从而将该问题转化为求从v1到v6的最短路径。我们利用Dijkstra算法求解本问题，所用的软件为matlab。而后通过计算机的多次模拟运算，分析以及检验，验证出我们建立该模型的科学性、合理性以及正确性。一、问题的重述：设备更新问题某工厂使用一台设备，每年年初工厂都要作出决定，如果继续使用旧的，要付维修费；若购买一台新设备，要付购买费。试制定一个五年的更新计划，使总支出最少。已知设备在各年的购买费，及不同机器役第2页共13页龄时的残值与维修费，如下表所示。项目第一年第二年第三年第四年第五年购买费1112131414机器役龄0—11—22—33—44—5维修费5681118残值43210二、模型假设：1、机器在购买N年之后维修费用是固定不变的，不存在人为的破坏因素使之不能正常运行；2、公司有足够的资金支付设备；3、公司该设备只使用一台，不存在公司同时用多台机器的现象4、从第一年开始一定要购置一台设备三、符号说明：1、vi表示第i年年初购进一台新设备，虚设一个点v6，表示第五年年底；2、边（vi，vj）表示第i年初购进的设备一直使用到第j年初（即第j-1年底）；3、边（vi，vj）上的数字表示第i年初购进设备，一直使用到第j第3页共13页年初所需支付的购买、维修的全部费用四、问题的分析：为了使问题简化，我们将求最小总支出转化为求最小路径问题，这样，设备更新问题可简化为求从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=20594030281213141515202941222119V1V2V3V6V5V4第4页共13页（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标号，所以修改这两个点的标号：第5页共13页T(v2)=min[T(v2),P(v1)+l12]=min[+∞,0+12]=12T(v3)=min[T(v1),P(v3)+l13]=min[+∞,0+19]=19T(v4)=min[T(v1),P(v4)+l14]=min[+∞,0+28]=28T(v5)=min[T(v1),P(v3)+l15]=min[+∞,0+50]=50T(v6)=min[T(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)=min[T(v3),P(v2)+l23]=min[19，12+13]=19T(v4)=min[T(v4),P(v2)+l24]=min[28，12+20]=28T(v5)=min[T(v5),P(v2)+l25]=min[40，12+29]=40T(v6)=min[T(v6),P(v2)+l26]=min[59，12+41]=53（5）比较所有T标号，T(v3)最小，所以令P(v3)=19.并记录路径（v1，v3）。（6）考虑点v3，有T(v4)=min[T(v3),P(v3)+l34]=min[28，19+14]=28T(v5)=min[T(v3),P(v3)+l35]=min[40，19+21]=40T(v6)=min[T(v3),P(v3)+l36]=min[53，19+30]=53（7）比较所有T标号，T(v4)最小，所以令P(v4)=28.并记录路径第6页共13页（v1，v4）。（8）考虑点v4，有T(v5)=min[T(v4),P(v4)+l45]=min[40,28+15]=40T(v1)=min[T(v6),P(v4)+l46]=min[49,28+22]=49（9）比较所有T标号，T(v5)最小，所以令P(v5)=40.并记录路径（v1，v5）。（10）考虑点v6，有T(v6)=min[T(v6),P(v5)+l56]=min[49,40+15]=49（11）因只有一个T标号T(v6),令P(v6)=49，记录路径（v3，v6），计算结束。由计算结果可知：v1v3v6为最短路，路长为49，即在第一年，第三年初各购买一台新设备为最优决策，这时5年的总费用为49.全部计算结果如下图所示，同时可得到v1到其他点的最短路径，如下图中的粗线所示：第7页共13页Matlab的编程语言如下：关于求最小路径的M函数function[S,D]=minRoute(i,m,W,opt)%图与网络论中秋最短路径的Dijkstra算法M函数%格式[S,D]=minroute(I,m,W,opt)%i为最短路径的起始点，m为图定点数,W为图的带权邻接矩阵,不构成边的两顶点之间的权用inf表示.S的每一列从上到下记录了从始点到终点的最短路径所经顶点的序号.opt(缺省值)时,S按最短路径值从小到大显示结果.%D是一行向量，对应记录了S各列所示路径的大小ifnargin4,opt=0;enddd=[];tt=[];ss=[];ss(1,1)=i;V=1:m;V(i)=[];594030281213141515202941222119V1（0）V2（12）V3（19）V6（49）V5（40）V4（28）第8页共13页dd=[0;i];kk=2;[mdd,ndd]=size(dd);while~isempty(V)[tmpd,j]=min(W(i,V));tmpj=V(j);fork=2:ndd[tmp1,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));iftmp3==tmpdss(1:2,kk)=[i;tmp(tmp4,2)];elsetmp5=find(ss(:,tmp4)~=0);tmp6=length(tmp5);ifdd(2,tmp4)==ss(tmp6,tmp4)ss(1:tmp6+1,kk)=[ss(tmp5,tmp4);tmp(tmp4,2)];elsess(1:3,kk)=[i;dd(2,tmp4);tmp(tmp4,2)];endenddd=[dd,[tmp3;tmp(tmp4,2)]];V(tmp(tmp4,3))=[];[mdd,ndd]=size(dd);kk=kk+1;end第9页共13页ifopt==1[tmp,t]=sort(dd(2,:));S=ss(:,t);D=dd(1,t);elseS=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,21,30];w(4,[5,6])=[15,22];w(5,6)=15;[s,d]=minroute(1,n,w)求解所得结果：s=111111023453000006第10页共13页d=01219284049六、模型的检验利用常规数学方法求解此题如下：由题意可知，五年下来最多能每一年用五台，最少要用一台机器，设总共所用的支出为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+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)=55第11页共13页b．第一台用一年，第二台用两年：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+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)=58（4）用四台设备时：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)+(5+5+6+5+5)-(4+4+3+4)=62d.第一台用一年，第二台用一年，第三台用一年：y=(11+12+14+14)+(5+6+5+5+5)-(3+4+4+4)=63（5）用五台设备时：第12页共13页此时只有一种情况：y=(11+12+13+14+14)+(5+5+5+5+5)-(4+4+4+4+4)=69由以上结果可看出，当y=49时取得最小值，即最小的总支出为第一台使用两年，在第三年初购买新的设备能使总支出最小，且最小总支出费用为49万元，这与计算结果完全吻合，充分说明了我们所建立的模型的合理性，可行性以及正确性！七、模型的评价及改进：本模型理论上可以用于解决任意有关设备更新的任何问题，成功的运用Dijkstra算法，该算法简洁明了，适用于无需遍布网络中所有点只要求得两定点的最短路径，对解决最小总支出是很方便而且优越，目前被认为是求无负权网络的最好方法；我们用计算机软件matlab可以成功地求出最小总支出，容易操作，具有实用性。我们还可以采用其它数学软件通过程序的编写运行来求得最优解，如Qsb，C++等，