最短路径问题数学建模课件.ppt

《最短路径问题数学建模课件.ppt》由会员分享，可在线阅读，更多相关《最短路径问题数学建模课件.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于最短路径问题数学建模1第1页，此课件共30页哦21023741165981第2页，此课件共30页哦3050402510500152025150102040201001025252010055102525550第3页，此课件共30页哦4l定义：设P(u,v)是加权图G中从u到v的路径,则该路径上的边权之和称为该路径的权,记为w(P).从u到v的路径中权最小者 P*(u,v)称为u到v的最短路径.1023741165981第4页，此课件共30页哦1023741165981第5页，此课件共30页哦算法步骤S:具有永久标号的顶点集;l(v):v的标记;f(v):v的父顶点,用以确定最短路径;输入加

2、权图的带权邻接矩阵w=w(vi,vj)nxm.初始化 令l(v0)=0,S=;vv0,l(v)=;更新l(v),f(v)寻找不在S中的顶点u,使l(u)为最小.把u加入到S中,然后对所有不在S中的顶点v,如l(v)l(u)+w(u,v),则更新l(v),f(v),即 l(v)l(u)+w(u,v),f(v)u;1)重复步骤2),直到所有顶点都在S中为止.第6页，此课件共30页哦第7页，此课件共30页哦8第8页，此课件共30页哦1023741165981第9页，此课件共30页哦算法步骤 d(i,j):i到j的距离;path(i,j):i到j的路径上i的后继点;输入带权邻接矩阵a(i,j).1）赋

3、初值 对所有i,j,d(i,j)a(i,j),path(i,j)j,k=l.2）更新d(i,j),path(i,j)对所有i,j,若d(i,k)+d(k,j)d(i,j),则 d(i,j)d(i,k)+d(k,j),path(i,j)path(i,k),k k+13）重复2)直到k=n+1第10页，此课件共30页哦第11页，此课件共30页哦12第12页，此课件共30页哦131023741165981第13页，此课件共30页哦14运行上页程序输出：运行上页程序输出：dis=21path=1 8 9 10 11 因此顶点因此顶点1到顶点到顶点11的最短路径为的最短路径为18 9 10 11,其长度

4、为其长度为21。第14页，此课件共30页哦15050402510500152025150102040201001025252010055102525550第15页，此课件共30页哦050402510500152025150102040201001025252010055102525550第16页，此课件共30页哦17 假设图有假设图有 n 个顶点，现需要求从顶点个顶点，现需要求从顶点1到顶点到顶点n的最的最短路径短路径.最短路径问题的0-1规划模型 设决策变量为设决策变量为xij,当顶点当顶点1至顶点至顶点n的路上含弧的路上含弧(i,j)时，时，xij=1；否则；否则xij=0.其数学规划表达

5、式为其数学规划表达式为(,)11(,)(,)min ;1,1,.1,;0,1,.01,(,).ijiji jEnnijjijji jEj iEijw xistxxininxi jE 或第17页，此课件共30页哦18最短路径问题的0-1规划模型 例（有向图最短路问题）在下图中，用点表示城市，现有 共7个城市.点与点之间的连线表示城市间有道路相连.连线旁的数字表示道路的长度.现计划从城市 到城市 铺设一条天然气管道，请设计出最小价格管道铺设方案.12123,AB B C C C DAD本质是求从城市 到城市 的一条最短路AD第18页，此课件共30页哦19最短路径问题的0-1规划模型 解：写出相应的

6、LINGO程序，MODEL:1!We have a network of 7 cities.We want to find 2 the length of the shortest route from city 1 to city 7;3 4sets:5 !Here is our primitive set of seven cities;6 cities/A,B1,B2,C1,C2,C3,D/;7 8 !The Derived set roads lists the roads that 9 exist between the cities;第19页，此课件共30页哦20最短路径问题的0-

7、1规划模型 10 roads(cities,cities)/11 A,B1 A,B2 B1,C1 B1,C2 B1,C3 B2,C1 B2,C2 B2,C3 12 C1,D C2,D C3,D/:w,x;13 endsets 14 15 data:16 !Here are the distances that correspond 17 to above links;18 w=2 4 3 3 1 2 3 1 1 3 4;19 enddata 第20页，此课件共30页哦21最短路径问题的0-1规划模型 20 21 n=size(cities);!The number of cities;22 m

8、in=sum(roads:w*x);23 for(cities(i)|i#ne#1#and#i#ne#n:24 sum(roads(i,j):x(i,j)=sum(roads(j,i):x(j,i);25 sum(roads(i,j)|i#eq#1:x(i,j)=1;END第21页，此课件共30页哦22最短路径问题的0-1规划模型 在上述程序中，21句中的n=size(cities)是计算集cities的个数，这里的计算结果是 ,这样编写方法目的在于提高程序的通用性.22句表示目标函数,即求道路的最小权值.23,24句表示约束中 的情况，即最短路中中间点的约束条件.25句表示约束中 的情况，即

9、最短路中起点的约束.7n 1,iin1i 约束中 的情况，也就是最短路中终点的情况，没有列在程序中，因为终点的约束方程与前个方程相关.当然，如果你将此方程列入到LINGO程序中，计算时也不会出现任何问题，因为LINGO软件可以自动删除描述线性规划可行解中的多余方程.in第22页，此课件共30页哦23最短路径问题的0-1规划模型 LINGO软件计算结果（仅保留非零变量）如下Global optimal solution found at iteration:0 Objective value:6.000000 Variable Value Reduced Cost X(A,B1)1.000000

10、 0.000000 X(B1,C1)1.000000 0.000000 X(C1,D)1.000000 0.000000 即最短路是 ,最短路长为6个单位.11ABCD第23页，此课件共30页哦24最短路径问题的0-1规划模型 例（无向图的最短路问题）求下图中 到 的最短路.1v11v 本例是处理无向图的最短路问题，在处理方式上与有向图的最短路有一些差别.第24页，此课件共30页哦25最短路径问题的0-1规划模型 解：对于无向图的最短路问题，可以这样理解，从点 到点 和点 到点 的边看成有向弧，其他各条边均看成有不同方向的双弧，因此，可以按照前面介绍有向图的最短路问题来编程序，但按照这种方法编

11、写LINGO程序相当于边（弧）增加了一倍.这里选择邻接矩阵和赋权矩阵的方法编写LINGO程序.1viviv11vMODEL:1 sets:2 cities/1.11/;3 roads(cities,cities):p,w,x;4 endsets 第25页，此课件共30页哦26最短路径问题的0-1规划模型 5 data:6 p=0 1 1 1 0 0 0 0 0 0 0 7 0 0 1 0 1 0 0 0 0 0 0 8 0 1 0 1 1 1 1 0 0 0 0 9 0 0 1 0 0 0 1 0 0 0 0 10 0 1 1 0 0 1 0 1 1 0 0 11 0 0 1 0 1 0 1

12、0 1 0 0 12 0 0 1 1 0 1 0 0 1 1 0 13 0 0 0 0 1 0 0 0 1 0 1 14 0 0 0 0 1 1 1 1 0 1 1 15 0 0 0 0 0 0 1 0 1 0 1 16 0 0 0 0 0 0 0 0 0 0 0;第26页，此课件共30页哦27最短路径问题的0-1规划模型 17 w=0 2 8 1 0 0 0 0 0 0 0 18 2 0 6 0 1 0 0 0 0 0 0 19 8 6 0 7 5 1 2 0 0 0 0 20 1 0 7 0 0 0 9 0 0 0 0 21 0 1 5 0 0 3 0 2 9 0 0 22 0 0 1 0

13、 3 0 4 0 6 0 0 23 0 0 2 9 0 4 0 0 3 1 0 24 0 0 0 0 2 0 0 0 7 0 9 25 0 0 0 0 9 6 3 7 0 1 2 26 0 0 0 0 0 0 1 0 1 0 4 27 0 0 0 0 0 0 0 9 2 4 0;28 enddata第27页，此课件共30页哦28最短路径问题的0-1规划模型 29n=size(cities);30min=sum(roads:w*x);31for(cities(i)|i#ne#1#and#i#ne#n:32 sum(cities(j):p(i,j)*x(i,j)33 =sum(cities(j):

14、p(j,i)*x(j,i);34sum(cities(j):p(1,j)*x(1,j)=1;END第28页，此课件共30页哦29最短路径问题的0-1规划模型 在上述程序中，第6行到第16行给出了图的邻接矩阵 ，到 和 到 的边按单向计算，其余边双向计算.第17行到第27行给出了图的赋权矩阵 ,注意：由于有了邻接矩阵 ，两点无道路连接时，权值可以定义为0.其它的处理方法基本上与有向图相同.P1v234,vvv8910,vvv11vWP用LINGO软件求解，得到（仅保留非零变量）Global optimal solution found at iteration:2 0 Objective value:13.00000 第29页，此课件共30页哦感谢大家观看第30页，此课件共30页哦