海岛优化方案答案

数学建模.doc123海岛优化方案分析摘要经济水平的增加，带动了旅游业的发展。本文研究了5个岛屿与港口之间最短距离及乘船计划。以最小费用为准则，制定了最优化一日游、二日游套餐。以及为满足游客的需要，通过考虑游客量及费用两大方面，找到建设旅馆的最优地方，与最优规模。问题一：对于一日游问题，首先考虑单线整体旅游，以所游两地的最大承受能力的最小值为游客量对 C52=10种路线分别计算，得到每条路线的费用。考虑到游客人数不定，所以以旅游线进行分类分为6种，1、2、3、4、5。分别对这5种线，从10种路线中进行最优匹配。根据所旅游景点尽可能分散，旅客尽可能多，总费用尽可能少的原则进行匹配。根据1mRu3衡量得到最优的五种一日游套餐对两日游，按C54 5种考虑，利用Dijkstra算法，得到每种路线的最优走法。同时仅有C、D两地可以入住，所以在参观景点次序排列时第二个位置（游客在旅游地直接入住）或第三个位置（游客不在旅游地入住，在第二天旅游地旅游之前先入住）必须是 C、D两景点中至少一个。并且在游客规模取景点承受能力的人数与旅馆容纳能力的最小值作为该次旅游的人数规模。 结合最有走法，与条件限制。其次，根据一日游的原则以相同的方法可以得到最优的两种套餐， 见表格5问题二：在假设所有景点都达到接待游客的能力后，得到所建旅店的最大规模，分别计算各点到B、C、D点在最大规模的情形下，根据算法3，利用公式u210sxk(8.5t14t1)1.5(100t140t2min(245,Ri))2)(1min(245,Ri)得到U2b33125kU2c44445kU2d51215k找到最低费用的位置，因此选取 B岛为新建旅馆地点。同时将规模按阶降低，利用相同的算法得到关于U2b的四组数据：245,33125k），(220，39288k)，（200,27370k），（180,30311k）将这四组数据以规模人数为x轴，以总费用为y轴。用插值与拟合的方法得到x、y之间的精品文档交流相应关系，取变化率最小，即图线最平缓的点的x值进行取整，作为新建旅馆的规模人数。即在B点建立旅馆且最大承受能力为200人。由于在考虑一日游问题上， 没有考虑住宿问题， 所以一日游套餐不需要要改动。 但是二日游问题上有一条最短路径因为B不能入住而舍去，需要改动。然后以相同的方法制定相应的套餐。符号说明:因租船所产生的费用u1:路程费u2：损失费t1:租大船的条数t2:租小船的条数：游客人数每条路线的最短路程:船只每公里费用系数Ri:第i个景点的游客承受力U2i:第i个景点到B点的费用V：表示所选两景点中，接受游客的能力中的最小值。：景点个数。问题分析问题一分析：一日游：由表1岛屿与港口之间距离，先绘制出海岛与港口粗略的平面分布图。再利用matlabfloyd算法，求在两点间的最短路。首先考虑旅行费问题，由已求出的五个海岛与港口六个点的任意两点的最短距离， 计算出（C52种）每种路线的最短路程，然后依次得到相应的每条路线的路程费用 u1:。其次考虑游船损失问题。根据 A、B、C、D、E各景点的承载游客的能力，所以，每条路线一般有：大船t1 0:3，小船t2 0:7之内进行合理匹配。根据已求的路线，求每条路线两个景点中最大承载能力的最小值为该条路线的规模人数， 计算出相应精品文档交流的u2。最后利用公式u1u2将C52结果按从小到大进行排列，根据游客的人数不同，考虑到实际问题，根据旅游线条数进行分类，得到5种分类。考虑到每个套餐中景点分散度，最短距离与总费用三者之间所占的权重按从小到大排列得到最优旅游套餐，取前六种路线即为旅游套餐。两日游：按C54 5种考虑，利用Dijkstra算法，得到每种路线的最优走法。同时仅有C、D两地可以入住，所以在参观景点次序排列时第二个位置（游客在旅游地直接入住）或第三个位置（游客不在旅游地入住，在第二天旅游地旅游之前先入住）必须是C、D两景点中至少一个。考虑到旅店的容纳人数。游客规模取景点承受能力的人数与旅馆容纳能力的最小值作为该次旅游线的人数规模。 结合最有走法、条件限制，根据一日游的算法，得到相应的 u1:、u2。其次，根据制定一日游套餐的原则，以相同的方法可以得到最优二日游套餐。问题二分析：建设新旅店问题，只需考虑两大准则，建设地点、建设规模。建设地点：首先以衡量标准 u u1 u2最小来标量。其中 u1：各个景点分别到 BgCgD的最短距离总和，u2：假设在同一时刻，各个景点都达到最大承载能力。选取各个景点的最大承载能力的总人数的和（景点最大游客量）的50%减去C、D景点所承受能力的总人数。得到建立旅馆的最大容纳规模。根据损失费用标量得到u2。利用uu11u2将B、C、D各点的情况依次算出，进行比较得到结果。（其中u1100t1sx0.85k40t2sxk，u12umin(245,Ri))1.5(100t140t2min(245,Ri)由u2u1u12将U2b、U2c、U2d依次算出，取min(U2b,U2c,U2d)的位置，即为新建旅馆的建设地点。建设国模：考虑到景点每天的游客流量不同，所以将最大游客流量按阶（以 20为一个单位）进行计算分别得到（ 245，U2i），(220,U2i),(200, U2i)，（180，U2i）四点，然后利用插值与拟合的方法得到，以 x:规精品文档交流模人数，y:总费用的相关关系图像，取斜率最小（图像最平缓）的人数规模阶段（近似取整），确定建旅馆的规模大小。由于在考虑一日游问题上，没有考虑住宿问题，所以一日游套餐不需要要改动。但是二日游问题上有一条最短路径因为B不能入住而舍去，需要改动。重新考虑最短路线，最优游客人数，最优购船计划，游览费用。同时在于其它四条路线进行比较，利用原先相同的方法，制定二日游套餐。模型建立与求解问题一由表1岛屿及港口之间的距离，利用 ps软件，画出海岛与港口的平面分布图图1：1＞一日游问题：假设该旅游区每天都有大量的游客来旅游，超过了各个景点的接待游客的能力。由于每个景点游半天，因此一日游涉及到2个景点的选取。因此有C52 10种情形，首先利用 matlabfloyd 算法求出任意两点（海岛与港口）间的最短距离得到如下表格表格1：加权图的任意两个岛屿之间的距离和路径距离矩阵M 路径矩阵N精品文档交流0462150607012345646030325311512344621300485390123456M=324802195N=2345650160535321085143456701159095850123456由此，得到相应的 10条游览路线的最短路程。根据路程费用的公式： u1 ks0.85t1 t2 结合已经求出的最短路程，得到每条路线的路程费用。因为每个景点的最大承载能力有限制，所以选取每条路线中两个景点的最大承载能力的最小值，作为该条游览路线的最大游览人数。 根据大船、小船的容纳人数，依此确定每条路线相应的t1:、t2:。然后根据公式：u2 u11.5100t140t2V，计算出每条路线的损失费用。V由于费用包括客均费用与损失费用，即u u1 u2通过普通算法2（路程费用，损失费用）得到每种路线的总游览费用。对于多种购船方案如下处理。其中：由于 V确定相应的t1、t2会得到相对应的分配，可能会得到两种分配， a1、a2例如：PBCP:S235km其中：V250人得到a1t13（游船少载50人）a2t12(游船少载30人)t20t22针对a1：u123530.85k599.25ku2u12501.550179.775uu1u2799.025k针对a2：u123520.85k869.5ku2u12501.550260.85uu1u21130.35k精品文档交流Q ua1ua2选取a1乘船方案将这10种方案依次算出游览费用。并且按照路线、最短路程、大船数量、小船数量、游览总费用，并按从小到大的顺序排列绘制成表格。表格2：路线最短路程t1总费用t2PACP181km21488.7kPADP215km21580.5kPABP231km21623.7kPBDP242km30628.22PCDP233km30727.40PBCP235km30779.03PDEP201km061518.43PAEP215km061566.44PCEP228km061661.14PBEP253km061843.28考虑到每天景点的游客量的不确定性，依据每天景点的游览路线的总条数进行分类。大致分成5类，1、2、3、4、5（1：只有一个景点达到最大承载能力。5所有景点，在同一时刻都达到最大承载能力）按照景点分散度，旅客人数及总费用，利用函数W 1(mRu)衡量，得到最优匹配，选取合理的 5种匹配绘制成表3格如下。表格3：线条数最佳人数最佳路线1经E210PDEP1不经E240PACP2全经E420PAEPPDEP2无要求520PACPPBDP3无要求730PACPPBDPPCEP

最佳分配（人数与路线相对应）PDEP210PACP240PAEP210PDEP210PACP240PBDP280PBDP240PACP280PCEP精品文档交流二日游：由于每日只能游2个景点，因此2日游需对4个景点进行旅游，在5个景点中C54 5，所以有5种景点旅游选择，分别是：ABCD ABCE ACDE BCDE ABDE将5种情形分别进行讨论：1、ABCE首先利用matlab行遍性问题中的TSP算法（程序见附录求最短路）可以得到由P点出发经过全部A、B、C、D回到P的最短路径图线。但由于，仅有C、D两个岛屿有游客可供住宿，所以在最短路线中，要求第2个位置（游客可以在旅游景点入住）或第3个位置（游客可以在旅游景点入住然后参观）必须是C、D中的至少得任意一个。若所得路线满足条件，则是所求路线。否则需进行下步计算。将ABCD进行满足条件的全排列，分别利用算法计算每个排列的人均费用，取人均费用最小的排列为该四个景点的最优游览路线，并且得到相应的路程费用。。取每条路线中四个景点的最大承载能力的、旅馆最大容纳能力的最小值，最为该条路线的最优游览人数。根据一日游求解损失费用的方法，得到每条路线在最优人数下的损失费用。然后把得到的数据按照路线、最短路程、大船数量、小船数量、人均费用回执成表格。得到如下表格。表格4最t1t2人均总费景点路线短距离用ABCDPACBDP248km21669.6kABCEPACBEP259km21590.15kACDEPEDCAP245km21803.25kBCDEPECBDP295km21940.21kABDEPEDBAP254km21840.12k考虑到实际问题，考虑到每个套餐中景点分散度，最短距离与总费用三者之间所占的权重，根据一日游套餐制定的与原则吗，得到如下二日游旅游套餐。将所到的数据按照最优路线条数，最优路线、最短路程、最优大船数量、最优小船数量、人均费用挥之表格，如下。表格5：路线条数最佳路线最佳人t1人均费用数t21PACBDP24021669.6k1PACBEP21021590.15k2PACBDP450421609.81PEDCAPk注：由于D的住宿承受力是200，因此当达到景点容纳能力后，若在D入住会大于住宿的承载力，因此在考虑BCDE及ABDE路线时，此时客人数量只能取两者最小的一个，因此双方考虑后的到如上表格精品文档交流问题二此问题要求确定新建旅馆的地点与规模人数，所以分两部分进行1.地点首先，假设在同一时刻所有景点都满员，则得到x=145050%x=725同时假设C、D旅馆都达到最大承受能力，所以所建旅馆的最大规模为725-200-280=245（人）其次分别利用算法计算出U2b、U2c、U2du2u1u12u1100t1sx0.85k40t2Sxu12u11.5(100t140t2min(245,Ri)min(245,Ri)因此可得U2b33125kU2c44445kU2d51215k选取B点为所建旅馆的地点。2.规模每天游览景点的人数不同，因此以新建旅馆的最大承受能力依次递减20人，分析对应的U2b的变化情况。由算法 5可得如下4组数据（245，33125） （220,44445）（200,27370） （180,30311）。其次，分别将这4组数据，利用matlab插值与拟合的方法，得到关于以规模人数为x轴，以总费用为y轴的相应关系如图精品文档交流用matlab中的figure工具找到最平缓位置（斜率变化不明显）。因此得到此时x在180:205。然后，进行精细分析。用matlab中坐标工具，可以得到该曲线中的最低点（199,27365）如图因此，取x=200即为该新旅馆的规模人数。由于一日游问题不考虑住宿问题，因此在游览套餐中一日游的不需要改动。由于二日游问题在考虑住宿条件。 在增加新的旅馆后，缩小了条件限制，扩大了可选择点。现在二日游问题上，游览路线的第二个位置或第三个位置可以是B、C、D、三点重的任意一个。因此在所求的最短路径中因B不能住宿而舍去的路线，精品文档交流现在需要重新进行考虑。因为P E C B D P是如上所说的问题，所以经过重新计算后年得到P C B D E P相应的最短距离： 258km， 大船数量：2，小船数量：0，最优人数：200，总费用：578.025k，将新的路线进行重新考虑，因此二日游套餐需要改动，改动结果如下。表格6：路线条数最佳路线最佳人t1t人均费用数21PCBDEP20020578.02k1PACBEP21021590.15k2PACBDP450421609.81PEDCAPk程序附件求最短路matlab程序a=[04621506070;460303255115;21300485390;50324802195;60555321085;701159095850][D,R]=floyd(a)%function[D,R]=floyd(a);n=size(a,1);D=afori=1:nforj=1:nR(i,j)=j;endendRfork=1:n精品文档交流fori=1:nforj=1:nifD(i,k)+D(k,j)<D(i,j)D(i,j)=D(i,k)+D(k,j);R(i,j)=R(i,k);endendendkDRendD=04621506070460303253115213004853905032480219560535321085701159095850R=123456123446123456123456143456123456二日游最短路lingo 程序：MODEL:SETS:CITY/1..6/:U;!U(I)=sequenceno.ofcity;LINK(CITY,CITY):DIST,!Thedistancematrix;X;!X(I,J)=1ifweuselinkI,J;ENDSETS精品文档交流DATA:!Distancematrix,itneednotbesymmetric;DIST=07011590957004621501154603032902130048955032950;ENDDATA!Them