數(shù)學(xué)建模-設(shè)備更新問題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上本隊(duì)分工：09數(shù)師2黃丹萍主管建模，09信本鄭永祥主管程序，09數(shù)師2鄭麗璇主管論文說明：我們的分工不是很明確的，我們主要都是一起討論合作想出解決此問題的答案的設(shè)備更新問題摘 要本文針對的問題是求解設(shè)備更新過程中最小總支出的問題，我們運(yùn)用了求最短路徑的方法，求出指定兩點(diǎn)之間的最短路即最小總支出，我們將第i年年初購進(jìn)一臺新設(shè)備設(shè)為變量vi( (i=1，2，3，4，5，6)，其中，v6為虛設(shè)點(diǎn)，表示第五年年底購進(jìn)設(shè)備，從而將該問題轉(zhuǎn)化為求從v1到v6的最短路徑。我們利用Dijkstra算法求解本問題，所用的軟件為matlab。而后通過計(jì)算機(jī)的多次模擬運(yùn)算，分析以及檢驗(yàn)，驗(yàn)

2、證出我們建立該模型的科學(xué)性、合理性以及正確性。一、問題的重述：設(shè)備更新問題某工廠使用一臺設(shè)備，每年年初工廠都要作出決定，如果繼續(xù)使用舊的，要付維修費(fèi)；若購買一臺新設(shè)備，要付購買費(fèi)。試制定一個五年的更新計(jì)劃，使總支出最少。已知設(shè)備在各年的購買費(fèi)，及不同機(jī)器役齡時的殘值與維修費(fèi)，如下表所示。項(xiàng)目第一年第二年第三年第四年第五年購買費(fèi)1112131414機(jī)器役齡0112233445維修費(fèi)5681118殘值43210二、模型假設(shè)：1、機(jī)器在購買N年之后維修費(fèi)用是固定不變的，不存在人為的破壞因素使之不能正常運(yùn)行；2、公司有足夠的資金支付設(shè)備；3、公司該設(shè)備只使用一臺，不存在公司同時用多臺機(jī)器的現(xiàn)象4、從第

3、一年開始一定要購置一臺設(shè)備三、符號說明：1、vi表示第i年年初購進(jìn)一臺新設(shè)備，虛設(shè)一個點(diǎn)v6，表示第五年年底；2、邊（vi，vj）表示第i年初購進(jìn)的設(shè)備一直使用到第j年初（即第j-1年底）；3、邊（vi，vj）上的數(shù)字表示第i年初購進(jìn)設(shè)備，一直使用到第j年初所需支付的購買、維修的全部費(fèi)用四、問題的分析：為了使問題簡化，我們將求最小總支出轉(zhuǎn)化為求最小路徑問題，這樣，設(shè)備更新問題可簡化為求從v1到v6的最短路問題，可由上表得下圖5940192830211515141312V1V2V6V5V4V320224129對于邊（v1，v2）有第一年購買的費(fèi)用11加上一年的維修費(fèi)用5減去一年役齡機(jī)器的殘值4得

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由上圖，我們就可用Di

5、jkstra算法將設(shè)備更新的問題算出最小總支出五、模型的建立與求解：由上述分析可知Dijkstra算法中所對應(yīng)的結(jié)點(diǎn)跟路徑，下面給出其基本步驟：采用標(biāo)號法，用兩種標(biāo)號：T標(biāo)號和P標(biāo)號，T標(biāo)號為試探性標(biāo)號，P標(biāo)號為永久性標(biāo)號，給vi一個P標(biāo)號時表示從vi到vj的最短路權(quán)，vi的標(biāo)號不再改變。給vi一個T標(biāo)號是表示從vi到vj的最短路權(quán)的上界，是一種臨時標(biāo)號，凡沒有得到P標(biāo)號的點(diǎn)都有T標(biāo)號。（1）首先給v1以P（v1）=0，給其余所有點(diǎn)T標(biāo)號，T(v1)=+（i=2，8）（2）由于（v1，v2），（v1，v3）,（v1，v4）,（v1，v5）,（v1，v6）邊屬于E，且v1，v2為T標(biāo)號，所以修改

6、這兩個點(diǎn)的標(biāo)號：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標(biāo)號，T(v2)最小，所以令P(v2)=12.并記錄路徑（v1，v2）。（4）v2為剛得到P標(biāo)號的點(diǎn)，考察邊（v2，v3），（v2，v3），（v2，v4）,（v2，v5），（v2，v6）的端點(diǎn)v1，

7、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標(biāo)號，T(v3)最小，所以令P(v3)=19.并記錄路徑（v1，v3）。（6）考慮點(diǎn)v3，有T(v4)=minT(v3),P(v3)+l34=min28，19+14=28T(v5)=minT(v3),P(v3)+l35=min40，19+21=40T(v6)=mi

8、nT(v3),P(v3)+l36=min53，19+30=53（7）比較所有T標(biāo)號，T(v4)最小，所以令P(v4)=28.并記錄路徑（v1，v4）。（8）考慮點(diǎn)v4，有T(v5)=minT(v4),P(v4)+l45=min40,28+15=40T(v1)=minT(v6),P(v4)+l46=min49,28+22=49（9）比較所有T標(biāo)號，T(v5)最小，所以令P(v5)=40.并記錄路徑（v1，v5）。（10）考慮點(diǎn)v6，有T(v6)=minT(v6),P(v5)+l56=min49,40+15=49（11）因只有一個T標(biāo)號T(v6),令P(v6)=49，記錄路徑（v3，v6），計(jì)算結(jié)

9、束。由計(jì)算結(jié)果可知：v1 v3 v6為最短路，路長為49，即在第一年，第三年初各購買一臺新設(shè)備為最優(yōu)決策，這時5年的總費(fèi)用為49.全部計(jì)算結(jié)果如下圖所示，同時可得到v1到其他點(diǎn)的最短路徑，如下圖中的粗線所示：5940283019211515141312V6（49）V5（40）V4（28）V3（19）V2（12）V1（0）20224129Matlab的編程語言如下：關(guān)于求最小路徑的M函數(shù)functionS,D=minRoute(i,m,W,opt)%圖與網(wǎng)絡(luò)論中秋最短路徑的Dijkstra算法M函數(shù)%格式S,D=minroute(I,m,W,opt)%i為最短路徑的起始點(diǎn)，m為圖定點(diǎn)數(shù),W為圖的

10、帶權(quán)鄰接矩陣,不構(gòu)成邊的兩頂點(diǎn)之間的權(quán)用inf表示.S的每一列從上到下記錄了從始點(diǎn)到終點(diǎn)的最短路徑所經(jīng)頂點(diǎn)的序號.opt(缺省值)時,S按最短路徑值從小到大顯示結(jié)果.%D是一行向量，對應(yīng)記錄了S各列所示路徑的大小if nargin<4,opt=0;enddd=;tt=;ss=;ss(1,1)=i;V=1:m;V(i)=;dd=0;i;kk=2;mdd,ndd=size(dd);while isempty(V) tmpd,j=min(W(i,V);tmpj=V(j); for k=2:ndd tmp1,jj=min(dd(1,k)+W(dd(2,k),V); tmp2=V(jj);tt(k

11、-1,:)=tmp1,tmp2,jj; end tmp=tmpd,tmpj,j;tt;tmp3,tmp4=min(tmp(:,1); if tmp3=tmpd ss(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)=i;dd(2,tmp4);tmp(tmp4,2); end end dd=dd,tmp3;tmp(tmp4,2);V(

12、tmp(tmp4,3)=; mdd,ndd=size(dd);kk=kk+1;endif opt=1 tmp,t=sort(dd(2,:);S=ss(:,t);D=dd(1,t);else S=ss;D=dd(1,:);end利用此函數(shù)的求解過程>> 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;>&

13、gt; s,d=minroute(1,n,w)求解所得結(jié)果：s = 1 1 1 1 1 1 0 2 3 4 5 3 0 0 0 0 0 6d = 0 12 19 28 40 49六、模型的檢驗(yàn)利用常規(guī)數(shù)學(xué)方法求解此題如下：由題意可知，五年下來最多能每一年用五臺，最少要用一臺機(jī)器，設(shè)總共所用的支出為y，（1） 只用一臺設(shè)備時：y=11+5+6+8+11+18=59（2） 用兩臺設(shè)備時：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)+(

14、5+6+8+5+6)-(2+3)=50d. 第一臺使用四年：y=(11+14)+(5+6+8+11+5)-(1+4)=55（3） 用三臺設(shè)備時：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+6+5+5+6)-(3+4+3)=55e 第一臺用兩年，第二臺用兩年：y=(11+

15、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） 用四臺設(shè)備時：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. 第一臺用一年，第二臺用一年，

16、第三臺用一年：y=(11+12+14+14)+(5+6+5+5+5)-(3+4+4+4)=63（5） 用五臺設(shè)備時：此時只有一種情況：y=(11+12+13+14+14)+(5+5+5+5+5)-(4+4+4+4+4)=69由以上結(jié)果可看出，當(dāng)y=49時取得最小值，即最小的總支出為第一臺使用兩年，在第三年初購買新的設(shè)備能使總支出最小，且最小總支出費(fèi)用為49萬元，這與計(jì)算結(jié)果完全吻合，充分說明了我們所建立的模型的合理性，可行性以及正確性！七、模型的評價及改進(jìn)：本模型理論上可以用于解決任意有關(guān)設(shè)備更新的任何問題，成功的運(yùn)用Dijkstra算法，該算法簡潔明了，適用于無需遍布網(wǎng)絡(luò)中所有點(diǎn)只要求得兩定點(diǎn)的最短路徑，對解決最小總支出是很方便而且優(yōu)越，目前被認(rèn)為是求無負(fù)權(quán)網(wǎng)絡(luò)的最好方法；我們用計(jì)算機(jī)軟件matlab可以成功地求出最小總支出，容易操作，具有實(shí)用性。我們還可以采用其它數(shù)學(xué)軟件通過程序的編寫運(yùn)行來求得最優(yōu)解，如Qsb，C+等，此外，這種算法還可以求從一個城市到另一個城市的最短路徑問題，資金周轉(zhuǎn)問題，聘請員工實(shí)現(xiàn)最優(yōu)化等問題，值得進(jìn)行社會推廣。但是，在本問題的建立過程中