最短路径问题数学建模实用教案

会计学1最短路径最短路径(ljng)问题问题 数学建模数学建模第一页，共31页。Floyd算法(sun f)Dijkstra算法(sun f)两个例子的求解引例2：最廉价航费表的制定引例1：最短运输路线问题最短路径问题的0-1规划模型第1页/共31页第二页，共31页。31023741165981第2页/共31页第三页，共31页。4050402510500152025150102040201001025252010055102525550第3页/共31页第四页，共31页。5l定义(dngy)：设P(u,v)是加权图G中从u到v的路径,则该路径上的边权之和称为该路径的权,记为w(P). 从u到v的路径中权最小者 P*(u,v)称为u到v的最短路径.1023741165981第4页/共31页第五页，共31页。1023741165981第5页/共31页第六页，共31页。S: 具有永久标号的顶点集;l(v): v的标记; f(v):v的父顶点,用以确定最短路径; 输入加权图的带权邻接矩阵w=w(vi,vj)nxm.初始化 令l(v0)=0,S=; vv0 ,l(v)=;更新(gngxn)l(v), f(v) 寻找不在S中的顶点u,使l(u)为最小.把u加入到S中,然后对所有不在S中的顶点v,如l(v)l(u)+w(u,v),则更新(gngxn)l(v),f(v), 即 l(v)l(u)+w(u,v),f(v)u;重复步骤2), 直到所有顶点都在S中为止.第6页/共31页第七页，共31页。第7页/共31页第八页，共31页。9第8页/共31页第九页，共31页。1023741165981第9页/共31页第十页，共31页。 d(i,j) : i到j的距离; path(i,j): i到j的路径上i的后继点; 输入(shr)带权邻接矩阵a(i,j).1）赋初值 对所有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页/共31页第十一页，共31页。第11页/共31页第十二页，共31页。13第12页/共31页第十三页，共31页。141023741165981第13页/共31页第十四页，共31页。15第14页/共31页第十五页，共31页。16050402510500152025150102040201001025252010055102525550第15页/共31页第十六页，共31页。050402510500152025150102040201001025252010055102525550第16页/共31页第十七页，共31页。18最短路径问题(wnt)的0-1规划模型 设决策(juc)变量为xij , 当顶点1至顶点n的路上含弧(i,j) 时，xij=1；否则xij=0. 其数学规划表达式为( , )11( , )( , )min ; 1,1,. . 1, ; 0,1, . 01,( , ). ijiji jEnnijjijji jEj iEijw xistxxininxi jE 或第17页/共31页第十八页，共31页。19最短路径(ljng)问题的0-1规划模型 例 （有向图最短路问题） 在下图中，用点表示城市，现有 共7个城市.点与点之间的连线表示城市间有道路相连.连线旁的数字表示道路的长度.现计划(jhu)从城市 到城市 铺设一条天然气管道，请设计出最小价格管道铺设方案. 12123,A B B C C C DAD本质是求从城市 到城市 的一条最短路AD第18页/共31页第十九页，共31页。20最短路径(ljng)问题的0-1规划模型 解：写出相应(xingyng)的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页/共31页第二十页，共31页。21最短路径问题的0-1规划(guhu)模型 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页/共31页第二十一页，共31页。22最短路径问题的0-1规划(guhu)模型 20 21 n=size(cities); ! The number of cities; 22 min=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页/共31页第二十二页，共31页。23最短路径问题的0-1规划(guhu)模型 在上述程序中， 21句中的n=size(cities)是计算集cities的个数，这里的计算结果是 , 这样编写方法目的在于提高程序的通用性.22句表示目标函数, 即求道路的最小权值.23, 24句表示约束中 的情况，即最短路中中间点的约束条件.25句表示约束中 的情况，即最短路中起点的约束.7n 1,iin1i 约束中 的情况，也就是最短路中终点的情况，没有列在程序中，因为终点的约束方程与前个方程相关.当然，如果你将此方程列入到LINGO程序中，计算时也不会出现任何问题，因为LINGO软件可以自动删除描述线性规划可行解中的多余方程.in第22页/共31页第二十三页，共31页。24最短路径问题的0-1规划(guhu)模型 LINGO软件计算结果（仅保留非零变量(binling)）如下Global optimal solution found at iteration: 0 Objective value: 6.000000 Variable Value Reduced Cost X( A, B1) 1.000000 0.000000 X( B1, C1) 1.000000 0.000000 X( C1, D) 1.000000 0.000000 即最短路(dunl)是 , 最短路(dunl)长为6个单位.11ABCD第23页/共31页第二十四页，共31页。25最短路径(ljng)问题的0-1规划模型 例（无向图的最短路(dunl)问题）求下图中 到 的最短路(dunl).1v11v 本例是处理(chl)无向图的最短路问题，在处理(chl)方式上与有向图的最短路有一些差别.第24页/共31页第二十五页，共31页。26最短路径问题的0-1规划(guhu)模型 解： 对于无向图的最短路问题，可以这样理解，从点 到点 和点 到点 的边看成有向弧，其他各条边均看成有不同方向的双弧，因此，可以按照前面介绍有向图的最短路问题来编程序，但按照这种方法编写LINGO程序相当于边（弧）增加了一倍.这里选择邻接矩阵和赋权矩阵的方法编写LINGO程序.1viviv11vMODEL: 1 sets: 2 cities/1.11/; 3 roads(cities, cities): p, w, x; 4 endsets 第25页/共31页第二十六页，共31页。27最短路径问题(wnt)的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 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页/共31页第二十七页，共31页。28最短路径问题(wnt)的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 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页/共31页第二十八页，共31页。29最短路径问题的0-1规划(guhu)模型 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): p(j,i)*x(j,i); 34sum(cities(j): p(1,j)*x(1,j)=1; END第28页/共31页第二十九页，共31页。30最短路径(ljng)问题的0-1规划模型 在上述程序中，第6行到第16行给出了图的邻接矩阵 ， 到 和 到 的边按单向计算，其余边双向计算.第17行到第27行给出了图的赋权矩阵 , 注意：由于有了邻接矩阵 ，两点无道路连接时，权值可以定义为0. 其它的处理方法基本上与有向图相同.P1v234,vv v8910,v vv11vWP用LINGO软件(run jin)求解，得到（仅保留非零变量） Global optimal solution found at iteration: 2 0 Objective value: 13.00000 第29页/共31页第三十页，共31页。31最短路径(ljng)问题的0-1规划模型 Variable Value Reduced Cost X( 1, 2) 1.000000 0.000000 X( 2, 5) 1.000000 0.000000 X( 3, 7) 1.000000 0.000000 X( 5, 6) 1.000000 0.000000 X( 6, 3) 1.000000 0.000000 X( 7, 10) 1.000000 0.000000 X( 9, 11) 1.000000 0.000000 X( 10, 9) 1.000000 0.000000 即最短路径(ljng)为1256371011最短路(dunl)长度为13.第30页/共31页第三十一页，共31页。