Dijkstra模型的建立及求解设备更新问题(图解法).doc

一、问题分析为了求解出寝室电风扇更新问题，即了解到总费用最低为最终依据来判定是否更新。根据收集的资料将最小费用化为最短路问题这样设备更新问题可以简化为求最短路问题。由资料表可得下图：(V1 , V2): 5 + 54 = 59;(V1, V3): 5 + 54 +12 = 71;(V1, V4): 5 + 54 + 12 + 15 = 86;(V1, V5): 5 + 54 + 12 + 15 + 20 = 106;(V1, V6): 5 + 54 + 12 + 15 + 20 + 23 = 129; (V1，V7): 5 + 54 + 12 + 15 + 20 + 23 + 28 = 157;(V2, V3): 60 + 12 =72;(V2, V4): 60 + 12 +15 = 87;(V2, V5): 60 + 12 +15 + 20 = 107;(V2, V6): 60 + 12 +15 + 20 + 23 = 130;(V2, V7): 60 + 12 +15 + 20 + 23 + 28 = 158;(V3,V4): 60 + 15 = 75;(V3,V5): 60 + 15 + 20 = 95;(V3,V6): 60 + 15 + 20 + 23 = 118;(V3 ,V7): 60 + 15 + 20 + 23 + 28 = 146;(V4,V5): 80 + 20 = 100;(V4, V6): 80 + 20 + 23 = 123;(V4,V7): 80 + 20 + 23 + 28 =151;(V5,V6): 80 + 23 =103;(V5 ,V7): 80 + 23 + 28 = 131;(V6,V7): 83 + 28 =111;二、符号说明用点vi表示第i年年初购进一台新电扇，加设v7表示第6年年底。从vi到v7各画一条弧（vi, v j）表示第i 年年初购进的设备一直使用到第j年年初，即j-1年底。弧(vi, v j)的权数即从第i年年初购进设备使用到第j-1年初的更新费用及维修费用之和。三、模型的建立及求解根据Dijkstra算法，采用双标号计算：T标号与P标号，T标号为试探性标号，P标号为永久性标号，给vi一个p表示从vs到vi点的最短路权，vi点的标号不再改变。给vi点一个T标号时，表示从vs到vi点的估计最短路权的上界，是一种临时标号，凡是没有得到P标号的点都有T标号。算法的每一步都把某一点的T标号改为P标号，当终点v t得到P标号时，全部计算结束。对于n 个顶点的图，最多经n-1 步就可以得到从始点到终点的最短路。步骤：（1） 给vs 以P 标号，P(vs) = 0,其余均给T标号，T(vi) = +。（2） 若vi点为刚得到的P标号的点，考虑这样的点 v j :(vi, v j)属于E，且v i 为T标号。对v j 的T标号进行如下的更改： T（v j）= minT(v j), P(vi) + li j;（3） 比较所有具有T标号的点，把最小者改为P标号，即 P(vi) = minT(vi);当存在两个以上最小者时，同时改为P标号，若全部点均为P标号则停止，否则转回（2）。求解如下：1、 首先给v1以P标号，P（v1）= 0,给其余所有点T标号：T(vi) = + (i=2,. ,7)2、 (v1, v2), (v1, v3),(v1,v4),(v1 ,v5),(v1, v6), (v1, v7)都属于E，分别检验各端点v2 ,v3, v4, v5, v6, v7.T(v2) = minT(v2),P(v1) + L12 = min+, 59 = 59;T(v3) = minT(V3), P(v1) + L13= min+,71 = 71;T(v4) = minT(v4), P(v1) + L14 = min+,86 = 86;T(v5) = minT(v5), P(v1) + L15 = min+, 106 = 106;T(v6) = minT(v6), P(v1) + L16 = min+, 129 = 129;T(v7) = minT(v7) , P(v1) + L17= min+,157 = 157;比较各个T标号，T(v2) = 59最小，给v2以P标号，即P(v2) = 59,记录路径（v1, v2）.3、 （v2, v3）,（v2, v4）,（v2, v5）,（v2, v6）, (v2, v7)都属于E，分别检查各端点v3, v4, v5, v6, v7.T(v3)= minT(V3), P(v2) + L23 = min71, 59 + 72 = 71;T(v4) = minT(v4), P(v2) + L24= min86, 59 + 87 = 86;T(v5) = minT(v5), P(v2) + L25 = min106, 59 + 107 = 106;T(v6) = minT(v6), P(v2) + L26 = min129, 59 + 130 = 129;T(v7) = minT(v7) ,P(v2) + L27 = min157, 59 + 158 = 157;比较各个T标号，T(v3)= 71最小，给v3以P标号，即P(v3) = 71,记录路径（v1, v3）。4、 （v3, v4）,（v3, v5）,（v3, v6）,（v4, v7）都属于E，分别检验各端点v4, v5, v6, v7.T(v4) = minT(v4), P(v3) + L34 = min86, 71 + 75 = 86;T(v5) = minT(v5), P(v3) + L35 = min106, 71 + 95 = 106;T(v6) = minT(v6), P(v3) + L36= min129, 71 + 118 = 129;T(v7) = minT(v7) ,P(v3) + L37= min157, 71 + 146 = 157;比较各T标号，T(v4)=86最小。给v4以P标号，即：P（v4）=86，（v1,v4）(v4,v5)(v4,v6)(v4,v7)属于E，检验各端点。T(v5)=minT(v5),P(v4)+L45=min106,86+100=106T(v6)=minT(v6),P(v4)+L46=min129,86+123=129T(v7)=minT(v7),P(v4)+L47=min157,86+151=157比较各T标号，T（v5）=106最小，P（v5）=106,记录路径（v1,v5）。5、检验端点v6, v7。T(v6)=minT(v6),P(v5)+L56=min129,106+103=129T(v7)=minT(v7),P(v5)+L57=min157,106+131=137比较各T标号，T（v6）=129最