海岛优化方案答案.doc

《海岛优化方案答案.doc》由会员分享，可在线阅读，更多相关《海岛优化方案答案.doc（14页珍藏版）》请在三一办公上搜索。

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

2、，得到每种路线的最优走法。同时仅有C、D两地可以入住，所以在参观景点次序排列时第二个位置游客在旅游地直接入住或第三个位置游客不在旅游地入住，在第二天旅游地旅游之前先入住必须是C、D两景点中至少一个。并且在游客规模取景点承受能力的人数与旅馆容纳能力的最小值作为该次旅游的人数规模。结合最有走法，与条件限制。其次，根据一日游的原则以一样的法可以得到最优的两种套餐，见表格5问题二：在假设所有景点都到达接待游客的能力后，得到所建旅店的最大规模，分别计算各点到B、C、D点在最大规模的情形下，根据算法3，利用公式得到找到最低费用的位置，因此选取B岛为新建旅馆地点。同时将规模按阶降低，利用一样的算法得到关于的

3、四组数据：245,33125，(220，39288)，200,27370，,30311将这四组数据以规模人数为轴，以总费用为轴。用插值与拟合的法得到、之间的相应关系，取变化率最小，即图线最平缓的点的值进展取整，作为新建旅馆的规模人数。即在B点建立旅馆且最大承受能力为200人。由于在考虑一日游问题上，没有考虑住宿问题，所以一日游套餐不需要要改动。但是二日游问题上有一条最短路径因为B不能入住而舍去，需要改动。然后以一样的法制定相应的套餐。 符号说明因租船所产生的费用路程费：损失费租大船的条数租小船的条数：游客人数 每条路线的最短路程船只每公里费用系数第个景点的游客承受力第个景点到B点的费用表示所选

4、两景点中，承受游客的能力中的最小值。：景点个数。问题分析问题一分析：一日游：由表1岛屿与港口之间距离，先绘制出海岛与港口粗略的平面分布图。再利用matlab floyd算法，求在两点间的最短路。首先考虑旅行费问题，由已求出的五个海岛与港口六个点的任意两点的最短距离，计算出种每种路线的最短路程，然后依次得到相应的每条路线的路程费用。其次考虑游船损失问题。根据A、B、C、D、E各景点的承载游客的能力，所以，每条路线一般有：大船，小船之进展合理匹配。根据已求的路线，求每条路线两个景点中最大承载能力的最小值为该条路线的规模人数，计算出相应的。最后利用公式将结果按从小到大进展排列，根据游客的人数不同，考

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

6、最优二日游套餐。问题二分析：建立新旅店问题，只需考虑两大准则，建立地点、建立规模。建立地点：首先以衡量标准最小来标量。其中：各个景点分别到的最短距离总和，：假设在同一时刻，各个景点都到达最大承载能力。选取各个景点的最大承载能力的总人数的和景点最大游客量的50%减去C、D景点所承受能力的总人数。得到建立旅馆的最大容纳规模。根据损失费用标量得到。利用将B、C、D各点的情况依次算出，进展比较得到结果。其中 ，)由将、依次算出，取min(,)的位置，即为新建旅馆的建立地点。建立国模：考虑到景点每天的游客流量不同，所以将最大游客流量按阶以20为一个单位进展计算分别得到245，(220,),(200,)，

7、四点，然后利用插值与拟合的法得到，以规模人数，总费用的相关关系图像，取斜率最小图像最平缓的人数规模阶段近似取整，确定建旅馆的规模大小。由于在考虑一日游问题上，没有考虑住宿问题，所以一日游套餐不需要要改动。但是二日游问题上有一条最短路径因为B不能入住而舍去，需要改动。重新考虑最短路线，最优游客人数，最优购船方案，游览费用。同时在于其它四条路线进展比较，利用原先一样的法，制定二日游套餐。模型建立与求解问题一由表1岛屿及港口之间的距离，利用软件，画出海岛与港口的平面分布图图1：1 一日游问题：假设该旅游区每天都有大量的游客来旅游，超过了各个景点的接待游客的能力。由于每个景点游半天，因此一日游涉及到2

8、个景点的选取。因此有种情形，首先利用matlab floyd算法求出任意两点海岛与港口间的最短距离得到如下表格表格1： 加权图的任意两个岛屿之间的距离和路径距离矩阵路径矩阵=由此，得到相应的10条游览路线的最短路程。 根据路程费用的公式： 结合已经求出的最短路程，得到每条路线的路程费用。 因为每个景点的最大承载能力有限制，所以选取每条路线中两个景点的最大承载能力的最小值，作为该条游览路线的最大游览人数。根据大船、小船的容纳人数，依此确定每条路线相应的、。然后根据公式：，计算出每条路线的损失费用。由于费用包括客均费用与损失费用，即通过普通算法2路程费用，损失费用得到每种路线的总游览费用。 对于多

9、种购船案如下处理。其中：由于V确定相应的、会得到相对应的分配，可能会得到两种分配，、例如：游船少载50人 (游船少载30人) 针对： 针对： 选取乘船案将这10种案依次算出游览费用。并且按照路线、最短路程、大船数量、小船数量、游览总费用，并按从小到大的顺序排列绘制成表格。表格2：路线最短路程 总费用 2 1 488.7215 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考虑到每

10、天景点的游客量的不确定性，依据每天景点的游览路线的总条数进展分类。大致分成5类，1、2、3、4、51：只有一个景点到达最大承载能力。5所有景点，在同一时刻都到达最大承载能力按照景点分散度，旅客人数及总费用，利用函数衡量，得到最优匹配，选取合理的5种匹配绘制成表格如下。表格3：线条数 最正确人数 最正确路线最正确分配人数与路线相对应 1 经E210210 1不经E240240 2 全经E420210210 2 无要求520240280 3 无要求730240280二日游：由于每日只能游2个景点，因此2日游需对4个景点进展旅游，在5个景点中，所以有5种景点旅游选择，分别是：将5种情形分别进展讨论：

11、1、 首先利用matlab行遍性问题中的TSP算法程序见附录求最短路可以得到由P点出发经过全部A、B、C、D回到P的最短路径图线。但由于，仅有C、D两个岛屿有游客可供住宿，所以在最短路线中，要求第2个位置游客可以在旅游景点入住或第3个位置游客可以在旅游景点入住然后参观必须是C、D中的至少得任意一个。假设所得路线满足条件，则是所求路线。否则需进展下步计算。将ABCD进展满足条件的全排列，分别利用算法计算每个排列的人均费用，取人均费用最小的排列为该四个景点的最优游览路线，并且得到相应的路程费用。取每条路线中四个景点的最大承载能力的、旅馆最大容纳能力的最小值，最为该条路线的最优游览人数。根据一日游求

12、解损失费用的法，得到每条路线在最优人数下的损失费用。然后把得到的数据按照路线、最短路程、大船数量、小船数量、人均费用回执成表格。得到如下表格。表格4景点路线 最短距离人均总费用 248 2 1 669.6259 2 1 590.15245 2 1803.25295 2 1 940.21254 2 1 840.12考虑到实际问题，考虑到每个套餐中景点分散度，最短距离与总费用三者之间所占的权重，根据一日游套餐制定的与原则吗，得到如下二日游旅游套餐。将所到的数据按照最优路线条数，最优路线、最短路程、最优大船数量、最优小船数量、人均费用挥之表格，如下。表格5：路线条数最正确路线最正确人数人均费用 1

13、2402 1669.6 1 2102 1590.15 2 4504 21609.81注：由于D的住宿承受力是200，因此当到达景点容纳能力后，假设在D入住会大于住宿的承载力，因此在考虑及路线时，此时客人数量只能取两者最小的一个，因此双考虑后的到如上表格问题二此问题要求确定新建旅馆的地点与规模人数，所以分两局部进展1.地点首先，假设在同一时刻所有景点都满员，则得到=1450 50%=725 同时假设C、D旅馆都到达最大承受能力，所以所建旅馆的最大规模为 725-200-280=245人其次分别利用算法计算出、因此可得 选取B点为所建旅馆的地点。2.规模每天游览景点的人数不同，因此以新建旅馆的最大

14、承受能力依次递减20人，分析对应的的变化情况。由算法5可得如下4组数据245，33125 220,44445 200,27370 ,30311。其次，分别将这4组数据，利用matlab插值与拟合的法，得到关于以规模人数为轴，以总费用为轴的相应关系如图用matlab中的figure工具找到最平缓位置斜率变化不明显。因此得到此时在180205。然后，进展精细分析。用matlab中坐标工具，可以得到该曲线中的最低点,27365如图因此，取=200即为该新旅馆的规模人数。由于一日游问题不考虑住宿问题，因此在游览套餐中一日游的不需要改动。由于二日游问题在考虑住宿条件。在增加新的旅馆后，缩小了条件限制，扩

15、大了可选择点。现在二日游问题上，游览路线的第二个位置或第三个位置可以是B、C、D、三点重的任意一个。因此在所求的最短路径中因B不能住宿而舍去的路线，现在需要重新进展考虑。因为是如上所说的问题，所以经过重新计算后年得到相应的最短距离：258，大船数量：2，小船数量：0，最优人数：200，总费用：578.025，将新的路线进展重新考虑，因此二日游套餐需要改动，改动结果如下。表格6：路线条数最正确路线最正确人数人均费用 1 2002 0578.02 1 2102 1590.15 2 4504 21609.81程序求最短路matlab程序a=0 46 21 50 60 70;46 0 30 32 55

16、 115;21 30 0 48 53 90;50 32 48 0 21 95;60 55 53 21 0 85;70 115 90 95 85 0D,R=floyd(a)%functionD,R=floyd(a);n=size(a,1);D=afor i=1:n for j=1:n R(i,j)=j; endendRfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)= U( K) + * ( K, J) - ( N - 2) * ( 1 - *( K, J) + ( N - 3) * *( J, K); ! Make the *s 0/1; FOR( LINK: BIN( *); ! For the first and last stop we know.; FOR( CITY( K)| K *GT* 1: U( K) = 1 + ( N - 2) * *( K, 1); END选择案matlab程序*= 240 240 240 210 250 280 210 250 210 210;y=231 215 215 235 242 253 233 228 201;a=*-ya = 9 59 25 -5 15 38 -43 17 -18 9. z.