最短路问题解决设备更新

1、蒇最短路问题解决设备更新芄最短路问题是网络理论中应用最广泛的问题之一，许多优化问题可以使用这个模型，如设备更新、 管道铺设、线路安排、厂区布局等。我们学习过最短路问题的动态规划解法，但某些最短路问题（如道路不能整齐分段者）构造动态规划方程比较困难，而图论方法比较有效。薁最短路问题的一般提法如下：设 G=（ V,E）为连通图， 图中各边 （ vi,vj ）有权 lij (l ij=表示 vi,vj 间无边 )，vs,vt为图中任意两点，求一条道路，使它是从 vs 到 vt 的所有路中总权最小的路。即：L（ ） =l ij 最小。羀 (vi ,vj)袇但有些最短路问题也可以是求网络中某指定点到其余

2、所有结点的最短路，或求网络中任意两点间的最短路。羆 解决最短路问题通常有三种解法：Dijkstra( 二次标号 )算法，逐次逼近算法，Floyd 算法。薄 Dijkstra 算法是由Dijkstra 于 1959 年提出，可用于求解指定两点vs， vt 间的最短路径，或从指定点vs 到其余各点的最短路，目前被认为是求无负权网络最短路问题的最好方法。肀 逐次逼近法可用于网络中带有负权的边时，求某指定点v1 到网络中任意点的最短路。芈 Floyd 算法可用于某些问题中，求网络上任意两点间的最短路，这类问题可以用Dijkstra 算法依次改变起点的办法计算，但比较繁琐。莄 在此介绍使用Dijkstr

3、a 算法解决设备更新问题。莃 Dijkstra 算法的基本思路基于以下原理：若序列v s，v1， ， vn-1， vn 是从 vs， vn 的最短路，则序列 v s，v1， ，vn-1 必为从 vs 到 vn-1 的最短路。 Dijkstra 算法的基本步骤，采用标号法。可用两种标号T 标号与 P 标号，T 标号为试探性标号（tentativelabel ），P 为永久性标号（permanentlabel），给 vs 点一个 P 表示从 vs 到 vi 点的最短路权， vi 点的标号不再改变。给vi 点一个 T 标号时，示从vs 到 vi 点的估计最短路权的上界，是一种临时标号，凡没有得到P

4、标号的点都有T 标号。算法每一步都把某一点的T 标号改为P 标号，当终点vt 得到 P 标号时，全部计算结束。对于有n 个顶点的图，最多经n-1 步就可以得到从始点到终点的最短路。肀步骤：虿（ 1）给 vs 以 P 标号， P(vs)=0 ，其余各点均给T 标号， T(v i)=+ 。膆（ 2）若 vi 点为刚得到 P 标号的点，考虑这样的点 vj：(vi,vj)属于 E，且 vj 为 T 标号。对 vj 的 T 标号进行如下的更改：肂 T(v j )=minT(v j),P(vi)+l ij 腿 （ 3）比较所有具有T 标号的点，把最小者改为P 标号，即：螆 P(vi)=minT(v i)薄

5、 当存在两个以上最小者时，可同时改为P 标号。若全部点均为P 标号则停止。否则用vi 代替 vi 转回（ 2）。袁 得知了 Dijkstra 算法的基本思路和基本步骤，下面举个实际应用的例子。艿例： 某工厂使用一台设备，每年年初工厂都要作出决定，如果继续使用旧的，要付维修费；若购买一台新设备，要付购买费。试制订一个5 年的更新计划，使总支出最少。芇若已知设备在各年的购买费，及不同机器役龄时的残值与维修费，如下表所示：第4年第5年芆项目袄第1年荿第2年蚈第3年购买费1112131414机器役龄0112233445维修费5681118残值43210解： 把这个问题化为最短路问题。用点vi 表示第i 年年初购进一台新设备，虚设一个点v6 表示第5 年年底。边（ vi,vj ）表示第i 年初购进的设备一直使用到第j 年年初（即第j 1 年年底）。边（ vi,vj ）上的数字表示第i 年初购进设备，一直使用到第j 年初所需要支付的购买、维修的全部费用（可由表中数据计算得到） 。例如（ v1,v4）边上的28 是第一年初购买费11 加上三年的维修费5， 6， 8，减去 3 年役龄设备的残值2；（