旅行商问题数学建模

黄石理工学院

大型作业

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。假设dij表示从城市i到城市j的费用。定义0-1整数型变量xij=1表示从城市i旅行到城市j，否则xij=0。则旅行问题的数学模型可表示为一个整数规划问题。 min z= s.t.

d

i 1

j

66

ijij

x (i j)

x

i 16

6

ij

=1 （i j；j=1,2,……,6）

x

j 1

ij

=1 (i j；i=1,2,……,6)

(i j;i=2,3,……,6;j=2,3,……6) ui uj nxij n1

其中辅助变量ui（i=2,3,……,6）可以是连续变化的，虽然这些变量在最优解中取普通的整数值（从而在约束条件中，可以限定这些变量为整数）。事实上，在最优解中，ui=访问城市的顺序数。

模型求解

运用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; ENDSETS

DATA: !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 300 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; @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; ENDSETS

DATA: !Cost matrix, 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( 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; ENDSETS

DATA: !Cost matrix, it 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)) = 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; ENDSETS

DATA: !Cost matrix, it need not 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; !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; ENDSETS

DATA: !Cost matrix, it need not 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 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; ENDSETS

DATA: !Cost matrix, it need not be symmetric; 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 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。 总费用花费最少，为950.

问题3.

在城市间旅游时他计划购买照相机、衣服、书籍、摄像机、渔具、白酒、食品、香烟等物品，而受航空行李重量的限制以及个人体力所限，所买物品的总重量不能超过15kg，各种物品的价格见附表2。请你为他决策买哪些物品，使所买物品总价值最大？

分析:解读题意，实际上此题涉及背包问题，题目转化为一个限重15公斤的背包，要求在8

件可带可不带的物品中做出合理的方法。

模型建立：将照相机，衣服，书籍，摄像机，渔具，酒，食品和香烟编号为1，2，3，4，5，6，7，8。设总容量为b,bi为每个物品的重量，ci为每个物品各自的价格。定义一个变量xi，当xi=1是，表示装第i件物品，当xi=0时，则不装（i=1,2,……,8）. 则约束条件为： max z=

cx

iii 1

8

bx

i 1

8

ii

b

xi=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月第一版