《试题二论文1.doc》由会员分享，可在线阅读，更多相关《试题二论文1.doc（18页珍藏版）》请在三一文库上搜索。
1、承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名
2、）：济宁学院 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 年 月 日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）： 海岛优化方案分析 摘要 经济水平的增加，带动了旅游业的发展。本文研究了5个岛屿与港口之间最短距离及乘船计划。以最小费用为准则，制定了最优化一日游、二日游套餐。以及为满足游客的需要，通过考虑游客
3、量及费用两大方面，找到建设旅馆的最优地方，与最优规模。问题一：对于一日游问题，首先考虑单线整体旅游，以所游两地的最大承受能力的最小值为游客量对=10种路线分别计算，得到每条路线的费用。考虑到游客人数不定，所以以旅游线进行分类分为6种，1、2、3、4、5。分别对这5种线，从10种路线中进行最优匹配。根据所旅游景点尽可能分散，旅客尽可能多，总费用尽可能少的原则进行匹配。根据衡量得到最优的五种一日游套餐，见表格4对两日游，按种考虑，利用算法，得到每种路线的最优走法。同时仅有C、D两地可以入住，所以在参观景点次序排列时第二个位置（游客在旅游地直接入住）或第三个位置（游客不在旅游地入住，在第二天旅游地旅
4、游之前先入住）必须是C、D两景点中至少一个。并且在游客规模取景点承受能力的人数与旅馆容纳能力的最小值作为该次旅游的人数规模。结合最有走法，与条件限制。其次，根据一日游的原则以相同的方法可以得到最优的两种套餐，见表格5问题二：在假设所有景点都达到接待游客的能力后，得到所建旅店的最大规模，分别计算各点到B、C、D点在最大规模的情形下，根据算法3，利用公式 得到 找到最低费用的位置，因此选取B岛为新建旅馆地点。同时将规模按阶降低，利用相同的算法得到关于的四组数据：（245,33125），(220，39288)，（200,27370），（180,30311）将这四组数据以规模人数为轴，以总费用为轴。用
5、插值与拟合的方法得到、之间的相应关系，取变化率最小，即图线最平缓的点的值进行取整，作为新建旅馆的规模人数。即在B点建立旅馆且最大承受能力为200人。由于在考虑一日游问题上，没有考虑住宿问题，所以一日游套餐不需要要改动。但是二日游问题上有一条最短路径因为B不能入住而舍去，需要改动。然后以相同的方法制定相应的套餐。 一、问题背景近年来，经济水平的快速提高，带动了旅游业飞速发展。旅游公司为了获取最大经济利益，满足游客的所有需求（游览景点个数尽可能多，游览时间尽可能少），希望制定最佳的游览路线。本文针对海岛问题，计算相关数据，根据游客的需要。制定了较为合理的一日游、二日游套餐。为了最完美的服务所有游客
6、，以及扩大该景点的吸引力，需要新旅馆。通过多方面考虑，确定新建位置与规模大小。2、 问题重述 某景区由5个海岛A,B,C,D,E组成。海岛之间及与大陆港口P的距离由表1给出每个海岛的游览时间为半天。C,D两个岛屿有旅馆可供住宿。游览的过程为：游船凌晨由港口P出发，每半天游览一个景点。如果行程超过一天，则晚上选择岛屿C或D住宿。游览结束后回到港口P。景点每次接待游客的能力由表2给出目前旅行社计划购买大、小两种游船用于旅游。大型可载乘客100人，小型40人。大型游船的每公里客均费用是小型游船的85%，但景点E景点E只能停泊小型游 客均旅行费用正比于船的行程。游船少载一个人的损失相当于客均旅行费用的
7、1.5倍。（1） 旅行社经理希望你综合考虑景点的接纳能力，设计出不超过六种一日游和2日游套餐以及与之相配套的购船计划。使得游览总费用尽可能低。（不考虑游船购置费用）（2） 据调查，有50%的游客希望在岛上过夜。但住宿容纳能力明显不足。因此，有人提议在B,C,D三个海岛之一兴建一个新的旅馆。试分析应该在哪一个海岛兴建，规模多大？旅游套餐是否应该作相应调整？ 三、 符号说明因租船所产生的费用路程费：损失费租大船的条数租小船的条数：游客人数 每条路线的最短路程船只每公里费用系数第个景点的游客承受力第个景点到B点的费用 表示所选两景点中，接受游客的能力中的最小值。 ：景点个数。 四、问题假设1.假设景
8、区旅游岛屿的最大接纳人数饱和。2.假设所有旅客都以团体的形式参加旅游。3.假设所有旅客从开始到结束旅游都采用一种方案，乘坐同一艘船。4.假设无论一日游还是二日游都忽略在行船过程中因其他因素导致旅游时间的损失，并且人均客费用不变5.假设在一日游多条游览路线同时进行时，不与景点的最大承受力相冲撞，各景点参观次序随机变动 五、问题分析问题一 分析：一日游：由表1岛屿与港口之间距离，先绘制出海岛与港口粗略的平面分布图。再利用matlab floyd算法，求在两点间的最短路。首先考虑旅行费问题，由已求出的五个海岛与港口六个点的任意两点的最短距离，计算出（种）每种路线的最短路程，然后依次得到相应的每条路线
9、的路程费用。其次考虑游船损失问题。根据A、B、C、D、E各景点的承载游客的能力，所以，每条路线一般有：大船，小船之内进行合理匹配。根据已求的路线，求每条路线两个景点中最大承载能力的最小值为该条路线的规模人数，计算出相应的。最后利用公式 将结果按从小到大进行排列，根据游客的人数不同，考虑到实际问题，根据旅游线条数进行分类，得到5种分类。考虑到每个套餐中景点分散度，最短距离与总费用三者之间所占的权重按从小到大排列得到最优旅游套餐，取前六种路线即为旅游套餐。两日游：按种考虑，利用算法，得到每种路线的最优走法。同时仅有C、D两地可以入住，所以在参观景点次序排列时第二个位置（游客在旅游地直接入住）或第三
10、个位置（游客不在旅游地入住，在第二天旅游地旅游之前先入住）必须是C、D两景点中至少一个。考虑到旅店的容纳人数。游客规模取景点承受能力的人数与旅馆容纳能力的最小值作为该次旅游线的人数规模。结合最有走法、条件限制，根据一日游的算法，得到相应的、。其次，根据制定一日游套餐的原则，以相同的方法可以得到最优二日游套餐。问题二分析：建设新旅店问题，只需考虑两大准则，建设地点、建设规模。建设地点：首先以衡量标准最小来标量。其中：各个景点分别到的最短距离总和，：假设在同一时刻，各个景点都达到最大承载能力。选取各个景点的最大承载能力的总人数的和（景点最大游客量）的50%减去C、D景点所承受能力的总人数。得到建立
11、旅馆的最大容纳规模。根据损失费用标量得到。利用 将B、C、D各点的情况依次算出，进行比较得到结果。（其中 ，) 由将、依次算出，取min(,)的位置，即为新建旅馆的建设地点。建设国模：考虑到景点每天的游客流量不同，所以将最大游客流量按阶（以20为一个单位）进行计算分别得到（245，），(220, ),(200, )，（180，）四点，然后利用插值与拟合的方法得到，以规模人数，总费用的相关关系图像，取斜率最小（图像最平缓）的人数规模阶段（近似取整），确定建旅馆的规模大小。 由于在考虑一日游问题上，没有考虑住宿问题，所以一日游套餐不需要要改动。但是二日游问题上有一条最短路径因为B不能入住而舍去，需
12、要改动。重新考虑最短路线，最优游客人数，最优购船计划，游览费用。同时在于其它四条路线进行比较，利用原先相同的方法，制定二日游套餐。 六、模型建立与求解问题一由表1岛屿及港口之间的距离，利用软件，画出海岛与港口的平面分布图图1：1 一日游问题：假设该旅游区每天都有大量的游客来旅游，超过了各个景点的接待游客的能力。由于每个景点游半天，因此一日游涉及到2个景点的选取。因此有种情形，首先利用matlab floyd算法求出任意两点（海岛与港口）间的最短距离得到如下表格表格1： 加权图的任意两个岛屿之间的距离和路径距离矩阵路径矩阵 =由此，得到相应的10条游览路线的最短路程。 根据路程费用的公式： 结合
13、已经求出的最短路程，得到每条路线的路程费用。 因为每个景点的最大承载能力有限制，所以选取每条路线中两个景点的最大承载能力的最小值，作为该条游览路线的最大游览人数。根据大船、小船的容纳人数，依此确定每条路线相应的、。然后根据公式：，计算出每条路线的损失费用。由于费用包括客均费用与损失费用，即 通过普通算法2（路程费用，损失费用）得到每种路线的总游览费用。 对于多种购船方案如下处理。其中：由于V确定相应的、会得到相对应的分配，可能会得到两种分配，、例如： （游船少载50人） (游船少载30人) 针对： 针对： 选取乘船方案将这10种方案依次算出游览费用。并且按照路线、最短路程、大船数量、小船数量、
14、游览总费用，并按从小到大的顺序排列绘制成表格。表格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所有景点，在同一时刻都达到最大承载能力）按照景点分散度，旅客人数及总费用，利用函数
15、衡量，得到最优匹配，选取合理的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个位置（游
16、客可以在旅游景点入住）或第3个位置（游客可以在旅游景点入住然后参观）必须是C、D中的至少得任意一个。若所得路线满足条件，则是所求路线。否则需进行下步计算。将ABCD进行满足条件的全排列，分别利用算法计算每个排列的人均费用，取人均费用最小的排列为该四个景点的最优游览路线，并且得到相应的路程费用。取每条路线中四个景点的最大承载能力的、旅馆最大容纳能力的最小值，最为该条路线的最优游览人数。根据一日游求解损失费用的方法，得到每条路线在最优人数下的损失费用。然后把得到的数据按照路线、最短路程、大船数量、小船数量、人均费用回执成表格。得到如下表格。表格4景点路线 最短距离 人均总费用 248 2 1 66
17、9.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入住会大于住宿的承载力，因此在考虑及路线时，此
18、时客人数量只能取两者最小的一个，因此双方考虑后的到如上表格问题二此问题要求确定新建旅馆的地点与规模人数，所以分两部分进行1.地点首先，假设在同一时刻所有景点都满员，则得到=1450 50%=725 同时假设C、D旅馆都达到最大承受能力，所以所建旅馆的最大规模为 725-200-280=245（人）其次分别利用算法计算出、 因此可得 选取B点为所建旅馆的地点。2.规模每天游览景点的人数不同，因此以新建旅馆的最大承受能力依次递减20人，分析对应的的变化情况。由算法5可得如下4组数据（245，33125） （220,44445） （200,27370） （180,30311）。其次，分别将这4组数据
19、，利用matlab插值与拟合的方法，得到关于以规模人数为轴，以总费用为轴的相应关系如图用matlab中的figure工具找到最平缓位置（斜率变化不明显）。因此得到此时在180205。然后，进行精细分析。用matlab中坐标工具，可以得到该曲线中的最低点（199,27365）如图因此，取=200即为该新旅馆的规模人数。由于一日游问题不考虑住宿问题，因此在游览套餐中一日游的不需要改动。由于二日游问题在考虑住宿条件。在增加新的旅馆后，缩小了条件限制，扩大了可选择点。现在二日游问题上，游览路线的第二个位置或第三个位置可以是B、C、D、三点重的任意一个。因此在所求的最短路径中因B不能住宿而舍去的路线，现
20、在需要重新进行考虑。因为 是如上所说的问题，所以经过重新计算后年得到 相应的最短距离：258，大船数量：2，小船数量：0，最优人数：200，总费用：578.025，将新的路线进行重新考虑，因此二日游套餐需要改动，改动结果如下。表格6：路线条数最佳路线最佳人数 人均费用 1 2002 0578.02 1 2102 1590.15 2 4504 21609.81七、模型的优缺点分析 本文对岛屿旅游旅行社套餐安排做了模型研究优点：1.我们假设了所有游客都是以参团的形式选择旅行社，简化了模型，便于分析和计算。2.对旅游路径的选择，利用 算法科学的得到最短路径，方便于后边的方案确定，达到花更少的钱，游览
21、更多的景点3.在问题二确定旅馆修建点时，采用选择问题的模型，利用matlab floyd算法得到B、C、D到其它岛屿的最短距离和提高了模型的准确性缺点： 1.在二日游套餐的选择上，选出的四个点，忽略了全排列的不同，假设了只需选择四个点，就取四个点的最短回路。排出了含四个点的其它旅行路线。2.在问题规模大小的确定上，采取逐渐逼近试探的方法，由于计算需要逼近，将步长选择20，这是比较模糊的，步长越小则结果越精确，所以对此还可以继续优化，以得到更准确的结果。八、参考文献1、赵静 但琦 数学建模与数学实验第三版 高等教育出版社 2010.122、姜启源，谢金星 叶俊，数学模型（第三版），北京：高等教育
22、出版社，2003年。3、张志涌 精通Matlab 北京航空航天大学出版社 2011.11九、程序附件求最短路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
23、)= 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 23
24、3 228 201;a=x-ya = 9 59 25 -5 15 38 -43 17 -18 9 算法5： %以最大景点承受能力计算损失费用（c+程序）Sx=bri=a;if a245 ri=a else ri=245t1=ri mod 100 t2=(ri-100t1) mod 40 u2=(10Sxk(8.5t1+4t2)*1.5*(100t1+40t2-ri) /ri插值做图matlab程序：x=180 200 220 245;y=30311 27370 39288 33125;cx=150:2:280;cy=interp1(x,y,cx,cubic);plot(x,y,+,cx,cy,x,y,r);xlabel(renshu),ylabel(feiyong)表1岛屿及港口之间距离（km）ABCDE大陆港口PA46AB21 AC50 AD60 AE70 AB30 BC32 BD53 BE115 BC48 CD53 CE90 CD21 DE95 DE85 E 表2景点旅游（半天）住宿（每晚）A240B470C250280D280200E210