基于最短路問題的最優設備更新與維修方案

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

關鍵詞：最短路徑；圖論；設備更新； 算法

【前言】

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

【問題分析】

本問題屬于最短路徑問題。最短路徑問題是指若網絡中每條邊都有一個數值（長度、成本、時間等），則找出兩節點（通常是源節點和阱節點）之間總權和最小的路徑就是最短路徑問題。

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

【問題求解】

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

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

表1 設備 1 每年年初價格（萬元）

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

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

表1 設備 1

利用 Dijkstra 算法以及以上所求數據即可求出最短路徑以及最優化的方案：設備一：第一年年初購買設備，第六年年初更新至第十年結束。

設備二：第一年年初購買設備，第六年年初更新至第十年結束。

設備三：第一年年初購買設備，第六年年初更新至第十年結束。

設備四：第一年年初購買設備，第五年年初更新至第十年結束。

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

參考文獻：

[1]徐俊明.圖論及其應用[M].北京：中國科學技術大學出版社，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月出生，河南南陽人，本科生，信息與計算科學專業。