摘要：本文是設(shè)備更新與維修的方案優(yōu)化問題.通過參考題目表格中所給的六年之內(nèi)每臺設(shè)備每年的價(jià)格以及使用不同時(shí)間所需維修費(fèi)用，對每臺設(shè)備在不同時(shí)間價(jià)格以及使用不同時(shí)間所需維修費(fèi)用通過最短路問題進(jìn)行分析，得到了四臺設(shè)備更新維修的最佳方案。針對此案例，使用了圖論和 算法。題目中給出了前六年設(shè)備更新維修的數(shù)據(jù)，通過擬合和線性回歸的方法，預(yù)測得出第六年至第十年間的設(shè)備更新維修的數(shù)據(jù)，再利用問題一的方法，做十年的加權(quán)有向圖，采用 算法，求出各設(shè)備最短路徑，綜合得出最優(yōu)方案：設(shè)備一：第一年年初購買設(shè)備，第六年年初更新至第十年結(jié)束。設(shè)備二：第一年年初購買設(shè)備，第六年年初更新至第十年結(jié)束。設(shè)備三：第一年年初購買設(shè)備，第六年年初更新至第十年結(jié)束。設(shè)備四：第一年年初購買設(shè)備，第五年年初更新至第十年結(jié)束。此時(shí)所需支付總費(fèi)用為 685.19 萬元，為最少費(fèi)用。

關(guān)鍵詞：最短路徑；圖論；設(shè)備更新； 算法

【前言】

企業(yè)使用一條由四臺設(shè)備組成的生產(chǎn)線，每年年初由企業(yè)領(lǐng)導(dǎo)決定每臺設(shè)備是購置新的還是繼續(xù)使用。若購置新設(shè)備，則需支出一定的購置費(fèi)用，若繼續(xù)使用，則需要支付一定的維修費(fèi)用。查找資料分別得到了四臺設(shè)備，每年年初的價(jià)格以及使用不用時(shí)間所需要的維修費(fèi)用。預(yù)測并制定該生產(chǎn)線十年之內(nèi)的最優(yōu)設(shè)備更新與維修方案。

【問題分析】

本問題屬于最短路徑問題。最短路徑問題是指若網(wǎng)絡(luò)中每條邊都有一個(gè)數(shù)值（長度、成本、時(shí)間等），則找出兩節(jié)點(diǎn)（通常是源節(jié)點(diǎn)和阱節(jié)點(diǎn)）之間總權(quán)和最小的路徑就是最短路徑問題。

單源采用三種方法：①利用曲線擬合的方法，通過擬合題目所提供的數(shù)據(jù)信息，做出圖像，得出每臺設(shè)備每年更新價(jià)格以及使用不同時(shí)間所需維修費(fèi)用的大致趨勢。②利用回歸分析的方法，預(yù)測題目所需的第六到十年間每臺設(shè)備每年更新價(jià)格以及使用不同時(shí)間所需維修費(fèi)用，做出圖表。③利用問題一中圖論和 的方法對十年間的數(shù)據(jù)進(jìn)行最短路分析，制定該生產(chǎn)線十年之間的最優(yōu)設(shè)備更新與維修方案。

【問題求解】

查閱提供的數(shù)據(jù)，通過擬合的方法做出近似函數(shù)圖像。易知年限與設(shè)備價(jià)格以及使用不同時(shí)間所需的設(shè)備維修費(fèi)用為一次線性關(guān)系，為預(yù)測第六年至第十年間設(shè)備價(jià)格以及使用不同時(shí)間設(shè)備所需維修費(fèi)用，可以通過線性回歸分析的方法，假設(shè) ，用試驗(yàn)值即樣本點(diǎn)對回歸系數(shù)a，b做點(diǎn)估計(jì)，再對a，b假設(shè)檢驗(yàn)，然后再 處對y進(jìn)行估計(jì)從而估計(jì)出來y的值[1]。然后運(yùn)用圖論和 的方法，推測得出十年之間所需支付總費(fèi)用最少的設(shè)備維修與更新方案。（以后均以設(shè)備一為例）。

根據(jù)本題以上的理論分析，利用回歸分析理論與擬合理論可分別推測出第七到十年四臺設(shè)備各自所需要的更新以及維修費(fèi)用（見如下表）：

表1 設(shè)備 1 每年年初價(jià)格（萬元）

由題意和所得到的數(shù)據(jù)信息，由此可推出本題加權(quán)有向圖的頂點(diǎn)數(shù)為11，根據(jù)頂點(diǎn)計(jì)算邊數(shù)公式可得，該問一共有55條邊，可得加權(quán)有向圖：

根據(jù)本題所提供的更新以及維修的費(fèi)用的數(shù)據(jù)信息，分別求出各個(gè)頂點(diǎn)的權(quán)值。以設(shè)備一為例，假設(shè)設(shè)備一第 年進(jìn)行更新，使用到第j年，其（i，j）的權(quán)值為第i年的更新價(jià)格加上前j-i年的維修費(fèi)用之和。

表1 設(shè)備 1

利用 Dijkstra 算法以及以上所求數(shù)據(jù)即可求出最短路徑以及最優(yōu)化的方案：設(shè)備一：第一年年初購買設(shè)備，第六年年初更新至第十年結(jié)束。

設(shè)備二：第一年年初購買設(shè)備，第六年年初更新至第十年結(jié)束。

設(shè)備三：第一年年初購買設(shè)備，第六年年初更新至第十年結(jié)束。

設(shè)備四：第一年年初購買設(shè)備，第五年年初更新至第十年結(jié)束。

此時(shí)所需支付總費(fèi)用為 685.19 萬元，為最少費(fèi)用。

參考文獻(xiàn)：

[1]徐俊明.圖論及其應(yīng)用[M].北京：中國科學(xué)技術(shù)大學(xué)出版社，2010：1-22.XU Junming.Graph Theory with Applica

tions[M].Beijing：University of Science and Technology

of China

[2]施泉生.運(yùn)籌學(xué)[M].北京：中國電力出版社，2008：177-

179. SHI QUANSHENG.Operational Research[M].Beijing：

China Electric Power Press，2008：177-179

作者簡介：路雯涵，女，1995年12月出生，河南南陽人，本科生，信息與計(jì)算科學(xué)專業(yè)。