旅行商问题数学建模

1、黄石理工学院 数学建模 大型作业 20112012 学年 第1学期目录一摘要二旅行问题1. 问题描述2. 符号说明3. 模型设计4. 建模求解5. 模型分析6.三建模过程及心得体会四参考文件一摘要本文是一个围绕旅行商问题和背包问题这两个经典问题的论文。问题一，是一个依赖与每个城市去一次且仅去一次的路线确定问题，问题二类似于问题一。问题三是一个依赖于可背重量限制的背包问题。关键词：HAMILTON回路 LINGO 最优旅行路线 0-1模型二旅行问题问题描述 某人要在假期内从城市A出发，乘火车或飞机到城市B,C,D,E,F旅游购物。他计划走遍这些城市各一次且仅一次，最后返回城市A。已知城市间的路费

2、数据见附表1，请你设计一条旅行路线使得他的总路费最少。如果临行他因故只能去4个城市，该怎样修订旅行路线？ 在城市间旅游时他计划购买照相机，衣服，书籍，摄像机，渔具，白酒，食品，而受航空行李重量的限制以及个人体力所限，所买物品的总重量不能超过15kg，各种物品的价格见附表2.请你为他决策买哪些物品，使所买物品价值最大。附表1：ABCDEFA0120250330210150B120098350225300C250980520430280D3303505200270185E2102254302700420F1503002801854200附表2照相机衣服书籍摄像机渔具白酒食品香烟重量（kg）1243

3、4221价格(元)1300275032043501400300120600 模型设计首先给出一个定义：设v1,v2,.,vn是图G中的n个顶点，若有一条从某一顶点v1出发，经过各节点一次且仅一次，最后返回出发点v1的回路，则称此回路为HAMILTON回路。 问题1.分析：这个优化问题的目标是使旅行的总费用最少，要做的决策是如何设定旅行路线，决策受的约束条件：每个城市都必须去，但仅能去一次。按题目所给，将决定变量，目标函数和约束条件用数学符号及式子表示出来，就可得一下模型。 模型建立：对于6个城市的旅行问题设A,B,C,D,E,F六个城市分别对应v1,v2,v3,v4,v5,v6。假设表示从城市

4、i到城市j的费用。定义0-1整数型变量=1表示从城市i旅行到城市j，否则=0。则旅行问题的数学模型可表示为一个整数规划问题。 min z= (ij) s.t. =1 （ij；j=1,2,6） =1 (ij；i=1,2,6) (ij;i=2,3,6;j=2,3,6)其中辅助变量（i=2,3,6）可以是连续变化的，虽然这些变量在最优解中取普通的整数值（从而在约束条件中，可以限定这些变量为整数）。事实上，在最优解中，=访问城市的顺序数。模型求解运用LINGO，输入程序：MODEL:!Traveling Sales Problem for the cities of six city;SETS: CI

5、TY / 1.6/: U; ! U( I) = sequence no. of city; LINK( CITY, CITY): COST, ! The cost matrix; X; ! X( I, J) = 1 if we use link I, J;ENDSETSDATA: !Cost matrix, it need not be symmetric; COST= 0 120 250 330 210 150 120 0 98 350 225 300 250 98 0 520 430 280 330 350 520 0 270 185 210 225 430 270 0 420 150 3

6、00 280 185 420 0 ;ENDDATA N= SIZE( CITY); MIN= SUM( LINK: COST * X); FOR( CITY( K): !It must be entered; SUM( CITY( I)| I #NE# K: X( I, K) = 1;! It must be departed; SUM( CITY( J)| J #NE# K: X( K, J) = 1;!Weak form of the subtour breaking constrains;!These are not very powerful for large problems; F

7、OR( 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); !Make the Xs 0/1;! For the first and last stop we know.;FOR( CITY( K)| K #GT# 1: U( K) = 1 + ( N - 2) * X( K, 1);END得到结果：总费用为1163路线：A-B-C-F-D-E-A问题2.临时因故只能去4个城市，那么应该怎样安排旅行路线。分析：在B,C,D,E,F五个城市中选

8、4个城市，显然有5种可能，按照问题一中的模型，将费用矩阵稍作修改，运用LINGO分别解除5种可能的费用，进行比较，即得结果。（1）选取B,D,E,F，计算旅行费用：MODEL:!Traveling Sales Problem for the cities of six city;SETS: CITY / 1.5/: U; ! U( I) = sequence no. of city; LINK( CITY, CITY): COST, ! The cost matrix; X; ! X( I, J) = 1 if we use link I, J;ENDSETSDATA: !Cost matri

9、x, it need not be symmetric; COST= 0 120 330 210 150 120 0 350 225 300 330 350 0 270 185 210 225 270 0 420 150 300 185 420 0 ;ENDDATA N= SIZE( CITY); MIN= SUM( LINK: COST * X); FOR( CITY( K): !It must be entered; SUM( CITY( I)| I #NE# K: X( I, K) = 1;! It must be departed; SUM( CITY( J)| J #NE# K: X

10、( K, J) = 1;!Weak form of the subtour breaking constrains;!These are not very powerful for large problems; 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); !Make the Xs 0/1;! For the first and last stop we know.;FOR( CITY( K)| K #GT# 1: U( K

11、) = 1 + ( N - 2) * X( K, 1);END得到结果：总费用：950路线：A-B-E-D-F-A(2)选取B,C,E,F，计算旅行费用：MODEL:!Traveling Sales Problem for the cities of six city;SETS: CITY / 1.5/: U; ! U( I) = sequence no. of city; LINK( CITY, CITY): COST, ! The cost matrix; X; ! X( I, J) = 1 if we use link I, J;ENDSETSDATA: !Cost matrix, it

12、 need not be symmetric; COST= 0 120 250 210 150 120 0 98 225 300 250 98 0 430 280 210 225 430 0 420 150 300 280 420 0 ;ENDDATA N= SIZE( CITY); MIN= SUM( LINK: COST * X); FOR( CITY( K): !It must be entered; SUM( CITY( I)| I #NE# K: X( I, K) = 1;! It must be departed; SUM( CITY( J)| J #NE# K: X( K, J)

13、 = 1;!Weak form of the subtour breaking constrains;!These are not very powerful for large problems; 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); !Make the Xs 0/1;! For the first and last stop we know.;FOR( CITY( K)| K #GT# 1: U( K) = 1 +

14、 ( N - 2) * X( K, 1);END得到结果：总费用：963路线：A-E-B-C-F-A(3)选取B,C,D,F,计算旅行费用：MODEL:!Traveling Sales Problem for the cities of six city;SETS: CITY / 1.5/: U; ! U( I) = sequence no. of city; LINK( CITY, CITY): COST, ! The cost matrix; X; ! X( I, J) = 1 if we use link I, J;ENDSETSDATA: !Cost matrix, it need n

15、ot be symmetric; COST= 0 120 250 330 150 120 0 98 350 300 250 98 0 520 280 330 350 520 0 185 150 300 280 185 0 ;ENDDATA N= SIZE( CITY); MIN= SUM( LINK: COST * X); FOR( CITY( K): !It must be entered; SUM( CITY( I)| I #NE# K: X( I, K) = 1;! It must be departed; SUM( CITY( J)| J #NE# K: X( K, J) = 1;!W

16、eak form of the subtour breaking constrains;!These are not very powerful for large problems; 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); !Make the Xs 0/1;! For the first and last stop we know.;FOR( CITY( K)| K #GT# 1: U( K) = 1 + ( N -

17、2) * X( K, 1);END得到结果：总费用：1013路线：A-B-C-F-D-A(4)选取路线:B,C,D,E,计算旅行费用：MODEL:!Traveling Sales Problem for the cities of six city;SETS: CITY / 1.5/: U; ! U( I) = sequence no. of city; LINK( CITY, CITY): COST, ! The cost matrix; X; ! X( I, J) = 1 if we use link I, J;ENDSETSDATA: !Cost matrix, it need not

18、be symmetric; COST= 0 120 250 330 210 120 0 98 350 225 250 98 0 520 430 330 350 520 0 270 210 225 430 270 0 ;ENDDATA N= SIZE( CITY); MIN= SUM( LINK: COST * X); FOR( CITY( K): !It must be entered; SUM( CITY( I)| I #NE# K: X( I, K) = 1;! It must be departed; SUM( CITY( J)| J #NE# K: X( K, J) = 1;!Weak

19、 form of the subtour breaking constrains;!These are not very powerful for large problems; 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); !Make the Xs 0/1;! For the first and last stop we know.;FOR( CITY( K)| K #GT# 1: U( K) = 1 + ( N - 2)

20、* X( K, 1);END得到结果：总费用：1173路线:A-C-B-E-D-A(5)选取C,D,E,F,计算旅行费用：MODEL:!Traveling Sales Problem for the cities of six city;SETS: CITY / 1.5/: U; ! U( I) = sequence no. of city; LINK( CITY, CITY): COST, ! The cost matrix; X; ! X( I, J) = 1 if we use link I, J;ENDSETSDATA: !Cost matrix, it need not be sym

21、metric; COST= 0 250 330 210 150 250 0 520 430 280 330 520 0 270 185 210 430 270 0 420 150 280 185 420 0 ;ENDDATA N= SIZE( CITY); MIN= SUM( LINK: COST * X); FOR( CITY( K): !It must be entered; SUM( CITY( I)| I #NE# K: X( I, K) = 1;! It must be departed; SUM( CITY( J)| J #NE# K: X( K, J) = 1;!Weak for

22、m of the subtour breaking constrains;!These are not very powerful for large problems; 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); !Make the Xs 0/1;! For the first and last stop we know.;FOR( CITY( K)| K #GT# 1: U( K) = 1 + ( N - 2) * X(

23、 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件可带可不带的物品中做出合理的方法。模型建立：将照相机，衣服，书籍，摄像机，渔具

24、，酒，食品和香烟编号为1，2，3，4，5，6，7，8。设总容量为b,为每个物品的重量，为每个物品各自的价格。定义一个变量，当=1是，表示装第i件物品，当=0时，则不装（i=1,2,8）.则约束条件为：max z=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: