数学建模排队论ppt课件.ppt

《数学建模排队论ppt课件.ppt》由会员分享，可在线阅读，更多相关《数学建模排队论ppt课件.ppt（51页珍藏版）》请在三一办公上搜索。

1、第六讲 排队论及排队系统优化,排队现象与排队系统;排队模型与系统参数;排队系统时间参数分布规律;排队系统的生灭过程与状态转移方程;排队系统分析; 单服务台负指数分布模型 多服务台负指数分布模型 排队系统优化分析;,排队论发源于上世纪初。当时美国贝尔电话公司发明了自动电话，以适应日益繁忙的工商业电话通讯需要。这个新发明带来了一个新问题，即通话线路与电话用户呼叫的数量关系应如何妥善解决，这个问题久久未能解决。1909年，丹麦的哥本哈根电话公司A.K.埃尔浪(Erlang)在热力学统计平衡概念的启发下予以解决了。,6.1 排队现象与排队系统,一、排队现象,（1）由于顾客到达和服务时间的随机性， 现实

2、中的排队现象几乎不可避免；（2）排队过程，通常是一个随机过程， 排队论又称“随机服务系统理论”；,二、排队系统,（一）排队服务过程,（二）排队系统的要素及其特征,1、排队系统的要素：,（1）顾客输入过程；（2）排队结构与排队规则；（3）服务机构与服务规则；,2、排队系统不同要素的主要特征：,（1）顾客输入过程,顾客源(总体)：有限/无限;顾客到达方式：逐个/逐批;(仅研究逐个情形)顾客到达间隔：随机型/确定型;顾客前后到达是否独立：相互独立/相互关联；输入过程是否平稳：平稳/非平稳；(仅研究平稳性),（2）排队结构与排队规则,顾客排队方式：等待制/即时制(损失制);排队系统容量：有限制/无限制

3、; 排队队列数目: 单列/多列;是否中途退出: 允许/禁止;是否列间转移: 允许/禁止; (仅研究禁止退出和转移的情形),（3）服务机构与服务规则,服务台(员)数目;单个/多个;服务台(员)排列形式;并列/串列/混合;服务台(员)服务方式;逐个/逐批;(研究逐个情形)服务时间分布;随机型/确定型;服务时间分布是否平稳:平稳/非平稳;(研究平稳情形),6.2 排队模型与系统参数,一、排队模型,(一)排队模型表示方法,1、D.G.Kendall(1953)表示法 X / Y / Z依据排队系统3个主要特征：（1） X 顾客到达间隔时间分布；（2） Y 服务台（员）服务时间分布；（3） Z 服务台（

4、员）个数（单个或多个并列）；,2、国际排队论标准化会议(1971)表示法 X / Y / Z / A / B / C（1） A 系统容量限制；（2） B 顾客源（总体）数目；（3） C 服务规则（FCFS，LCFS等）；,略去后三项，即指 “X/Y/Z/FCFS”；这里仅研究FCFS的情形；,(二)到达间隔和服务时间典型分布,（1） 泊松分布 M ；（2） 负指数分布 M ；（3） k阶爱尔朗分布 Ek；（4） 确定型分布 D；（5） 一般服务时间分布 G；,M/M/1，M/D/1，M/ Ek /1；M/M/c， M/M/c/m， M/M/c/N/ ，。,(三)排队模型示例,二、系统参数,(一

5、)系统运行状态参数,1、系统状态 N(t) 指排队系统在时刻t时的全部顾客数 N(t)， 包括“排队顾客数”和“正被服务顾客数”；,系统状态的可能值如下：（1）系统容量无限制， N(t) =0，1，2，; (2) 系统容量为N时, N(t) =0,1,2,N; (3) 服务台个数为c/损失制, N(t) =0,1,2,c;,一般,系统状态N(t)是随机的。,2、系统状态概率： (1)瞬态概率Pn(t) 表示时刻系统状态 N(t)=n 的概率; (2) 稳态概率Pn Pn= Pn(t) ; 一般，排队系统运行了一定长的时 间后，系统状态的概率分布不再随时间 t变化，即初始时刻（t=0）系统状态的

6、 概率分布(Pn(0) ，n0）的影响将消失。,(二)系统运行指标参数 评价排队系统的优劣。,1、队长与排队长 (1)队长: 系统中的顾客数（n）； 期望值 Ls= n*Pn (2)排队长: 系统中排队等待服务的顾客数; 期望值 Lq =,Lq= Ls-正被服务的顾客数,2、逗留时间与等待时间 (1)逗留时间: 指一个顾客在系统中的全部停留时间； 期望值，记为 Ws (2)等待时间: 指一个顾客在系统中的排队等待时间； 期望值，记为 Wq,Ws = Wq + E服务时间,3、其他相关指标 (1)忙 期: 指从顾客到达空闲服务机构起到服务 机构再次空闲的时间长度； (2)忙期服务量：指一个忙期内

7、系统平均完成 服务的顾客数； (3)损失率: 指顾客到达排队系统，未接受服务 而离去的概率； (4)服务强度： = /c ；,6.3 排队系统时间参数分布规律,一、顾客到达时间间隔分布 (一)泊松流与泊松分布,如果顾客到达满足如下条件,则称为泊松流: (1) 在不相互重叠的时间区间内，到达顾客数 相互独立(无后效性). (2) 对于充分小的时间间隔 内，到达 1个顾客的概率与t无关，仅与时间间隔 成正比 (平稳性)： (3) 对于充分小的时间间隔 ，2个及以 上顾客到达的概率可忽略不计 (普通性)。,对泊松流，在时间t系统内有n个顾客的概率服从如下泊松分布 EN(t)=t ; Var N(t)

8、=t ; 单位时间平均到达的顾客数；,若顾客到达间隔T的概率密度为 则称T服从负指数分布，分布函数如下：若顾客流是泊松流时，顾客到达的时间间隔 显然服从上述负指数分布(WHY);ET=1/ ; Var T=1/2 ; T=1/,(二)泊松流到达间隔服从负指数分布,二、顾客服务时间分布 (一)负指数分布,(1) 对一个顾客的服务时间Ts，等价于相邻两个顾客离开排队系统的时间间隔。若Ts服从负指数分布，其概率密度和分布函数分别为 则 ETs=1/ ; Var Ts=1/ 2 ; Ts=1/ (2) ETs=1/ ：每个顾客的平均(期望)服务时间； :单位时间服务的顾客数，平均(期望)服务率；,(二

9、)爱尔朗(Erlang)分布,(1) 设v1,v2,vk是k个相互独立的随机变量,服从相同参数1/ k的负指数分布,则:T= v1+v2+vk的概率密度为 称T服从k阶爱尔朗分布。 (2) ET=1/ ; Var T=1/( k2) (3) T的意义之一: k个串联服务台的总服务时间！,6.4 排队系统的生灭过程与状态转移方程,一、排队系统的生灭过程,(一)生灭过程的背景与定义,设某系统具有状态集S=0,1,2,或S=0,1,2,k,N(t)表示系统在时刻 t (t=0) 的状态。 若在N(t)=n的条件下，随机过程N(t),t=0满足以下条件: (1) N(t+t)转移到“n+1”的概率为n

10、(t ) ; (2) N(t+t)转移到“n-1”的概率为n(t ) ; (3) N(t+t)转移到其他状态“S-n+1,n-1”的概 率为o(t )(高阶无穷小) ; 则称随机过程N(t),t=0为生灭过程。,n ，n ，t ( ？),(二)生灭过程状态变化的性质,(1) 在无穷小t内,系统或生长1个;或灭亡1个;或既 不生长又不灭亡（概率:1- n(t ) -n(t ) ）; (2)系统生长一个的概率n(t )与t有关，而与t无 关; 与系统当前状态n有关，而与以前的状态无关； (3)系统灭亡一个的概率n(t )与t有关，而与t无 关; 与系统当前状态n有关，而与以前的状态无关；,马尔可夫

11、性质,(三) 排队系统的生灭过程,顾客到达“生”；顾客离开“灭”,顾客到达,顾客离去,(1)生灭过程示意,若排队系统具有下列性质: (1) 顾客到达为泊松流，时间间隔服从参 数为n的负指数分布; (2) 顾客服务时间服从参数为 n的负指 数分布; 则排队系统的随机过程N(t),t=0具有马 尔可夫性质, 为一个生灭过程.,(2)生灭过程定义,二、排队系统的状态转移方程,(一) 排队系统状态的概率及其分布,(1)瞬态概率Pn(t) 表示时刻系统状态N(t)=n的概率; (2) 稳态概率Pn Pn= Pn(t) ;,一般，稳态概率Pn的分布，是分析计算排队系统运行优劣的基础。,三、 排队系统稳态概

12、率Pn的求解,对一般排队系统，均有下式成立,其中有效到达率为,四、 排队系统性能参数的一般关系 Little 公式,6.4 典型排队系统分析,6 .4 .1 单服务台负指数分布M/M/1排队系统,模型的条件是：1、输入过程顾客源是无限的，顾客到达完全是随机的，单个到来，到达过程服从普阿松分布，且是平稳的；2、排队规则单队，且队长没有限制，先到先服务；3、服务机构单服务台，服务时间的长短是随机的，服从相同的指数分布 。,对于MM1模型有如下公式：,例1,某医院急诊室同时只能诊治一个病人，诊治时间服从指数分布，每个病人平均需要15分钟。病人按泊松分布到达，平均每小时到达3人。试对此排队队系统进行分

13、析。解 对此排队队系统分析如下：（1）先确定参数值：这是单服务台系统，有： 故服务强度为：,（2）计算稳态概率：这就是急诊室空闲的概率，也是病人不必等待立即就能就诊的概率。 而病人需要等待的概率则为：这也是急诊室繁忙的概率。,（2）计算系统主要工作指标。急诊室内外的病人平均数：急诊室外排队等待的病人平均数：病人在急诊室内外平均逗留时间：病人平均等候时间：,（4）为使病人平均逗留时间不超过半小时，那么平均服务时间应减少多少？由于代入=3，解得5，平均服务时间为： 15123min即平均服务时间至少应减少3min,(5)若医院希望候诊的病人90% 以上都能有座位,则候诊室至少应安置多少座位? 设应

14、该安置个座位,加上急诊室的一个座位,共有+1个。要使90% 以上的候诊病人有座位，相当于使“来诊的病人数不多于+1个”的概率不少于90%，即,两边取对数（x2）lg lg0.1因 1，故所以 x 6即候诊室至少应安置6个座位。,第三节 M / M / S 模型,此模型与M/M/1模型不同之处在于有S个服务台，各服务台的工作相互独立，服务率相等，如果顾客到达时，S个服务台都忙着，则排成一队等待，先到先服务的单队模型。整个系统的平均服务率为s，*/s，（*1）为该系统的服务强度。,1、状态概率,2、主要运行指标3、系统状态N S的概率,例2 承接例1，假设医院增强急诊室的服务能力，使其同时能诊治两

15、个病人，且平均服务率相同，试分析该系统工作情况。,解 这相当于增加了一个服务台，故有： S=2,=3人/h，=4人/h,病人必须等候的概率,即系统状态N2的概率：,表61 两个系统的比较,例3 某医院挂号室有三个窗口，就诊者的到达服从泊松分布，平均到达率为每分钟0.9人，挂号员服务时间服从指数分布，平均服务率每分钟0.4人，现假设就诊者到达后排成一队，依次向空闲的窗口挂号，显然系统的容量和顾客源是不限的，属于M/M/S型的排队服务模型。求：该系统的运行指标 解,如果在例3中，就诊者到达后在每个挂号窗口各自排成一队，即排成3队，且进入队列后不离开，各列间也互不串换，这就形成3个队列，而例3中的其它条件不变。假设每个队列平均到达率相等且为：1230.9/30.3（人/分钟）这样，原来的M/M/3系统就变成了3个M/M/1型的子系统。 现按M/M/1型计算主要运行指标，并与上面的例子进行对比分析，结果见表62,表62 两个模型的比较,6.6 排队系统实例分析,（1）快餐店的学问；,