运筹学 第八章.ppt

《运筹学 第八章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第八章最短路问题第一节最短路问题引例例下图为单行线交通网，每有向边旁的数字表示通过这条线所需的费用。现在某人要从v1出发，通过这个交通网到v8去，求使总费用最小的旅行路线。v2v523464v3v1v4v6121061210v8v9v72363从v1到v8：P1=（v1，v2，v5，v8）费用6+1+6=13P2=（v1，v3，v4，v6，v7，v8）费用3+2+10+2+4=21P3=……从v1到v8的旅行路线从v1到v8的路。旅行路线总费用路上所有有向边权之和。最短路问题中，不考虑有向环、并行有向边。v2v523464v3v1v4v6121061210v8v9

2、v72363最短路问题给定有向网络D=（V，A，W），任意有向边aij∈A，有权w（aij）=wij，给定D中的两个顶点vs，vt。设P是D中从vs到vt的一条路，定义路P的权（长度）是P中所有有向边的权之和，记为w（P）。最短路问题就是要在所有从vs到vt的路中，求一条路P0，使称P0是从vs到vt的最短路。路P0的权称为从vs到vt的路长。记为ust。计算过程中可采用标号方法。vs到vi的最短路长度已求出，相应的点记“永久”标号；vs到vi的最短路长度尚未求出,相应的点记“临时”标号。前点标号j:表示点vs到vj的最短路上vj的前一点。如j=m，表示vs到

3、vj的最短路上vj前一点是vm。第二节最短路的标号算法当所有wij≥0时，本算法是用来求给定点vs到任一个点vj最短路的公认的最好方法。事实：如果P是D中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。最短路的子路也是最短路。1,6图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,01,∞1,∞1,11,∞1,∞1,∞1,31,6图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,01,∞1,∞1,11,∞1,∞1,∞1,31,6图上标号法:v5v

4、223464v3v1v4121061210v8v9v72363v60,01,∞4,111,11,∞1,∞1,∞1,31,5图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,01,∞4,111,11,∞1,∞1,∞1,31,63,5图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,01,∞4,111,11,∞1,∞1,31,∞3,5图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,04,111,11,∞2,61,∞1,31,∞3,5图上标号法:v5v22

5、3464v3v1v4121061210v8v9v72363v60,05,101,11,∞2,65,121,35,9问题：①本例中，v1到v9的最短路？②无向网络:③负权有向边时。wijvivjwijwijvjvi无向网络中，最短路→最短链。④多个点对之间最短路？v1v2v312-3Dijkstra算法失效------floyd算法例2某台机器可连续工作4年，也可于每年末卖掉，换一台新的。已知于各年初购置一台新机器的价格及不同役龄机器年末的处理价格如下表。新机器第一年运行及维修费为0.3万元，使用1-3年后机器每年的运行及维修费用分别为0.8，1.5，2.0万元。试

6、确定该机器的最优更新策略，使4年内用于更换、购买及运行维修的总费用为最省。j第一年第二年第三年第四年年初购置价使用j年的机器处理价2.52.02.61.62.81.33.11.1例3某公司在六个城市c1,…,c6中有分公司，从ci到cj的直接航程票价记在下述矩阵中的(i,j)位置上。（∞表示无直接航路），请帮助该公司设计一张任意两城市间的票价最便宜的路线表。050∞40251001520∞25∞1501020∞∞20100551025∞25550例4已知有6个村子，相互间道路的距离如下图示。拟合建一所小学，已知A处有小学生50人，B处40人，C处60人，D处20人

7、，E处70人，F处90人，问小学应建在哪一个村子，使学生上学最方便（原则①所有人走的总路程最短；②尽可能公平。）。AFEDCB2781361364