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

1、第 1 頁 共 4 頁最短路法解決設(shè)備更新問題 最短路法解決設(shè)備更新問題某工廠使用一臺設(shè)備，每年年初工廠都要作出決定，如果繼續(xù)使用舊的，要付維修費(fèi)；若購買一臺新設(shè)備，要付購買費(fèi)。試制定一個五年的更新計劃，使總支出最少。已知設(shè)備在各年的購買費(fèi)，及不同機(jī)器役齡時的殘值與維修費(fèi)，如下表所示。項(xiàng)目 第一年 第二年 第三年 第四年 第五年購買費(fèi) 11 12 13 14 14機(jī)器役齡 0—1 1—2 2—3 3—4 4—5維修費(fèi) 5 6 8 11

2、18殘值 4 3 2 1 0二、模型假設(shè)： 二、模型假設(shè)：1、機(jī)器在購買 N 年之后維修費(fèi)用是固定不變的，不存在人為的破壞因素使之不能正常運(yùn)行；2、公司有足夠的資金支付設(shè)備；3、公司該設(shè)備只使用一臺，不存在公司同時用多臺機(jī)器的現(xiàn)象4、從第一年開始一定要購置一臺設(shè)備三、符號說明： 三、符號說明：1、vi 表示第 i 年年初購進(jìn)一臺新設(shè)備，虛設(shè)一個點(diǎn) v6，表示第五年年底；2、邊（vi，vj）表示第 i 年初購進(jìn)的設(shè)備一直使用到第 j 年初

3、（即第 j-1 年底） ；3、邊（vi，vj）上的數(shù)字表示第 i 年初購進(jìn)設(shè)備，一直使用到第 j 年初所需支付的購買、維修的全部費(fèi)用四、問題的分析： 四、問題的分析：為了使問題簡化，我們將求最小總支出轉(zhuǎn)化為求最小路徑問題，這樣，設(shè)備更新問題可簡化為求從 v1 到 v6 的最短路問題，可由上表得下圖第 3 頁 共 4 頁（2）由于（v1，v2） ， （v1，v3）,（v1，v4）,（v1，v5）,（v1，v6）邊屬于 E，且 v1，v2

4、為 T 標(biāo)號，所以修改這兩個點(diǎn)的標(biāo)號：T(v2)=min[T(v2),P(v1)+l12]=min[+∞,0+12]=12 T(v3)=min[T(v1),P(v3)+l13]=min[+∞,0+19]=19 T(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[

5、+∞,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，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]=2

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

7、40，19+21]=40 T(v6)=min[T(v3),P(v3)+l36]=min[53，19+30]=53（7）比較所有 T 標(biāo)號，T(v4)最小，所以令 P(v4)=28.并記錄路徑（v1，v4） 。（8）考慮點(diǎn) 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 標(biāo)號，T(v5)最

8、小，所以令 P(v5)=40.并記錄路徑（v1，v5） 。（10）考慮點(diǎn) v6，有T(v6)=min[T(v6),P(v5)+l56]=min[49,40+15]=49（11）因只有一個 T 標(biāo)號 T(v6),令 P(v6)=49，記錄路徑（v3，v6） ，計算結(jié)束。由計算結(jié)果可知：v1 v3 v6 為最短路，路長為 49，即在第一年，第三 年初各購買一臺新設(shè)備為最優(yōu)決策，這時 5 年的總費(fèi)用為 49.全部計算結(jié)果如下圖