黄石理工学院数学建模大型作业2011—2012 学年第1学期目录一．摘要二．旅行问题1.问题描述2.符号说明3.模型设计4.建模求解5.模型分析6.三．建模过程及心得体会四．参考文件一．摘要本文是一个围绕旅行商问题和背包问题这两个经典问题的论文。

问题一，是一个依赖与每个城市去一次且仅去一次的路线确定问题，问题二类似于问题一。

问题三是一个依赖于可背重量限制的背包问题。

关键词：HAMILTON回路 LINGO 最优旅行路线 0-1模型二．旅行问题问题描述某人要在假期内从城市A出发，乘火车或飞机到城市B,C,D,E,F 旅游购物。

他计划走遍这些城市各一次且仅一次，最后返回城市A。

已知城市间的路费数据见附表1，请你设计一条旅行路线使得他的总路费最少。

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

模型设计首先给出一个定义：设v1,v2,......,vn 是图G 中的n 个顶点，若有一条从某一顶点v1出发，经过各节点一次且仅一次，最后返回出发点v1的回路，则称此回路为HAMILTON 回路。

问题1.分析：这个优化问题的目标是使旅行的总费用最少，要做的决策是如何设定旅行路线，决策受的约束条件：每个城市都必须去，但仅能去一次。

按题目所给，将决定变量，目标函数和约束条件用数学符号及式子表示出来，就可得一下模型。

模型建立：对于6个城市的旅行问题设A,B,C,D,E,F 六个城市分别对应v1,v2,v3,v4,v5,v6。

假设ij d 表示从城市i 到城市j 的费用。

定义0-1整数型变量ij x =1表示从城市i 旅行到城市j ，否则ij x =0。

则旅行问题的数学模型可表示为一个整数规划问题。

min z=661ij iji jdx =∑∑ (i ≠j)s.t.61iji x=∑=1 （i ≠j ；j=1,2, (6)61ijj x=∑=1 (i ≠j ；i=1,2, (6)1i j ij u u nx n -+≤- (i ≠j;i=2,3,……,6;j=2,3,……6)其中辅助变量i u （i=2,3,……,6）可以是连续变化的，虽然这些变量在最优解中取普通的整数值（从而在约束条件中，可以限定这些变量为整数）。

事实上，在最优解中，i u =访问城市的顺序数。

模型求解运用LINGO ，输入程序：MODEL :!Traveling Sales Problem for the cities of six city; SETS :CITY / 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 150120 0 98 350 225 300250 98 0 520 430 280330 350 520 0 270 185210 225 430 270 0 420150 300 280 185 420 0 ;ENDDATAN= @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;@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 X's 0/1;! For the first and last stop we know...;@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:!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 symmetric;COST= 0 120 330 210 150120 0 350 225 300330 350 0 270 185210 225 270 0 420150 300 185 420 0 ;ENDDATAN= @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;@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 X's 0/1;! For the first and last stop we know...;@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:!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 symmetric;COST= 0 120 250 210 150120 0 98 225 300250 98 0 430 280210 225 430 0 420150 300 280 420 0 ;ENDDATAN= @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;@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 X's 0/1;! For the first and last stop we know...;@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:!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 symmetric;COST= 0 120 250 330 150120 0 98 350 300250 98 0 520 280330 350 520 0 185150 300 280 185 0 ;ENDDATAN= @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;@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 X's 0/1;! For the first and last stop we know...;@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:!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 symmetric;COST= 0 120 250 330 210120 0 98 350 225250 98 0 520 430330 350 520 0 270210 225 430 270 0 ;ENDDATAN= @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;@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 X's 0/1;! For the first and last stop we know...;@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:!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 symmetric;COST= 0 250 330 210 150250 0 520 430 280330 520 0 270 185210 430 270 0 420150 280 185 420 0 ;ENDDATAN= @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;@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 X's 0/1;! For the first and last stop we know...;@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。