运筹学最短路邮递员问题PPT学习教案

1、会计学1 运筹学最短路邮递员问题运筹学最短路邮递员问题 第1页/共118页 第2页/共118页 例 求图中v1 到v8 的最短路。 v4 v2 3 2 6 5 v3 v5 v6 v7 v8 6 3 5 5 2 1 1 1 4 7 9 解：标p（v1）=0，其余点标T（vi）=+，i=2,3,4,5,6,7,8; T（v2）=min+,0+3=3, k（v2 ）=v1 T（v3）=min+,0+5=5, k（v3 ）=v1 T（v4）=min+,0+6=6, k（v2 ）=v1 将具有最小T标号的v2 点的标号改为p标号：p（v2）=3； T（v3）=min5,3+1=4, k（v3 ）=v2

2、T（v5）=min+,3+7=10, k（v5 ）=v2 T（v6）=min+,3+4=7, k（v6 ）=v2 目前，点v3 具有最小T标号，将其标号改为p标号： p（v3）=4； v1 第3页/共118页 v4 v2 3 2 6 5 v3 v5 v6 v7 v8 6 3 5 2 1 1 1 4 9v1 7 p（v1） =0 p（v2） =3 p（v3） =4 T（v4）=min6,4+1=5, k（v4 ）=v3 T（v6）=min7,4+2=6, k（v6 ）=v3 目前，点v4 具有最小T标号，将其标号改为p标号： p（v4）=5； T（v6）=min6,5+3=6; T（v7）=mi

3、n+,5+5=10, k（v7 ）=v4 目前，点v6 具有最小T标号，将其标号改为p标号： p（v6）=6； T（v5）=min10,6+2=8, k（v5 ）=v6 T（v7）=min10,6+1=7, k（v7 ）=v6 T（v8）=min+,6+9=15, k（v8）=v6 5 目前，点v7 具有最小T标号，将其标号改为p标号： p（v7）=7； T（v8）=min15,7+5=12, k（v8）=v7 ; p（v5）=8； T（v8）=min12,8+6=12, p（v8）=12；反向追踪找最短路径。 第4页/共118页 最短路径为：v1v2v3v6v7v8 ； 因p（v8）=12，

4、所以v1v8 的最短距离为12。 最短路问题不仅可以求解交通图中两点之间的最短距离，实际 中很多问题也可变为最短路问题加以求解。例如设备更新问题，厂 区合理布局问题等。兹举一例： 例1（设备更新问题）某企业使用一台设备，在每年年底，企业 都要决策下年度是购买一台新设备呢？还是继续使用这台设备。若 购买新的，就要支付一笔购置费；如果使用旧设备，只要支付维修 费，而维修费随着设备的使用年限延长而增加。现根据以往统计资 料已经估算出设备在各年初的价格和不同使用年限的修理费用，分 别如表1、表2所示。 试确定一个五年内的设备更新计划，使五年内总支出最小。 图上标示法图上标示法 下面我们结合例3介绍求解

5、最短路问题的图上标示法图上标示法，它比狄 克斯拉算法更简洁。 第5页/共118页 年份 一 二 三 四 五 购 置 费 11 11 12 12 13 表1 使用年限 01 12 23 34 45 年修理费 5 6 8 11 18 表2 解：先根据表1、表2的数据画出设备更新费用网络图，如下 图所示。图中点vi 表示第i 年开始，弧（vi ,vj）表示设备第i 年初使 用到第j 年初，弧（vi ,vj）上的权数表示该期间设备所需的费用。这 样，求五年内设备最优更新方案便转化为求v1v6 的 最短路。 v 1 v 2 v 3 v 4 v5 v 6 1 6 1 6 17171 8 22 30 41

6、59 22 3 0 41 23 31 23 第6页/共118页 设d（vi）表示点vi 到终点的最短距离，根据动态规划最优性原理 ，最短路径中任何子路径也必然是最短的。因此有 d（vi）=minij +d（vj） 注意，上式要对以vi 为起点的所有弧（vi ,vj）进行计算。然后将计 j 算结果直接标在图中点vi 的旁边，同时标出与点vi 最近的邻接点。 先从点v5 算起，逆向进行。 v 1 v 2 v 3 v 4 v5 v 6 1 6 1 6 17171 8 22 30 41 59 22 3 0 23 23 41 对于点v5 ：d（v5）=18，v5 v6 ； 18 v5 v6 对于点v4

7、：d（v4）=min17+18,23=23，v4 v6 ； 23 v4 v6 对于点v3 ：d（v3）=min17+23,23+18,31=31，v3 v6 ； 31 31 v3 v6 对于点v2 ：d（v2）=min16+31,22+23,30+18,41=41，v2v6 ； 41 v2 v6 对于点v1 ：d（v1）=min16+41,22+31,30+23,41+18,59=53,v1v3；或v1 v4。 53 v1 v3v6 或 v1 v4v6 第7页/共118页 第8页/共118页 第9页/共118页 第10页/共118页 5 1 2 7 5 6 3 4 2 5 5 2 7 31 3

8、 5 7 1 第11页/共118页 1 2 3 2 5 2 第12页/共118页 第13页/共118页 第14页/共118页 第15页/共118页 第16页/共118页 5 1 2 7 5 6 3 4 2 5 5 2 7 31 3 5 7 1 第17页/共118页 0 5 1 2 7 5 6 3 4 2 5 5 2 7 31 3 5 7 1 0 第18页/共118页 5 1 2 7 5 6 3 4 2 5 5 2 7 31 3 5 7 1 0 第19页/共118页 5 1 2 7 5 6 3 4 2 5 5 2 7 31 3 5 7 1 0 第20页/共118页 5 1 2 7 5 6 3 4

9、 2 5 5 2 7 31 3 5 7 1 0 2 第21页/共118页 5 1 2 7 5 6 3 4 2 5 5 2 7 31 3 5 7 1 0 2 3 第22页/共118页 5 1 2 7 5 6 3 4 2 5 5 2 7 31 3 5 7 1 0 2 3 第23页/共118页 5 1 2 7 5 6 3 4 2 5 5 2 7 31 3 5 7 1 0 2 3 4 第24页/共118页 5 1 2 7 5 6 3 4 2 5 5 2 7 31 3 5 7 1 0 2 3 4 第25页/共118页 5 1 2 7 5 6 3 4 2 5 5 2 7 31 3 5 7 1 0 2 3

10、4 7 第26页/共118页 5 1 2 7 5 6 3 4 2 5 5 2 7 31 3 5 7 1 0 2 3 4 7 第27页/共118页 5 1 2 7 5 6 3 4 2 5 5 2 7 31 3 5 7 1 0 2 3 4 7 8 第28页/共118页 5 1 2 7 5 6 3 4 2 5 5 2 7 31 3 5 7 1 0 2 3 4 7 8 第29页/共118页 5 1 2 7 5 6 3 4 2 5 5 2 7 31 3 5 7 1 0 2 3 4 7 8 13 第30页/共118页 5 1 2 7 5 6 3 4 2 5 5 2 7 31 3 5 7 1 0 2 3 4

11、 7 8 13 第31页/共118页 第32页/共118页 第33页/共118页 第34页/共118页 第35页/共118页 第36页/共118页 第37页/共118页 第38页/共118页 第39页/共118页 第40页/共118页 第41页/共118页 第42页/共118页 第43页/共118页 第44页/共118页 第45页/共118页 第46页/共118页 第47页/共118页 第48页/共118页 第49页/共118页 第50页/共118页 第51页/共118页 第52页/共118页 第53页/共118页 第54页/共118页 第55页/共118页 第56页/共118页 第57页/共

12、118页 第58页/共118页 第59页/共118页 第60页/共118页 第61页/共118页 第62页/共118页 第63页/共118页 第64页/共118页 第65页/共118页 第66页/共118页 第67页/共118页 第68页/共118页 第69页/共118页 第70页/共118页 第71页/共118页 第72页/共118页 第73页/共118页 第74页/共118页 第75页/共118页 第76页/共118页 第77页/共118页 第78页/共118页 第79页/共118页 第80页/共118页 第81页/共118页 V1 V2 V3 V4 V5 V6 V7 D(vi) V103

13、0506393456093 V2 300203363153063 V3 502002050254050 V4 633320030183363 V5 936350300486393 V6 451525184801548* V7 603040336315063 第82页/共118页 第83页/共118页 第84页/共118页 第85页/共118页 第86页/共118页 第87页/共118页 第88页/共118页 第89页/共118页 第90页/共118页 第91页/共118页 第92页/共118页 第93页/共118页 第94页/共118页 第95页/共118页 第96页/共118页 第97页/共118页 第98页/共118页 第99页/共118页 第100页/共1