1、 1 数学建模 .doc 123 海岛优化方案分析 摘要 经济水平的增加，带动了旅游业的发展。本文研究了 5个岛屿与港口之间最短距离及乘船计划。以最小费用为准则，制定了最优化一日游、二日游套餐。以及为满足游客的需要，通过考虑游客量及 费用两大方面，找到建设旅馆的最优地方，与最优规模。 问题一： 对于一日游问题，首先考虑单线整体旅游，以所游两地的最大承受能力的最小值为游客量对 25C =10 种路线分别计算，得到每条路线的费用。考虑到游客人数不定，所以以旅游线进行分类分为 6 种， 1、 2、 3、 4、 5。分别对这5 种线，从 10 种路线中进行最优匹配。根据所旅游景点尽可能分散，旅客尽可能
2、多，总费用尽可能少的原则进行匹配。根据 13w m R u 衡量得到最优的五种一日游套餐 对两日游，按 45 5C 种考虑，利用 Dijkstra 算法，得到每种路线的最优走法。同时仅有 C、 D 两地可以入住，所以在参观景点次序排列时第二个位置（游客在旅游地直接入住）或第三个位置（游客不在旅游地入住，在第二天旅游地旅游之前先入住）必须是 C、 D 两景点中至少一个。并且在游客规模取景点承受能力的人数与旅馆容纳能力的最小值作为该次旅游的人数规模。结合最有走法，与条件限制。其次，根据一日游的原则以相同的方法可以得到最优的两种套餐，见表格5 问题二： 在假设所有景点都达到接待游客的能力后，得到所建
3、旅店的最大规模，分别计算各点到 B、 C、 D 点在最大规模的情形下，根据算法 3，利用公式 2 1 2 1 211 0 ( 8 . 5 4 ) ( 1 ) 1 . 5 ( 1 0 0 4 0 m in ( 2 4 5 , ) )m in ( 2 4 5 , )xi iu s k t t t t RR 得到 2 33125bUk 2 44445cUk 2 51215dUk 找到最低费用的位置，因此选取 B 岛为新建旅馆地点。 同时将规模按阶降低，利用相同的算法得到关于 2bU 的四组数据：（ 245,33125k ）， (220， 39288k )，（ 200,27370k ），（ 180,3
4、0311k ）将这四组数据以规模人数为 x 轴，以总费用为 y 轴 。用插值与拟合的方法得到 x 、 y 之间的2 相应关系，取变化率最小，即图线最平缓的点的 x 值进行取整，作为新建旅馆的规模人数。即在 B 点建立旅馆且最大承受能力为 200 人。 由于在考虑一日游问题上，没有考虑住宿问题，所以一日游套餐不需要要改动。但是二日游问题上有一条最短路径因为 B 不能入住而舍去，需要改动。然后以相同的方法制定相应的套餐。 符号说明 :u 因租船所产生的费用 1:u 路程费 2u ：损失费 1:t 租大船的条数 2:t 租小船的条数 x ：游客人数 :s 每条路线的最短路程 :k 船只每公里费用系数
5、 :iR 第 i 个景点的游客承受力 2:iU 第 i 个景点到 B 点的费用 ：V 表示所选两景点中，接受游客的能力中的最小值。 m ：景点个数。 问题分析 问题一 分析：一日游：由表 1 岛屿与港口之间距离，先绘制出海岛与港口粗略的平面分布图。再利用 matlab floyd 算法，求在两点间的最短路。首先考虑旅行费问题，由已求出的五个海岛与港口六个点的任意两点的最短距离，计算出（ 25C 种）每种路线的最短路程，然后依次得到相应的每条路线的路程费用 1:u 。其次考虑游船损失问题。根据 A、 B、 C、 D、 E各景点的承载游客的能力，所以，每条路线一般有： 大船 1 03t ，小船 2
6、 07t 之内进行合理匹配。根据已求的路线，求每条路线两个景点中最大承载能力的最小值为该条路线的规模人数，计算出相应3 的 2u 。最后利用公式 12u u u 将 25C 结果按从小到大进行排列，根据游客的人数不同，考虑到实际问题，根据旅游线条数进行分类 ，得到 5 种分类。考虑到每个套餐中景点分散度，最短距离与总费用三者之间所占的权重按从小到大排列得到最优旅游套餐，取前六种路线即为旅游套餐。 两日游：按 45 5C 种考虑，利用 Dijkstra 算法，得到每种路线的最优走法。同时仅有 C、 D 两地可以入住，所以在参观景点次序排列时第二个位置（游客在旅游地直接入住）或第三个位置（游客不在
7、旅游地入住，在第二天旅游地旅游之前先入住）必须是 C、 D 两景点中至少一个。考虑到旅店的容纳人数。游客规模取景 点承受能力的人数与旅馆容纳能力的最小值作为该次旅游线的人数规模。结合最有走法、条件限制，根据一日游的算法，得到相应的 1:u 、 2u 。其次，根据制定一日游套餐的原则，以相同的方法可以得到最优二日游套餐。 问题二 分析：建设新旅店问题，只需考虑两大准则，建设地点、建设规模。建设地点：首先以衡量标准 12u u u最小来标量。其中 1u ：各个景点分别到 BCD 的最短距离总和， 2u ：假设在同一时刻，各个景点都达到最大承载能力。选取各个景点的最大承载能力的总人数的和（景点最大游
8、客量）的 50%减去 C、 D 景点所承受能力的总人数。得到建立旅馆的最大容纳规模。根据损失费用标量得到 2u 。利用 121u u u 将 B 、 C 、 D 各 点 的 情 况 依 次 算 出 ， 进 行 比 较 得 到 结 果 。（ 其 中 1 1 21 0 0 0 . 8 5 4 0xxu t s k t s k ，1 2 1 21 . 5 ( 1 0 0 4 0 m in ( 2 4 5 , )m in ( 2 4 5 , ) iiuu t t RR ) 由 2 1 12u u u 将 2bU 、 2cU 、 2dU 依次算出，取 min( 2bU , 2cU , 2dU )的位置，
9、即为新建旅馆的建设地点。建设国模：考虑到景点每天的游客流量不同，所以将最大游客流量按阶（以 20 为一个单位）进行计算分别得到（ 245， 2iU ）， (220, 2iU ),(200, 2iU )，（ 180， 2iU ）四点 ，然后利用插值与拟合的方法得到，以 :x 规4 模人数， :y 总费用的相关关系图像，取斜率最小（图像最平缓）的人数规模阶段（近似取整），确定建旅馆的规模大小。 由于在考虑一日游问题上，没有考虑住宿问题，所以一日游套餐不需要要改动。但是二日游问题上有一条最短路径因为 B 不能入住而舍去，需要改动。重新考虑最短路线，最优游客人数，最优购船计划，游览费用。同时在于其它四
10、条路线进行比较，利用原先相同的方法，制定二日游套餐。 模型建立与求解 问题一 由表 1岛屿及港口之间的距离，利用 ps 软件，画出海岛与港口的平面分布图 图 1： 1 一日游问题：假设该旅游区每天都有大量的游客来旅游，超过了各个景点的接待游客的能力。由于每个景点游半天，因此一日游涉及到 2 个景点的选取。因此有 25 10C 种情形，首先利用 matlab floyd 算法求出任意两点（海岛与港口）间的最短距离得到如下表格 表格 1： 加权图的任意两个岛屿之间的距离和路径 距离矩阵 M 路径矩阵 N 5 M =0 4 6 2 1 5 0 6 0 7 04 6 0 3 0 3 2 5 3 1 1
11、 52 1 3 0 0 4 8 5 3 9 05 0 3 2 4 8 0 2 1 9 56 0 5 3 5 3 2 1 0 8 57 0 1 1 5 9 0 9 5 8 5 0N =1 2 3 4 5 61 2 3 4 4 61 2 3 4 5 62 3 4 5 61 4 3 4 5 61 2 3 4 5 6由此，得到相应的 10条游览路线的最短路程。 根据路程费用的公式： 1 1 20.85u ks t t 结合已经求出的最短路程，得到每条路线的路程费用。 因为每个景点的最大承载能力有限制，所以选取每条路线中两个景点的最大承载能力的最小值，作为该条游览路线的最大游览人数。根据大船、小船的容纳
12、人数，依此确定每条路线相应的 1:t 、 2:t 。然后根据公式： 12 1 21 . 5 1 0 0 4 0uu t t VV ，计算出每条路线的损失费用。 由于费用包括客均费用与损失费用，即 12u u u 通过普通算法 2（路程费用，损失费用）得到每种路线的总游览费用。 对于多种购船方案如下处理。其中：由于 V 确定相应的 1t 、 2t 会得到相对应的分配，可能会得到两种分配， 1a 、 2a 例如： : 2 3 5 2 5 0P B C P S k m V 其 中 ： 人 得 到 12 310tta （游船少载 50 人） 12 222tta (游船少载 30 人 ) 针对 1a ：
13、 112122 3 5 3 0 .8 5 5 9 9 .2 51 .5 5 0 1 7 9 .7 7 52507 9 9 .0 2 5u k kuuu u u k 针对 2a ： 112122 3 5 2 0 .8 5 8 6 9 .51 .5 5 0 2 6 0 .8 52501 1 3 0 .3 5u k kuuu u u k 6 12aauu 选取 1a 乘船方案 将这 10 种方案依次算出游览费用。并且按照路线、最短路程、大船数量、小船数量、游览总费用，并按从小到大的顺序排列绘制成表格。 表格 2： 路线 最短路程 1t 2t 总费用 P A C P 181km 2 1 488.7k
14、P A D P 215km 2 1 580.5k P A B P 231km 2 1 623.7k P B D P 242km 3 0 628.22 P C D P 233km 3 0 727.40 P B C P 235km 3 0 779.03 P D E P 201km 0 6 1518.43 P A E P 215km 0 6 1566.44 P C E P 228km 0 6 1661.14 P B E P 253km 0 6 1843.28 考虑到每天景点的游客量的不确定性，依据每天景点的游览路线的总条数进行分类。 大致分成 5 类， 1、 2、 3、 4、 5（ 1：只有一个景点
15、达到最大承载能力。 5所有景点，在同一时刻都达到最大承载能力）按照景点分散度，旅客人数及总费用，利用函数 1 ()3W m R u 衡量，得到最优匹配，选取合理的 5 种匹配绘制成表格如下。 表格 3： 线条数 最佳人数 最佳路线 最佳分配（人数与路线相对应） 1 经 E210 P D E P P D E P 210 1 不经 E240 P A C P P A C P 240 2 全经 E420 P A E P P D E P P A E P 210 P D E P 210 2 无要求 520 P A C P P B D P P A C P 240 P B D P 280 3 无要求 730
16、P A C P P B D P P C E P P B D P 240 P A C P 280 P C E P 7 2 二日游：由于每日只能游 2个景点，因此 2日游需对 4个景点进行旅游，在 5 个景点中 45 5C ，所以有 5种景点旅游选择，分别是： ABCD ABCE ACDE BCDE ABDE 将 5 种情形分别进行讨论： 1、 ABCE 首先利用 matlab行遍性问题中的 TSP算法（程序见附录求最短路）可以得到由 P点出发经过全部 A、 B、 C、 D 回到 P 的最短路径图线。但由于，仅有 C、 D 两个岛屿有游客可供住宿，所以在最短路线中，要求第 2个位置（游客可以在旅游
17、景点入住）或第 3个位置（游客可以在旅游景点入住然后参观 ） 必须是 C、 D 中的至少得任意一个。若所得路线满足条件，则是所求路线。否则需进行下步计算。将 ABCD 进行满足条件的全排列，分别利用算法计算每个排列的人均费用，取人均费用最小的排列为该四个景点的最优游览路线，并且得到相应的路程费用。取每条路线中四个景点的最大承载能力的、旅馆最大容纳能力的最小值，最为该条路线的最优游览人数。根据一日游求解损失费用的方法，得到每条路线在最优人数下的损失费用。然后把得到的数据按照路线、最短路程、大船数量、小船数量、人均费用回执成表格。得到如下表格。 表格 4 景点 路线 最 短距离 1t 2t 人均总
18、费用 ABCD P A C B D P 248km 2 1 669.6k ABCE P A C B E P 259km 2 1 590.15k ACDE P E D C A P 245km 2 1 803.25k BCDE P E C B D P 295km 2 1 940.21k ABDE P E D B A P 254km 2 1 840.12k 考虑到实际问题，考虑到每个套餐中景点分散度，最短距离与总费用三者之间所占的权重，根据一日游套餐制定的与原则吗，得到如下二日游旅游套餐。将所到的 数据按照最优路线条数，最优路线、最短路程、最优大船数量、最优小船数量、人均费用挥之表格，如下。 表格
19、5： 路线条数 最佳路线 最佳人数 1t 2t 人均费用 1 P A C B D P 240 2 1 669.6k 1 P A C B E P 210 2 1 590.15k 2 P A C B D P P E D C A P 450 4 2 1609.81k 注：由于 D 的住宿承受力是 200，因此当达到景点容纳能力后，若在 D 入住会大于住宿的承载力，因此在考虑 BCDE 及 ABDE 路线时，此时客人数量只能取两者最小的一个，因此双方考虑后的到如上表格 8 问题二 此问题要求确定新建旅馆的地点与规模人数，所以分两部分进行 1.地点 首先，假设在同一时刻所有景点都满员，则得到 x =14
20、50 50%x =725 同时假设 C、 D旅馆都达到最大承受能力，所以所建旅馆的最大规模为 725-200-280=245（人） 其次分别利用算法计算出 2bU 、 2cU 、 2dU 2 1 12u u u 1 1 21 0 0 0 . 8 5 4 0xxu t s k t S 11 2 1 21 . 5 ( 1 0 0 4 0 m in ( 2 4 5 , )m in ( 2 4 5 , ) iiuu t t RR 因此可得 2 33125bUk 2 44445cUk 2 51215dUk 选取 B点为所建旅馆的地点。 2.规模 每天游览景点的人数不同，因此以新建旅馆的最大承受能力依次递
21、减 20 人，分析对应的 2bU 的变化情况。由算法 5 可得如下 4 组数据 （ 245， 33125） （ 220,44445） （ 200,27370） （ 180,30311）。 其次，分别将这 4 组数据，利用 matlab 插值与拟合的方法，得到关于以规模人数为 x 轴，以总费用为 y 轴的相应关系如图 9 用 matlab 中的 figure 工具找到最平缓位置（斜率变化不明显）。因此得到此时 x在 180 205。然后，进行精细分析。用 matlab 中坐标工具，可以得到该曲线中的最低点（ 199,27365） 如图 因此，取 x =200 即为该新旅馆的规模人数。 由于一日游
22、问题不考虑住宿问题，因此在游览套餐中一日游的不需要改动。由于二日游问题在考虑住宿条件。在增加新的旅馆后，缩小了条件限制，扩大了可选择点。现在二日游问题上，游览路线的第二个位置或第三个位置可以是 B、C、 D、三点重的任意一个。因此在所求的最短路径中因 B不能住宿而舍去的路线，10 现在需要重新进行考虑。因为 P E C B D P 是如上所说的问题，所以经过重新计算后年得到 PEDBCP 相应的最短距离： 258km ， 大船数量： 2，小船数量： 0，最优人数： 200，总费用：578.025k ，将新的路线进行重新考虑，因此二日游套餐需要改动，改动结果如下。 表格 6： 路线条数 最佳路线
23、 最佳人数 1t 2t 人均费用 1 PEDBCP 200 2 0 578.02k 1 P A C B E P 210 2 1 590.15k 2 P A C B D P P E D C A P 450 4 2 1609.81k 程序 附件 求最短路 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) %functionD,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
