《运筹学》课程授课教案（讲稿）第17讲 最短路举例

课程名称：《运筹学》第_17_讲次1、最短路逐次逼近法授课题目2、最短路举例本讲目的要求及重点难点：【目的要求】通过本讲课程的学习，掌握最短路逐次逼近法，对于一些实际应用问题会建立最短路模型分析求解。【重点及难点】最短路逐次逼近法。内容[本讲课程的引入]Dijkstra算法只适用全部权为非负的情况，如果某边上权为负的，此算法不能使用，因此我们学习逐次逼近法。[本讲课程的内容]2、逐次逼近法算法的基本思路与步骤：首先设任一点v,到任一点v,都有一条弧，如果在图G中，(vi，V,)A，则添加弧(v,，V)并令=+0。显然，从v到v,的最短路是从v,出发，沿着这条路到某个点v，再沿弧(v，)到,。则v到,的这条路必然也是,到v,的最短路。否则，从,到,的这条路将不是最短的。于是，设P,表示从到v,的最短路长，P,表示从到v,的最短路长，则有下列方程：P, = min(P: +1,)利用如下的递推公式：开始时，令Pd"=lj(j =1,2,,n)即用v到v，的直接距离做初始解。从第二步起，使用递推公式：P() = min[P(-1) +1,](k=2,3,,n)

课程名称：《运筹学》 第 17 讲次 授课题目 1、最短路逐次逼近法 2、最短路举例 本讲目的要求及重点难点： 目的要求] 通过本讲课程的学习，掌握最短路逐次逼近法，对于一些实际应用问题会建 立最短路模型分析求解。 [重点及难点] 最短路逐次逼近法。 内 容 [本讲课程的引入] Dijkstra 算法只适用全部权为非负的情况，如果某边上权为负的，此算法不能使用， 因此我们学习逐次逼近法。 [本讲课程的内容] 2、逐次逼近法 算法的基本思路与步骤： 首先设任一点 i v 到任一点 j v 都有一条弧，如果在图 G 中， (vi , v j ) A ，则添加弧 ( , ) i j v v ， 并令 l i j  。 显然，从 1 v 到 j v 的最短路是从 1 v 出发，沿着这条路到某个点 i v ，再沿弧 ( , ) i j v v 到 j v 。则 1 v 到 i v 的这条路必然也是 1 v 到 i v 的最短路。否则，从 1 v 到 j v 的这条路将不是最短的。于是，设 P1 j 表示 从 1 v 到 j v 的最短路长， P1i 表示从 1 v 到 i v 的最短路长，则有下列方程： min{ } 1 1i i j i j P  P  l 利用如下的递推公式： 开始时，令 ( 1,2, , ) 1 (1) P1 j  l j j   n 即用 1 v 到 j v 的直接距离做初始解。 从第二步起，使用递推公式： P Pi k l i j （k n） i k j min[ ] 2 , 3, , ( 1) 1 ( ) 1     

内容求P()，当进行到第步，若出现P() = P(-1)(j=1,2,",n)则停止计算，P（j=1,2,,n）即为>到各点的最短路长。例8.8求图8-15中v到各点的最短路解利用上面的递推公式4将计算结果列出，如表8一1所示，图8——15表8——1计算过程表终点biPlP(2PISP始点VVsVV2V3V6V7Vs0Vi-230000-126-5-5-32S-2138V4023-7-71-1V's-3107V61105-1-5V75-5-3Vs6可以看出，当1=4时，有：P(4)=P(3（j=1,2，,8)，因此，表中的最后一列，就是从到，2，…，"的最短路权(表中没有数字的空格表示+）。为了求出从到各个点的最短路，一般采用反向追踪的方法：如果已知P,，那么寻求一个点"，使得Ps+lk,=Py，然后记录下（v）.再看Pis，寻求一个点Vi，使得Pi+li=Pik，，依次类推，一直到达为止。这样，从到的最短路是（y，…，Vi，Vh，y)。在本例中，由表8—1知，Ps=6。由于Pi6+16s=(-1)+7，记录下%。由于Ps+1%6=P，记录下。由于P+3=Pi3，于是，从到vg的最短路是（

内 容 求 ( ) 1 k P j ，当进行到第 t 步，若出现 P1 ( j t)  P1 ( j t1) （j 1, 2 ,  , n） 则停止计算， P1 ( j t)（j 1, 2 ,  , n） 即为 1 v 到各点的最短路长。 例 8.8 求图 8—15 中 1 v 到各 点的最短路 解 利用上面的递推公式， 将计算结果列出，如表 8—1 所示。 表 8——1 计算过程表 终点 始点 li j (1) P1 j (2) P1 j (3) P1 j (4) P1 j v1 v2 v3 v4 v5 v6 v7 v8 v1 0 －1 －2 3 0 0 0 0 v2 6 0 2 －1 －5 －5 －5 v3 －3 0 －5 1 －2 －2 －2 －2 v4 8 0 2 3 －7 －7 －7 v5 －1 0 1 －3 －3 v6 1 0 1 7 －1 －1 －1 v7 －1 0 5 －5 －5 v8 －3 －5 0 6 6 可以看出，当 t =4 时，有： ( 1,2 , ,8) (3) 1 (4) P1 j  P j j   ，因此，表中的最后一列， 就是从 v 1 到 v 1，v 2 ，.，v8的最短路权(表中没有数字的空格表示+∞) 。为了求出从 v1 到各个点的最短路，一般采用反向追踪的方法：如果已知 P1 j ,那么寻求一个点 v k ,使得 k k j P j P l 1   1 ,然后记录下(v k , v j ).再看 P1k ,寻求一个点 i v ，使得 i ik Pk P l 1   1 ，.，依 次类推，一直到达 v 1为止。这样，从 v 1到 vj 的最短路是（v 1 , .，vi ,，vk ,，vj）。 在本例中，由表 8—1 知， P18  6 。由于 P16  l 68  (1)  7 ，记录下 v 6。由于 13 36 P16 P  l  ,记录下 v 3。由于 11 13 P13 P  l  ,于是，从 v 1到 v 8的最短路是(v 1，v 3，v 6， v 8 )。 7 3 －1 8 v1 v2 v3 v4 v5 －2 6 －3 －5 －1 －3 －5 2 1 －1 2 1 1 v6 v7 v8 图 8——15

内容对于递推公式中的P(的实际意义为：从到,点，最多含有k-1中间点的最短路权，所以在含有n个点的图中，如果不含有总权小于零的回路，求从到任一点的最短路权，用上述算法最多经过n一1次选代必定收敛。如果图中含有总权小于零的回路，则可能某些最短路权没有下界。最短路的应用：例8.9某工厂使用一种设备，这种设备在一定的年限内随着时间的推移逐渐损坏。所以工厂在每年年初都要决定设备是否更新。若购置设备，每年需支付购置费用；若继续使用旧设备，需要支付维修与运行费用，而且随着设备的老化会逐年增加。计划期（五年）内中每年的购置费、维修费与运行费如表8一2所示，工厂要制定今后五年设备更新计划，问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。这个问题可以转化为图的问题，考虑六个节点vi、V2、V3、V4、Vs、V6，其中v（i=12，3，4，5）表示在第i年初要购置新设备。节点是虚设点，表示第五年的年底才购置新设备。再从点w（i=1,2,3，4,5)引出指向v1，V+2，，的弧，弧（vi，）表示第i年年初购进的新设备一直使用到第j年（(j=2，3，4，5，6)的年初。弧（vi，）上所赋的权为第i年的购置费加上从第i年初使用到第j年初的维修费用的总和。这样，我们得到一个赋权的有向图G，见图8一16。于是，问题就变为用最短路问题来求解。表8一—2计划期内费用表年份/23451820212324购置费0134使用年数1-22-34-557维修费12182585604042302830V4Vs2628252946324462图8—16

内 容 对于递推公式中的 ( ) 1 k P j 的实际意义为：从 v 1到 vj 点，最多含有 k 1 中间点的最短路 权，所以在含有 n 个点的图中，如果不含有总权小于零的回路，求从 v 1 到任一点的最短路 权，用上述算法最多经过 n 1 次迭代必定收敛。如果图中含有总权小于零的回路，则可能 某些最短路权没有下界。 最短路的应用： 例 8.9 某工厂使用一种设备，这种设备在一定的年限内随着时间的推移逐渐损坏。 所以工厂在每年年初都要决定设备是否更新。若购置设备，每年需支付购置费用；若继续 使用旧设备，需要支付维修与运行费用，而且随着设备的老化会逐年增加。计划期（五年） 内中每年的购置费、维修费与运行费如表 8—2 所示，工厂要制定今后五年设备更新计划， 问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。 这个问题可以转化为图的问题，考虑六个节点 v1、v2、v3、v4、v5、v6，其中 vi (i = 1 , 2 , 3 , 4 , 5 ) 表示在第 i 年初要购置新设备。节点 v 6是虚设点，表示第五年的年底才购置新 设备。再从点 vi (i = 1 , 2 , 3 , 4 , 5 )引出指向 vi+1，vi+2，┅，v 6 的弧，弧（vi , vj）表示第 i 年年初购进的新设备一直使用到第 j 年（(j = 2 , 3 , 4 , 5，6)的年初。弧（vi , vj）上所赋 的权为第 i 年的购置费加上从第 i 年初使用到第 j 年初的维修费用的总和。这样，我们得到 一个赋权的有向图 G，见图 8—16。于是，问题就变为用最短路问题来求解。 表 8——2 计划期内费用表 年份 1 2 3 4 5 购置费 18 20 21 23 24 使用年数 0—1 1—2 2—3 3—4 4—5 维修费 5 7 12 18 25 28 v1 v2 v3 v4 v5 v6 23 25 26 29 30 42 60 85 32 44 62 34 46 28 40 30 图 8—16

内容[本讲小结】今天我们主要学习了权为负数的逐次逼近法，并举了一些实际例子，希望同学们回去好好复习。【本讲课程的作业】预习最大流问题

内 容 [本讲小结] 今天我们主要学习了权为负数的逐次逼近法，并举了一些实际例子，希望同学们回去 好好复习。 [本讲课程的作业] 预习最大流问题