基于最短路问题的最优设备更新与维修方案

摘要：本文是设备更新与维修的方案优化问题.通过参考题目表格中所给的六年之内每台设备每年的价格以及使用不同时间所需维修费用，对每台设备在不同时间价格以及使用不同时间所需维修费用通过最短路问题进行分析，得到了四台设备更新维修的最佳方案。针对此案例，使用了图论和 算法。题目中给出了前六年设备更新维修的数据，通过拟合和线性回归的方法，预测得出第六年至第十年间的设备更新维修的数据，再利用问题一的方法，做十年的加权有向图，采用 算法，求出各设备最短路径，综合得出最优方案：设备一：第一年年初购买设备，第六年年初更新至第十年结束。设备二：第一年年初购买设备，第六年年初更新至第十年结束。设备三：第一年年初购买设备，第六年年初更新至第十年结束。设备四：第一年年初购买设备，第五年年初更新至第十年结束。此时所需支付总费用为 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月出生，河南南阳人，本科生，信息与计算科学专业。