第五讲 排队论模型与蒙特卡罗仿真2010-5-16

1--基本原理、MATLAB实现及案例分析排队论模型与蒙特卡罗仿真2讲座提纲•一引例•二排队现象•三排队论的研究方法•四蒙特卡罗仿真原理•五仿真例子与分析•六作业3一引例•1到银行取钱，发现前面有几十个人在排着队，你掉头就走：不能忍受啊！怎么不多开几家银行、再增加几个服务窗口啊！假如你是相关人员，你觉得应根据什么来决定是否需要开设新的银行或增加新的服务窗口——要知道这次让你心烦具有随机性（偶然性）啊。•2银行一般都有几个服务窗口，过去是顾客每个窗口分别排队等待服务，而现在几乎都改为叫号制，这相当于多个窗口只排一队的服务规则。银行为什么要这么做?有什么好处？4排队是我们日常生活中常见的现象，如：•上、下班搭乘公共汽车；•顾客到商店购买物品；•病员到医院看病；•学生去食堂就餐等出现的排队和等待服务现象。二排队现象5排队可以是有形的，也可以是无形的。如几个顾客打电话到出租车站要车，如果出租车站无足够车辆，则部分顾客只得在要车处等待，他们分散在不同地方，形成一个无形的排队序列。排队论就是研究排队现象及其规律的一门学科，是运筹学的一个分支。如同数学的特质那样，排队论研究的内容比我们感觉中的排队现象要广泛得多，它是研究那些本质上都有排队特征的一类现象。具体表现在：6排队的不一定是人，也可以是物。例如：生产线上等待加工的原料、半成品；因故障停止运转等待修理的机器等。7上述问题虽互不相同，但却都有要求得到某种服务的人或物以及提供服务的人或机构。排队论里把要求服务的对象统称为“顾客”,提供服务的人或机构称为“服务台”或“服务员”。8不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图2-1至图2-3。图2-1单服务台排队系统9图2-2单队列——S个服务台并联的排队系统图2-3S个队列——S个服务台的并联排队系统10面对拥挤现象，人们总希望尽量设法减少排队，通常的做法是增加服务设施。但是增加设施的数量越多，人力、物力的支出就越大，同时会出现空闲浪费。如果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响。11顾客排队时间的长短与服务设施规模的大小，就构成了随机服务系统中的一对矛盾。如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾。这就是随机服务系统理论——排队论所要研究解决的问题。12排队结构服务机构顾客源顾客到达排队规则服务规则离去图1排队系统示意图3.1排队系统的组成与特征排队系统一般有三个基本组成部分：1.输入过程；2.排队规则；3.服务机构。三排队论的研究方法13输入即顾客的到达，可有下列情况：1）顾客源可能是有限的，也可能是无限的。2）顾客是成批到达或是单个到达。3）顾客到达间隔时间可能是随机的或确定的。4）顾客到达可能是相互独立或关联的。所谓独立就是以前顾客的到达对以后顾客的到达无影响。5）输入过程可以是平稳的（stationary），也可以是非平稳的。输入过程平稳的指顾客相继到达的间隔时间分布和参数（均值、方差）与时间无关；非平稳的则与时间相关。3.1.1输入过程14分为损失制、等待制、混合制三大类。(1)损失制指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号。3.1.2.排队规则15(2)等待制当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。例如，排队等待售票，故障设备等待维修等。等待制中，服务台在选择顾客进行服务时，常有如下四种规则：先到先服务（FCFS）按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形。此外还有后到先服务（LCFS），随机服务（RAND）和优先权服务（PR）三种情形。16(3)混合制．这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：①队长有限。当排队等待服务顾客人数超过规定数量时，后来顾客就自动离去，另求他处服务。如水库的库容、旅馆的床位等都是有限的。另两种情况指等待时间和逗留时间限制的情形，略去。一般的，损失制和等待制可认为是混合制的两种极端特殊情形。173.1.3服务机构1）服务机构可以是单服务员和多服务员服务，这种服务形式与队列规则联合后形成了多种不同队列，不同形式的排队服务机构。如前图2-1到2-3：2)服务方式分为单个顾客服务和成批顾客服务。3)服务时间分为确定型和随机型。4)服务时间的分布在这里我们假定是平稳的。18上述特征中最主要的、影响最大的是：•顾客相继到达的间隔时间分布•服务时间的分布•服务台数D.G.Kendall在1953提出了分类法，称为Kendall记号(适用于并列服务台)即：X/Y/Z，式中：X——顾客相继到达间隔时间分布。M—负指数分布Markov，D—确定型分布Deterministic，Ek—K阶爱尔朗分布Erlang，3.2排队系统的描述符号与模型分类19GI—一般相互独立随机分布(GeneralIndependent)，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，指顾客到达为泊松过程，服务时间为负指数分布，单台，无限容量，无限源，先到先服务的排队系统模型。203.3排队论研究的基本问题1.排队系统的统计推断:即判断一个给定的排队系统符合于哪种模型，以便根据排队理论进行研究。2.系统性态问题:即研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布和忙期分布等统计指标,包括了瞬态和稳态两种情形。3.最优化问题：即包括最优设计(静态优化)，最优运营（动态优化）。21求解一般排队系统问题的目的主要是通过研究排队系统运行的效率指标，估计服务质量，确定系统的合理结构和系统参数的合理值，以便实现对现有系统合理改进和对新建系统的最优设计等。排队问题的一般步骤：1.确定或拟合排队系统顾客到达的时间间隔分布和服务时间分布。2.研究分析排队系统理论分布的概率特征。3.研究系统状态的概率。系统状态是指系统中顾客数。状态概率用Pn(t)表示,即在t时刻系统中有n个顾客的概率，也称瞬态概率。22求解状态概率Pn(t)方法是建立含Pn(t)的微分差分方程，通过求解微分差分方程得到系统瞬态解，由于瞬态解一般求出确定值比较困难，即便求得一般也很难使用。因此常常使用它的极限(如果存在的话)：nttnp)(plim稳态的物理意义图，系统的稳态一般很快都能达到，但实际中达不到稳态的现象也存在。要注意的是求稳态概率Pn并不一定求t→∞的极限,只需求Pn’(t)=0。过渡状态稳定状态pnt图3排队系统状态变化示意图称为稳态(steadystate)解，或称统计平衡状态(StatisticalEquilibriumState)的解。234.根据排队系统对应的理论模型求用以判断系统运行优劣的基本数量指标的概率分布或特征数。数量指标主要包括:(1)平均队长（Ls）:系统中的顾客数。平均队列长（Lg）:系统中排队等待服务的顾客数。(2)平均逗留时间(Ws):指一个顾客在系统中的停留时间。平均等待时间(Wg):一个顾客在系统中排队等待的时间。(3)忙期：指从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度。（忙期和一个忙期中平均完成服务顾客数都是衡量服务机构效率的指标，忙期关系到工作强度）243.4理论分布tnnenttP!)(}{式中λ为常数(λ0)，称X服从参数为λ的泊松分布，若在上式中引入时间参数t，即令λt代替λ，则有：1.泊松分布在概率论中，我们曾学过泊松分布，设随机变量为X，则有：{}!nePXnnn=0,1,2,…（1）与时间有关的随机变量的概率，是一个随机过程，即泊松过程。t0，n=0,1,2,…（2）25})()({},{1221ntNtNPttPn（t2t1，n≥0）若设N(t)表示在时间区间[0,t)内到达的顾客数(t0),Pn(t1,t2)表示在时间区间[t1,t2)(t2t1)内有n(≥0)个顾客到达的概率。即：在一定的假设条件下顾客的到达过程就是一个泊松过程。当Pn(t1,t2)符合下述三个条件时，顾客到达过程就是泊松过程(顾客到达形成普阿松流)。26①无后效性：各区间的到达相互独立,即Markov性。.......t0t1t2…tn-1tn}|)({}|)({11112211)()(,...,)(,)(nnnnxtxnxtxxtxxtxnntxPntxP也就是说过程在t+Δt所处的状态与t以前所处的状态无关。②平稳性：即对于足够小的Δt，有：)()(tttttP，1普阿松流具有如下特性：在[t,t+Δt]内有一个顾客到达的概率与t无关,而与Δt成正比。27③普通性：对充分小的Δt,在时间区间（t,t+Δt）内有2个或2个以上顾客到达的概率是一高阶无穷小.由此知，在(t，t+Δt)区间内没有顾客到达的概率为：)(1),(0tottttP令t1=0,t2=t,则P(t1,t2)=Pn(0,t)=Pn(t)λ0是常数，它表示单位时间到达的顾客数，称为概率强度。2)(),(nntotttP即P0+P1+P≥2=128其概率密度函数为：tTTedtdF)t(ft02.负指数分布当输入过程是泊松流时，我们研究两顾客相继到达的时间间隔的概率分布。设T为时间间隔，分布函数为FT（t），则：FT（t）=P{T≤t}此概率等价于在[0，t）区间内至少有1个顾客到达的概率。tTetPtF1)(1)(0∴t0tetP)(0∵没有顾客到达的概率为：(由（5）式而来)间隔：间隔：间隔对分布函数微分29λ表示单位时间内顾客平均到达数。1/λ表示顾客到达的平均间隔时间。可以证明，间隔时间T独立且服从负指数分布与顾客到达形成泊松流是等价的。对顾客的服务时间：系统处于忙期时两顾客相继离开系统的时间间隔，一般地也服从负指数分布，设：即T服从负指数分布，它的期望及方差为：1][TE21][TVar接受服务，然后离开服务时间的分布：30其中：μ表示单位时间内能被服务的顾客数，即平均服务率。1/μ表示一个顾客的平均服务时间。tetF1)(tetf)(，则令，则ρ称为服务强度。一般的，要设ρ1（否则队列会无限，永远达不到稳态）31对排队模型，在给定输入和服务条件下，主要研究系统的下述运行指标：(1)系统的平均队长Ls(期望值)和平均队列长Lq(期望值)；(2)系统中顾客平均逗留时间Ws与队列中平均等待时间Wq；本节只研究M/M/1模型.3.5M/M/1模型研究32标准的M/M/1模型（M/M/1/∞/∞/FCFS）系统中有n个顾客1.稳态概率Pn的计算在任意时刻t，状态为n的概率Pn(t)（瞬态概率），它决定了系统的运行特征。已知顾客到达服从参数为λ的泊松过程，服务时间服从参数为μ的负指数分布。现仍然通过研究区间[t，t+Δt）的变化来求解。在时刻t+Δt，系统中有n个顾客不外乎有下列四种情况（[t，t+Δt）内到达或离开2个以上没列入）。？33区间(t,t+Δt)情况时刻t的顾客到达离去时刻t+Δt的顾客(t,t+Δt)的概率[0,t+Δt]的概率An××n1-λΔt+O(Δt)1-μΔt+O(Δt)Pn(1-λΔt+O(Δt))·（1-μΔt+O(Δt)）Bn+1×√n1-λΔt+O