沿着大长河露营doc.docx
《沿着大长河露营doc.docx》由会员分享,可在线阅读,更多相关《沿着大长河露营doc.docx(64页珍藏版)》请在冰点文库上搜索。
![沿着大长河露营doc.docx](https://file1.bingdoc.com/fileroot1/2023-5/19/f5a64bba-8c6c-4986-be73-79961e8d0b42/f5a64bba-8c6c-4986-be73-79961e8d0b421.gif)
沿着大长河露营doc
2012高教社杯全国大学生数学建模竞赛
承诺书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮
件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问
题。
我们知道,抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺,严格遵守竞赛规则,以保证竞赛的公正、公平性。
如有违反竞赛规则的行为,我们将受到严肃处理。
我们参赛选择的题号是(从A/B/C/D中选择一项填写):
我们的参赛报名号为(如果赛区设置报名号的话):
所属学校(请填写完整的全名):
参赛队员(打印并签名):
1.
2.
3.
指导教师或指导教师组负责人(打印并签名):
日期:
2012年8月11日
赛区评阅编号(由赛区组委会评阅前进行编号):
2012高教社杯全国大学生数学建模竞赛
编号专用页
赛区评阅编号(由赛区组委会评阅前进行编号):
赛区评阅记录(可供赛区评阅时使用):
评
阅
人
评
分
备
注
全国统一编号(由赛区组委会送交全国前编号):
全国评阅编号(由全国组委会评阅前进行编号
沿着“大长河”露营.
摘要
最近几年来,户外露营的人越来越多,而水上旅游也成了当今一大热门。
由于游客的不断上升,则我们必然要有一个合理的安排使得游客尽兴的同时也不浪费露营地,这样才是双赢的局面。
在模型建立之前,我们提出了两个问题:
一、
安排一个最优的混合旅行方案,使得最大限度的利用露营地,并且要是船只尽可能少的接触到河上其它的船只;二、对河流的承载能力提出我们自己的建议,以及向河流管理者描述我们的主要发现。
在该模型中,首先,我们考虑的是一次旅行怎么选择两种船只,这样可以确
定船只的平均行驶速度,以及露营地是否被占用、两个露营地间漂流所需时间等
问题。
其次,我们考虑的是任意两次旅行中两艘船只是否相遇的问题。
最后,运
用计算机模拟的原理考虑任意船只是否相遇,模拟整个漂流过程。
对于第一个问
题,我们将问题进行简化,求解任意一艘船漂流的过程,建立了模型Ⅰ。
在模型
Ⅰ的基础上进行改进,对任意两艘船漂流的动态进行分析,建立模型Ⅱ。
在模型
Ⅱ的基础上,我们推广到了模拟任意多艘船的漂流过程,由此建立了模型Ⅲ。
由
于在求解模型Ⅲ的时候遇到一些问题,所以我们另外建立模型Ⅳ,将整个问题中
所要考虑的几个方面简化为几个因素,分别考虑各个因素,然后用蒙特卡洛法模
拟出选择不同种类的旅行总的航行时间、每天漂流时间所服从的近似的概率分
布,然后运用整数规划与遗传算法对模型进行求解,得出结果:
河流的最大承载
能力:
C1854;此时机动帆船每天发的船次:
Ma6;橡胶筏每天所发的船
次:
MA5;每天一共所发的船次:
M11。
关键词:
水上漂流、计算机模拟、蒙特卡洛法、整数规划、遗传算法
1
摘要1
一、问题重述3
二、问题分析3
三、模型假设4
四、定义与符号说明5
五、模型建立与求解7
5.1模型Ⅰ7
5.2模型Ⅱ8
5.3模型Ⅲ10
5.4模型Ⅳ11
(1)预定发船方案模型14
(2)船只在河上漂流总时间的模型14
(3)旅行每天的漂流时间的模拟15
(4)船只到达露营点的模拟16
(5)船只在露营地相遇的模拟17
(6)河流的承载能力的模拟18
六、模型评价与推广20
七、参考文献20
八、给河运管理人员的信21
2
一、问题重述
在一条长为225英里且顺流而下的河上,人们开始了他们的水上露营旅游。
本次旅游可以选择两种不同的船只:
一种为平均4英里/小时的以浆作为动力的
橡胶筏;另一种为平均8英里/小时的机动帆船。
目前,每年在六个月的旅游开放时段内(一年的其余部分的天气对于河流旅
行来说太冷),共可安排X次旅行。
整个旅行河道上共有Y处露营地,露营地均
匀的分布在整个河道,整个旅行从开始到结束会经历6至18个夜晚。
所以,我
们提出了两个问题。
问题一:
如何安排一个最优的混合旅行方案,在露营地一定的条件下,不同
的时间(单位为夜)和推动方式(马达或浆),最大限度的利用露营地,同时使得行驶的船只最少的接触到在河上其它的船只。
问题二:
对河流的承载能力提出相关的意见,以及向河流的管理者描述我们自己的主要发现。
二、问题分析
2.1问题1的分析:
问题1在数学上属于一种优化问题,即在不同的时间、不同的推动方式(马
达或浆)下,安排一个最优的混合旅行方案,使得最大限度的利用露营地,并且要使船只尽可能少的接触到河上其它的船只。
本次论文我们采用了计算机模拟、蒙特卡洛法、整数规划、遗传算法等相关理论来建立与求解模型。
首先,我们考虑一艘船在河上行驶的情况,明确如何选择船只以及确定船的速度,建立模型Ⅰ;其次,我们考虑的是任意两次旅行中两艘船只是否相遇的问题,建立模型Ⅱ;最后,运用计算机模拟的方法建立数学模型Ⅲ,考虑任意船只是否相遇的问题。
在模型Ⅲ的求解过程中,遇到了一些问题以至于无法进行下去,所以我们建立了另一种模型(模型Ⅳ)进行求解。
首先将问题简化成为各个不同因素,然后分别对不同的因素进行分析,最后将他们综合起来,建立模型并求解。
2.2问题2的分析:
问题2中们是要对河流的承载能力提出建议,所以必须在问题1的基础上得出每天最多可以进行几次水上旅行,才能最大限度的利用露营地,从而进一步求
3
出这六个月最多能够进行多少次水上次旅行,得出该河流的承载能力。
实现河的承载能力最大化,既要考虑每天所发船次的最大化,又要考虑不合理船次的最小化,之后,对求出的河流承载能力进行分析,给出自己的意见。
三、模型假设
3.1模型假设
1每艘船行驶过程中不考虑换船的问题。
2每艘船一天只停靠一个露营地,两个露营者不能在同一时间内占据同一个露营地。
3假设在这六个月中的游客数量认为是服从正态分布。
4考虑到漂流带来的身体疲劳,所以我们假设一天行驶时间为8:
00—16:
00,其余时间为休息时间。
5不考虑外界自然因素给船带来的影响。
注:
月份的正态分布参数
为了便于计算,我们不妨设每个月为30天,共有180天,题中所描述的河流是在全年比较热的六个月才开放旅游的,容易想象,在开放旅游的开始和结束这段期间,天气会较冷,游客自然就偏少,所以游客在这六个月的分布我们不妨认为是中间高两边低的正态分布的。
1
(x)2
e2
2
正态分布:
fx
2
据此可得到的游客在每月份旅游的概率,将其归一化后作为游客在每月份旅游的真正概率。
所以我们选定旅游的月份为3月到9月,每月30天,总共180天。
3.2模型前提
考虑到游客在河上的浏览时间不宜过长,所以我们将漂流时间定为8小时,
从8:
00—16:
00。
我们假设游客选择游览的天数为天,已知总河长为225英里,橡胶筏的速度
为4英里/每小时,机动帆船速度为8英里/每小时。
则:
机动帆船平均每天漂流的时间:
225
t1(3.1)
8t
橡胶筏平均每天漂流的时间:
225
t2(3.2)
4t
其中t为船只完成整段旅行所停留的夜晚。
夜晚个数为6至18个。
据此可得不同类型漂流的船次如下表:
4
表3—1不同类型漂流的船次
夜
6
7
8
9
10
11
12
13
14
15
16
17
18
橡
胶
9.4
8
7.03
6.3
5.63
5.11
4.7
4.3
4
3.75
3.5
3.3
3.13
筏
机
动
4.7
4
3.52
3.1
2.81
2.56
2.3
2.2
2
1.88
1.8
1.7
1.56
帆
船
从表中可知,总共有26种不同的旅行方式,但由于我们假设最多漂流时间为8个小时,所以橡胶筏用六夜完成整个旅游几乎不可能,则将其排除。
所以我们可以看到,共有25种不同的旅行方式。
四、定义与符号说明
符号
定义
单位
vi
第i次旅行的速度
英里/小
时
pi
第i次选择推动方式(马达或浆)的变量(0或1)
—
qi,j
选择露营地是否被占的变量(
0或1)
—
S
河的长度
英里
d
两露营地之间的平均距离
英里
Y
露营地的数量
个
X
安排的旅行次数
次
ti,j
第i次旅行从出发到第j个露营地的时间
小时
Tj
随机在营地停留是时间
小时
5
x
y
Y
t0
T0
ty
TY
M
Ma
b
B
dxy
DxY
j
xykj
xYkj
pxykj
pxYkj
在六个月开放期间的中第
x天(x
180
)
—
一天中的第y班机动帆船
—
一天中的第Y班橡皮筏
—
每天的首班机动帆船出发时间
小时
每天的首班橡皮筏出发时间
小时
第j班摩托艇距离上一艘的发船间距(
t1
0)
英里
第j班橡皮筏距离上一艘的发船间距(
T1
0)
英里
每天一共所发的船次
—
机动帆船每天发的船次
—
机动帆船每天的的行驶时间
小时
橡皮筏每天的的行驶时间
小时
第x天时第y班摩托艇的漂流的天数
天
第x天时第Y班橡皮筏的漂流的天数
天
第j个露营地
—
第x天时第y班摩托艇在其航行的第
k天到达第j个露营地
—
这一事件
第x天时第Y班橡皮筏在其航行的第
k天到达第j个露营地
—
这一事件
第x天时第y班摩托艇在其航行的第
k天到达第j个露营地
—
的概率
第x天时第Y班摩托艇在其航行的第
k天到达第j个露营地
—
的概率
6
五、模型建立与求解
在我们建模之前,我们必须对旅游方针制定一些原则:
原则1:
两个露营者不能在同一时间内占据同一个露营地。
原则2:
由于气候原因,这六个月在开头和末尾会比较冷,游客的数量显然是比较少的,这点可以从模型中体现出来。
原则3:
在旅游人数达到最大的时候,我们要尽可能的降低游客在河中的碰面率。
5.1模型Ⅰ:
一次旅行漂流过程
为了简化整个复杂混合的旅行方式,我们必须分析每一次旅行的状态与时间的关联。
在这个模型里,从开始的下水点到最终结束点,共225英里,且是顺流而下的,是单向的行驶。
所以我们首先关注一次旅行。
在这一次单种工具的旅行的模型中,模型需要明确表明之前状态与之后状态的关联。
这里的状态是指:
第i次旅行的船到达第j个露营点的时候,船只能否在这个露营地露营休息。
在一次的旅行中我们只能选择一种船只,选择橡胶筏(vi
4英里/小时)或
机动帆船(vi
8英里/小时)。
由此,我们可以得到以下等式:
vi4pi8(1pi)
(i=1,2,3,,,X)
(5.1)
其中v
是指第
i
次旅行的速度,p
是指第
i
次选择推动方式
(
马达或浆的变
i
i
)
量(0或1)。
这里vi
由pi决定,当pi=0时,则vi等于8英里/小时,可以知道这次旅行所使用
的船只为机动帆船。
而当pi=1时,vi等于4
英里/小时,则此次旅行选用的船只
为橡胶筏。
等式
(1)表示这第i次的旅行所选用的推动方式。
这一次的旅行不仅与它的推动方式有关,而且与它到达某一露营地是否被
占而选择露宿与否有关。
于是我们引入一个变量qi,j,来表示露营地是否已被占
领,等式如下:
1
第j个露营地还没被占
qi,j
(5.2)
0
第j个露营地已被占领
其中qi,j表示选择露营地是否被占领的变量,i=1,2,3,,,X;j=1,2,3,,,
7
Y。
由于露营者不能在同一时间内占据同一个露营地,所以当这个露营地被前一只船只占领,后一只到的船只则会穿过该露营地,向下一个露营地前进。
我们知道整个旅行河道上共有Y处露营地,露营地均匀的分布在整个河道。
我们设两个相邻的露营地之间的相距d英里,如此我们就可以得到关于d与Y之间的关系式:
S
(5.3)
d
1
Y
这里S为整条河流的长度,并知道S=225英里。
另外,一次旅行的时间不是无限的,规定整个旅行从开始到结束会经历
6至
18个夜晚。
所以我们设定第
i次旅行从出发到终点所经历的时间为
ti(单位:
小
时),我们得到以下不等式:
144ti
432
(5.4)
我们由上面式子(5.1),(5.2),(5.3)得到以下式子:
ti,jti,j1
d
Tj1
(i1,2,3,,X;j1,2,3,
Y)
(5.5)
qi,j1
vi
其中ti,j表示第i次的旅行船只到达第j个露营点的时间;ti,j1表示该船只到达第
j-1
个的露营点的时间;
d船只在两露营地移动所花费的时间;Tj1为船只在第
vi
j-1
个露营地所停留的时间。
第
j-1个露营地所停留是时间Tj1为随机数,我们通
过计算机得到。
我们把单次旅行的看作是动态的而且与之前船只的旅行状况有关。
5.2模型Ⅱ:
两艘船在河中相遇的动态分析
我们为了更好更多的利用各个露营地,因此,我们应该尽可能多的安排旅行总次数X,让游客最少的接触到在河上其它的船只。
我们可以先将模型简化,设定为两艘船在河上行驶。
相遇是指在某一时间两艘船只在同一地点。
这样,我们将它们细化到在两相
邻露营地的中间河域上相遇,即在两艘船只在第j个露营点与第j+1个露营地之
间相遇。
我们通过函数来明确的表示这一过程所带来的相关的时间与地点,以及
它们的关系。
下图表示两船只在这中间河域相遇的发生图:
8
d
第j个露营地第(j+1)个露营地
第i次旅行
第k次旅行
出发地相遇地
图5—1两船在河上相遇的发生图
如图5—1中所示,我们假设第i次旅行先经过这第j点时间为ti,j,而后,经过
时间(tk,jti,j)后第k次旅行经过j点。
接着经过时间t小时后,第i旅行跟第
k次旅行的船只相遇。
因此,我们可以联系上下得到以下式子:
Sj(t)vktvi(tk,j
ti,j
t)
k,i
1,2,
X;j
1,2,Y.
(5.6)
其中k
i。
这两次旅游的船只是否停靠第
j
或第j+1个露营地与他们经过露营地时露营
地是否被占有关,于是我们假设得到以下式子:
qi,j
qk,j
1
(k,i
1,2,X;k
i;j
1,2,
Y)
(5.7)
0
其中qi,j
表示第i次旅行到达第j
个露营地时露营地是否被占领的变量;
qk,j
表示第k次旅行到达第j个露营地时露营地是否被占领的变量。
我们根据以上式子(5.6),(5.7),我们假设不同的情况,分成以下三种,来考虑两船只相遇的情况:
情况一:
Sj(t)
0
假设:
(5.8)
qi,jqk,j
1
9
这种假设里,当Sj(t)=0时,则两船相遇,而两只船都未占领这j点露营,即是
这第j个露营地并没有被他们任意一只船停靠。
因此,当这两只船都并未在这个露营地停留,所以当Sj(t)=0时,经过时间t小时后,他们在两露营地之间的这
段河域上相遇了。
情况二:
Sj(t)
0
(5.9)
假设:
0
qi,jqk,j
在这个假设中,qi,j
qk,j0则得到他们其中一组在这个
j露营地停留过。
所以,
我们就可以知道他们其中一只旅行船只在这个露营地停止宿营,
而另一只继续前
进。
所以,他们不会在这两个宿营地之间相遇。
情况三:
Sj(t)0Sj(t)0
假设:
(5.10)
qi,jqk,j0qi,jqk,j1
当Sj(t)0,不管露营地是否被占领,他们都不会在同一时间在同一地点相遇,所以这种假设两艘船都不会相遇。
5.3模型Ⅲ:
多次旅游的漂流过程
5.3.1计算机模拟
计算机模拟是一种用来帮助人们在不确定的条件下进行决策的方法。
人们在完全不了解事件的发生及其影响如何的条件下,从若干方案中选出一种行动方案来。
计算机模拟可以反复进行,改变系统的结构和系数都比较容易。
在实际问题中,面对一些带随机因素的复杂系统,用分析方法建模常常需要作许多简化假设,与面临的实际问题可能相差甚远,以致解答根本无法应用。
这时,计算机模拟几乎成为唯一的选择。
5.3.2整个漂流过程的模拟
由模型Ⅰ和模型Ⅱ可知,当我们只进行一次旅游的时候,我们并不需要考虑露营地是否已经被占领的问题,船只可以停在每一个露营地;当我们考虑两次旅游的时候,我们就要考虑两艘船的距离间隔,以至于推断出它们是否会相遇、露营地怎么安排的问题;当我们考虑整个漂流过程的时候,船与船之间的相遇问题就是我们重点要解决的问题,同时还有它们的碰面率。
所以,为了确定典型的旅游行程,如漂流艇的类型、露营地、时间间隔等,
我们需要做一系列的轨道运行的实际流程图,一个重要的流程图如图2所示:
经过几次的模拟,获得最优的X(露营旅游次数)、最小的E(遇到的次数)
以及最小的TP(旅行时间)。
另一个重要流程图如图3所示:
由于在建立该模型的时候,我们还没有考虑到一些实际的问题以及程序上遇
10
到一些问题,知识还不够全面,所以我们建立了另外一种模型来寻求解答,即是模型Ⅳ。
5.4模型Ⅳ:
将整个问题中所要考虑的几个方面简化为以下几个因素
(1)发船方案(发船的时刻表);
(2)船只在河上漂流的总时间;
(3)船只每天的漂流时间;
(4)单次旅行到达露营点的概率;
(5)多次旅行在露营点的相遇的概率;
(6)河流的承载能力;
各个因素之间的相互影响如下:
图5—2各个因素之间的影响关系
11
开始
设定初始值Y,N.
其中令X0,
同时用零矩阵L进行记录旅行
把整条河分成N个部分
pirand,v4pi8(1
pi)
S
在每两个露营地之间的
Y1
移动时间为t1
v
在每个部分游玩时间为
t2,同时假设有n次旅行
i
1
通过旅行路线来数出
每次旅行相遇数
E,
N
i
n
露营数
X
,和旅行
的时间
TP
Y
模拟单次旅行,进入图4
得出X,E,TP
N
能完成旅行吗?
Y
END
XX1
记录每次旅行路线
12
图53轨道运行的实际流程图
给每个部分进行标号j1
jN
能完成整个路线
Y
得到离开时间t3
N
t3是白天时间吗?
Y
t38:
00下个早上
记录到达时间t4
N
t是白天时间吗?
Y
t8:
00下个早上
4
到达了那个部分
N
有露营地吗?
不能完成整个线路
Y
计算出相遇数E
N
EK?
进入图三流程图
Y
jj1
离开时间到达时间玩的时间
图5—4轨道运行的实际流程图
13
5.4.1模型的建立
(1)预定发船方案模型如下:
我们最终的目的是建立这样的一个每天发船的时刻表来调度船只:
表5—1每天发船的时刻表
首班船发船时间t1
第二班船发船时间t2
第三班船发船时间t3
第四班船发船时间t4
,,,,,
末班船发船时间tn
(2)船只在河上漂流总时间的模型如下:
考虑橡皮筏为人力驱动,机动帆船为机械驱动他们在速度方面存在差异,必然会导致船只在河上漂流时间的长短不一,同时公园管理方面的调度方式对船只在河上漂流总时间也有一定影响。
我们知道整个旅行河道上共有
Y处露营地,露营地均匀的分布在整个河道。
我们设两个相邻的露营地之间的相距
d英里,如此我们就可以得到关于
d与Y
之间的关系式,公式(5.3):
d
S
Y1