《物流运筹方法与工具 教学课件 ppt 作者 彭秀兰 毛磊第五章运输路径规划 第二节单一路线问题》由会员分享，可在线阅读，更多相关《物流运筹方法与工具 教学课件 ppt 作者 彭秀兰 毛磊第五章运输路径规划 第二节单一路线问题（16页珍藏版）》请在金锄头文库上搜索。
1、在运输路径规划中，很多问题可归纳为单一起讫点的运输路 线问题，即网络理论中的最短路问题。最短路问题是网络理论中 应用最广泛的问题之一，许多求优问题可以使用这个模型，如设 备更新、管道铺设、线路安排、厂区布局等。另外诸如运价最 小、运行时间最短、最可靠路线等问题，都可能转化为最短路问 题加以解决。 最短路问题的一般提法如下： 为连通图，图中各边 有权 （ 表示 间无边）， 为图中任意两点，求一条道路 ，使它是从 到 的所有路中总权最小的路。即 最小 有些最短路问题也可以是求网络中某指定点到其余所有结点 的最短路，或求网络中任意两点间的最短路。,一、EWDijkstra算法,本算法可用于求解指定两
2、点间的最短路或从指定 点到其余各点的最短路，目前被认为是求无负权网络 最短路问题的最好方法，由Dijkstra于1959年提出。 算法的基本思路基于以下原理：若序列 是从 到 的最短路，则序列 必为从 到 的最短路。,一、EWDijkstra算法,下面给出Dijkstra算法基本步骤，采用标号法。 可用两种标号：标号和标号，标号为临时性标号 （Temporary Label），为永久性标号（Permanent Label），给点一个标号时，表示从 到点 的最 短路权， 的标号不再改变。给点 一个标号T 时，表示从 到 点的估计最短路权的上界，是一 种临时标号，凡没有得到P标号的都有T 标号。算
3、法 每一步都把某一点的T标号改为P标号，当终点vt 得到 P标号时，全部计算结束。对于有n个顶点的图，最多 经n-1步就可以得到从始点到终点的最短路。,一、EWDijkstra算法,步骤： （一）给 以P 标号， 其余各点给T 标号， 。 （二）若 点为刚得到P 标号的点，考虑这样的点 属于E，且 为T 标号。对 的T 标号进行如下的更改： （三）比较所有具有T标号的点，把最小者改为P 标号，即 若全部点均为P 标号则停止，否则用 代 转回（二）。,一、EWDijkstra算法,例5-1 用Dijkstra算法求图5-5（a）中v1点v8到 点的最短路。,图 5-5,一、EWDijkstra算
4、法,例5-1 解：（一）给 以 标号， 其余所有点给 标号， 。 （二）由于 边属于 ，且 为 标号，所以修改这两个点的标号：,T（v2）= min T(v2),P(v1)+l12 = min +，0+4 = 4 T（v3）= min T(v3),P(v1)+l13 = min +，0+6 = 6 （三）比较T标号，T（v2）最小，所以令 P（v2）=4,一、EWDijkstra算法,例5-1 （四）v2为刚得到P标号的点，考察边（v2, v4）（v2, v5）的端点v4 ，v5。 T（v4）= min T(v4),P(v2)+l24 = min +，4+5 = 9 T（v5）= min T(
5、v5),P(v2)+l25 = min +，4+4 = 8 （五）比较所有T标号，T（v3）最小，所以令P（v3）= 6。 （六）考虑v3，有 T（v4）= min T(v4),P(v3)+l34 = min 9，6+4 = 9 T（v5）= min T(v5),P(v3)+l35 = min 8，6+7 = 8 （七）全部T标号中，T（v5）最小，令P（v5）= 8。 （八）考察v5，有 T（v6）= min T(v6),P(v3)+l56 = min +，8+5 = 13 T（v7）= min T(v7),P(v3)+l57 = min +，8+6 = 14 （九）全部T标号中，T（v4）
6、最小，令P（v4）= 9。,一、EWDijkstra算法,例5-1 （十）考察v4，有 T（v6）= min T(v6),P(v4)+l46 = min 13，9+9 = 13 T（v7）= min T(v7),P(v4)+l47 = min 14，9+7 = 14 （十一）全部T标号中，T（v6）最小，令P（v6）= 13。 （十二）考察v6，有 T（v7）= min T(v7),P(v6)+l67 = min 14，13+4 = 14 T（v8）= min T(v8),P(v6)+l68 = min +，13+4 = 17 （十三）全部T标号中，T（v7）最小，令P（v7）= 14。 （十
7、四）考察v7，有 T（v8）= min T(v8),P(v7)+l78 = min 17，141 = 15 （十五）只有一个T标号T（v8），令P（v8）= 15，停。 全部计算结果见图5-5（b），v1到v8之最短路为 v1v2v5v7v8，路长P（v8）= 15，同时得到v1点到其余 各点的最短路。,二、Bellman算法,算法的基本思路是：从 到 的最短路总是沿着该路从 先到某一点 ，然后再沿着 边到达 ，而 到 的 这条路必然也是 到 的最短路。若令 表示从 到 的 最短路长， 为 到 的最短路长，则必有下列方程：,用迭代方法解这个方程。开始时令 ， 即用 到的直接距离做初始解，若 与
8、 间无边，则记 ， 间的最短路长为+。从第二步起，使用迭代公式 求 ，当进行到第t步，若出现 则停止， 即为vi 点到各点的最短路长。,二、Bellman算法,例5-2 求图5-6中 点到各点的最短路。 解：初始条件为,图 5-6,第一轮迭代：,二、Bellman算法,类似可得,可以看出 表示从 点两步到 的最短路长。全部计算过程可用表5-2表示。,迭代进行到第六步时，发现 则停止。表中最后一列数字分别表示 点到各点的最短路长。 如果需要知道 点到各点的最短路径，可以采取“反向追踪”的办法。,例5-2,二、Bellman算法,由于递推公式中的 ，实际意义为从v1到vj点、至多含有k-1个中间
9、点的最短路权，所以在含有n各点的图中，如果不含有总权小于零的回 路，求从v1点到任一点的最短路权，用上述算法最多经过n-1次迭代必定 收敛。显然如果图中含有总权小于零的回路，最短权没有下界。 表5-2,说明：表中空格为。,二、Bellman算法,例5-3 已知一个地区的交通网络如图5-7所示，其中 点代表居民小区，边表示公路， 为公路距离，问 区中心医院应建在哪个小区，可使离医院最远的小 区居民就诊时所走的路程最近？,图 5-7,二、Bellman算法,例5-3 解：这是个选址问题，实际要求出图的中心，可以化为一系列求最短路问题。先求出 到其他各点的最短路长 ，令 ，表示若医院建在 ，则离医院最远的小区距离为 。再依次计算 到其余各点的最短路，类似求出 。 中最小着即为所求，计算结果见表5-3。,二、Bellman算法,表5-3,由于 最小，所以医院应建立在 ，此时离医院最远的小区距离为48，比医院建再其他小区时最远的小区距离都短。,本节作业题,教材P122： 1题，2题，3题。,
