2023年12月7日发(作者:汉川高考数学试卷答案)

2012年美赛B题

题目翻译:

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

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

沿着大朗河露营

摘要

我们开发了一个模型来安排沿大河的行程。我们的目标是为了优化乘船旅行的时间,从而使6个月的旅游旺季出游人数最大化。

我们模拟团体从营地到营地旅行的过程。根据给定的约束条件,我们的算法输出了每组沿河旅行最佳的日程安排。通过研究算法的长期反应,我们可以计算出旅行的最大数量,我们定义为河流的承载能力。

我们的算法适应于科罗多拉大峡谷的个案分析,该问题的性质与大长河问题有许多共同之处。

最后,我们考察当改变推进方法,旅程时间分布,河上的露营地数量时承载能力的变化的敏感性。

我们解决了使沿大朗河出游人数最大化的休闲旅行计划。从首次启动到最终结束(225英里),参与者需使用桨供电的橡胶筏或机动船在指定的参与者露营地游玩6到18个晚上。为了确保一个真实的荒野体验,一组在同一时间最多占据一个营地。这个约束限制了公园的6个月的旅游旺季期间可能的旅行数量。

我们模拟情景,然后把我们相似特性的研究结果进行比较,从而验证了我们的方法是否能得到令人满意的结果。

我们的模型是适用于针对有着不同长度的河流、不同数量的露营地、不同的行程持续时间、以及不同的船的速度的情况中,找到最佳的行程安排。

问题重述

•应该如何制定不同长度和推进过程的旅行计划,使其在6个月的旅行季中旅行可能数量最大化?

•在任何时候,有多少新的组可以开始河上旅行?

•什么是河流的承载能力——在六个月的旅行季中可以发送顺流而下的最大数量的组?

模型概述

我们设计了一个模型,

•可以应用到具有相似属性的真实世界的河流(即,大峡谷);

•足够灵活,以模拟各种可行的输入参数;

•模拟河往返调度的关于旅行分布长度(无论是6,12,或18天)的推进,不同的分布速度和不同数量的露营地的函数。

该模型可以预测出这6个月的旅行季的旅游人数。它还回答有关河流的承载能力,有利的推进速度和行程长度的分布,每一天可以有多少组开始河流之旅,以及如何安排行程。

约束条件

问题指定了以下限制:

•旅行在始发点开始并在终点结束,225公里的下游。

•只有两种船:桨供电的橡胶筏和电机化船。

•桨供电的橡皮筏平均每小时旅行4英里。

•电动船平均每小时旅行8英里。

•旅行时间范围是6至18晚。

•旅行安排在一年的6个月期间。

•露营地沿河均匀分布。

•没有两个组可以同时占据相同的营地。

问题假设

•我们可以规定每天能到河上航行的桨供电河筏和机帆船的比例。

如果有太多的桨动力船在短时间内出行,有可能会出现问题。

•桨供电筏一趟的时间是12天或18天,机动船的为6天或12天。

这种简化使得我们的模型产生有意义的结果。同时,让我们比较不同的行程长度的效果。

•每个营地每晚只能有一组。这符合河川管理者的要求。

•每一天,一组只能向下游移动,或留在其目前的营地——不能向上游航行。这将流动组限制在了一个单一的方向上,从而极大地简化了我们该如何移动营地与营地间的组。

•旅行组从上午8时至下午6时,每天最多只能航行9小时(减去一个小时休息/午餐/等)。这意味着,每一天,桨动力筏旅行最多航行36英里,机动船最多72英里。这种假设使我们可以确定哪些组可以合理地达到某一的营地。

桨动力阀最多36英里每•旅行团每天的航行里程不能超过他们合理的旅行距离:天,机动阀72英里每天。

•我们忽略可能影响最大出行距离的变量,如天气和河流条件。没有办法将这些变量精确地包括在模型中。 •露营营地之间的距离均匀分布,这样营地间的距离就等于河流的长度除以营地的数量。因此,我们可以将河流表示为一个等距离分布露营地的数列。

•A组必须在其行程的最后一天到达终点的河流:A组即使可以,也不会提前离开河流。A组不会超出计划的旅行时间。我们相信这个假设符合河流管理者以及旅行质量的标准。

模型建立

我们定义一些术语和短语:

开放的营地(open campsite):如果目前没有旅行团占用,营地是开放的:如果没有组被分配到,营地是开放的。

的移动到一个开放的营地(moving to an open campsite):对于一组营地是组,其移动到其他的开放营地,即,相当于组分配到新营地。。

由于旅游团只可以向下游移动,或留在他们目前的营地,我们有等待名单(waitlist):某天的等待名单是那些在河上但还没有开始当天的旅行团组成,此时他们在等待名单上的排名和他们到达营地c的能力将他们包含在能够到达营地c的所有组的集合单上的组以当前的营地初值为,这些组被视作有着最大的优先权。等待名,并且有着之为P=1的优先权知道他们从等待名单上移除,并到河上开始旅行。

离开河流(off the River):我们认为,河上第一个离开的营地是,它始终是一个开放的营地(因此,任何数量的组可以被分配给它。这符合任何数量的旅行团都可以在任何一天离开河流的理解。 最远的空营地(the Farthest Empty Campsite):我们的调度算法使用一个数组作为数据结构来表示河流,数组的每个元素作为一个营地。每天以找到在河上最远的开放营地c来开始该算法,然后生成一个集合当晚可能到达c的组。因此,

Gc = {gi | li + mi

≥ c},

其中•

•如果是该组的当前位置,限定了组是该小组可以在一天之内旅行的最大距离。

必须能够在一天之内到达营地ç。

,其中包含了所有在是有在河上以及等待名单上的组构成。

,那么我们可以移动到下一个最远的空营地——位于上流,并更接近于河流的起点。该算法总是从河流的末端向河流的始端运行。

•如果,则算法试图将具有最高优先级的组移动到营地C。

为止。此时,每个能在河上继续该调度算法一直执行到最远的空营地是航行的组被分配到一个营地,然后我们开始另一个算法来模拟第二天。

优先级:

一旦集合地。优先级已形成为特定的露营地Ç,算法必须决定哪个组移动到该营是一个衡量组落后或提前于计划的程度的量:

衡量多远的前面或后面的计划组gi是:

•••>1:<1:=1:组进度落后;

组提前;

组恰恰是按计划进行。

我们尽量用最高的优先级别将组移动到c。具体的例子,以及如何用优先级解决这些问题,在图1和图2中概述了。

优先顺序和其他注意事项:

我们的算法总是试图移动落后于计划最多的组,来以确保每组都能在河上扎营,

图1调度算法发现,最远的开放营地是营地6,组A,B,C可能达到。 B组具有最高优先级,所以我们移动B组到营地6。

图2由于调度算法的过程经过了营地6,它发现下一个最远开放式营地是营地5。该算法得出A组和C能到达营地5;由于PA> PC,A组搬到营地5。并且扎营的夜数就等于之前确定的旅行长度。然而,在某些情况下,它可能无法以最高的优先级将组移到最远的可用的开放营地。这种情况下,如果具有最高优先级的是提前与计划的(P<1)。我们提供以下规则处理组优先级:

•如果•如果是落后进度,即提前,即>1,那么移动到c——其最远可达的开放营地。

——

该组在河上已经度过的夜数乘<1,然后计算以每天计划行进的平均距离。如果结果是大于或等于(以英里为单位)的露营地c的位置,那么移动•不管可确保,,如果选择到c。这样做可以让不再提前于计划。

,除非。此功能,那么不移动的行程不会在其计划结束日期前结束。在图3中示出了一个组的优先级被忽略的情况。

调度仿真:

现在我们证明我们的模型可以用来安排河流上的旅行次数。

在下面的例子中,我们假设沿225英里的河流有50个露营地,我们设定每天河上有四个组。我们为

图3

最远的开放营地不在河上。该算法找到,组D可以移动到那里,但D组有,即组D计划在河上待12晚,但到目前为止,只待了11晚——所以D组仍然在河上,在营地171和224(含)之间。 我们引进的四个特定组做了一个25天的行程计划。我们选择了旺季中的一天,以证明我们的模型的时间稳定性。四组的特性如下:

••••

:::桨机机供动动电,,,=6;

=18;

=12;

=12。

案例:(大峡谷)

大峡谷是一个针对我们模型研究的理想情况,因为它和大朗河的许多特征相同。峡谷的主要河流长为226英里,它拥有235个露营地,它在一年里大约有六个月都开放。它可以让游客乘坐机动船或桨供电河筏分别最多航行12天或18天。

使用的大峡谷参数中,我们模拟了多次来测试我们的模型。我们改变每天在河上的组的数量,想要得出河流的承载量—— 图5

例如组推出的第25天时间表。

图6

在图5的基础上顺流而下的组的运动。组由不同的行程持续时间参数在不同的时间到达终点。

图7

每组行进过程的优先级值。由于算法为了保持组群按时进行,值收敛到P=1。

长达六个月的可能的最大旅行数量。主要的制约因素是,每趟必须持续组的计划旅程时间。在夏季,大峡谷一般会将新的六组置于水上[贾等人的水。2006 ],所以我们使用这个值为我们的第一次模拟。在每一次模拟中,我们使用同等数量的机帆船,桨动力筏,以及相等行程长度的分配。

我们的模型预测出成功离开河的组(已完成人数)的数量,以及超过他们预定的截止日期(逾期人数)的人的数量,以及没有离开候补名单的人的数量(候补名单上的总人数)。这些值随着我们改变分配到水上的新团队的数量而变化(团队/天)。

表2每组每天的模拟结果

仿真组/天

模拟

每组每天载

人数 数

完成人数

逾期人数

等待人数

表1表明了18个组中每天可分配到河上的最大人数。在过去的六个月中,乘船人数近3000人次。增加至18组/天以上,很可能导致迟到人次(我们的模拟结束时,一些团体仍然在河上)和长候补名单。在模拟1中,我们将1,080组分配到河中(6组/天×180天),但只有996组成功离开;其余的组在近这六个月时段的末期开始并且没有在此季度结束之前完成他们的行程。这些团体有对本公司业绩的影响可以忽略不计,因此我们忽略它们。

承载力的敏感性分析:

因此,通过寻找大

大朗河的管理者面临着和大峡谷的管理者都类似的任务。峡谷的最佳解决方案,我们也可以找到一个大朗河的最佳解决方案。然而,这个最佳的解决方案是基于两个关键假设:

1,每一天,我们把到大约相同数量的群体放到河里;

2,河大约每英里有一个营地。

我们可以对大峡谷做这些假设,因为这些假设对大峡谷来说是成立的,但我们不知道,如果他们是否对大朗河成立。

为了应对这些未知因素,我们创建了表3。其生成的值是通过把河上的营地数量Y以及动力阀与每天发行的机动船的比率R进行拟合得到的,然后将新增到河上的人数增至河水的最大承载力。

表三

河的承载力关于营地数量以及动力阀与机动船的比率的方程

表3中的峰值承载能力可以看成是一个三维的空间中的点,我们可以找到拟合度最高的曲面--(几乎)经过通过数据点。拟合度最好的曲面可以让我们设定河峰值承载能力M为插入值。基本上,它给出了M关于Y和R的函数,显示了M关于Y和/或R的敏感程度。图7该曲面的轮廓图。 图7 表3中的点的最高拟合度的曲面轮廓图

沿着垂直线的脊线的R = 1:1可以预测出,对于任何给定的Y在 100和300之间的值,当R = 1:1时河流会有一个最优值。不幸的是,这个最佳拟合曲面的公式很复杂,它在工作表3的数据之外并不能给出一个准确的推断;因此它并不是一个特别有用测量其它R值的峰值承载能力的工具。最好的预测峰值承载力的方法就是使用我们的调度算法。

承载能力R和D的敏感性分析:

我们已经得到了了M关于R和Y的函数,但我们仍然不知道M是怎样被河上不同群体的旅行时间(D)所影响的。例如,如果我们的计划是6天或12天的旅行,这将如何影响M?河流管理者想知道什么样关于不同的旅行时间和速度的结合将可能以最好的方式利用河流。

我们用我们的算法来试图回答这个问题。我们讲露营地的数量设置在200并且确定峰值承载力值的R和D。此仿真的结果如表4所示。

表4是为了解决怎样分配旅行时间和速度会得到最大承载能力的问题。例如:如果河流管理者目前在安排旅行时间

6,12,或18:容量可以通过增加R至接近1:1或通过降低D至更接近“6或12” 而增大。

12或18:降低D到接近“6或12”。

6或12:增加R至更接近4:1。

模型求解

河流管理者问多少次旅行可以被添加到大朗河的季节。不知道河流现在是如何被管理的细节,我们不能给出一个确切的答案。然而,通过把我们的模型用到大峡谷的一项研究中,我们发现结果可以外推到大朗河的背景下。特别地,大朗河的经理可以增加约(3000−x)组至漂流季节,其中X是当前旅次的数量、3000是我们的调度算法预测的容量。

此外,我们模拟了某些变量的相互关系;M,D,R,和Y。河流管理者可以参考我们的数据和表格,看他们如何能改变当前流D和Y,R值,以实现更大的大朗河承载能力。

我们还通过一个用优先级值来有序的将组群运送到下游的算法,解决了给移到大朗河下游的组群分配营地的问题。

局限性和误差分析:

承载能力估计过高:

我们的模型有几个局限性。它假定河的承载能力只受到的露营地数量,旅行时间,和运输方法的限制。我们将河流的承载力最大化,即使这意味着几乎每一个营地每晚都被占用了。这可能不是最理想的,可能导致河流堵塞或环境退化。因此,我们的模型可能高估了在很长一段时间内的旅行可能的最大数量。

环境问题:

我们大峡谷的案例研究的表明,我们的模型忽略了的变量。我们确信大峡谷可以为在六个月的时段内为3,,000个旅行提供足够的营地,正如我们的算法所预测得。然而,由于实际的数量约是1000次[贾等人。2006 ],错误可能是由于营地能力之外的因素导致的,比如环境因素。

忽视河流的速度:

另一个我们模型所忽略的变量是河流的速度。河流的速度随着河道的深度和坡度的增加,使得我们关于每天旅行的最大距离恒定的假设不可能。当河流经历洪流,河的速度加倍,所有的营地都会被水淹没。又一次,我们的模型结果没有反映这些问题。

参考文献

c.u.博尔德系应用数学 配合表面X-Y-Z数据点。/computing/Mathematica 。

贾,琳达,丽诺尔和洛里布林顿等,2006,科罗拉多河管理计划。:///grca/ parkmgmt /上传/ crmpif_。

国家公园服务,2008,大峡谷国家公园/grca/naturescience/。

2011大峡谷国家公园,2011营地名单。

http:///grca/parkmgmt/upload/。

沙利文史提夫,2011,大峡谷的河流统计2010日历年。

/grca/planyourvisit/upload/calendar_year_2010_river_。

维基百科2012年/wiki/river。

致大朗河经理的一封信

为了回答你的关于旅行调度和河承载能力的问题,我们写了这封信来告诉你我们的发现。

我们的主要成果是建立了一个调度算法。如果在大朗河中实现,它可以建议公园巡游者如何最好地调度不同长度和进度的旅行。最佳的计划将在六个月的旅行季节内尽可能地使旅行数量达到最大。

我们的算法比较灵活,需要各种不同的输入数据。这些包括营地的数量和可用性,并与各旅游团相关参数结合起来。给予必要的输入,我们可以输出每天的时间表。在本质上,我们的算法是通过使用从以前的河流的状态而实现的。计划包括河上每个营地组的分配,以及那些等待开始他们旅行的人。如果知道未来的等待名单,我们的算法可以提前几个月输出时间表,这样管理层就能安排出未来任一天营地的精确位置。

为你省掉了很多数学细节,让我们简单地说,我们的算法采用优先级系统。通过将那些落后于行程的人移至更远的营地并且阻碍那些先于行程的人,此算法让那些落后于行程的人优先。这样一来,它可以保证所有的旅行将会在旅客计划完成的时间内恰好完成。 但调度只有一部分是我们的算法可以做的。它也可以计算在6个月的季度内可能的旅行的最大数量。我们称它为河流的承载能力。如果我们发现我们低于承载能力,我们的算法可以告诉我们每天可以有多少组增加到水上。相反,如果我们遇到河流堵塞,我们可以决定每天要应该减少多少组来让水上工作恢复正常运行。

其中,我们的算法一个有趣的发现是动力阀与机动船的比率将怎样影响我们可以送到下游的旅行数量。当处理分布均匀的出行时间时(从6到18天),我们建议一个1:1的比例来最大化河流的承载能力。如果分布偏向较短的旅行时间,那么我们的模型预测预测出增加至4:1的比率将导致承载力增加。如果分布偏向相反的方式,即偏向更长的旅行时间,那么河流的承载能力将远不比前两种情况—所以这种情况是不被建议的。

我们的算法已经经过全面地测试,我们相信这是一个确定河流承载能力的有力工具——优化日常工作的安排,并确保人们在享受真正野外旅行的同时能够按计划完成旅行。

诚挚的

13955队,团队成员芯片杰克逊,卢卡斯,和特拉维斯彼得斯,和团队的顾问阿米兰。


更多推荐

旅行,营地,河流