基于最短路径问题在企业设备更新中的应用

1、基于最短路径问题在企业设备更新中的应用摘要：介绍通过应用书本中最短路径的算法，来解决企业中设备的更新换代问题。文中给出了企业设备更新中的数学模型，举例说明了如何更新企业中设备，使得企业的投入最小，即最大限度地减少企业的成本。本例也说明了用数据结构中的算法在解决实际问题中的应用是十分广泛、重要的。关键词：最短路径；Dijkstra算法;企业设备更新1. 问题的提出1.1问题的实质设备更新问题。某企业使用某种设备，在每年的年初，企业领导部门就要决定是购置新的，还是继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用旧设备，则需支付一定的维修费用。现在的问题是如何制定一个几年之内的设备更新

2、计划，使得总的支付费用最少。1.2问题的意义由于现代企业竞争形势的日益严峻，使得企业要降低生产成本，以取得最大限度利润。而生产材料价格的透明化、生产力成本的固定化，迫使企业从生产设备着手来考虑生产成本的问题。设备更新问题，这对一个单位、公司来说是一笔较大的资金，所以如何使设备每年的投入最少，这是一个最短路径问题，该问题可以使用Dijkstra算法来解决。1.3问题的分析在带权连通平面图中求最短路径，是图论的基本问题之一，在实际的工作中具有很重要的意义。对该问题的两个比较典型的算法是Dijkstra算法。由于Dijkstra算法适合于较为复杂的带权连通图，所以在本文中应用了最短路径求解中的Dij

3、kstra算法，来解决如何以最低的代价换取最大的经济利润。2.算法的基本概念2.1 Dijkstra算法基本思想把顶点集V分为两组，令S表示已求出最短路径的顶点集合为第一组，其余尚未确定最短路径的顶点集合T为第二组。初始状态时，集合S中只包含源点V，T中含除源点之外的其余顶点，此时各顶点的当前最短路径长度为源点到该结点的弧上的权值。然后不断从集合T中选取到顶点V路径长度最短的顶点u加入到集合S中，集合S中每加入一个新的u，都要修改顶点V到集合T中剩余顶点的最短路径长度的值，集合T中各顶点新的最短路径长度值为原来的最短路径的值加上u到该顶点的路径长度值中的较小值。重复此过程，直到集合T中的顶点全

4、部加入集合S为止。2.2 Dijkstra算法实现过程假设用带权的邻接矩阵arcs表示带权有向图，arcsij表示弧<vi,vj>上的权值。若<vi,vj>不存在，则置<vi,vj>为(在计算机上可用允许的最大值代替)。S为已找到从v出发的最短路径的终点的集合，它的初始状态为空集。那么，从v出发到图上其余各顶点(终点)vi可能达到的最短路径长度的初值为：Di=arcsLoacate Vex(G,v)i viV。选择vj,使得Dj=MinDi| vV-S，vj就是当前求得的一条从v出发的最短路径的终点，令S=Sj。修改从v出发到集合V-S上任一顶点vk可达的最

5、短路径长度。Dj+arcsjk<Dk，则修改Dk为Dk=Dj+arcsjk。重复操作以上步骤共n-1次。由此求得从v到图上其余各顶点的最短路径。3.分析问题3.1建立数学模型现在用一个简单的数学模型来说明。假设某企业中，我们用一个五年之内要更新某种设备的计划为例来说明，若已知这种设备在每年年初的价格为：年限第1年第2年第3年第4年第5年单价（万元）1111121213使用不同年限的设备所需要的维修费用为：使用年限0112233445维修费用(万元)5681118可供选择的设备更新方案显然是很多的。例如，每年都购置一台新设备，则其购置费用为：11+11+12+12+13=59。而每年支付的

6、维修费用为5，五年合计25。于是五年总的支付费用为59+25=84。又如决定在第1、3、5年各购进一台，这个方案的设备购置费用为：11+12+13=36，维修费用为5+6+5+6+5=27。五年总的支付费用为36+27=63。如何制定方案使得总的支付费用最少呢？可以把这个问题转化为求最短路径问题，见下图，用Vi代表“第i年年初购进一台新设备”这种状态。假设一顶点V6可理解为第五年年底。从Vi，Vi+1，.，V6各画一条弧。弧(Vi，Vj)表示第i年年初购进的设备一直使用到第j年年初(第j-1年年底)。每条弧的权可按已知资料(例如给定的两张表)计算出来。例如(V1，V4)是第1年年初购进设备(支

7、付购置费11)，一直使用到第3年年底(支付维修费5+6+8=19)，故(V1，V4)上的权值为30。进而转化为带权连通图，如下图所示。这样，制定一个最优的设备更新计划的问题就等价于寻求从V1到V6的最短路径问题。3.2算法设计思想首先设两个集合，S是最短距离已经确定的V中的顶点集；T=V-S是最短距离尚未确定的顶点集。将第1年年初V1视为设备更新的起点，先把V1计入一个集合S中，从V1开始，遍历其余顶点寻找最短路径。此时与V1相连的5个顶点中，路径最短的为V1到V2的距离，所以将V2计入集合S内，然后从S中的所有顶点出发，寻找下一个路径最短且顶点不在集合S中的顶点。即在V-S中选minDi=K

8、(iV-S),将K加入S中：S=SK，T=T-K。调整Dn中各顶点的最短距离Dj：若Dj>DK+W(K, j),则Dj=DK+W(K,j)，否则不改变Dj的原来值。若T=V-S为空，或T=V-S中顶点的Dj全为终止，否则继续。3.3算法实现输入：顶点数；各顶点之间的路径值。输出：最优方案，包括起始顶点、中间顶点、终止顶点及顶点之间的路径值之和。方法：SN为布尔向量，当i号顶点纳入时Si=TRUE；Di初值为源点s到其它各顶点的直接距离。1）输入顶点数：6；2）再输入边数：15；3）然后输入每条边的起点、终点及对应权值；4）最后输入源点序号。此过程为一个程序，其功能是：输入n年年初设备的价

9、格与使用不同时间（年）的设备所需要的维修费用，为该企业领导部门确定一个方案使得在n年内为这台机器支付的总费用最少。3.4运行结果及说明最后求得V1，V3，V6及V1，V4，V6均为最短路径。即有两个最优方案：一个方案是第1年、第3年各购置一台新设备。4.计算复杂度分析通过该算法编写的程序已经在Microsoft Visual C+6.0的运行环境下编译通过，并运行成功，得出的结果与预期的相同，有两条备选方案。第一个循环的时间复杂度是O(n)，第二个循环共进行n-1次，每次执行的时间是O(n)。所以总的时间复杂度是O(n2)。如果用带权的邻接表作为有向图的存储结构，则显然修改D的时间可以减少，但

10、由于在D向量中选择最小分量的时间不变，所以总的时间仍为. O(n2)。5.结语Dijkstra算法总是做出在当前看来最好的选择，也就是说该算法并不是从整体上的最优考虑，它做出的选择只是在某种意义上的局部最优选择，但最终能得到整个问题的最优解。Dijkstra算法不仅仅应用于企业设备更新问题，还可应用于其他很多地方，例如：网线和电线的辅设、管道的辅设等，用此算法都可以得到最优的布线路径，达到省时、省料、省力的目的。从此算法也可以看出，Dijkstra算法在现实生活中的应用是十分广泛的。参考文献:1严蔚敏，吴伟民.数据结构题集（C语言版）M.北京：清华大学出版社，1997.2谭浩强.C语言程序设计（第二版）M.北京：清华大学出版社， 2000.3余祥宣，崔国华，邹海明.计算机算法基础（第二版）M.武汉：