华北科技学院基础部综合性实验
实验报告
课程名称运筹学B
实验学期 2011 至 2012 学年第 2 学期学生所在系部基础部
年级 09 专业班级计算B091班
学生姓名张成林学号 200909014101 任课教师孙士国
实验成绩
《 运筹学B 》课程综合性实验报告
开课实验室： 数学应用实验室 2012 年 6 月 13 日
实验题目
TSP 问题
一、实验目的
1）领会TSP 问题的理论和方法。

2）会编制上述方法的基于lingo 语言的计算程序，并用来求解有关问题。

3）熟悉求解TSP 问题的有关方法和理论。

4）针对所给问题编制程序，并上机计算其所需要的结果。

二、设备与环境
Lingo11.0 软件等
三、实验内容及要求
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 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 为下三角矩阵，ij d 表示城市i 与城市j 之间的距离。

设0--1矩阵s 用来表示经过的各城市之间的路线。

设
⎩⎨
⎧=j
i j i s ij 到城市若从城市到城市若不从城市1
则该TSP 问题转化为如下线性模型：
∑∑=-==
n i i j ij
ij d s
Z 21
1
min
112..2
2,3,,01j j ik ji k i
j i ij
s s t s s i n s ><>⎧=⎪⎪+==⎨⎪⎪=⎩∑∑∑ 或
2．算法设计与实现
程序如下：
!TSP quesion;
MODEL:
SETS:
city/1..10/;
link(city,city)|&1#GT#&2:d,s;
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*s);
@SUM(city(j)|j#GT#1:S(j,1))=2; !与第1个城市相连的有两个城市;
@FOR(city(i)|i#GT#1:@SUM(city(j)|j#GT#i:s(j,i))+@SUM(city(k) |k#LT#i:s(i,k))=2); !与第i个城市相连有两个城市;
@FOR(link:@BIN(s));
四、实验结果及分析
模型结果如图1所示
图1
由图1可知：
S(3,2)=1,S(4,1)=1,S(4,3)=1,S(6,5)=1,S(7,2)=1,S(7,5)=1,S(8,6)=1,S(9, 1)=1,S(10,8)=1,S(10,9)=1。

其它全为0。

其最短路线为1—4—3—2—7—5—6—8—10—9—1，最短距离为77公里。

五、总结
通过本次综合实验，我熟悉了TSP最短路问题的理论和方法，代码实现了其算法和功能，收获很大。

开始设计之时完全没头绪，对与理论学习不够扎实的我深感“书到用时方恨少”只好再把书上介绍的相关知识重新阅读一遍，对知识进行了全面而系统的梳理，遇到难处首先是苦思冥想寻求方法，再向同学请教，终于熟练掌握了基本理论知识，而且领悟了诸多平时学习难以理解掌握的的较难的知识。

在这次的综合实验中不仅检验了我所学习的知识，也培养了我如何去把握一件事情，如何去做一件事情，又如何完成一件事情。

在实验过程中，和同学们相互探讨，相互学习，相互监督，获益匪浅。

教师评
评定项目 A B C D 评定项目 A B C D 问题分析清楚模型正确
算法正确运行结果正确
结果解释合理操作熟练
文字流畅报告规范
其他：
评价教师签名：
年月日。