海岛优化方案答案

精品文档 1欢迎下载 数学建模 doc 123 海岛优化方案分析 摘要 经济水平的增加 带动了旅游业的发展 本文研究了 5 个岛屿与港口之间 最短距离及乘船计划 以最小费用为准则 制定了最优化一日游 二日游套餐 以及为满足游客的需要 通过考虑游客量及费用两大方面 找到建设旅馆的最 优地方 与最优规模 问题一 问题一 对于一日游问题 首先考虑单线整体旅游 以所游两地的最大承 受能力的最小值为游客量对 10 种路线分别计算 得到每条路线的费用 考 2 5 C 虑到游客人数不定 所以以旅游线进行分类分为 6 种 1 2 3 4 5 分别对 这 5 种线 从 10 种路线中进行最优匹配 根据所旅游景点尽可能分散 旅客尽 可能多 总费用尽可能少的原则进行匹配 根据 1 3 wmRu 衡量得到最优的五种一日游套餐 对两日游 按种考虑 利用算法 得到每种路线的最优走法 4 5 5C Dijkstra 同时仅有 C D 两地可以入住 所以在参观景点次序排列时第二个位置 游客在 旅游地直接入住 或第三个位置 游客不在旅游地入住 在第二天旅游地旅游 之前先入住 必须是 C D 两景点中至少一个 并且在游客规模取景点承受能力 的人数与旅馆容纳能力的最小值作为该次旅游的人数规模 结合最有走法 与 条件限制 其次 根据一日游的原则以相同的方法可以得到最优的两种套餐 见表格 5 问题二 问题二 在假设所有景点都达到接待游客的能力后 得到所建旅店的最大规 模 分别计算各点到 B C D 点在最大规模的情形下 根据算法 3 利用公式 21212 1 10 8 54 1 1 5 10040min 245 min 245 xi i us kttttR R 得到 2 33125 b Uk 2 44445 c Uk 2 51215 d Uk 找到最低费用的位置 因此选取 B 岛为新建旅馆地点 同时将规模按阶降低 利用相同的算法得到关于的四组数据 2b U 245 33125 220 39288 200 27370 180 30311 将这四组kkkk 数据以规模人数为轴 以总费用为轴 用插值与拟合的方法得到 之间xyxy 精品文档 2欢迎下载 的相应关系 取变化率最小 即图线最平缓的点的值进行取整 作为新建旅x 馆的规模人数 即在 B 点建立旅馆且最大承受能力为 200 人 由于在考虑一日游问题上 没有考虑住宿问题 所以一日游套餐不需要要改动 但是 二日游问题上有一条最短路径因为 B 不能入住而舍去 需要改动 然后以相同的方法制定 相应的套餐 符号说明 因租船所产生的费用 u 路程费 1 u 损失费 2 u 租大船的条数 1 t 租小船的条数 2 t 游客人数x 每条路线的最短路程 s 船只每公里费用系数 k 第 个景点的游客承受力 i Ri 第 个景点到 B 点的费用 2 i Ui V 表示所选两景点中 接受游客的能力中的最小值 m 景点个数 问题分析 问题一问题一 分析 一日游 由表 1 岛屿与港口之间距离 先绘制出海岛与港口粗略的平 面分布图 再利用 matlab floyd 算法 求在两点间的最短路 首先考虑旅行费 问题 由已求出的五个海岛与港口六个点的任意两点的最短距离 计算出 种 每种路线的最短路程 然后依次得到相应的每条路线的路程费用 2 5 C 1 u 其次考虑游船损失问题 根据 A B C D E 各景点的承载游客的能力 所以 每条路线一般有 大船 小船之内进行合理匹配 根据已求 1 03t 2 07t 的路线 求每条路线两个景点中最大承载能力的最小值为该条路线的规模人数 计算出相应的 最后利用公式 2 u 精品文档 3欢迎下载 12 uuu 将结果按从小到大进行排列 根据游客的人数不同 考虑到实际问题 2 5 C 根据旅游线条数进行分类 得到 5 种分类 考虑到每个套餐中景点分散度 最 短距离与总费用三者之间所占的权重按从小到大排列得到最优旅游套餐 取前 六种路线即为旅游套餐 两日游 按种考虑 利用算法 得到每种路线的最优走法 4 5 5C Dijkstra 同时仅有 C D 两地可以入住 所以在参观景点次序排列时第二个位置 游客在 旅游地直接入住 或第三个位置 游客不在旅游地入住 在第二天旅游地旅游 之前先入住 必须是 C D 两景点中至少一个 考虑到旅店的容纳人数 游客规 模取景点承受能力的人数与旅馆容纳能力的最小值作为该次旅游线的人数规模 结合最有走法 条件限制 根据一日游的算法 得到相应的 其次 根 1 u 2 u 据制定一日游套餐的原则 以相同的方法可以得到最优二日游套餐 问题二问题二 分析 建设新旅店问题 只需考虑两大准则 建设地点 建设规模 建设 地点 首先以衡量标准最小来标量 其中 各个景点分别到 12 uuu 1 u 的最短距离总和 假设在同一时刻 各个景点都达到最大承载能力 B C D 2 u 选取各个景点的最大承载能力的总人数的和 景点最大游客量 的 50 减去 C D 景点所承受能力的总人数 得到建立旅馆的最大容纳规模 根据损失费用 标量得到 利用 2 u 12 1uuu 将 B C D 各点的情况依次算出 进行比较得到结果 其中 112 1000 8540 xx utskts k 1212 1 5 10040min 245 min 245 i i u uttR R 由将 依次算出 取 min 的位置 2112 uuu 2b U 2c U 2d U 2b U 2c U 2d U 即为新建旅馆的建设地点 建设国模 考虑到景点每天的游客流量不同 所以 将最大游客流量按阶 以 20 为一个单位 进行计算分别得到 245 2i U 220 200 180 四点 然后利用插值与拟合的方法得到 2i U 2i U 2i U 以规模人数 总费用的相关关系图像 取斜率最小 图像最平缓 的人数 x y 规模阶段 近似取整 确定建旅馆的规模大小 精品文档 4欢迎下载 由于在考虑一日游问题上 没有考虑住宿问题 所以一日游套餐不需要要 改动 但是二日游问题上有一条最短路径因为 B 不能入住而舍去 需要改动 重新考虑最短路线 最优游客人数 最优购船计划 游览费用 同时在于其它 四条路线进行比较 利用原先相同的方法 制定二日游套餐 模型建立与求解 问题一问题一 由表 1 岛屿及港口之间的距离 利用软件 画出海岛与港口的平面分布ps 图 图 1 1 1 一日游问题 假设该旅游区每天都有大量的游客来旅游 超过了各个 景点的接待游客的能力 由于每个景点游半天 因此一日游涉及到 2 个景点的 选取 因此有种情形 首先利用 matlab floyd 算法求出任意两点 海 2 5 10C 岛与港口 间的最短距离得到如下表格 表格 1 加权图的任意两个岛屿之间的距离和路径 距离矩阵M路径矩阵N M 04621506070 460303253115 21300485390 50324802195 60535321085 701159095850 N 123456 123446 123456 123456 143456 123456 精品文档 5欢迎下载 由此 得到相应的 10 条游览路线的最短路程 根据路程费用的公式 结合已经求出的最短路程 得到 112 0 85ukstt 每条路线的路程费用 因为每个景点的最大承载能力有限制 所以选取每条路线中两个景点的最大 承载能力的最小值 作为该条游览路线的最大游览人数 根据大船 小船的容 纳人数 依此确定每条路线相应的 然后根据公式 1 t 2 t 计算出每条路线的损失费用 1 212 1 5 10040 u uttV V 由于费用包括客均费用与损失费用 即 12 uuu 通过普通算法 2 路程费用 损失费用 得到每种路线的总游览费用 对于多种购船方案如下处理 其中 由于 V 确定相应的 会得到相对应 1 t 2 t 的分配 可能会得到两种分配 1 a 2 a 例如 235250PBCPSkmV 其中 人 游船少载 50 人 游船少载 30 人 得到 1 2 3 10 t t a 1 2 2 22 t t a 针对 1 a 1 1 2 12 235 3 0 85599 25 1 5 50179 775 250 799 025 ukk u u uuuk 针对 2 a 1 1 2 12 235 2 0 85869 5 1 5 50260 85 250 1130 35 ukk u u uuuk 12 aa uu 选取乘船方案 1 a 将这 10 种方案依次算出游览费用 并且按照路线 最短路程 大船数量 小船 数量 游览总费用 并按从小到大的顺序排列绘制成表格 精品文档 6欢迎下载 表格 2 路线最短路程 1 t 2 t 总费用 PACP 181km 2 1 488 7k PADP 215km 2 1 580 5k PABP 231km 2 1 623 7k PBDP 242km 3 0 628 22 PCDP 233km 3 0 727 40 PBCP 235km 3 0 779 03 PDEP 201km 0 6 1518 43 PAEP 215km 0 6 1566 44 PCEP 228km 0 6 1661 14 PBEP 253km 0 6 1843 28 考虑到每天景点的游客量的不确定性 依据每天景点的游览路线的总条数进行 分类 大致分成 5 类 1 2 3 4 5 1 只有一个景点达到最大承载能力 5 所有景点 在同一时刻都达到最大承载能力 按照景点分散度 旅客人数及 总费用 利用函数衡量 得到最优匹配 选取合理的 5 种匹配 1 3 WmRu 绘制成表格如下 表格 3 线条数 最佳人数 最佳路线最佳分配 人数与 路线相对应 1 经 E210PDEP 21PDEP 0 1 不经 E240PACP 240PACP 2 全经 E420PAEP PDEP 210PAEP 21PDEP 0 精品文档 7欢迎下载 2 无要求 520PACP PBDP 240PACP 28PBDP 0 3 无要求 730PACP PBDP PCEP 24PBDP 028PACP 0 PCEP 二日游 由于每日只能游 2 个景点 因此 2 日游需对 4 个景点进行旅游 2 在 5 个景点中 所以有 5 种景点旅游选择 分别是 4 5 5C ABCDABCEACDEBCDEABDE 将 5 种情形分别进行讨论 1 首先利用 matlab 行遍性问题中的 TSP 算法 程序见附录求最短ABCE 路 可以得到由 P 点出发经过全部 A B C D 回到 P 的最短路径图线 但由于 仅有 C D 两个岛屿有游客可供住宿 所以在最短路线中 要求第 2 个位置 游 客可以在旅游景点入住 或第 3 个位置 游客可以在旅游景点入住然后参观 必须是 C D 中的至少得任意一个 若所得路线满足条件 则是所求路线 否则 需进行下步计算 将 ABCD 进行满足条件的全排列 分别利用算法计算每个排列 的人均费用 取人均费用最小的排列为该四个景点的最优游览路线 并且得到 相应的路程费用 取每条路线中四个景点的最大承载能力的 旅馆最大容纳能 力的最小值 最为该条路线的最优游览人数 根据一日游求解损失费用的方法 得到每条路线在最优人数下的损失费用 然后把得到的数据按照路线 最短路 程 大船数量 小船数量 人均费用回执成表格 得到如下表格 表格 4 景点路线 最 短距离 1 t 2 t 人均总费 用 ABCDPACBDP 248km 2 1 669 6k ABCEPACBEP 259km 2 1 590 15k ACDEPEDCAP 245km 2 1 803 25k BCDEPECBDP 295km 2 1 940 21k ABDEPEDBAP 254km 2 1 840 12k 精品文档 8欢迎下载 考虑到实际问题 考虑到每个套餐中景点分散度 最短距离与总费用三者 之间所占的权重 根据一日游套餐制定的与原则吗 得到如下二日游旅游套餐 将所到的数据按照最优路线条数 最优路线 最短路程 最优大船数量 最优 小船数量 人均费用挥之表格 如下 表格 5 路线条数最佳路线最佳人 数 1 t 2 t 人均费用 1 PACBDP 2402 1 669 6k 1 PACBEP 2102 1 590 15k 2 PACBDP PEDCAP 4504 21609 81 k 注 由于 D 的住宿承受力是 200 因此当达到景点容纳能力后 若在 D 入住 会大于住宿的承载力 因此在考虑及路线时 此时客人数量只能BCDEABDE 取两者最小的一个 因此双方考虑后的到如上表格 问题二问题二 此问题要求确定新建旅馆的地点与规模人数 所以分两部分进行 1 地点 首先 假设在同一时刻所有景点都满员 则得到 1450 50 725 同x x 时假设 C D 旅馆都达到最大承受能力 所以所建旅馆的最大规模为 725 200 280 245 人 其次分别利用算法计算出 2b U 2c U 2d U 2112 uuu 112 1000 8540 xx utsktS 1 1212 1 5 10040min 245 min 245 i i u uttR R 因此可得 2 33125 b Uk 2 44445 c Uk 2 51215 d Uk 选取 B 点为所建旅馆的地点 2 规模 每天游览景点的人数不同 因此以新建旅馆的最大承受能力依次递减 20 人 分析对应的的变化情况 由算法 5 可得如下 4 组数据 2b U 245 33125 220 44445 200 27370 180 30311 其次 分别将这 4 组数据 利用 matlab 插值与拟合的方法 得到关于以规模人 精品文档 9欢迎下载 数为轴 以总费用为轴的相应关系如图xy 用 matlab 中的 figure 工具找到最平缓位置 斜率变化不明显 因此得到此时 在 180205 然后 进行精细分析 用 matlab 中坐标工具 可以得到该曲线x 中的最低点 199 27365 如图 因此 取 200 即为该新旅馆的规模人数 x 由于一日游问题不考虑住宿问题 因此在游览套餐中一日游的不需要改动 由于二日游问题在考虑住宿条件 在增加新的旅馆后 缩小了条件限制 扩大 了可选择点 现在二日游问题上 游览路线的第二个位置或第三个位置可以是 精品文档 10欢迎下载 B C D 三点重的任意一个 因此在所求的最短路径中因 B 不能住宿而舍去的 路线 现在需要重新进行考虑 因为 PECBDP 是如上所说的问题 所以经过重新计算后年得到 PEDBCP 相应的最短距离 258 大船数量 2 小船数量 0 最优人数 200 总费km 用 578 025 将新的路线进行重新考虑 因此二日游套餐需要改动 改动结k 果如下 表格 6 路线条数最佳路线最佳人 数 1 t 2 t 人均费用 1 PEDBCP 2002 0 578 02k 1 PACBEP 2