泊松分布与生灭过程

第二节顾客到达分布

7/28/20241系统的组成顾客服务机构顾客到达有先后服务时间有长短存在随机性7/28/20242要想预测在某一时刻将有多少顾客要求服务系统服务，或者预测某一顾客的服务时间将要延误多久这都是不可能的对单位时间内到达系统的顾客数和服务时间这两个随机变量进行概率的描述描述顾客到达和服务时间的方法，要求出单位时间内有K个顾客到达系统要求服务的概率，以及服务时间不少于某一时间长度的概率7/28/20243最简单流（泊松流）

流的平稳性对于任意的t≥0及Δt≥0，在时间区间(t,t+Δt)内有n个顾客到达的概率只与Δt有关，与时间区间的起点t无关。

当Δt充分小时，在(t,t+Δt)内有一个顾客到达的概率与Δt成正比，即其中，O(Δt)是当Δt→0时，关于Δt高阶无穷小，λ为单位时间内的顾客到达平均数。7/28/20244

流的无后效性

在时间轴上，互不相交的时间区段和内，顾客的到达数是相互独立的，即前一顾客的到达不影响后一顾客的到达。7/28/20245流的普遍性

在同一时刻，有两个及两个以上顾客到达的概率与有一个顾客到达的概率相比小到可以忽略的程度，即当Δt充分小时，在时间区间(t,t+Δt)内有2个及2个以上顾客到达的概率是关于的高阶无穷小。7/28/20246流的平稳性流的普遍性在区间(t,t+Δt)内没有顾客到达的概率7/28/20247在长为(t,t+Δt)的时间区间内，到达n个顾客的概率?设把长为Δt的时间区间分成m等分，每段长度为。若在dt内，有一个顾客到达，则称被“占着”，如果在dt内，没有顾客到达，则称为“空着”。被“占着”的概率近似为被“空着”的概率近似根据流的无后效性，在m个dt中，有顾客到达与没有顾客到达可以看成是m次独立的试验7/28/20248在长为(t,t+Δt)的时间区间内，到达n个顾客的概率?在m个dt中，有n个dt被顾客“占着”的概率利用二项定律7/28/20249dt0，m

7/28/202410符合最简单流（泊松流）的随机事件发生规律称为泊松分布单位时间发生n个随机时间的概率参数1个：λ—顾客的平均到达率思考：交叉口交通流量，排队车辆？7/28/202411泊松分布的另外一种表达方式——负指数分布若n=0在Δt的时间段内没有顾客达到的概率前后两次随机事件发生的时间间隔大于Δt7/28/202412负指数分布泊松分布在单位时间Δt内，发生n次随机事件的概率随机事件发生时间间隔大于单位时间Δt的概率随机事件发生时间间隔小于单位时间Δt的概率参数1个：λ—顾客的平均到达率7/28/202413如果顾客的到达过程服从最简单流，则顾客单位时间内的到达数服从泊松分布。如果顾客的到达过程服从最简单流，则顾客到达的时间间隔服从负指数分布。从本质上看，泊松分布与负指数分布是同一个过程的不同表现形式。7/28/202414第三节生灭过程7/28/202415研究系统内部状态变化的过程系统状态i状态i+1状态i-1在Δt时刻内发生两个或两个以上事件的概率为O(Δt)一个事件一个事件一、生灭过程定义Δt→0，O(Δt)→0如在Δt→0内，交叉口一条车道

到达两辆车的概率为O(Δt)→07/28/202416系统具有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内有一个顾客离开的概率7/28/2024173、在（t,t+Δt）内系统发生两次以上转移的概率为O(Δt)，即有2个以上顾客到达或离开的概率为

——普遍性条件只要排队系统的输入过程和服务过程符合泊松分布，排队过程符合生灭过程7/28/202418二、生灭过程状态转移图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)趋向于常数：系统达到稳定7/28/202419系统达到稳定后：每个状态转入率的期望值与转出率的期望值相等。对于状态i：转出率的期望值为转入率的期望值为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……P0P1P2Pi7/28/202420有对于S0转入转出转出转入对于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……P0P1P2Pi7/28/202421状态转移方程求解该方程，可以获得各状态对应的概率7/28/202422对于S0对于S1依次类推且有7/28/202423例：某排队系统：M/M/1/3/∞/FCFS，λ=2，μ=3。求解各状态对应的概率。首先，做出相应的状态转移图S0S1S2S3222333对于S0对于S1对于S27/28/202424生灭过程求解排队系统各状态概率过程建立状态转移图建立状态转移方程求解状态转移方程各状态转入率期望值与转出率期望值相等各状态概率7/28/202425作业：利用生灭过程求解以下排队系统各状态的概率。S0S1S2S32232437/28/202426第三节M/M/1排队系统顾客到达服从泊松分布—顾客到达率为λ服务过程服从泊松分布（负指数分布）—系统服务率为μ单通道，先到先服务最简单的M/M/1排队系统：M/M/1/∞/∞M/M/1/m/∞7/28/202427M/M/1/∞/∞排队系统系统容量无限、顾客源无限最基本的排队系统排队过程为生灭过程过程7/28/202428S0S1S2Si-1SiSi+1μμμμμμμλλλλλλλ…P0P1P2Pi…列状态转移方程组求各状态概率7/28/202429M/M/1/∞/∞排队系统各状态概率归结为无穷等比数列求和ρ<1，数列收敛P0=1-ρ

ρ>1，数列发散系统稳定系统不稳定称ρ为服务强度，若服务强度大于1，说明单位时间内到达的顾客数比完成服务的顾客数多，系统中排队长度越来越大，产生阻塞。7/28/202430利用排队系统各状态概率计算运行指标1、队长——系统中的顾客数量队长7/28/2024312、排队长——系统中等待的顾客数量通道数7/28/2024323、逗留时间——顾客在排队系统中的总时间李太勒公式前后2名顾客到达系统的时间间隔7/28/2024334、排队时间——顾客在排队系统中的等待时间李太勒公式前后2名顾客到达系统的时间间隔7/28/202434M/M/1/m/∞排队系统系统容量有限、顾客源无限7/28/202435P0P1P2S2S0S1SiSmμμμμμλλλλλ…Pi…Pm列状态转移方程组求各状态概率7/28/202436并不要求ρ<1。特别地，当ρ=1时，P0=1/(m+1)(ρ≠1)7/28/202437利用排队系统各状态概率计算运行指标1、队长——系统中的顾客数量队长7/28/2024382、排队长——系统中等待的顾客数量通道数7/28/2024393、逗留时间——顾客在排队系统中的总时间李太勒公式前后2名顾客到达系统的时间间隔7/28/202440有效到达率λe当排队长度未满容量时，平均到达率为λ当排队容量已满容量时，平均到达率为07/28/202441逗留时间7/28/2024424、排队时间——顾客在排队系统中的等待时间李太勒公式前后2名顾客到达系统的时间间隔7/28/202443作业汽车通过一检查站时进行验证。汽车按泊松分布到达检查站，平均间隔0.6分钟，验证时间平均为15秒（验证时间服从负指数分布）。请分析该排队系统，求该排队系统各状态对应的概率，以及队长、排队长、顾客逗留时间、顾客等待时间等运行指标。7/28/202444顾客的到达是服务参数λ的泊松分布；顾客的服务时间是服从参数为μ的负指数分布；有S个服务台，顾客按到达的先后次序接受服务。第四节M/M/S排队系统7/28/202445当顾客到达时，若有空闲的服务台就立即接受服务，若所有的服务台都忙着，则顾客排成一个队列等待服务。7/28/202446常见的M/M/S/∞/∞及M/M/S/m/∞两类7/28/202447M/M/S/∞/∞排队系统—标准M/M/S系统7/28/202448系统中个服务台的服务率均为μ

，于是整个服务机构的最大服务率为Sμ

。与M/M/1/∞/∞系统类似，只有当时，才能使服务系统达到稳态而不排成无限的队列。系统的服务强度7/28/202449当系统中只有一个顾客时，则有S-1个服务台空闲着，仅一个服务台在服务，这时的服务率为μ

，当系统有2个顾客时，就有2个服务台工作，其服务率为2μ

，…，当系统中有S个顾客时，则服务率达到最大值Sμ

，当系统中的顾客数超过S时，由于个服务台都忙着，其余顾客必须排队，这时的服务率仍为Sμ

7/28/202450M/M/1系统M/M/S系统7/28/202451M/M/S系统7/28/202452根据正则条件7/28/202453利用排队系统各状态概率计算运行指标1、排队长7/28/2024542、平均等候时间

7/28/2024553、逗留时间４、平均顾客数7/28/202456系统容量受限制、顾客源无限、先到先服务的M/M/S系统。该系统共有m-S个位置可供顾客排队。当顾客到达时，若系统饱和，即服务台都忙着，排队位置已排满，则后到的顾客立即离去，另求服务。因此，该系统中只可能有m+1个状态。

M/M/S/m/∞/∞排队系统7/28/202457与M/M/S/∞/∞系统的推导类似，可得M/M/S/m/∞系统的状态指标及运行指标。7/28/202458第五节排队服务系统的最优化问题排队系统设计最优化的目标在于使系统设施达到最大使用效益，或者说，在一定的质量指标下要求服务机构最为经济一般要求系统最优7/28/202459对于顾客来说，总是要求提高服务水平（如增设服务台数、加快服务时间）以减少排队费用，若要完全满足顾客的要求，则会导致服务机构过大，使用效率降低