最短路径LINGO算法.doc

《最短路径LINGO算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、s,cities)/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)

4、#eq#D(i,j)+F(j),1,0));end