c题家庭暑假旅游套餐的设计2,新

c题家庭暑假旅游套餐的设计

摘要

近年来，我国的综合国力不断提高，经济实力不断增强，这与我国的旅游业发展有着不小的关系。随着我国步入小康社会，人民的生活水平不断提高，旅游已成为提高人们生活质量的重要活动之一。

现基于人们对旅游的热情，本文准备研究最合理的旅游方案，来满足不用家庭对暑假旅游的不同需求，解决他们在需求中所遇到的问题。为此我们根据他们经济状况的不同，先将他们分为贫穷、一般和上等三类家庭。由于贫穷家庭一般不会参加旅游活动，所以我们将重点考虑一般家庭和上等家庭。我们将利用Matlab、蚁群算法、Floyd算法、哈密顿回路、层次分析法等，通过建立数学模型来解决问题。关键词：Matlab 蚁群算法 Floyd算法哈密顿回路层次分析法家庭旅游问题

Summary

In recent years,China’s comprehensive national strength increasing,growing economic strength.There are a lot of relationship between the development of Chinese tourism industry.Along with our country into a well-off society,people’s living standards improve,tourism has become one of the

important activities o improve people’s life quality.

Now,based on people’s enthusiasm for tourism,this article to study the most reasonable summer tourism plan,to solve the different needs of different family to travel to solve their problems in demand.We according to different economic conditions,the first divided them into poverty,general and fine three types of families.Due to poor families generally do not participate in tourism activities,so we will focus on general families and fine families travel,use of Matlab,ant colony algorithm,Floyd hierarchy

algorithm,Hamiltonian

the

circuit,analytic establishment

process(ahp),through

mathematical model to solve the problem of tourism.

Key words:Matlab ant colony algorithm Floyd algorithm Hamiltonian circuit analytic hierarchy process(ahp) Family travel issues.

一、问题重述

随着近年来旅游业的不断发展，我国海南三亚地区越来越吸引广大的游客。在本文中，我们将研究一下不同家庭去三亚旅游的路线设计问题：

1.一般家庭：在暑假一个月内，其资金有限（2000元），让其尽可能的游览最多的景点。

2.上等家庭：在暑假一个月内，其资金不限，让其尽可能

的游览最多的景点。

二、问题分析

/km 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

在收集三亚各个主要旅游景点之间的路程（表一）、各个景点的最佳逗留时间（表二）等信息的基础上，我们将做一下数据分析和抽象：表一：

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0 51 39.9 47.3 42.4 28.6 69.8 29.1 35 66.1 66.7 30.2 63.5 50 20.7 29.3 51 0 29.7 5.2 11.1 37.3 24 44.1 52.5 16.4 97 25.1 17.7 2.3 51.2 38 39.9 29.7 0 24.9 25.9 26 54.8 42.4 50.8 46.1 86.3 7.1 48.4 29.2 50 26.7 47.3 5.2 24.9 0 3.2 33.9 28 42.3 50.8 21.6 9.39 19.9 21.6 4.6 49.7 34.6 42.4 11.1 25.9 3.2 0 27 29.8 40.3 50.7 26.5 96.4 17.8 23.5 6.5 47.7 33.2 28.6 37.3 26 33.9 27 0 59.8 24.9 33.4 53.6 76.7 20.2 53.5 36.6 32.5 2.2 69.8 24 54.8 28 29.8 59.8 0 67.7 76.1 13.8 123.6 47.4 9.6 22.4 75 61.6 29.1 44.1 42.4 42.3 40.3 24.9 67.7 0 8.8 63.9 71.1 29 60.8 44.6 26.9 26.1 35 52.5 50.8 50.8 50.7 33.4 76.1 8.8 0 74.6 66.2 36.6 69.6 55.1 23.6 34.2 66.1 16.4 46.1 21.6 26.5 53.6 13.8 63.9 74.6 0 112.5 41.3 7.3 18.5 71.5 54.2 66.7 97 86.3 9.39 96.4 76.7 123.6 71.1 66.2 112.5 0 81 117 96.7 55.8 78.4 30.2 25.1 7.1 19.9 17.8 20.2 47.4 29 36.6 41.3 81 0 41.1 24.7 35.9 20.8 63.5 17.7 48.4 21.6 23.5 53.5 9.6 60.8 69.6 7.3 117 41.1 0 18.6 68.5 54.6 50 2.3 29.2 4.6 6.5 36.6 22.4 44.6 55.1 18.5 96.7 24.7 18.6 0 52.2 37.4 20.7 51.2 50 49.7 47.7 32.5 75 26.9 23.6 71.5 55.8 35.9 68.5 52.2 0 34.3 29.3 38 26.7 34.6 33.2 2.2 61.6 26.1 34.2 54.2 78.4 20.8 54.6 37.4 34.3 0 29.1 37.9 26.6 34.4 32.6 0.533 60.5 25.5 33.7 54 78.2 20.6 54 37.2 33.7 1.6 35

24.2

6.7

19.2

48.6

34.7

39.1

40.4

81.7

2.3

42.1

23.6

21.7

1.费用有限，时间有限，且要尽可能多的游览景点，即要综合考虑各景点到达另一个景点的交通便捷相关信息条件，当然也还要尽量避免住宿问题（筛选出最优的旅游路线），这要用到层次分析法。

2.时间有限，费用不限，要尽可能多的游览景点，即要综合考虑各景点到达另一个景点的交通便捷相关信息条件，当然

17 18 29.1 35 37.9 24.226.6 6.7 34.4 19.232.6 19 0.533 21 60.5 48.625.5 34.733.7 39.154 40.478.2 81.720.6 2.3 54 42.137.2 23.633.7 39 1.6 21.70 21.521.5

路程

也还要尽量避免住宿问题（筛选出最优的旅游路线），这也要用到层次分析法。

为了解决上述两个问题：我们需要分解来做。首先，解决问题一：它可以看成是“只有费用有限，尽可能多的游览景点，如何设计旅途行程表”和“只有时间有限，尽可能多的游览景点，如何设计旅旅途行程表”的“双重约束”，即可在问题、的基础上求解。

其次，解决问题二：它可以看成是在“旅游费用不限，将10个景点全部旅游完，至少需要的时间”这个问题的基础上求解。

三、模型假设

四、定义与符号的说明

五、模型的建立与求解六、2、构造判断矩阵

通过权重比较，建立矩阵{Wij}55，其中ij表示第i项因素相对于第j项因素的重要性，

以1为界限，大于1表示i比j重要，小于1反之，采用1-9的数值标度，建立判断矩阵如下：

113W

113

311114

4122112938

191 3181

3、判断矩阵是通过旅游者的主观评价给出的标度，可能有些时候并不一致，比如该局正应当满足：a12

CaC1C11

，且a23221，可是事实上旅行者却; a131

C3a31C2a21C3a31

有可能给出不一致的数值，因此需要将其一致化。

4、判断矩阵一致化

定义：设有正互反成对比较矩阵：

W1W1W1a1 a1 ,  , a11121n

WWW12n

W2W2W2a21 a221 ,  , a2n

W1W2Wn

A Wi

   aij

Wj



WWWnnana  a1 n1n2nnW1W2Wn

除满足：（i）正互反性：即

aij aij0

( 或 aijaji1) aji

则称满足上述条件的正互反对称矩阵A为一致性矩阵，简称一致阵。

我们考察一致性矩阵（一致阵）性质：性质1：A的秩 Rank(A)=1

A的唯一非0的特征根为n

性质2：A的任一列（行）向量都是对应特征根n的特征向量：

即有(特征向量、特征值)：

七、模型的评价

W1W1W2AW

1WnW1

W1W2W2W2WnW2

W1WnW1

W2W2Wn，则向量W W

Wn3

Wn

W1

W1

满足A

WnW1

W1W2WnW2W1Wn





Wn

WnW11W2nW2n WnnWn

即：(AnI)0 可知一致矩阵的含义：n件物体M1, M2, ,Mn，它们重量分别为W1, W2 , ,Wn，将他们两两比较重量，其比值构成一致矩阵，若用重量向量

W1

W

W2右乘A，则A的特征值为n，以n为特征根的特征向量经归一化后就表示诸因

Wn

素对上层因素的权重。心跳达人的正互反对称矩阵：

1.0000

0.33331.0000

1.00003.00003.00001.00003.00000.33330.1456

1.00000.25000.50000.11110.0497

4.00001.00002.00000.3333，特征向量：0.1772



2.00000.50001.00000.12500.0961

9.00003.00008.00001.00000.5315

5)一致性检验CI

maxn

CIj，CR

n1RI

ajCI3

a

j

，当CR

RIj

为该矩阵满足一致性。在这里，我们计算的CR0.01970.1，通过检验。 6)准则层正互反成对比较矩阵建立（仅以费用因素为例）。

求解各景点在同一因子之下相比较的权重

同理，可以得到其它几种准则因子在“民俗文化”的效用取向之下各景点的权重

1) 计算组合权并排序

由公式Wi

ab (i1,,n)计算“民俗文化”的决策结果

jijj1

(3)游客根据自己对目地风格的需求，按照权重配比由高到低的顺序，得出最佳方案。

(4)我们把家庭的经济状况分为三种情况：贫穷、一般、富有。因为家庭条件较困难的一般不会选择旅游，所以我们不讨论这种情况。下面，我们就经济条件一般和富有的列出来以下两个表格。

旅行商问题的基本理论

某旅行商欲往n个城市推销货物，从某个城市出发，沿途经过各个城市一次后返回出发城市，要确定一条行走的路线，使得总路径最短。这个问题称为旅行

[1]

商问题（TSP）。用图论的术语说，就是在一个赋权完全图中，找出一个有最小权的Hamilton 圈C。称这种圈为最优圈。与最短路问题及连线问题相反，尽管目前还没有求解旅行商问题的有效算法。但是却有一个可行的办法是求一个Hamilton 圈，然后适当修改以得到具有较小权的另一个Hamilton 圈。修改的方法叫做改良圈算法。设初始圈Cv1v2

vnv1。

（1）对于1i1jn,构造新的Hamilton圈：

Cijv1v2vivjvj1vj2vi1vj1vj2

vnv1,

1i

它是由C中删去的边viv,添加边vi和vji1和vjvj1而vv1j得到的。若

w(vivj)w(vi1vj1)w(vivi1)w(vjvj1)，则以Cij代替C，Cij叫做C的改良圈。（2）转（1），直至无法改进，停止。

用改良圈算法得到的结果几乎可以肯定不是最优的。为了得到更高的精确度，在不给定起始位置的前提下，可以选择不同的初始圈，重复进行n次算法，以求得精确的结果。

4.1.2 旅行商问题的数学表达式

设城市的个数为n,dij是两个城市i与j之间的距离，xij0或1（1表示走过城市i到城市j的路，0表示没有选择走这条路）。则有

mindijxij

ij

s..t

x

j1n

1,i1,2,1,

j1,2,

,n,(每个点只有一条边出去)

x

i1i,js

,n,(每个点只有一条边出去)

,n}

x

s1,2sn1,s{1,2,

(各起点和终点外，各边不构成圈)

4.1.3 模型一求解

按附件所给各城市的顺序编号1,2,,100，用两城市间的直线距离代表两城市的距离，我们以任意两点之间的最短距离矩阵为权重矩阵，利用w1(i,j)100100构造无向图UG1，据题意并不知周先生的起始地点，因此利用Matlab软件重复进行100次改良圈算法，尝试以每一个城市为出发点（算法见附录），首先设

按改良圈算法求出此时的最优圈后，改变初始圈Cv2v1vnv2,Cv1v2vnv1,，依次进行下去，求出符合要求的最短距离的最优圈circle1，保证了从终点返回到

出发点的距离也最短，即周游先生的最短旅行方案，如下：

路线

我们运用Matlab软件模拟出了周先生最短的旅游线路，见图1。其中每一个‘*’表示每个城市，折线表示旅游线路，标有51的城市是周先生旅行的起点，标有99的城市是周先生旅游的终点，由终点99返回起点51所构成的闭合回路就是周先生最短的旅行路线，其费用为问题二

对于问题二，我们同样运用问题一中所建的模型一，将模型一中的权值“最短距离”换为“最少花费”，建立模型二。利用下面的分段函数求出花费最小的矩阵F(i,j)100100：

F(i,j)d(i,j)1.5,d(i,j)500

F(i,j)1.4d(i,j),500d(i,j)1000 F(i,j)1.1d(i,j),1000d(i,j)

问题二中规定了周游先生旅游的起始城市为第一个城市。因此利用

F(i,j)100

100

为w2(i,j)100100构造无向图UG2，再利用Matlab软件进行1次改良圈算

法（算法见附录），就会得到最优圈circle2，即花费最少的旅行路线。如下：路线

我们运用Matlab软件模拟出了周先生最经济的旅游线路，见图2。其中每一个‘*’表示每个城市，折线表示旅游线路，标有1的城市是周先生旅行的起点，标有100的城市是周先生旅游的终点，由终点100返回起点1所构成的闭合回路就是周先生最经济的旅行路线，其长度为140430元。

4.3.1多目标规划思想

基于选择既省钱、省时又方便的最佳旅游方案，我们建立了用序贯式算法求解多目标规划[2]的模型。序贯式算法的核心是根据优先级的先后次序，将目标规划问题分解成一系列的单目标规划问题，然后再依次求解。

求解目标规划的序贯算法：

对于k1,2,

,q,求解单目标规划

mins..t



z(wkjdjwkjdj)

j1

(1)

,l,k1

(2)(3)(4) (5)

ax

ijj1n

(,)bi,i1,

cx

ijj1l



j1

ddi1,2,jiigi,

(wd

xj0,

jwsjdj)zs,s1,2,

j1,2,,n,l

di,di0,i1,2,

(6)



其最优目标值为zk，当k1时，约束（4）为空约束。当kq时，zq所对

应的解x为目标规划的最优解。

4.3.1模型的求解

附录

问题一最短旅行方案的Matlab源程序 clc,clear %主函数：

function main load mydata global d

d=zeros(100); C=zeros(100,102); for i=1:100 for j=1:100

d(i,j)=6378.140*acos(sin(y0(i)*pi/180)*sin(y0(j)*pi/180)...

+cos(y0(i)*pi/180)*cos(y0(j)*pi/180)*cos((x0(i)-x0(j))*pi/180)); end end

xlswrite('juli',d,'sheet1') [i,j,y]=find(d); a=sparse(i,j,y); a=tril(a); L=size(d,1) for i=1:100

c1=[i 1:100 100];

[circle,long]=modifycircle(c1,L);

c2=[i 100 1:100];%改变初始圈，该算法的最后一个顶点不动 [circle2,long2]=modifycircle(c2,L); if long2

circle=circle2;

end

changdu(i)=long; C(i,:)=circle; circle,long end

[zuiyou,I]=min(changdu); circle0=C(I,:)

xlswrite('luxian1.xls',circle0,'sheet1') x=[x0(circle0(1:end-1)) x0(51)]; y=[y0(circle0(1:end-1)) y0(51)]; scatter(x,y,'*') hold on plot(x,y)

xlabel('经度') ylabel('纬度') gtext('51'); gtext('99');

%被调用函数：

function [circle,long]=modifycircle(c1,L); global d flag=1;

while flag>0 flag=0; for m=1:L-3 for n=m+2:L-1

if d(c1(m),c1(n))+d(c1(m+1),c1(n+1))

c1(m+1:n)=c1(n:-1:m+1); end end end end

long=d(c1(1),c1(L)); for i=1:L-1

long=long+d(c1(i),c1(i+1)); end

circle=c1;

c题家庭暑假旅游套餐的设计

摘要

Summary

important activities o improve people’s life quality.

algorithm,Hamiltonian

the

circuit,analytic establishment

process(ahp),through

mathematical model to solve the problem of tourism.

Key words:Matlab ant colony algorithm Floyd algorithm Hamiltonian circuit analytic hierarchy process(ahp) Family travel issues.

一、问题重述

随着近年来旅游业的不断发展，我国海南三亚地区越来越吸引广大的游客。在本文中，我们将研究一下不同家庭去三亚旅游的路线设计问题：

1.一般家庭：在暑假一个月内，其资金有限（2000元），让其尽可能的游览最多的景点。

2.上等家庭：在暑假一个月内，其资金不限，让其尽可能

的游览最多的景点。

二、问题分析

/km 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

在收集三亚各个主要旅游景点之间的路程（表一）、各个景点的最佳逗留时间（表二）等信息的基础上，我们将做一下数据分析和抽象：表一：

24.2

6.7

19.2

48.6

34.7

39.1

40.4

81.7

2.3

42.1

23.6

21.7

2.时间有限，费用不限，要尽可能多的游览景点，即要综合考虑各景点到达另一个景点的交通便捷相关信息条件，当然

17 18 29.1 35 37.9 24.226.6 6.7 34.4 19.232.6 19 0.533 21 60.5 48.625.5 34.733.7 39.154 40.478.2 81.720.6 2.3 54 42.137.2 23.633.7 39 1.6 21.70 21.521.5

路程

也还要尽量避免住宿问题（筛选出最优的旅游路线），这也要用到层次分析法。

其次，解决问题二：它可以看成是在“旅游费用不限，将10个景点全部旅游完，至少需要的时间”这个问题的基础上求解。

三、模型假设

四、定义与符号的说明

五、模型的建立与求解六、2、构造判断矩阵

通过权重比较，建立矩阵{Wij}55，其中ij表示第i项因素相对于第j项因素的重要性，

以1为界限，大于1表示i比j重要，小于1反之，采用1-9的数值标度，建立判断矩阵如下：

113W

113

311114

4122112938

191 3181

3、判断矩阵是通过旅游者的主观评价给出的标度，可能有些时候并不一致，比如该局正应当满足：a12

CaC1C11

，且a23221，可是事实上旅行者却; a131

C3a31C2a21C3a31

有可能给出不一致的数值，因此需要将其一致化。

4、判断矩阵一致化

定义：设有正互反成对比较矩阵：

W1W1W1a1 a1 ,  , a11121n

WWW12n

W2W2W2a21 a221 ,  , a2n

W1W2Wn

A Wi

   aij

Wj



WWWnnana  a1 n1n2nnW1W2Wn

除满足：（i）正互反性：即

aij aij0

( 或 aijaji1) aji

则称满足上述条件的正互反对称矩阵A为一致性矩阵，简称一致阵。

我们考察一致性矩阵（一致阵）性质：性质1：A的秩 Rank(A)=1

A的唯一非0的特征根为n

性质2：A的任一列（行）向量都是对应特征根n的特征向量：

即有(特征向量、特征值)：

七、模型的评价

W1W1W2AW

1WnW1

W1W2W2W2WnW2

W1WnW1

W2W2Wn，则向量W W

Wn3

Wn

W1

W1

满足A

WnW1

W1W2WnW2W1Wn





Wn

WnW11W2nW2n WnnWn

即：(AnI)0 可知一致矩阵的含义：n件物体M1, M2, ,Mn，它们重量分别为W1, W2 , ,Wn，将他们两两比较重量，其比值构成一致矩阵，若用重量向量

W1

W

W2右乘A，则A的特征值为n，以n为特征根的特征向量经归一化后就表示诸因

Wn

素对上层因素的权重。心跳达人的正互反对称矩阵：

1.0000

0.33331.0000

1.00003.00003.00001.00003.00000.33330.1456

1.00000.25000.50000.11110.0497

4.00001.00002.00000.3333，特征向量：0.1772



2.00000.50001.00000.12500.0961

9.00003.00008.00001.00000.5315

5)一致性检验CI

maxn

CIj，CR

n1RI

ajCI3

a

j

，当CR

RIj

为该矩阵满足一致性。在这里，我们计算的CR0.01970.1，通过检验。 6)准则层正互反成对比较矩阵建立（仅以费用因素为例）。

求解各景点在同一因子之下相比较的权重

同理，可以得到其它几种准则因子在“民俗文化”的效用取向之下各景点的权重

1) 计算组合权并排序

由公式Wi

ab (i1,,n)计算“民俗文化”的决策结果

jijj1

(3)游客根据自己对目地风格的需求，按照权重配比由高到低的顺序，得出最佳方案。

旅行商问题的基本理论

[1]

vnv1。

（1）对于1i1jn,构造新的Hamilton圈：

Cijv1v2vivjvj1vj2vi1vj1vj2

vnv1,

1i

它是由C中删去的边viv,添加边vi和vji1和vjvj1而vv1j得到的。若

w(vivj)w(vi1vj1)w(vivi1)w(vjvj1)，则以Cij代替C，Cij叫做C的改良圈。（2）转（1），直至无法改进，停止。

4.1.2 旅行商问题的数学表达式

设城市的个数为n,dij是两个城市i与j之间的距离，xij0或1（1表示走过城市i到城市j的路，0表示没有选择走这条路）。则有

mindijxij

ij

s..t

x

j1n

1,i1,2,1,

j1,2,

,n,(每个点只有一条边出去)

x

i1i,js

,n,(每个点只有一条边出去)

,n}

x

s1,2sn1,s{1,2,

(各起点和终点外，各边不构成圈)

4.1.3 模型一求解

按改良圈算法求出此时的最优圈后，改变初始圈Cv2v1vnv2,Cv1v2vnv1,，依次进行下去，求出符合要求的最短距离的最优圈circle1，保证了从终点返回到

出发点的距离也最短，即周游先生的最短旅行方案，如下：

路线

F(i,j)d(i,j)1.5,d(i,j)500

F(i,j)1.4d(i,j),500d(i,j)1000 F(i,j)1.1d(i,j),1000d(i,j)

问题二中规定了周游先生旅游的起始城市为第一个城市。因此利用

F(i,j)100

100

为w2(i,j)100100构造无向图UG2，再利用Matlab软件进行1次改良圈算

法（算法见附录），就会得到最优圈circle2，即花费最少的旅行路线。如下：路线

4.3.1多目标规划思想

求解目标规划的序贯算法：

对于k1,2,

,q,求解单目标规划

mins..t



z(wkjdjwkjdj)

j1

(1)

,l,k1

(2)(3)(4) (5)

ax

ijj1n

(,)bi,i1,

cx

ijj1l



j1

ddi1,2,jiigi,

(wd

xj0,

jwsjdj)zs,s1,2,

j1,2,,n,l

di,di0,i1,2,

(6)



其最优目标值为zk，当k1时，约束（4）为空约束。当kq时，zq所对

应的解x为目标规划的最优解。

4.3.1模型的求解

附录

问题一最短旅行方案的Matlab源程序 clc,clear %主函数：

function main load mydata global d

d=zeros(100); C=zeros(100,102); for i=1:100 for j=1:100

d(i,j)=6378.140*acos(sin(y0(i)*pi/180)*sin(y0(j)*pi/180)...

+cos(y0(i)*pi/180)*cos(y0(j)*pi/180)*cos((x0(i)-x0(j))*pi/180)); end end

xlswrite('juli',d,'sheet1') [i,j,y]=find(d); a=sparse(i,j,y); a=tril(a); L=size(d,1) for i=1:100

c1=[i 1:100 100];

[circle,long]=modifycircle(c1,L);

c2=[i 100 1:100];%改变初始圈，该算法的最后一个顶点不动 [circle2,long2]=modifycircle(c2,L); if long2

circle=circle2;

end

changdu(i)=long; C(i,:)=circle; circle,long end

[zuiyou,I]=min(changdu); circle0=C(I,:)

xlswrite('luxian1.xls',circle0,'sheet1') x=[x0(circle0(1:end-1)) x0(51)]; y=[y0(circle0(1:end-1)) y0(51)]; scatter(x,y,'*') hold on plot(x,y)

xlabel('经度') ylabel('纬度') gtext('51'); gtext('99');

%被调用函数：

function [circle,long]=modifycircle(c1,L); global d flag=1;

while flag>0 flag=0; for m=1:L-3 for n=m+2:L-1

if d(c1(m),c1(n))+d(c1(m+1),c1(n+1))

c1(m+1:n)=c1(n:-1:m+1); end end end end

long=d(c1(1),c1(L)); for i=1:L-1

long=long+d(c1(i),c1(i+1)); end

circle=c1;

c题家庭暑假旅游套餐的设计2,新

相关内容

热门内容

标签