海岛优化专项方案答案.doc

数学建模.doc
123

海岛优化方案分析
摘要
经济水平增长，带动了旅游业发展。本文研究了5个岛屿与港口之间最短距离及乘船筹划。以最小费用为准则，制定了最优化一日游、二日游套餐。以及为满足游客需要，通过考虑游客量及费用两大方面，找到建设旅馆最优地方，与最优规模。
问题一：对于一日游问题，一方面考虑单线整体旅游，以所游两地最大承受能力最小值为游客量对=10种路线分别计算，得到每条路线费用。考虑到游客人数不定，因此以旅游线进行分类分为6种，1、2、3、4、5。分别对这5种线，从10种路线中进行最优匹配。依照所旅游景点尽量分散，旅客尽量多，总费用尽量少原则进行匹配。依照

衡量得到最优五种一日游套餐
对两日游，按种考虑，运用算法，得到每种路线最优走法。同步仅有C、D两地可以入住，因此在参观景点顺序排列时第二个位置（游客在旅游地直接入住）或第三个位置（游客不在旅游地入住，在第二天旅游地旅游之前先入住）必要是C、D两景点中至少一种。并且在游客规模取景点承受能力人数与旅馆容纳能力最小值作为该次旅游人数规模。结合最有走法，与条件限制。另一方面，依照一日游原则以相似办法可以得到最优两种套餐，见表格5

问题二：在假设所有景点都达到接待游客能力后，得到所建旅店最大规模，分别计算各点到B、C、D点在最大规模情形下，依照算法3，运用公式

得到

找到最低费用位置，因而选用B岛为新建旅馆地点。
同步将规模按阶减少，运用相似算法得到关于四组数据：（245,33125），(220，39288)，（200,27370），（180,30311）将这四组数据以规模人数为轴，以总费用为轴。用插值与拟合办法得到、之间相应关系，取变化率最小，即图线最平缓点值进行取整，作为新建旅馆规模人数。即在B点建立旅馆且最大承受能力为200人。
由于在考虑一日游问题上，没有考虑住宿问题，因此一日游套餐不需要要改动。但是二日游问题上有一条最短途径由于B不能入住而舍去，需要改动。然后以相似办法制定相应套餐。
符号阐明

因租船所产生费用
路程费
：损失费
租大船条数
租小船条数
：游客人数

每条路线最短路程

船只每公里费用系数
第个景点游客承受力
第个景点到B点费用

表达所选两景点中，接受游客能力中最小值。
：景点个数。
问题分析
问题一
分析：一日游：由表1岛屿与港口之间距离，先绘制出海岛与港口粗略平面分布图。再运用matlab floyd算法，求在两点间最短路。一方面考虑旅行费问题，由已求出五个海岛与港口六个点任意两点最短距离，计算出（种）每种路线最短路程，然后依次得到相应每条路线路程费用。另一方面考虑游船损失问题。依照A、B、C、D、E各景点承载游客能力，因此，每条路线普通有：大船，小船之内进行合理匹配。依照已求路线，求每条路线两个景点中最大承载能力最小值为该条路线规模人数，计算出相应。最后运用公式

将成果按从小到大进行排列，依照游客人数不同，考虑到实际问题，依照旅游线条数进行分类，得到5种分类。考虑到每个套餐中景点分散度，最短距离与总费用三者之间所占权重按从小到大排列得到最优旅游套餐，取前六种路线即为旅游套餐。
两日游：按种考虑，运用算法，得到每种路线最优走法。同步仅有C、D两地可以入住，因此在参观景点顺序排列时第二个位置（游客在旅游地直接入住）或第三个位置（游客不在旅游地入住，在第二天旅游地旅游之前先入住）必要是C、D两景点中至少一种。考虑到旅店容纳人数。游客规模取景点承受能力人数与旅馆容纳能力最小值作为该次旅游线人数规模。结合最有走法、条件限制，依照一日游算法，得到相应、。另一方面，依照制定一日游套餐原则，以相似办法可以得到最优二日游套餐。

问题二
分析：建设新旅店问题，只需考虑两大准则，建设地点、建设规模。建设地点：一方面以衡量原则最小来标量。其中：各个景点分别到最短距离总和，：假设在同一时刻，各个景点都达到最大承载能力。选用各个景点最大承载能力总人数和（景点最大游客量）50%减去C、D景点所承受能力总人数。得到建立旅馆最大容纳规模。依照损失费用标量得到。运用

将B、C、D各点状况依次算出，进行比较得到成果。（其中 ，)
由将、、依次算出，取min(,,)位置，即为新建旅馆建设地点。建设国模：考虑到景点每天游客流量不同，因此将最大游客流量按阶（以20为一种单位）进行计算分别得到（245，），(220，),(200，)，（180，）四点，然后运用插值与拟合办法得到，以规模人数，总费用有关关系图像，取斜率最小（图像最平缓）人数规模阶段（近似取整），拟定建旅馆规模大小。

由于在考虑一日游问题上，没有考虑住宿问题，因此一日游套餐不需要要改动。但是二日游问题上有一条最短途径由于B不能入住而舍去，需要改动。重新考虑最短路线，最优游客人数，最优购船筹划，游览费用。同步在于其他四条路线进行比较，运用原先相似办法，制定二日游套餐。

模型建立与求解
问题一
由表1岛屿及港口之间距离，运用软件，画出海岛与港口平面分布图
图1：

＜1＞ 一日游问题：假设该旅游区每天均有大量游客来旅游，超过了各个景点接待游客能力。由于每个景点游半天，因而一日游涉及到2个景点选用。因而有种情形，一方面运用matlab floyd算法求出任意两点（海岛与港口）间最短距离得到如下表格
表格1：

加权图任意两个岛屿之间距离和途径
距离矩阵
途径矩阵
=
=
由此，得到相应10条游览路线最短路程。
依照路程费用公式： 结合已经求出最短路程，得到每条路线路程费用。
由于每个景点最大承载能力有限制，因此选用每条路线中两个景点最大承载能力最小值，作为该条游览路线最大游览人数。依照大船、小船容纳人数，依此拟定每条路线相应、。然后依照公式：，计算出每条路线损失费用。
由于费用涉及客均费用与损失费用，即

通过普通算法2（路程费用，损失费用）得到每种路线总游览费用。
对于各种购船方案如下解决。其中：由于 V拟定相应、会得到相相应分派，也许会得到两种分派，、
例如：
（游船少载50人） (游船少载30人)
针对：

针对：

选用乘船方案
将这10种方案依次算出游览费用。并且按照路线、最短路程、大船数量、小船数量、游览总费用，并按从小到大顺序排列绘制成表格。
表格2：

路线
最短路程

总费用

181
2
1
488.7

215
2
1
580.5

231
2
1
623.7

242
3
0
628.22

233
3
0
727.40

235
3
0
779.03

201
0
6
1518.43

215
0
6
1566.44

228
0
6
1661.14

253
0
6
1843.28
考虑到每天景点游客量不拟定性，根据每天景点游览路线总条数进行分类。大体提成5类，1、2、3、4、5（1：只有一种景点达到最大承载能力。5所有景点，在同一时刻都达到最大承载能力）按照景点分散度，旅客人数及总费用，运用函数衡量，得到最优匹配，选用合理5种匹配绘制成表格如下。
表格3：

线条数
最佳人数
最佳路线
最佳分派（人数与路线相相应）
1
经E210

210
1
不经E240

240
2
全经E420

210
210
2
无规定520

240
280
3
无规定730

240280

二日游：由于每日只能游2个景点，因而2日游需对4个景点进行旅游，在5个景点中，因此有5种景点旅游选取，分别是：

将5种情形分别进行讨论：
1、 一方面运用matlab行遍性问题中TSP算法（程序见附录求最短路）可以得到由P点出发通过所有A、B、C、D回到P最短途径图线。但由于，仅有C、D两个岛屿有游客可供住宿，因此在最短路线中，规定第2个位置（游客可以在旅游景点入住）或第3个位置（游客可以在旅游景点入住然后参观）必要是C、D中至少得任意一种。若所得路线满足条件，则是所求路线。否则需进行下步计算。将ABCD进行满足条件全排列，分别运用算法计算每个排列人均费用，取人均费用最小排列为该四个景点最优游览路线，并且得到相应路程费用。。取每条路线中四个景点最大承载能力、旅馆最大容纳能力最小值，最为该条路线最优游览人数。依照一日游求解损失费用办法，得到每条路线在最优人数下损失费用。然后把得到数据按照路线、最短路程、大船数量、小船数量、人均费用回执成表格。得到如下表格。
表格4

景点

路线
最
短距离

人均总费用

248
2
1
669.6

259
2
1
590.15

245
2
1
803.25

295
2
1
940.21

254
2
1
840.12
考虑到实际问题，考虑到每个套餐中景点分散度，最短距离与总费用三者之间所占权重，依照一日游套餐制定与原则吗，得到如下二日游旅游套餐。将所到数据按照最优路线条数，最优路线、最短路程、最优大船数量、最优小船数量、人均费用挥之表格，如下。
表格5：

路线条数
最佳路线
最佳人数

人均费用
1

240
2 1
669.6
1

210
2 1
590.15
2

450
4 2
1609.81

注：由于D住宿承受力是200，因而当达到景点容纳能力后，若在D入住会不不大于住宿承载力，因而在考虑及路线时，此时客人数量只能取两者最小一种，因而双方考虑后到如上表格
问题二
此问题规定拟定新建旅馆地点与规模人数，因此分两某些进行
1.地点
一方面，假设在同一时刻所有景点都满员，则得到=1450 50%=725 同步假设C、D旅馆都达到最大承受能力，因此所建旅馆最大规模为
725-200-280=245（人）
另一方面分别运用算法计算出、、

因而可得
选用B点为所建旅馆地点。
2.规模
每天游览景点人数不同，因而以新建旅馆最大承受能力依次递减20人，分析相应变化状况。由算法5可得如下4组数据
（245，33125） （220,44445） （200,27370） （180,30311）。
另一方面，分别将这4组数据，运用matlab插值与拟合办法，得到关于以规模人数为轴，以总费用为轴相应关系如图

用matlab中figure工具找到最平缓位置（斜率变化不明显）。因而得到此时在180205。然后，进行精细分析。用matlab中坐标工具，可以得到该曲线中最低点（199,27365）如图

因而，取=200即为该新旅馆规模人数。
由于一日游问题不考虑住宿问题，因而在游览套餐中一日游不需要改动。由于二日游问题在考虑住宿条件。在增长新旅馆后，缩小了条件限制，扩大了可选取点。当前二日游问题上，游览路线第二个位置或第三个位置可以是B、C、D、三点重任意一种。因而在所求最短途径中因B不能住宿而舍去路线，当前需要重新进行考虑。由于

是如上所说问题，因此通过重新计算后年得到

相应最短距离：258，大船数量：2，小船数量：0，最优人数：200，总费用：578.025，将新路线进行重新考虑，因而二日游套餐需要改动，改动成果如下。
表格6：

路线条数
最佳路线
最佳人数

人均费用
1

200
2 0
578.02
1

210
2 1
590.15
2

450
4 2
1609.81

程序附件
求最短路matlab程序
a=[0 46 21 50 60 70;
46 0 30 32 55 115;
21 30 0 48 53 90;
50 32 48 0 21 95;
60 55 53 21 0 85;
70 115 90 95 85 0]
[D,R]=floyd(a)
%function[D,R]=floyd(a);

n=size(a,1);
D=a
for i=1:n
for j=1:n
R(i,j)=j;
end
end
R

for k=1:n
for i=1:n
for j=1:n
if D(i,k)+D(k,j)<D(i,j)
D(i,j)=D(i,k)+D(k,j);
R(i,j)=R(i,k);
end
end
end
k
D
R
end

D =

0 46 21 50 60 70
46 0 30 32 53 115
21 30 0 48 53 90
50 32 48 0 21 95
60 53 53 21 0 85
70 115 90 95 85 0

R =

1 2 3 4 5 6
1 2 3 4 4 6
1 2 3 4 5 6
1 2 3 4 5 6
1 4 3 4 5 6
1 2 3 4 5 6

二日游最短路lingo程序：
MODEL：
SETS：
CITY / 1.. 6/：U；！U( I) = sequence no. of city；
LINK( CITY，CITY)：
DIST， ！The distance matrix；
X； ！X( I，J) = 1 if we use link I，J；
ENDSETS
DATA： !Distance matrix，it need not be symmetric；
DIST =0 70 115 90 95
70 0 46 21 50
115 46 0 30 32
90 21 30 0 48
95 50 32 95 0；
ENDDATA
!The model:Ref. Desrochers & Laporte，OR Letters，
Feb. 91；
N = @SIZE( CITY)；
MIN = @SUM( LINK：DIST * 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 constraints；
！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)))；
！Make the X's 0/1；
@FOR( LINK：@BIN( X))；
！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
选取方案matlab程序
x=[ 240 240 240 210 250 280 210 250 210 210];y=[231 181 215 215 235 242 253 233 228 201];a=x-y

a =

9 59 25 -5 15 38 -43 17 -18 9