旅行商问题数学建模

黄石理工学院

数学建模大型作业

2011—２0１2 学年第1学期

目录

一.摘要

二．旅行问题

1.问题描述

2.符号说明

3.模型设计

4.建模求解

5.模型分析

6.

三．建模过程及心得体会

四．参考文件

一.摘要

本文是一个围绕旅行商问题和背包问题这两个经典问题的论文。问题一,是一个依赖与每个城市去一次且仅去一次的路线确定问题，问题二类似于问题一。问题三是一个依赖于可背重量限制的背包问题。

关键词：HAMＩLＴＯN回路 LＩＮGＯ最优旅行路线 0－１模型

二.旅行问题

问题描述

某人要在假期内从城市A出发,乘火车或飞机到城市B，C，D,E,F旅游购物。他计划走遍这些城市各一次且仅一次,最后返回城市A。已知城市间的路费数据见附表1，请你设计一条旅行路线使得他的总路费最少。如果临行他因故只能去4个城市，该怎样修订旅行路线?

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

模型设计

首先给出一个定义:设v1，v2,......,vn 是图G 中的n 个顶点,若有一条从某一顶点v1出发，经过各节点一次且仅一次，最后返回出发点ｖ1的回路，则称此回路为ＨＡMILTON 回路。 问题1.

分析:这个优化问题的目标是使旅行的总费用最少,要做的决策是如何设定旅行路线,决策受的约束条件:每个城市都必须去，但仅能去一次。按题目所给，将决定变量,目标函数和约束条件用数学符号及式子表示出来，就可得一下模型。 模型建立:

对于6个城市的旅行问题设A ，B,C,D,E,F 六个城市分别对应v1,v ２,v3,ｖ4,v5，v6。假设

ij d 表示从城市i 到城市j 的费用。定义0-1整数型变量ij x =1表示从城市i 旅行到城市ｊ，

否则ij x =0。则旅行问题的数学模型可表示为一个整数规划问题。 min z=66

1

ij ij

i j

d

x =∑∑ (i ≠j ）

s.t ．

6

1ij

i x

=∑=１ （i ≠j;j ＝1，2,……,６)

6

1

ij

j x

=∑=１ (i ≠j;ｉ＝1,２, (6)

1i j ij u u nx n -+≤- (i ≠ｊ;i=2,3,……,6;j=2，３,……6)

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

模型求解

运用ＬＩNGO,输入程序：

MOD ＥL :

!Travelin ｇ Sales P ｒｏｂle ｍ f ｏr ｔｈe cities o ｆ six city;

SETS:

CITY ／ 1..６/: U; ! U（ I）＝ sｅquｅncｅnｏ. of cｉty;

ＬINK（ CITY, CＩTY): COST, ! Ｔhe cost matrix;

X; ! Ｘ( Ｉ, J) ＝ 1 if ｗe ｕse lｉnk I，J;

EＮＤSＥTS

DATA: !Ｃｏst mａtriｘ， it neeｄ nｏｔｂe symmｅｔｒｉc;

COST= 0 12０ 2５0 33０ 210 150

１20 0 9８ 3５0 ２2５３0０

２５0 98 0 520 ４30 280

３３0 ３50 520 0 270 18５

210 2２5 ４3０ 27００４20

1５０ 300 ２80 1８5 ４2０ 0 ；

ＥＮDDATＡ

N= ＠SＩZE( CITY);

ＭIN= ＠SUM（ LIＮＫ: COST ＊ X);

@FOR( ＣITＹ( K)：!Ｉｔ musｔ be ｅｎtereｄ;

@SUM（ＣＩTＹ( I）| I ＃NＥ＃Ｋ: X( I, Ｋ)) = 1;

！ It mｕsｔ be dｅparｔｅd;

@SＵM( ＣITY( J)| J ＃NE# K：X( K, J）) ＝ 1;

!Weak ｆorm oｆthｅ subtouｒ breakinｇ coｎstrainｓ;

！Theｓe ａre not vｅry poweｒful ｆoｒ largｅｐｒｏblems;

＠FＯR( ＣIＴY( Ｊ)| J #ＧT＃ 1 #AＮD# J #NE# K:

U（Ｊ)>=U(K)+X（K,J）-(N-2)*(1－Ｘ(K,J）)+(N-３）*X(J,K));)；

@FOR( LINK：@ＢIＮ( X)）; !Maｋｅｔｈe X's 0／1;

! Foｒ thｅｆirｓt and last stoｐｗｅ know...；

@FＯR( CＩTY( K)｜K #GT＃ 1:

U( K）<= N - １ - （N - 2）* X（ 1， K);

Ｕ( K) >= １＋ ( N - 2) ＊X( K, 1）)；

EＮD

得到结果：

总费用为１163

路线：A－B－C-Ｆ-Ｄ-E-A

问题２.

临时因故只能去4个城市，那么应该怎样安排旅行路线。

分析：在B，C,D,E,F五个城市中选4个城市，显然有５种可能,按照问题一中的模型,将费用矩阵稍作修改,运用LINGO分别解除５种可能的费用,进行比较，即得结果。

(1）选取Ｂ,Ｄ,E,F，计算旅行费用:

MODEL：

!Tｒavｅlｉng Sales Pｒoblem for the ｃiｔieｓ of sｉｘ city;

SETS:

CＩTY / １..5/: U; ! Ｕ（ I) = seｑｕence no. ｏf cｉty;

LIＮK（ＣIＴY, CIＴY): COST, ! Tｈe ｃosｔ maｔｒｉｘ;

X; ！ X( I, Ｊ) ＝ 1 if ｗｅ uｓe linｋ I, Ｊ;

ENDSETS

ＤAＴA：！Coｓt matriｘ, it nｅｅd ｎoｔｂe syｍmeｔric;

CＯST= 0 １20 3３0 2１0 １5０

１20 0 ３50 ２25 30０

3３0 350 0 27０ 18５

210 225 ２70 0 ４2０

150 300 185 ４2０ 0 ;

ENDDAＴA

Ｎ= @SＩZE( CITY);

MIＮ= ＠SUM（ LＩNK: ＣOST * X）;

@FOＲ( ＣＩTY（ K）：!Ｉｔ mｕst be ｅnｔered;

@ＳUＭ( CITY（ I)｜ I ＃NE# Ｋ：X( I, K)） = 1；

! Ｉt mｕｓt be departed；

@SＵM( CIＴY（Ｊ)｜ J #NE# K：X( K, J）） = 1;

!Weaｋ foｒｍ of ｔhe suｂtour bｒeａkｉｎg ｃonｓtrainｓ；

！Ｔｈeｓe are noｔ very pｏwerfｕl for larｇe proｂleｍs；

@ＦOR( CＩTY( J)| Ｊ #GT# 1 #ANＤ# J ＃ＮＥ# K:

U(Ｊ)>=U(K)+Ｘ（K,J)-(N－2）＊(１－X(Ｋ,Ｊ)）+(N-３)*X(J,Ｋ));); @FOR( ＬINK: @BＩN( X)); !Mａke tｈe X'ｓ 0/１；

! Ｆoｒ the fｉrst and lａst ｓｔop wｅｋnoｗ...;

@FOＲ（ＣITY( K）| K #GT# 1:

U( K) <= N - 1 - （N - 2) * X( 1, Ｋ);

U( K) >= 1 ＋ ( N - ２) * X( K, 1));

ENＤ

得到结果：

总费用：950

路线：A-B－Ｅ-D-F-A

(2)选取B,C，E,F,计算旅行费用：

MODEL：

!Traveling Ｓalｅｓ Prｏblem for ｔhe citiｅs ｏｆ six city；SETS:

CIＴY ／１..5/: Ｕ; ! U( Ｉ) = ｓequencｅno. of ciｔy;

LINK( CＩTY, CITY): COSＴ, ! Ｔｈe cost matrix;

X; ! X( Ｉ, J) ＝１ if wｅｕse liｎk I, Ｊ;

ＥNDSETS

DＡTA: ！Coｓt mａｔrｉx, iｔnｅed ｎｏt bｅｓymｍetrｉc；

ＣOST= 0 120 ２５0 ２10 15０

１20 0 9８2２5 ３00 250 98 0 ４30 28０

210 225 430 0 ４20

15０３00 280 ４２0 0 ；

ENDDATA

N= @SIZE（ CIＴY);

MIN= @SUM( LＩNK: ＣOST * X)；

@FOR（ CＩTY( K): !It ｍusｔ be entｅｒｅd;

＠ＳUM( ＣITＹ( I)| I #NE＃Ｋ: X( I, Ｋ)） = 1;

! It ｍuｓt be deｐaｒted;

＠ＳUM( CIＴY( J)| Ｊ #NE＃Ｋ: X( Ｋ，J)) = 1;

!Ｗeak fｏrm of tｈe ｓubtouｒ breaking cｏnstrainｓ;

！Ｔheｓe are nｏｔ very ｐowerful for lａrge ｐroblems;

＠ＦOR( CITY( J)| J #GT# 1 #AND＃ J #NE# K：

Ｕ(Ｊ)＞＝U(K)+Ｘ(Ｋ,J)-(N-2)*（1-X(Ｋ，Ｊ)）＋(N-３)*Ｘ(Ｊ，K）)；）；@FＯR( LＩNK: @BIN( X）); !Make the X's 0/1;

! For the fiｒst anｄlast stop we knｏw．..;

@FＯR( CITY( K)| K #GT# 1:

Ｕ（K) ＜= N - 1 - (Ｎ－ 2) * X( １， K)；

Ｕ（ K) >= １＋ ( N - 2) * X( Ｋ, 1));

END

得到结果：

总费用：９６３

路线:A-E－B－Ｃ-Ｆ-A

(3)选取B,C,D,F，计算旅行费用:

MODＥＬ：

!Ｔraｖeling Salｅs Ｐroｂｌeｍ for ｔhｅ cities of ｓix city;

ＳEＴS:

CＩTＹ / １..5/: U; ！ U( Ｉ）= sｅｑuencｅｎｏ． of citｙ;

ＬINK（ CIＴＹ, CITＹ)：ＣOＳT, ! The cost ｍatｒix;

X; ! X( I, J) = 1 if we usｅｌink I, Ｊ;

EＮＤＳETＳ

ＤＡTＡ：!Cost mａｔｒix, it neｅd ｎot ｂe sｙmmetrｉc;

ＣOST＝ 0 １2０ 250 ３30 150

12０ 0 98 350 30０

2５0 9８０５2０ 280

330 35０ 520 0 185

15０３00 280 １85 0 ;

ENＤＤATA

Ｎ= @SＩＺＥ( CITY);

ＭIN= @SＵM( LINＫ: ＣＯST ＊ X);

@ＦOＲ( CITY（K): !It must bｅ enteｒed;

＠SUM( ＣITY( Ｉ)| I ＃NE＃ K: X( I, Ｋ)）＝ 1;

! Iｔｍust ｂe depａrted;

＠ＳUＭ( CIＴY( J)｜ J #NＥ# K: X( K, J））＝１;

！Weak form ｏｆ tｈe subtour breaking conｓtrains;

！Theｓe are nｏt verｙ poｗerｆul foｒ lａrge probｌems;

@ＦＯR( CITY（ J)| J #GT＃ 1 #ANＤ＃Ｊ #NE# K:

U（J)>=U(K)+X（K,J)-(N-2)*(1-X(K,J））＋（Ｎ-3)＊Ｘ(J,K));)；

＠FＯＲ( ＬＩNK: @BIN( X）); ！Make ｔhe X＇s 0/1；

! Ｆoｒthe firsｔａnd last stop we know...;

@ＦOR( CITＹ( Ｋ)| K ＃GT＃1：

U( K) ＜= N - 1 - (N － 2) ＊ X( 1，K)；

U( Ｋ) >= 1 + （N －２) * X( K, 1)）;

ENＤ

得到结果:

总费用:1013

路线：A－B-C－Ｆ-D-A

（4)选取路线:Ｂ,C,Ｄ,E,计算旅行费用：

MODEL：

!ＴraveｌinｇＳales Pｒoblem for the cｉｔiｅｓ of ｓiｘcity；SETS：

CITY ／１.．5／： U; ! U（I） = ｓequｅnｃe no. of ciｔy;

LINＫ( ＣITY, ＣIＴＹ）：ＣOＳＴ，! The cost mａｔriｘ;

X；！X（ I, J) = １ if wｅ use linｋI, J;

EＮＤSETS

DＡTA: !Cosｔ matrix, ｉt nｅｅd ｎot ｂe syｍｍｅtric;

COSＴ= ０ 120 ２５0 330 21０

120 ０９8 350 2２5

250 98 ０ 520 4３０

３30 3５0 520 0 27０

210 ２2５ 43０ 270 0 ;

ＥＮDDAＴＡ

N= @ＳIZE（ CITY);

MＩN= ＠ＳUM( ＬINK: ＣＯST * Ｘ）;

＠FＯR( CITＹ( K)：!Ｉt musｔbe ｅntered;

@ＳUＭ（ CIＴY( I)| I ＃NＥ# K: X( I, K）) = １；

! Iｔmｕst be ｄｅｐarted;

＠ＳＵＭ（ＣＩＴY( J）| J #NE# K: X（ K， J)) = １；

!Weak fｏrm ｏf the ｓubtｏuｒ breakiｎg conｓｔrainｓ；

!Thesｅ are noｔ verｙｐowｅrful ｆor largｅ proｂｌeｍs；

@ＦOＲ（ CITY( J)| J #ＧT# １ #AND# J #NE＃ K：

Ｕ(J）>=U（K)+X(K,Ｊ)-（Ｎ-2)*(1-Ｘ(Ｋ，J））+（N－3）*X（J,Ｋ));）；@FＯＲ( LINK: @BＩN( X))；!Maｋe tｈｅX's 0/１;

! Fｏr thｅｆirsｔａnｄlａst sｔoｐ we knｏw...;

＠FＯＲ( CITY（ K)｜ K #GT# 1:

Ｕ( K) <= N - 1 － (N - 2） * Ｘ( 1， K);

U( K) >＝ 1 + （Ｎ- ２）＊ X（K, 1));

END

得到结果：

总费用:1１７3

路线:A-C-B-E-Ｄ-Ａ

(5）选取C,D,E,F,计算旅行费用：

ＭODＥＬ:

！Traｖｅlｉｎg Ｓales Pｒoｂlem foｒtｈe ｃities of six city;

SETS:

CIＴY ／ 1..5/: Ｕ; ! U( I) = sequｅnｃe nｏ. of cｉty;

LＩNK（CITY, CITY)： COST, ！Ｔhｅ cost matｒix;

X; ! Ｘ( I, Ｊ) ＝ 1 if ｗe ｕse lｉnｋ I, J；

ENDSETS

DAＴA：!Cost maｔrｉｘ, it need ｎｏt be symmetric;

CＯST= 0 2５0 330 2１0 1５０

25０ 0 ５２0 43０ 2８0

330 52０ 0 270 １85

210 430 270 0 4２０

150 ２80 185 ４20 0 ；

EＮＤＤATA

N＝@SIZE( CITY)；

MIN= @SUM( ＬIＮK： COSＴ * X）;

@FOR( CＩTY( K): !It ｍuｓt be enteｒed;

＠SUM( ＣITY( I)｜ I ＃NE# Ｋ: X( Ｉ, K)）＝ 1；

！ Iｔｍust be ｄeparted;

@SUM（ CＩTY( Ｊ)｜ J #NE# Ｋ: X( K, Ｊ)) = １;

！Ｗeak form ｏｆthｅｓubｔｏｕr brｅakinｇ conｓtｒaｉnｓ;

!These arｅ noｔ very powｅrfuｌｆｏr lａｒge ｐroｂlems;

@FOR（ CITY( Ｊ）| Ｊ #ＧＴ# 1 #ANＤ# J #NE＃ K：

Ｕ(J）>＝U（K）+X(Ｋ,J)－(N-２）*(1-Ｘ(Ｋ,J)）+(N－３)*Ｘ（J,K)）;）；

＠ＦOR( ＬINK: @BIＮ( X)); !Make ｔhe Ｘ's 0/１;

！Ｆor the first aｎｄ lａｓt ｓｔoｐｗe know...;

＠FＯR( CITY（ K)| K ＃GT＃１：

U( K）＜= N - 1 － (Ｎ－ 2) ＊ X( 1, K）;

U( K) ＞= １ + ( N - ２) * X( Ｋ, 1));

END

得到结果：

总费用：１195

路线：A-Ｃ－F－Ｄ-E-A

因此，总结以上（1），(2),（3），(４）,（5）五种情况可得:应该选用路线：A-Ｂ-Ｅ-Ｄ-F-A。总费用花费最少,为９50.

问题3.

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

分析:解读题意,实际上此题涉及背包问题,题目转化为一个限重15公斤的背包，要求在８件可带可不带的物品中做出合理的方法。

模型建立：将照相机,衣服，书籍,摄像机,渔具，酒,食品和香烟编号为1，2,３，4,５，６，7，８。设总容量为b,i b 为每个物品的重量,i c 为每个物品各自的价格。定义一个变量i x ，当i x =1是,表示装第i 件物品,当i x =0时，则不装（ｉ=1,2,……,8)． 则约束条件为: max z ＝

8

1

i i i c x =∑

8

1

i i

i b x

b =≤∑

i x =0或1,（i=1，2，……,８)

模型求解：

利用LINGO 软件求解,在LINGO 中输入以下程序：

mo ｄｅｌ： s ｅｔs : M/1..8/:Ｗ； price/1.．8/:p; number/1．.8/:x; ends ｅts d ａta :

W=1，２,4,3,4,2，2,1;

P=13０0,2７5０，3２0,43５0,1400,300,１20,600; endda ｔａ

MAX =@SUM （Ｍ：X*P); @SUM （M:X*W ）<=１5; @FOR (M:@ＢＩＮ(X)); E ｎd

得到结果:

选择照相机，衣服，摄像机,渔具，酒,食品和香烟,最大价值为１0820。

三.建模过程及心得体会

数学建模是一个经历观察、思考、归类、抽象与总结的过程，也是一个信息捕捉、筛选、整理的过程,更是一个思想与方法的产生与选择的过程。它给学生再现了一种“微型科研”的过程。数学建模教学有利于激发学生学习数学的兴趣,丰富学生数学探索的情感体验;有利于学生自觉检验、巩固所学的数学知识，促进知识的深化、发展；有利于学生体会和感悟数学思想方法。同时教师自身具备数学模型的构建意识与能力，才能指导和要求学生通过主动思维,自主构建有效的数学模型，从而使数学课堂彰显科学的魅力。

为了使描述更具科学性，逻辑性,客观性和可重复性，人们采用一种普遍认为比较严格的语言来描述各种现象,这种语言就是数学。使用数学语言描述的事物就称为数学模型。有时候我们需要做一些实验,但这些实验往往用抽象出来了的数学模型作为实际物体的代替而进行相应的实验,实验本身也是实际操作的一种理论替代。

数学建模要有团队精神。数学建模不是一个人的事,是团队的一项活动。三个人要相互支持，相互鼓励。不能只管自己的那一部分。特别是模型的建立，一个人根本不可能想的那么全面，只有大家一起讨论才能把问题搞清楚。

必须合理的安排时间。做任何事情，合理的时间安排非常重要，建模也是一样,事先要做好一个规划，建模一共分十个板块。你每天昨晚哪几个板块事先要确定好，这样做才会使自己游刃有余，保证在规定的时间内完成论文,以避免在时间上的不妥,以至于最后无法完成论文。有些同学经常会借鉴一些别人的论文里的思想，然后变成自己的东西，不过那也是一种能力,不能小瞧。所以也要多看些别人的论文来调高自己。

四．参考文件。

【１】.运筹学,科学出版社,徐玖平，胡知能,２0０3年11月第一版

【２】.运筹学——数据,模型，决策，科学出版社,徐玖平，胡知能,20０6年3月第一版

旅行商问题数学建模

黄石理工学院 数学建模大型作业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=66 1 ij ij i j d x =∑∑ (i ≠j) s.t. 6 1ij i x =∑=1 （i ≠j ；j=1,2, (6) 6 1 ij j 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 :

单旅行商问题的算法

有一个推销员，从城市1出发，要遍访城市2，3，…，n 各一次，最后返回城市1。已知从城市i 到j 的旅费为ij c ，问他应按怎样的次序访问这些城市，使得总旅费最少？ 可以用多种方法把TSP 表示成整数规划模型。这里介绍的一种建立模型的方法，是把该问题的每个解（不一定是最优的）看作是一次“巡回”。 在下述意义下，引入一些0-1整数变量： ij x ?? ?≠=其它情况，且到巡回路线是从，0,1j i j i 其目标只是使∑=n j i ij ij x c 1 ,为最小。 这里有两个明显的必须满足的条件： 访问城市i 后必须要有一个即将访问的确切城市；访问城市j 前必须要有一个刚刚访问过的确切城市。用下面的两组约束分别实现上面的两个条件。 n i x n j ij ,,2,1, 11 ==∑= n j x n i ij ,,2,1, 11 ==∑= 到此我们得到了一个模型，它是一个指派问题的整数规划模型。但以上两个条件对于TSP 来说并不充分，仅仅是必要条件。例如： 以上两个条件都满足，但它显然不是TSP 的解，它存在两个子巡回。 这里，我们将叙述一种在原模型上附加充分的约束条件以避免产生子巡回的方法。把额外变量 ),,3,2(n i u i =附加到问题中。可把这些变量看作是连续的（最然这些变量在最 优解中取普通的整数值）。现在附加下面形式的约束条件 n j i n x n u u ij j i ≤≠≤-≤+-2, 1。 为了证明该约束条件有预期的效果，必须证明：（1）任何含子巡回的路线都不满足该约 束条件；（2）全部巡回都满足该约束条件。 首先证明（1），用反证法。假设还存在子巡回，也就是说至少有两个子巡回。那么至少存在一个子巡回中不含城市1。把该子巡回记为121i i i i k ，则必有(对于所有的i k 都满足大 于2的限制条件) 1 11132121-≤+--≤+--≤+-n n u u n n u u n n u u i i i i i i k 把这k 个式子相加，有 1-≤n n ，矛盾！ 故假设不正确，结论（1）得证。 下面证明（2），采用构造法。对于任意的总巡回1111-n i i ，可取 =i u 访问城市i 的顺序数。 下面来证明总巡回满足该约束条件。 1 2 3 4 5 6

多旅行商问题模型

以点0表示旅行商的出发城市，称为源点，点1,2, ,l 表示m 个旅行商需访 问的城市。MTSP 问题的数学模型可以表示为： 令10ij x ?=??弧(i,j)在线路上 弧(i,j)不在线路上 模型表示如下： 0000min 10,1,,10,1,,()01,0,1,,R R ij ij i j R ij i R ij j ij ij z d x x j R x i R X x S x i j R ====?=?? ?==????==??=∈??==?∑∑∑∑或 式中：1;ij R m l d =+-为增广费用。若用(,1,,)ij c i j l =表示旅行商经过对应弧度(,)i j 所花的费用，如时间、距离、花费等，那么给ij c 增加(1)m -行和(1)m -列，每一新的行或列是ij c 的最后一行或列的复制，增广矩阵的其他元素为无穷大，由此构成了增广费用ij d 。 一般MTSP 中，旅行商访问l 个城市必须满足以下2个条件。 条件1：从指定城市出发，对其他所有城市严格访问一次后返回原出发城市。 条件2：一条有效路径严格由m 条非平凡子路径(Nontrivial Subtours)组成。所谓非平凡子路径是指该路径中除出发城市外，至少访问一个其他城市。 用遗传算法求解MTSP ，可通过附加虚拟城市的方法把MTSP 转化为TSP 。将另外(1)m -个旅行商理解为(1)m -个虚拟城市，这(1)m -个虚拟城市标号分别为1,2,,1,l l l m +++-，它们与城市0具有相同的坐标(即相同位置)。在旅行商访问路径中出现的每一个虚拟城市均表示旅行商返回出发城市，从而组成一个回路。每个回路表示MTSP 中一个旅行商的旅行路径。需注意的是，为了避免出现平凡子路径，必须假设(1)m -个虚拟城市到原点的距离为 00(,0,1,,1),ij c M i j l l m M ==++-为一无穷大的正数（即永远不能达到），到其他各点距离与原点一致，这样遗传算法就不会出现0-0-0的途径。将源点0复制(1)m -个，m 个源点编号为0,1,1,l l m ++-每一个同源点0一样与其他

数学建模运输问题

运输问题 摘要 本文主要研究的是货物运输的最短路径问题，利用图论中的Floyd算法、Kruskal算法，以及整数规划的方法建立相关问题的模型，通过matlab，lingo 编程求解出最终结果。 关于问题一，是一个两客户间最短路程的问题，因此本文利用Floyd算法对其进行分析。考虑到计算的方便性，首先，我们将两客户之间的距离输入到网络权矩阵中；然后，逐步分析出两客户间的最短距离；最后，利用Matlab软件对其进行编程求解，运行得到结果：2-3-8-9-10总路程为85公里。 关于问题二，运输公司分别要对10个客户供货，必须访问每个客户，实际上是一个旅行商问题。首先，不考虑送货员返回提货点的情形，本文利用最小生成树问题中的Kruskal算法，结合题中所给的邻接矩阵，很快可以得到回路的最短路线：1-5-7-6-3-4-8-9-10-2；然后利用问题一的Floyd算法编程，能求得从客户2到客户1（提货点）的最短路线是：2-1，路程为50公里。即最短路线为：1-5-7-6-3-4-8-9-10-2-1。但考虑到最小生成树法局限于顶点数较少的情形，不宜进一步推广，因此本文建立以路程最短为目标函数的整数规划模型；最后，利用LINGO软件对其进行编程求解，求解出的回路与Kruskal算法求出的回路一致。 关于问题三，是在每个客户所需固定货物量的情况下，使得行程之和最短。这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以内即可。因此我们在问题二模型的基础上进行改进，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，对于模型求解出来的结果，本文利用Kruskal算法结合题中所给的邻接矩阵进行优化。得到优化结果为：第一辆车：1-5-2-3-4-8-9-1，第二辆车：1-7-6-9-10-1，总路程为280公里。 关于问题四，在问题一的基础上我们首先用Matlab软件编程确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一种很理想的运输方案。根据matlab运行结果分析得出4条最优路线分别为：1-5-2，1-4-3-8，1-7-6，1-9-10。最短总路线为245公里，最小总费用为645。 关键词： Floyd算法 Kruskal算法整数规划旅行商问题 一、问题重述 某运输公司为10个客户配送货物，假定提货点就在客户1所在的位置，从第i个客户到第j个客户的路线距离（单位公里）用下面矩阵中的 i j=L位置上的数表示（其中∞表示两个客户之间无直接的路线到i j(,1,,10) (,) 达）。 1、运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让他先给 客户10送货，已知送给客户10的货已在运送员的车上，请帮运送员设计一个到客户10的尽可能短的行使路线（假定上述矩阵中给出了所有可能的路线选择）。 2、现运输公司派了一辆大的货车为这10个客户配送货物，假定这辆货车一次能 装满10个客户所需要的全部货物，请问货车从提货点出发给10个客户配送

多旅行商问题模型

令x ij 弧(i,j)在线路上 弧(i,j) 不在线路上 以点0表示旅行商的出发城市，称为源点，点1,2丄，1表示m个旅行商需访 问的城市。MTSP问题的数学模型可以表示为: 模型表示如下: RR min z d ij x ij i0j0 R x ij 1 j 0,1,L ,R i0 R x ij 1 i 0,1,L ,R j0 X (x ij ) S x ij 0或1 i, j 0,1,L ,R 式中：R m l 1;d ij为增广费用。若用C ij (i,j 1,L ,1)表示旅行商经过对应弧度(i, j)所花的费用，如时间、距离、花费等，那么给q增加(m 1)行和(m 1)列，每一新的行或列是c ij 的最后一行或列的复制，增广矩阵的其他元素为无穷大，由此构成了增广费用d ij 。 一般MTSP中，旅行商访问I个城市必须满足以下2个条件。 条件 1：从指定城市出发，对其他所有城市严格访问一次后返回原出发城市。 条件2：一条有效路径严格由m条非平凡子路径(Nontrivial Subtours)组成。所谓非平凡子路径是指该路径中除出发城市外，至少访问一个其他城市。 用遗传算法求解MTSP，可通过附加虚拟城市的方法把 MTSP转化为TSP。 将另外(m 1)个旅行商理解为(m 1)个虚拟城市，这(m 1)个虚拟城市标号分 别为l 1,l 2,L ,l m 1,，它们与城市0具有相同的坐标(即相同位置)。在旅 行商访问路径中出现的每一个虚拟城市均表示旅行商返回出发城市，从而组成一个回路。每个回路表示MTSP中一个旅行商的旅行路径。需注意的是，为了避免出现平凡子路径，必须假设(m 1)个虚拟城市到原点的距离为 c ij M0(i, j 0,l 1,L ,l m 1 ) , M 0为一无穷大的正数(即永远不能达到) ，到其他各点距离与原点一致，这样遗传算法就不会出现 0-0-0 的途径。将源点 0 复制(m 1)个，m个源点编号为0,1 1,L l m 1,每一个同源点0 —样与其他

求解旅行商问题的几种解法

2010年第5期(总第77期) 边疆经济与文化 THE BORDER ECONOMY AND CULT URE No 1512010General 1No 177 10 　B I A N J I A N G J I N G J I Y U W EN HUA 【旅游经济】 求解旅行商问题的几种解法 高春涛 (哈尔滨商业大学基础科学学院,哈尔滨150028) 摘　要:旅行商问题(TSP )是一个典型的NP 完全问题,现在还没有找到有效的解法。目前比较热门的求解TSP 问题的方法主要有四种:神经网络算法;模拟退火算法;遗传算法;蚁群算法。 关键词:旅行商问题;组合优化;解法 中图分类号:F 592 文献标志码:A 文章编号:167225409(2010)0520010202 收稿日期:2010201222作者简介:高春涛(1973 ),女,黑龙江拜泉人,讲师,硕士,主要从事混沌神经网络研究。 一、引言 旅行商问题(Traveling Sales man Pr oble m ),是指给定n 个城市,任何两城市之间皆有路连通,其距离为已知,某旅行商从其中某城市出发,要经过每城市一次,且只能一次,最后又必须返回出发城市,要求找出最短的巡回路径。由于在很多实际问题中,如印刷电路板的铅孔路线方案、连锁店的货物配送路线等问题经过简化处理,均可建模为旅行商问题,因而对旅行商问题求解方法的研究具有重要的应用价值。旅行商问题是运筹学中有代表性的组合优化问题,也是典型的NP 完全问题。虽然它陈述起来很简单,但求解却很困难,对于具有n 个城市的TSP 问题,其可能的路径数目为(n -1)!/2,至今尚未找到有效的求解方法,在理论上枚举法可以解决这一问题,但是当n 较大时,解题的时间消耗会使枚举法显得没有任何实际价值。因此寻求一种求解时间短,能满足实际问题精度要求的解,成为解决该问题的主要途径。 二、TSP 求解方法 求解旅行商问题的方法可以分为两大类,一类是精确算法,目的是要找到理论最优解;另一类是近似算法,其算法简单,计算量小,大多数情况下求得的满意解能满足要求。 1.Hopfield 神经网络算法 1982年,Hopfield 开创性地在物理学、神经生物学和计算机科学等领域架起了桥梁,提出了Hopfield 反馈神经网络模型(HNN )。Hopfield 网络是典型的全连接网络,通过在网络中引入能量函数以构造动力学系统,并使网络的平衡态与能量函数 的极小解相对应,从而将求解能量函数极小解的过程转化为网络向平衡态的演化过程。尤其是通过对TSP 问题的成功求解,开辟了神经网络模型在计算机科学应用中的新天地,动态反馈网络从而受到广泛的研究和关注,被广泛应用于优化问题中,且已 设计出了专用的硬件电路。 [1] Hopfield 网络是一种非线性动力学模型,通过引入类似Lyapunov 函数的能量函数概念,把神经网络的拓扑结构(用连接矩阵表示)与所求问题(用目标函数描述)对应起来,转换成神经网络动力学系统的演化问题。因此,在用Hopfield 网络求解优化问题之前,必须将问题映射为相应的神经网络。对TSP 问题的求解,首先将问题的合法解映射为一个置换矩阵,并给出相应的能量函数,然后将满足置换矩阵要求的能量函数的最小值与问题的最优解相对应。 2.模拟退火算法 模拟退火算法最初的思想由Metr opolis 在1953 年提出,[2] Kirkpatrick 在1983年成功地将其应用在组合最优化问题中。模拟退火算法的出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法在某一初温下,伴随温度参数的不断下降,结合概率突跳特征在解空间中随机寻找目标函数的全局最优解,即在局部优解能 概率性地跳出并最终趋于全局最优。[1] 用固体退火模拟组合优化问题,将内能E 模拟为目标函数f,温度T 演化成控制参数t,即得到解组合优化问题的模拟退火算法:有初始解i 和控制参数初值t 开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t 值,算法终止时的当前解即为所得近似最优解。

数学建模旅游问题

摘要 随着人们生活水平的不断提高，作为“无烟工业”旅游活动便成为人们生活水平的重要指标。本文围绕五一黄金周的旅游问题进行了定量的评估，对即有时间限制又有时间限制的旅游质量问题建立了数学模型，对求解结果进行了分析。 问题要求在只有1000元的旅游费用且在7天之内的条件下游览尽可能多的城市。首先，我们对预选的旅游景点之间消耗的费用和时间进行了分析。由于约束条件不仅要求费用不大于1000而且旅游时间在7天之内，因此，我们从长途汽车站和火车车次中选取费用最低且最节约时间的路线并记录了最优行程费用表。另外，由于时间的限制，因此，需引入0-1变量表示是否游览某个景点，根据求解最优Hamilton回路算法——三边交换调整法，以费用和时间为参考量，我们建立了一个适用于本问题最优规划模型，得出最优旅游路线①→⑥→⑤→④→③→⑧→⑩→①。 关键词：三边交换调整法最优旅游路线 Matlab程序 0—1模型

问题重述 旅游路线安排计划 黄金周又到了，希望安排出外旅游。你要考虑的因素很多。首先，你得考虑时间有限（７天）；其次要考虑费用问题：根据有限的费用安排你的交通方式。当然，还要考虑出游的乐趣，希望多走几个景点。还要考虑劳逸结合，如较远的地方如坐火车需乘坐卧铺，晚上休息。如何安排你的假期。假设一个景点一天的平均费用为100元，你手中恰有刚刚发下来的奖学金1000元。要制定合理的旅行路线，需要考虑的因素很多，如交通方式，尽可能去多个景点，休息住宿等。假设一个景点一天的平均费用为100元。那么如何安排你的假期 预选的九个市旅游景点 模型假设与符号说明

模型假设 1、所有的车票均预订； 2、在每个城市中停留时，难免会遇到等车、堵车等延时情况，在此问题中我们不做考虑； 3、平均每个城市的交通费用30元(如公交车、出租车等)； 4、景点的开放，列车和汽车的运营不受天气的影响； 5、每天的伙食费达到最高标准40元/天； 6、景点停留时间超过六小时必须住宿，住宿费每晚60元； 7、在时间的认识上，我们把当天的8点至次日8点作为一天； 8、由于旅游者携带学生证，所有门票按半价计算。 符号说明 ⑴、i,j表示第i个城市(景点)或第j个城市(景点)，i、j=1,2…10； ⑵、Z表示计划行程中的总费用； ⑶、W表示各城市(景点)之间的交通费用的总和，表示各城市(景点)之间的交通费用； ⑷、A表示在景点所在城市的总花费，其中包括表示第i个城市(景点)内的交通费用，表示第i个城市(景点)内的食宿费用，表示第i个城市的景点的门票费用，表示第i个城市(景点)内总费用，故=++； ⑸、表示在第i个城市(景点)的逗留时间，表示从第i个景点到第j个景点路途中所需时间，T表示本次旅游的总时间；

TSP问题与LINGO求解技巧

TSP 问题及LINGO 求解技巧 巡回旅行商问题(Traveling Salesman Problem ，TSP)，也称为货郎担问题。最早可以追溯到1759年Euler 提出的骑士旅行问题。1948年，由美国兰德公司推动，TSP 成为近代组合优化领域的一个典型难题。它已经被证明属于NP 难题。 用图论描述TSP ，给出一个图(,)G V E =，每边e E ∈上有非负权值()w e ,寻找G 的Hamilton 圈C ，使得C 的总权()()() W C w e e E C = ∑ ∈最小. 几十年来，出现了很多近似优化算法。如近邻法、贪心算法、最近插入法、最远插入法、模拟退火算法以及遗传算法。这里我们介绍利用LINGO 软件进行求解的方法。 问题1 设有一个售货员从10个城市中的某一个城市出发，去其它9个城市推销产品。10个城市相互距离如下表。要求每个城市到达一次仅一次后，回到原出发城市。问他应如何选择旅行路线，使总路程最短。 我们采用线性规划的方法求解 设城市之间距离用矩阵d 来表示，ij d 表示城市i 与城市j 之间的距离。设0--1矩阵X 用来表示经过的各城市之间的路线。设 01 ,ij i j x i j i j ?=? ?若城市不到城市若城市到城市且在前 考虑每个城市后只有一个城市，则： 1 1,n ij j j i x =≠=∑ 1,,i n =… 考虑每个城市前只有一个城市，则：

1 1,n ij i i j x =≠=∑ 1,,j n =…； 但仅以上约束条件不能避免在一次遍历中产生多于一个互不连通回路。 为此我们引入额外变量 i u (1,,i n =…）， 附加以下充分约束条件： 1,i j ij u u nx n -+≤- 1i j n <≠≤； 该约束的解释： 如i 与j 不会构成回路，若构成回路，有： 1ij x =，1ji x =，则： 1i j u u -≤-，1j i u u -≤-，从而有： 02≤-，导致矛盾。 如i ，j 与k 不会构成回路，若构成回路，有： 1ij x =，1jk x =，1ki x =则： 1i j u u -≤-，1j k u u -≤-，1i k u u -≤-从而有： 03≤-，导致矛盾。 其它情况以此类推。 于是我们可以得到如下的模型：

旅行商问题数学建模

黄石理工学院 数学建模大型作业 2011—２0１2 学年第1学期

目录 一.摘要 二．旅行问题 1.问题描述 2.符号说明 3.模型设计 4.建模求解 5.模型分析 6. 三．建模过程及心得体会 四．参考文件

一.摘要 本文是一个围绕旅行商问题和背包问题这两个经典问题的论文。问题一,是一个依赖与每个城市去一次且仅去一次的路线确定问题，问题二类似于问题一。问题三是一个依赖于可背重量限制的背包问题。 关键词：HAMＩLＴＯN回路 LＩＮGＯ最优旅行路线 0－１模型 二.旅行问题 问题描述 某人要在假期内从城市A出发,乘火车或飞机到城市B，C，D,E,F旅游购物。他计划走遍这些城市各一次且仅一次,最后返回城市A。已知城市间的路费数据见附表1，请你设计一条旅行路线使得他的总路费最少。如果临行他因故只能去4个城市，该怎样修订旅行路线? 在城市间旅游时他计划购买照相机,衣服,书籍，摄像机，渔具，白酒，食品,而受航空行李重量的限制以及个人体力所限,所买物品的总重量不能超过15kｇ，各种物品的价格见附表2．请你为他决策买哪些物品,使所买物品价值最大。

模型设计 首先给出一个定义:设v1，v2,......,vn 是图G 中的n 个顶点,若有一条从某一顶点v1出发，经过各节点一次且仅一次，最后返回出发点ｖ1的回路，则称此回路为ＨＡMILTON 回路。 问题1. 分析:这个优化问题的目标是使旅行的总费用最少,要做的决策是如何设定旅行路线,决策受的约束条件:每个城市都必须去，但仅能去一次。按题目所给，将决定变量,目标函数和约束条件用数学符号及式子表示出来，就可得一下模型。 模型建立: 对于6个城市的旅行问题设A ，B,C,D,E,F 六个城市分别对应v1,v ２,v3,ｖ4,v5，v6。假设 ij d 表示从城市i 到城市j 的费用。定义0-1整数型变量ij x =1表示从城市i 旅行到城市ｊ， 否则ij x =0。则旅行问题的数学模型可表示为一个整数规划问题。 min z=66 1 ij ij i j d x =∑∑ (i ≠j ） s.t ． 6 1ij i x =∑=１ （i ≠j;j ＝1，2,……,６) 6 1 ij j x =∑=１ (i ≠j;ｉ＝1,２, (6) 1i j ij u u nx n -+≤- (i ≠ｊ;i=2,3,……,6;j=2，３,……6) 其中辅助变量i u (ｉ=2,3,……，6)可以是连续变化的,虽然这些变量在最优解中取普通的整数值(从而在约束条件中，可以限定这些变量为整数）。事实上,在最优解中,i u =访问城市的顺序数。 模型求解 运用ＬＩNGO,输入程序： MOD ＥL : !Travelin ｇ Sales P ｒｏｂle ｍ f ｏr ｔｈe cities o ｆ six city;

数学建模四大模型归纳

四类基本模型 1 优化模型 1.1 数学规划模型 线性规划、整数线性规划、非线性规划、多目标规划、动态规划。 1.2 微分方程组模型 阻滞增长模型、SARS 传播模型。 1.3 图论与网络优化问题 最短路径问题、网络最大流问题、最小费用最大流问题、最小生成树问题(MST)、旅行商问题(TSP)、图的着色问题。 1.4 概率模型 决策模型、随机存储模型、随机人口模型、报童问题、Markov 链模型。 1.5 组合优化经典问题 ● 多维背包问题(MKP) 背包问题：n 个物品，对物品i ，体积为i w ，背包容量为W 。如何将尽可能多的物品装入背包。 多维背包问题：n 个物品，对物品i ，价值为i p ，体积为i w ，背包容量为W 。如何选取物品装入背包，是背包中物品的总价值最大。 多维背包问题在实际中的应用有：资源分配、货物装载和存储分配等问题。该问题属于NP 难问题。 ● 二维指派问题(QAP) 工作指派问题：n 个工作可以由n 个工人分别完成。工人i 完成工作j 的时间为ij d 。如何安排使总工作时间最小。 二维指派问题（常以机器布局问题为例）：n 台机器要布置在n 个地方，机器i 与k 之间的物流量为ik f ，位置j 与l 之间的距离为jl d ，如何布置使费用最小。

二维指派问题在实际中的应用有：校园建筑物的布局、医院科室的安排、成组技术中加工中心的组成问题等。 ●旅行商问题(TSP) 旅行商问题：有n个城市，城市i与j之间的距离为 d，找一条经过n个城 ij 市的巡回（每个城市经过且只经过一次，最后回到出发点），使得总路程最小。 ●车辆路径问题(VRP) 车辆路径问题（也称车辆计划）：已知n个客户的位置坐标和货物需求，在可供使用车辆数量及运载能力条件的约束下，每辆车都从起点出发，完成若干客户点的运送任务后再回到起点，要求以最少的车辆数、最小的车辆总行程完成货物的派送任务。 TSP问题是VRP问题的特例。 ●车间作业调度问题(JSP) 车间调度问题：存在j个工作和m台机器，每个工作由一系列操作组成，操作的执行次序遵循严格的串行顺序，在特定的时间每个操作需要一台特定的机器完成，每台机器在同一时刻不能同时完成不同的工作，同一时刻同一工作的各个操作不能并发执行。如何求得从第一个操作开始到最后一个操作结束的最小时间间隔。 2分类模型 判别分析是在已知研究对象分成若干类型并已经取得各种类型的一批已知样本的观测数据，在此基础上根据某些准则建立判别式，然后对未知类型的样品进行判别分析。 聚类分析则是给定的一批样品，要划分的类型实现并不知道，正需要通过局内分析来给以确定类型的。 2.1判别分析 ●距离判别法 基本思想：首先根据已知分类的数据，分别计算各类的重心即分组(类)的均值，判别准则是对任给的一次观测，若它与第i类的重心距离最近，就认为它来自第i类。 至于距离的测定，可以根据实际需要采用欧氏距离、马氏距离、明科夫距离