资源描述：
《运筹学最短路邮递员问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、最短路问题最短路问题是最重要的优化问题之一，它不仅可以直接应用于解决生产实际的许多问题例如各种管道的铺设、线路的安排、厂区的布局、设备的更新等等，而且经常被作为一个基本工具，用于解决其它优化问题如运输网络的最小费用流等。（最短距离、费时最少、费用最省）定义（权、赋权图）：对图G的每一条边e，可赋与一个实数w（e）称为边e的权。图G连同它边上的权称为赋权图。路中边权最小的称为最短路。权可以表示铁路长度，通讯网络的造价，网络中表示耗时等。狄克斯拉（Dijkstra）算法最短路问题可以化为线性规划问题求解，也可以用动态规划方法求解，这里介绍一种有效算法—狄克斯
2、拉（Dijkstra）算法，这一算法是1959年首次被提出来的。该算法适用于每条弧的权数ωij≥0情形。算法的基本思路：从发点vs出发，有一个假想的流沿网络一切可能的方向等速前进，遇到新节点后，再继续沿一切可能的方向继续前进，则最先到达终点vt的流所走过的路径一定是最短的。为了实现这一想法，对假想流依次到达的点，依次给予p标号，表示vs到这些点的最短距离。对于假想流尚未到达的点给予T标号，表示vs到这些点的最短距离的估计值。具体作法如下：1°标p（vs）=0，其余点标T（vi）=+∞;2°由刚刚获得p标号的vi点出发，改善它的相邻点vj的T标号,即新的T
3、（vj）=min{老的T（vj），p（vi）+ωij}若T（vj）=p（vi）+ωij，则记k（vj）=vi（前点标记）;3°找出具有最小T标号的点，将其标号改为p标号。若vt已获得p标号，则已找到最短路，由k（vt）反向追踪，就可找出vs到vt的最短路径，p（vt）就是vs到vt的最短距离。否则，转2°。例求图中v1到v8的最短路。v4v23265v3v5v6v7v863552111479解：标p（v1）=0，其余点标T（vi）=+∞，i=2,3,4,5,6,7,8;T（v2）=min{+∞,0+3}=3,k（v2）=v1T（v3）=min{+∞,0+
4、5}=5,k（v3）=v1T（v4）=min{+∞,0+6}=6,k（v2）=v1将具有最小T标号的v2点的标号改为p标号：p（v2）=3；T（v3）=min{5,3+1}=4,k（v3）=v2T（v5）=min{+∞,3+7}=10,k（v5）=v2T（v6）=min{+∞,3+4}=7,k（v6）=v2目前，点v3具有最小T标号，将其标号改为p标号：p（v3）=4；v1v4v23265v3v5v6v7v8635211149v17p（v1）=0p（v2）=3p（v3）=4T（v4）=min{6,4+1}=5,k（v4）=v3T（v6）=min{7,4+
5、2}=6,k（v6）=v3目前，点v4具有最小T标号，将其标号改为p标号：p（v4）=5；T（v6）=min{6,5+3}=6;T（v7）=min{+∞,5+5}=10,k（v7）=v4目前，点v6具有最小T标号，将其标号改为p标号：p（v6）=6；T（v5）=min{10,6+2}=8,k（v5）=v6T（v7）=min{10,6+1}=7,k（v7）=v6T（v8）=min{+∞,6+9}=15,k（v8）=v65目前，点v7具有最小T标号，将其标号改为p标号：p（v7）=7；T（v8）=min{15,7+5}=12,k（v8）=v7;p（v5）=8
6、；T（v8）=min{12,8+6}=12,p（v8）=12；反向追踪找最短路径。最短路径为：v1→v2→v3→v6→v7→v8；因p（v8）=12，所以v1→v8的最短距离为12。最短路问题不仅可以求解交通图中两点之间的最短距离，实际中很多问题也可变为最短路问题加以求解。例如设备更新问题，厂区合理布局问题等。兹举一例：例1（设备更新问题）某企业使用一台设备，在每年年底，企业都要决策下年度是购买一台新设备呢？还是继续使用这台设备。若购买新的，就要支付一笔购置费；如果使用旧设备，只要支付维修费，而维修费随着设备的使用年限延长而增加。现根据以往统计资料已经估
7、算出设备在各年初的价格和不同使用年限的修理费用，分别如表1、表2所示。试确定一个五年内的设备更新计划，使五年内总支出最小。图上标示法下面我们结合例3介绍求解最短路问题的图上标示法，它比狄克斯拉算法更简洁。年份一二三四五购置费1111121213表1使用年限0~11~22~33~44~5年修理费5681118表2解：先根据表1、表2的数据画出设备更新费用网络图，如下图所示。图中点vi表示第i年开始，弧（vi,vj）表示设备第i年初使用到第j年初，弧（vi,vj）上的权数表示该期间设备所需的费用。这样，求五年内设备最优更新方案便转化为求v1→v6的最短路。v
8、1v2v3v4v5v616161717182230415922304123312
