运筹学-第十章-排队论定稿

1、排队论排队论v引言v生灭过程和Poisson过程vM/M/s等待制排队模型第一节 引言一、排队系统的特征及排队论一、排队系统的特征及排队论排队论(Queuing Theory)，又称随机服务系统理论(Random Service System Theory),是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。排队是我们在日常生活和生产中经常遇到的现象。例如，上、下班搭乘公共汽车；顾客到商店购买物品；病员到医院看病；旅客到售票处购买车票；学生去食堂就餐等就常常出现排队和等待现象。除了上述有形有形的排队之外，还有大

2、量的所谓“无形无形”排队现象，如几个顾客打电话到出租汽车站要求派车，如果出租汽车站无足够车辆、则部分顾客只得在各自的要车处等待，他们分散在不同地方，却形成了一个无形队列在等待派车。排队的不一定是人，也可以是物：例如，通讯卫星与地面若干待传递的信息；生产线上的原料、半成品等待加工；因故障停止运转的机器等待工人修理；码头的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋等等。显然，上述各种问题虽互不相同，但却都有要求得到某种服务的人或物和提供服务的人或机构。排队论里把要求服务的对象统称为“顾客”,而把提供服务的人或机构称为“服务员”或“服务机构”。实际的排队系统可以千差万别，但都可以一般地描述

3、如下：顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图1-1至1-4图1-1 单服务台排队系统图1-2 单队列S个服务台并联的排队系统图1-3 S个队列S个服务台的并联排队系统图1-4 单队多个服务台的串联排队系统类似地还可画出许多其他形式的排队系统，如串并混联的系统，网络排队系统等尽管各种排队系统的具体形式不同，但都可以由图1-5加以描述图1-5 随机服务系统通常称上图表示的系统为一随机聚散服务系统，任一排队系统都是一个随机聚散服务系统。这里，“聚”表示顾客的到达，“散”表示顾客的离去。所谓随机性,是排队系统的一个普遍特点，是指顾

4、客的到达情况(如相继到达时间间隔)与每个顾客接受服务的时间往往是事先无法确切知道的，或者说是随机的。一般来说，排队论所研究的排队系统中，顾客到来的时顾客到来的时刻和服务台提供服务的时间长短都是随机的刻和服务台提供服务的时间长短都是随机的，因此这样的服务系统被称为随机服务系统小结排队系统又称随机服务系统排队系统又称随机服务系统有请求服务的人或物；有请求服务的人或物；有为顾客服务的人或物；有为顾客服务的人或物； 顾客到达时间与接受服务时间是随机的。顾客到达时间与接受服务时间是随机的。结构：结构：顾客到达顾客到达-排队排队-服务机构服务服务机构服务-顾客离去顾客离去二、排队系统的描述二、排队系统的描

5、述实际中的排队系统各有不同，但概括起来都由三个基本部分组成：1输入过程输入过程2排队及排队规则排队及排队规则3服务机制服务机制1输入过程这是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流一般可以从3个方面来描述一个输入过程。(1)顾客总体数又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。例如，到售票处购票的顾客总数可以认为是无限的，而车间内停机待修得机器显然是有限的。(2)顾客到达方式这是描述顾客是怎样来到系统的，他们是单个单个到达，还是成批成批到达。病人到医院看病是顾客单个到达的例子。在库存问题中如将生产器材进货或产品入库看作是顾客，那么这种

6、顾客则是成批到达的。(3)顾客流的概率分布，或称相继顾客到达的时间间隔的分布。这是求解排队系统有关运行指标问题时，首先需这是求解排队系统有关运行指标问题时，首先需要确定的指标要确定的指标。这也可以理解为在一定的时间间隔内到达K个顾客(K=1、2、)的概率是多大。 顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布爱尔朗分布等若干种。2排队及排队规则(1)排队排队分为有限排队有限排队和无限排队无限排队两类。有限排队有限排队是指排队系统中的顾客数是有限的，即系统的空间是有限的，当系统被被占满时，后面再来的顾客将不能进入系统；无限排队无限排队是指系统中顾客数可以是无限的，队列可

7、以排到无限长，顾客到达系统后均均可进入系统排队或接受服务，这类系统又称为等待制排队系统等待制排队系统。有限排队系统有限排队系统损失制排队系统混合制排队系统（排队空间为0的系统）（允许排队，但又不允许队列无限长）这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。典型例子是典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为损失制。损失制排队系统损失制排队系统（排队空间为0的系统）等待制等待制排队系统排队系统当顾客到达时，若所有服务台都被占用且又允许排队，则该顾客将进入队列等待。例如，排队等待售票，故障设

8、备等待维修等。服务台对顾客进行服务所遵循的规则通常有：先到先服务（FCFS）后到先服务（LCFS）优先权（PR）随机服务（RAND）仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。混合制排队系统混合制排队系统这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种： 队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。 如旅馆的床位是有限的。 等待时间有限。即顾客在系统中的等待时间不超过

9、某一给定的长度T，当等待时间超过T 时，顾客将自动离去，并不再回来。 如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。（允许排队，但又不允许队列无限长） 逗留时间(等待时间与服务时间之和)有限。例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t 时，若在这个时间内未被击落，也就不可能再被击落了。不难注意到，损失制和等待制可看成是混合制的特殊情形，如记s为系统中服务台的个数，K为系统中可容纳的顾客数, 则当K=s时，混合制即成为损失制；当K=时，混合制即成为等待制。3服务机制排队系统的服务机制可以从以下3方面来描述： 服务台数量及构成形式。从数量上说，服务台有单服务台和

10、多服务台之分。从构成形式上看，服务台有： 单队单服务台式； 单队多服务台并联式； 多队多服务台并联式； 单队多服务台串联式； 单队多服务台并串联混合式 以及多队多服务台并串联混合式等等。(2) 服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客就属于成批服务。医生看病是单个服务(3) 服务时间的分布一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K阶爱尔朗分布、等等。三、排队系统的分类符号表示三、排队系统的分类符号表示肯道尔（D.G.Kendall）分类（1953）：X / Y / Z / A /

11、 B /C 其中： X 顾客到达的分布； Y 服务时间的分布； Z 服务台数； A 系统容量； B 顾客源的个体数。 C 服务规则表示分布的符号：M-负指数分布或泊松分布；D-定长分布；Ek-k阶爱尔朗分布；GI-一般独立随机分布；G-一般随机分布 例如：某排队问题为MMSFCFS，则表示顾客到达间隔时间为负指数分布(泊松流)；服务时间为负指数分布；有s(s1)个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则。某些情况下，排队问题仅用上述表达形式中的前3个、4个、5个符号。如不特别说明则均理解为系统等待空间容量无限；顾客源无限，先到先服务，单个服务的等待制系统四、排队系

12、统的主要数量指标四、排队系统的主要数量指标评价排队系统的优劣。评价排队系统的优劣。下面给出的这些数量指标一般都是和系统运行的时刻有关的随机变量，求这些随机变量的瞬时分布一般是很困难的。为了分析上的简便，并注意到相当一部分排队系统在运行了一定时间后，都会趋于一个平衡状态(或称平稳状态)。在平衡状态下，队长的分布、等待时间的分布、忙期的分布都和系统所处的时刻无关，而且系统的初始状态的影响也会消失。因此，我们在本章中将主要讨论与系统所处时刻无关的性质，即统计平衡性质。1、队长与排队长、队长与排队长(1)队长队长: 系统中的顾客数（n）； N(t)-N-L (2)排队长排队长: 系统中排队等待服务的顾

13、客数; Nq(t)- Nq-Lq2、逗留时间与等待时间、逗留时间与等待时间(1)逗留时间逗留时间: 指一个顾客在系统中的全部停留时间； T(t)-T-W(2)等待时间等待时间: 指一个顾客在系统中的排队等待时间；Tq(t)- Tq-Wq这四项主要性能指标(又称主要工作指标)的值越小，说明系统排队越少，等待时间越少，因而系统性能越好。显然，它们是顾客与服务系统的管理者都很关注的。3、忙期和闲期、忙期和闲期(1)忙期忙期: 是指从顾客到达空闲着的服务机构起，到服务机构再次 成为空闲止的这段时间，即服务机构连续忙的时间。 (2)闲期闲期: 与忙期相对的是闲期，即服务机构连续保持空闲的时间。 在排队系

14、统中，忙期和闲期总是交替出现的。BBII4、其他相关指标、其他相关指标 (1)(1)忙期服务量：忙期服务量：指一个忙期内系统平均完成 服务的顾客数；(2)损失率损失率: 指顾客到达排队系统，未接受服务 而离去的概率; （对损失制或系统容量有限而言） (3)服务强度：服务强度： = = /s/s ；根据前面的约定，我们将主要分析系统的平稳分布。于是记：Pn ：当系统达到统计平衡时处于状态n的概率（pn(t)）n :当系统处于状态n时，新来顾客的平均到达率平均到达率(单位 时间内来到系统的平均顾客数)n：当系统处于状态n时，整个系统的平均服务率 （单位时间内可以服务完的顾客数）当n为常数时，记为；

15、当每个服务台的平均服务率为常数时，记每个服务台的服务率为。s表示系统中并行的服务台数则当ns时，有ns ,于是令 = /s ， 称为服务强度 （traffic intensity）随机变量：随机变量： 数数 随着实验的结果的不同而变化随着实验的结果的不同而变化 离散型离散型： 的所有可能只有限或至多可列个的所有可能只有限或至多可列个连续型连续型： （ ）取值于某个区间（）取值于某个区间（a a，b b）分布函数）分布函数( (连续连续):): xpxF aFbFbap 的概率分布的概率分布(离散): iixpxp i=1,2,311iixp34 数学期望数学期望:(离散) E()= 1iiip

16、xdxxxf (连续) E()= 方差方差: 2EED EE22 = BAPBPABP 条件概率条件概率: 密度函数密度函数:(连续) dttfxFx 0 xf 1dttf , ,35tnnenttP !)( 式中式中为常数为常数(0)0)，称，称X X服从参数为服从参数为的泊松分布，若在上的泊松分布，若在上式中引入时间参数式中引入时间参数t t，即令，即令tt代替代替，则有：，则有： 在概率论中，我们曾学过泊松分布，设随机变量为在概率论中，我们曾学过泊松分布，设随机变量为X，则有：则有：!nenXPn n=0,1,2, （1） 与时间有关的随机变量的概率与时间有关的随机变量的概率，是一个，是

17、一个随机过程随机过程，即，即泊泊松过程松过程。 t0，n=0,1,2, （2）36vP(X(0)=0)=1。v不相交区间上增量相互独立，即对一切0t1t2s)的概率分布为泊松分布。若若X还满足还满足vX(t)-X(s)的分布仅依赖于t-s，则称X为齐次泊松过程; 泊松过程需要满足的条件是：泊松过程需要满足的条件是：)()(,1221ntNtNPttPn （t2t1，n0） 若设若设N(t)N(t)表示在时间区间表示在时间区间0,t)0,t)内到达的顾客数内到达的顾客数(t0),P(t0),Pn n(t(t1 1,t,t2 2) )表示在时间区间表示在时间区间tt1 1,t,t2 2)(t)(t

18、2 2tt1 1) )内有内有n(0)n(0)个个顾客到达的概率。即：顾客到达的概率。即： 当当P Pn n(t(t1 1,t,t2 2) )符合下述三个条件时，顾客到达过程就是泊松符合下述三个条件时，顾客到达过程就是泊松过程过程( (顾客到达形成普阿松流顾客到达形成普阿松流) )。38tnnenttP!)(, 0 无后效性：无后效性：各区间的到达相互独立各区间的到达相互独立, ,即即MarkovMarkov性。性。. . . . . . . t0 t1 t2 tn-1 tn|)(|)(11112211)()(,.,)(,)(nnnnxtxnxtxxtxxtxnntxPntxP 也就是说过程在

19、也就是说过程在t+tt+t所处的状态与所处的状态与t t以前所处的状态无以前所处的状态无关。关。 平稳性：平稳性：即对于足够小的即对于足够小的tt，有：，有：)()(tttttP ，1普阿松流具有如下特性：普阿松流具有如下特性： 在在t,t+tt,t+t内有一个顾客到达的概率与内有一个顾客到达的概率与t t无关无关, ,而与而与tt成成正比。正比。39 普通性：普通性：对充分小的对充分小的t,t,在时间区间（在时间区间（t,t+tt）内有）内有2 2个个或或2 2个以上顾客到达的概率是一高阶无穷小个以上顾客到达的概率是一高阶无穷小. . 由此知，在由此知，在(t，t+t)t)区间内没有顾客到达

20、的概率为：区间内没有顾客到达的概率为：)(1),(0tottttP 令令t1 1=0,t=0,t2 2=t,=t,则则P(tP(t1 1,t,t2 2)=P)=Pn n(0,t)=P(0,t)=Pn n(t)(t) 0 0 是常数，它是常数，它表示单位时间到达的顾客数，称为概率强表示单位时间到达的顾客数，称为概率强度。度。2)(),(nntotttP 即即 P P0 0+P+P1 1+P+P22=1=140泊松过程的数字特征泊松过程的数字特征 （n n个顾客到达的概率）个顾客到达的概率）tnnenttP !)()(tetetNEtt )(ttar )(N(V2 2、负指数分布、负指数分布密度函

21、数0for t00 )(tforetftT数学期望1)(TE方差21)(TVar随机变量 T分布函数tetTP1)(fT(t)t1)(TE)()0(ttTtPtTPfT(t)tttfT(t) 是一个严格下降函数设设v v1 1, v, v2 2，, v, vk k是是k k个独立的随机变量，服从相同参个独立的随机变量，服从相同参数数 k k 的负指数分布，那么：的负指数分布，那么：kT 21其概率密度函数是其概率密度函数是011 te)!k()kt(k)t (ftkkk 则称则称T服从服从k阶阶爱尔朗分布。其数字特征为：爱尔朗分布。其数字特征为： 1TE21 kTVar , 串列串列k k个服

22、务台个服务台，每台服务时间相互独立，服从相同负指，每台服务时间相互独立，服从相同负指数分布（参数数分布（参数k k ），那么一顾客走完），那么一顾客走完k k个服务台总共所需要个服务台总共所需要服务时间服从上述服务时间服从上述k k阶阶ErlangErlang分布。分布。 例例: :有易碎物品有易碎物品500500件件, ,由甲地运往乙地由甲地运往乙地, ,根据以往统计根据以往统计资料资料, ,在运输过程中易碎物品按普阿松流发生破碎在运输过程中易碎物品按普阿松流发生破碎, ,其概率其概率为为0.002,0.002,现求现求:1.:1.破碎破碎3 3件物品的概率件物品的概率;2.;2.破碎少于破

23、碎少于3 3件的概件的概率和多于率和多于3 3件的概率件的概率;3.;3.至少有一件破损的概率至少有一件破损的概率. . 解解: : =0.002500=1 1 1破碎破碎3 3件物品的概率为件物品的概率为: : P(k=3)=( P(k=3)=( 3 3/3/3！)e)e- - =(1=(13 3/3/3！)e)e-1-1=0.0613=0.0613 即物品破碎即物品破碎3 3件的概率为件的概率为6.136.13 2. 2.破碎物品少于破碎物品少于3 3件的概率件的概率: :45 破碎物品少于破碎物品少于3 3件的概率为件的概率为91.9791.97 破碎物品多于破碎物品多于3 3件的概率为

24、件的概率为: : 02. 098. 01!1330 kkekp 3.3.至少有一件破碎的概率为至少有一件破碎的概率为 PkPk 1=1-(11=1-(1k k/k!)e/k!)e- - =1-(1=1-(10 0/0!)e/0!)e-1-1=0.632=0.632 9197. 021112120 eeknp46 2001年全国数学竞赛的年全国数学竞赛的B题题“公交车调度公交车调度”某条公交线路上行方向共某条公交线路上行方向共1414站，下行方向共站，下行方向共 1313站站. .公交公司配给该线路同一型号的大客车，每公交公司配给该线路同一型号的大客车，每辆标准载客辆标准载客100100人，据统

25、计客车在该线路上运行的人，据统计客车在该线路上运行的平均速度为平均速度为2020公里公里/ /小时小时. .运营调度要求，乘客候车运营调度要求，乘客候车时间一般不要超过时间一般不要超过1010分钟，早高峰一般不要超过分钟，早高峰一般不要超过例子例子5 5分钟，车辆满载率不应超过分钟，车辆满载率不应超过120%120%，一般也不要，一般也不要低于低于50%. 试根据这些材料和要求，为该线路设计一个试根据这些材料和要求，为该线路设计一个便于操作的全天（工作日）的公交车调度方案便于操作的全天（工作日）的公交车调度方案包括两个起点站的发车时刻表；一共需要多少包括两个起点站的发车时刻表；一共需要多少辆车

26、；这个方案以怎样的程度照顾到了乘客和辆车；这个方案以怎样的程度照顾到了乘客和公交公司双方的利益；等等公交公司双方的利益；等等. . 1. 问题分析问题分析 将公交车的运行看作是提供服务，即服务机构；将公交车的运行看作是提供服务，即服务机构； 将乘客看作顾客，乘客乘坐公交车看作是接受公交将乘客看作顾客，乘客乘坐公交车看作是接受公交的服务的服务. . 公交车运行中乘客的数目描述了系统的状公交车运行中乘客的数目描述了系统的状 态，随着时间的变化，一些乘客得到服务后离去，态，随着时间的变化，一些乘客得到服务后离去， 又有一些新的顾客到来，在人数较多时就要排队等又有一些新的顾客到来，在人数较多时就要排队

27、等服务系统，这里拟用排队论来解决该问题服务系统，这里拟用排队论来解决该问题. .按排队按排队论的要求，将公交车看作服务机构，乘客看作顾客论的要求，将公交车看作服务机构，乘客看作顾客. . 候，而且，顾客到来的时间具有随机性，对顾客的候，而且，顾客到来的时间具有随机性，对顾客的服务时间也有随机性，所以公交车运行系统是一个服务时间也有随机性，所以公交车运行系统是一个随时间变化的随机动态系统，可以看作一个随机随时间变化的随机动态系统，可以看作一个随机 2. 基本假设基本假设(i). 某站旅客到达为泊松过程某站旅客到达为泊松过程(ii).公交车对每批乘客服务时间为相互独立的负公交车对每批乘客服务时间为

28、相互独立的负指数分布，指数分布，每批服务时间是指公交车从起始站出每批服务时间是指公交车从起始站出 乘客到达时间间隔服从参数为乘客到达时间间隔服从参数为 的的k k阶爱尔朗分布：阶爱尔朗分布：发再返回起始站所需的时间为发再返回起始站所需的时间为 .RTt110()10!00kitmmitetP tit 服从参数服从参数为的负指数分布为的负指数分布 .RTt与与 的关系为的关系为：其中其中表示运行一个程序的平均时间表示运行一个程序的平均时间. RTt11RTRTE tT RTt3. 模型的建立与求解模型的建立与求解k阶爱尔朗分布的概率密度为：阶爱尔朗分布的概率密度为：到达间隔的期望值到达间隔的期望

29、值1()( )(1)!kt ta tAek 0( )( )() ,( )0tkAsedA tres ss 10( )mmkE tdA t 公交车服务系统的服务强度为公交车服务系统的服务强度为： 以平均等待队长衡量乘客的满意度，系统以平均等待队长衡量乘客的满意度，系统 以乘客的等待时间在非高峰期不超过以乘客的等待时间在非高峰期不超过10分分服务台的平均占有数衡量公交车公司的利益作服务台的平均占有数衡量公交车公司的利益作为规划模型的目标为规划模型的目标；钟，高峰期不超过钟，高峰期不超过5分钟，以及车容量在区间分钟，以及车容量在区间(50,120)作为约束条件，建立随机规划模型作为约束条件，建立随机

30、规划模型 :1tRTmmE vTE nk 约束条件为约束条件为：对上述模型求解即可得到公交车调度的一个对上述模型求解即可得到公交车调度的一个完整方案完整方案.至此，利用排队论来建立调度问题的至此，利用排队论来建立调度问题的一个明确、完整的随机规划数学模型，可以利用一个明确、完整的随机规划数学模型，可以利用2min min(1)E lE qE qwkE qw 20(50,120)( )5(10)(1)KKWxdW xorn 第二节第二节生灭过程和生灭过程和Poisson过程过程一、生灭过程简介一类非常重要其广泛存在的排队系统是生灭过程排队系统。生灭过程是一类特殊的随机过程，在生物学、物理学、运筹

31、学中有广泛的应用。定义定义1 设N(t)，t0 为一个随机过程。如N(t)的概率分布具有以下性质： （1）假设N(t)= n，则从时刻 t 起到下一个顾客到达时刻止的时 间服从参数为n 的负指数分布，n=0，1，2，。 （2）假设N(t)= n，则从时刻 t 起到下一个顾客离去时刻止的时间服从参数为n的负指数分布，n=0，1，2，。 （3）同一时刻只有一个顾客到达或离去。则称设N(t)， t0 为一个生灭过程。v顾客到达“生”；v顾客离开“灭”服务机构顾客聚顾客散顾客到达顾客到达顾客离去顾客离去n ， n ，生灭过程示意图：为求平稳分布，考虑系统在 t+t 时刻可能处的任一状态n的概率。状态转

32、移图状态转移图一般说来，得到 是比较困难的，因此通常是求当系统达到平稳状态后的状态分布，记为 , n=0,1,2 ，. ( )( )( )nN tptP N tn的 分 布np方式 T时刻状态概率（t,t+t）内发生的事件发生的概率1nPn(t)无到达，无离去 （1-nt） (1-nt) 2n -1Pn-1(t)到达一个，无离去 n-1t (1-n-1t) 3n +1Pn+1(t)无到达，离去一个(1-n+1t) n+1t 4nPn(t)到达一个，离去一个 (nt) (nt) 各种方式发生概率表各种方式发生概率表方式1，2，3，4互不相容且完备，于是：111111()( ) (1)(1)( )

33、 ()(1)( ) (1)()( ) ()()nnnnnnnnnnnnnP ttP tttPtttPtttP ttt 0()()( )limnnntdP ttP ttP td tt1111( )( )()( )nnnnnnnPtP tPtt2项都变为零项都变为零对上式求导有：当n=0时，只有方式1和3，4发生，且方式1中无离去的概率为1，则:00011( )( )( )dP tP tP tdt 我们假设系统是平稳的，即与时刻无关，于是可得：( )0ndPtdt00110PP1111()0nnnnnnnPPPn=1,2,3.00110PP0101()PP0011122()0PPP1111122(

34、)0PPP012011122()PPP 继续迭代：120011.nnnnnPP记12011.nnnnnC则平稳状态的分布为：0nnPC P如何求P0?由概率分布的要求：01nnP0111nnCP有：0111nnPC于是：小结120011.nnnnnPP 0111nnPC系统达到平稳状态后的状态分布-Pn12011.nnnnnC 举例某小型超市有一个收款台。交款顾客以每小时30人的负指数分布到达。当收款台前只有一名顾客时，有一名收款员单独服务，收款时间为平均1.5min/人的负指数分布；当有2名或以上顾客时，将增加一名助手共同为顾客服务，收款时间将缩短至平均1min的负指数分布。求收款台前有求收

35、款台前有n名顾客的概名顾客的概率率Pn01.30/nh人16040/1.5h人260.60/1nh人解： 1011112.303 1( ).(40)(60)4 2nnnnnnC n=1,2.0111113111.( )42nnnnPC=则有由级数可知：11nna q当|q| 0称为过程N(t)的强度，而o(t)为当t-0时关于t 的高阶无穷小。( ,)1()P N t tttot 00( )( )( , )( ),0N tN tN t tN t t 表示在时间间隔0,t内出现的质点数注：（2） 独立性任意两个不相交区间内顾客到达情况相互独立（3） 普通性在 t, t+t 内多于一个顾客到达的概

36、率为()ot亦即对于充分小的t，在 t, t+t 内出现2个或2个以上质点的概率与出现一个质点的概率相比可以忽略不计。则称 N(t), t 0 为Poisson过程（强度为 ）。()otj=2P N(t, t+ t)=j定理1 设N(t)为时间 0, t 内到达系统的顾客数，则 N(t), t 0 为Poisson过程的充分必要条件是：()( )!nttP N tnenn=1,2定理1说明，如果顾客的到达为Poisson流的话，则到达顾客数的分布恰为Poisson分布。举例顾客按泊松流到达餐厅，平均每小时20人，在上午11：07餐厅内有18人试求：到11：12餐厅内有20名顾客的概率分析：依题

37、意知 20（人（人/小时）小时）()( )!nttP N tnen由公式可知：21(20)121(20)112()20.2623122!P Ne在（1/12）h内到达顾客2人的概率为：但无论是从Poisson过程的定义，还是根据其概率分布去对顾客的到达情况进行分析，都有许多不便之处。实际问题中比较容易得到和进行分析的往往是顾客相继到达系统的时刻，或相继到达的时间间隔。定理2设N(t)为时间 0, t 内到达系统的顾客数，则 N(t), t 0 为参数为的Poisson过程的充分必要条件是：相续到达时间间隔服从相互独立的参数为的负指数分布。定理2说明，顾客相续到达时间间隔服从相互独立的参数为的负

38、指数分布，与到达过程为参数的Poisson过程是等价的。举例某排队系统，顾客到达为泊松流，平均1人/h。假如有一名顾客于中午12点到达该排队系统情况下。试求：下一名分别于下午1点前、12点间、2点后到达的概率。分析：因顾客到达为泊松流，则说明顾客到达时间间隔T服从负指数分布，故T的概率密度fT(t)为：0( )00tTetftt（1）因下一名顾客在下午1:00前到达，有 0 T 1,则1100(01)0.6321ttPTe dte （2）下一名顾客在下午1:002:00之间达到，即 1 T 2,则2200(2)1(2)11 0.1353ttP TP Te dte 第三节 M/M/s等待制排队模

39、型一、单服务台模型M/M/1/ 是指：顾客的相继到达时间服从参数为的负指数分布，服务台数为1，服务时间服从参数为的负指数分布，系统空间无限，允许无限排队。1、队长的分布由n =( n=0，1，2，) n =( n=0，1，2，)记 =/并设 4)；(7)在六天工作日内系统中没有顾客的小时数； (8)若决定当顾客平均逗留时间超过半个小时时，就应增加一个售票窗口，试问这相当于要求顾客的平均到达率是原有的几倍？举例解：按题意可知=24人人/小时，小时，=40人人/小时，小时，=/=0.6（1）010 .4P（2）1 . 5 ()1L人（3）1W0.0625 =3.75 L小时分钟（4）220.91()qL 人（5）W0.03752.25qqL小时分钟（6）550110.0781p 4nn=0p(L 4)=1-p（7）因每天系统内没有顾客的小时数为8p0=3.2小时,故一周六天工作日内没有顾客的