泊松分布与生灭过程讲课适用.ppt

第二节第二节 顾客到达分顾客到达分布布1优选课堂系统的组成系统的组成顾客顾客服务机构服务机构顾客到达有先后顾客到达有先后服务时间有长短服务时间有长短存在随机性2优选课堂v要想预测在某一时刻将有多少顾客要求服务系统服务，或者预测某一顾客的服务时间将要延误多久这都是不可能的 v对单位时间内到达系统的顾客数和服务时间这两个随机变量进行概率的描述v描述顾客到达和服务时间的方法，要求出单位时间内有K个顾客到达系统要求服务的概率，以及服务时间不少于某一时间长度的概率 3优选课堂最简单流（泊松流） v 流的平稳性Ø对于任意的t≥0及Δt≥0，在时间区间(t,t+Δt)内有n个顾客到达的概率只与Δt有关，与时间区间的起点t无关 当Δt充分小时，在(t,t+Δt)内有一个一个顾客到达的概率与Δt成正比，即其中，O(Δt)是当Δt →0时，关于Δt高阶无穷小，λ为单位时间内的顾客到达平均数4优选课堂v 流的无后效性 v在时间轴上，互不相交的时间区段 和 内，顾客的到达数是相互独立的，即前一顾客的到达不影响后一顾客的到达。

5优选课堂v流的普遍性 v在同一时刻，有两个及两个以上顾客到达的概率与有一个顾客到达的概率相比小到可以忽略的程度，即当Δt充分小时，在时间区间(t,t+Δt)内有2个及2个以上顾客到达的概率是关于的高阶无穷小6优选课堂流的平稳性流的普遍性在区间(t,t+Δt)内没有顾客到达的概率 7优选课堂在长为(t,t+Δt)的时间区间内，到达n个顾客的概率 ?v设把长为Δt的时间区间分成m等分，每段长度为 若在dt内，有一个顾客到达，则称被“占着”，如果在dt内，没有顾客到达，则称为“空着”u被“占着”的概率近似为u被“空着”的概率近似根据流的无后效性，在m个dt中，有顾客到达与没有顾客到达可以看成是m次独立的试验 8优选课堂在长为(t,t+Δt)的时间区间内，到达n个顾客的概率 ?在在m m个个dtdt中，有中，有n n个个dtdt被顾客被顾客“占着占着”的概率的概率 利用二项定律 9优选课堂dt0，m 10优选课堂符合最简单流（泊松流）的随机事件发生规律称为泊松分布泊松分布单位时间发生n个随机时间的概率参数1个：λ—顾客的平均到达率思考：思考：交叉口交通流量，排队车辆？交叉口交通流量，排队车辆？11优选课堂泊松分布泊松分布的另外一种表达方式的另外一种表达方式——负指数分布负指数分布若n=0在在Δt的时间段内没有顾客达到的概率的时间段内没有顾客达到的概率前后两次随机事件发生的时间间隔大于Δt12优选课堂负指数分布负指数分布泊松分布泊松分布在单位时间在单位时间Δt内，发生内，发生n次随机事件的概率次随机事件的概率随机事件发生时间间隔随机事件发生时间间隔大于单位时间大于单位时间ΔΔt t的概率的概率随机事件发生时间间隔随机事件发生时间间隔小于单位时间小于单位时间ΔΔt t的概率的概率参数参数1个：个：λλ——顾客的平均到达率顾客的平均到达率13优选课堂v如果顾客的到达过程服从最简单流，则顾客单位时间内的到达数服从泊松分布。

v如果顾客的到达过程服从最简单流，则顾客到达的时间间隔服从负指数分布v从本质上看，泊松分布与负指数分布是同一个过程的不同表现形式14优选课堂第三节第三节 生灭过程生灭过程15优选课堂v研究系统内部状态变化的过程研究系统内部状态变化的过程系统状态系统状态i i状态状态i+1i+1状态状态i-1i-1在在ΔΔt t时刻内发生两个或两个以上时刻内发生两个或两个以上事件的概率为事件的概率为O(O(ΔΔt)t)一个事件一个事件一个事件一个事件一、生灭过程定义一、生灭过程定义ΔΔt→0t→0，， O(O(ΔΔt) →0t) →0如在如在ΔΔt→0t→0内，交叉口一条车道内，交叉口一条车道 到达两到达两辆车的概率为辆车的概率为O(O(ΔΔt) →0t) →016优选课堂 系统具有系统具有0,1,2,0,1,2,……个状态在任何时刻，若个状态在任何时刻，若系统处于状态系统处于状态i i，并且系统状态随时间变化的过，并且系统状态随时间变化的过程满足以下条件，称为一个生灭过程：程满足以下条件，称为一个生灭过程：1 1、在（、在（t,t+t,t+ΔΔt t）内系统由状态）内系统由状态i i转移到状态转移到状态i+1i+1的的概率为概率为λλi iΔΔt+O(t+O(ΔΔt)t)——平稳性条件平稳性条件ΔΔt t内有一个顾客到达的概率内有一个顾客到达的概率2 2、在（、在（t,t+t,t+ΔΔt t）内系统由状态）内系统由状态i i转移到状态转移到状态i-1i-1的的概率为概率为μi iΔΔt+O(t+O(ΔΔt)t)——平稳性条件平稳性条件ΔΔt t内有一个顾客离开的概率内有一个顾客离开的概率17优选课堂3 3、在（、在（t,t+t,t+ΔΔt t）内系统发生两次以上转移的概率）内系统发生两次以上转移的概率为为O(O(ΔΔt)t)，即有，即有2 2个以上顾客到达或离开的概率为个以上顾客到达或离开的概率为 ——普遍性条件普遍性条件只要排队系统的输入过程和服务过程符合泊松分布，只要排队系统的输入过程和服务过程符合泊松分布，排队过程符合生灭过程排队过程符合生灭过程18优选课堂二、生灭过程状态转移图二、生灭过程状态转移图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 t→→∞∞时，时，P Pi i(t)(t)趋向于常数：趋向于常数：系统达到稳定系统达到稳定19优选课堂v系统达到稳定后：每个状态转入率的期系统达到稳定后：每个状态转入率的期望值与转出率的期望值相等。

望值与转出率的期望值相等对于状态对于状态i 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……P P0 0P P1 1P P2 2P Pi i20优选课堂有有对于对于S S0 0转入转入转出转出转出转出转入转入对于对于S Sk kS0S1S2Si-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……P P0 0P P1 1P P2 2P Pi i21优选课堂状态转移方程状态转移方程求解该方程，可以获得各状态对应的概率求解该方程，可以获得各状态对应的概率22优选课堂对于对于S S0 0对于对于S S1 1依次类推依次类推且有且有23优选课堂例：例：某排队系统：某排队系统： M/M/1/3/∞/FCFSM/M/1/3/∞/FCFS，，λλ=2=2，，μμ=3=3求解各状态对应的概率求解各状态对应的概率Ø首先，做出相应的状态转移图首先，做出相应的状态转移图S0S1S2S3222333对于对于S S0 0对于对于S S1 1对于对于S S2 224优选课堂生灭过程求解排队系统各状态概率过程生灭过程求解排队系统各状态概率过程建立状态转移图建立状态转移图建立状态转移方程建立状态转移方程求解状态转移方程求解状态转移方程各状态转入率期望值各状态转入率期望值与转出率期望值相等与转出率期望值相等各状态概率各状态概率25优选课堂作业：作业：利用生灭过程求解以下排队系统各状态的概率。

利用生灭过程求解以下排队系统各状态的概率S0S1S2S32 22 23 32 24 43 326优选课堂第三节第三节 M/M/1M/M/1排队系统排队系统Ø顾客到达服从泊松分布顾客到达服从泊松分布—顾客到达率为顾客到达率为λØ服务过程服从泊松分布（负指数分布）服务过程服从泊松分布（负指数分布）—系统服务率为系统服务率为μØ单通道，先到先服务单通道，先到先服务最简单的最简单的M/M/1M/M/1排队系统：排队系统：M/M/1/M/M/1/∞/∞∞/∞M/M/1/M/M/1/m/∞m/∞27优选课堂M/M/1/∞/∞M/M/1/∞/∞排队系统排队系统系统容量无限、顾客源无限系统容量无限、顾客源无限最基本的排队系统最基本的排队系统排队过程为生灭过程过程排队过程为生灭过程过程28优选课堂S0S1S2Si-1SiSi+1μμμμμμμλλλλλλλ…P P0 0P P1 1P P2 2P Pi i…列状态转移方程组求各状态概率列状态转移方程组求各状态概率29优选课堂M/M/1/∞/∞M/M/1/∞/∞排队系统各状态概率排队系统各状态概率归结为无穷等比数列求和归结为无穷等比数列求和ρ<1<1，数列收敛，数列收敛P P0 0=1-=1-ρρ ρ>1 1，数列发散，数列发散系统稳定系统稳定系统不稳定系统不稳定称称ρρ为服务强度，若服务强度大于为服务强度，若服务强度大于1 1，说明单位时间内到达的顾客，说明单位时间内到达的顾客数比完成服务的顾客数多，系统中排队长度越来越大，产生阻塞。

数比完成服务的顾客数多，系统中排队长度越来越大，产生阻塞30优选课堂利用排队系统各状态概率计算运行指标利用排队系统各状态概率计算运行指标v1、队长、队长——系统中的顾客数量系统中的顾客数量队长队长31优选课堂v2、排队长、排队长——系统中等待的顾客数量系统中等待的顾客数量通道数通道数32优选课堂v3、逗留时间、逗留时间——顾客在排队系统中的总时间顾客在排队系统中的总时间李太勒公式李太勒公式前后前后2 2名顾客到达系统的时间间隔名顾客到达系统的时间间隔33优选课堂4、排队时间、排队时间——顾客在排队系统中的等待时间顾客在排队系统中的等待时间李太勒公式李太勒公式前后前后2 2名顾客到达系统的时间间隔名顾客到达系统的时间间隔34优选课堂M/M/1/m/∞M/M/1/m/∞排队系统排队系统系统容量有限、顾客源无限系统容量有限、顾客源无限35优选课堂P P0 0P P1 1P P2 2S2S0S1SiSmμμμμμλλλλλ…P Pi i…P Pm m列状态转移方程组求各状态概率列状态转移方程组求各状态概率36优选课堂并不要求并不要求ρρ<1<1特别地，当特别地，当ρρ=1=1时，时，P P0 0=1/(m+1)=1/(m+1)(ρ≠≠1)1)37优选课堂利用排队系统各状态概率计算运行指标利用排队系统各状态概率计算运行指标v1、队长、队长——系统中的顾客数量系统中的顾客数量队长队长38优选课堂v2、排队长、排队长——系统中等待的顾客数量系统中等待的顾客数量通道数通道数39优选课堂v3、逗留时间、逗留时间——顾客在排队系统中的总时间顾客在排队系统中的总时间李太勒公式李太勒公式前后前后2 2名顾客到达系统的时间间隔名顾客到达系统的时间间隔40优选课堂有效到达率有效到达率λλe e当排队长度未满容量时，平均到达率为当排队长度未满容量时，平均到达率为λλ当排队容量已满容量时，平均到达率为当排队容量已满容量时，平均到达率为0 041优选课堂逗留时间逗留时间42优选课堂4、排队时间、排队时间——顾客在排队系统中的等待时间顾客在排队系统中的等待时间李太勒公式李太勒公式前后前后2 2名顾客到达系统的时间间隔名顾客到达系统的时间间隔43优选课堂作业 汽车通过一检查站时进行验证。

汽车按泊松分汽车通过一检查站时进行验证汽车按泊松分布到达检查站，平均间隔布到达检查站，平均间隔0.60.6分钟，验证时间分钟，验证时间平均为平均为1515秒（验证时间服从负指数分布）请秒（验证时间服从负指数分布）请分析该排队系统，求该排队系统各状态对应的分析该排队系统，求该排队系统各状态对应的概率，以及队长、排队长、顾客逗留时间、顾概率，以及队长、排队长、顾客逗留时间、顾客等待时间等运行指标客等待时间等运行指标44优选课堂v顾客的到达是服务参数λ的泊松分布；v顾客的服务时间是服从参数为μ的负指数分布；v有S个服务台，顾客按到达的先后次序接受服务第四节第四节 M/M/S排队系统排队系统45优选课堂v当顾客到达时，若有空闲的服务台就立即接受服务，若所有的服务台都忙着，则顾客排成一个队列等待服务46优选课堂常见的M/M/S/∞/∞及M/M/S/m/∞两类 47优选课堂M/M/S/∞/∞排队系统—标准M/M/S系统 48优选课堂v系统中个服务台的服务率均为μ ，于是整个服务机构的最大服务率为Sμ 与M/M/1/∞/∞系统类似，只有当 时，才能使服务系统达到稳态而不排成无限的队列 。

系统的服务强度 49优选课堂当系统中只有一个顾客时，则有S-1个服务台空闲着，仅一个服务台在服务，这时的服务率为μ ，当系统有2个顾客时，就有2个服务台工作，其服务率为2 μ ，…，当系统中有S个顾客时，则服务率达到最大值S μ ，当系统中的顾客数超过S时，由于个服务台都忙着，其余顾客必须排队，这时的服务率仍为S μ 50优选课堂M/M/1系统M/M/S系统51优选课堂M/M/S系统52优选课堂根据正则条件53优选课堂利用排队系统各状态概率计算运行指标利用排队系统各状态概率计算运行指标v1、排队长、排队长54优选课堂v2、、平均等候时间平均等候时间 55优选课堂v3、逗留时间、逗留时间v４、平均顾客数４、平均顾客数 56优选课堂 系统容量受限制、顾客源无限、先到先服务的M/M/S系统该系统共有m-S个位置可供顾客排队当顾客到达时，若系统饱和，即服务台都忙着，排队位置已排满，则后到的顾客立即离去，另求服务因此，该系统中只可能有m+1个状态 M/M/S/m/∞/∞排队系统57优选课堂 与M/M/S/∞/∞系统的推导类似，可得M/M/S/m/∞系统的状态指标及运行指标 58优选课堂第五节 排队服务系统的最优化问题 v排队系统设计最优化的目标在于使系统设施达到最大使用效益，或者说，在一定的质量指标下要求服务机构最为经济v一般要求系统最优59优选课堂v对于顾客来说，总是要求提高服务水平（如增设服务台数、加快服务时间）以减少排队费用，若要完全满足顾客的要求，则会导致服务机构过大，使用效率降低，造成浪费。

v从服务机构来说，总是希望服务机构能达到最高的使用效率，每个服务台都不出现空闲状态，这必然导致顾客等候费用的增加，影响顾客的利益v排队系统最优化的目的是综合考虑两者的利益，使二者费用之和为最小，确定达到这个目标的最优服务水平v另一常用的目标函数是使系统的纯收入（服务收入与服务成本之差）为最大 60优选课堂服务水平服务水平61优选课堂v排队服务系统的最优化问题通常归结为求极值问题求导（求偏导） 迭代法 试算法 常用的求极值方法有：62优选课堂作业v教材170页6-963优选课堂。