沿着大长河.doc

沿着“大长河”露营摘要本文就沿着“大长河”露营问题进行探究，旨在解决如何使更多的游客进入河道风景区，即使目标函数最大化的问题。为了合理的安排游客的出行，解决游客能得到最大满意度问题的同时，还要考虑河道承载能力。由于游客的不断上升，我们必然要有一个合理的安排以使得游客尽兴的同时也不浪费露营地，使之达到双赢的局面。在模型建立之前，考虑到安全原因，游客在河上的浏览时间不宜过长，所以我们将漂流时间定为8小时，从8：0016：00。这是建模的关键。由于露营时间的限制，河流长度一定，出行方式一定，则可以求出两种出行方式每天航行路程和航行时间的范围及概率。在该模型一中，我们首先假定游客只能选择两种船中的其中一种，利用层次分析法解决在两船不相遇的情况下，使河流的载流量最大问题。此时求得，当两宿营地之间的距离英里时，能得使宿营地的利用率最大。又由于每个旅行者可以看做相互独立的，因此每天发出的船具有重复性，在使每两船不相遇的情况下，使露营地的利用率尽可能达到最高，在利用率尽量高的情况下，可得到每天发出的船只为20只。模型一虽然在游客数量很多时，可以使露营地的利用率达到很高，但是游客只能服从管理者的安排旅行，因此很难是游客满意。因此建立模型二，经分析得出该问属于多台服务器多个顾客的服务问题，服务器即露营地，因此假定为多服务台模型，把游客到来看作泊松分布，漂流者对营地的选择服从0-1分布。求得其分布函数，然后利用排队论知识建立多服务台系统，利用软件求出游客平均排队长与平均等待时间等数据，并通过表格表示出来。关键词：层次分析法、多服务台模型、排队论、0-1分布、 一、问题重述在一条长为225英里且顺流而下的河上，人们开始了他们的水上露营旅游。本次旅游可以选择两种不同的船只：一种为平均4英里/小时的以浆作为动力的橡胶筏；另一种为平均8英里/小时的机动帆船。目前，每年在六个月的旅游开放时段内(一年的其余部分的天气对于河流旅行来说太冷)，共可安排X次旅行。整个旅行河道上共有Y处露营地，露营地均匀的分布在整个河道，整个旅行从开始到结束会经历6至18个夜晚。所以，我们提出了两个问题。问题一：如何安排一个最优的混合旅行方案，在露营地一定的条件下，不同的时间(单位为夜)和推动方式(马达或浆)，最大限度的利用露营地，同时使得行驶的船只最少的接触到在河上其它的船只。问题二：对河流的承载能力提出相关的意见，以及向河流的管理者描述我们自己的主要发现。二、问题分析2.1对问题一的分析问题1在数学上属于一种优化问题，即在不同的时间、不同的推动方式(马达或浆)下，安排一个最优的混合旅行方案，使得最大限度的利用露营地，并且要使船只尽可能少的接触到河上其它的船只。本次论文我们采用了计算机模拟、蒙特卡洛法、整数规划、遗传算法等相关理论来建立与求解模型。首先，我们考虑一艘船在河上行驶的情况，明确如何选择船只以及确定船的速度，建立模型；其次，我们考虑的是任意两次旅行中两艘船只是否相遇的问题，建立模型；最后，运用计算机模拟的方法建立数学模型，考虑任意船只是否相遇的问题。在模型的求解过程中，遇到了一些问题以至于无法进行下去，所以我们建立了另一种模型（模型）进行求解。首先将问题简化成为各个不同因素，然后分别对不同的因素进行分析，最后将他们综合起来，建立模型并求解。2.2 对问题2的分析问题2中们是要对河流的承载能力提出建议，所以必须在问题1的基础上得出每天最多可以进行几次水上旅行，才能最大限度的利用露营地，从而进一步求出这六个月最多能够进行多少次水上次旅行，得出该河流的承载能力。实现河的承载能力最大化，既要考虑每天所发船次的最大化，又要考虑不合理船次的最小化，之后，对求出的河流承载能力进行分析，给出自己的意见。三、模型假设1、假设每位漂流者服从管理者的安排，每位漂流者的露营路线是确定的漂流者每天的航行时间与里程数是确定的。2、假设每位漂流者服从管理者的安排，每位漂流者的露营路线是确定的漂流者每天的航行时间与里程数是确定的。3、假设漂流者自始至终选择一种交通工具。4、假设漂流者登下船的时间不计，即登下船不耗费时间。 5、假设漂流者每天只进行一次漂流，漂流至露营地时即进行露营准备或休整。四、符号说明：载流量；：每个露营地之间的距离；：露营地数量；：第条船第天的位置；：第天时第条船的航行里程数；五、模型的建立与求解5.1 对模型一的建立与求解假定漂流者服从管理者的安排，按照固定的模式进行漂流，每位漂流者的露营路线是确定的，漂流者每天的航行时间与里程数是确定的,次一天的漂流者是第一天漂流者的跟随者，同一天出发的漂流者的露营地是连在一起的，在此种情况下计算河流的最大载流量。考虑到安全原因，游客在河上的浏览时间不宜过长，所以我们将漂流时间定为8小时，从8：0016：00。我们假设游客选择游览的时间单位为天，已知总河长为225英里，橡胶筏的速度为4英里/每小时，机动帆船速度为8英里/每小时。 则：机动帆船平均每天漂流的时间： 橡胶筏平均每天漂流的时间： 其中为船只完成整段旅行所停留的夜晚。夜晚个数为6至18个。因为河流的总长是225英里，乘客可以选择平均4英里/小时的的橡胶筏或者平均8英里/小时的机动帆船旅行。因此每位乘客的漂流时间为56.25小时或者28.125小时。考虑到整个旅行从开始到结束会经历6至18个夜晚，因此每天的漂流时间为1.56254.6875小时或者为3.1259.375小时，每天的漂流行程为12.537.5英里。橡皮筏的航行时间为为(中间取整),机动帆船的航行时间为（1）计算每天最少航行时间时，要露宿18个夜晚，最后一天即第19天不能露宿，取第19天白天航行最大距离为12.5英里，所以每天最少航行时间（2）计算每天最多航行时间时，要露宿六个夜晚，最后一天即第7天不能露宿，设第七天白天航行距离为最大距离，,解得，所以每天最多航行时间橡皮筏的航行时间的分布律：航行时间A345678相应概率P10.10.150.250.250.150.1里程数121620242832当选用机动帆船时，（1）计算每天最少航行时间时，要露宿18个夜晚，最后一天即第19天不能露宿，取第19天白天航行距离为12.5英里，所以每天最少航行时间（2）计算每天最多航行时间时，要露宿六个夜晚，最后一天即第7天不能露宿，设第七天白天航行距离为最大距离，,解得，所以每天最多航行时间机动帆船的航行时间的分布律：航行时间B1.522.533.544.5相应概率P20.050.10.20.30.20.10.05里程数12162024283236选择橡皮筏的航行出发的时间是8:00AM-13:00PM, 橡皮筏的航行整点出发。如果选择机动帆船航行的出发时间是8:00AM-14:30PM,机动帆船发船间隔为半小时。设航行时间，则 , 设出发时间为, , ， 为满足的出发时间, 为满足的出发时间在仅考虑单侧露营的情况下，假设每天发出的船只数为，那么 其中表示第只船的航行情况，即每天的航程记录。设每天的航行里程数为，第天第只船的位置 为第条船第天的位置， 的航行里程数第天时第条船的航行里程数： 若当天发出的船离出发点最远船只只与前一天发出的船离出发点最近的船只满足 即为两宿营地之间的距离，则能得使宿营地的利用率最好，以第二天为例若使得载流量最大，则：由此可得到载流量公式 载流量的大小主要取决于每个宿营地之间的距离。在假设每天发出的船只是在相邻的露营地露营时，假设露营的顺序是按照船只的编号安排的，编号大的离出发地最近，则当天发出的离出发地最远的船只与前一天发出的离出发地最近的船只如果相隔一个露营地之间的距离，则露营地的利用效率最高。假设，即每个露营地之间的距离。则共有的露营地数量是, 露营地数量，又船只须露营时，到达一个露营地如果有人已在此地露营，则须到下一个露营地。此时希望露营地之间的距离短些，在漂流时，露营地之间的距离长一些，这样就能避免两船相遇，英里，假设露营地利用率为95%，则，则每天发出的船只数为。以11天为例，得到的船只航行里程数如下表所示： 天数编号1234567891011剩余里程数12202020202020202020241924202020202020202020241736202020202020202020241548202020202020202020241351020202020202020202024116122020202020202020202497142020202020202020202478162020202020202020202459182020202020202020202431020202020202020202020241因为大长河两岸均有露营地，因此每天可以发20只船，按照这种模式运行，可通过计算得到露营地的入住率，如下图所示：5.2 对模型二的建立与求解模型一虽然在正常漂流者充足的情况下有很高的入住率，但是在这种安排下，很难使漂流者满意，因此对模型进行改进，在漂流者人数较少的情况下，漂流者可以随机的选择每天的航行里程数，以使得漂流者满意。另外在游客较多时，会造成漂流者排队的现象。为了保证漂流者能更自由的选择露营地，所以每天进入的人数应当尽量少，但是每天发放的船只较少的话，也会造成漂流者排队。因此该问属于多台服务器多个顾客的服务问题，服务器即露营地，一旦接受漂流者，在当天就不能为其他露营者服务，在大长河已经进入正常运营的情况下，假定为多服务台模型当漂流者到来的分布为泊松分布时，用表示两个相继到达的时间间隔，是一个随机变量，其分布函数。令，于是，分布密度为。这里表示单位时间内平均到达的顾客数，可以假定每天前来漂流的人数为50人。则表示相继顾客到达平均间隔时间。设露营地对一个漂流者的服务时间（即在忙期内相继离开露营地的两个漂流者的时间间隔）服从于0-1分布，当有一个游客到来时，其选择的航行里程数为 为偶数假设服从均匀分布， 第个露营地被占用的概率令对于第一个进入的源流者而言，对于第个漂流者而言，所以对于每一个露营地为其他漂流者服务的概率均为对第个露营地，服务率分布函数为其中表示平均服务率（即单位时间内被服务完的漂流者），可以知道且期望值为，表示平均一个顾客的服务时间。 设漂流者单个到达，相继到达时间间隔服从参数为的负指数分布，系统中每天最多有个露营地可以被接受是否选择入住，每个露营地是否接受漂流者相互独立，且服从参数为的负指数分布。当漂流者到达时，若有空闲的露营地则马上被漂流者选择是否入住，当所有的露营地被占满时，漂流者便排成一个队列等待，等待时间为无限。下面来讨论这个排队系统的平稳分布，注意到对个数为的多服务台系统，有 和记则当时，有故其中公式（19）和式（20）给出了在平衡条件下系统中顾客为的概率，当时，即系统中顾客数大于或等于服务台个数，这时再来的顾客必须等候，因此记上式也称为等待公式，它给出了漂流者到达系统时需要等待的概率。对多台服务器等待制排队系统，由已得到的平稳分布可得平均排队长为：或 记系统中正在接受服务的顾客的平均数为,显然也是正在忙的服务台的平均数，故说明平均在忙的服务台的个数不依赖与服务台个数,这是一个有趣的结果可得到平均队长为=平均排队长+正在接受服务的顾客平均数=对多服务系统，此式依然成立，即有,系统，其中， ，由多服务台等待制系统的有关公式，可得到（1） 整个售票处空闲的概率=0.0844（2） 平均排队长=1.703（人）平均队长= 37.46（人）（3）平均等待时间 平均逗留时间六、模型的评价与改进问题一中通过建立0-1规划模型以及利用约束条件通过来求解，比较全面。通过建立面包烘烤函数和组合容量利用率对方案性能进行评价，但这种模型比较模糊，不能精确地对烘烤面包进行有效组合。问题二中建立目标函数，通过第一问的18种组合进行优化选择，该模型若能与方差相结合会更好，同时存在程序麻烦，输入繁琐的缺点。第三问中面包先等待后烘烤模型具有快速求解，简单易懂，易建立的优点。但该模型不能对哪块面包先进行烘烤做出更强说服力证明，考虑的相关影响因素少，求解不全面。参考文献1韩中庚，数学建模方法及其应用第二版，北京：高等教育出版社，2009年。 2肖华勇，基于MATLAB和LINGO的数学实用教程第一版。西安：2009.3。3林秋红，整数规划在数学建模中的应用，大众科技,NO.5,34页，2010年。4张磊 毕靖 郭莲英，MATLAB实用教程第一版，北京：人民邮电出版社，2008年。附录当漂流天数为18天时： 天数编号123456789101112131415161718剩余里程数1212121212121212121212121212121212121924121212121212121212121212121212121217361212121212121212121212121212121212154812121212121212121212121212121212121351012121212121212121212121212121212121161212121212121212121212121212121212129当漂流天数为16天时： 天数编号 12345678910111213141516剩余里程数12141414141414141414141414141414132414141414141414141414141414141411361414141414141414141414141414149481414141414141414141414141414147510141414141414141414141414141414561214141414141414141414141414141437141414141414141414141414141414141当漂流天数为14天时： 天数编号1234567891011121314剩余里程数12161616161616161616161616161524161616161616161616161616161336161616161616161616161616161148161616161616161616161616169510161616161616161616161616167612161616161616161616161616165714161616161616161616161616163816161616161616161616161616161当漂流天数为13天时： 天数编号12345678910111213剩余里程数121818181818181818181818187241818181818181818181818185361818181818181818181818183481818181818181818181818181510181818181818181818181818-1612181818181818181818181818-3714181818181818181818181818-5816181818181818181818181818-7918181818181818181818181818-9当漂流天数为11天时：天数编号1234567891011剩余里程数1220202020202020202020232420202020202020202020213620202020202020202020194820202020202020202020175102020202020202020202015612202020202020202020201371420202020202020202020118162020202020202020202099182020202020202020202071020202020202020202020205当漂流天数为10天时： 天数编号12345678910剩余里程数12222222222222222222252422222222222222222223362222222222222222222148222222222222222222195102222222222222222221761222222222222222222215714222222222222222222138162222222222222222221191822222222222222222291020222222222222222222711222222222222222222225当漂流天数为9天时 天数编号123456789剩余里程数122424242424242424312424242424242424242936242424242424242427482424242424242424255102424242424242424236122424242424242424217142424242424242424198162424242424242424179182424242424242424151020242424242424242413112224242424242424241112242424242424242424-3当漂流天数为9天时： 天数编号123456789剩余里程数1226262626262626261524262626262626262613362626262626262626114826262626262626269510262626262626262676122626262626262626571426262626262626263816262626262626262619182626262626262626-110202626262626262626-311222626262626262626-512242626262626262626-713262626262626262626-9当漂流天数为8天时： 天数编号12345678剩余里程数122828282828282827242828282828282825362828