文档介绍：最短路问题的LINGO求解
设图共有个节点,其赋权图的邻接矩阵为. , ;当为无向图时, 和分别由图得到,通常不一样。当,表示节点与节点不连通。令。假设图的所有权值
现求节点到节点的最短路,其线性规划模型为:
模型一
决策变量:设
目标函数为寻找一条节点到节点的通路,使其上权值和最小,故目标函数为:
,却不能有路回来,故有:
且
,却不能有路出去,故有:
,其它点进入和出去的路是一样多(可都为0),则:
且
,约束为:
总的线性规划模型为:
图1 无向图最短路示意图
示例演示
例1 ,求点1到点11的最短路。
其Lingo实现程序为:
model:
sets:
point/1..11/:u;
road(point,point):W,X;
endsets
data:
W=0,2,8,1,0,0,0,0,0,0,0,
2,0,6,0,1,0,0,0,0,0,0,
8,6,0,7,5,1,2,0,0,0,0,
1,0,7,0,0,0,9,0,0,0,0,
0,1,5,0,0,3,0,2,9,0,0,
0,0,1,0,3,0,4,0,6,0,0,
0,0,2,9,0,4,0,0,3,1,0,
0,0,0,0,2,0,0,0,7,0,9,
0,0,0,0,9,6,3,7,0,1,2,
0,0,0,0,0,0,1,0,1,0,4,
0,0,0,0,0,0,0,9,2,4,0;
enddata
min=***@sum(road(i,j):w(i,j)*x(i,j)); !最短路;
***@for(point(i)|i#ne#1#and#i#ne#11:***@sum(point(k):x(k,i))=***@sum(point(j):x(i,j)));
***@sum(point(j)|j#ne#1:x(1,j))=1; !起始点要出去;
***@sum(point(k)|k#ne#1:x(k,1))=0; !不能回到起始点;
***@sum(point(k)|k#ne#11:x(k,11))=1; !要到达目标点;
***@sum(point(j)|j#ne#11:x(11,j))=0; !目标点不能出去;
 ***@for(road(i,j):x(i,j)<=W(i,j)); !不能到达的路不考虑;
***@for(road(i,j):***@bin(x(i,j)));
 end
结果为minZ=13
x(1,2)=1 x(2,5)=1; x(5,6)=1 x(6,3)=1
x(3,7)=1 x(7,10)=1 x(10,9)=1 x(9,11)=1
故路径为12563710911
模型二
不必考虑起始点不回去,结束点不出去,统一考虑所有中间点不出现圈,添加约束为:
总模型为:
其Lingo实现程序为:
model:
sets:
point/1..11/;
road(point,point):W,X;
endsets
data:
W=0,2,8,1,0,0,0,0,0,0,0,
2,0,6,0,1,0,