|
图论中TSP(Traveling Salesman Problem）问题的LINGO求解与应用
问题1 设有一个售货员从10个城市中的某一个城市出发，去其它9个城市推销产品。10个城市相互距离如下表。要求每个城市到达一次仅一次后，回到原出发城市。问他应如何选择旅行路线，使总路程最短。     
MODEL:
SETS:
city/1..10/:u;
link(city,city):d,x;
ENDSETS
DATA:
d=0 7 4 5 8 6 12 13 11 18
7 0 3 10 9 14 5 14 17 17
4 3 0 5 9 10 21 8 27 12
5 10 5 0 14 9 10 9 23 16
8 9 9 14 0 7 8 7 20 19
6 14 10 9 7 0 13 5 25 13
12 5 21 10 8 13 0 23 21 18
13 14 8 9 7 5 23 0 18 12
11 17 27 23 20 25 21 18 0 16
18 17 12 16 19 13 18 12 16 0;
@text()=@writefor(link(i,j)|x(i,j)#gt#0:' x(',i,',',j,')=',x(i,j));
ENDDATA
MIN=@SUM(link:d*x);
@for(city(j):@sum(city(i)|j#ne#i:x(i,j))=1);
@for(city(i):@sum(city(j)|j#ne#i:x(i,j))=1);
@for(link(i,j)|i#ne#j#and#i#gt#1:u(i)-u(j)+10*x(i,j) |