TSP问题及LINGO求解技巧
    巡回旅行商问题(Traveling Salesman Problem，TSP)，也称为货郎担问题。最早可以追溯到1759年Euler提出的骑士旅行问题。1948年，由美国兰德公司推动，TSP成为近代组合优化领域的一个典型难题。它已经被证明属于NP难题。
  用图论描述TSP，给出一个图，每边上有非负权值,寻G的Hamilton圈C，使得C的总权最小.
  几十年来，出现了很多近似优化算法。如近邻法、贪心算法、最近插入法、最远插入法、模拟退火算法以及遗传算法。这里我们介绍利用LINGO软件进行求解的方法。
问题1  设有一个售货员从10个城市中的某一个城市出发，去其它9个城市推销产品。10个城市相互距离如下表。要求每个城市到达一次仅一次后，回到原出发城市。问他应如何选择旅行路线，使总路程最短。
                    表1    10个城市距离表
城市
1
2
3
4
5
6
7
8
9
10
1
0
7
4
5
8
6
12
13
11
18
2
7
0
3
10
9
14
5
14
17
17
3
4
3
0
5
9
10
21
8
27
12
4
5
10
5
0
14
9
10
9
23
16
5
8
9
9
14
0
7
8
7
20
19
6
6
14
10
9
7
0
13
5
25
13
7
12
5
21
10
8
13
0
23
21
18
8
13
14
8
9
7
5
23
0
18
12
9
11
17
27
23
20
25
21
18
0
16
10
18
17
12
16
19
13
18
12
16
0
我们采用线性规划的方法求解
设城市之间距离用矩阵来表示，表示城市与城市之间的距离。设0--1矩阵用来表示经过的各城市之间的路线。设
考虑每个城市后只有一个城市，则：
 
考虑每个城市前只有一个城市，则：
  ；
但仅以上约束条件不能避免在一次遍历中产生多于一个互不连通回路。
为此我们引入额外变量，附加以下充分约束条件：    ；
    该约束的解释：
    如与不会构成回路，若构成回路，有：
    ，，则：
    ，，从而有：
    ，导致矛盾。
    如，与不会构成回路，若构成回路，有：
    ，，则：
    ，，从而有：
    ，导致矛盾。
  其它情况以此类推。
于是我们可以得到如下的模型：
前面问题的Lingo程序
!TSP quesion;
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); !城市j前有一个城市相连;
  @for(city(i):@sum(city(j)|j#ne#i:x(i,j))=1); !城市i后前有一个城市相连;
  @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
得到的结果如下：  X(3,2)=1,X(4,1)=1,X(4,3)=1,X(6,5)=1,X(7,2)=1,X(7,5)=1,X(8,6)=1,X(9,1)=1,X(10,8)=1,X(10,9)=1。其它全为0。
其最短路线为1—4—3—2—7—5—6—8—10—9—1，最短距离为77公里。
问题2．2005年电工杯B题比赛项目排序问题
全民健身计划是1995年在国务院领导下，由国家体委会同有关部门、各众组织和社会团体共同推行的一项依托社会、全民参与的体育健身计划，是与实现社会主义现代化目标相配套的社会系统工程和跨世纪的发展战略规划。现在，以全民健身为主要内容的众性体育活动蓬勃开展，举国上下形成了全民健身的热潮，人民众健康水平不断提高，同时也扩大了竞
技体育的社会影响，提高了竞技体育水平。现在各级、各类、各种运动比赛比比皆是，这不但提高了全民的身体素质，而且使一批运动员脱颖而出，成为运动健将，为国家争得了荣誉。
在各种运动比赛中，为了使比赛公平、公正、合理的举行，一个基本要求是：在比赛项目排序过程中，尽可能使每个运动员不连续参加两项比赛，以便运动员恢复体力，发挥正常水平。
1．表2是某个小型运动会的比赛报名表。有14个比赛项目，40名运动员参加比赛。表中第1行表示14个比赛项目，第1列表示40名运动员，表中“＃”号位置表示运动员参加此项比赛。建立此问题的数学模型，并且合理安排比赛项目顺序，使连续参加两项比赛的运动员人次尽可能的少；
2．文件“运动员报名表”中给出了某个运动比赛的报名情况。共有61个比赛项目，1050人参加比赛。请给出算法及其框图，同时给出合理的比赛项目排序表，使连续参加两项比赛的运动员人次尽可能的少；
3．说明上述算法的合理性；
4．对“问题2”的比赛排序结果，给出解决“运动员连续参加比赛”问题的建议及方案。
表2  某小型运动会的比赛报名表
项目
运动员
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1
#
#
fopen中文路径问题#
#
2
#
#
#
3
#
#
#
4
#
#
#
5
#
#
#
6
#
#
7
#
#
8
#
#
9
#
#
#
#
10
#
#
#
#
11
#
#
#
#
12
#
#
13
#
#
#
14
#
#
#
15
#
#
#
16
#
#
#
17
#
#
18
#
#
19
#
#
20
#
#
21
#
#
22
#
#
23
#
#
24
#
#
#
#
25
#
#
#
26
#
#
27
#
#
28
#
#
 
29
#
#
#
30
 
#
#
31
#
#
#
32
#
#
33
#
#
34
#
#
#
#
35
#
#
#
36
#
#
37
#
#
#
38
#
#
#
#
39
#
#
#
#
40
#
#
#
#
问题一解答：
若项目和项目相邻，可以计算出同时参加这两个项目的人数，作为和的距离。则问题转化为求项目1到项目14的一个排列，使相邻距离和最小。我们采用TSP问题求解。但由于开始项目和结束项目没有连接，可考虑引入虚拟项目15，该虚拟项目与各个项目的距离都为0。
距离矩阵的求法：
该报名表用矩阵表示。
则
 
  另外
  由于问题1中40个运动员参加14个项目的比赛是word表，可将其拷贝到Excel表中，然后将#替换为1，将空格替换为0，形成0-1表，并拷贝到数据文件中。问题2中1050个运动员参加的61个项目比赛的Access数据库中的表保存为Excel表，然后在表中将#替换为1，将空格替换为0，形成0-1表，并拷贝到数据文件中。
在Matlab中编制如下程序形成距离矩阵。
load table1.txt;
a=table1;
[m,n]=size(a);
d=zeros(n+1,n+1);  %定义距离矩阵;
for i=1:n
for j=1:n             
  for k=1:m
  d(i,j)=d(i,j)+a(k,i)*a(k,j);  %计算不同项目之间距离
  end
end
end
for i=1:n+1
    d(i,i)=0;
end   
  %输出文件
fid=fopen('dis1.txt','w');
for i=1:n+1
for j=1:n+1
  fprintf(fid,'%1d ',d(i,j));
  end
fprintf(fid,'\n');
end 
fclose(fid);
输出的距离矩阵为：
0  2  1  2  0  0  1  0  1  2  1  1  1  1  0
2  0  1  4  1  0  1  1  1  3  1  0  2  1  0
1  1  0  1  0  0  0  3  1  1  0  2  2  1  0

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。