排队论简介

一、概率论回顾随机变量离散型随机变量概率分布和概率分布图数学期望和方差常见离散型随机变量的概率分布二点分布?二项式分布?Poisson分布?1.1、随机变量与概率分布pXPpXP1)0(,)1(),,1,0(,)(nkqpCkXPknkkn)(,)(0;,1,0!)(XDXEkekkXPk泊松分布的定义及图形特点,,,,,!)(210kkekXPk设随机变量X所有可能取的值为0,1,2,…,且概率分布为：其中0是常数,则称X服从参数为的泊松分布,记作X~P().λλλ泊松分布的图形特点：X~P()λ历史上，泊松分布是作为二项分布的近似，于1837年由法国数学家泊松引入的.在实际中，许多随机现象服从或近似服从泊松分布.二项分布与泊松分布泊松定理：,,2,1,0,!)1(limkkeppCkknnknknn设是一个正整数，，则有由此可知设随机变量Xn~B(n,p),(n＝0,1,2,…),且n很大，p很小，记=np，则,...2,1,0,!}{kekkXPknpnPoisson分布可以作为大量试验中稀有事件出现的频数的概率分布数学模型。如地震、火山爆发、特大洪水、意外事故等等某电话交换台收到的电话呼叫数；到某机场降落的飞机数;一个售货员接待的顾客数;一台纺纱机的断头数;…一放射性源放射出的粒子数；例如这些随机变量都有如下特点：都取正整数，且与时间间隔长度关；取值概率只与时间间隔的长度有关，而与从哪个时刻开始算起没有关系；在互不相交的时间间隔内，彼此没有影响。在自然界和人们的现实生活中,经常要遇到在随机时刻出现的某种事件.我们把在随机时刻相继出现的事件所形成的序列,叫做随机事件流.若事件流具有平稳性、无后效性、普通性，则称该事件流为泊松事件流（泊松流）.泊松分布产生的一般条件下面简要解释平稳性、无后效性、普通性.平稳性:在任意时间区间内[t,t+t)，事件发生k次(k≥0)的概率只依赖于区间长度t，而与区间起点t无关.无后效性:普通性:在不相交的时间区间内，事件的发生是相互独立的，前一区间内发生的事件数不影响到后面区间事件的发生数的概率.在足够短的时间内，事件出现两次或两次以上的概率可忽略不计.对泊松流，在任意时间间隔(0,t)内,事件(如交通事故)出现的次数服从参数为t的泊松分布.称为泊松流的强度.λλ随机变量连续型随机变量概率密度函数概率分布函数数学期望和方差常见连续型随机变量的概率分布均匀分布指数分布？正态分布？k阶爱尔朗分布？一、随机变量与概率分布2/1)(,/1)()0(0,00,)(XDXExxexax随机变量X为时间间隔，如顾客到达的时间间隔、电话呼叫的时间、产品的寿命等。密度函数),(~)(,)()0,(,21)(222)(22NXXDXERRxexax随机变量X为时间(长度），如产品的尺寸、重量、测量误差等。密度函数指数分布密度函数0fort00fortαetfαtT)(均值1)(TE方差21)(TVar随机变量T分布函数αte1t)P(TfT(t)t1)(TE指数分布性质1)()0(ttTtPtTPfT(t)tttfT(t)是一个严格下降函数指数分布性质2)()/(tTPtTttTP无后效性)()()()()()/()()(tTPeeeeeetTPttTPtTPtTandttTPtTttTPttttttt取值概率只与时间间隔的长度有关，而与从那个时刻开始算起没有关系；不管多长时间(t)已经过去，逗留时间的概率分布与下一个事件的相同.T：元件寿命。元件已使用小时的条件下，一共能用的概率＝从开始算起至少能用的概率。即元件对于已使用小时没有记忆。（无记忆性）tttttPoisson过程与Poisson分布定理1：设为时间内到达系统的顾客数则为Poisson过程的充要条件是)(tNt,0}0),({ttN,...2,1!)(})({nentntNPtn服从参数为的Piosson分布ttNDttNE)(,)()(tNtPoisson过程与负指数分布定理2：设为时间内到达系统的顾客数则为参数为的Poisson过程的充要条件是相继到达的时间间隔T服从相互独立的参数为的负指数分布。)(tNt,0}0),({ttN0,00,)(ttetatT：第n个顾客与第n-1个顾客到达的时间间隔；nX1T2TnT1nT1nT0TnXPoisson过程与Poisson分布的关系：定理1：设为时间内到达系统的顾客数则为Poisson过程的充要条件是)(tNt,0}0),({ttN,...2,1!)(})({nentntNPtn定理2：设为时间内到达系统的顾客数则为参数为的Poisson过程的充要条件是相继到达的时间间隔T服从相互独立的参数为的负指数分布。)(tNt,0}0),({ttN0,00,)(ttetatT对于Poisson流：——单位时间平均到达的顾客数——顾客相继到达的平均间隔时间/1二、排队论的基本知识2.1排队模型2.2排队系统的组成和特征排队论研究的内容性态问题:排队系统的概率规律,如队长分布,等待时间分布等.最优化问题:排队系统的最优设计.统计推断:判定排队系统的类型.顾客源2.1、排队模型排队系统排队结构服务机构排队规则服务规则接受服务后离去——排队系统的的一般表示服务机构服务台(a)一个队列、单服务台（阶段）服务台1服务台2(b)一个队列、s个服务阶段服务机构服务台1服务台2服务机构(c)一个队列、s个服务台一个服务阶段服务台3服务台4服务台1服务台2服务机构(d)s个队列、s个服务阶段服务台3服务台4服务台1服务台2:1–2–4:2–4–3:3–2–1–4服务机构(e)混合型排队结构服务台(f)一个队列服务台(g)s个队列输入过程顾客总体:有限,无限.顾客到达方式:单个,成批.顾客到达间隔时间:确定的、随机的.顾客到达的独立性:独立,不独立.输入过程的平稳性:与时间无关(平稳的),与时间有关(非平稳的).2.2、排队系统的组成和特征顾客到达时间间隔的分布:：第n个顾客与第n-1个顾客到达的时间间隔；nXnT：第n个顾客到达的时刻；设nTTT100,,2,1,1nTTXnnn令1T2TnT1nT1nT0TnX顾客到达时间间隔的分布:假定是独立同分布，分布函数为，排队论中常用的有两种：}{nX)(tA}{nX（2）最简流（即Poisson流）（M）：顾客到达时间间隔为独立的，服从负指数分布，其密度函数为（1）定长分布（D）：顾客到达时间间隔为确定的。000)(ttetat因为负指数分布具有无后效性（即Markov性）排队及排队规则即时制(损失制)等待制先到先服务:FCFS后到先服务:LCFS随机服务优先权服务：PS队容量:有限,无限;有形,无形.队列数目:单列,多列.服务机构服务员数量:无,单个,多个.队列与服务台的组合服务方式:单个顾客,成批顾客.服务时间:确定的,随机的.服务时间和到达间隔时间至少一个是随机的.服务时间分布是平稳的.服务时间分布:设某服务台的服务时间为V，其密度函数为b（t），常见的分布有：（1）定长分布（D）：每个顾客接受服务的时间是一个确定的常数。（2）负指数分布（M）：每个顾客接受服务时间相互独立，具有相互的负指数分布：其中，为一常数。000)(ttetbt0μ--单位时间平均服务完成的顾客数1/μ--每个顾客的平均服务时间符号表示:X/Y/ZX–顾客到达间隔时间分布Y--服务时间分布Z--服务台个数X,Y可以是:M--负指数分布D--确定性的Ek--k阶Erlang分布GI--一般相互独立的到达时间间隔分布G--一般(General)时间分布排队系统的分类扩展符号表示:X/Y/Z/A/B/CA--系统容量B--顾客源中顾客的数量C--服务规则:FCFS,LCFS,等等.若省略后三项，即是指下面的情形：X/Y/Z///FCFS例：M/M/s/K表示？已知:顾客到达间隔时间分布,服务时间分布.求:队长:Ls--系统中的顾客数.排队长(队列长):Lq--队列中的顾客数.Ls=Lq+正在接受服务的顾客数逗留时间:WS--顾客在系统中的停留时间等待时间:Wq--顾客在队列中的等待时间.WS=Wq+服务时间忙期,损失率,服务强度.排队问题的求解三.单服务台负指数分布排队系统分析3.1M/M/1模型3.2M/M/1/N/模型(即系统的容量有限)3.3M/M/1//m模型（即顾客源为有限）顾客源排队系统排队结构服务机构排队规则服务规则接受服务后离去3.1M/M/1模型无限输入过程服从参数为的Poisson过程单队队长无限先到先服务服务时间服从参数为的负指数分布生灭过程求解：np:系统达到平稳后，系统有n个顾客的概率。1n0)(0n01110nnnPPPPP平衡方程：1n)1(10nnPP1:令，且当时01102101......,...2,1,ppCnpCpnnnnnnnnn其中关于的几点说明：)1(/1/1(2)01(3)p顾客平均到达率顾客平均服务率一个顾客服务时间一个顾客到达时间——服务强度,1)4(即顾客的顾客平均到达率小于顾客平均服务率时，系统才能达到统计平稳。•系统中至少有一个顾客的概率；•服务台处于忙的状态的概率；•反映系统繁忙程度计算有关指标101......)2(...)32()1(3232321n0nsnnsLnnPL队长队列长1)1()1(201n10nssnnnnqLPLPnPPnL计算有关指标逗留时间:可以证明,Ws服从参数为μ-λ的负指数分布.则:等待时间1sW1sqWW服务计算有关指标计算有关指标Little公式（相互关系）qsqsqqssLL小结1sWqWqLsL平均服务时间平均在忙的服务台数/正在接受服务的顾客数有效到达率平均忙期B,忙期出现的概率平均闲期I,闲期出现的概率(1-)忙期B:闲期I=:(1-)平均闲期I=1/闲期的分布与顾客到达时间间隔的相同----服从参数为的负指数分布计算有关指标忙期与闲期WHY?1-P0=平均忙期B,忙期出现的概率平均闲期I,闲期出现的概率(1-)忙期B:闲期I=:(1-)平均闲期I=1/平均忙期B=(/(1-))/=1/(-)计算有关指标忙期与闲期与逗留时间Ws相同!!!?4.1标准的M/M/c模型（M/M/c//）4.2标准的M/M/c/N/型4.3标准的M/M/c//m模型多服务台负指数分布排队系统分析规定：各服务台工作是相互独立的，且平均服务率相同，均为。整个服务机构的平均服务率为：c(当nc)，n(当nc);记=/,s=/c=/c为服务系统的平均利用率当/c1时，不会排成无限队列。4.1标准的M/M/c模型（M/M/c//）例如：