美国数学建模“大长河”露营

摘要本文就沿着”大长河”露营问题进行探究,旨在解决如何使更多的游客加入漂流,即使目标函数最大化的问题。由于游客数量的增加，管理者应合理安排游客出行，最大限度的利用露营地，并且使船只尽少接触河面上其他船只，在考虑河面容纳量的条件下，解决游客出行问题。针对问题一，建立了动态规划模型。我们首先根据管理者的目的和旅客的要求对摩托船和橡皮筏的比例进行研究，得出比例8：2。其次，利用泊松分布和正态分布，建立整体规划模型，得到乘坐不同类型船只漂流天数和每天行程的概率，并对其进行归一化处理。接着，利用截面法，得出旅客个数与露营点个数成正比。最后，建立动态规划模型，利用matlab求解：露营点数，船数量，平均每天旅客数为。针对问题二，建立了排程 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 模型，得到每天的排程方案。首先对某一天的情况进行分析，得出这天出发的机动帆船和橡胶筏的数量分别为5艘和1艘，以及得出发船时刻表。这样就可以根据这天的情况来安排，依次循环，得到以后每天的方案。问题三要求我们对河流容纳量提出自己的建议，我们建立了河流容纳量模型。很容易得到河流最大容纳量是露营点的个数48.为了使模型更具说服力，我们对模型进行了验证。得出的结果认为是合理的。关键词：露营漂流整数规划模型排程方案模型容纳量模型动态规划模型目录TOC\o"1-3"\h\z\uHYPERLINK\l"_Toc347148238"一、问题重述PAGEREF_Toc347148238\h3HYPERLINK\l"_Toc347148239"二、问题分析PAGEREF_Toc347148239\h3HYPERLINK\l"_Toc347148240"三、符号说明PAGEREF_Toc347148240\h5HYPERLINK\l"_Toc347148241"四、模型假设PAGEREF_Toc347148241\h6HYPERLINK\l"_Toc347148242"五、模型的建立与求解PAGEREF_Toc347148242\h6HYPERLINK\l"_Toc347148243"六、模型验证PAGEREF_Toc347148243\h14HYPERLINK\l"_Toc347148244"七、模型评价PAGEREF_Toc347148244\h15HYPERLINK\l"_Toc347148245"八、模型改进PAGEREF_Toc347148245\h15问题重述随着生活水平的提高，人们更倾向于投入野外生活，亲近大自然。闻名遐迩的大长河以漂流而享誉世界各地，河流顺流而下，共225公里。可供旅客选择的船只有两种：一种为平均4英里/小时的以桨为动力的橡胶筏；另一种为平均8英里/小时的机动帆船。目前每年有六个月的旅行开放时间（一年内的其余部分的天气对于河流旅行来讲温度太低），共可以安排X次旅行，整个旅行河道上共均匀分布有Y处露营，从开始到结束经历6到18个夜晚。在此，我们提出以下两个问题：问题一：在露营地一定的条件下，选取不同的时间（单位为夜）以及推动方式（马达或桨），使得行驶的船只最少的接触到河面上的其他的船只，最大限度的利用露营地，也就是说，在长河的的漂流季节，最多能有多少乘船旅行加入？如何安排一个最优的混合旅行方案，提出最佳排程方案。问题二：对于河流的承载能力提出相关的意见，以及准备一页备忘录，向河流的管理者描述我们的主要发现。问题分析问题一在数学上属于动态规划问题，即在不同时间、不同的驱动方式下，安排一个最优的混合旅游方案，使得在一定时间段内最大限度的利用露营地是的每天增开尽量多的船只而接纳更多的旅行队，并且要使船只尽可能少接触到河上的其他船只。假设管理者只考虑船只的主动性，根据实际调查的情况来合理安排摩托船和橡胶筏的数量比，暂且忽略旅客对不同中船只喜欢与否的主观性。这样旅行队选择摩托船和橡胶筏的概率问题就化简成为求解所安排两种类型船只的比例。然而，为让旅行队享尽水面飘流的乐趣，必须将船只的主动权给予旅行队，即：在规定的时间范围内（8：00-18：00）搭乘一种船只，并完成漂流。乘坐不同类型船只的旅行队的旅行天数的平均值不同，但他们的旅行的天数都成泊松分布；不同旅行天数计划旅行路程的平均值也不同，但是每天的旅行路程服从正态分布。于是可以得到不同类型的旅行船只的天数和路程，可以由此计算出旅行船只在河面上相遇的概率。在我根据靠近优先的原则概率。根据题目，我们可以得到6个月内的总漂流船只和露营地的个数，先确定第一天的船只类型，进而计算出6个月中的每天的排成安排。问题二中，要对河流的承载能力提出建议，在问题一的基础上得出每天最多可以进行几次水上旅行，才能最大限度的利用露营地，从而进一步求出这六个月可以进行几次水上旅行，得出该河流的承载能力。实现河的承载能力最大化，对求出的河流承载能力进行分析，给出意见。思路流程图如下：预处理1、摩托船和橡皮筏的比例2、旅行天数的概率分布3、每天行进路程的概率分布4、截面法得到旅客数与露营点个数建立规划模型目标函数：旅客最大约束1、旅客找到露营地概率足够大2、旅客间相遇次数足够小3、露营地个数约束动态规划模型每一天根据前一天安排……第一天摩托船：4橡皮筏：2建立排程方案模型符号说明游客选择摩托船的概率游客选择橡皮艇的概率选择摩托船漂流所用的时间选择橡皮艇漂流所用的时间选择摩托船游玩k天的概率选择橡皮艇游玩k天的概率归一化处理后选择摩托船游玩k天的概率归一化处理后选择橡皮艇游玩k天的概率选择旅行时长为k天的平均概率选择旅行时长为k天的游客平均每天漂流的路程船的平均速度每天最多旅行长度k天旅行计划的游客每日旅行路程游客平均每天行程模型假设1.旅行队一旦选定一种交通工具在途中不能更改。2.认为船一旦行驶到终点即可被公园投入再使用。3.旅行队的数量足够。4.每一组旅行队的行驶时间为8：00-18：00，其他时间在露营地休息。5.不考虑外界因素给船带来的影响。6.假设在这六个月中的游客数量符合正态分布。模型的建立与求解我们假设游客选择游览的天数为天，已知河总长为225英里，橡胶筏的速度为4英里/每小时，机动帆船速度为8英里/每小时。则：机动帆船平均每天漂流的时间：（1）橡胶筏平均每天漂流的时间：（2）其中为船只完成整段旅行所停留的夜晚。夜晚个数为6至18个。因为河流的总长是225英里，乘客可以选择平均4英里/小时的橡胶筏或者平均为8英里/小时的机动帆船旅行。因此每位乘客的漂流时间为56.25小时或者28.125小时。考虑到整个旅行从开始到结束会经历6至18个夜晚，因此每天的漂流时间为1.5625----4.6875小时或者为3.125-----9.375小时，每天的漂流行程为12.5----37.5公里。据此可得不同类型漂流的船次如下表：表一不同漂流类型不同旅行天数下每天平均旅行时间天数6789101112131415161718胶筏9.487.06.35.65.14.74.343.73.53.33.1机动帆船4.743.53.12.82.52.32.221.81.81.71.5从表中可知，总共有26种不同的旅行方式，最多漂流时间为9.4小时，我们可以认为每日最长漂流时间为10小时。也就是说，每天的漂流时长不会超过10小时。5.1.1模型一的建立（1）机动帆船和橡胶筏比例的研究我们从两方面来考虑现实橡皮筏和机动帆船的比例。一是从河流的管理者角度，我们知道机动帆船的速度是橡胶筏的2倍，可以认为选择机动帆船的旅行队会更快的到达终点，管理者要允许更多的旅行队参加漂流，机动帆船应该更多一些。二是从旅行队的角度，河流全长225英里，是比较长的，旅行队的目的是为了游赏风景而不是为了划船，可以认为旅行队选择机动帆船的概率会更多一些。综合以上两点考虑，我们认为，旅行队选择机动帆船和橡胶筏的比例为8:2，也就是说，旅行队选择机动帆船的概率为80%，选择橡胶筏的概率为20%。即：旅行队露营天数的研究我们假设选择机动帆船和橡皮筏的旅行队每天行进6小时，这是符合实际情况的.那么，机动帆船所用的总时间：（小时）(3)选择机动帆船的旅行队平均需要的旅行时长：（天）（4）同理，橡皮筏的旅行队平均需要的旅行时长：（小时）(5)选择橡皮筏的旅行队平均需要的旅行时长：（天）(6)假设游客对旅游天数的选择服从泊松分布，即得到，选择不同类型漂流的旅行队的旅行天数的概率分布：选择机动帆船的旅行队旅行天数k的概率分布：(7)表二游客选择摩托船旅行k天的概率分布时长6789101112概率0.14620.10440.06530.03630.01810.00820.0034时长131415161718概率0.00130.00050.00010.00000.00000.0000选择橡胶筏的旅行队旅行天数k的概率分布：(8)表三游客选择橡胶筏旅行k天的概率分布（3）桨、马达和露营天数的关系首先对上一步求出的旅行队旅行天数k的概率分布进行归一化处理：(9)(10)就可以得到旅行队旅行选择时长的概率公式:(11)表四游客选择不同方式旅游k天的平均概率分布时长6789101112概率0.318360.237060.16040.10270.064780.041680.0276时长131415161718概率0.018460.013980.008540.004920.002760.0016（4）每日旅行路程的研究：假设旅行队可以自由选择每日旅行路程，并且这个路程符合正态分布规律。1、均值：旅行k天的游客每天的平均路程：（12）这里把总的路程看作1，以简化计算。2、方差：前面已经说明，每天一条船最长漂流时间小时旅行队每天旅行速度的平均值：(英里/小时)(13)那么旅行队每日旅行的最大路程：(14)根据概率论中的准则确定旅行路程的(15)得到(16)3、天旅行计划的游客每日旅行路程：上面得到了天旅行计划的游客每日平均旅行路程和路程的方差，我们认为，旅行队每日旅行的路程服从正态分布，这是符合实际情况的，因为刚开始的时候，旅行队由于好奇新鲜等原因，每日走的会相对较慢，路程较短；在旅行的中间时刻会相对较快，形成较长；在快结束的时候，也会相对较慢，行程较短。(17)其中代表在k天旅行计划中的第天，就表示天旅行计划之内第天的行程。4、游客平均每天行程：(18)（5）截面法模拟游客流在以上的平均化计算的铺垫下，把问题模拟成流体在管子中的流动，在流量最大的情况下计算单位时间里通过某一截面的流体体积即可得到最大流量。流体截面简化图 计算公式 六西格玛计算公式下载结构力学静力计算公式下载重复性计算公式下载六西格玛计算公式下载年假计算公式 为：(19)代入数据，得到：(20)从简化的式子可以得到旅行的旅行队数X是与露营点数Y成正比的，说明，露营点越多，允许旅行的旅行队就越多，这是符合实际情况的。动态规划模型的建立这条河长225英里，认为露营地的个数是符合实际情况的。下面以为例说明确定旅行队数和露营点数规划模型的建立过程。在第四步中，我们得到了旅行队每日的最长路程，于是得到游客每日平均通过的最多露营点数量:(21)假设游客会选择距离希望露营点最近的露营地露营，那么旅行对可以选择的通过的露营点的个数有15个，我们可以根据旅行队一天走过的路程来计算经过的每个露营点露营的概率，计算公式如下：(22)下表就是旅行队每日经过的每个露营点露营的概率：表五旅行队每日经过的每个露营点露营的概率123456780.03760.06580.07720.08640.0980.12570.14740.16891011121314150.13940.11760.09630.05840.02860.00730.0089每个露营点被占据的概率：(23)代入公式计算得到每个露营点被占据的概率的数据表如下：表六每个露营点被占据的概率30313233343536370.64560.64540.64480.64450.64430.64390.64360.643538394041424344450.64320.64290.64210.64140.64080.64010.63950.639246474849505152530.63860.63820.63760.63730.63680.63640.63570.6355545556575859600.63510.63470.63460.63420.63360.63330.6328特殊情况下，一队游客可以在时间t内找到一处空露营点的概率k近似于二项分布，其公式为：(24)变换导出：(25)由于是不确定的，得到的是与的关系式。在计算过程中，令，得到一组解，可以认为，的解是和这组解很相近的。表七旅行天数k=1时的近似解30313233343536377.347.146.986.766.546.366.185.9638394041424344455.745.685.465.365.145.024.864.746474849505152534.564.454.344.24.093.983.793.66545556575859603.63.523.463.373.293.223.163.行进中的碰撞次数1仍然以流体模型来计算碰撞次数。此时假定流体分为两层，上层为机动帆船层，下层为橡胶筏。两层密度分别为：(26)(27)每日平均行进路程(28)又(29)从第二步中我们可以得到(30)由以上三式可以得到(31)碰撞次数的计算(32)这得到的是碰撞次数与露营地个数的关系式，代入数据，得到与的关系如下表：表八碰撞次数C与露营地个数的对应关系30313233343536371.561.741.982.172.242.382.522.6438394041424344452.822.963.093.323。463.613.823.9646474849505152534.164.344.584.764.985.185.365.62545556575859605.946.266.486.767.027.267.62确定与的值确定和值的限定条件①碰撞次数小于3(33)②能够在5小时内找到一处空露营地(34)③露营地个数在30到60之间(35)④旅行队数为正整数(36)综上所述，规划模型为：5.1.2模型一的求解根据建立的模型，由遗传算法进行求解：首先设定若干组具体的船只调度时刻表；作河流承载能力的适值函数；将时刻表代入模型中，选择河流承载能力较大的可行解进行交叉，变换；重复进行数次后，所得的解应趋于稳定，此时变为所求的最优解；求解结果：河流的最大承载能力，对应露营点数。进一步得到露营点的间距英里，也是比较符合现实情况的。即河流的最大承载能力为1206只船，总共有48个露营点。5.2模型二的建立与求解排程方案模型：对于每一队游客，我们就可以依照他们可到达的露营点被占据概率的大小给出建议休息点的位置。在第一个模型中我们已经得到了在允许漂流的6个月内可以旅行的总的旅行队数和露营地的各个数，得到平均每天的旅行队数：由于第一天之前是没有旅行队在露营点的，所以第一天安排6个旅行队进行旅行，下面我们根据模型一给出出发的各个旅行队的类型：首先选择机动帆船的旅行队的个数：这里取;选择橡胶筏的旅行队个数：这里取；从上面可以看到，管理者平均每天需要安排5艘机动帆船和一艘橡胶筏。根据模型一得求解可知某一天发船的时刻表如下：发船时刻表时间机动帆船橡皮筏8：00：00-9：00AM2010：00：00-11：00AM1114：00：00-15：00PM1017：00：00-18：00PM10综上可知，我们已经得出了每天发船的时刻表，并求得河流在这6个月中最大的承载能力为1206艘船，每天总发船六艘，其中机动帆船5艘，橡胶筏1艘。5.3模型三的建立与求解河流的容纳量模型河流的容纳量是指一天中河流最多进行旅行的旅行队的个数。由于河流上的个数已经确定为48个，容易理解，当一天中的所有露营点都被占据时，河流的容纳量就已经达到了极限，即A=Y。模型验证模型二和模型三都是在模型一的基础上进行的，为了验证模型的正确性，我们对模型一进行检验。由于被占用的露营地个数是不会变得，这里只对进行检验。考虑到第一种特殊的极端情况，所有的旅行队都选择摩托船，并且都在和上度过6个晚上后到达终点，并且每天发船次数一样，成为典型的的相逐问题，这样，可以求得一个最大的旅行队的数量：(43)考虑到第二种特殊的极端情况，所有的旅行队都选择桨船，并且都在和上度过18个晚上后到达终点，同样每天发船次数一样，这样，可以求得一个最小的旅行队的数量：(44)我们发现，本模型得出的结果比最少情况的旅行队数量有很大的增加，同时比较接近最大的旅行队数量，主观认为是本模型得出的结果是合理的。下面的说明可以进一步验证本模型的正确性：在模型中我们给出摩托船和桨船的所占所有船的比例分别是：0.8和0.2.这里我们对上面的和进行简单的线性加权：（45）可以更直观发现，模型得出的结果是比较正确的。模型评价对于本文的数学模型，既有相应的优点也有一定的缺点。我们已经完成了两个主要问题，寻找出了我们认为相对较优的的排程方式，以及提出了我们对河流承载能力的意见。优点和缺点如下所示：7.1优点7.1.1兼顾管理者与旅行队的需要，对两种类型的船给出了一个合理的比例。7.1.2充分考虑到旅行队的实际需求，给予旅行队选择旅行天数以及每天行进路程的自由，使得旅行队可以享受更多的乐趣。7.1.3运用数形结合的思想，简单易懂，达到了多需要的效果。7.2缺点7.2.1模型假设时认为在六个月中每天前来漂流的旅行队是一样多的，与实际情况存在偏差。7.2.2没有明确给出每天的安排，只是给出一种确定方法。模型改进针对模型的缺点，我们给出模型改进的方向。题中所描述的河流是在全年比较热的六个月才开放旅游的，容易想象，在开放旅游的开始和结束这段期间，天气会比较冷，游客自然就偏少，所以游客在这六个月的分布我们不妨认为是中间高两边低的正态分布。正态分布：据此可得到的游客在每月份旅游的概率，将其归一化后作为旅客在每月旅游的真正概率，从而可以得到每月旅游的旅游队的个数。结合每月旅游的旅行队的个数，可用所建模型对每个月的旅行队做出更加符合实际的安排。九、模型的推广我们所建立的模型是一类典型的动态优化模型，广泛性极强，对管理者解决旅行队排程有很好的指导性作用，不仅如此，它对班轮调度、列车优化调度各类动态规划问题都会有很好的启发作用。十、参考文献[1]玛莉.数学实验与建模.北京：清华大学出版社，2012.[2]杨国兴，刘振武.列车优化调度的一种一种启发式算法[J].系统 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 理论。[3]邵立群.计算机模拟实现漂流调度的优化模型，硅谷，2012年04期。