2012年美国大学生数学建模竞赛B题特等奖文章翻译要点.pdf

《2012年美国大学生数学建模竞赛B题特等奖文章翻译要点.pdf》由会员分享，可在线阅读，更多相关《2012年美国大学生数学建模竞赛B题特等奖文章翻译要点.pdf（15页珍藏版）》请在三一文库上搜索。

1、2012 年美赛 B 题 题目翻译： 到 Big Long River （225 英里）游玩的游客可以享受那里的风景和振奋人心的急 流。远足者没法到达这条河，唯一去的办法是漂流过去。这需要几天的露营。河 流旅行始于 First Launch ，在 Final Exit 结束，共 225 英里的顺流。旅客可以选 择依靠船桨来前进的橡皮筏，它的速度是4 英里每小时，或者选择8 英里每小 时的摩托船。旅行从开始到结束包括大约6 到 18 个晚上的河中的露营。负责管 理这条河的政府部门希望让每次旅行都能尽情享受野外经历，同时能尽量少的与 河中其他的船只相遇。当前，每年经过Big Long 河的游客有

2、X 组，这些漂流都 在一个为期 6 个月时期内进行，一年中的其他月份非常冷，不会有漂流。在Big Long 上有 Y 处露营地点，平均分布于河廊。随着漂流人数的增加，管理者被要 求应该允许让更多的船只漂流。 他们要决定如何来安排最优的方案：包括旅行时 间（以在河上的夜晚数计算）、选择哪种船（摩托还是桨船），从而能够最好地 利用河中的露营地。换句话说，Big Long River 在漂流季节还能增加多少漂流旅 行数？管理者希望你能给他们最好的建议，告诉他们如何决定河流的容纳量，记 住任两组旅行队都不能同时占据河中的露营地。此外，在你的摘要表一页， 准备 一页给管理者的备忘录，用来描述你的关键发现

3、。 沿着大朗河露营 摘要 我们开发了一个模型来安排沿大河的行程。我们的目标是为了优化乘船旅行 的时间，从而使 6 个月的旅游旺季出游人数最大化。 我们模拟团体从营地到营地旅行的过程。根据给定的约束条件， 我们的算法 输出了每组沿河旅行最佳的日程安排。通过研究算法的长期反应， 我们可以计算 出旅行的最大数量，我们定义为河流的承载能力。 我们的算法适应于科罗多拉大峡谷的个案分析，该问题的性质与大长河问题 有许多共同之处。 最后，我们考察当改变推进方法， 旅程时间分布， 河上的露营地数量时承载 能力的变化的敏感性。 我们解决了使沿大朗河出游人数最大化的休闲旅行计划。从首次启动到最终 结束（225 英

4、里），参与者需使用桨供电的橡胶筏或机动船在指定的参与者露营 地游玩 6 到 18 个晚上。为了确保一个真实的荒野体验，一组在同一时间最多占 据一个营地。这个约束限制了公园的6 个月的旅游旺季期间可能的旅行数量。 我们模拟情景， 然后把我们相似特性的研究结果进行比较，从而验证了我们 的方法是否能得到令人满意的结果。 我们的模型是适用于针对有着不同长度的河流、不同数量的露营地、 不同的 行程持续时间、以及不同的船的速度的情况中，找到最佳的行程安排。 问题重述 ?应该如何制定不同长度和推进过程的旅行计划，使其在6 个月的旅行季中旅行 可能数量最大化？ ?在任何时候，有多少新的组可以开始河上旅行？ ?

5、什么是河流的承载能力在六个月的旅行季中可以发送顺流而下的最大数量 的组？ 模型概述 我们设计了一个模型， ?可以应用到具有相似属性的真实世界的河流（即，大峡谷）; ?足够灵活，以模拟各种可行的输入参数; ?模拟河往返调度的关于旅行分布长度（无论是6，12，或 18 天）的推进，不同 的分布速度和不同数量的露营地的函数。 该模型可以预测出这6 个月的旅行季的旅游人数。 它还回答有关河流的承载 能力，有利的推进速度和行程长度的分布，每一天可以有多少组开始河流之旅， 以及如何安排行程。 约束条件 问题指定了以下限制： ?旅行在始发点开始并在终点结束，225 公里的下游。 ?只有两种船：桨供电的橡胶筏

6、和电机化船。 ?桨供电的橡皮筏平均每小时旅行4 英里。 ?电动船平均每小时旅行8 英里。 ?旅行时间范围是 6 至 18 晚。 ?旅行安排在一年的6 个月期间。 ?露营地沿河均匀分布。 ?没有两个组可以同时占据相同的营地。 问题假设 ?我们可以规定每天能到河上航行的桨供电河筏和机帆船的比例。 如果有太多的桨动力船在短时间内出行，有可能会出现问题。 ?桨供电筏一趟的时间是12 天或 18 天，机动船的为 6 天或 12 天。 这种简化使得我们的模型产生有意义的结果。同时，让我们比较不同的行程长度 的效果。 ?每个营地每晚只能有一组。这符合河川管理者的要求。 ?每一天，一组只能向下游移动，或留在其

7、目前的营地不能向上游航行。这 将流动组限制在了一个单一的方向上，从而极大地简化了我们该如何移动营地与 营地间的组。 ?旅行组从上午 8 时至下午 6 时，每天最多只能航行9 小时（减去一个小时休息 / 午餐/等）。这意味着，每一天，桨动力筏旅行最多航行36 英里，机动船最多 72 英里。这种假设使我们可以确定哪些组可以合理地达到某一的营地。 ?旅行团每天的航行里程不能超过他们合理的旅行距离：桨动力阀最多 36 英里每 天，机动阀 72英里每天。 ?我们忽略可能影响最大出行距离的变量，如天气和河流条件。没有办法将这些 变量精确地包括在模型中。 ?露营营地之间的距离均匀分布，这样营地间的距离就等于

8、河流的长度除以营地 的数量。因此，我们可以将河流表示为一个等距离分布露营地的数列。 ?A组必须在其行程的最后一天到达终点的河流：A 组即使可以，也不会提前离 开河流。A 组不会超出计划的旅行时间。 我们相信这个假设符合河流管理者以及 旅行质量的标准。 模型建立 我们定义一些术语和短语： 开放的营地（ open campsite）：如果目前没有旅行团占用，营地是开放的：如 果没有组被分配到，营地是开放的。 移动到一个开放的营地 （moving to an open campsite ）：对于一组营地是的 组，其移动到其他的开放营地， 即， 相当于组分配到新营地。 由于旅游团只可以向下游移动，或留

9、在他们目前的营地，我们有。 等待名单（waitlist）：某天的等待名单是那些在河上但还没有开始当天的旅行 团组成，此时他们在等待名单上的排名和他们到达营地c 的能力将他们包含在能 够到达营地 c 的所有组的集合，这些组被视作有着最大的优先权。等待名 单上的组以当前的营地初值为， 并且有着之为 P=1 的优先权知道他们从等待 名单上移除，并到河上开始旅行。 离开河流（ off the River ）：我们认为，河上第一个离开的营地是，它始 终是一个开放的营地 （因此，任何数量的组可以被分配给它。这符合任何数量的 旅行团都可以在任何一天离开河流的理解。 最远的空营地（ the Farthest

10、Empty Campsite）:我们的调度算法使用一个数 组作为数据结构来表示河流， 数组的每个元素作为一个营地。 每天以找到在河上 最远的开放营地 c 来开始该算法，然后生成一个集合，其中包含了所有在 当晚可能到达 c 的组。因此， Gc = gi | li + mi c, 其中是该组的当前位置，是该小组可以在一天之内旅行的最大距离。 ? 限定了组必须能够在一天之内到达营地 ?。 ? 是有在河上以及等待名单上的组构成。 ?如果 ，那么我们可以移动到下一个最远的空营地位于上流，并 更接近于河流的起点。该算法总是从河流的末端向河流的始端运行。 ?如果，则算法试图将具有最高优先级的组移动到营地C。

11、 该调度算法一直执行到最远的空营地是为止。此时，每个能在河上继续 航行的组被分配到一个营地，然后我们开始另一个算法来模拟第二天。 优先级 : 一旦集合已形成为特定的露营地? ，算法必须决定哪个组移动到该营 地。优先级是一个衡量组落后或提前于计划的程度的量： 衡量多远的前面或后面的计划组gi 是： ?1：组进度落后 ; ? PC ，A 组搬到营地 5。并且扎营 的夜数就等于之前确定的旅行长度。然而，在某些情况下， 它可能无法以最高的 优先级将组移到最远的可用的开放营地。这种情况下，如果具有最高优先级的是 提前与计划的（ P1，那么移动到 c其最远可达的开放营地。 ?如果提前，即 1，然后计算 该

12、组在河上已经度过的夜数乘 以每天计划行进的平均距离。 如果结果是大于或等于 （以英里为单位） 的露营地 c 的位置，那么移动到 c。这样做可以让不再提前于计划。 ?不管，如果选择，那么不移动，除非。此功能 可确保，的行程不会在其计划结束日期前结束。在图3 中示出了一个组的优 先级被忽略的情况。 调度仿真： 现在我们证明我们的模型可以用来安排河流上的旅行次数。 在下面的例子中， 我们假设沿 225 英里的河流有 50 个露营地， 我们设定每 天河上有四个组。我们为 图 3 最远的开放营地不在河上。该算法找到，组D 可以移动到那里，但D 组 有，即组 D 计划在河上待 12 晚，但到目前为止，只待

13、了11 晚 所以 D 组仍然在河上，在营地171 和 224（含）之间。 我们引进的四个特定组做了一个25 天的行程计划。我们选择了旺季中的一天， 以证明我们的模型的时间稳定性。四组的特性如下： ? ：机动， =6; ?：桨供电，=18; ?：机动，=12; ?：桨供电，=12。 案例：（大峡谷） 大峡谷是一个针对我们模型研究的理想情况，因为它和大朗河的许多特征相 同。峡谷的主要河流长为226 英里，它拥有 235 个露营地，它在一年里大约有 六个月都开放。它可以让游客乘坐机动船或桨供电河筏分别最多航行12 天或 18 天。 使用的大峡谷参数中， 我们模拟了多次来测试我们的模型。我们改变每天在

14、 河上的组的数量，想要得出河流的承载量 图 5 例如组推出的第 25 天时间表。 图 6 在图 5 的基础上顺流而下的组的运动。组由不同的行程持续时间参数在不 同的时间到达终点。 图7每组行进过程的优先级值。由于算法为了保持组群按时进行，值收敛到 P=1。 长达六个月的可能的最大旅行数量。主要的制约因素是， 每趟必须持续组的计划 旅程时间。在夏季，大峡谷一般会将新的六组置于水上贾等人的水。 2006 ，所 以我们使用这个值为我们的第一次模拟。在每一次模拟中， 我们使用同等数量的 机帆船，桨动力筏，以及相等行程长度的分配。 我们的模型预测出成功离开河的组（已完成人数） 的数量， 以及超过他们预

15、定的截止日期（逾期人数）的人的数量，以及没有离开候补名单的人的数量（候 补名单上的总人数）。 这些值随着我们改变分配到水上的新团队的数量而变化（团 队/天）。 表 2 每组每天的模拟结果 仿真组 /天 模拟 数 每组每天载 人数 完成人数逾期人数 等待人数 表 1 表明了 18 个组中每天可分配到河上的最大人数。在过去的六个月中， 乘船人数近 3000 人次。增加至 18 组/天以上，很可能导致迟到人次（我们的模 拟结束时，一些团体仍然在河上）和长候补名单。在模拟1 中，我们将 1,080 组分配到河中 （6 组/天 180 天），但只有 996 组成功离开 ;其余的组在近这六个 月时段的末期

16、开始并且没有在此季度结束之前完成他们的行程。这些团体有对本 公司业绩的影响可以忽略不计，因此我们忽略它们。 承载力的敏感性分析： 大朗河的管理者面临着和大峡谷的管理者都类似的任务。因此，通过寻找大 峡谷的最佳解决方案， 我们也可以找到一个大朗河的最佳解决方案。然而，这个 最佳的解决方案是基于两个关键假设： 1，每一天，我们把到大约相同数量的群体放到河里； 2，河大约每英里有一个营地。 我们可以对大峡谷做这些假设， 因为这些假设对大峡谷来说是成立的，但我 们不知道，如果他们是否对大朗河成立。 为了应对这些未知因素，我们创建了表3。其生成的值是通过把河上的营地 数量 Y 以及动力阀与每天发行的机动

17、船的比率R 进行拟合得到的，然后将新增 到河上的人数增至河水的最大承载力。 表三 河的承载力关于营地数量以及动力阀与机动船的比率的方程 表 3 中的峰值承载能力可以看成是一个三维的空间中的点，我们可以找到拟 合度最高的曲面 -（几乎）经过通过数据点。拟合度最好的曲面可以让我们设定 河峰值承载能力 M 为插入值。 基本上，它给出了 M 关于 Y 和 R 的函数，显示了 M 关于 Y 和/或 R 的敏感程度。图7 该曲面的轮廓图。 图 7表 3 中的点的最高拟合度的曲面轮廓图 沿着垂直线的脊线的R = 1：1 可以预测出，对于任何给定的Y 在 100 和 300 之间的值，当 R = 1：1 时河

18、流会有一个最优值。不幸的是，这个最佳拟合 曲面的公式很复杂， 它在工作表 3 的数据之外并不能给出一个准确的推断；因此 它并不是一个特别有用测量其它R 值的峰值承载能力的工具。最好的预测峰值 承载力的方法就是使用我们的调度算法。 承载能力 R 和 D 的敏感性分析： 我们已经得到了了M 关于 R 和 Y 的函数，但我们仍然不知道M 是怎样被河 上不同群体的旅行时间（D）所影响的。例如，如果我们的计划是6 天或 12 天 的旅行， 这将如何影响 M？河流管理者想知道什么样关于不同的旅行时间和速度 的结合将可能以最好的方式利用河流。 我们用我们的算法来试图回答这个问题。我们讲露营地的数量设置在20

19、0 并且确定峰值承载力值的R 和 D。此仿真的结果如表4 所示。 表 4 是为了解决怎样分配旅行时间和速度会得到最大承载能力的问题。例 如：如果河流管理者目前在安排旅行时间 6，12，或 18：容量可以通过增加R 至接近 1:1 或通过降低 D 至更接近 “6 或 12” 而增大。 12 或 18：降低 D 到接近 “6 或 12” 。 6 或 12：增加 R 至更接近 4:1。 模型求解 河流管理者问多少次旅行可以被添加到大朗河的季节。不知道河流现在是如 何被管理的细节， 我们不能给出一个确切的答案。然而，通过把我们的模型用到 大峡谷的一项研究中， 我们发现结果可以外推到大朗河的背景下。特别

20、地，大朗 河的经理可以增加约 （3000-x ） 组至漂流季节， 其中 X 是当前旅次的数量、 3000 是我们的调度算法预测的容量。 此外，我们模拟了某些变量的相互关系；M，D，R，和 Y。河流管理者可 以参考我们的数据和表格，看他们如何能改变当前流D 和 Y，R 值，以实现更 大的大朗河承载能力。 我们还通过一个用优先级值来有序的将组群运送到下游的算法，解决了给移 到大朗河下游的组群分配营地的问题。 局限性和误差分析： 承载能力估计过高： 我们的模型有几个局限性。 它假定河的承载能力只受到的露营地数量，旅行 时间，和运输方法的限制。 我们将河流的承载力最大化，即使这意味着几乎每一 个营地每

21、晚都被占用了。这可能不是最理想的，可能导致河流堵塞或环境退化。 因此，我们的模型可能高估了在很长一段时间内的旅行可能的最大数量。 环境问题： 我们大峡谷的案例研究的表明， 我们的模型忽略了的变量。 我们确信大峡谷 可以为在六个月的时段内为3，,000 个旅行提供足够的营地， 正如我们的算法所 预测得。然而，由于实际的数量约是1000 次贾等人。 2006 ，错误可能是由于 营地能力之外的因素导致的，比如环境因素。 忽视河流的速度： 另一个我们模型所忽略的变量是河流的速度。河流的速度随着河道的深度和 坡度的增加， 使得我们关于每天旅行的最大距离恒定的假设不可能。当河流经历 洪流，河的速度加倍，所

22、有的营地都会被水淹没。又一次，我们的模型结果没有 反映这些问题。 参考文献 c.u.博尔德系应用数学配合表面 X-Y-Z 数据点。 http:/amath.colorado.edu/computing/Mathematica 。 贾，琳达，丽诺尔和洛里布林顿等,2006, 科罗拉多河管理计划。 2006.http:/www.nps.gov/grca/ parkmgmt /上传/ crmpif_s.pdf 。 国家公园服务 ,2008, 大峡谷国家公园 http:/www.nps.gov/grca/naturescience/higlow2008-permit.htm。 2011 大峡谷国家公园

23、 ,2011 营地名单。 http：/www.nps.gov/grca/parkmgmt/upload/2011campsitelist.pdf。 沙利文史提夫 ,2011, 大峡谷的河流统计2010 日历年。 http:/www.nps.gov/grca/planyourvisit/upload/calendar_year_2010_river_statis tics.pdf 。 维基百科 2012 年 http:/en.wikipedia.org/wiki/river。 致大朗河经理的一封信 为了回答你的关于旅行调度和河承载能力的问题，我们写了这封信来告诉你 我们的发现。 我们的主要成果是

24、建立了一个调度算法。如果在大朗河中实现， 它可以建议 公园巡游者如何最好地调度不同长度和进度的旅行。最佳的计划将在六个月的旅 行季节内尽可能地使旅行数量达到最大。 我们的算法比较灵活， 需要各种不同的输入数据。 这些包括营地的数量和可 用性，并与各旅游团相关参数结合起来。给予必要的输入， 我们可以输出每天的 时间表。在本质上， 我们的算法是通过使用从以前的河流的状态而实现的。计划 包括河上每个营地组的分配， 以及那些等待开始他们旅行的人。如果知道未来的 等待名单，我们的算法可以提前几个月输出时间表，这样管理层就能安排出未来 任一天营地的精确位置。 为你省掉了很多数学细节，让我们简单地说，我们的

25、算法采用优先级系统。 通过将那些落后于行程的人移至更远的营地并且阻碍那些先于行程的人，此算法 让那些落后于行程的人优先。 这样一来，它可以保证所有的旅行将会在旅客计划 完成的时间内恰好完成。 但调度只有一部分是我们的算法可以做的。它也可以计算在6 个月的季度内 可能的旅行的最大数量。 我们称它为河流的承载能力。 如果我们发现我们低于承 载能力，我们的算法可以告诉我们每天可以有多少组增加到水上。相反，如果我 们遇到河流堵塞，我们可以决定每天要应该减少多少组来让水上工作恢复正常运 行。 其中， 我们的算法一个有趣的发现是动力阀与机动船的比率将怎样影响我们 可以送到下游的旅行数量。当处理分布均匀的出行时间时（从6 到 18 天），我 们建议一个 1:1 的比例来最大化河流的承载能力。如果分布偏向较短的旅行时 间，那么我们的模型预测预测出增加至4:1 的比率将导致承载力增加。 如果分布 偏向相反的方式， 即偏向更长的旅行时间， 那么河流的承载能力将远不比前两种 情况所以这种情况是不被建议的。 我们的算法已经经过全面地测试， 我们相信这是一个确定河流承载能力的有 力工具优化日常工作的安排， 并确保人们在享受真正野外旅行的同时能够按 计划完成旅行。 诚挚的 13955 队，团队成员芯片杰克逊，卢卡斯，和特拉维斯彼得斯，和团队的顾问阿 米兰。