旅行商问题数学建模

黄石理工学院

大型作业

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…… 此处隐藏：6469字，全部文档内容请下载后查看。喜欢就下载吧 ……