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

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

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

3、用多臺(tái)機(jī)器的現(xiàn)象4、從第一年開始一定要購(gòu)置一臺(tái)設(shè)備三、符號(hào)說明：1、Vi表示第i年年初購(gòu)進(jìn)一臺(tái)新設(shè)備，虛設(shè)一個(gè)點(diǎn)V6，表示第五年 年底；2、 邊（Vi，Vj）表示第i年初購(gòu)進(jìn)的設(shè)備一直使用到第j年初（即 第j-1年底）；3、 邊（Vi，Vj ）上的數(shù)字表示第i年初購(gòu)進(jìn)設(shè)備，一直使用到第j年初所需支付的購(gòu)買、維修的全部費(fèi)用 四、問題的分析：為了使問題簡(jiǎn)化，我們將求最小總支出轉(zhuǎn)化為求最小路徑問題，這樣，設(shè)備更新問題可簡(jiǎn)化為求從 V1到V6的最短路問題，可由上表得下對(duì)于邊（Vi， V2）有第一年購(gòu)買的費(fèi)用11加上一年的維修費(fèi)用5減去一年役齡機(jī)器的殘值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 算法將設(shè)備更新的問題算出最小總支出五、模型的建立與求解：

5、由上述分析可知 Dijkstra 算法中所對(duì)應(yīng)的結(jié)點(diǎn)跟路徑， 下面給出其基本步驟：采用標(biāo)號(hào)法，用兩種標(biāo)號(hào)：T標(biāo)號(hào)和P標(biāo)號(hào)，T標(biāo)號(hào)為試 探性標(biāo)號(hào)，P標(biāo)號(hào)為永久性標(biāo)號(hào)，給Vi 個(gè)P標(biāo)號(hào)時(shí)表示從Vi到Vj 的最短路權(quán)， vi 的標(biāo)號(hào)不再改變。給 vi 一個(gè) T 標(biāo)號(hào)是表示從 vi 到 Vj的最短路權(quán)的上界，是一種臨時(shí)標(biāo)號(hào)，凡沒有得到 P標(biāo)號(hào)的點(diǎn)都 有T標(biāo)號(hào)。（1）首先給Vi以P（Vi）=0，給其余所有點(diǎn)T標(biāo)號(hào)，T（vi）=+ 乂（ i=2，8）（2）由于（ Vi，V2）， （Vi，V3） ,（Vi，V4） ,（Vi，V5） ,（Vi，V6）邊屬于E,且Vi, V2為T標(biāo)號(hào)，所以修改這兩個(gè)點(diǎn)的標(biāo)號(hào)：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標(biāo)號(hào)，T(V2)最小，所以令P(V2)=12.并記錄路徑 (V1，V2)。(4) V2為剛得到P標(biāo)號(hào)的點(diǎn)，考察邊(V2, V3), ( V2 , V3), ( V2

7、 , V4), ( V2，V5)，( V2，V6)的端點(diǎn) 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 標(biāo)號(hào)， T(V3) 最小，所以令 P(V3)=19. 并記錄路徑 (V1， V3)。(6) 考慮點(diǎn)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 標(biāo)號(hào)， T(V4) 最小，所以令 P(V4)=28. 并記錄路徑第 8 頁 共 13 頁(Vi, V4 )。(7) 考慮點(diǎn)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標(biāo)號(hào)，T(V5)最小，所以令P(V5)=

9、40.并記錄路徑 (Vi，V5 )。(9) 考慮點(diǎn)V6,有T(V6)=minT( V6),P( V5)+ l 56=min49,40+15=49(10) 因只有一個(gè)T標(biāo)號(hào)T(V6),令P(V6)=49，記錄路徑(V3，V6)，計(jì)算結(jié)束。由計(jì)算結(jié)果可知：Vi L 3 6為最短路，路長(zhǎng)為49,即 在第一年，第三年初各購(gòu)買一臺(tái)新設(shè)備為最優(yōu)決策，這時(shí) 5年的總費(fèi)用 為49.全部計(jì)算結(jié)果如下圖所示，同時(shí)可得到Vi到其他點(diǎn)的最短路徑，如下圖中的粗線所示：Matlab的編程語言如下：關(guān)于求最小路徑的 M函數(shù)fun cti onS,D=mi nRoute(i,m,W,opt)%圖與網(wǎng)絡(luò)論中秋最短路徑的Dijk

10、stra算法M函數(shù)%格式S,D=minroute(I,m,W,opt)%i為最短路徑的起始點(diǎn)， m為圖定點(diǎn)數(shù) W為圖的帶權(quán)鄰接矩陣 不構(gòu)成邊的兩頂點(diǎn)之間的權(quán)用 inf表示.S的每一列從上到下記 錄了從始點(diǎn)到終點(diǎn)的最短路徑所經(jīng)頂點(diǎn)的序號(hào).opt(缺省值)時(shí),S按最短路徑值從小到大顯示結(jié)果 .%D是一行向量，對(duì)應(yīng)記錄了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利用此函數(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

13、,21,30;>> w(4,5,6)=15,22;>> w(5,6)=15;>> s,d=minroute(1,n,w)求解所得結(jié)果：s =1111110234530000060 12 19 28 40 49六、模型的檢驗(yàn)利用常規(guī)數(shù)學(xué)方法求解此題如下： 由題意可知，五年下來最多能每一年用五臺(tái)，最少要用一 臺(tái)機(jī)器，設(shè)總共所用的支出為 y ，( 1) 只用一臺(tái)設(shè)備時(shí)： y=11+5+6+8+11+18=59(2) 用兩臺(tái)設(shè)備時(shí)：a. 第一臺(tái)使用一年：y=(11+13)+(5+6+5+6+8+11)-(3+2)=53b. 第一臺(tái)使用兩年： y=(11+13)+(5

14、+6+5+6+8)-(3+2)=49c. 第一臺(tái)使用三年： y=(11+14)+(5+6+8+5+6)-(2+3)=50d. 第一臺(tái)使用四年：y=(11+14)+(5+6+8+11+5)-(1+4)=55(3) 用三臺(tái)設(shè)備時(shí)：a.第一臺(tái)用一年，第二臺(tái)用一年：y=(11+12+13)+(5+5+5+6+8)-(4+4+4+2)=55b 第一臺(tái)用一年，第二臺(tái)用兩年： y=(11+12+14)+(5+5+6+5+6)-(4+3+3)=54C.第一臺(tái)用一年，第二臺(tái)用三年：y=(11+12+14)+(5+5+6+8+5)-(4+2+4)=56d 第一臺(tái)用兩年，第二臺(tái)用一年：y=(11+13+14)+(5

15、+6+5+5+6)-(3+4+3)=55e. 第一臺(tái)用兩年，第二臺(tái)用兩年：y=(11+13+14)+(5+6+5+6+5)-(3+3+4)=55f. 第一臺(tái)用三年，第二臺(tái)用一年：y=(11+14+14)+(5+6+8+5+5)-(4+3+3)=584) 用四臺(tái)設(shè)備時(shí)：a. 第一臺(tái)用一年，第二臺(tái)用一年，第三臺(tái)用一年：y=(11+12+13+14)+(5+5+5+5+6)-(4+4+4+3)=61b. 第一臺(tái)用一年，第二臺(tái)用一年，第三臺(tái)用兩年：y=(11+12+13+14)+(5+5+5+6+5)-(4+4+3+4)=61C. 第一臺(tái)用一年，第二臺(tái)用兩年，第三臺(tái)用一年：y=(11+12+14+14

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