最短路程问题(lingo)

《最短路程问题(lingo)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、例7.4最短路问题给定N个点组成集合，由集合中任一点到另一点的距离用表示，如果到没有弧联结，则规定，又规定，指定一个终点，要求从点出发到的最短路线。这里我们用动态规划方法来做。用所在的点表示状态，决策集合就是除以外的点，选定一个点以后，得到效益并转入新状态，当状态是时，过程停止。显然这是一个不定期多阶段决策过程。定义是由点出发至终点的最短路程，由最优化原理可得这是一个函数方程，用LINGO可以方便的解决。!最短路问题;model:data:n=10;enddatasets:cities/1..n/:F;!10个城市;roads(cities,citie

2、s)/1,21,32,42,52,63,43,53,64,74,85,75,85,96,86,97,108,109,10/:D,P;endsetsdata:D=65369751191875410579;enddataF(n)=0;@for(cities(i)

3、i#lt#n:F(i)=@min(roads(i,j):D(i,j)+F(j)););!显然，如果P(i,j)=1,则点i到点n的最短路径的第一步是i-->j，否则就不是。由此，我们就可方便的确定出最短路径;@for(roads(i,j):P(i,j)=@if(F(i)#eq#D(i,j)+F(j

4、),1,0));end计算的部分结果为：Feasiblesolutionfoundatiteration:0 VariableValueN10.00000F(1)17.00000F(2)11.00000F(3)15.00000F(4)8.000000F(5)13.00000F(6)11.00000F(7)5.000000F(8)7.000000F(9)9.000000F(10)0.000000P(1,2)1.000000P(1,3)0.000000P(2,4)1.000000P(2,5)0.000000P(2,6)0.000000P(3,4)1.000

5、000P(3,5)0.000000P(3,6)0.000000P(4,7)0.000000P(4,8)1.000000P(5,7)1.000000P(5,8)0.000000P(5,9)0.000000P(6,8)1.000000P(6,9)0.000000P(7,10)1.000000P(8,10)1.000000P(9,10)1.000000 例3.5（最短路问题）在纵横交错的公路网中，货车司机希望找到一条从一个城市到另一城市的最短路。假设图3-1表示的是该公路网，节点表示货车可以停靠的城市，弧上的权表示两个城市之间的距离（百公里）。那么，货车从城

6、市S出发到达城市T，如何选择行驶路线，使所经过的路程最短？SA1A2A3B1B2C1C2T363658674678956图3-1最短路问题的例子假设从S到T的最优行驶路线P经过城市C1，则P中从S到C1的子路也一定是从S到C1的最优行驶路线；假设P经过城市C2，则P中从S到C2的子路也一定是从S到C2的最优行驶路线。因此，为了得到从S到T的最优行驶路线，我们只需要先求出从S到Ck（k=1,2）的最优行驶路线，只需要先求出从S到Bj（j=1,2）的最优行驶路线；只需要先求出从S到Ai（i=1,2）的最优行驶路线。而从S到Ai（i=1,2,3）的最优行驶路

7、线是很容易得到的（实际上，此例中S到Ai（i=1,2）只有唯一的道路）。也就是说，此例中我们可以把从S到T的行驶过程分成4个阶段，即S→Ai（i=1,2,3）Ai→Bj（j=1,2），Bj→Ck（k=1,2），Ck→T。记d(Y,X)为城市Y与城市X之间的直接距离（若这两个城市之间没有道路直接相连，则可以认为直接距离为无穷大），用L(X)表示城市S到城市X的最优行驶路线的路长，则有L(S)=0对本例的具体问题，可以直接计算如下：所以，从S到T的最优行驶路线的路长为20。进一步分析以上求解过程，可以得到从S到T的最优行驶路线为S→A3→B2→C1→T上面

8、这种计算方法在数学上称为动态规划（dynamicprogramming）,是最优化的一个分支。例3.5（最短路问题）在纵横交错的公路网中，货车司机希望找到一条从一个城市到另一城市的最短路。假设图3-1表示的是该公路网，节点表示货车可以停靠的城市，弧上的权表示两个城市之间的距离（百公里）。那么，货车从城市S出发到达城市T，如何选择行驶路线，使所经过的路程最短？SA1A2A3B1B2C1C2T363658674678956图3-1最短路问题的例子假设从S到T的最优行驶路线P经过城市C1，则P中从S到C1的子路也一定是从S到C1的最优行驶路线；假设P经过城

9、市C2，则P中从S到C2的子路也一定是从S到C2的最优行驶路线。因此，为了得到从S到T的最优行