排队论PPT学习课件学习教案

1、会计学1排队排队(pi du)论论PPT学习课件学习课件第一页，共72页。2022-7-6运筹学校级重点建设课程电子(dinz)教案2大纲要求：掌握排队论的基本概念、常见(chn jin)的到达时间间隔分布和服务时间分布特性，生灭过程及稳态概率。单服务台负指数分布排队模型；多服务台负指数排队模型；排队系统设计的最优化重点：掌握M/M/1模型及其应用难点：到达流的稳态概率和系统状态转移概率及其优化服务设计自学：M/G/1模型第1页/共72页第二页，共72页。2022-7-6运筹学校级重点建设课程(kchng)电子教案3第2页/共72页第三页，共72页。2022-7-6运筹学校级重点建设课程电子(

2、dinz)教案4到达的顾客要求的服务服务机构机械坏了 修理 修理工人修理工人 领取配件 管理员病人 就诊 医生打电话 通话 交换台文件 打印(d yn) 打印(d yn)机飞机降落 降落 跑道指挥机构顾客 就餐 服务员汽车 路口 红绿灯第3页/共72页第四页，共72页。2022-7-6运筹学校级重点建设课程电子(dinz)教案5排队结构服务机构顾客源顾客到达排队规则服务规则离去图1 排 队系统示意图第4页/共72页第五页，共72页。2022-7-6运筹学校级重点建设(jinsh)课程电子教案6第5页/共72页第六页，共72页。2022-7-6运筹学校级重点(zhngdin)建设课程电子教案7第

3、6页/共72页第七页，共72页。2022-7-6运筹学校级重点建设课程(kchng)电子教案8112n. . .12n。单队单服务台多队多服务台（并列)单队多服务台（并列）12n.12312单队多服务台（串列）混合形式第7页/共72页第八页，共72页。2022-7-6运筹学校级重点建设(jinsh)课程电子教案9 2)服务方式分为单个顾客服务和成批顾客服务。服务方式分为单个顾客服务和成批顾客服务。 3)服务时间分为确定服务时间分为确定(qudng)型型(定常时间）和随机型。定常时间）和随机型。 4)服务时间的分布在这里我们假定是平稳的。服务时间的分布在这里我们假定是平稳的。 我们研究的问题是：

4、输入是服从(fcng)某种分布，顾客的到达是相互独立到达的平稳过程；各列间不能相互转移、中途不能退出；单个单个地服务方式，服务服从(fcng)某种分布， FCFS。第8页/共72页第九页，共72页。2022-7-6运筹学校级重点(zhngdin)建设课程电子教案10最主要的、影响最大的是：最主要的、影响最大的是：顾客相继顾客相继(xingj)到达的间隔时间分布到达的间隔时间分布服务时间的分布服务时间的分布服务台数服务台数，1953提出了分类法，称为提出了分类法，称为Kendall记号记号(适用于并列服务台适用于并列服务台),1971又扩展成为：又扩展成为：X/Y/Z/A/B/C第9页/共72页

5、第十页，共72页。2022-7-6运筹学校级重点建设(jinsh)课程电子教案11第10页/共72页第十一页，共72页。2022-7-6运筹学校级重点建设课程(kchng)电子教案12Z填写并列的服务台数填写并列的服务台数A排队系统排队系统(xtng)的最大容量的最大容量NB顾客源数量顾客源数量m C排队规则（排队规则（FCFS、LCFS等。本章仅研究等。本章仅研究FCFS的排队规则）的排队规则）如如 M/M/1/FCFS即为顾客到达时间间隔为负指数分布，服务时间为负指数分布，单台，无限容量，无限源，先到先服务的排队系统即为顾客到达时间间隔为负指数分布，服务时间为负指数分布，单台，无限容量，无

6、限源，先到先服务的排队系统(xtng)模型。模型。第11页/共72页第十二页，共72页。2022-7-6运筹学校级重点建设(jinsh)课程电子教案13( (静态优化静态优化) )，最优运营（动态优化）。，最优运营（动态优化）。第12页/共72页第十三页，共72页。2022-7-6运筹学校级重点(zhngdin)建设课程电子教案14统计(tngj)推断最优设计性态问题(wnt)排队系统研究问题阶段示意图排队系统研究问题阶段示意图第13页/共72页第十四页，共72页。2022-7-6运筹学校级重点建设课程电子(dinz)教案15第14页/共72页第十五页，共72页。2022-7-6运筹学校级重点

7、建设(jinsh)课程电子教案16 2、根据排队(pi du)系统对应的理论模型求出用以判断系统运行优劣的基本数量指标的概率分布或特征数。 数量指标主要包括:(1) 队长：系统中的顾客数，它的数学期望记为Ls 。 队列长：系统中排队(pi du)等待服务的顾客数，它的数学期望记为Lq 。 系统中顾客数Ls =系统中排队(pi du)等待服务的顾客数Lq +正被服务的顾客数(2) 逗留时间：指一个顾客在系统中的停留时间，它的数学期望记为Ws。 第15页/共72页第十六页，共72页。2022-7-6运筹学校级重点建设课程(kchng)电子教案17 等待时间：指一个顾客在系统中排队等待的时间，它的数

8、学期望记为等待时间：指一个顾客在系统中排队等待的时间，它的数学期望记为Wq 。逗留时间逗留时间=等待时间等待时间+服务时间服务时间(3)忙期：指从顾客到达空闲服务机构起到服务机构再次忙期：指从顾客到达空闲服务机构起到服务机构再次(zi c)为空闲这段时间长度。（忙期和一个忙期中平均完成服务顾客数都是衡量服务机构效率的指标，忙期关系到工作强度）为空闲这段时间长度。（忙期和一个忙期中平均完成服务顾客数都是衡量服务机构效率的指标，忙期关系到工作强度） 为了计算上述的数量指标，必须首先计算系统状态的概率为了计算上述的数量指标，必须首先计算系统状态的概率 系统状态：系统状态是指系统中顾客数。系统状态：系

9、统状态是指系统中顾客数。第16页/共72页第十七页，共72页。2022-7-6运筹学校级重点建设课程(kchng)电子教案18 状态概率：用状态概率：用Pn(t)表示表示,即在即在t时刻系统中有时刻系统中有n个顾客个顾客(gk)的概率，也称瞬态概率。它是表述系统的各种性能指标的基础。的概率，也称瞬态概率。它是表述系统的各种性能指标的基础。 状态的可能值：状态的可能值： 队长没有限制时：队长没有限制时：n=0 ，1，2， 队长有限制时：队长有限制时：n= 0，1，2，3，N 即时制：服务台个数是即时制：服务台个数是c时，时，n=0 ，1，c 求解状态求解状态(zhungti)概率概率Pn(t)方

10、法：是建立含方法：是建立含Pn(t)的微分差分方程，通过求解微分差分方程得到系统瞬态解，由于瞬态解一般求出确定值比较困难，即便求得一般也很难使用。因此我们常常使用它的极限的微分差分方程，通过求解微分差分方程得到系统瞬态解，由于瞬态解一般求出确定值比较困难，即便求得一般也很难使用。因此我们常常使用它的极限(如果存在的话如果存在的话)：第17页/共72页第十八页，共72页。2022-7-6运筹学校级重点(zhngdin)建设课程电子教案19nttnp)(plim稳态的物理意义见右图，系统的稳态一般很快都能达到，但实际中达不到稳态的现象也存在稳态的物理意义见右图，系统的稳态一般很快都能达到，但实际中

11、达不到稳态的现象也存在(cnzi)。值得注意的是求稳态概率。值得注意的是求稳态概率Pn并不一定求并不一定求t的极限的极限,而只需求而只需求Pn(t)=0 即可。即可。过渡状态稳定状态pnt图3 排队系统状态变化示意图 称为称为(chn wi)稳态稳态(steady state)解，或称统计平衡状态解，或称统计平衡状态 (Statistical Equilibrium State)的解。的解。第18页/共72页第十九页，共72页。2022-7-6运筹学校级重点(zhngdin)建设课程电子教案20第19页/共72页第二十页，共72页。2022-7-6运筹学校级重点建设课程(kchng)电子教案2

12、1第20页/共72页第二十一页，共72页。2022-7-6运筹学校级重点建设(jinsh)课程电子教案22第21页/共72页第二十二页，共72页。2022-7-6运筹学校级重点建设(jinsh)课程电子教案23第22页/共72页第二十三页，共72页。2022-7-6运筹学校级重点建设课程电子(dinz)教案24随机变量：数随机变量：数 随着实验的结果的不同而变化随着实验的结果的不同而变化 离散型：离散型：的所有可能只有限的所有可能只有限(yuxin)或至多可列个或至多可列个 连续型：连续型：（）取值于某个区间（）取值于某个区间（a，b）分布函数分布函数(连续连续): xpxF aFbFbap

13、的概率分布的概率分布(离散): iixpxpi=1,2,311iixp第23页/共72页第二十四页，共72页。2022-7-6运筹学校级重点(zhngdin)建设课程电子教案25数学期望数学期望:(离散) E()= 1iiipxdxxxf (连续) E()= 方差方差: 2EED EE22= BApBpABp条件概率条件概率:密度函数密度函数:(连续) dttfxFx 0 xf 1dttf,第24页/共72页第二十五页，共72页。2022-7-6运筹学校级重点建设课程(kchng)电子教案26式中式中为常数为常数(chngsh)(0)，称，称X服从参数为服从参数为的泊松分布。的泊松分布。若在上

14、式中引入时间参数若在上式中引入时间参数t，即令，即令t代替代替，则有：，则有：!nenxPnn=0,1,2, （1）tnnenttP!)(t0，n=0,1,2, （2）第25页/共72页第二十六页，共72页。2022-7-6运筹学校级重点建设(jinsh)课程电子教案27)()(,1221ntNtNPttPn（t2t1，n0）第26页/共72页第二十七页，共72页。2022-7-6运筹学校级重点(zhngdin)建设课程电子教案28 无后效性（独立性）：各区间内的顾客无后效性（独立性）：各区间内的顾客(gk)到达数相互独立，即到达数相互独立，即Markov性。性。. . . . . . . t

15、0 t1 t2 tn-1 tn平稳性：即对于足够小的平稳性：即对于足够小的t，在时间，在时间(shjin)区间区间t，t+t)内有内有1个顾客到达的概率为个顾客到达的概率为)()(1tttttP， 当当Pn(t1,t2)符合于下述三个条件时，我们说顾客到达过程就是泊松过程或者说顾客到达形成普阿松流。符合于下述三个条件时，我们说顾客到达过程就是泊松过程或者说顾客到达形成普阿松流。 普阿松流的三个特性：普阿松流的三个特性：设表示单位时间内有一个顾客到达的概率第27页/共72页第二十八页，共72页。2022-7-6运筹学校级重点建设(jinsh)课程电子教案29 普通性：对充分小的普通性：对充分小的

16、t,在时间在时间(shjin)区间区间t,t+t）内有）内有2个或个或2个以上顾客到达的概率是个以上顾客到达的概率是t一高阶无穷小一高阶无穷小.)(1),(0tottttP 令令t1=0,t2=t, 则则Pn(t1,t2)=Pn(0,t)=Pn(t) 也就是也就是(jish)在在t,t+t内有一个顾客到达的概率与内有一个顾客到达的概率与t无关无关,而与而与t成正比。成正比。 0 是常数，称为概率强度是常数，称为概率强度2)(),(nntotttP即即由此知，在由此知，在(t，t+t)区间内没有顾客到达的概率为区间内没有顾客到达的概率为:ttttttptttpii)(1),(1),(10区间长度

17、为t时有n个顾客的概率第28页/共72页第二十九页，共72页。2022-7-6运筹学校级重点建设课程(kchng)电子教案30 为了求为了求Pn(t)，即，即Pn(0,t)，需要研究它在时刻，需要研究它在时刻t到到t+t时刻的改变量，也就是要建立时刻的改变量，也就是要建立Pn(t)的微分方程。的微分方程。 对于区间对于区间0，t+t)可以分成可以分成0，t)和和t，t+t)，其到达总数是，其到达总数是n，不外有下列三种，不外有下列三种(sn zhn)情况：所以有：情况：所以有：第29页/共72页第三十页，共72页。2022-7-6运筹学校级重点建设课程电子(dinz)教案310，t)t,t+t

18、0,t+t 区间情形个数概率个数概率概率A n pn(t) 0 1-t+ pn(t)(1-t+ (t) (t)B n-1 pn-1(t) 1t pn-1(t)t(t) (t)n-2 Pn-2(t) 2C n-3 Pn-3(t) 30 P0(t) n第30页/共72页第三十一页，共72页。2022-7-6运筹学校级重点建设课程电子(dinz)教案32令令t0取极限取极限(jxin)（并注意初始条件）得：（并注意初始条件）得：当当n=0时，没有时，没有(mi yu)B，C两种情况，则：两种情况，则：1)0(0P)()(00tPdttdP(4)()()1)()(1tttPttPttPnnn)()()

19、()()(1tttPttPtPttPnnnntttPtPttPttPnnnn)()()()()(1)()()(1tPtPdttdPnnnn0 (3)(0)0nP第31页/共72页第三十二页，共72页。2022-7-6运筹学校级重点建设课程电子(dinz)教案33代初始条件代初始条件(t=0)有有：CCt01n C C = 0= 0ttP)(n0（3）式两端）式两端(lin dun)乘乘 et 并移项得：并移项得：tetP)(0(5)（没有顾客到达的概率）dttPtdP)()(00由上式得：由上式得：CttP)(n0两边两边(lingbin)积分得：积分得：一阶台劳展开为一阶台劳展开为1-t第3

20、2页/共72页第三十三页，共72页。2022-7-6运筹学校级重点(zhngdin)建设课程电子教案34tntnetPetPdtd)()(1将将n=1,2,3代入（代入（6）得：）得：积分得：积分得：11101)()(dtetPetPtnttn(6)110011)()(dtetPetPttt(注意利用注意利用(5)式式)tdteettt1011tntntnetPetPedttdP)()()(1tntnntetPetPdttdPe)()()(1第33页/共72页第三十四页，共72页。2022-7-6运筹学校级重点建设课程电子(dinz)教案35如此继续如此继续(jx)递推下去得：递推下去得：te

21、ttP! 2)()(22（2个顾客到达的概率）个顾客到达的概率）（n个顾客到达的概率）个顾客到达的概率）tnnenttP!)()( 即随机变量即随机变量N(t)=n服从泊松分布。它的数学期望服从泊松分布。它的数学期望(qwng)和方差为：和方差为：tettP)(1（1个顾客到达的概率个顾客到达的概率）11011102111)()(dteetdtetPetPtttttt2221t第34页/共72页第三十五页，共72页。2022-7-6运筹学校级重点建设课程电子(dinz)教案361)0(,)(nxfexf则有由高等数学知，若设由高等数学知，若设.!.! 212nxxxenx即：即：tkkekt!

22、)(0!)()()(11ntnetnPtNEnntnn)!1()(11nttennt令令k=n-1，则：，则：!)()(0kttetNEkkttetetNEtt)(第35页/共72页第三十六页，共72页。2022-7-6运筹学校级重点建设课程电子(dinz)教案372121)()!1()()!2()(tntntttennnttttttettett22)() 1()() 1(ttNVar)(即：即：21221)(!)()()(tntnnettPnnntnn22)()()(tNEtNEtNVar同理方差为：同理方差为：211121)()!1()()!1()() 1()()!1()(tntntnte

23、tntnennntnnt第36页/共72页第三十七页，共72页。2022-7-6运筹学校级重点(zhngdin)建设课程电子教案38其概率密度函数为：其概率密度函数为：tTTedtdFtf)(t0tTetPtF1)(1)(0t0tetP)(0 没有顾客到达的概率没有顾客到达的概率为：为： (由（由（5）式而来）式而来)第37页/共72页第三十八页，共72页。2022-7-6运筹学校级重点建设(jinsh)课程电子教案39 由前知，由前知，表示单位时间内顾客平均到达数，这里表示单位时间内顾客平均到达数，这里1/表示顾客到达的平均间隔时间，两者是吻合表示顾客到达的平均间隔时间，两者是吻合(wnh)

24、的。的。 可以证明，间隔时间可以证明，间隔时间T独立且服从负指数分布与顾客到达形成泊松流是等价的。独立且服从负指数分布与顾客到达形成泊松流是等价的。 下面我们再谈一下服务时间下面我们再谈一下服务时间(shjin)的分布：的分布： 对顾客的服务时间对顾客的服务时间(shjin)，实际是系统处于忙期时两顾客相继离开系统的时间，实际是系统处于忙期时两顾客相继离开系统的时间(shjin)间隔，一般地也服从负指数分布，即：间隔，一般地也服从负指数分布，即：即即T服从负指数分布，由概率论知它的期望及方差为：服从负指数分布，由概率论知它的期望及方差为：1TE21TVar dxxxfTE)(第38页/共72页

25、第三十九页，共72页。2022-7-6运筹学校级重点建设(jinsh)课程电子教案40其中：其中：表示单位时间内能被服务完成的顾客数，即平均表示单位时间内能被服务完成的顾客数，即平均(pngjn)服务率。服务率。 1/表示一个顾客的平均表示一个顾客的平均(pngjn)服务时间。服务时间。 3.爱尔朗爱尔朗(Erlang)分布分布 设设v1, v2，, vk是是k个独立的随机变量个独立的随机变量(su j bin lin)，服从相同参数，服从相同参数k的负指数分布，那么：的负指数分布，那么：tetF1)(tetf)(，则，则令令 ，则，则称为称为服务强度服务强度。第39页/共72页第四十页，共7

26、2页。2022-7-6运筹学校级重点(zhngdin)建设课程电子教案41 串列的串列的k个服务台，每台服务时间相互独立，服从相同的负指数分布（参数个服务台，每台服务时间相互独立，服从相同的负指数分布（参数(cnsh)k），那么一顾客走完），那么一顾客走完k个服务台总共所需要服务时间就服从上述的个服务台总共所需要服务时间就服从上述的k阶阶Erlang分布。分布。0)!1()()(1tekktktftkkk则称则称T服从服从(fcng)k阶爱尔朗分布，其特征值为阶爱尔朗分布，其特征值为:1TE21kTVar,kT 21的概率密度是的概率密度是(可以证明可以证明)当当k=1k=1时，时， Erla

27、ng分布即为负指数分布；分布即为负指数分布；当当k增加时，增加时， Erlang分布逐渐变为对称的；分布逐渐变为对称的；当当k 30时，时， Erlang分布近似于正态分布；分布近似于正态分布；每一个服从每一个服从k ，因此，因此E(Ti)=1/ k ，且，且Ti之间相互独立之间相互独立bk(t)tk=1k=21/ Erlang分布曲线分布曲线k=3第40页/共72页第四十一页，共72页。2022-7-6运筹学校级重点建设课程电子(dinz)教案42 例例:有易碎物品有易碎物品500件件,由甲地运往乙地由甲地运往乙地,根据以往统计资料根据以往统计资料,在运输过程中易碎物品按普阿松流发生破碎在运

28、输过程中易碎物品按普阿松流发生破碎,其概率为其概率为0.002,现求现求:1.破碎破碎3件物品的概率件物品的概率;2.破碎少于破碎少于3件的概率和多于件的概率和多于3件的概率件的概率;3.至少至少(zhsho)有一件破损的概率有一件破损的概率. 解解:1.求破碎求破碎3件物品的概率件物品的概率: =0.002500=1 则则 P(k=3)=(3/3！)e-=(13/3！)e-1=0.0613 即物品破碎即物品破碎3件的概率为件的概率为6.13 2.破碎物品少于破碎物品少于3件的概率件的概率:第41页/共72页第四十二页，共72页。2022-7-6运筹学校级重点(zhngdin)建设课程电子教案

29、43 破碎物品少于破碎物品少于3件的概率件的概率(gil)为为91.97破碎物品多于破碎物品多于3件的概率件的概率(gil)为为:02. 098. 01!1430kkekp3.至少至少(zhsho)有一件破碎的概率为有一件破碎的概率为 Pk1=1-(1k/k!)e-=1-(10/0!)e-1=0.6329197. 02111!2120eekkknp第42页/共72页第四十三页，共72页。2022-7-6运筹学校级重点建设课程电子(dinz)教案44研究对象为单队、单服务台（服务台数为研究对象为单队、单服务台（服务台数为1），包括：），包括：（1）标准）标准(biozhn)M/M/1模型（模型（

30、M/M/1/）；）；（2）系统容量有限制（）系统容量有限制（M/M/1/N/）（3）有限顾客源（）有限顾客源（M/M/1/m）第43页/共72页第四十四页，共72页。2022-7-6运筹学校级重点建设课程电子(dinz)教案45 以后各节将介绍几个常见以后各节将介绍几个常见(chn jin)的排队模型。对排队模型，在给定输入和服务条件下，主要研究系统的下述运行指标：的排队模型。对排队模型，在给定输入和服务条件下，主要研究系统的下述运行指标： (1)系统的平均队长系统的平均队长Ls(期望值期望值)和平均队列长和平均队列长Lq期望值；期望值； (2)系统中顾客平均逗留时间系统中顾客平均逗留时间Ws

31、与队列中平均等待时间与队列中平均等待时间Wq； 本节只研究本节只研究M/M/1模型，下面分三种情况讨论：模型，下面分三种情况讨论：第44页/共72页第四十五页，共72页。2022-7-6运筹学校级重点(zhngdin)建设课程电子教案461、输入过程：顾客源无限，顾客单个到达，相互独立，服从普阿松分布，平稳；2、排队规则：单队，队长无限制，FCFS。3、服务机构：单服务台，各顾客服务时间相互独立，服从负指数分布。此外：假设到达时间间隔和服务时间是相互独立的。标准的标准的M/M/1模型即为模型即为M/M/1/FCFS模型模型第45页/共72页第四十六页，共72页。2022-7-6运筹学校级重点建

32、设课程电子(dinz)教案47区间(t,t+t)情况时刻t 的顾客 到达 离去时刻t+t的顾客(t, t+t)的概率0, t+t的概率(略去(t)Ann1-t+(t)1-t+(t)Pn(t)(1-t)(1-t)Bn+1n1-t+(t)t+(t)Pn+1(t) (1-t)(t)Cn-1nt+(t)1-t+(t)Pn-1(t) (t)(1-t)Dnnt+(t)t+(t)Pn(t) (t)(t)第46页/共72页第四十七页，共72页。2022-7-6运筹学校级重点(zhngdin)建设课程电子教案48 由于这四种情况是互不相容由于这四种情况是互不相容(xin rn)的，所以的，所以Pn(t+t)应是

33、这四项之和，将所有的高阶无穷小合并，则有：应是这四项之和，将所有的高阶无穷小合并，则有：tttPtttPtttPttPnnnn)1)()()1)(1)()(1)()1 ()(1ttttPn)()()()()()(1)(11ttPttPtPtttttPnnnn)()()()(11tttPttPnn第47页/共72页第四十八页，共72页。2022-7-6运筹学校级重点建设课程(kchng)电子教案49)()()()1)(11tttPttPtttPnnntttPtPtPttPttPnnnnn)()()()()()()(11令令t0，得关于，得关于Pn(t)的微分差分的微分差分(ch fn)方程：方程

34、：)()()()()(11tPtPtPdttdPnnnn(1) 当当n=0时，只有表中的（时，只有表中的（A）、（）、（B）两种情况，因为在较小的）两种情况，因为在较小的t内不可能内不可能(knng)发生（发生（D）（到达后即离去），若发生可将）（到达后即离去），若发生可将t取小即可。取小即可。第48页/共72页第四十九页，共72页。2022-7-6运筹学校级重点(zhngdin)建设课程电子教案50)()1)()1)()(100tttPttPttP)()()(100tPtPdttdP(2) 这种系统状态(n)随时间变化的过程(guchng)就是生灭过程(guchng)（Birth and D

35、eath Process），它可以描述细菌的生灭过程(guchng)。 对于方程(1)、(2)求解很麻烦，即便求得解也是瞬态解，无法应用。为此,我们只要求得稳态解即可。 稳态时，Pn(t)与时间无关，可以写成Pn， 它对时间的导数为0，所以由(1)、(2)两式得：在时刻t系统处于无顾客状态(zhungti)，而在t+t时刻内又没有顾客来到系统（必然没有离去事件）在时刻t系统有一个顾客接受服务，在t+t时刻内服务完毕离去，且在t+t时刻内又没有顾客来到系统第49页/共72页第五十页，共72页。2022-7-6运筹学校级重点(zhngdin)建设课程电子教案510)(11nnnPPP010PP(3

36、)(4) 上式即为关于上式即为关于(guny)Pn的差分方程。由此可得该排队系统的状态转移图：的差分方程。由此可得该排队系统的状态转移图：012n-1nn+1. .状态转换图由（由（4）得：）得：001PPP其中其中服务强度服务强度 将其代入（将其代入（3）式并令）式并令n=1,2,(也可从状态转移图中看出状态平衡也可从状态转移图中看出状态平衡(pnghng)方程方程)得：得：第50页/共72页第五十一页，共72页。2022-7-6运筹学校级重点(zhngdin)建设课程电子教案520)(120PPPn=10)(020PPP020202)()(1PPPPn=20)(231PPP0)(0230P

37、PP030302223)()(1PPPP第51页/共72页第五十二页，共72页。2022-7-6运筹学校级重点建设课程电子(dinz)教案53以此类推以此类推(y c li tu)，当，当n=n时，时，00)(PPPnnn(5)1(否则排队无限远，无法服务完否则排队无限远，无法服务完)10nnP以及概率性质知：以及概率性质知：111000PPnn(数列的极限为 )1110PnnP)1 (6)当=1时，似乎好象来一个顾客服务一个顾客，但这是在均衡条件下和所有的顾客的服务时间都相等(xingdng)时，才会出现不存在排队现象的这种理想的现象。在随机的情况下，这是不可能的。第52页/共72页第五十三

38、页，共72页。2022-7-6运筹学校级重点建设课程(kchng)电子教案54 上式就是系统稳态概率，以它为基础可以上式就是系统稳态概率，以它为基础可以 算出系统的运行算出系统的运行(ynxng)指标。指标。 2. 系统的运行系统的运行(ynxng)指标计算指标计算 (1) 系统中的平均顾客数（队长期望值系统中的平均顾客数（队长期望值Ls）nnnnsnPnL001.)1(.)1 ( 3)1 ( 2)1 (32nn.3322143322nnnn1.32n(01)1第53页/共72页第五十四页，共72页。2022-7-6运筹学校级重点建设课程(kchng)电子教案55Ls即:(7)nnnnqnPn

39、L111) 1() 1(nnnnn111)1 (12sL(8) (3) 顾客在系统中的平均逗留时间顾客在系统中的平均逗留时间(shjin)Ws 顾客在系统中的逗留时间顾客在系统中的逗留时间(shjin)是随机变量，可以证明，它服从参数为是随机变量，可以证明，它服从参数为-的负指数分布，分布函数的负指数分布，分布函数(2) 队列中等待的平均队列中等待的平均(pngjn)顾客数顾客数Lq（队列长期望值）（队列长期望值）第54页/共72页第五十五页，共72页。2022-7-6运筹学校级重点(zhngdin)建设课程电子教案56和密度和密度(md)函数为：函数为：wewF)(1)(wewf)()()(

40、（w0） 1wEWs)(WsLs (4)顾客在队列中的等待时间的期望值顾客在队列中的等待时间的期望值Wq 顾客在队列中的等待时间应为顾客在队列中的等待时间应为Ws减去平均服务减去平均服务(fw)时间。时间。111WsWq)(WqLq第55页/共72页第五十六页，共72页。2022-7-6运筹学校级重点建设(jinsh)课程电子教案57四个指标的关系四个指标的关系(gun x)为为(Little 公式公式)： 3. 系统(xtng)的忙期与闲期系统处于空闲状态的概率：系统处于空闲状态的概率：10P系统处于繁忙状态的概率：系统处于繁忙状态的概率：01) 0(PNPLsLq1swqwWsLsWqLq

41、1qswwqsLL下标s表示系统下标q表示队列第56页/共72页第五十七页，共72页。2022-7-6运筹学校级重点建设课程(kchng)电子教案58排队系统 服务台顾客 N 4 3 2 1被拒绝第57页/共72页第五十八页，共72页。2022-7-6运筹学校级重点建设课程(kchng)电子教案59)()()(100tPtPdttdP(2)对于对于(duy)(1)式，当式，当n=1,2,N-1时，也仍能成立。时，也仍能成立。)()()()()(1tPtPtPdttdPnnnn(1)(n=1,2,N-1)但当但当n=N时，有下面两种情况：时，有下面两种情况：第58页/共72页第五十九页，共72页

42、。2022-7-6运筹学校级重点建设(jinsh)课程电子教案60情 况时 刻t的 顾 客区 间 t, t+ t时 刻t+ t的 顾 客 数概 率AN无 离 去 （ 肯 定 不 到 达 ）NPN(t) (1- t)BN-1一 人 到 达 （ 无 离 去 ）NPN-1(t) tttPttPttPNNN)()1 ()()(1)()()(1tPtPdttdPNNN(8)其状态其状态(zhungti)转移图为转移图为:012n-1nn+1. .状态转换图. .N-1N第59页/共72页第六十页，共72页。2022-7-6运筹学校级重点(zhngdin)建设课程电子教案61在稳态情况在稳态情况(qngk

43、ung)下有：下有：010PP0)(11nnnPPP01NNPP(9)解（解（9）式得：）式得：01PP022PP0PPNNNnnNnnNnnPPP000001 而等比数列而等比数列(dn b sh li)10111NnNn第60页/共72页第六十一页，共72页。2022-7-6运筹学校级重点建设(jinsh)课程电子教案621011NPnNnP111(1,nN)(10) 注：当注：当=1时，试讨论其概率时，试讨论其概率Pn下面下面(xi mian)计算其运行指标：计算其运行指标：(1) 平均平均(pngjn)队长队长Ls：nPnLnNnNNnns01011nNnNn0111111) 1(1N

44、NN(1)试证=1时,Ls=N/2第61页/共72页第六十二页，共72页。2022-7-6运筹学校级重点建设课程电子(dinz)教案63（2）队列）队列(duli)长（期望值）长（期望值）NnsnqPLPnL10)1 () 1( 有效到达率有效到达率e的引入：的引入： Little公式可应用的条件是：其平均到达率公式可应用的条件是：其平均到达率是在系统是在系统有空时有空时的平均到达率。当系统满员时，就不能再应用了。要用就应该应用有效到达率。的平均到达率。当系统满员时，就不能再应用了。要用就应该应用有效到达率。 因为系统容量有限，当满员时，顾客将被拒绝，因此实际的顾客到达率为因为系统容量有限，当

45、满员时，顾客将被拒绝，因此实际的顾客到达率为0，与，与不一样，为了求其他指标，需要求得有效到达率为不一样，为了求其他指标，需要求得有效到达率为e：)1 (NeP)1 (0Pe可以验证：可以验证：第62页/共72页第六十三页，共72页。2022-7-6运筹学校级重点建设课程电子(dinz)教案64esesqLLLesSLWeqqLW此种情况此种情况(qngkung)的公式与的公式与前类似，前类似，只有只有Ls不不同，同，e与与 不同。求不同。求e必须先求必须先求得得P0或或Pn才行。才行。1)1 ()1 (0NqssPLPLw（3）顾客逗留）顾客逗留(duli)时间（期望值）时间（期望值）（4）

46、顾客等待时间（期望值）顾客等待时间（期望值）1sqwwLittle公式第63页/共72页第六十四页，共72页。2022-7-6运筹学校级重点建设课程电子(dinz)教案65例例2某单人理发馆共有某单人理发馆共有(n yu)六把椅子接待顾客排队，六把椅子接待顾客排队，无座时将离去，顾客平均到达率为无座时将离去，顾客平均到达率为3人人/h，理发时间平均为，理发时间平均为15分钟，求：分钟，求：(1) 求某一顾客到达就能理发的概率求某一顾客到达就能理发的概率;(2) 求需要等待的顾客数的期望值求需要等待的顾客数的期望值;(3) 求有效到达率求有效到达率;(4) 求一顾客在系统中的逗留时间和排队时间平

47、均值求一顾客在系统中的逗留时间和排队时间平均值;(5) 在可能到来的顾客中，有百分之几不等待就离开？在可能到来的顾客中，有百分之几不等待就离开？解：解：N=6+1=7，=3，=42778. 075. 0175. 0111810NP(1)11. 275. 0175. 0825. 075. 01) 1(18811NNsNL39. 1)2778. 01 (11. 2)1 (0PLLsq(2)第64页/共72页第六十五页，共72页。2022-7-6运筹学校级重点(zhngdin)建设课程电子教案66(3)89. 2)2778. 01 (4)1 (0Pemin8 .4373. 089. 211. 2hLWessmin86.2848. 089. 239. 1hLWeqq(4)(5)%71. 375. 075. 0175. 01117817NNPP0=0.27780P1=0.20836P2=0.15627P3=0.11720 = 0.9629=96.29%P4=0.08790 故拒绝的概率为3.71%P5=0.06593P6=0.04944第65页/共72页第六十六页，共72页。2022-7-6运筹学校级重点建设课程电子(di