最短路程问题

1、例7. 4最短路问题给定N个点1顽=1，2,N)组成集合P，,由集合中任一点心到 另一点P，照距离用门表示，如果亿到P，没有孤联结，则规定勺二心，又规定 c=O(l j,否则就不是。由此，我们就可方便的确定出最短路径；for (roads (i, j):P(i, j)=if(F(i) #eq# D(i, j)+F(j), 1,0);end计算的部分结果为：Feasible solution found at iteration:0VariableValueN10. 00000F( 1)17.00000F( 2)11.00000F( 3)15.00000F( 4)8.000000F( 5)13.

2、00000F( 6)11.00000F( 7)5.000000F( 8)7.000000KI/ KI/ KI/ KI/ KI/ KI/ KI/ KI/ KI/ KI/ KI/ KI/ KI/ KI/ KI/ 9023456456 7 8 7 8989000 1 1119.000000 0.000000 1. 000000 0.000000 1. 000000 0.000000 0.000000 1. 000000 0.000000 0.000000 0.000000 1. 000000 1. 000000 0.000000 0.000000 1. 000000 0.000000 1. 0000

3、00 1. 000000 1. 000000例3.5 (最短路问题)在纵横交错的公路网中，货车司机希望找到一条从一个城市到另一 城市的最短路。假设图3-1表示的是该公路网，节点表示货车可以停靠的城市，孤上的权表 示两个城市之间的距离(百公里)。那么，货车从城市S出发到达城市T,如何选择行驶路 线，使所经过的路程最短？图3-1最短路问题的例子假设从S到T的最优行驶路线P经过城市Ci,贝叩中从S到Ci的子路也一定是从S到Ci的最优 行驶路线：假设P经过城市C2,贝”中从S到C2的子路也一定是从S到C2的最优行驶路线。 因此，为了得到从S到T的最优行驶路线，我们只需要先求出从S到Ck(k=l,2)的

4、最优行驶 路线，只需要先求出从S到Bj (j=l,2)的最优行驶路线；只需要先求出从S到Ai (1=1,2)的 最优行驶路线。而从s到A (1=1,2,3)的最优行驶路线是很容易得到的(实际上，此例中s 到A (1=1,2)只有唯一的道路)。也就是说，此例中我们可以把从S到T的行驶过程分成4个阶段，即Sf Ai (1=1,2,3)Ai fBj (j=l,2), Bjf Ck(k=l,2), Ck-T。记d(Y,X)为城市Y与城市X之间的直接距离(若这 两个城市之间没有道路直接相连，则可以认为直接距离为无穷大)，用L(X)表示城市S到城市 X的最优行驶路线的路长，则有L (S)二 0(X) =

5、mmL(V)+d(y,X),X。S对本例的具体问题，可以直接计算如下：ZXA) = 6,L(A2) = 3,(人3)= 3;L(B) = mmL(Ai)+ 6, L(A2) + 8, L(A3) + 7) = 10 = L(Aj + 7,L(B2) = min侦如 + 5,以4 ) + 6, A(A3) + 4) = 7 = L(A3) + 4;L(Cj = nun(L(B1)4- 6,L(2)4-8) = 15 = L(B2) + 8,L(C2) = ininL(B1) + 7, L(B2) + 9) = 16 = L(B2) + 9;L(T) = mm匕(CJ + 5, L(C2) + 6

6、 = 20 =匕(Cj + 5.所以，从S到T的最优行驶路线的路长为20。进一步分析以上求解过程，可以得到从S到T的最 优行驶路线为S-*A3* B2*Ci*T上面这种计算方法在数学上称为动态规划(dynamic programming)，是最优化的一个分支。 作为一个例子，我们用LINGO来解这个最短路问题。我们可以编写如下的LINGO程序。集合段 定义的“CITIES城市）是一个基本集合（元素通过枚举给出），L是其对应的属性变量（我 们要求的最短路长）;“ROADS”（道路）是由CITIES导出的一个派生集合（请特别注意其用法）, 由于只有一部分城市之间有道理相连，所以不应该把它定义成稠密

7、集合，我们进一步将其元 素通过枚举给出，这就是一个稀疏集合。D是稀疏集合ROADS对应的属性变量（给定的距离）最短路程问题最短路程问题(shortest path problems)是图论另一类与优化有关的问题，对于这个问题， 图论中巳有解决的方法，如最短路问题的求解方法有Dijkstra算法。这里主要讨论的是如何 用LINGO软件来解决最短路问题。例7在图1中，用点表示城市，现有A, B” B2 , Ci，C” C3, D共七个城市。点与点之 间的连线表示城市间有道理相连。连线旁的数字表示道路的长度。现计划从城市A到城市 D铺设一条天然气管道，请设计出最小价格管道铺设方案。【分析】此例的本质

8、是求从城市A到城市D的一条最短路。 最短路问题的数学表达式假设图有n个顶点，现需要求从顶点1到顶点n的最短路，设决策变量为x,j,当学=1 说明弧(ij)位于顶点1至顶点n的路上；否则X1J=0o其数学规划表达式为mm /七；1, ，= 1, flflEE 七=T, =，y=iy=iA 1ED*(P)U, I 1,7?；S. t.Xy 0, (/, J) G E.下面介绍的方法是按照规划问题设计的LINGO程序，程序名exam0708.1g4.MODEL:! We have a network of 7 cities. We want to findthe length of the shor

9、test route from city 1 to city 7;3sets:! Here is our primitive set of seven cities;cities/A, Bl, B2, Cl, C2, C3, D/;7! The Derived set roads” lists the roads thatexist between the cities;roads(cities, cities)/A, Bl A, B2 Bl, Cl Bl, C2 Bl, C3 B2, Cl B2, C2 B2, C3C1,DC2,DC3,D/: w,x;endsets14data:! Her

10、e are the idstances that correspondto above links;w = 24 3 3 1 2 3 1 1 34;enddata20n = size(cites); ! The number of cities;niiii = sum(ioads: w * x);fbr(cities(i)|i # ne # 1 # and # i # ne # n:sum(ioads(ij): x(ij) = sum(roads(jj): x(j,i);sum(rads(ij)|i # eq # 1 : x(ij) = 1;END在上述程序中，21行中的n=size(cities)是计算集cities的个数，这里的计算结果是n=7, 这只编写的方法的目的在于提高程序的通用性o 22行表示目标函数(14),即求道路的最小 权值。23、24行表示约束(15)中1=1的情形，即最短路中起点的约束。约束(15)中i=n的情形，也就是最短路中终点的情形，没有列在程序中，因为终点的 约束方程与前n-1个方程线性相关。当然，如果将此方程列入LINGO程序中，计算时也不 会出现任何问题，因为LINGO软件可以自动删除描述线性规划可行解中的多余方程。LINGO软件计算结果(仅保留非