數(shù)學(xué)建模-設(shè)備更新問題_第1頁
數(shù)學(xué)建模-設(shè)備更新問題_第2頁
數(shù)學(xué)建模-設(shè)備更新問題_第3頁
數(shù)學(xué)建模-設(shè)備更新問題_第4頁
數(shù)學(xué)建模-設(shè)備更新問題_第5頁
已閱讀5頁,還剩8頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

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)行社會推廣。但是,在本問題的建立過程中

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論