所有分类排队论学习教案.pptx

《所有分类排队论学习教案.pptx》由会员分享，可在线阅读，更多相关《所有分类排队论学习教案.pptx（78页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、所有所有(suyu)分类排队论分类排队论第一页，共78页。2 2 排队：生活中存在大量排队：生活中存在大量(dling)有形和无形的排队或拥挤现象，如旅客购票，轮有形和无形的排队或拥挤现象，如旅客购票，轮船等待进港等排队等待服务的现象。船等待进港等排队等待服务的现象。排队排队(pi du)与排队与排队(pi du)论论队列可能是有形的，如在火车站售票处买票，也可能是无形的，如电队列可能是有形的，如在火车站售票处买票，也可能是无形的，如电话订票；顾客可能是人，如在银行等待取款的顾客，也可能是物，如话订票；顾客可能是人，如在银行等待取款的顾客，也可能是物，如等待进港的船只；服务台可能是人，如售票员

2、，也可能是物，如机场等待进港的船只；服务台可能是人，如售票员，也可能是物，如机场跑道；顾客数可能有限，如等待买票的人，也可能无限，如泄洪问题跑道；顾客数可能有限，如等待买票的人，也可能无限，如泄洪问题(wnt)中的上游来水中的上游来水.第1页/共78页第二页，共78页。3 3排队论：就是通过对服务对象到来及服务时间的统计研究，得出一些些数量指标（等待时间、排队长度、忙期长短等）的统计规律，然后排队论：就是通过对服务对象到来及服务时间的统计研究，得出一些些数量指标（等待时间、排队长度、忙期长短等）的统计规律，然后(rnhu)根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满

3、足服务对象的需要，又能使机构的费用最经济或某些指标最优的一门科学。根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，又能使机构的费用最经济或某些指标最优的一门科学。排队论起源于排队论起源于20世纪初的电话通话。世纪初的电话通话。19091920年丹麦数学家、电年丹麦数学家、电气工程师爱尔朗（气工程师爱尔朗（A.K.Erlang）用概率论方法研究电话通话问题，从）用概率论方法研究电话通话问题，从而开创了这门应用而开创了这门应用(yngyng)学科，并为这门学科建立许多基本原则。学科，并为这门学科建立许多基本原则。他在热力学统计平衡理论的启发下，成功地建立了

4、电话统计平衡模型，他在热力学统计平衡理论的启发下，成功地建立了电话统计平衡模型，并由此得到一组递推状态方程，从而导出著名的埃尔朗电话损失率公并由此得到一组递推状态方程，从而导出著名的埃尔朗电话损失率公式。式。第2页/共78页第三页，共78页。4 4 20世纪世纪30年代中期，当费勒年代中期，当费勒(W.Feller)引进了生灭过程时，排队论才被数学界承认为引进了生灭过程时，排队论才被数学界承认为一门重要的学科。在第二次世界大战期间和第二次世界大战以后，排队论在运筹学这个一门重要的学科。在第二次世界大战期间和第二次世界大战以后，排队论在运筹学这个(zh ge)新领域中变成了一个重要的内容。新领域

5、中变成了一个重要的内容。20世纪世纪50年代初，堪道尔年代初，堪道尔(D.G.Kendall)对排对排队论作了系统的研究，他用嵌入马尔柯夫队论作了系统的研究，他用嵌入马尔柯夫(A.A.Markov)链方法研究排队论，使排队论得链方法研究排队论，使排队论得到了进一步的发展。是他首先（到了进一步的发展。是他首先（1951年）用母组成的符号表示排队系统。年）用母组成的符号表示排队系统。作为运筹学的一个重要分支，排队论广泛应用于计算机网络作为运筹学的一个重要分支，排队论广泛应用于计算机网络,生产生产,运输运输,库存等库存等各项资源共享的随机各项资源共享的随机(su j)服务系统。服务系统。第3页/共7

6、8页第四页，共78页。5 5排队排队服务台服务服务台服务服务后顾客离去服务后顾客离去排队系统排队系统顾客到达顾客到达14.1排队排队(pi du)过程及其特征过程及其特征简单简单(jindn)排队的一般过程可表示为：排队的一般过程可表示为：排队系统排队系统 顾顾 客客 服务台服务台 服服 务务电话系统电话系统 电话呼叫电话呼叫 电话总机电话总机 接通呼叫或取消呼叫接通呼叫或取消呼叫售票系统售票系统 购票旅客购票旅客 售票窗口售票窗口 收款、售票收款、售票设备维修设备维修 出故障的设备出故障的设备 修理工修理工 排除设备故障排除设备故障 防空系统防空系统 进入阵地的敌机进入阵地的敌机 高射炮高射

7、炮 瞄准、射击，敌机被击落或离瞄准、射击，敌机被击落或离开开一、排队一、排队(pi du)系统与排队系统与排队(pi du)过程过程第4页/共78页第五页，共78页。6 6 服务系统服务台（通道服务系统服务台（通道(tngdo)）的数目：）的数目：如银行储蓄所的服务窗口；车站、码头的检票通道如银行储蓄所的服务窗口；车站、码头的检票通道(tngdo)；飞机跑道，海港的泊位等有单通道；飞机跑道，海港的泊位等有单通道(tngdo)单服务台，也有单通道单服务台，也有单通道(tngdo)多服务台，如联合办公的政务大厅。多服务台，如联合办公的政务大厅。1、服务、服务(fw)机构与服务机构与服务(fw)台台

8、顾客到达顾客到达服务完成离去服务完成离去服务台服务台单服务台排队单服务台排队单服务台排队单服务台排队(pi du)(pi du)系统，如系统，如系统，如系统，如图：图：图：图：过程与特征过程与特征第5页/共78页第六页，共78页。7 7多多服服务务台台排排队队(pi du)系统系统多队多队顾客到达 服务完成离去服务完成离去服务服务台台n服务服务台台2服务服务台台1服务完成离去服务完成离去服务完成离去服务完成离去顾客到达服务完成离去服务服务台台n服务服务台台2服务台服务台1 单队单队过程过程(guchng)与特征与特征多通道单服务台与多通道多服务台等不同多通道单服务台与多通道多服务台等不同(b

9、tn)组合方式。组合方式。第6页/共78页第七页，共78页。8 8过程过程(guchng)与特征与特征单队多台串联单队多台串联(chunlin)系统系统第7页/共78页第八页，共78页。9 9多队多台串并联系统多队多台串并联系统(xtng)顾客到达服务台是随机的。顾客到达服务台时，若服务台空闲，则立顾客到达服务台是随机的。顾客到达服务台时，若服务台空闲，则立刻接受服务；否则，顾客应等待刻接受服务；否则，顾客应等待(dngdi)至服务台空闲时，再接受服至服务台空闲时，再接受服务务.顾客接受服务后即离开服务台顾客接受服务后即离开服务台.第8页/共78页第九页，共78页。10102、顾客、顾客(gk

10、)到达过程：到达过程：顾客顾客(gk)依何种统计规律到达服务台的过程。依何种统计规律到达服务台的过程。如：去银行如：去银行(ynhng)储蓄所存取款，人与人往往事先不相互联系，即独立到达，到达的时间也具有随机性。群体无限储蓄所存取款，人与人往往事先不相互联系，即独立到达，到达的时间也具有随机性。群体无限又称输入过程：指顾客到达的规律，如顾客数（有限或无限），顾客到达的方式（批量或单个），相继到达的顾客之间的时间间隔的分布。又称输入过程：指顾客到达的规律，如顾客数（有限或无限），顾客到达的方式（批量或单个），相继到达的顾客之间的时间间隔的分布。食堂打饭，批量，有限食堂打饭，批量，有限过程与特征过

11、程与特征第9页/共78页第十页，共78页。1111（1）平稳性：在时间区间）平稳性：在时间区间 t,t+t)内到达内到达k个顾客的概率与个顾客的概率与t无关，无关，只与只与 t 有关，记为有关，记为 pk(t）；）；（2）无后效性：不相交的时间区间内到达的顾客数互相独立；）无后效性：不相交的时间区间内到达的顾客数互相独立；（3）普通性：在足够短的时间内到达多于一个顾客的概率可以）普通性：在足够短的时间内到达多于一个顾客的概率可以(ky)忽略；忽略；（4）有限性：任意有限个区间内到达有限个顾客的概率等于）有限性：任意有限个区间内到达有限个顾客的概率等于1。当满足当满足(mnz)以下四个条件时，这

12、种到达过程称为泊松流（泊松过程以下四个条件时，这种到达过程称为泊松流（泊松过程）。）。泊松分布泊松分布(fnb)：P(x)=x e-/x!(x=0,1,2,)其中：其中：为单位时间平均到达的顾客数为单位时间平均到达的顾客数过程与特征过程与特征第10页/共78页第十一页，共78页。1212 P（服务（服务(fw)时间时间 t)=1-e-t 。二、服务时间二、服务时间(shjin)分布分布到来的顾客从开始接受服务到服务完成所花费的时间，由于受来客到来的顾客从开始接受服务到服务完成所花费的时间，由于受来客(lik)业务多少、复杂程度等多种因素影响，服务时间是随机变量。业务多少、复杂程度等多种因素影响

13、，服务时间是随机变量。其中：其中：为平均服务率，即单位时间服务的顾客数，为平均服务率，即单位时间服务的顾客数，一般来说一般来说,简单的排队系统的服务时间往往服从负指数分布简单的排队系统的服务时间往往服从负指数分布,即每位患者接受服务的时间是独立同分布的即每位患者接受服务的时间是独立同分布的,其分布函数为其分布函数为过程与特征过程与特征第11页/共78页第十二页，共78页。1313三、排队三、排队(pi du)规则规则2.等待制：顾客到达时等待制：顾客到达时,如果所有服务台都没有空闲如果所有服务台都没有空闲,他们就排他们就排 队等待队等待.等待服务的次序又有各种不同的规则：等待服务的次序又有各种

14、不同的规则：先到先服务先到先服务,如就诊、排队取药等；如就诊、排队取药等；（FCFS）后到先服务后到先服务,如医院处理急症病人；（如医院处理急症病人；（LCFS）随机服务随机服务,服务台空闲时服务台空闲时,随机挑选等待的患者随机挑选等待的患者(hunzh)进行进行服务；服务；RS 优先权服务优先权服务,如照顾号如照顾号.PP 过程过程(guchng)与特征与特征（分为三类：损失制、等待制、混合制）（分为三类：损失制、等待制、混合制）1.损失制：顾客到达时损失制：顾客到达时,如果所有服务台都没有空闲如果所有服务台都没有空闲,该顾客不该顾客不 愿等待，就随即从系统消失愿等待，就随即从系统消失.3.

15、混合制：既有等待又有损失的情况混合制：既有等待又有损失的情况,如患者等待时考虑排队的如患者等待时考虑排队的 队长、等待时间的长短等因素而决定去留队长、等待时间的长短等因素而决定去留.队列的数目可是单列，也可是多列的；队列的数目可是单列，也可是多列的；容量可能是有限的，也可能是无限的。容量可能是有限的，也可能是无限的。第12页/共78页第十三页，共78页。1414四、平稳四、平稳(pngwn)状态：状态：求解状态概率求解状态概率Pn(t)的方法是建立含的方法是建立含Pn(t)的微分差分方程。通过求解微分差分方程得的微分差分方程。通过求解微分差分方程得到系统瞬态解。由于瞬态解一般到系统瞬态解。由于

16、瞬态解一般(ybn)求出确定值比较困难，即便求得一般求出确定值比较困难，即便求得一般(ybn)也很难使用。因此常常使用它的极限：也很难使用。因此常常使用它的极限：称为称为(chn wi)(chn wi)稳态稳态(steady state)(steady state)解，或解，或称统计平衡状态称统计平衡状态(Statistical Equilibrium (Statistical Equilibrium State)State)的解。的解。过程与特征过程与特征第13页/共78页第十四页，共78页。1515 稳态的物理意义稳态的物理意义(yy)(yy)图，系统的稳态一般很快都能达到，但实际图，系统

17、的稳态一般很快都能达到，但实际中达不到稳态的现象也存在。要注意的是求稳态概率中达不到稳态的现象也存在。要注意的是求稳态概率PnPn并不一定求并不一定求tt的极限的极限,只需求只需求Pn(t)=0 Pn(t)=0。过渡状态 稳定状态 pnt 排队系统状态变化示意图排队系统状态变化示意图过程过程(guchng)与特征与特征第14页/共78页第十五页，共78页。1616 Y 服务服务(fw)时间的概率分布，可取：时间的概率分布，可取：M、D、G、Ek 等等 D.G.Kendall，1953提出了分类法，称提出了分类法，称Kendall记号记号(适用适用(shyng)于并列服务台于并列服务台)X 顾客

18、到达顾客到达(dod)的概率分布，可取：的概率分布，可取：M D Ek GI G五、排队系统的符号表示五、排队系统的符号表示:X/Y/Z:d/e/f，M负指数分布负指数分布(Markov)，D确定型分布确定型分布(Deterministic)EkK阶爱尔朗分布阶爱尔朗分布(Erlang)GI 一般相互独立随机分布一般相互独立随机分布 (General Independent)，G 一般随机分布。一般随机分布。f排队规则，排队规则，FCFS，LCFS，RS，PP如如 M/M/1/FCFSM/M/1/FCFS即为顾客到达为泊松过程，服务时间为负指数分布，单台，无限容量，无限源，先到先服务的排队系统

19、模型。即为顾客到达为泊松过程，服务时间为负指数分布，单台，无限容量，无限源，先到先服务的排队系统模型。Z 服务台个数，取正整数；服务台个数，取正整数；过程与特征过程与特征d 排队系统的最大容量，可取正整数或排队系统的最大容量，可取正整数或e 顾客源的最大容量，可取正整数或顾客源的最大容量，可取正整数或 第15页/共78页第十六页，共78页。1717排队系统排队系统(xtng)类型，排队系统类型，排队系统(xtng)参数的统计推断和结构分析等，参数的统计推断和结构分析等，如排队系统如排队系统(xtng)的统计规律性：队长分布、等待时间分布和忙期分布等的统计规律性：队长分布、等待时间分布和忙期分布

20、等统计指标统计指标,瞬态、稳态情形。瞬态、稳态情形。六六、排队论研究排队论研究(ynji)的主要问题的主要问题排队系统的最优化问题：即包括最优设计排队系统的最优化问题：即包括最优设计(静态优化静态优化)，最优运营（动态，最优运营（动态优化）研究排队系统运行的效率指标，估计服务质量，确定系统的合理优化）研究排队系统运行的效率指标，估计服务质量，确定系统的合理结构和系统参数的合理值，以便实现对现有结构和系统参数的合理值，以便实现对现有(xin yu)系统合理改进和系统合理改进和对新建系统的最优设计等对新建系统的最优设计等过程与特征过程与特征第16页/共78页第十七页，共78页。1818忙期忙期指从

21、顾客指从顾客(gk)到达空闲服务机构起到服务机构再次为空闲这到达空闲服务机构起到服务机构再次为空闲这段时间长度。（忙期和一个忙期中平均完成服务顾客段时间长度。（忙期和一个忙期中平均完成服务顾客(gk)数都是衡量数都是衡量服务机构效率的指标，忙期关系到工作强度），等等服务机构效率的指标，忙期关系到工作强度），等等。Wq：平均：平均(pngjn)等待时间，一个顾客在系统中排队等待的时间。等待时间，一个顾客在系统中排队等待的时间。Ws：平均逗留：平均逗留(duli)时间，指一个顾客在系统中的停留时间。时间，指一个顾客在系统中的停留时间。Ls=系统中排队等待服务的顾客数系统中排队等待服务的顾客数Lq+

22、正被服务的顾客数正被服务的顾客数cLq:系统中排队等待服务的顾客数。系统中排队等待服务的顾客数。七、排队系统主要特征指标七、排队系统主要特征指标过程与特征过程与特征第17页/共78页第十八页，共78页。191914.214.2 M/M/1/FCFS M/M/1/FCFS模型模型(mxng)(mxng)设某储蓄所排队过程可用设某储蓄所排队过程可用M/M/1/模型描述。即：到达过程服从模型描述。即：到达过程服从泊松分布，服务时间服从负指数分布，单服务台，排队长度泊松分布，服务时间服从负指数分布，单服务台，排队长度(chngd)无限制和顾客的来源无限制先到先服务。无限制和顾客的来源无限制先到先服务。

23、顾客平均到达率顾客平均到达率 ，顾客平均服务率，顾客平均服务率 ，(0当当wi+si-ti 0第19页/共78页第二十页，共78页。2121ti空闲服务时间 频次 理论次数 （分钟）fi pi 1 10 9 2 12 13 .合计到达间隔 频次 理论次数 （分钟）fi pi 1 10 9 2 8 11 .合计第20页/共78页第二十一页，共78页。2222 1.1.系统中无顾客的概率系统中无顾客的概率系统中无顾客的概率系统中无顾客的概率 P0=1 P0=1 /2.2.平均排队的顾客数平均排队的顾客数平均排队的顾客数平均排队的顾客数 Lq=Lq=2/2/()3.3.系统中的平均顾客数系统中的平均

24、顾客数系统中的平均顾客数系统中的平均顾客数 Ls=Lq+Ls=Lq+/4.4.顾客花在排队上的平均等待顾客花在排队上的平均等待顾客花在排队上的平均等待顾客花在排队上的平均等待(dngdi)(dngdi)时间时间时间时间 Wq=Lq/Wq=Lq/5.5.顾客在系统中的平均逗留时间顾客在系统中的平均逗留时间顾客在系统中的平均逗留时间顾客在系统中的平均逗留时间 Ws=Wq+1/Ws=Wq+1/6.6.顾客得不到及时服务必须排队等待顾客得不到及时服务必须排队等待顾客得不到及时服务必须排队等待顾客得不到及时服务必须排队等待(dngdi)(dngdi)的概率的概率的概率的概率 Pw=Pw=/7.7.系统中

25、恰好有系统中恰好有系统中恰好有系统中恰好有 n n 个顾客的概率个顾客的概率个顾客的概率个顾客的概率 Pn=(Pn=(/)n P0)n P0二、计算二、计算(j sun)系统特征值并进行系统分析系统特征值并进行系统分析主要主要(zhyo)数量指标公式如下数量指标公式如下:第21页/共78页第二十二页，共78页。23 （4）平均）平均(pngjn)队长：队长：Lq=2/()=(0.6)2/0.8(0.8 0.6)=2.25 (个个)单台泊松单台泊松三、示例三、示例(shl)求解求解1、特征指标、特征指标(zhbio)计算：计算：（1）平均到达率）平均到达率：=36/60=0.6（2）平均服务率）

26、平均服务率 =48/60=0.8。（3）系统中没有顾客的概率：）系统中没有顾客的概率：P0=1 /=1 0.6/0.8=0.25,例：某储蓄所只有一个服务窗口。根据经验，假设顾客的到达过程服从泊松分例：某储蓄所只有一个服务窗口。根据经验，假设顾客的到达过程服从泊松分布，平均每小时到达顾客布，平均每小时到达顾客36人；储蓄所的服务时间服从负指数分布，平均每人；储蓄所的服务时间服从负指数分布，平均每小时能处理小时能处理48位顾客的业务。试求这个排队系统的数量指标。位顾客的业务。试求这个排队系统的数量指标。第22页/共78页第二十三页，共78页。2424P P P Pn n n n=(=(=(=(/

27、)n n n n P P P P0 0 0 0=(0.75)=(0.75)=(0.75)=(0.75)n n n n 0.25,n=1,2,0.25,n=1,2,0.25,n=1,2,0.25,n=1,2,。系统里的顾客数系统里的顾客数概率概率系统里的顾客数系统里的顾客数概率概率00.250040.079110.187550.059320.140660.044530.105570.1335单台泊松单台泊松储蓄所的排队储蓄所的排队(pi du)系统里有系统里有n个顾客的概率列入表个顾客的概率列入表14-1：（5）系统）系统(xtng)中平均顾客数：中平均顾客数：Ls=Lq+/=2.25+0.6/

28、0.8=3(个个),（6）平均）平均(pngjn)排队等待时间：排队等待时间：Wq=Lq/=2.25/0.6=3.75（分钟）（分钟）（7）平均逗留时间：）平均逗留时间：Ws=Wq+1/=3.75+1/0.8=5（分钟）（分钟）（8）必须排队等待概率：）必须排队等待概率：Pw=/=0.6/0.8=0.75（9）系统中有）系统中有n个顾客的概率：个顾客的概率：第23页/共78页第二十四页，共78页。2525 通过计算数据与表中数据，可知通过计算数据与表中数据，可知(k zh)储蓄所的排队系统并不尽如人意，到达储蓄所有储蓄所的排队系统并不尽如人意，到达储蓄所有75%的概率要排队等待，排队的长度平均

29、为的概率要排队等待，排队的长度平均为2.25人，排队的平均时间为人，排队的平均时间为3.75分钟，是分钟，是1.25分钟的分钟的3倍，而且储蓄所里有倍，而且储蓄所里有7个或更多的顾客的概率为个或更多的顾客的概率为13.35%，这个概率太高了。而要提高服务水平，减少顾客的平均排队时间和平均服务时间，一般可采用两种措施：，这个概率太高了。而要提高服务水平，减少顾客的平均排队时间和平均服务时间，一般可采用两种措施：单台泊松单台泊松第一第一(dy)，减少服务时间，提高服务率；，减少服务时间，提高服务率；2、计算结果分析、计算结果分析(fnx)第二，增加服务台即增加服务窗口。第二，增加服务台即增加服务窗

30、口。第24页/共78页第二十五页，共78页。2626不增加服务不增加服务(fw)窗口，而增加新型点钞机，建立储户管理信息系统，可以缩短储蓄所窗口，而增加新型点钞机，建立储户管理信息系统，可以缩短储蓄所每笔业务的服务每笔业务的服务(fw)时间，使每小时平均服务时间，使每小时平均服务(fw)的顾客数目从原来的的顾客数目从原来的48人提高到人提高到60人，即每分钟平均服务人，即每分钟平均服务(fw)的顾客数从的顾客数从0.8人提高到人提高到1人，人，3、改进、改进(gijn)该服务系统方法该服务系统方法缩短储蓄所每笔业务缩短储蓄所每笔业务(yw)的服的服务时间务时间设法将平均服务率由设法将平均服务率

31、由48人提高到人提高到60人人/小时。小时。即：即：=0.6，=1（1）重新计算系统特征指标，计算得到的结果如表）重新计算系统特征指标，计算得到的结果如表14-2所示所示系统里没有顾客的概率系统里没有顾客的概率:P00.4平均排队的顾客人数平均排队的顾客人数:Lq0.9人人系统里的平均顾客数系统里的平均顾客数:Ls1.5人人一位顾客平均排队时间一位顾客平均排队时间:Wq1.5分钟分钟一位顾客平均逗留时间一位顾客平均逗留时间:Ws2.5分钟分钟顾客到达系统必须等待排队的概率顾客到达系统必须等待排队的概率Pw0.6系统里有系统里有7个或更多顾客的概率为个或更多顾客的概率为P(n7)0.027第25

32、页/共78页第二十六页，共78页。27从上表从上表(shn bio)可以看出由于把服务率从可以看出由于把服务率从0.8提高到提高到1，其排队系统有了很大的改进，其排队系统有了很大的改进，顾客平均排队时间由顾客平均排队时间由3.75分钟减少到分钟减少到1.5分钟，顾客平均逗留时间从分钟，顾客平均逗留时间从5分钟减少到分钟减少到2.5分钟，分钟，在系统里有在系统里有7个或更多顾客的概率有大幅度的下降，从个或更多顾客的概率有大幅度的下降，从13.35%下降到下降到2.79%。单台泊松单台泊松系统里没有顾客的概率系统里没有顾客的概率:P00.4平均排队的顾客人数平均排队的顾客人数:Lq0.9人人系统里

33、的平均顾客数系统里的平均顾客数:Ls1.5人人一位顾客平均排队时间一位顾客平均排队时间:Wq1.5分钟分钟一位顾客平均逗留时间一位顾客平均逗留时间:Ws2.5分钟分钟顾客到达系统必须等待排队的概率顾客到达系统必须等待排队的概率Pw0.6系统里有系统里有7个或更多顾客的概率为个或更多顾客的概率为P(n7)0.0272、计算结果分析、计算结果分析(fnx)第26页/共78页第二十七页，共78页。2828系统里没有顾客的概率系统里没有顾客的概率:P00.6250平均排队的顾客人数：平均排队的顾客人数：Lq0.2250人人系统里的平均顾客数系统里的平均顾客数：Ls0.6人人一位顾客平均排队时间：一位顾

34、客平均排队时间：Wq0.75分钟分钟一位顾客平均逗留时间：一位顾客平均逗留时间：Ws2.000分钟分钟顾客到达系统必须等待排队的概率顾客到达系统必须等待排队的概率Pw0.375系统里有系统里有7个或更多顾客的概率：个或更多顾客的概率：P(n7)0.0074增设一个服务窗口，排队的规则为每个窗口排一个队，先到先服务，并假设顾客一增设一个服务窗口，排队的规则为每个窗口排一个队，先到先服务，并假设顾客一旦排了一个队，就不能再换到另一个队上去。这种处理方法就是把顾客分流旦排了一个队，就不能再换到另一个队上去。这种处理方法就是把顾客分流(fn li)，把一个排队分成两个排队系统，每个排队系统中有一个服务

35、台，每个系统的，把一个排队分成两个排队系统，每个排队系统中有一个服务台，每个系统的服务率仍然为服务率仍然为0.8，但到达率由于分流，但到达率由于分流(fn li)，只有原来的一半了，只有原来的一半了，=0.3，这，这时可求得每一个排队系统的数量指标如表时可求得每一个排队系统的数量指标如表14-3单台泊松单台泊松4、改进该服务、改进该服务(fw)系统方法系统方法 增设窗口分流顾客增设窗口分流顾客 =0.3，=0.8第27页/共78页第二十八页，共78页。2929比较知道，采用第二个方法的服务水平也使得原来的服务水平有了很大的提高，顾客比较知道，采用第二个方法的服务水平也使得原来的服务水平有了很大

36、的提高，顾客平均排队平均排队(pi du)时间减少到了时间减少到了0.75分钟，顾客平均逗留时间减少到分钟，顾客平均逗留时间减少到2分钟。分钟。0.62500.2250人人0.6人人0.75分钟分钟2.000分钟分钟0.3750.00740.40.9人人1.5人人1.5分钟分钟2.5分钟分钟0.60.027系统里没有顾客的概率系统里没有顾客的概率平均排队的顾客人数平均排队的顾客人数系统里的平均顾客数系统里的平均顾客数一位顾客平均排队时间一位顾客平均排队时间一位顾客平均逗留时间一位顾客平均逗留时间顾客到达系统必须等待排队的概率顾客到达系统必须等待排队的概率系统里有系统里有7个或更多顾客的概率为个

37、或更多顾客的概率为单台泊松单台泊松如果在第二种方法中把排队的规则如果在第二种方法中把排队的规则(guz)变一下，在储蓄所里只排一个队，这样的变一下，在储蓄所里只排一个队，这样的排队系统就变成了排队系统就变成了 M/M/2排队系统。排队系统。5、不同系统改进方式效果、不同系统改进方式效果(xiogu)的比较的比较=0.6，=1=0.3，=0.8第28页/共78页第二十九页，共78页。3030三、关于三、关于(guny)泊松流泊松流的证明的证明设设N（t)表示在时间区间表示在时间区间0,t内到达内到达(dod)的顾客数（的顾客数（t0)令令Pn(t1，t2)表示在区间表示在区间t1，t2)内有内有

38、n个顾客到达个顾客到达(dod)的概率，即：的概率，即：Pn(t1，t2)=PN(t2)-N(t1)=n ，(n0)当符合以下三个条件，可说到达顾客当符合以下三个条件，可说到达顾客(gk)形成泊松流。形成泊松流。1、在不相交（重叠）的时间区间内到达的顾客数互相独立；、在不相交（重叠）的时间区间内到达的顾客数互相独立；2、在时间区间、在时间区间 t,t+t)内到达内到达k个顾客的概率与个顾客的概率与t无关，只与无关，只与 t 有关，有关，约与区间长约与区间长 t成正比，即：成正比，即：P1(t，t+t)=t+o(t)其中：其中：o(t)，当，当 t 0时关于时关于 t的高阶无穷小；的高阶无穷小；

39、0,常数，它表示单常数，它表示单位时间有一个顾客到达的概率，称为概率强度位时间有一个顾客到达的概率，称为概率强度3、对于充分小的、对于充分小的 t 在区间在区间t,t+t)内有内有2个以上顾客到达的概率极小，可个以上顾客到达的概率极小，可以忽略不计。以忽略不计。在上述条件下研究顾客到达数为在上述条件下研究顾客到达数为n的概率分布的概率分布单台泊松单台泊松第29页/共78页第三十页，共78页。3131由条件由条件(tiojin)2（与（与t无关），总可以取时间由无关），总可以取时间由0算起，并简记算起，并简记Pn(0，t)=Pn(t)由条件由条件(tiojin)2，3容易推得在容易推得在t,t+

40、t)区间内没有顾客到区间内没有顾客到达的概率：达的概率：P0(t，t+t)=1-t+o(t)，（无人到达与，（无人到达与1个以上个以上(yshng)到达对立）到达对立）在求在求Pn(t)时，通常采用建立未知函数的微分方程的方法，先求未知函数时，通常采用建立未知函数的微分方程的方法，先求未知函数Pn(t)由时刻由时刻t到到t+t的改变量，从而建立起的改变量，从而建立起t时刻的概率分布与时刻的概率分布与t+t时刻概率分布的关系方时刻概率分布的关系方程。程。对于区间对于区间0,t+t)可分成两个互不重叠的区间可分成两个互不重叠的区间0,t)和和t,t+t)，设现在到达，设现在到达的顾客总数是的顾客总

41、数是n，分别出现在这两个区间上，不外乎下列三种情况，分别出现在这两个区间上，不外乎下列三种情况区间区间 0，t)t，t+t）0，t+t）情况情况 个数个数 概率概率 个数个数 概率概率 个数个数 概概率率(A)n Pn(t)0 1-t+o(t)n Pn(t)(1-t+o(t)(B)n-1 Pn-1(t)1 t n Pn-1(t)t(C)n-2 Pn-2(t)2 o(t)n o(t)n-3 Pn-3(t)3 o(t)n o(t).0 Pn(t)n o(t)n o(t)单台泊松单台泊松第30页/共78页第三十一页，共78页。3232区间区间 0，t)t，t+t）0，t+t）情况情况 个数个数 概率

42、概率 个数个数 概率概率 个数个数 概概率率(A)n Pn(t)0 1-t+o(t)n Pn(t)(1-t+o(t)(B)n-1 Pn-1(t)1 t n Pn-1(t)t(C)n-2 Pn-2(t)2 o(t)n o(t)n-3 Pn-3(t)3 o(t)n o(t).0 Pn(t)n o(t)n o(t)因为，在区间因为，在区间0,t+t)内到达内到达n个顾客应是表中三个互不相容的情个顾客应是表中三个互不相容的情形形(qng xing)之一，所以其概率：之一，所以其概率：P n(t，t+t)应是三者概率之和。应是三者概率之和。Pn(t，t+t)=Pn(t)(1-t)+Pn-1(t)t+o(

43、t)=Pn(t)-Pn(t)t+Pn-1(t)t+o(t)Pn(t，t+t)-Pn(t)t=-Pn(t)+Pn-1(t)+o(t)/t单台泊松单台泊松因此因此(ync)可写到前面可写到前面(qin mian)第31页/共78页第三十二页，共78页。3333Pn(t，t+t)-Pn(t)t=-Pn(t)+Pn-1(t)+o(t)/t令：令：t0，可写成微分形式，有下列，可写成微分形式，有下列(xili)方程，并注意到初方程，并注意到初始条件始条件dPn(t)dt=-Pn(t)+Pn-1(t)Pn(0)=0 （在在0时刻系统中有时刻系统中有n个顾客的概率等于个顾客的概率等于0）当当n=0时，到达顾

44、客不存在时，到达顾客不存在(cnzi)n-1,n-2,即没有即没有(A)(B)两种情况，所以：两种情况，所以：dP0(t)dt=-P0(t)P0(0)=1解以上解以上(yshng)两式，得两式，得:Pn(t)=(t)nn！e-tn=1,2,3.，t 0(在在0时刻系统中有时刻系统中有0个顾客的概率等于个顾客的概率等于1）单台泊松单台泊松当定义t为1个单位长度在一个时间单位到达x个顾客的概率P(x),为14.1式第32页/共78页第三十三页，共78页。3434dP0(t)dt=-P0(t)由由解得解得:P0(t)=e-tdPn(t)dt=-Pn(t)+Pn-1(t)对于对于两边乘以积分因子(yn

45、z)et 并移项，有：dPn(t)dt+Pn(t)et=et Pn-1(t)etddt Pn(t)et=et Pn-1(t)进行积分得：进行积分得：Pn(t)et=Pn-1(t)et dt依次(yc)代入n=1,2,.P1(t)et=tn=1:P1(t)=te-tPn(t)=(t)nn！e-tn=1,2,3.，t 0分布分布(fnb)证明：证明：n=2：,n=3EN=tDN=t为平均到达数为平均到达数第33页/共78页第三十四页，共78页。3535 系统系统(xtng)(xtng)中有中有n n个顾客个顾客四、关于模型四、关于模型(mxng)M/M/1:/FCFS 特征指标的证明特征指标的证明

46、1.1.稳态概率稳态概率(gil)Pn(gil)Pn的计算的计算 在任意时刻在任意时刻t t，状态为，状态为n n的概率的概率P Pn n(t)(t)（瞬态概率），它决定了系统的运行特征。（瞬态概率），它决定了系统的运行特征。已知顾客到达服从参数为已知顾客到达服从参数为的泊松过程，服务时间服从参数为的泊松过程，服务时间服从参数为的负指数分布。的负指数分布。现仍然通过研究区间现仍然通过研究区间 t，t+tt）的变化来求解在时刻）的变化来求解在时刻t+tt，系统中有，系统中有 n n 个个顾客不外乎有下列四种情况。（顾客不外乎有下列四种情况。（t，t+tt）内到达或离开）内到达或离开,2 2个及其

47、以上个及其以上没列没列入）。入）。？单台泊松单台泊松第34页/共78页第三十五页，共78页。3636这四种情况这四种情况(qngkung)是互不相容的，所以是互不相容的，所以Pn(t+t)应是这四项之和，则有：应是这四项之和，则有：所有所有(suyu)(suyu)的高的高阶阶 无穷小和并无穷小和并单台泊松单台泊松第35页/共78页第三十六页，共78页。3737 令令t0t0，得关于，得关于P Pn n(t)(t)的微分差分方程：的微分差分方程：.(1)当当n=0时，只有表中的（时，只有表中的（A）、（）、（B）两种情况，因为在较小的）两种情况，因为在较小的t内不可能发生内不可能发生(fshng

48、)（D）（到达后即离去），若发生）（到达后即离去），若发生(fshng)可将可将t取小即可。取小即可。单台泊松单台泊松第36页/共78页第三十七页，共78页。3838 (2)(2)这这种种系系统统状状态态(n)随随时时间间(shjin)变变化化的的过过程程就就是是生生灭灭过过程（程（Birth and Death Process）。）。稳态时，稳态时，Pn(t)与时间与时间(shjin)无关无关,可以可以(ky)写写成成Pn,(3)(3)(4)(4)单台泊松单台泊松它对时间的导数为它对时间的导数为0，所以由，所以由(1)、(2)两式得：两式得：方程方程(1)、(2)解是瞬态解解是瞬态解,无法应

49、用。无法应用。第37页/共78页第三十八页，共78页。3939 由此可得该排队系统的状态由此可得该排队系统的状态(zhungti)转移图：转移图：由（由（4）得：）得：其中其中服务强度服务强度将其代入（将其代入（3）式并令）式并令n=1,2,(也可从状态转移图中看出也可从状态转移图中看出(kn ch)状态平衡方程状态平衡方程)得：得：(3)(3)(4)(4)关于关于Pn的差分的差分(ch fn)方程方程 n-1n-1n n n+1n+12 20 01 1 状态转移图状态转移图单台泊松单台泊松第38页/共78页第三十九页，共78页。4040 n=1n=1 n=2n=2 单台泊松单台泊松第39页/

50、共78页第四十页，共78页。4141 以此类推以此类推(y c li tu)，当，当n=n时，时，(5)(5)及概率性质知：及概率性质知：（数列的极限为数列的极限为）(6)(6)否则排队否则排队(pi du)无限远无限远 系统系统(xtng)稳态概稳态概率率系统的运行指标系统的运行指标单台泊松单台泊松第40页/共78页第四十一页，共78页。42422.系统系统(xtng)的运行指标的运行指标 (1)系统系统(xtng)中的队长中的队长Ls（平均队长）（平均队长）(0c时时多台泊松多台泊松7.系统中恰好有系统中恰好有 n 个顾客个顾客(gk)的概率的概率第48页/共78页第四十九页，共78页。5