海岛优化方案答案.doc

数学建模.doc123 海岛优化方案分析 摘要 经济水平的增加，带动了旅游业的发展。本文研究了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.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考虑到每天景点的游客量的不确定性，依据每天景点的游览路线的总条数进行分类。大致分成5类，1、2、3、4、5（1：只有一个景点达到最大承载能力。5所有景点，在同一时刻都达到最大承载能力）按照景点分散度，旅客人数及总费用，利用函数衡量，得到最优匹配，选取合理的5种匹配绘制成表格如下。表格3：线条数 最佳人数 最佳路线最佳分配（人数与路线相对应） 1 经E210210 1不经E240240 2 全经E420210210 2 无要求520240280 3 无要求730240280 二日游：由于每日只能游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.6259 2 1 590.15 245 2 1803.25 295 2 1 940.21 254 2 1 840.12考虑到实际问题，考虑到每个套餐中景点分散度，最短距离与总费用三者之间所占的权重，根据一日游套餐制定的与原则吗，得到如下二日游旅游套餐。将所到的数据按照最优路线条数，最优路线、最短路程、最优大船数量、最优小船数量、人均费用挥之表格，如下。表格5：路线条数最佳路线最佳人数 人均费用 1 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.规模每天游览景点的人数不同，因此以新建旅馆的最大承受能力依次递减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 2002 0578.02 1 2102 1590.15 2 4504 21609.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 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; endendR for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)= U( K) + X ( K, J) - ( N - 2) * ( 1 - X( K, J) + ( N - 3) * X( J, K); ! Make the Xs 0/1; FOR( LINK: BIN( X); ! For the first and last stop we know.; FOR( CITY( K)| K #GT# 1: 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-ya = 9 59 25 -5 15 38 -43 17 -18 912