TSP问题《运筹学》综合性实验报告.docx

华北科技学院基础部综合性实验
实验报告
课程名称运筹学B
实验学期2011至2012学年第2学期
学生所在系部
基础部
年级09
专业班级
计算B091班
学生姓名
张成林
学号200909014101
任课教师
华北科技学院基础部综合性实验
实验报告
课程名称运筹学B
实验学期2011至2012学年第2学期
学生所在系部
基础部
年级09
专业班级
计算B091班
学生姓名
张成林
学号200909014101
任课教师
孙士国
实验成绩
华北科技学院综合性实验报告
第1页
2012年6月13日
《运筹学B》课程综合性实验报告
开课实验室：数学应用实验室
实验题目TSP问题
一、实验目的
1）领会TSP问题的理论和方法。
2）会编制上述方法的基于lingo语言的计算程序，并用来求解有关问题。
3）熟悉求解TSP问题的有关方法和理论。
4）针对所给问题编制程序，并上机计算其所需要的结果。
二、设备与环境

三、实验内容及要求
TSP问题1
设有一个售货员从10个城市中的某一个城市出发，去其它9个城市推销产品。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
A
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
1•问题分析与建模：
设城市之间距离用矩阵d来表示，其中d为下三角矩阵，d..表示城市i与城市j之j
间的距离。设0--1矩阵s用来表示经过的各城市之间的路线。设
'0若不从城市i到城市j
S=5
[1若从城市i到城市j
则该TSP问题转化为如下线性模型:
-ryyyiT门
minZ=乙乙sd
ijij
i=2j=1
rEs=2
j1
ys+ys=2i=2,3,
ikji
k<ij〉i
s=0或1
iij
华北科技学院综合性实验报告
第4页

程序如下：
!TSPquesion;
MODEL:
SETS:city/1..1O/;link(city,city)|&1#GT#&2:d,s;ENDSETS
DATA:
d=7
4
3
5
10
5
8
9
9
14