《2012年美国大学生数学建模竞赛B题特等奖文章翻译》由会员分享,可在线阅读,更多相关《2012年美国大学生数学建模竞赛B题特等奖文章翻译(15页珍藏版)》请在金锄头文库上搜索。
1、 2012年美赛B题题目翻译:到Big Long River(225英里)游玩的游客可以享受那里的风景和振奋人心的急流。远足者没法到达这条河,唯一去的办法是漂流过去。这需要几天的露营。河流旅行始于First Launch,在 Final Exit结束,共225英里的顺流。旅客可以选择依靠船桨来前进的橡皮筏,它的速度是4英里每小时,或者选择8英里每小时的摩托船。旅行从开始到结束包括大约6到18个晚上的河中的露营。负责管理这条河的政府部门希望让每次旅行都能尽情享受野外经历,同时能尽量少的与河中其他的船只相遇。当前,每年经过Big Long河的游客有X组,这些漂流都在一个为期6个月时期内进行,一年中
2、的其他月份非常冷,不会有漂流。在Big Long上有Y处露营地点,平均分布于河廊。随着漂流人数的增加,管理者被要求应该允许让更多的船只漂流。他们要决定如何来安排最优的方案:包括旅行时间(以在河上的夜晚数计算)、选择哪种船(摩托还是桨船),从而能够最好地利用河中的露营地。换句话说,Big Long River在漂流季节还能增加多少漂流旅行数?管理者希望你能给他们最好的建议,告诉他们如何决定河流的容纳量,记住任两组旅行队都不能同时占据河中的露营地。此外,在你的摘要表一页,准备一页给管理者的备忘录,用来描述你的关键发现。 沿着大朗河露营摘要我们开发了一个模型来安排沿大河的行程。我们的目标是为了优化乘
3、船旅行的时间,从而使6个月的旅游旺季出游人数最大化。我们模拟团体从营地到营地旅行的过程。根据给定的约束条件,我们的算法输出了每组沿河旅行最佳的日程安排。通过研究算法的长期反应,我们可以计算出旅行的最大数量,我们定义为河流的承载能力。我们的算法适应于科罗多拉大峡谷的个案分析,该问题的性质与大长河问题有许多共同之处。最后,我们考察当改变推进方法,旅程时间分布,河上的露营地数量时承载能力的变化的敏感性。 我们解决了使沿大朗河出游人数最大化的休闲旅行计划。从首次启动到最终结束(225英里),参与者需使用桨供电的橡胶筏或机动船在指定的参与者露营地游玩6到18个晚上。为了确保一个真实的荒野体验,一组在同一
4、时间最多占据一个营地。这个约束限制了公园的6个月的旅游旺季期间可能的旅行数量。我们模拟情景,然后把我们相似特性的研究结果进行比较,从而验证了我们的方法是否能得到令人满意的结果。我们的模型是适用于针对有着不同长度的河流、不同数量的露营地、不同的行程持续时间、以及不同的船的速度的情况中,找到最佳的行程安排。 问题重述应该如何制定不同长度和推进过程的旅行计划,使其在6个月的旅行季中旅行可能数量最大化?在任何时候,有多少新的组可以开始河上旅行?什么是河流的承载能力在六个月的旅行季中可以发送顺流而下的最大数量的组? 模型概述我们设计了一个模型,可以应用到具有相似属性的真实世界的河流(即,大峡谷);足够灵
5、活,以模拟各种可行的输入参数;模拟河往返调度的关于旅行分布长度(无论是6,12,或18天)的推进,不同的分布速度和不同数量的露营地的函数。该模型可以预测出这6个月的旅行季的旅游人数。它还回答有关河流的承载能力,有利的推进速度和行程长度的分布,每一天可以有多少组开始河流之旅,以及如何安排行程。 约束条件问题指定了以下限制:旅行在始发点开始并在终点结束,225公里的下游。只有两种船:桨供电的橡胶筏和电机化船。桨供电的橡皮筏平均每小时旅行4英里。电动船平均每小时旅行8英里。旅行时间范围是6至18晚。旅行安排在一年的6个月期间。露营地沿河均匀分布。没有两个组可以同时占据相同的营地。 问题假设我们可以规
6、定每天能到河上航行的桨供电河筏和机帆船的比例。如果有太多的桨动力船在短时间内出行,有可能会出现问题。桨供电筏一趟的时间是12天或18天,机动船的为6天或12天。这种简化使得我们的模型产生有意义的结果。同时,让我们比较不同的行程长度的效果。每个营地每晚只能有一组。这符合河川管理者的要求。每一天,一组只能向下游移动,或留在其目前的营地不能向上游航行。这将流动组限制在了一个单一的方向上,从而极大地简化了我们该如何移动营地与营地间的组。旅行组从上午8时至下午6时,每天最多只能航行9小时(减去一个小时休息/午餐/等)。这意味着,每一天,桨动力筏旅行最多航行36英里,机动船最多72英里。这种假设使我们可以
7、确定哪些组可以合理地达到某一的营地。旅行团每天的航行里程不能超过他们合理的旅行距离:桨动力阀最多36英里每天,机动阀72英里每天。我们忽略可能影响最大出行距离的变量,如天气和河流条件。没有办法将这些变量精确地包括在模型中。露营营地之间的距离均匀分布,这样营地间的距离就等于河流的长度除以营地的数量。因此,我们可以将河流表示为一个等距离分布露营地的数列。A组必须在其行程的最后一天到达终点的河流:A组即使可以,也不会提前离开河流。A组不会超出计划的旅行时间。我们相信这个假设符合河流管理者以及旅行质量的标准。 模型建立我们定义一些术语和短语:开放的营地(open campsite):如果目前没有旅行团
8、占用,营地是开放的:如果没有组被分配到,营地是开放的。移动到一个开放的营地(moving to an open campsite):对于一组营地是的组,其移动到其他的开放营地,即,相当于组分配到新营地。由于旅游团只可以向下游移动,或留在他们目前的营地,我们有。等待名单(waitlist):某天的等待名单是那些在河上但还没有开始当天的旅行团组成,此时他们在等待名单上的排名和他们到达营地c的能力将他们包含在能够到达营地c的所有组的集合,这些组被视作有着最大的优先权。等待名单上的组以当前的营地初值为,并且有着之为P=1的优先权知道他们从等待名单上移除,并到河上开始旅行。离开河流(off the Ri
9、ver):我们认为,河上第一个离开的营地是,它始终是一个开放的营地(因此,任何数量的组可以被分配给它。这符合任何数量的旅行团都可以在任何一天离开河流的理解。最远的空营地(the Farthest Empty Campsite):我们的调度算法使用一个数组作为数据结构来表示河流,数组的每个元素作为一个营地。每天以找到在河上最远的开放营地c来开始该算法,然后生成一个集合,其中包含了所有在当晚可能到达c的组。因此,Gc = gi | li + mi c,其中是该组的当前位置,是该小组可以在一天之内旅行的最大距离。 限定了组必须能够在一天之内到达营地。 是有在河上以及等待名单上的组构成。如果,那么我们
10、可以移动到下一个最远的空营地位于上流,并更接近于河流的起点。该算法总是从河流的末端向河流的始端运行。如果,则算法试图将具有最高优先级的组移动到营地C。该调度算法一直执行到最远的空营地是为止。此时,每个能在河上继续航行的组被分配到一个营地,然后我们开始另一个算法来模拟第二天。优先级:一旦集合已形成为特定的露营地,算法必须决定哪个组移动到该营地。优先级是一个衡量组落后或提前于计划的程度的量:衡量多远的前面或后面的计划组gi是:1:组进度落后; PC,A组搬到营地5。并且扎营的夜数就等于之前确定的旅行长度。然而,在某些情况下,它可能无法以最高的优先级将组移到最远的可用的开放营地。这种情况下,如果具有
11、最高优先级的是提前与计划的(P1,那么移动到c其最远可达的开放营地。如果提前,即1,然后计算该组在河上已经度过的夜数乘以每天计划行进的平均距离。如果结果是大于或等于(以英里为单位)的露营地c的位置,那么移动到c。这样做可以让不再提前于计划。不管,如果选择,那么不移动,除非。此功能可确保,的行程不会在其计划结束日期前结束。在图3中示出了一个组的优先级被忽略的情况。调度仿真: 现在我们证明我们的模型可以用来安排河流上的旅行次数。 在下面的例子中,我们假设沿225英里的河流有50个露营地,我们设定每天河上有四个组。我们为图3 最远的开放营地不在河上。该算法找到,组D可以移动到那里,但D组有,即组D计
12、划在河上待12晚,但到目前为止,只待了11晚所以D组仍然在河上,在营地171和224(含)之间。我们引进的四个特定组做了一个25天的行程计划。我们选择了旺季中的一天,以证明我们的模型的时间稳定性。四组的特性如下:机动,=6;:桨供电, =18;:机动, =12; : 桨 供 电 , =12。案例:(大峡谷)大峡谷是一个针对我们模型研究的理想情况,因为它和大朗河的许多特征相同。峡谷的主要河流长为226英里,它拥有235个露营地,它在一年里大约有六个月都开放。它可以让游客乘坐机动船或桨供电河筏分别最多航行12天或18天。使用的大峡谷参数中,我们模拟了多次来测试我们的模型。我们改变每天在河上的组的数
13、量,想要得出河流的承载量图5 例如组推出的第25天时间表。图6 在图5的基础上顺流而下的组的运动。组由不同的行程持续时间参数在不同的时间到达终点。图7 每组行进过程的优先级值。由于算法为了保持组群按时进行,值收敛到P=1。长达六个月的可能的最大旅行数量。主要的制约因素是,每趟必须持续组的计划旅程时间。在夏季,大峡谷一般会将新的六组置于水上贾等人的水。2006 ,所以我们使用这个值为我们的第一次模拟。在每一次模拟中,我们使用同等数量的机帆船,桨动力筏,以及相等行程长度的分配。 我们的模型预测出成功离开河的组(已完成人数)的数量,以及超过他们预定的截止日期(逾期人数)的人的数量,以及没有离开候补名单的人的数量(候补名单上的总人数)。这些值随着我们改变分配到水上的新团队的数量而变化(团队/天)。 表2每组每天的模拟结果仿真组/天 模拟数每组每天载人数完成人数逾期人数等待人数表1表明了18个组中每天可分配到河上的最大人数。在过去的六个月中,乘船人数近3000人次。增加至18组