旅行商问题数学建模.docx
《旅行商问题数学建模.docx》由会员分享，可在线阅读，更多相关《旅行商问题数学建模.docx（15页珍藏版）》请在冰点文库上搜索。
旅行商问题数学建模
黄石理工学院
数学建模大型作业
2011—2012学年第1学期
一．摘要
二．旅行问题
1.问题描述
2.符号说明
3.模型设计
4.建模求解
5.模型分析
6.
三．建模过程及心得体会
四．参考文件
一．摘要
本文是一个围绕旅行商问题和背包问题这两个经典问题的论文。
问题一，是一个依赖与每个城市去一次且仅去一次的路线确定问题，问题二类似于问题一。
问题三是一个依赖于可背重量限制的背包问题。
关键词：
HAMILTON回路LINGO最优旅行路线0-1模型
二．旅行问题
问题描述
某人要在假期内从城市A出发，乘火车或飞机到城市B,C,D,E,F旅游购物。
他计划走遍这些城市各一次且仅一次，最后返回城市A。
已知城市间的路费数据见附表1，请你设计一条旅行路线使得他的总路费最少。
如果临行他因故只能去4个城市，该怎样修订旅行路线？
在城市间旅游时他计划购买照相机，衣服，书籍，摄像机，渔具，白酒，食品，而受航空行李重量的限制以及个人体力所限，所买物品的总重量不能超过15kg，各种物品的价格见附表2.请你为他决策买哪些物品，使所买物品价值最大。
附表1：
A
B
C
D
E
F
A
0
120
250
330
210
150
B
120
0
98
350
225
300
C
250
98
0
520
430
280
D
330
350
520
0
270
185
E
210
225
430
270
0
420
F
150
300
280
185
420
0
附表2
照相机
衣服
书籍
摄像机
渔具
白酒
食品
香烟
重量（kg）
1
2
4
3
4
2
2
1
价格（元）
1300
2750
320
4350
1400
300
120
600
模型设计
首先给出一个定义：
设v1,v2,......,vn是图G中的n个顶点，若有一条从某一顶点v1出发，经过各节点一次且仅一次，最后返回出发点v1的回路，则称此回路为HAMILTON回路。
问题1.
分析：
这个优化问题的目标是使旅行的总费用最少，要做的决策是如何设定旅行路线，决策受的约束条件：
每个城市都必须去，但仅能去一次。
按题目所给，将决定变量，目标函数和约束条件用数学符号及式子表示出来，就可得一下模型。
模型建立：
对于6个城市的旅行问题设A,B,C,D,E,F六个城市分别对应v1,v2,v3,v4,v5,v6。
假设
表示从城市i到城市j的费用。
定义0-1整数型变量
=1表示从城市i旅行到城市j，否则
=0。
则旅行问题的数学模型可表示为一个整数规划问题。
minz=
（i
j）
s.t.
=1（i
j；j=1,2,……,6）
=1（i
j；i=1,2,……,6）
（i
j;i=2,3,……,6;j=2,3,……6）
其中辅助变量
（i=2,3,……,6）可以是连续变化的，虽然这些变量在最优解中取普通的整数值（从而在约束条件中，可以限定这些变量为整数）。
事实上，在最优解中，
=访问城市的顺序数。
模型求解
运用LINGO，输入程序：
MODEL:
!
TravelingSalesProblemforthecitiesofsixcity;
SETS:
CITY/1..6/:
U;!
U（I）=sequenceno.ofcity;
LINK（CITY,CITY）:
COST,!
Thecostmatrix;
X;!
X（I,J）=1ifweuselinkI,J;
ENDSETS
DATA:
!
Costmatrix,itneednotbesymmetric;
COST=0120250330210150
120098350225300
250980520430280
3303505200270185
2102254302700420
1503002801854200;
ENDDATA
N=@SIZE（CITY）;
MIN=@SUM（LINK:
COST*X）;
@FOR（CITY（K）:
!
Itmustbeentered;
@SUM（CITY（I）|I#NE#K:
X（I,K））=1;
!
Itmustbedeparted;
@SUM（CITY（J）|J#NE#K:
X（K,J））=1;
!
Weakformofthesubtourbreakingconstrains;
!
Thesearenotverypowerfulforlargeproblems;
@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（LINK:
@BIN（X））;!
MaketheX's0/1;
!
Forthefirstandlaststopweknow...;
@FOR（CITY（K）|K#GT#1:
U（K）<=N-1-（N-2）*X（1,K）;
U（K）>=1+（N-2）*X（K,1））;
END
得到结果：
总费用为1163
路线：
A-B-C-F-D-E-A
问题2.
临时因故只能去4个城市，那么应该怎样安排旅行路线。
分析：
在B,C,D,E,F五个城市中选4个城市，显然有5种可能，按照问题一中的模型，将费用矩阵稍作修改，运用LINGO分别解除5种可能的费用，进行比较，即得结果。
（1）选取B,D,E,F，计算旅行费用：
MODEL:
!
TravelingSalesProblemforthecitiesofsixcity;
SETS:
CITY/1..5/:
U;!
U（I）=sequenceno.ofcity;
LINK（CITY,CITY）:
COST,!
Thecostmatrix;
X;!
X（I,J）=1ifweuselinkI,J;
ENDSETS
DATA:
!
Costmatrix,itneednotbesymmetric;
COST=0120330210150
1200350225300
3303500270185
2102252700420
1503001854200;
ENDDATA
N=@SIZE（CITY）;
MIN=@SUM（LINK:
COST*X）;
@FOR（CITY（K）:
!
Itmustbeentered;
@SUM（CITY（I）|I#NE#K:
X（I,K））=1;
!
Itmustbedeparted;
@SUM（CITY（J）|J#NE#K:
X（K,J））=1;
!
Weakformofthesubtourbreakingconstrains;
!
Thesearenotverypowerfulforlargeproblems;
@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（LINK:
@BIN（X））;!
MaketheX's0/1;
!
Forthefirstandlaststopweknow...;
@FOR（CITY（K）|K#GT#1:
U（K）<=N-1-（N-2）*X（1,K）;
U（K）>=1+（N-2）*X（K,1））;
END
得到结果：
总费用：
950
路线：
A-B-E-D-F-A
（2）选取B,C,E,F，计算旅行费用：
MODEL:
!
TravelingSalesProblemforthecitiesofsixcity;
SETS:
CITY/1..5/:
U;!
U（I）=sequenceno.ofcity;
LINK（CITY,CITY）:
COST,!
Thecostmatrix;
X;!
X（I,J）=1ifweuselinkI,J;
ENDSETS
DATA:
!
Costmatrix,itneednotbesymmetric;
COST=0120250210150
120098225300
250980430280
2102254300420
1503002804200;
ENDDATA
N=@SIZE（CITY）;
MIN=@SUM（LINK:
COST*X）;
@FOR（CITY（K）:
!
Itmustbeentered;
@SUM（CITY（I）|I#NE#K:
X（I,K））=1;
!
Itmustbedeparted;
@SUM（CITY（J）|J#NE#K:
X（K,J））=1;
!
Weakformofthesubtourbreakingconstrains;
!
Thesearenotverypowerfulforlargeproblems;
@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（LINK:
@BIN（X））;!
MaketheX's0/1;
!
Forthefirstandlaststopweknow...;
@FOR（CITY（K）|K#GT#1:
U（K）<=N-1-（N-2）*X（1,K）;
U（K）>=1+（N-2）*X（K,1））;
END
得到结果：
总费用：
963
路线：
A-E-B-C-F-A
（3）选取B,C,D,F,计算旅行费用：
MODEL:
!
TravelingSalesProblemforthecitiesofsixcity;
SETS:
CITY/1..5/:
U;!
U（I）=sequenceno.ofcity;
LINK（CITY,CITY）:
COST,!
Thecostmatrix;
X;!
X（I,J）=1ifweuselinkI,J;
ENDSETS
DATA:
!
Costmatrix,itneednotbesymmetric;
COST=0120250330150
120098350300
250980520280
3303505200185
1503002801850;
ENDDATA
N=@SIZE（CITY）;
MIN=@SUM（LINK:
COST*X）;
@FOR（CITY（K）:
!
Itmustbeentered;
@SUM（CITY（I）|I#NE#K:
X（I,K））=1;
!
Itmustbedeparted;
@SUM（CITY（J）|J#NE#K:
X（K,J））=1;
!
Weakformofthesubtourbreakingconstrains;
!
Thesearenotverypowerfulforlargeproblems;
@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（LINK:
@BIN（X））;!
MaketheX's0/1;
!
Forthefirstandlaststopweknow...;
@FOR（CITY（K）|K#GT#1:
U（K）<=N-1-（N-2）*X（1,K）;
U（K）>=1+（N-2）*X（K,1））;
END
得到结果：
总费用：
1013
路线：
A-B-C-F-D-A
（4）选取路线:
B,C,D,E,计算旅行费用：
MODEL:
!
TravelingSalesProblemforthecitiesofsixcity;
SETS:
CITY/1..5/:
U;!
U（I）=sequenceno.ofcity;
LINK（CITY,CITY）:
COST,!
Thecostmatrix;
X;!
X（I,J）=1ifweuselinkI,J;
ENDSETS
DATA:
!
Costmatrix,itneednotbesymmetric;
COST=0120250330210
120098350225
250980520430
3303505200270
2102254302700;
ENDDATA
N=@SIZE（CITY）;
MIN=@SUM（LINK:
COST*X）;
@FOR（CITY（K）:
!
Itmustbeentered;
@SUM（CITY（I）|I#NE#K:
X（I,K））=1;
!
Itmustbedeparted;
@SUM（CITY（J）|J#NE#K:
X（K,J））=1;
!
Weakformofthesubtourbreakingconstrains;
!
Thesearenotverypowerfulforlargeproblems;
@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（LINK:
@BIN（X））;!
MaketheX's0/1;
!
Forthefirstandlaststopweknow...;
@FOR（CITY（K）|K#GT#1:
U（K）<=N-1-（N-2）*X（1,K）;
U（K）>=1+（N-2）*X（K,1））;
END
得到结果：
总费用：
1173
路线:
A-C-B-E-D-A
（5）选取C,D,E,F,计算旅行费用：
MODEL:
!
TravelingSalesProblemforthecitiesofsixcity;
SETS:
CITY/1..5/:
U;!
U（I）=sequenceno.ofcity;
LINK（CITY,CITY）:
COST,!
Thecostmatrix;
X;!
X（I,J）=1ifweuselinkI,J;
ENDSETS
DATA:
!
Costmatrix,itneednotbesymmetric;
COST=0250330210150
2500520430280
3305200270185
2104302700420
1502801854200;
ENDDATA
N=@SIZE（CITY）;
MIN=@SUM（LINK:
COST*X）;
@FOR（CITY（K）:
!
Itmustbeentered;
@SUM（CITY（I）|I#NE#K:
X（I,K））=1;
!
Itmustbedeparted;
@SUM（CITY（J）|J#NE#K:
X（K,J））=1;
!
Weakformofthesubtourbreakingconstrains;
!
Thesearenotverypowerfulforlargeproblems;
@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（LINK:
@BIN（X））;!
MaketheX's0/1;
!
Forthefirstandlaststopweknow...;
@FOR（CITY（K）|K#GT#1:
U（K）<=N-1-（N-2）*X（1,K）;
U（K）>=1+（N-2）*X（K,1））;
END
得到结果：
总费用：
1195
路线：
A-C-F-D-E-A
因此，总结以上
（1），
（2），（3），（4），（5）五种情况可得:
应该选用路线：
A-B-E-D-F-A。
总费用花费最少，为950.
问题3.
在城市间旅游时他计划购买照相机、衣服、书籍、摄像机、渔具、白酒、食品、香烟等物品，而受航空行李重量的限制以及个人体力所限，所买物品的总重量不能超过15kg，各种物品的价格见附表2。
请你为他决策买哪些物品，使所买物品总价值最大？
分析:
解读题意，实际上此题涉及背包问题，题目转化为一个限重15公斤的背包，要求在8件可带可不带的物品中做出合理的方法。
模型建立：
将照相机，衣服，书籍，摄像机，渔具，酒，食品和香烟编号为1，2，3，4，5，6，7，8。
设总容量为b,
为每个物品的重量，
为每个物品各自的价格。
定义一个变量
，当
=1是，表示装第i件物品，当
=0时，则不装（i=1,2,……,8）.
则约束条件为：
maxz=
=0或1，（i=1,2,……,8）
模型求解：
利用LINGO软件求解，在LINGO中输入以下程序：
model:
sets:
M/1..8/:
W;
price/1..8/:
p;
number/1..8/:
x;
endsets
data:
W=1,2,4,3,4,2,2,1;
P=1300,2750,320,4350,1400,300,120,600;
enddata
MAX=@SUM（M:
X*P）;
@SUM（M:
X*W）<=15;
@FOR（M:
@BIN（X））;
End
得到结果：
选择照相机，衣服，摄像机，渔具，酒，食品和香烟，最大价值为10820。
三．建模过程及心得体会
数学建模是一个经历观察、思考、归类、抽象与总结的过程，也是一个信息捕捉、筛选、整理的过程，更是一个思想与方法的产生与选择的过程。
它给学生再现了一种“微型科研”的过程。
数学建模教学有利于激发学生学习数学的兴趣，丰富学生数学探索的情感体验；有利于学生自觉检验、巩固所学的数学知识，促进知识的深化、发展；有利于学生体会和感悟数学思想方法。
同时教师自身具备数学模型的构建意识与能力，才能指导和要求学生通过主动思维，自主构建有效的数学模型，从而使数学课堂彰显科学的魅力。
为了使描述更具科学性，逻辑性，客观性和可重复性，人们采用一种普遍认为比较严格的语言来描述各种现象，这种语言就是数学。
使用数学语言描述的事物就称为数学模型。
有时候我们需要做一些实验，但这些实验往往用抽象出来了的数学模型作为实际物体的代替而进行相应的实验，实验本身也是实际操作的一种理论替代。
数学建模要有团队精神。
数学建模不是一个人的事，是团队的一项活动。
三个人要相互支持，相互鼓励。
不能只管自己的那一部分。
特别是模型的建立，一个人根本不可能想的那么全面，只有大家一起讨论才能把问题搞清楚。
必须合理的安排时间。
做任何事情，合理的时间安排非常重要，建模也是一样，事先要做好一个规划，建模一共分十个板块。
你每天昨晚哪几个板块事先要确定好，这样做才会使自己游刃有余，保证在规定的时间内完成论文，以避免在时间上的不妥，以至于最后无法完成论文。
有些同学经常会借鉴一些别人的论文里的思想，然后变成自己的东西，不过那也是一种能力，不能小瞧。
所以也要多看些别人的论文来调高自己。
四．参考文件。
【1】.运筹学，科学出版社，徐玖平，胡知能，2003年11月第一版
【2】.运筹学——数据，模型，决策，科学出版社，徐玖平，胡知能，2006年3月第一版
升级会员 