第五讲蒙特卡洛方法及排队论讲稿.ppt
《第五讲蒙特卡洛方法及排队论讲稿.ppt》由会员分享,可在线阅读,更多相关《第五讲蒙特卡洛方法及排队论讲稿.ppt(66页珍藏版)》请在三一文库上搜索。
1、蒙特卡罗仿真与排队论模型,梦想点燃激情,激情成就未来,柴中林 2011/4/16,数模提高班之专题五,数学模型的解有两种,精确解,近似解,当然,对解的近似程度以及求解的复杂程度做一定的讨论对建模来讲都是有益的。,求解问题,人们总希望得到精确解。但是在很多情况下,精确解是求不出或很难求出的。在此情况下,求得问题的近似解就是必然的了。此外,从应用的角度讲,一定程度的近似解就够了。,引言,排队论是重要的一类随机模型,而蒙特拉罗方法则是基于随机理论的一种重要的仿真模拟方法,它们都与不确定现象相关。,引言,自然现象有两类,确定性现象,不确定性现象,随机现象,模糊现象,2、能用蒙特卡罗方法编程求解问题;,
2、1、了解蒙特卡罗方法的原理和适用范围;,3、了解排队问题的特点、基本类型和理论;,4、能对简单的排队问题编程求解。,本专题的学习目的,一、蒙特卡罗方法简介,蒙特卡罗(Monte Carlo,美国一赌城的名称)方法又称统计模拟法、随机抽样技术,是一种以概率和统计理论方法为基础的基于随机模拟的数值计算方法。它将所求解的问题同一定的概率模型相联系,用计算机和随机数实现统计模拟或抽样,再根据统计理论获得问题的近似解。,蒙特卡罗方法的概率论依据: 1 设A表示一随机事件,P(A),fn(A)分别表示A发生的概率和频率,则当n很大时有P(A)fn(A)。 2 设X是一随机变量(总体), E(X)=, D(
3、X)=2分别是X 的期望和方差,X1, X2,Xn, 是来自总体X的一个样本,则 分别是 和2的估计。 3 该方法也可以估计参数,如()中含参数,利用的估计式就可估计出参数的值。,模拟 得到,模拟得到,随机数的产生,其他一些随机变量可利用U(0,1)分布通过适当数学方法得到(参见下面例子),仿真与模拟的目的和原理,仿真和模拟可以说是针对同一内容的不同角度的看法描述,当需要对某一问题观察研究而相应的观察和实验时间和成本花费太高时,可以考虑用一个模型代替原型,用模型的研究达到原型的研究的目的(以节约时间和成本),这就是仿真,其在计算机上等的实现过程也称为模拟。,例1:中子穿过原子反应堆屏障问题模拟
4、,原子反应堆外的铅屏障是用来屏障原子反应堆中逸出的中子的,以免给人类造成危害。经试验和分析,可做以下简单假设:每一个进入屏障的中子在撞到铅原子前行进的距离为D,然后这个中子以随机方向弹回来,并且在它的下一次撞击中又行进距离D。假设屏障厚度为3D,每一个中子能经受10次撞击,问进入的中子能以多大的比例穿透铅屏障?,二、仿真例子与分析,分析:该问题显然难以用概率论解决,用蒙特卡罗方法却很容易。为方便,不妨做进一步假设: 1 中子反弹回反应堆后认为不能穿过屏障。 2 与铅原子相撞后任意方向等可能反弹。 3 中子撞击十次后毁灭。画图如右,模拟流程图如下,中子撞击铅屏模拟流程图,初始化系统状态,产生一个
5、新中子的初试方向和运行终点,中子回到 反应堆了吗,求频率,结束,Y,N,碰撞,产生新方向和运行终点,模拟次数 到了吗,N,Y,中子出了 铅屏了吗,碰撞次数到了吗,N,频数增加,Y,Y,N,对复杂的对象编程,画一个流程图是很有价值的,程序为,n=10000; % test number m=0; %frequency for i=1:n theta=unifrnd(-pi,pi); % initinal angle x=cos(theta); % only x needed for j=1:10 theta=2*pi*rand;%new angle hitted x=x+cos(theta);
6、if x3 m=m+1; break; end end end fn=m/n % rate,例2:计算定积分,分析: 这个积分应该有精确解,因为原函数的缘故这个积分不易求得,精确解难以得到,故求一个近似解是必然的选择。可以用其他方法求近似解,这里用蒙特卡罗方法。用蒙特卡罗方法离不开随机变量。当问题本身具有随机性时,随机变量的选取与这个随机问题应当一致(如上例);而当问题本身不具有随机性时(本例),就要引入随机变量,将确定性问题转化为不确定问题,以求得问题的解。,根据积分区域,引入随机变量 X,且XU(0,3),记其密度含函数为(x) ,又记f(x)=exp(-x2),且在0,3上记Y=F(x)
7、=f(x)/ (x),则 模拟结果为0.8704,软件算得结果为0.8862.,计算重积分原理相同,且更有价值,例3:用蒙特卡罗法求的(近似)值,求的值已有多种方法,而且要多精确都可以。蒙特卡罗方法求的值效果并不好,这里主要介绍原理。本问题相当于用蒙特卡罗法求一个参数的近似值。,可以根据圆面积及其积分如上构造模型,也可如下构造:设XU(-1,1), YU(-1,1),且相互独立,则(X,Y)在如右图所示的正方形内服从均匀分布。今考虑事件X2+Y21,该事件就相当于随机变量(X,Y)落在圆周内。利用均匀分布的特征容易得到,从而 4fn(A),程序如下,n=10000; % test number
8、 m=0; for i=1:n x=unifrnd(-1,1); %generate the rand number of x y=unifrnd(-1,1); %generate the rand number of y if x2+y21 % judge if (X,Y) is in the circle m=m+1; % add the frequency end end fn=m/n % rate yuanzhoulv=4*fn %result,评注,蒙特卡罗方法适应于随机的问题,对于非随机问题,必须将它转化为随机的问题。蒙特卡罗方法的优点是程序结构简单,不随对象复杂度的增加而增加,其
9、缺点是近似解的精度不高,误差具有随机性,不易估计。蒙特卡罗方法应在其他方法难以求解的时去用;当然,还要求该方法此时适合用。,三排队论,1 到银行取钱,发现前面有几十个人在排着队,你掉头就走:不能忍受啊!怎么不多开几家银行、再增加几个服务窗口啊! 假如你是工作人员,你觉得应根据什么来决定是否需要开设新的银行或增加新的服务窗口要知道一次的排队人多具有随机性(偶然性)啊。 2 银行一般都有几个服务窗口,过去是顾客每个窗口分别排队等待服务,而现在几乎都改为叫号制,这相当于多个窗口只排一队的服务规则。银行为什么要这么做? 有什么好处?,引例,排队是我们日常生活中常见的现象,如: 上、下班搭乘公共汽车;
10、顾客到商店购买物品; 病员到医院看病; 学生去食堂就餐等出现的排队和等待 服务现象。,排队现象,排队可以是有形的,也可以是无形的。 如几个顾客打电话到出租车站要车,如果出租车站无足够车辆,则部分顾客只得在要车处等待,他们分散在不同地方,形成一个无形的排队序列。,排队论就是研究排队现象及其规律的一门学科,是运筹学的一个分支。如同数学的特质那样,排队论研究的内容比我们感觉中的排队现象要广泛得多,它是研究那些本质上都有排队特征的一类现象。具体表现在:,排队的不一定是人,也可以是物。 例如:生产线上等待加工的原料、半成品; 因故障停止运转等待修理的机器等。,上述问题虽互不相同,但却都有要求得到某种服务
11、的人或物以及提供服务的人或机构。 排队论里把要求服务的对象统称为“顾客”,提供服务的人或机构称为“服务台”或“服务员”。,不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待,则加入等待队伍,待获得服务后离开系统,见图2-1至图2-3。,图2-1 单服务台排队系统,图2-2 单队列S个服务台并联的排队系统,图2-3 S个队列S个服务台的并联排队系统,面对拥挤现象,人们总希望尽量设法减少排队,通常的做法是增加服务设施。 但是增加设施的数量越多,人力、物力的支出就越大,同时会出现空闲浪费。 如果服务设施太少,顾客排队等待的时间就会很长,这样对
12、顾客会带来不良影响。,顾客排队时间的长短与服务设施规模的大小,就构成了随机服务系统中的一对矛盾。 如何做到既保证一定的服务质量指标,又使服务设施费用经济合理,恰当地解决顾客排队时间与服务设施费用大小这对矛盾。 这就是随机服务系统理论排队论所要研究解决的问题。,4.1 排队系统的组成与特征 排队系统一般有三个基本组成部分:1.输入过程;2.排队规则;3.服务机构。,四 排队论的研究方法,输入即顾客的到达,可有下列情况: 1)顾客源可能是有限的,也可能是无限的。 2)顾客是成批到达或是单个到达。 3)顾客到达间隔时间可能是随机的或确定的。 4)顾客到达可能是相互独立或关联的。所谓独立就是以前顾客的
13、到达对以后顾客的到达无影响。 5)输入过程可以是平稳的(stationary),也可以是非平稳的。输入过程平稳的指顾客相继到达的间隔时间分布和参数(均值、方差)与时间无关;非平稳的则与时间相关。,4 . 1.1 输入过程,分为损失制、等待制、混合制三大类。 (1)损失制 指如果顾客到达排队系统时,所有服务台都已被先来的顾客占用,那么他们就自动离开系统永不再来。 典型例子是,如电话拔号后出现忙音,顾客不愿等待而自动挂断电话,如要再打,就需重新拔号。,4 . 1 . 2. 排队规则,(2)等待制 当顾客来到系统时,所有服务台都不空,顾客加入排队行列等待服务。 例如,排队等待售票,故障设备等待维修等
14、。 等待制中,服务台在选择顾客进行服务时,常有如下四种规则: 先到先服务(FCFS ) 按顾客到达的先后顺序对顾客进行服务,这是最普遍的情形。 此外还有后到先服务(LCFS),随机服务(RAND)和优先权服务(PR)三种情形。,(3)混合制这是等待制与损失制相结合的一种服务规则,一般是指允许排队,但又不允许队列无限长下去。具体说来,大致有三种: 队长有限。当排队等待服务顾客人数超过规定数量时,后来顾客就自动离去,另求他处服务。 如水库的库容、旅馆的床位等都是有限的。 另两种情况指等待时间和逗留时间限制的情形,略去。 一般的,损失制和等待制可认为是混合制的两种极端特殊情形。,4.1.3 服务机构
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五 讲蒙特卡洛 方法 排队 讲稿
链接地址:https://www.31doc.com/p-3123278.html