国赛集训专题——蒙特卡洛方法及排队论资料课件.ppt

2014数学建模集训专题五 蒙特卡罗模拟方法与排队论模型,精彩源于坚持，搏过才知其美,柴中林 2014/7/14,本专题提纲,一 引言 二 蒙特卡罗仿真原理介绍 三 蒙特卡罗仿真例子与分析 四 排队论简介 五 排队论研究方法 六 作业,数学建模的解有两类,精确解,近似解,当然，对解的近似程度以及求解过程的复杂程度做一定的探讨对建模来讲是有益的。,求解问题，总希望得到精确解。但很多情况下，精确解是求不出或者难以求出的。在此情况下，求得问题的近似解就成了必然的选择。此外，从应用的角度讲，一定程度的近似解就够了。,一 引言,排队论是重要的一类随机模型(现象)，而蒙特卡罗方法则是基于随机理论的一种重要的仿真模拟方法，它们都与不确定性现象相关联。,自然现象有两类,确定性现象,不确定性现象,随机现象,模糊现象,在一定条件下必然发生的现象,2、能用蒙特卡罗方法编程求解问题；,1、了解蒙特卡罗方法的原理和适用范围；,3、了解排队问题的特点、基本类型和理论；,4、能对简单的排队问题编程计算。,本专题的学习目的,二 蒙特卡罗仿真原理介绍,蒙特卡罗(Monte Carlo，美国一赌城的名称)方法又称统计模拟法、随机抽样技术，是一种以概率论和统计方法为基础的基于随机模拟的数值计算方法。它将所求解的问题同一定的概率模型相联系，用计算机和它产生的随机数实现统计模拟或抽样，再根据统计理论获得问题的近似解。,蒙特卡罗方法的概率论依据： 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 蒙特卡罗方法的精髓或妙处在于设计合理的概率模型，以便用模拟的方法求解问题。,模拟 得到,模拟得到,（伪）随机数的产生,其他一些随机变量的随机数可利用U(0,1)分布等通过适当数学方法得到,仿真与模拟的目的和原理,仿真和模拟可以说是针对同一内容的不同角度的看法描述，当需要对某一问题观察研究而相应的观察和实验时间和成本花费太高时，可以考虑用一个模型代替原型，用模型的研究达到原型的研究的目的（以节约时间和成本），这就是仿真，其在计算机上等的实现过程也称为模拟。,例1：中子穿过原子反应堆屏障问题模拟,原子反应堆外的铅屏障是用来屏障堆中逸出的中子的，以免造成危害。一般的，可做以下简单假设：每个进入屏障的中子在撞到铅原子前行进的距离为D，然后这个中子以随机方向弹回来，并且在它的下一次撞击中又行进距离D。假设屏障厚度为3D，每一个中子能经受10次撞击，问进入的中子能以多大的比例穿透铅屏障？,三 仿真例子与分析,反应堆,铅屏障,运动的中子,分析：该问题显然难以用概率论解决，用蒙特卡罗方法却很容易。为方便，将屏障内外径看作直线段，并做进一步假设： 1 中子反弹回反应堆后认为不能穿过屏障。 2 与铅原子相撞后任意方向等可能反弹。 3 中子撞击十次后必毁灭。画图如右，模拟流程图如下,中子撞击铅屏模拟流程图,初始化系统状态,产生一个新中子的初试方向和运行终点,中子回到 反应堆了吗,求频率,结束,Y,N,碰撞，产生新方向和运行终点,模拟次数 到了吗,N,Y,中子出了 铅屏了吗,碰撞次数到了吗,N,频数增加,Y,Y,N,对复杂对象的编程，画一个流程图是很有帮助的,中子问题程序,n=10000; % simulation number m=0; %frequency;Further,D is deemed to be 1 for i=1:n theta=unifrnd(-pi/2,pi/2); % initinal angle x=cos(theta); % only x needs to be considered for j=1:10 theta=2*pi*rand;%new angle after a hitting x=x+cos(theta);% new distance is added if x3 % the neutron passes through the barrier m=m+1; % m adds 1 break; end end end fn=m/n %frequency,例2：计算定积分,分析： 这个积分应该有精确解，因为原函数的缘故这个积分不易求得，故求一个近似解是必然的选择。可以用其他方法求近似解，这里用蒙特卡罗方法。用蒙特卡罗方法离不开随机变量。当问题本身具有随机性时，随机变量的选取与这个随机问题应当一致（如上例）；而当问题本身不具有随机性时（本例），就要引入随机变量，将确定性问题转化为不确定问题，以求得问题的解。,根据积分区域，引入随机变量 XU(0,3),记其密度函数为(x)(=1/3)，又记f (x)=exp(-x2),且在0,3上记Y=F(X)=f (X)/(X)=3exp(-X2)，则 模拟结果为0.8704,软件算得结果为0.8862.,计算重积分原理相同，且更有价值,例3 赶火车,一列火车大约在下午1点离开A站，其规律如下： 离站时间 13：00 13：05 13：00 概率 0.7 0.2 0.1 火车从A站到B站所需时间服从正态分布，平均30分钟，标准差2分钟。如果你要赶的是这趟火车的下一站B，而你到达的时间分布为 时间 13：28 13：30 13：32 13：34 概率 0.3 0.4 0.2 0.1 问你能赶上这列火车的概率是多少？,问题分析： 解决实际问题，需要将问题符号化和数学化。这个转化有的很明显，较容易；有的则不然，需要一定的技巧.转化的原则是模型和问题在本质上等价。当转化有多种方式时，我们选最简单的一种。,对于问题，赶上火车的可能性就是概率。显然，对问题来说所求概率一定存在，但却不易求得。从应用上讲，知道概率的近似值就够了，这就用上频率。我们的做法相当于仿真：假想这个人按题设条件不断的赶往开到B站的火车，计算他赶上的频率。 但对于火车在1点离开A站的概率是0.7 该怎么处理？我们给一个最简单的随机变量： XU(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应满足,然而，我们仍然难以应用，且不直观。鉴于报童问题的随机性特点，用仿真是非常有效的方法。为此，我们举一个具体例子，设a=0.5, b=0.3, c=0.15,且每天的报纸需求服从P(50)的分布，模拟见程序。由模拟可知每天宜订购51份报纸。,其中p(r)为密度函数,评注,蒙特卡罗方法适应于随机性问题，对于非随机性问题，必须将它转化为随机问题。蒙特卡罗方法的优点是程序结构简单，计算复杂性不随对象复杂度的增加而增加，缺点是近似解的精度不高，误差具有随机性，不易估计。蒙特卡罗方法应在其他方法难以求解的时去用；当然，还要求该方法此时适合用。,四 排队论简介,1 到银行取钱，发现前面有几十个人在排着队，你掉头就走：不能忍受啊！怎么不多开几家银行、再增加几个服务窗口啊！ 假如你是工作人员，你觉得应根据什么来决定是否需要开设新的银行或增加新的服务窗口要知道一次的排队人多会具有偶然性的！ 2 银行一般都有几个服务窗口，过去是顾客每个窗口分别排队等待服务，而现在几乎都改为叫号制，这相当于多个窗口只排一队。银行为什么要这么做? 有什么好处？,引例,排队是我们日常生活中常见的现象，如： 上、下班搭乘公共汽车； 顾客到商店购买物品； 病人到医院看病； 学生去食堂就餐等出现的排队和等待 服务现象。,排队现象,排队可以是有形的，也可以是无形的。 如几个顾客打电话到出租车站要车，如果出租车站无足够车辆，则部分顾客只得在要车处等待，他们分散在不同地方，形成一个无形的排队序列。,排队论就是研究排队现象及其规律的一门学科，是运筹学的一个分支。如同数学的特质那样，排队论研究的内容比我们感觉中的排队现象要广泛得多，它是研究那些本质上都有排队特征的一类现象。具体表现在：,排队的不一定是人，也可以是物。 例如：生产线上等待加工的原料、半成品； 因故障停止运转等待修理的机器等。,上述问题虽互不相同，但却都有要求得到某种服务的人或物以及提供服务的人或机构。 排队论里把要求服务的对象统称为“顾客”,提供服务的人或机构称为“服务台”或“服务员”。,不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图1-3。,图1 单服务台排队系统,图3-2 单队列S个服务台并联的排队系统,图3-3 S个队列S个服务台的并联排队系统,面对拥挤现象，人们总希望尽量设法减少排队，通常的做法是增加服务设施。 但是增加设施的数量越多，人力、物力的支出就越大，同时会出现空闲浪费。 如果服务设施太少，顾客排队等待的时间就会很长，这样会对顾客带来不良影响。,顾客排队时间的长短与服务设施规模的大小，就构成了随机服务系统中的一对矛盾。 如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾。 这就是随机服务系统理论排队论所要研究解决的问题（寻找一个平衡方案）。,2019/11/17,31,可编辑,5.1 排队系统的组成与特征 排队系统一般有三个基本组成部分：1.输入过程；2.排队规则；3.服务机构。,五 排队论的研究方法,输入即顾客的到达，可有下列情况： 1）顾客源可能是有限的，也可能是无限的。 2）顾客是成批到达或是单个到达。 3）顾客到达间隔时间可能是随机的或确定的。 4）顾客到达可能是相互独立或关联的。所谓独立就是前面顾客的到达对后面顾客的到达无影响。 5）输入过程可以是平稳的，也可以是非平稳的。平稳是指顾客相继到达的间隔时间分布和参数（均值、方差）与时间无关；非平稳的则与时间相关。,5 . 1.1 输入过程,分为损失制、等待制、混合制三大类。 (1)损失制 指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。 典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号。,5 . 1 . 2. 排队规则,(2)等待制 当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。 例如，排队等待售票，故障设备等待维修等。 等待制中，服务台在选择顾客进行服务时，常有如下四种规则： 先到先服务（FCFS ） 按顾客到达的先后顺序对他们进行服务，这是最普遍的情形。 此外还有后到先服务（LCFS），随机服务（RAND）和优先权服务（PR）三种情形。,(3)混合制这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种： 队长有限。当排队等待服务顾客人数超过规定数量时，后来顾客就自动离去，另求他处服务。 如水库的库容、旅馆的床位等都是有限的。 另两种情况指等待时间和逗留时间限制的情形，略去。 一般的，损失制和等待制可认为是混合制的两种极端特殊情形。,5.1.3 服务机构,1）服务机构可以是单服务员和多服务员服务，这种服务形式与队列规则联合后形成了多种不同队列，不同形式的排队服务机构。如前图1-3,2)服务方式分为单个顾客服务和成批顾客服务。 3)服务时间分为确定型和随机型。 4)服务时间的分布在这里假定是平稳的。,上述特征中最主要的、影响最大的是： 顾客相继到达的间隔时间分布 服务时间的分布 服务台数 D.G.Kendall在1953提出了分类法，称为Kendall记号(适用于并列服务台)即：X/Y/Z， 式中：X顾客相继到达间隔时间分布。 M负指数分布Markov， D确定型分布Deterministic， EkK阶爱尔朗分布Erlang，,5.2 排队系统的描述符号与模型分类,GI 一般相互独立随机分布(General Independent)， G 一般随机分布， Y填写服务时间分布（与上同）， Z填写并列的服务台数。 如 M/M/1即为顾客到达为泊松过程，服务时间为负指数分布，单台的排队系统模型。 在1971年的一次国际会议上，将Kendall记号扩充为 ： X/Y/Z/A/B/C。其中前三项意义不变，后三项为 A排队系统的最大容量 B顾客源数量 C排队规则 并约定，如略去后三项，即指 X/Y/Z/FCFS。因此M/M/1/FCFS，可简写为M/M/1，指顾客到达为泊松过程，服务时间为负指数分布，单台，无限容量，无限源，先到先服务的排队系统模型。,5.3 排队论研究的基本问题 1.排队系统的统计推断:即判断一个给定的排队系统符合于哪种模型，以便根据排队理论进行研究。 2.系统性态问题:即研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布和忙期分布等统计指标,包括了瞬态和稳态两种情形。 3.最优化问题：即包括最优设计(静态优化)，最优运营（动态优化）。,分布检验,求解一般排队系统问题的目的主要是通过研究排队系统运行的效率指标，估计服务质量，确定系统的合理结构和系统参数的合理值，以便实现对现有系统合理改进和对新建系统的最优设计等。 排队问题的一般步骤： 1. 确定或拟合排队系统顾客到达的时间间隔分布和服务时间分布。 2. 研究分析排队系统理论分布的概率特征。 3. 研究系统状态的概率。系统状态是指系统中顾客数。状态概率用Pn(t)表示,即在t时刻系统中有n个顾客的概率，也称瞬态概率。,求解状态概率Pn(t)的方法是建立含Pn(t)的微分差分方程，通过求解微分差分方程得到系统瞬态解，由于瞬态解一般难以求出确定值，即便求得一般也难以使用。因此常常使用它的极限(如果存在的话)：,稳态的物理意义图，系统的稳态一般很快都能达到，但实际中达不到稳态的现象也存在。要注意的是求稳态概率Pn并不一定求t的极限,只需求Pn(t)=0 。,称为稳态解，或称统计平衡状态的解。,4.根据排队系统对应的理论模型求用以判断系统运行优劣的基本数量指标的概率分布或特征数。 数量指标主要包括: (1)平均队长（Ls）:系统中的顾客数。 平均队列长（Lg）:系统中排队等待服务的顾客数。 (2)平均逗留时间(Ws):指一个顾客在系统中的停留时间。 平均等待时间(Wg):一个顾客在系统中排队等待的时间。 (3)忙期：指从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度。（忙期和一个忙期中平均完成服务顾客数都是衡量服务机构效率的指标，忙期关系到工作强度）,5.4 理论分布,1.泊松分布 设随机变量为X，则有：,n=0,1,2, （1）,与时间有关的随机变量的概率，是一个随机过程，即泊松过程。,t0，n=0,1,2, （2）,（t2t1，n0）,若设N(t)表示在时间区间0,t)内到达的顾客数(t0),Pn(t1,t2)表示在时间区间t1,t2)(t2t1)内有n(0)个顾客到达的概率。即：,当Pn(t1,t2)符合下述三个条件时，顾客到达过程就是泊松过程(顾客到达形成普阿松流)。,平稳性：即对于足够小的t，有：,普阿松流具有如下特性：,在t,t+t内有一个顾客到达的概率与t无关,而与t成正比。, 普通性：对充分小的t,在时间区间（t,t+t）内有2个或2个以上顾客到达的概率是一高阶无穷小.,由此知，在(t，t+t)区间内没有顾客到达的概率为：,令t1=0,t2=t,则Pn(t1,t2)=Pn(0,t)=Pn(t),0 是常数，它表示单位时间到达的顾客数，称为概率强度。,即,P0+P1+P2=1,2.负指数分布 当输入过程是泊松流时，我们研究两顾客相继到达的时间间隔的概率分布。 设T为时间间隔，分布函数为FT（t），则： FT（t）=PTt 此概率等价于在0，t）区间内至少有1个顾客到达的概率。,没有顾客到达的概率为： (由（5）式而来),间隔：,间隔：,间隔,对分布函数微分,表示单位时间内顾客到达的平均数。 1/表示顾客到达的平均间隔时间。 可以证明，间隔时间T独立且服从负指数分布与顾客到达形成泊松流是等价的。,对顾客的服务时间：系统处于忙期时两顾客相继离开系统的时间间隔，一般地也服从负指数分布，设：,即T服从负指数分布，它的期望及方差为：,接受服务，然后离开,服务时间的分布：,其中：表示单位时间内能被服务的顾客数，即平均 服务率。 1/表示一个顾客的平均服务时间。,，则,令 ，则称为服务强度。,一般的，要设1（否则队列会无限， 永远达不到稳态）,对排队模型，在给定输入和服务条件下，主要研究系统的下述运行指标： (1)系统的平均队长Ls(期望值)和平均队列长Lq(期望值)； (2)系统中顾客平均逗留时间Ws与队列中平均等待时间Wq； 本节只研究M/M/1模型.,5.5 M/M/1 模型研究,经研究（非常复杂，参见运筹学教材），上述四个指标的关系为(Little 公式)：,知识点评：,从上述分析可以看出：排队论是有用的，同时又非常难。根据顾客的到来，排队方式和服务方式可以存在很多种模型。最简单的M/M/1模型就这么复杂，何况其他模型。事实上能进行理论研究的排队模型是不多的，而这些模型多少还有些理想化的成分。对于生活中许多一般化的排队问题，是难以求出其概率分布，得到其平均队长、等待时间等标志性参数的，怎么办？这就需要仿真和模拟，而蒙特卡罗方法是求解这类问题的有效方法,此外，对于给定的排队问题，若给出了顾客到达和服务时间的分布类型，可直接模拟。若给出的是一些顾客到达和服务时间的数据，则要根据数据特点判断可能的分布类型，进行分布类型的检验，并求得相关的参数，再利用分布和参数模拟。若分布不属于泊松分布，且简单，可直接用频率当概率进行模拟。 提醒：实际问题中顾客到达的类型可能太多，由于随机的原因可能有些小概率现象发生。若全部考虑所编程序会太复杂，没有实用价值。因此，对顾客的到达，服务时间等要适当简化处理，如把一些小概率不考虑或并到其他事件中去（无论如何都是近似解）。,例5： M/M/1模型及其模拟流程图,M/M/1模型即顾客到达的间隔和服务时间都服从负指数分布，只有一个服务台，队长无限。我们先分析其排队和服务的特点，再给出模拟流程图，而后用适当参数计算顾客的平均等待时间和逗留时间。,模拟过程分析,因为 Matlab的删除需要，队伍中至少要