LINGO 课程试验专题——TSP
前言：TSP 问题，即巡回旅行商问题，也称为货担郎问题，早期是1759年Euler 提出的骑士旅行问题。
1948年，有美国兰德公司推动，成为近代组合优化问题中的一个典型难题，它被证明为是NP 难题。
图论描述就是给定一个有向或者是无向的图，并给定他们各边的权值，找一个Hamilton 圈使得总权最小。
例：设有一个销售员从10个城市中的某一个城市出发，去其他的9个城市推销产品。
10个城市相互距离如下表所示。
要求每个城市到达且仅到达一次，回到
方法一：设城市之间的距离用矩阵d 来表示，其中d 为下三角矩阵，ij d 表示城市i 与城市j 之间的距离。
设0-1矩阵x 用来表示经过的各城市之间的路线。
设
01ij i j x i j
⎧=⎨⎩若城市不到城市若城市到城市则建立该TSP 问题的模型如下:
()
1
21121min ..22,3,4,...,01n i ij ij
i j j j ik ji k i
j i ij
z x d x s t x x i n x -===><>=⎧⎪⎪+==⎨⎪⎪=⎩∑∑∑∑∑或 它的主要思想就是与第一个城市相连的有两个城市，与第i 个城市相连的有两个城市，每个城市都有相连的两个城市，这个自然就够成一个Hamilton 圈，但是不保证有多个圈的情况。
LINGO 具体程序如下：
model:
sets:
city/1..10/;
link(city,city)|&1#GT#&2:d,x;
endsets
data:
d=7
4 3
5 10 5
8 9 9 14
6 14 10 9 7
12 5 21 10 8 13
13 14 8 9 7 5 23
11 17 27 23 20 25 21 18
18 17 12 16 19 13 18 12 16;
enddata
min=@sum(link:d*x);@sum(city(j)|j#GT#1:x(j,1))=2;
@for(city(i)|i#GT#1:@sum(city(j)|j#GT#i:x(j,i))+@sum(city(k)|k#LT#i:x(i,k))=2);@for(link:@bin(x));
得到的结果：
Global optimal solution found.
Objective value: 77.00000
Objective bound: 77.00000
Infeasibilities: 0.000000 Extended solver steps: 0
Total solver iterations: 12
结果分析：从这个结果我们可以看出，该TSP 问题的最短距离是77km ，其最短路线为：143275681091→→→→→→→→→→。
该方法将TSP 问题求解化为线性规划，用LINGO 求解。
求解速度极快，但是可能会形成一个子圈，没有办法得到真正的最优解。
方法二:设城市之间的距离用矩阵d 来表示，ij d 表示城市i 到城市j 之间的距离。
设0-1矩阵x 用来表示经过的各城市之间的路线。
设
01,ij i j x i j i j ⎧=⎨⎩
若城市不到城市若城市到城市且在前 考虑每个城市前只有一个城市
1,1n ij j j i x =≠=∑ 1,2,3,...,i n =
每个城市后也只有一个城市
1,1n ij i i j x =≠=∑ 1,2,3,...,j n =
但是仅仅只有以上的条件是不能避免在一次遍历当中产生多于一个互不连通的回路，因此我们要加入约束条件，引入额外变量(1,2,3,...,)i u i n =,即1,1i j ij u u nx n i j n -+≤-<≠≤
对于该约束的解释是:
一方面i 与j 不会构成回路，若构成回路，有1,1,ij ji x x ==则1,1i j j i u u u u -≤--≤-，从而有02≤-，导致矛盾。
另一方面i ，j 与k 不会构成回路，若构成回路，有1,1,1,ij jk ki x x x ===则有1,1,1,i j j k k i u u u u u u -≤--≤--≤-从而有03≤-，导致矛盾。
其他情况以此类推。
于是就可以得到此方法的求解模型：
Variable Value Reduced Cost X( 3, 2) 1.000000 3.000000
X( 4, 1) 1.000000 5.000000
X( 4, 3) 1.000000 5.000000
X( 6, 5) 1.000000 7.000000
X( 7, 2) 1.000000 5.000000
X( 7, 5) 1.000000 8.000000
X( 8, 6) 1.000000 5.000000
X( 9, 1) 1.000000 11.00000
X( 10, 8) 1.000000 12.00000
X( 10, 9) 1.000000 16.00000
,11,1,min 1,1,2,3,...,1,1..
01,1,2,3,...,1,1,2,3,...,1,2,3,...,n ij ij i j n
ij i i j
i j ij ij n ij j j i i z d x
x j n
u u nx n i j n s t x i j n x i n u i n ==≠=≠=
⎧==⎪⎪⎪-+≤-<≠≤⎪⎪===⎨⎪⎪==⎪⎪=⎪⎩∑∑∑或，为实数，
编写的LINGO 程序如下：
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;
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)<=9);
@for(link:@bin(x));
end
运行结果显示：
Global optimal solution found.
Objective value: 77.00000
Objective bound: 77.00000
Infeasibilities: 0.000000
Extended solver steps: 0
Total solver iterations: 785
Variable Value Reduced Cost
X( 1, 4 ) 1.000000 5.000000
X( 2, 7) 1.000000 5.000000
X( 3, 2) 1.000000 3.000000
X( 4, 3) 1.000000 5.000000
X( 5, 6) 1.000000 7.000000
X( 6, 8) 1.000000 5.000000
X( 7, 5) 1.000000 8.000000
X( 8, 10) 1.000000 12.00000
X( 9, 1) 1.000000 11.00000
X( 10, 9) 1.000000 16.00000
结果分析：从该结果可以看出，与方法一得到的结果相同，它的优点是可以很好的解决圈的问题，不会出现有子圈的问题；缺点是对规模较大的问题的计算非常耗时。
心得体会：学习LINGO后，觉得有些数学问题变得更简单了，例如以前解决TSP 问题我们采用是纯计算方式：蛮力法，回溯法等，现在采用计算机，充分发扬了计算机与数学的结合，讲计算机与数学整合到一块，这是现代社会所需要的综合型人才息息相关，所以学习lingo是大学里面和工作比较接近的科目，所以我觉得lingo真好！。