基于最短路問題的最優(yōu)設(shè)備更新與維修方案

摘要：本文是設(shè)備更新與維修的方案優(yōu)化問題.通過參考題目表格中所給的六年之內(nèi)每臺設(shè)備每年的價格以及使用不同時間所需維修費用，對每臺設(shè)備在不同時間價格以及使用不同時間所需維修費用通過最短路問題進行分析，得到了四臺設(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é)束。此時所需支付總費用為 685.19 萬元，為最少費用。

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

【前言】

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

【問題分析】

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

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

【問題求解】

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

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

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

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

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

表1 設(shè)備 1

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

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

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

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

此時所需支付總費用為 685.19 萬元，為最少費用。

參考文獻：

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

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

of China

[2]施泉生.運籌學[M].北京：中國電力出版社，2008：177-

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

China Electric Power Press，2008：177-179

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