lingo怎么解决TSP问题比如我已知A,B,C,D.之间的距离,求最小解,写出程序,
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/25 11:39:30
lingo怎么解决TSP问题比如我已知A,B,C,D.之间的距离,求最小解,写出程序,
lingo怎么解决TSP问题
比如我已知A,B,C,D.之间的距离,求最小解,写出程序,
lingo怎么解决TSP问题比如我已知A,B,C,D.之间的距离,求最小解,写出程序,
这段程序是关于13个城市的tsp问题的程序,一般解决更多城市的tsp问题,有蚁群,神经网络,和模拟退火等方法,这里给出lingo的程序,算作抛砖引玉吧.
MODEL:
SETS:
city/A1..A13/:U;!U(i)=cicy No;
links(city,city):distance,!the distance of the matrix;
X;!x(i,j)=1 if we use link i,j;
ENDSETS
DATA:!distance matrix;
!10000,the distance of impossible link;
distance= 0,62,92,73,10000,10000,10000,10000,10000,10000,10000,10000,10000,
62,0,10000,10000,58,10000,10000,10000,10000,10000,10000,10000,10000,
92,10000,0,10000,10000,52,57,10000,10000,10000,10000,10000,10000,
73,10000,10000,0,10000,10000,59,10000,10000,10000,10000,10000,10000,
10000,58,10000,10000,0,10000,10000,104,10000,10000,10000,10000,10000,
10000,10000,52,10000,10000,0,10000,10000,85,104,10000,77,10000,
10000,10000,57,59,10000,10000,0,10000,81,10000,10000,10000,10000,
10000,10000,10000,10000,104,10000,10000,0,10000,115,166,10000,10000,
10000,10000,10000,10000,10000,85,81,10000,0,10000,10000,10000,63,
10000,10000,10000,10000,10000,104,10000,115,10000,0,10000,10000,10000,
10000,10000,10000,10000,10000,10000,10000,166,10000,10000,0,87,73,
10000,10000,10000,10000,10000,77,10000,10000,10000,10000,87,0,10000,
10000,10000,10000,10000,10000,10000,10000,10000,63,10000,73,10000,0;
ENDDATA
n=@SIZE(city);
!minimize total distance of the links;
MIN=@SUM(links:distance*X);
!the entrance;
@FOR(city(k):
@SUM(city(i)|i#ne#k:x(i,k))=1;
!it must be departed;
@SUM(city(j)|j#ne#k:x(k,j))=1;
@FOR(city(j)|j#gt#1 #and# j#ne#k:U(j)>=U(k)+X(k,j)-(N-2)*(1-X(k,j))+(N-3)*X(j,k)););
@FOR(links:@BIN(x)); !it makes the x's 0 or 1;
@FOR(city(k)|k#gt#1:
U(k)=1+(N-2)*X(k,1));
END