2014国赛集训专题6蒙特卡洛方法及排队论

计量数模提高班专题五2014数学建模集训专题五蒙特卡罗模拟方法与排队论模型柴中林2014/7/14计量数模提高班专题五本专题提纲一引言二蒙特卡罗仿真原理介绍三蒙特卡罗仿真例子与分析四排队论简介五排队论研究方法六作业计量数模提高班专题五数学建模的解有两类•精确解•近似解当然，对解的近似程度以及求解过程的复杂程度做一定的探讨对建模来讲是有益的。求解问题，总希望得到精确解。但很多情况下，精确解是求不出或者难以求出的。在此情况下，求得问题的近似解就成了必然的选择。此外，从应用的角度讲，一定程度的近似解就够了。一引言计量数模提高班专题五排队论是重要的一类随机模型(现象)，而蒙特卡罗方法则是基于随机理论的一种重要的仿真模拟方法，它们都与不确定性现象相关联。自然现象有两类•确定性现象•不确定性现象•随机现象•模糊现象在一定条件下必然发生的现象计量数模提高班专题五2、能用蒙特卡罗方法编程求解问题；1、了解蒙特卡罗方法的原理和适用范围；3、了解排队问题的特点、基本类型和理论；4、能对简单的排队问题编程计算。本专题的学习目的计量数模提高班专题五二蒙特卡罗仿真原理介绍蒙特卡罗(MonteCarlo，美国一赌城的名称)方法又称统计模拟法、随机抽样技术，是一种以概率论和统计方法为基础的基于随机模拟的数值计算方法。它将所求解的问题同一定的概率模型相联系，用计算机和它产生的随机数实现统计模拟或抽样，再根据统计理论获得问题的近似解。计量数模提高班专题五蒙特卡罗方法的概率论依据：1设A是一随机事件，P(A)是A发生的概率，fn(A)是n次试验中A发生的频率，则当n很大时有：P(A)≈fn(A)。2设X是一随机变量（总体）,E(X)=μ,D(X)=σ2分别是X的期望和方差，X1,X2,…Xn,是来自X的一个样本，则分别是μ和σ2的有效估计。3上述式子不仅可以求概率等的近似值，也可以估计参数。如μ（λ）中含参数λ，根据μ的估计式的求解就可得到λ的近似值。4蒙特卡罗方法的精髓或妙处在于设计合理的概率模型，以便用模拟的方法求解问题。niiXXn122)(11ˆniiXXn11ˆ模拟得到模拟得到计量数模提高班专题五（伪）随机数的产生rand产生一个服从U(0,1)分布的随机数rand(m,n)产生mn个服从U(0,1)分布的随机数exprnd(λ)产生一个服从e(λ)分布的随机数poissrnd(λ)产生一个服从P(λ)分布的随机数binornd(n,p)产生一个服从B(n,p)分布的随机数normrnd(μ,σ)产生一个服从N(μ,σ2)分布的随机数unifrnd(a,b)产生一个服从U(a,b)分布的随机数其他一些随机变量的随机数可利用U(0,1)分布等通过适当数学方法得到计量数模提高班专题五仿真与模拟的目的和原理•仿真和模拟可以说是针对同一内容的不同角度的看法描述，当需要对某一问题观察研究而相应的观察和实验时间和成本花费太高时，可以考虑用一个模型代替原型，用模型的研究达到原型的研究的目的（以节约时间和成本），这就是仿真，其在计算机上等的实现过程也称为模拟。计量数模提高班专题五例1：中子穿过原子反应堆屏障问题模拟原子反应堆外的铅屏障是用来屏障堆中逸出的中子的，以免造成危害。一般的，可做以下简单假设：每个进入屏障的中子在撞到铅原子前行进的距离为D，然后这个中子以随机方向弹回来，并且在它的下一次撞击中又行进距离D。假设屏障厚度为3D，每一个中子能经受10次撞击，问进入的中子能以多大的比例穿透铅屏障？三仿真例子与分析反应堆铅屏障运动的中子计量数模提高班专题五分析：该问题显然难以用概率论解决，用蒙特卡罗方法却很容易。为方便，将屏障内外径看作直线段，并做进一步假设：1中子反弹回反应堆后认为不能穿过屏障。2与铅原子相撞后任意方向等可能反弹。3中子撞击十次后必毁灭。画图如右，模拟流程图如下屏障x轴y轴中子外半径内半径计量数模提高班专题五中子撞击铅屏模拟流程图初始化系统状态产生一个新中子的初试方向和运行终点中子回到反应堆了吗求频率,结束YN碰撞，产生新方向和运行终点模拟次数到了吗NY中子出了铅屏了吗碰撞次数到了吗N频数增加YYN对复杂对象的编程，画一个流程图是很有帮助的计量数模提高班专题五中子问题程序•n=10000;%simulationnumber•m=0;%frequency;Further,Disdeemedtobe1•fori=1:n•theta=unifrnd(-pi/2,pi/2);%initinalangle•x=cos(theta);%onlyxneedstobeconsidered•forj=1:10•theta=2*pi*rand;%newangleafterahitting•x=x+cos(theta);%newdistanceisadded•ifx0%theneutronreturnstothepile•break;•end•ifx3%theneutronpassesthroughthebarrier•m=m+1;%madds1•break;•end•end•end•fn=m/n%frequency计量数模提高班专题五例2：计算定积分•分析：这个积分应该有精确解，因为原函数的缘故这个积分不易求得，故求一个近似解是必然的选择。可以用其他方法求近似解，这里用蒙特卡罗方法。用蒙特卡罗方法离不开随机变量。当问题本身具有随机性时，随机变量的选取与这个随机问题应当一致（如上例）；而当问题本身不具有随机性时（本例），就要引入随机变量，将确定性问题转化为不确定问题，以求得问题的解。dxxI)exp(302计量数模提高班专题五•根据积分区域，引入随机变量X∽U(0,3),记其密度函数为φ(x)(=1/3)，又记f(x)=exp(-x2),且在[0,3]上记Y=F(X)=f(X)/φ(X)=3exp(-X2)，则模拟结果为0.8704,软件算得结果为0.8862.YYEXFEdxxxFdxxxxfdxxfI)())(()()()()()()(303030计算重积分原理相同，且更有价值计量数模提高班专题五例3赶火车一列火车大约在下午1点离开A站，其规律如下：离站时间13：0013：0513：00概率0.70.20.1火车从A站到B站所需时间服从正态分布，平均30分钟，标准差2分钟。如果你要赶的是这趟火车的下一站B，而你到达的时间分布为时间13：2813：3013：3213：34概率0.30.40.20.1问你能赶上这列火车的概率是多少？计量数模提高班专题五•问题分析：解决实际问题，需要将问题符号化和数学化。这个转化有的很明显，较容易；有的则不然，需要一定的技巧.转化的原则是模型和问题在本质上等价。当转化有多种方式时，我们选最简单的一种。计量数模提高班专题五•对于问题，赶上火车的可能性就是概率。显然，对问题来说所求概率一定存在，但却不易求得。从应用上讲，知道概率的近似值就够了，这就用上频率。我们的做法相当于仿真：假想这个人按题设条件不断的赶往开到B站的火车，计算他赶上的频率。•但对于火车在1点离开A站的概率是0.7该怎么处理？我们给一个最简单的随机变量：X~U(0,1)，则P(0X0.7)=0.7。这样，我们产生一个服从U(0,1)分布的随机数X，若它满足0X0.7，我们就认为火车在13：00离开A站。对于火车以0.2的概率13：05离开A站，虽然P(0X0.2)=0.2，但我们不能用，因为这会产生火车同时以13点和13：05离开的情形（两个事件相容），为此，我们用P(0.7X0.9)=0.2，对13：10离开，我们用P(0.9X)=0.1，其余类似。模拟见程序计量数模提高班专题五例4报童问题问题报童售报：a(零售价)b(购进价)c(退回价)售出一份赚a-b；退回一份赔b-c每天购进多少份可使收入最大？分析购进太多卖不完退回赔钱购进太少不够销售赚钱少应根据需求确定购进量.每天需求量是随机的优化问题的目标函数应是长期的日平均收入每天收入是随机的存在一个合适的购进量等于每天收入的期望计量数模提高班专题五设报纸每天需求量为r的概率为f(r),r=0,1,2,…，由数学建模知识可得最佳订购量n应满足0()d()dnnprrabbcprr然而，我们仍然难以应用，且不直观。鉴于报童问题的随机性特点，用仿真是非常有效的方法。为此，我们举一个具体例子，设a=0.5,b=0.3,c=0.15,且每天的报纸需求服从P(50)的分布，模拟见程序。由模拟可知每天宜订购51份报纸。其中p(r)为密度函数计量数模提高班专题五评注•蒙特卡罗方法适应于随机性问题，对于非随机性问题，必须将它转化为随机问题。蒙特卡罗方法的优点是程序结构简单，计算复杂性不随对象复杂度的增加而增加，缺点是近似解的精度不高，误差具有随机性，不易估计。蒙特卡罗方法应在其他方法难以求解的时去用；当然，还要求该方法此时适合用。计量数模提高班专题五四排队论简介•1到银行取钱，发现前面有几十个人在排着队，你掉头就走：不能忍受啊！怎么不多开几家银行、再增加几个服务窗口啊！假如你是工作人员，你觉得应根据什么来决定是否需要开设新的银行或增加新的服务窗口——要知道一次的排队人多会具有偶然性的！•2银行一般都有几个服务窗口，过去是顾客每个窗口分别排队等待服务，而现在几乎都改为叫号制，这相当于多个窗口只排一队。银行为什么要这么做?有什么好处？引例计量数模提高班专题五排队是我们日常生活中常见的现象，如：•上、下班搭乘公共汽车；•顾客到商店购买物品；•病人到医院看病；•学生去食堂就餐等出现的排队和等待服务现象。排队现象计量数模提高班专题五排队可以是有形的，也可以是无形的。如几个顾客打电话到出租车站要车，如果出租车站无足够车辆，则部分顾客只得在要车处等待，他们分散在不同地方，形成一个无形的排队序列。排队论就是研究排队现象及其规律的一门学科，是运筹学的一个分支。如同数学的特质那样，排队论研究的内容比我们感觉中的排队现象要广泛得多，它是研究那些本质上都有排队特征的一类现象。具体表现在：排队的不一定是人，也可以是物。例如：生产线上等待加工的原料、半成品；因故障停止运转等待修理的机器等。计量数模提高班专题五上述问题虽互不相同，但却都有要求得到某种服务的人或物以及提供服务的人或机构。排队论里把要求服务的对象统称为“顾客”,提供服务的人或机构称为“服务台”或“服务员”。计量数模提高班专题五不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图1-3。图1单服务台排队系统计量数模提高班专题五图3-2单队列——S个服务台并联的排队系统图3-3S个队列——S个服务台的并联排队系统计量数模提高班专题五面对拥挤现象，人们总希望尽量设法减少排队，通常的做法是增加服务设施。但是增加设施的数量越多，人力、物力的支出就越大，同时会出现空闲浪费。如果服务设施太少，顾客排队等待的时间就会很长，这样会对顾客带来不良影响。计量数模提高班专题五顾客排队时间的长短与服务设施规模的大小，就构成了随机服务系统中的一对矛盾。如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾。这就是随机服务系统理论——排队论所要研究解决的问题（寻找一个平衡方案）。计量数模提高班专题五排队结构服务机构顾客源顾客到达排队规则服务规则离去图1排队系统示意图5.1排队系统的组成与特征排队系统一般有三个基本组成部分：1.输入过程；2.排队规则；3.服务机构。五排队论的研究方法计量数模提高班专题五输入即顾客的到达，可有下列情况：1）顾客源可能是有限的，也可能是无限的。2）顾客是成批到达或是单个到达。3）顾客到达间隔时间可能是随机的或确定的。4）顾客到达可能是相互独立或关联的。所谓独立就是前面顾客的到达对后面顾客的到达无影响。5）输入过程可以是平稳的，也可以是非平稳的。平稳