泊松分布与生灭过程.ppt

2019/12/13,1,第二节顾客到达分布,2019/12/13,2,系统的组成,顾客,服务机构,顾客到达有先后,服务时间有长短,存在随机性,2019/12/13,3,要想预测在某一时刻将有多少顾客要求服务系统服务，或者预测某一顾客的服务时间将要延误多久这都是不可能的对单位时间内到达系统的顾客数和服务时间这两个随机变量进行概率的描述描述顾客到达和服务时间的方法，要求出单位时间内有K个顾客到达系统要求服务的概率，以及服务时间不少于某一时间长度的概率,2019/12/13,4,最简单流（泊松流）,流的平稳性对于任意的t0及t0，在时间区间(t,t+t)内有n个顾客到达的概率只与t有关，与时间区间的起点t无关。当t充分小时，在(t,t+t)内有一个顾客到达的概率与t成正比，即其中，O(t)是当t0时，关于t高阶无穷小，为单位时间内的顾客到达平均数。,2019/12/13,5,流的无后效性在时间轴上，互不相交的时间区段和内，顾客的到达数是相互独立的，即前一顾客的到达不影响后一顾客的到达。,2019/12/13,6,流的普遍性在同一时刻，有两个及两个以上顾客到达的概率与有一个顾客到达的概率相比小到可以忽略的程度，即当t充分小时，在时间区间(t,t+t)内有2个及2个以上顾客到达的概率是关于的高阶无穷小。,2019/12/13,7,流的平稳性,流的普遍性,在区间(t,t+t)内没有顾客到达的概率,2019/12/13,8,在长为(t,t+t)的时间区间内，到达n个顾客的概率?,设把长为t的时间区间分成m等分，每段长度为。若在dt内，有一个顾客到达，则称被“占着”，如果在dt内，没有顾客到达，则称为“空着”。被“占着”的概率近似为被“空着”的概率近似,根据流的无后效性，在m个dt中，有顾客到达与没有顾客到达可以看成是m次独立的试验,2019/12/13,9,在长为(t,t+t)的时间区间内，到达n个顾客的概率?,在m个dt中，有n个dt被顾客“占着”的概率,利用二项定律,2019/12/13,10,dt0，m,2019/12/13,11,符合最简单流（泊松流）的随机事件发生规律称为泊松分布,单位时间发生n个随机时间的概率,参数1个：顾客的平均到达率,思考：交叉口交通流量，排队车辆？,2019/12/13,12,泊松分布的另外一种表达方式负指数分布,若n=0,在t的时间段内没有顾客达到的概率,前后两次随机事件发生的时间间隔大于t,2019/12/13,13,负指数分布,泊松分布,在单位时间t内，发生n次随机事件的概率,随机事件发生时间间隔大于单位时间t的概率,随机事件发生时间间隔小于单位时间t的概率,参数1个：顾客的平均到达率,2019/12/13,14,如果顾客的到达过程服从最简单流，则顾客单位时间内的到达数服从泊松分布。如果顾客的到达过程服从最简单流，则顾客到达的时间间隔服从负指数分布。从本质上看，泊松分布与负指数分布是同一个过程的不同表现形式。,2019/12/13,15,第三节生灭过程,2019/12/13,16,研究系统内部状态变化的过程,系统状态i,状态i+1,状态i-1,在t时刻内发生两个或两个以上事件的概率为O(t),一个事件,一个事件,一、生灭过程定义,t0，O(t)0,如在t0内，交叉口一条车道到达两辆车的概率为O(t)0,2019/12/13,17,系统具有0,1,2,个状态。在任何时刻，若系统处于状态i，并且系统状态随时间变化的过程满足以下条件，称为一个生灭过程：,1、在（t,t+t）内系统由状态i转移到状态i+1的概率为it+O(t)平稳性条件,t内有一个顾客到达的概率,2、在（t,t+t）内系统由状态i转移到状态i-1的概率为it+O(t)平稳性条件,t内有一个顾客离开的概率,2019/12/13,18,3、在（t,t+t）内系统发生两次以上转移的概率为O(t)，即有2个以上顾客到达或离开的概率为,普遍性条件,只要排队系统的输入过程和服务过程符合泊松分布，排队过程符合生灭过程,2019/12/13,19,二、生灭过程状态转移图,状态,顾客到达率,系统服务率,t时，Pi(t)趋向于常数：系统达到稳定,2019/12/13,20,系统达到稳定后：每个状态转入率的期望值与转出率的期望值相等。,对于状态i：转出率的期望值为,转入率的期望值为,P0,P1,P2,Pi,2019/12/13,21,有,对于S0,转入,转出,转出,转入,对于Sk,P0,P1,P2,Pi,2019/12/13,22,状态转移方程,求解该方程，可以获得各状态对应的概率,2019/12/13,23,对于S0,对于S1,依次类推,且有,2019/12/13,24,例：,某排队系统：M/M/1/3/FCFS，=2，=3。求解各状态对应的概率。,首先，做出相应的状态转移图,对于S0,对于S1,对于S2,2019/12/13,25,生灭过程求解排队系统各状态概率过程,建立状态转移图,建立状态转移方程,求解状态转移方程,各状态转入率期望值与转出率期望值相等,各状态概率,2019/12/13,26,作业：利用生灭过程求解以下排队系统各状态的概率。,S0,S1,S2,S3,2,2,3,2,4,3,2019/12/13,27,第三节M/M/1排队系统,顾客到达服从泊松分布顾客到达率为服务过程服从泊松分布（负指数分布）系统服务率为单通道，先到先服务,最简单的M/M/1排队系统：,M/M/1/,M/M/1/m/,2019/12/13,28,M/M/1/排队系统,系统容量无限、顾客源无限,最基本的排队系统,排队过程为生灭过程过程,2019/12/13,29,列状态转移方程组求各状态概率,2019/12/13,30,M/M/1/排队系统各状态概率归结为无穷等比数列求和,1，数列发散,系统稳定,系统不稳定,称为服务强度，若服务强度大于1，说明单位时间内到达的顾客数比完成服务的顾客数多，系统中排队长度越来越大，产生阻塞。,2019/12/13,31,利用排队系统各状态概率计算运行指标,1、队长系统中的顾客数量,队长,2019/12/13,32,2、排队长系统中等待的顾客数量,通道数,2019/12/13,33,可编辑,2019/12/13,34,3、逗留时间顾客在排队系统中的总时间,李太勒公式,前后2名顾客到达系统的时间间隔,2019/12/13,35,4、排队时间顾客在排队系统中的等待时间,李太勒公式,前后2名顾客到达系统的时间间隔,2019/12/13,36,M/M/1/m/排队系统,系统容量有限、顾客源无限,2019/12/13,37,列状态转移方程组求各状态概率,2019/12/13,38,并不要求1。,特别地，当=1时，P0=1/(m+1),(1),2019/12/13,39,利用排队系统各状态概率计算运行指标,1、队长系统中的顾客数量,队长,2019/12/13,40,2、排队长系统中等待的顾客数量,通道数,2019/12/13,41,3、逗留时间顾客在排队系统中的总时间,李太勒公式,前后2名顾客到达系统的时间间隔,2019/12/13,42,有效到达率e,当排队长度未满容量时，平均到达率为当排队容量已满容量时，平均到达率为0,2019/12/13,43,逗留时间,2019/12/13,44,4、排队时间顾客在排队系统中的等待时间,李太勒公式,前后2名顾客到达系统的时间间隔,2019/12/13,45,作业,汽车通过一检查站时进行验证。汽车按泊松分布到达检查站，平均间隔0.6分钟，验证时间平均为15秒（验证时间服从负指数分布）。请分析该排队系统，求该排队系统各状态对应的概率，以及队长、排队长、顾客逗留时间、顾客等待时间等运行指标。,2019/12/13,46,顾客的到达是服务参数的泊松分布；顾客的服务时间是服从参数为的负指数分布；有S个服务台，顾客按到达的先后次序接受服务。,第四节M/M/S排队系统,2019/12/13,47,当顾客到达时，若有空闲的服务台就立即接受服务，若所有的服务台都忙着，则顾客排成一个队列等待服务。,2019/12/13,48,常见的M/M/S/及M/M/S/m/两类,2019/12/13,49,M/M/S/排队系统标准M/M/S系统,2019/12/13,50,系统中个服务台的服务率均为，于是整个服务机构的最大服务率为S。与M/M/1/系统类似，只有当时，才能使服务系统达到稳态而不排成无限的队列。,系统的服务强度,2019/12/13,51,当系统中只有一个顾客时，则有S-1个服务台空闲着，仅一个服务台在服务，这时的服务率为，当系统有2个顾客时，就有2个服务台工作，其服务率为2，当系统中有S个顾客时，则服务率达到最大值S，当系统中的顾客数超过S时，由于个服务台都忙着，其余顾客必须排队，这时的服务率仍为S,2019/12/13,52,M/M/1系统,M/M/S系统,2019/12/13,53,M/M/S系统,2019/12/13,54,根据正则条件,2019/12/13,55,利用排队系统各状态概率计算运行指标,1、排队长,2019/12/13,56,2、平均等候时间,2019/12/13,57,3、逗留时间,、平均顾客数,2019/12/13,58,系统容量受限制、顾客源无限、先到先服务的M/M/S系统。该系统共有m-S个位置可供顾客排队。当顾客到达时，若系统饱和，即服务台都忙着，排队位置已排满，则后到的顾客立即离去，另求服务。因此，该系统中只可能有m+1个状态。,M/M/S/m/排队系统,2019/12/13,59,与M/M/S/系统的推导类似，可得M/M/S/m/系统的状态指标及运行指标。,2019/12/13,60,第五节排队服务系统的最优化问题,排队系统设计最优化的目标在于使系统设施达到最大使用效益，或者说，在一定的质量指标下要求服务机构最为经济一般要求系统最优,2019/12/13,61,对于顾客来说，总是要求提高服务水平（如增设服务台数、加快服务时间）以减少排队费用，若要完全满足顾客的要求，则会导致服务机构过大，使用效率降低，造成浪费。从服务机构来说，总是希望服务机构能达到最高的使用效率，每个服务台都不出现空闲状态，这必然导致顾客等