泊松分布与生灭过程

2020/3/171第二节顾客到达分布2020/3/172系统的组成顾客服务机构顾客到达有先后服务时间有长短存在随机性2020/3/173要想预测在某一时刻将有多少顾客要求服务系统服务，或者预测某一顾客的服务时间将要延误多久这都是不可能的对单位时间内到达系统的顾客数和服务时间这两个随机变量进行概率的描述描述顾客到达和服务时间的方法，要求出单位时间内有K个顾客到达系统要求服务的概率，以及服务时间不少于某一时间长度的概率2020/3/174最简单流（泊松流）流的平稳性对于任意的t≥0及Δt≥0，在时间区间(t,t+Δt)内有n个顾客到达的概率只与Δt有关，与时间区间的起点t无关。当Δt充分小时，在(t,t+Δt)内有一个顾客到达的概率与Δt成正比，即其中，O(Δt)是当Δt→0时，关于Δt高阶无穷小，λ为单位时间内的顾客到达平均数。)(),(1tottttP2020/3/175流的无后效性在时间轴上，互不相交的时间区段和内，顾客的到达数是相互独立的，即前一顾客的到达不影响后一顾客的到达。21,tt43,tt)(4321tttt2020/3/176流的普遍性在同一时刻，有两个及两个以上顾客到达的概率与有一个顾客到达的概率相比小到可以忽略的程度，即当Δt充分小时，在时间区间(t,t+Δt)内有2个及2个以上顾客到达的概率是关于的高阶无穷小。2)(),(nntotttP2020/3/177)(),(1tottttP流的平稳性2)(),(nntotttP流的普遍性)(1),(0tottttP在区间(t,t+Δt)内没有顾客到达的概率2020/3/178在长为(t,t+Δt)的时间区间内，到达n个顾客的概率?设把长为Δt的时间区间分成m等分，每段长度为。若在dt内，有一个顾客到达，则称被“占着”，如果在dt内，没有顾客到达，则称为“空着”。被“占着”的概率近似为被“空着”的概率近似)(),(1tottttP)(tPnmtdt/)(1),(0tottttP根据流的无后效性，在m个dt中，有顾客到达与没有顾客到达可以看成是m次独立的试验2020/3/179在长为(t,t+Δt)的时间区间内，到达n个顾客的概率?)(tPn在m个dt中，有n个dt被顾客“占着”的概率利用二项定律nmnnmmnmtmtCnPtP1)()(2020/3/1710dt0，mnmnnmmnmtmtCtP1lim)(nmnmmtmtnnmmmm1!)1()2)(1(limnmmnmtmnmmmmmnt111lim)(！mmnmtnt1lim)(！tnnenttP！)()(tnent！)(2020/3/1711符合最简单流（泊松流）的随机事件发生规律称为泊松分布tnnenttP！)()(单位时间发生n个随机时间的概率参数1个：λ—顾客的平均到达率思考：交叉口交通流量，排队车辆？2020/3/1712泊松分布的另外一种表达方式——负指数分布tnnenttP！)()(若n=0在Δt的时间段内没有顾客达到的概率tetP)(0前后两次随机事件发生的时间间隔大于ΔttethP)(2020/3/1713tethP)(负指数分布tnnenttP！)()(泊松分布在单位时间Δt内，发生n次随机事件的概率随机事件发生时间间隔大于单位时间Δt的概率tethP1)(随机事件发生时间间隔小于单位时间Δt的概率参数1个：λ—顾客的平均到达率2020/3/1714如果顾客的到达过程服从最简单流，则顾客单位时间内的到达数服从泊松分布。如果顾客的到达过程服从最简单流，则顾客到达的时间间隔服从负指数分布。从本质上看，泊松分布与负指数分布是同一个过程的不同表现形式。2020/3/1715第三节生灭过程2020/3/1716研究系统内部状态变化的过程系统状态i状态i+1状态i-1在Δt时刻内发生两个或两个以上事件的概率为O(Δt)一个事件一个事件一、生灭过程定义Δt→0，O(Δt)→0如在Δt→0内，交叉口一条车道到达两辆车的概率为O(Δt)→02020/3/1717系统具有0,1,2,……个状态。在任何时刻，若系统处于状态i，并且系统状态随时间变化的过程满足以下条件，称为一个生灭过程：1、在（t,t+Δt）内系统由状态i转移到状态i+1的概率为λiΔt+O(Δt)——平稳性条件Δt内有一个顾客到达的概率2、在（t,t+Δt）内系统由状态i转移到状态i-1的概率为μiΔt+O(Δt)——平稳性条件Δt内有一个顾客离开的概率2020/3/17183、在（t,t+Δt）内系统发生两次以上转移的概率为O(Δt)，即有2个以上顾客到达或离开的概率为20)(nntP——普遍性条件只要排队系统的输入过程和服务过程符合泊松分布，排队过程符合生灭过程2020/3/1719二、生灭过程状态转移图S0S1S2Si-1SiSi+1Sk-1Skμ1μ2μ3μi-1μiμi+1μi+2μk-1μkλ0λ1λ2λi-2λi-1λiλi+1λk-2λk-1……状态顾客到达率系统服务率t→∞时，Pi(t)趋向于常数：系统达到稳定2020/3/1720系统达到稳定后：每个状态转入率的期望值与转出率的期望值相等。对于状态i：转出率的期望值为iiiiiiiPPP)(转入率的期望值为1111iiiiPPS0S1S2Si-1SiSi+1Sk-1Skμ1μ2μ3μi-1μiμi+1μi+2μk-1μkλ0λ1λ2λi-2λi-1λiλi+1λk-2λk-1……P0P1P2Pi2020/3/1721iiiP)(1111iiiiPP有对于S00011PP转入转出11kkkkPP转出转入对于SkS0S1S2Si-1SiSi+1Sk-1Skμ1μ2μ3μi-1μiμi+1μi+2μk-1μkλ0λ1λ2λi-2λi-1λiλi+1λk-2λk-1……P0P1P2Pi2020/3/1722iiiP)(1111iiiiPP状态转移方程求解该方程，可以获得各状态对应的概率2020/3/17230011PP0101PP对于S0对于S12200111)(PPP0101PP021011212PPP依次类推01102111PPPiiiiiiii且有kiiP012020/3/1724例：某排队系统：M/M/1/3/∞/FCFS，λ=2，μ=3。求解各状态对应的概率。首先，做出相应的状态转移图S0S1S2S3222333对于S0对于S10010132PPP002101121294PPPP对于S203278PP301iiP127894320000PPPP2020/3/1725生灭过程求解排队系统各状态概率过程建立状态转移图建立状态转移方程求解状态转移方程kiiP01各状态转入率期望值与转出率期望值相等各状态概率2020/3/1726作业：利用生灭过程求解以下排队系统各状态的概率。S0S1S2S32232432020/3/1727第三节M/M/1排队系统顾客到达服从泊松分布—顾客到达率为λ服务过程服从泊松分布（负指数分布）—系统服务率为μ单通道，先到先服务最简单的M/M/1排队系统：M/M/1/∞/∞M/M/1/m/∞2020/3/1728M/M/1/∞/∞排队系统系统容量无限、顾客源无限最基本的排队系统排队过程为生灭过程过程2020/3/1729S0S1S2Si-1SiSi+1μμμμμμμλλλλλλλ…P0P1P2Pi…列状态转移方程组求各状态概率01PP001PPP0111PPPPiiiiii1)1(032Pi01iiP2020/3/17301)1(032PiM/M/1/∞/∞排队系统各状态概率归结为无穷等比数列求和ρ1，数列收敛1110PP0=1-ρρ1，数列发散系统稳定系统不稳定称ρ为服务强度，若服务强度大于1，说明单位时间内到达的顾客数比完成服务的顾客数多，系统中排队长度越来越大，产生阻塞。2020/3/1731利用排队系统各状态概率计算运行指标1、队长——系统中的顾客数量0iiSiPL队长)10(1)2()32()1(3232320100iiiiiiiii2020/3/17322、排队长——系统中等待的顾客数量1)1(iiqiPL通道数11)1(2011PLPPiSiiii2020/3/17333、逗留时间——顾客在排队系统中的总时间)1/(SSWL李太勒公式前后2名顾客到达系统的时间间隔/SSLW2020/3/17344、排队时间——顾客在排队系统中的等待时间)1/(qqWL李太勒公式前后2名顾客到达系统的时间间隔/qqLW2020/3/1735M/M/1/m/∞排队系统系统容量有限、顾客源无限2020/3/1736P0P1P2S2S0S1SiSmμμμμμλλλλλ…Pi…Pm列状态转移方程组求各状态概率01PP001PPP0111PPPPiiiiiimiiP011)1(032Pmi2020/3/17371)1(032Pmi并不要求ρ1。1201111mmP特别地，当ρ=1时，P0=1/(m+1)(ρ≠1)2020/3/1738利用排队系统各状态概率计算运行指标1、队长——系统中的顾客数量0miiSiPL队长21010110001100)1()1(1)11()()(mmmmiimiimimiiimmPddPddPddPiPPi112mLS2020/3/17392、排队长——系统中等待的顾客数量miiqiPL1)1(通道数)1(011PLPPiSmimiii2020/3/17403、逗留时间——顾客在排队系统中的总时间)1/(SSWL李太勒公式前后2名顾客到达系统的时间间隔/SSLW2020/3/1741有效到达率λe011)1(imimiiiePPP当排队长度未满容量时，平均到达率为λ当排队容量已满容量时，平均到达率为02020/3/1742逗留时间eSSLW/2020/3/17434、排队时间——顾客在排队系统中的等待时间)1/(qqWL李太勒公式前后2名顾客到达系统的时间间隔eqqLW/2020/3/1744作业汽车通过一检查站时进行验证。汽车按泊松分布到达检查站，平均间隔0.6分钟，验证时间平均为15秒（验证时间服从负指数分布）。请分析该排队系统，求该排队系统各状态对应的概率，以及队长、排队长、顾客逗留时间、顾客等待时间等运行指标。2020/3/1745顾客的到达是服务参数λ的泊松分布；顾客的服务时间是服从参数为μ的负指数分布；有S个服务台，顾客按到达的先后次序接受服务。第四节M/M/S排队系统20