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

《2014国赛集训专题6蒙特卡洛方法及排队论.ppt》由会员分享，可在线阅读，更多相关《2014国赛集训专题6蒙特卡洛方法及排队论.ppt（61页珍藏版）》请在三一文库上搜索。

1、计量数模提高班专题五20142014数学建模集训专题五数学建模集训专题五蒙特卡罗模拟方法与排队论模型蒙特卡罗模拟方法与排队论模型柴中林柴中林 2014/7/14 2014/7/142021/6/161计量数模提高班专题五本专题提纲一 引言二 蒙特卡罗仿真原理介绍三 蒙特卡罗仿真例子与分析四 排队论简介五 排队论研究方法六 作业2021/6/162计量数模提高班专题五 数学建模的解有两类数学建模的解有两类精确解精确解近似解近似解 当然，对解的近似程度以及求解过程的复杂程度做一定的探当然，对解的近似程度以及求解过程的复杂程度做一定的探讨对建模来讲是有益的。讨对建模来讲是有益的。求解问题，总希望得到

2、精确解。但很多情况下，精确解是求不求解问题，总希望得到精确解。但很多情况下，精确解是求不出或者难以求出的。在此情况下，求得问题的近似解就成了必然出或者难以求出的。在此情况下，求得问题的近似解就成了必然的选择。此外，从应用的角度讲，一定程度的近似解就够了。的选择。此外，从应用的角度讲，一定程度的近似解就够了。一一 引言引言2021/6/163计量数模提高班专题五 排队论是重要的一类随机模型排队论是重要的一类随机模型(现象现象)，而蒙特卡罗方法则是，而蒙特卡罗方法则是基于随机理论的一种重要的仿真模拟方法，它们都与不确定性基于随机理论的一种重要的仿真模拟方法，它们都与不确定性现象相关联。现象相关联。

3、自然现象有两类自然现象有两类确定性现象确定性现象不确定性现象不确定性现象随机现象随机现象模糊现象模糊现象在一定条件下必然发生的现象2021/6/164计量数模提高班专题五2、能用蒙特卡罗方法编程求解问题；、能用蒙特卡罗方法编程求解问题；1、了解蒙特卡罗方法的原理和适用范围；、了解蒙特卡罗方法的原理和适用范围；3、了解排队问题的特点、基本类型和理论；、了解排队问题的特点、基本类型和理论；4、能对简单的排队问题编程计算。、能对简单的排队问题编程计算。本专题的学习目的本专题的学习目的2021/6/165计量数模提高班专题五二二 蒙特卡罗仿真原理介绍蒙特卡罗仿真原理介绍 蒙特卡罗(Monte Carl

4、o，美国一赌城的名称)方法又称统计模拟法、随机抽样技术，是一种以概率论和统计方法为基础的基于随机模拟的数值计算方法。它将所求解的问题同一定的概率模型相联系，用计算机和它产生的随机数实现统计模拟或抽样，再根据统计理论获得问题的近似解。2021/6/166计量数模提高班专题五蒙特卡罗方法的概率论依据：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 上述式子不仅可以求概率等的近似值，也

5、可以估计参数。如（）中含参数，根据的估计式的求解就可得到的近似值。4 蒙特卡罗方法的精髓或妙处在于设计合理的概率模型，以便用模拟的方法求解问题。模拟得到模拟得到2021/6/167计量数模提高班专题五（伪）随机数的产生rand产生一个服从U(0,1)分布的随机数rand(m,n)产生mn个服从U(0,1)分布的随机数exprnd()产生一个服从e()分布的随机数poissrnd()产生一个服从P()分布的随机数binornd(n,p)产生一个服从B(n,p)分布的随机数normrnd(,)产生一个服从N(,2)分布的随机数unifrnd(a,b)产生一个服从U(a,b)分布的随机数其他一些随机

6、变量的随机数可利用U(0,1)分布等通过适当数学方法得到2021/6/168计量数模提高班专题五仿真与模拟的目的和原理 仿真和模拟可以说是针对同一内容的不仿真和模拟可以说是针对同一内容的不同角度的看法描述，当需要对某一问题观同角度的看法描述，当需要对某一问题观察研究而相应的观察和实验时间和成本花察研究而相应的观察和实验时间和成本花费太高时，可以考虑用一个模型代替原型，费太高时，可以考虑用一个模型代替原型，用模型的研究达到原型的研究的目的（以用模型的研究达到原型的研究的目的（以节约时间和成本），这就是仿真，其在计节约时间和成本），这就是仿真，其在计算机上等的实现过程也称为模拟。算机上等的实现过程

7、也称为模拟。2021/6/169计量数模提高班专题五例1：中子穿过原子反应堆屏障问题模拟 原子反应堆外的铅屏障是用来屏障堆中逸出的中子的，以免造成危害。一般的，可做以下简单假设：每个进入屏障的中子在撞到铅原子前行进的距离为D，然后这个中子以随机方向弹回来，并且在它的下一次撞击中又行进距离D。假设屏障厚度为3D，每一个中子能经受10次撞击，问进入的中子能以多大的比例穿透铅屏障？三 仿真例子与分析反应堆铅屏障运动的中子2021/6/1610计量数模提高班专题五 分析：该问题显然难以用概率论解决，用蒙特卡罗方法却很容易。为方便，将屏障内外径看作直线段，并做进一步假设：1 中子反弹回反应堆后认为不能穿

8、过屏障。2 与铅原子相撞后任意方向等可能反弹。3 中子撞击十次后必毁灭。画图如右，模拟流程图如下屏障x轴y轴中子外半径内半径2021/6/1611计量数模提高班专题五中子撞击铅屏模拟流程图 初始化系统状态 产生一个新中子的初试方向和运行终点 中子回到 反应堆了吗求频率,结束YN 碰撞，产生新方向和运行终点 模拟次数 到了吗NY 中子出了 铅屏了吗 碰撞次数到了吗N 频数增加YYN对复杂对对复杂对象的编程，象的编程，画一个流画一个流程图是很程图是很有帮助的有帮助的2021/6/1612计量数模提高班专题五中子问题程序n=10000;%simulation numberm=0;%frequency

9、Further,D is deemed to be 1for 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 endfn=m/n

10、frequency2021/6/1613计量数模提高班专题五例2：计算定积分 分析：这个积分应该有精确解，因为原函数的缘故这个积分不易求得，故求一个近似解是必然的选择。可以用其他方法求近似解，这里用蒙特卡罗方法。用蒙特卡罗方法离不开随机变量。当问题本身具有随机性时，随机变量的选取与这个随机问题应当一致（如上例）；而当问题本身不具有随机性时（本例），就要引入随机变量，将确定性问题转化为不确定问题，以求得问题的解。2021/6/1614计量数模提高班专题五 根据积分区域，引入随机变量 XU(0,3),记其密度函数为(x)(=1/3)，又记f(x)=exp(-x2),且在0,3上记Y=F(X)=f

11、X)/(X)=3exp(-X2)，则 模拟结果为0.8704,软件算得结果为0.8862.计算重积分原理相同，且更有价值2021/6/1615计量数模提高班专题五例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问 你 能 赶 上 这 列 火 车 的 概 率 是 多 少？2021/6/1616计量数模提

12、高班专题五问题分析问题分析：解决实际问题，需要将问题符号化和数学化。这个转化有的很明显，较容易；有的则不然，需要一定的技巧.转化的原则是模型和问题在本质上等价。当转化有多种方式时，我们选最简单的一种。2021/6/1617计量数模提高班专题五 对于问题，赶上火车的可能性就是概率。显然，对问题来说所求概率一定存在，但却不易求得。从应用上讲，知道概率的近似值就够了，这就用上频率。我们的做法相当于仿真：假想这个人按题设条件不断的赶往开到B站的火车，计算他赶上的频率。但对于火车在1点离开A站的概率是0.7 该怎么处理？我们给一个最简单的随机变量：XU(0,1)，则P(0X0.7)=0.7。这样，我们产

13、生一个服从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.9 b(购进价购进价)c(退回价退回价)售出一份赚售出一份赚 a-b；退回一份赔；退回一份赔 b-c 每天购进多少份可使收入最大？每天购进多少份可使收入最大？分分析析购进太多购进太多卖不完退回卖不完退回赔钱赔钱购进太少购进太少不够销售不够销售赚钱少赚钱少应根据需求确定购进量应

14、根据需求确定购进量.每天需求量是随机的每天需求量是随机的优化问题的目标函数应是长期的日平均收入优化问题的目标函数应是长期的日平均收入每天收入是随机的每天收入是随机的存在一个合存在一个合适的购进量适的购进量等于每天收入的期望等于每天收入的期望2021/6/1619计量数模提高班专题五设报纸设报纸每天需求量为每天需求量为 r 的概率为的概率为 f(r),r r=0,1,2,，由数学建模知识可得最佳订购量由数学建模知识可得最佳订购量n应满足应满足 然而，我们仍然难以应用，且不直观。鉴于报童问题的随机性特点，用仿真是非常有效的方法。为此，我们举一个具体例子，设a=0.5,b=0.3,c=0.15,且每

15、天的报纸需求服从P(50)的分布，模拟见程序。由模拟可知每天宜订购51份报纸。其中p(r)为密度函数2021/6/1620计量数模提高班专题五评注蒙特卡罗方法适应于随机性问题，对于非随机性问题，必须将它转化为随机问题。蒙特卡罗方法的优点是程序结构简单，计算复杂性不随对象复杂度的增加而增加，缺点是近似解的精度不高，误差具有随机性，不易估计。蒙特卡罗方法应在其他方法难以求解的时去用；当然，还要求该方法此时适合用。2021/6/1621计量数模提高班专题五四 排队论简介 1 1 到银行取钱，发现前面有几十个人在排着到银行取钱，发现前面有几十个人在排着队，你掉头就走：不能忍受啊！怎么不多开几队，你掉头

16、就走：不能忍受啊！怎么不多开几家银行、再增加几个服务窗口啊！家银行、再增加几个服务窗口啊！假如你是假如你是工作人员，你觉得应根据什么来决定是否需要工作人员，你觉得应根据什么来决定是否需要开设新的银行或增加新的服务窗口开设新的银行或增加新的服务窗口要知道要知道一次的排队人多会具有偶然性的！一次的排队人多会具有偶然性的！2 2 银行一般都有几个服务窗口，过去是顾银行一般都有几个服务窗口，过去是顾客每个窗口分别排队等待服务，而现在几乎都客每个窗口分别排队等待服务，而现在几乎都改为叫号制，这相当于多个窗口只排一队。银改为叫号制，这相当于多个窗口只排一队。银行为什么要这么做行为什么要这么做?有什么好处？

17、有什么好处？引例2021/6/1622计量数模提高班专题五 排排队队是是我我们们日日常常生生活活中中常常见见的的现现象象，如：如：上、下班搭乘公共汽车；上、下班搭乘公共汽车；顾客到商店购买物品；顾客到商店购买物品；病人到医院看病；病人到医院看病；学学生生去去食食堂堂就就餐餐等等出出现现的的排排队队和和等等待待 服务现象。服务现象。排队现象排队现象2021/6/1623计量数模提高班专题五 排队可以是有形的，也可以是无形的。排队可以是有形的，也可以是无形的。如如几几个个顾顾客客打打电电话话到到出出租租车车站站要要车车，如如果果出出租租车车站站无无足足够够车车辆辆，则则部部分分顾顾客客只只得得在在

18、要要车车处处等等待待，他他们们分分散散在在不不同同地地方方，形形成成一一个无形的排队序列。个无形的排队序列。排队论就是研究排队现象及其规律的一门排队论就是研究排队现象及其规律的一门学科，是运筹学的一个分支。如同数学的特学科，是运筹学的一个分支。如同数学的特质那样，排队论研究的内容比我们感觉中的质那样，排队论研究的内容比我们感觉中的排队现象要广泛得多，它是研究那些本质上排队现象要广泛得多，它是研究那些本质上都有排队特征的一类现象。具体表现在：都有排队特征的一类现象。具体表现在：2021/6/1624 排队的不一定是人，也可以是物。排队的不一定是人，也可以是物。例例如如：生生产产线线上上等等待待加

19、加工工的的原原料料、半半成品；成品；因故障停止运转等待修理的机器等。因故障停止运转等待修理的机器等。2021/6/1625计量数模提高班专题五 上上述述问问题题虽虽互互不不相相同同，但但却却都都有有要要求求得得到到某某种种服服务务的的人人或或物物以以及及提提供供服务的人或机构。服务的人或机构。排排队队论论里里把把要要求求服服务务的的对对象象统统称称为为“顾顾客客”,”,提提供供服服务务的的人人或或机机构构称称为为“服务台服务台”或或“服务员服务员”。2021/6/1626计量数模提高班专题五 不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排

20、队等待，则加入等待队伍，待获得服务后离开系统，见图1-3。图图1 1 单服务台排队系统单服务台排队系统2021/6/1627计量数模提高班专题五图图3-2 3-2 单队列单队列SS个服务台并联的排队系统个服务台并联的排队系统图图3-3 S3-3 S个队列个队列SS个服务台的并联排队系统个服务台的并联排队系统2021/6/1628计量数模提高班专题五 面面对对拥拥挤挤现现象象，人人们们总总希希望望尽尽量量设设法法减减少排队，通常的做法是增加服务设施。少排队，通常的做法是增加服务设施。但但是是增增加加设设施施的的数数量量越越多多，人人力力、物物力力的支出就越大，同时会出现空闲浪费。的支出就越大，同

21、时会出现空闲浪费。如如果果服服务务设设施施太太少少，顾顾客客排排队队等等待待的的时时间就会很长，这样会对顾客带来不良影响。间就会很长，这样会对顾客带来不良影响。2021/6/1629计量数模提高班专题五 顾顾客客排排队队时时间间的的长长短短与与服服务务设设施施规规模模的的大小，就构成了随机服务系统中的一对矛盾。大小，就构成了随机服务系统中的一对矛盾。如如何何做做到到既既保保证证一一定定的的服服务务质质量量指指标标，又又使使服服务务设设施施费费用用经经济济合合理理，恰恰当当地地解解决决顾顾客排队时间与服务设施费用大小这对矛盾。客排队时间与服务设施费用大小这对矛盾。这这就就是是随随机机服服务务系系

22、统统理理论论排排队队论论所所要研究解决的问题（寻找一个平衡方案）。要研究解决的问题（寻找一个平衡方案）。2021/6/1630计量数模提高班专题五 5.1 5.1 排队系统的组成与特征排队系统的组成与特征 排队系统一般有三个基本组成部分：排队系统一般有三个基本组成部分：1.1.输输入过程；入过程；2.2.排队规则；排队规则；3.3.服务机构。服务机构。五五 排队论的研究方法排队论的研究方法2021/6/1631计量数模提高班专题五 输入即顾客的到达，可有下列情况：输入即顾客的到达，可有下列情况：1）顾客源可能是有限的，也可能是无限的。顾客源可能是有限的，也可能是无限的。2）顾客是成批到达或是单

23、个到达。顾客是成批到达或是单个到达。3）顾客到达间隔时间可能是随机的或确定的。顾客到达间隔时间可能是随机的或确定的。4）顾客到达可能是相互独立或关联的。所谓独顾客到达可能是相互独立或关联的。所谓独立就是前面顾客的到达对后面顾客的到达无影响。立就是前面顾客的到达对后面顾客的到达无影响。5）输入过程可以是平稳的，也可以是非平稳的。输入过程可以是平稳的，也可以是非平稳的。平稳是指顾客相继到达的间隔时间分布和参数（均平稳是指顾客相继到达的间隔时间分布和参数（均值、方差）与时间无关；非平稳的则与时间相关。值、方差）与时间无关；非平稳的则与时间相关。5.1.1 1.1 输入过程输入过程2021/6/163

24、2计量数模提高班专题五 分为分为损失制、等待制、混合制损失制、等待制、混合制三大类。三大类。(1)(1)损损失失制制 指指如如果果顾顾客客到到达达排排队队系系统统时时，所所有有服服务务台台都都已已被被先先来来的的顾顾客客占占用用，那那么么他们就自动离开系统永不再来。他们就自动离开系统永不再来。典典型型例例子子是是，如如电电话话拔拔号号后后出出现现忙忙音音，顾顾客客不不愿愿等等待待而而自自动动挂挂断断电电话话，如如要要再再打打，就需重新拔号。就需重新拔号。5 5.1.2 2.排队规排队规则则2021/6/1633计量数模提高班专题五 (2)(2)等等待待制制 当当顾顾客客来来到到系系统统时时，所

25、所有有服服务务台台都都不不空，顾客加入排队行列等待服务。空，顾客加入排队行列等待服务。例如，排队等待售票，故障设备等待维修等。例如，排队等待售票，故障设备等待维修等。等等待待制制中中，服服务务台台在在选选择择顾顾客客进进行行服服务务时时，常常有有如下四种规则：如下四种规则：先先到到先先服服务务（FCFS FCFS）按按顾顾客客到到达达的的先先后后顺顺序序对他们进行服务，这是最普遍的情形。对他们进行服务，这是最普遍的情形。此此外外还还有有后后到到先先服服务务（LCFSLCFS），随随机机服服务务（RAND）和优先权服务和优先权服务（PR）三种情形。三种情形。2021/6/1634计量数模提高班专

26、题五 (3)(3)混混合合制制这这是是等等待待制制与与损损失失制制相相结结合合的的一一种种服服务务规规则则，一一般般是是指指允允许许排排队队，但但又又不不允允许许队队列列无无限限长长下下去去。具具体说来，大致有三种：体说来，大致有三种：队队长长有有限限。当当排排队队等等待待服服务务顾顾客客人人数数超超过过规规定定数数量量时，后来顾客就自动离去，另求他处服务。时，后来顾客就自动离去，另求他处服务。如水库的库容、旅馆的床位等都是有限的如水库的库容、旅馆的床位等都是有限的。另两种情况指等待时间和逗留时间限制的情形，略去。另两种情况指等待时间和逗留时间限制的情形，略去。一一般般的的，损损失失制制和和等

27、等待待制制可可认认为为是是混混合合制制的的两两种种极极端端特特殊情形。殊情形。2021/6/1635计量数模提高班专题五5.1.3 5.1.3 服务机构服务机构 1 1）服服务务机机构构可可以以是是单单服服务务员员和和多多服服务务员员服服务务，这这种种服服务务形形式式与与队队列列规规则则联联合合后后形形成成了了多多种种不不同同队列，不同形式的排队服务机构。如前图队列，不同形式的排队服务机构。如前图1-31-3 2)2)服务方式分为单个顾客服务和成批顾客服务。服务方式分为单个顾客服务和成批顾客服务。3)3)服务时间分为确定型和随机型。服务时间分为确定型和随机型。4)4)服务时间的分布在这里假定是

28、平稳的。服务时间的分布在这里假定是平稳的。2021/6/1636计量数模提高班专题五 上述特征中最主要的、影响最大的是：上述特征中最主要的、影响最大的是：顾客相继到达的间隔时间分布顾客相继到达的间隔时间分布服务时间的分布服务时间的分布服务台数服务台数 D.G.KendallD.G.Kendall在在19531953提出了分类法，称为提出了分类法，称为KendallKendall记号记号(适用于并列服务台适用于并列服务台)即：即：X/Y/ZX/Y/Z，式中：式中：X顾客相继到达间隔时间分布。顾客相继到达间隔时间分布。M负指数分布负指数分布Markov，D确定型分布确定型分布Determinist

29、ic，EkK阶爱尔朗分布阶爱尔朗分布Erlang，5.2 5.2 5.2 5.2 排队系统的描述符号与模型分类排队系统的描述符号与模型分类排队系统的描述符号与模型分类排队系统的描述符号与模型分类2021/6/1637计量数模提高班专题五 GI 一般相互独立随机分布一般相互独立随机分布(General Independent)，G 一般随机分布，一般随机分布，Y填写服务时间分布（与上同），填写服务时间分布（与上同），Z填写并列的服务台数。填写并列的服务台数。如如 M/M/1M/M/1即即为为顾顾客客到到达达为为泊泊松松过过程程，服服务务时时间间为为负负指指数数分分布布，单台的排队系统模型。单台的

30、排队系统模型。在在19711971年的一次国际会议上，将年的一次国际会议上，将KendallKendall记号扩充为记号扩充为：X/Y/Z/A/B/CX/Y/Z/A/B/C。其中前三项意义不变，后三项为。其中前三项意义不变，后三项为 A排队系统的最大容量排队系统的最大容量 B顾客源数量顾客源数量 C排队规则排队规则并并约约定定，如如略略去去后后三三项项，即即指指 X/Y/Z/X/Y/Z/FCFS/FCFS/FCFS/FCFS。因因因因此此此此M/M/1/M/M/1/FCFS/FCFS/FCFS/FCFS，可可可可简简简简写写写写为为为为M/M/1M/M/1，指指指指顾顾客客到到达达为为泊泊松松

31、过过程程，服服务务时时间间为为负负指指数数分分布布，单单台台，无无限限容容量量，无无限限源源，先到先服务的排队系统模型。先到先服务的排队系统模型。2021/6/1638计量数模提高班专题五 5.35.3 排队论研究的基本问题排队论研究的基本问题 1.1.排排队队系系统统的的统统计计推推断断:即即判判断断一一个个给给定定的的排排队队系系统统符符合合于于哪哪种种模模型型，以以便便根根据据排排队队理理论论进进行行研究。研究。2.2.系系统统性性态态问问题题:即即研研究究各各种种排排队队系系统统的的概概率率规规律律性性，主主要要研研究究队队长长分分布布、等等待待时时间间分分布布和和忙忙期分布等统计指标

32、期分布等统计指标,包括了瞬态和稳态两种情形。包括了瞬态和稳态两种情形。3.3.最最优优化化问问题题：即即包包括括最最优优设设计计(静静态态优优化化)，最优运营（动态优化）。，最优运营（动态优化）。2021/6/1639计量数模提高班专题五分布检验 求求解解一一般般排排队队系系统统问问题题的的目目的的主主要要是是通通过过研研究究排排队队系系统统运运行行的的效效率率指指标标，估估计计服服务务质质量量，确确定定系系统统的的合合理理结结构构和和系系统统参参数数的的合合理理值值，以以便便实实现现对对现现有有系统合理改进和对新建系统的最优设计等。系统合理改进和对新建系统的最优设计等。排队问题的一般步骤：排

33、队问题的一般步骤：1 1.确确定定或或拟拟合合排排队队系系统统顾顾客客到到达达的的时时间间间间隔隔分分布和服务时间分布。布和服务时间分布。2 2.研究分析排队系统理论分布的概率特征。研究分析排队系统理论分布的概率特征。3 3.研研究究系系统统状状态态的的概概率率。系系统统状状态态是是指指系系统统中中顾顾客客数数。状状态态概概率率用用P Pn n(t)(t)表表示示,即即在在t t时时刻刻系系统统中中有有n n个顾客的概率，也称瞬态概率。个顾客的概率，也称瞬态概率。2021/6/1640计量数模提高班专题五 求解状态概率求解状态概率P Pn n(t)(t)的方法是建立含的方法是建立含P Pn n

34、t)(t)的微分的微分差分方程，通过求解微分差分方程得到系统瞬态解，差分方程，通过求解微分差分方程得到系统瞬态解，由于瞬态解一般难以求出确定值，即便求得一般也难由于瞬态解一般难以求出确定值，即便求得一般也难以使用。因此常常使用它的极限以使用。因此常常使用它的极限(如果存在的话如果存在的话)：稳态的物理意义图，系稳态的物理意义图，系统的稳态一般很快都能统的稳态一般很快都能达到，但实际中达不到达到，但实际中达不到稳态的现象也存在。要稳态的现象也存在。要注意的是求稳态概率注意的是求稳态概率P Pn n并不一定求并不一定求t的极限的极限,只需求只需求P Pn n(t)=0(t)=0。过渡状态 稳定状

35、态 pn t 图5 排队系统状态变化示意图 称为稳态解，称为稳态解，或称统计平衡状态或称统计平衡状态的解。的解。2021/6/1641计量数模提高班专题五 4 4.根据排队系统对应的理论模型根据排队系统对应的理论模型求用以判断系求用以判断系统运行优劣的基本数量指标的概率分布或特征数。统运行优劣的基本数量指标的概率分布或特征数。数量指标主要包括数量指标主要包括:(1)(1)平均队长（平均队长（L Ls s）:系统中的顾客数。系统中的顾客数。平均队列长（平均队列长（L Lg g）:系统中排队等待服务的顾客数。系统中排队等待服务的顾客数。(2)(2)平均逗留时间平均逗留时间(Ws):(Ws):指一个

36、顾客在系统中的停留时间。指一个顾客在系统中的停留时间。平均等待时间平均等待时间(Wg):(Wg):一个顾客在系统中排队等待的时间。一个顾客在系统中排队等待的时间。(3)(3)忙期：指从顾客到达空闲服务机构起到服务机构再次为忙期：指从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度。（忙期和一个忙期中平均完成服务顾客空闲这段时间长度。（忙期和一个忙期中平均完成服务顾客数都是衡量服务机构效率的指标，忙期关系到工作强度）数都是衡量服务机构效率的指标，忙期关系到工作强度）2021/6/1642计量数模提高班专题五5.4 5.4 理论分布理论分布 式中式中为常数为常数(0)0)，称，称X X服从参

37、数为服从参数为的泊松分布，的泊松分布，若在上式中引入时间参数若在上式中引入时间参数t t，即令，即令tt代替代替，则有：，则有：1.泊松分布泊松分布 设随机变量为设随机变量为X，则有：则有：n=0,1,2,（1）与与时时间间有有关关的的随随机机变变量量的的概概率率，是是一一个个随随机机过过程程，即即泊松过程泊松过程。t0，n=0,1,2,（2）2021/6/1643计量数模提高班专题五（t2t1，n0）若若设设N(t)N(t)表表示示在在时时间间区区间间0,t)0,t)内内到到达达的的顾顾客客数数(t0),P(t0),Pn n(t(t1 1,t,t2 2)表表示示在在时时间间区区间间tt1 1

38、t,t2 2)(t)(t2 2tt1 1)内内有有n(0)n(0)个顾客到达的概率。即：个顾客到达的概率。即：在在一一定定的的假假设设条条件件下下 顾顾客客的的到到达达过过程程就就是是一个泊松过程。一个泊松过程。当当P Pn n(t(t1 1,t,t2 2)符合下述三个条件时，顾客到达过程符合下述三个条件时，顾客到达过程就是泊松过程就是泊松过程(顾客到达形成普阿松流顾客到达形成普阿松流)。2021/6/1644计量数模提高班专题五 无后效性：无后效性：各区间的到达相互独立各区间的到达相互独立,即即MarkovMarkov性。性。也就是说过程在也就是说过程在t+tt+t所处的状态与所处的状态与

39、t t以前所处的状以前所处的状态无态无关。关。平稳性：平稳性：即对于足够小的即对于足够小的tt，有：有：普阿松流具有如下特性：普阿松流具有如下特性：在在t,t+tt,t+t内有一个顾客到达的概率与内有一个顾客到达的概率与t t无关无关,而与而与tt成正比。成正比。2021/6/1645计量数模提高班专题五 普普通通性性：对对充充分分小小的的t,t,在在时时间间区区间间（t,t+tt）内有内有2 2个或个或2 2个以上顾客到达的概率是一高阶无穷小个以上顾客到达的概率是一高阶无穷小.由此知，在由此知，在(t，t+t)t)区间内没有顾客到达的概率为：区间内没有顾客到达的概率为：令令t1 1=0,t=

40、0,t2 2=t,=t,则则P Pn n(t(t1 1,t,t2 2)=P)=Pn n(0,t)=P(0,t)=Pn n(t)(t)0 0 是常数，它是常数，它表示单位时间到达的顾客数，称表示单位时间到达的顾客数，称为概率强度。为概率强度。即即 P P0 0+P+P1 1+P+P22=1=12021/6/1646计量数模提高班专题五 其概率密度函数为：其概率密度函数为：t0t0 2.2.负指数分布负指数分布 当当输输入入过过程程是是泊泊松松流流时时，我我们们研研究究两两顾顾客客相相继继到到达的时间间隔的概率分布。达的时间间隔的概率分布。设设T T为时间间隔，分布函数为为时间间隔，分布函数为F

41、FT T（t t），则：），则：F FT T（t t）=PTt=PTt 此此概概率率等等价价于于在在00，t t）区区间间内内至至少少有有1 1个个顾顾客客到到达的概率。达的概率。t0t0 没有顾客到达的概率没有顾客到达的概率为：为：(由（由（5）式而来）式而来)间隔：间隔：间隔：间隔：间隔间隔 对对分布函分布函数微分数微分2021/6/1647计量数模提高班专题五 表示单位时间内顾客到达的平均数。表示单位时间内顾客到达的平均数。1/表示顾客到达的平均间隔时间。表示顾客到达的平均间隔时间。可可以以证证明明，间间隔隔时时间间T T独独立立且且服服从从负负指指数数分分布布与与顾客到达形成泊松流是等

42、价的。顾客到达形成泊松流是等价的。对对顾顾客客的的服服务务时时间间：系系统统处处于于忙忙期期时时两两顾顾客客相相继继离离开系统的时间间隔开系统的时间间隔，一般地也服从负指数分布，设：，一般地也服从负指数分布，设：即即T服从负指数分布，它的期望及方差为：服从负指数分布，它的期望及方差为：接受服务，然后离开接受服务，然后离开服务时间的分布：服务时间的分布：2021/6/1648计量数模提高班专题五其中：其中：表示单位时间内能被服务的顾客数，即平均表示单位时间内能被服务的顾客数，即平均 服务率。服务率。1/1/表示一个顾客的平均服务时间。表示一个顾客的平均服务时间。，则，则令令 ，则，则称为服务强度

43、称为服务强度。一般的，要设一般的，要设1（否则队列会无限，永远达不到稳态）2021/6/1649计量数模提高班专题五 对对排排队队模模型型，在在给给定定输输入入和和服服务务条条件件下下，主主要要研究系统的下述运行指标：研究系统的下述运行指标：(1)(1)系系统统的的平平均均队队长长LsLs(期期望望值值)和和平平均均队队列列长长LqLq(期望值期望值)；(2)(2)系系统统中中顾顾客客平平均均逗逗留留时时间间WsWs与与队队列列中中平平均均等等待时间待时间WqWq；本节只研究本节只研究M/M/1M/M/1模型模型.5.5 M/M/1 5.5 M/M/1 模型研究模型研究2021/6/1650计

44、量数模提高班专题五 经研究（非常复杂，参见运筹学教材），上经研究（非常复杂，参见运筹学教材），上述四个指标的关系为述四个指标的关系为(Little Little 公式公式)：2021/6/1651计量数模提高班专题五知识点评：从上述分析可以看出：排队论是有用的，同时又非常难。根据顾客的到来，排队方式和服务方式可以存在很多种模型。最简单的M/M/1模型就这么复杂，何况其他模型。事实上能进行理论研究的排队模型是不多的，而这些模型多少还有些理想化的成分。对于生活中许多一般化的排队问题，是难以求出其概率分布，得到其平均队长、等待时间等标志性参数的，怎么办？这就需要仿真和模拟，而蒙特卡罗方法是求解这类问

45、题的有效方法2021/6/1652计量数模提高班专题五 此外，对于给定的排队问题，若给出了顾客到达和服务时间的分布类型，可直接模拟。若给出的是一些顾客到达和服务时间的数据，则要根据数据特点判断可能的分布类型，进行分布类型的检验，并求得相关的参数，再利用分布和参数模拟。若分布不属于泊松分布，且简单，可直接用频率当概率进行模拟。提醒：实际问题中顾客到达的类型可能太多，由于随机的原因可能有些小概率现象发生。若全部考虑所编程序会太复杂，没有实用价值。因此，对顾客的到达，服务时间等要适当简化处理，如把一些小概率不考虑或并到其他事件中去（无论如何都是近似解）。2021/6/1653计量数模提高班专题五例5

46、M/M/1模型及其模拟流程图 M/M/1模型即顾客到达的间隔和服务时间都服从负指数分布，只有一个服务台，队长无限。我们先分析其排队和服务的特点，再给出模拟流程图，而后用适当参数计算顾客的平均等待时间和逗留时间。2021/6/1654计量数模提高班专题五模拟过程分析因为 Matlab的删除需要，队伍中至少要有两个人（可虚拟，将将来的加进来）。假设有一个顾客刚开始服务，在它服务期间，顾客仍会来。当他服务结束后，若没有等待顾客，时间推到下一个顾客到来，等待时间不增加。若有等待顾客，则第一个顾客离开队列，开始服务，所有等待的顾客的等待时间加到总的等待时间中去。模拟结束后，将总的等待时间除服务人数得平

47、均等待时间。2021/6/1655计量数模提高班专题五M/M/1模型流程图 初始化系统状态 第一个人接受服务 有人等吗 计算相关结果 结束 时间推到该人服务结束 同时他离开系统Y 时间推到下一个顾客到来 服务人数 到了吗N 服务中会有 人来吗 产生新到达顾客NNYY2021/6/1656计量数模提高班专题五 当模拟 100次得 Wq=9.0459,Ws=12.5612,而当模拟 1000次得 Wq=10.1294,Ws=13.1731,而从理论上应该是Wq=3/4/(1/3-1/4)=9,Ws=1/(1/3-1/4)=12，它们还是接近的。2021/6/1657计量数模提高班专题五 随机问题和

48、排队问题在数模竞赛中多次出现过。如“1997A题：零件的参数设计”，“2009B题：眼科病床的合理安排”，“2013A题车道被占用对城市道路通行能力的影响”，还有2014年美赛题目：除非超车否则靠右行驶。2009B题目是多队列多服务台，多种服务规则的排队模型，理论求解是不可能的，回归等其他方法也不行，模拟才是有效的解决方法。2013A题目也类似，只是顾客在队列上要交叉。另外：元胞机是一种专门的模拟方法，处理的对象就是排队等随机问题，只是在模拟上有独到之处。深入了解模拟可参阅它。2021/6/1658计量数模提高班专题五六、作业六、作业 1 两人约定下午1-3点在某处见面，设两人的到达分别服从分布U(1,3)和N(2,1)（若不在1-3 内，再产生随机数），且一人最多等另一人15分钟，求两人见面的概率。2 编程模拟顾客到达服从负指数分布（两顾客到达平均间隔=10），服务时间分别服从正态分布（均值为9，方差为4）和定长时间（T=9）的排队过程，求顾客平均等待时间和逗留时间。3(选做)，求积分的近似值，其中D是椭圆4x2+9y2=36的内部。2021/6/1659计量数模提高班专题五Thank you!2021/6/1660计量数模提高班专题五 结束语结束语若有不当之处，请指正，谢谢！若有不当之处，请指正，谢谢！