运筹学排队论新.pptx

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

1、第十二章第十二章 排队论排队论 到达间隔的分布和服务时间的分布到达间隔的分布和服务时间的分布本章内容本章内容基本概念基本概念单服务台负指数分布排队系统的分析单服务台负指数分布排队系统的分析多服务台负指数分布排队系统的分析多服务台负指数分布排队系统的分析一般服务时间一般服务时间M/G/1模型模型第1页/共131页排队论(Queuing Theory)，又称随机服务系统理论(Random ServiceSystemTheory)。1909年由丹麦工程师爱尔朗(A.KErlang)在研究电话系统时创立的。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。特

2、别是自二十世纪60年代以来，由于计算机的飞速发展，使排队论的应用有了更广阔的前景。第2页/共131页Where the Time Goes?美国人一生中平均要花费美国人一生中平均要花费-6年年 饮食饮食5年年 排队等待排队等待4年年 做家务做家务2年年 回电话不成功回电话不成功 1年年 寻找放置不当的物品寻找放置不当的物品8个月个月 打开邮寄广告打开邮寄广告6个月个月 停在红灯前停在红灯前第3页/共131页商业服务系统商业服务系统系统类型系统类型顾客顾客服务台服务台理发店理发店人人理发师理发师银行出纳服务银行出纳服务人人出纳出纳ATMATM机服务机服务人人ATMATM机机商店收银台商店收银台人

3、人收银员收银员管道服务管道服务阻塞的管道阻塞的管道管道工管道工电影院售票窗口电影院售票窗口人人售票员售票员机场检票处机场检票处人人航空公司代理人航空公司代理人经纪人服务经纪人服务人人股票经纪人股票经纪人第4页/共131页运输服务系统运输服务系统系统类型系统类型顾客顾客服务台服务台公路收费站公路收费站汽车汽车收费员收费员卡车装货地卡车装货地卡车卡车装货工人装货工人港口卸货区港口卸货区轮船轮船卸货工人卸货工人等待起飞的飞机等待起飞的飞机飞机飞机跑道跑道航班服务航班服务人人飞机飞机出租车服务出租车服务人人出租车出租车电梯服务电梯服务人人电梯电梯消防部门消防部门火灾火灾消防车消防车停车场停车场汽车汽车

4、停车空间停车空间急救车服务急救车服务人人急救车急救车第5页/共131页 面对拥挤现象，如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾，这就是排队论所要研究解决的问题之一。第6页/共131页第一节第一节 基本概念基本概念第7页/共131页（一）排队系统的特征及组成（一）排队系统的特征及组成排队系统的共同特征:有要求得到某种服务的人或物。排队论里把要求服务的对象统称为“顾客”有提供服务的人或机构。把提供服务的人或机构称为“服务台”或“服务员”顾客的到达、服务的时间至少有一个是随机的，服从某种分布。第8页/共131页一般的排队系统，都可由

5、一般的排队系统，都可由图图12-112-1加以描述。加以描述。顾客源顾客源排队结构排队结构服服务务机机构构排队规则排队规则顾客到来顾客到来服务规则服务规则离去离去图12-1排队系统排队系统第9页/共131页排队系统都有输入过程、排队规则和服务台等3个组成部分：1、输入过程这是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流一般可以从3个方面来描述输入过程。排队系统的组成第10页/共131页(1)顾客总体数组成(又称顾客源)是有限的，也可以是无限的。例如，到售票处购票的顾客总数可以认为是无限的，而某个工厂因故障待修的机床则是有限的。(2)顾客到达方式。描述顾客是怎样来到系统

6、的，他们是单个到达，还是成批到达。病人到医院看病是顾客单个到达的例子。在库存问题中如将生产器材进货或产品入库看作是顾客，那么这种顾客则是成批到达的。第11页/共131页(3)顾客流的概率分布，或称顾客相继到达时间间隔的分布。这是求解排队系统有关运行指标问题时，首先需要确定的指标。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。第12页/共131页2、排队规则这是指服务台从队列中选取顾客进行服务的顺序。损失制混合制队长有限等待时间有限逗留时间有限排队规则等待制先到先服务后到先服务随机服务优先权服务第13页/共131页3服务台情况。服务台可以从3方面来描述：(1)

7、服务台数量及构成形式图12-2单队列-单服务台排队系统第14页/共131页图12-3单队列S个服务台并联的排队系统图12-4S个队列S个服务台的并联排队系统第15页/共131页图12-5单队多个服务台的串联排队系统图12-6多队多服务台混联、网络系统第16页/共131页(2)服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。(3)服务时间的分布。在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K级爱尔朗分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。第17页/共131页为了区别各种排队系统，根据输入过程、排队规则和服务机制的不

8、同，对排队模型进行分类。DGKendall在1953年提出了模型分类方法，1971年在排队论符号标准化会议上，将Kendall符号扩充为如下固定格式：X/Y/Z/A/B/C各符号的意义为：（二）排队模型的分类第18页/共131页X表示顾客相继到达间隔时间分布，常用下列符号：X/Y/Z/A/B/CM表示到达过程为泊松过程或负指数分布；D表示定长输入；Ek表示k阶爱尔朗分布；GI表示一般相互独立的时间间隔分布；G表示一般服务时间的分布。第19页/共131页Y表示服务时间分布，常用下列符号：X/Y/Z/A/B/CM表示服务过程为泊松过程或负指数分布；D表示定长分布；Ek表示k阶爱尔朗分布；G表示一般

9、相互独立的随机分布。第20页/共131页Z表示服务台(员)个数：“1”则表示单个服务台，“s”(s1)表示多个服务台。X/Y/Z/A/B/CA表示系统中顾客容量限额，或称等待空间容量：时为等待制系统，此时一般省略不写；若为有限整数时，为混合制系统。第21页/共131页B表示顾客源限额。分有限与无限两种，表示顾客源无限，此时一般也可省略不写。X/Y/Z/A/B/CC表示服务规则，常用下列符号：FCFS：表示先到先服务；LCFS：表示后到先服务；PR：表示优先权服务。第22页/共131页例如：某排队问题为MMSFCFS则表示顾客到达间隔时间为负指数分布(泊松流)；服务时间为负指数分布；有s(s1)

10、个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则。可简记为：M/M/s第23页/共131页某些情况下，排队问题仅用上述表达形式中的前3个、4个、5个符号。如不特别说明均理解为系统等待空间容量无限；顾客源无限，先到先服务，单个服务的等待制系统。第24页/共131页（三）排队系统的主要数量指标1.队长和排队长队长是指系统中的顾客数(排队等待的顾客数与正在接受服务的顾客数之和)。排队长是指系统中正在排队等待服务的顾客数。第25页/共131页2等待时间和逗留时间从顾客到达时刻起到他开始接受服务止这段时间称为等待时间，是随机变量。从顾客到达时刻起到他接受服务完成止这段时间称为逗留

11、时间，也是随机变量。第26页/共131页3忙期和闲期忙期是指从顾客到达空闲着的服务机构起，到服务机构再次成为空闲止的这段时间，即服务机构连续忙的时间。这是个随机变量，它关系到服务员的服务强度。与忙期相对的是闲期，即服务机构连续保持空闲的时间。在排队系统中，忙期和闲期总是交替出现的。第27页/共131页除了上述几个基本数量指标外，还会用到其他一些重要的指标：损失制或系统容量有限的情况下，由于顾客被拒绝，而使服务系统受到损失的顾客损失率及服务强度等，也都是十分重要的数量指标。第28页/共131页4.一些数量指标的常用记号(1)主要数量指标 N(t)：时刻t系统中的顾客数(又称为系统的状态)，即队长

12、；Nq(t)：时刻t系统中排队的顾客数，即排队长；T(t)：时刻t到达系统的顾客在系统中的逗留时间；Tq(t)：时刻t到达系统的顾客在系统中的等待时间。第29页/共131页上面数量指标一般都是和系统运行的时间有关的随机变量，求它们的瞬时分布一般很困难。注意到相当一部分排队系统在运行了一定时间后，都会趋于一个平衡状态(或称平稳状态)。在平衡状态下，这些量与系统所处的时刻无关，而且系统的初始状态的影响也会消失。因此，我们在本章中将主要讨论与系统所处时刻无关的性质，即统计平衡性质。第30页/共131页L或Ls平均队长稳态系统任一时刻的顾客数的期望值；Lq平均等待队长或队列长稳态系统任一时刻等待服务的

13、顾客数期望值；W或Ws 平均逗留时间 进入稳态系统的顾客逗留时间期望值；Wq平均等待时间 进入稳态系统的顾客等待时间期望值。第31页/共131页Pn 系统的状态Pn=PN=n：稳态系统任一时刻状态为n的概率。当n=0时，Pn即P0为稳态系统所有服务台全部空闲的概率。第32页/共131页(2)其他常用数量指标s系统中并联服务台的数目平均到达率（单位时间内到达的平均顾客数）1/平均到达间隔平均服务率（单位时间内可以服务完的平均顾客数）1/平均服务时间第33页/共131页对于损失制和混合制的排队系统，顾客在到达服务系统时，若系统容量已满，则自行消失。这就是说，到达的顾客不一定全部进入系统，为此引入：

14、e 有效平均到达率，即每单位时间实际进入系统的平均顾客数（期望值），不同于。对于等待制的排队系统，有：e 第34页/共131页第二节第二节 到达间隔的分布和服务时间的分布到达间隔的分布和服务时间的分布第35页/共131页一、Poisson流（Poisson过程）定义定义 满足以下三个条件的输入流称为满足以下三个条件的输入流称为PoissonPoisson流流1 1、无后效性无后效性：不相交的时间区间内到达的顾客数互：不相交的时间区间内到达的顾客数互相独立。相独立。2 2、平稳性平稳性：在时间区间在时间区间t,t+t,t+t)t)内到达内到达1 1个顾客个顾客的概率只与的概率只与 t t有关。即

15、有关。即 表示单位时间内有一个顾客到达的概率。表示单位时间内有一个顾客到达的概率。3 3、普通性普通性：设在设在t,t+t,t+t t）内到达多于一个顾客）内到达多于一个顾客的概率极小，即的概率极小，即第36页/共131页Poisson流与流与Poisson分布分布定定理理1 对对于于一一个个参参数数为为 的的Poisson流流，在在0，t内到达内到达n个顾客的概率为个顾客的概率为 即服从以即服从以 为参数的为参数的Poisson分布。分布。定理定理1说明说明 如果顾客的到达为如果顾客的到达为Poisson流的话，则流的话，则到达顾客数的分布恰好为到达顾客数的分布恰好为Poisson分布。分布

16、。第37页/共131页二、负指数分布 在实际的排队系统中服务时间的概率分布可以是在实际的排队系统中服务时间的概率分布可以是各种形式，但在排队论中，最容易进行数学处理、最各种形式，但在排队论中，最容易进行数学处理、最常用的一种重要分布是负指数分布。常用的一种重要分布是负指数分布。设随机变量设随机变量T服从以服从以 为参数的负指数分布，它为参数的负指数分布，它的分布函数为：的分布函数为：第38页/共131页负指数分布的性质：负指数分布的性质：性质性质1 1 由条件概率公式容易证明由条件概率公式容易证明 性质性质2 2 当单位时间内的顾客到达数服从以当单位时间内的顾客到达数服从以 为平均数为平均数的

17、泊松分布时，则顾客相继到达的间隔时间的泊松分布时，则顾客相继到达的间隔时间T T服从负服从负指数分布。指数分布。这性质称为这性质称为无记忆性无记忆性。若。若T T表示排队系统中顾客到达的表示排队系统中顾客到达的时间间隔，那么这个性质说明一个顾客到来所需要的时间间隔，那么这个性质说明一个顾客到来所需要的时间与过去一个顾客到来所需要的时间时间与过去一个顾客到来所需要的时间s s无关，所以说无关，所以说在这种情形下的顾客到达是纯随机的。在这种情形下的顾客到达是纯随机的。第39页/共131页由性质由性质2 2可知：可知：相继到达的间隔时间是独立且为相同相继到达的间隔时间是独立且为相同参数的负指数分布，

18、与输入过程为泊松流（参数为参数的负指数分布，与输入过程为泊松流（参数为 ）是等价的。）是等价的。根据负指数分布与泊松流的关系可以推导出，当根据负指数分布与泊松流的关系可以推导出，当服务机构对顾客的服务时间服从参数为服务机构对顾客的服务时间服从参数为 的负指数分的负指数分布，如果服务机构处于忙期，则该服务机构的输出，布，如果服务机构处于忙期，则该服务机构的输出，即服务完毕离开服务机构的顾客数将是服从泊松分布即服务完毕离开服务机构的顾客数将是服从泊松分布的泊松流。其中的泊松流。其中 为每个顾客的平均服务时间，也是为每个顾客的平均服务时间，也是顾客相继离开的间隔顾客相继离开的间隔。第40页/共131

19、页三、k阶爱尔朗分布定定理理 设设v1，v2，vk是是k个个互互相相独独立立的的随随机机变变量量，服从相同参数服从相同参数k 的负指数分布，那么的负指数分布，那么S=v1+v2+vk服从服从k阶阶Erlang分布，分布，S的密度函数为的密度函数为第41页/共131页K=1时爱尔朗分布化归为负指数分布，当K时，得到长度为1/的定长服务。m=1k=1k=2k=4k=8第42页/共131页第三节第三节 单服务台负指数分布排队系统的分析单服务台负指数分布排队系统的分析第43页/共131页标准排队模型标准排队模型 M/M/1:/FCFS顾客到达的时间间隔是负指数分布，即输入流是参数为的Poisson流服

20、从参数为的负指数分布一个服务台排队系统的容量无限顾客源的容量无限实行先到先服务的一个服务系统第44页/共131页一、系统稳态概率一、系统稳态概率p pn n的计算的计算 假设在假设在t+t+t t时刻系统中顾客数为时刻系统中顾客数为n n的概率的概率P Pn n(t+(t+t)t)Pn(t)Pn-1(t)Pn+1(t)Pn(t)Snt+t时刻时刻SnSnSn+1Sn-1t时刻时刻无到达，无离开无到达，无离开无到达，离开一个无到达，离开一个到达一个，无离开到达一个，无离开到达一个，离开一个到达一个，离开一个第45页/共131页由于这四种方式互不相容，故由概率的加法定理得：由于这四种方式互不相容，

21、故由概率的加法定理得：该差分方程组为该差分方程组为瞬态解瞬态解，需求稳态解。，需求稳态解。第46页/共131页M/M/1:/FCFS稳态时状态转移图012n-1nn+1稳态情况下，系统状态已不随时间发生变化：稳态情况下，系统状态已不随时间发生变化：第47页/共131页稳态情况下，系统状态已不随时间发生变化：稳态情况下，系统状态已不随时间发生变化：第48页/共131页得到得到 令称为服务强度，则得得第49页/共131页系统的过渡状态与稳定状态系统的过渡状态与稳定状态过渡过渡稳定稳定第50页/共131页二、二、系统的数量指标系统的数量指标1 1、服务台空闲的概率和忙的概率：、服务台空闲的概率和忙的

22、概率：空闲的概率：空闲的概率：P P0 0=1-=1-忙的概率：忙的概率：1-P0 0=2 2、系统中平均顾客数（队长期望值、系统中平均顾客数（队长期望值LsLs）：）：第51页/共131页3 3、系统中等待的平均顾客数（队长期望值、系统中等待的平均顾客数（队长期望值LqLq）：）：4 4、系统中顾客逗留时间的期望值：、系统中顾客逗留时间的期望值：第52页/共131页5 5、队列中顾客逗留时间的期望值：、队列中顾客逗留时间的期望值：现将以上公式归纳如下：现将以上公式归纳如下：它们相互关系如下：它们相互关系如下：第53页/共131页Little公式公式下列公式对任何服务系统均成立下列公式对任何服

23、务系统均成立第54页/共131页例例1 高高速速公公路路入入口口收收费费处处设设有有一一个个收收费费通通道道，汽汽车车到到达达服服从从Poisson分分布布，平平均均到到达达速速率率为为100辆辆小小时时，收收费费时时间间服服从从负负指指数数分分布布，平平均均收收费费时时间间为为15秒辆。求秒辆。求1、收费处空闲的概率；、收费处空闲的概率；2、收费处忙的概率；、收费处忙的概率；3、系统中分别有、系统中分别有1，2，3辆车的概率。辆车的概率。第55页/共131页解解：根根据据题题意意,=100辆辆/小小时时,1/=15（秒秒/辆辆）=1/240（小时（小时/辆）辆）,即即 240（辆（辆/小时）

24、。小时）。因此，因此，=/=100/240=5/12。系统空闲的概率为：系统空闲的概率为：P0=1-=1-(5/12)=7/12=0.583系统忙的概率为：系统忙的概率为：1-P0=1-(1-)=5/12=0.417第56页/共131页系统中有系统中有1辆车的概率为：辆车的概率为：P1=(1-)=0.4170.583=0.243系统中有系统中有2辆车的概率为：辆车的概率为：P2=2(1-)=0.417 20.583=0.101系统中有系统中有3辆车的概率为：辆车的概率为：P3=3(1-)=0.417 30.583=0.0421第57页/共131页例例2 高高速速公公路路入入口口收收费费处处设设

25、有有一一个个收收费费通通道道，汽汽车车到到达达服服从从Poisson分分布布，平平均均到到达达速速率率为为200辆辆小小时时，收收费费时时间间服服从从负负指指数数分分布布，平平均均收收费费时时间间为为15秒秒辆辆。求求Ls、Lq、Ws和和Wq。第58页/共131页解：根据题意，解：根据题意，=200辆辆/小时，小时，=240辆辆/小时，小时，=/=5/6。第59页/共131页有限队列模型有限队列模型 M/M/1:N/FCFS 如果系统的最大容量为如果系统的最大容量为N时，排队等待的顾客最多时，排队等待的顾客最多为为N-1，在某时刻一顾客到达时，如系统中已有，在某时刻一顾客到达时，如系统中已有N

26、个个顾客，那么这个顾客就被拒绝进入系统。顾客，那么这个顾客就被拒绝进入系统。第60页/共131页系统的状态概率平衡方程系统的状态概率平衡方程对于状态对于状态0：P1=P0对于状态对于状态k：Pk-1+Pk+1=(+)Pk 0k3)=0.570.75排队长1.7（人）2.25（人）（各子系统）平均队长3.95（人）9（人）（整个系统）平均逗留时间4.39（分钟）10（分钟）平均等待时间1.89（分钟）7.5（分钟）第88页/共131页M/M/c:N/FCFS模型模型 离开离开服务台服务台服务台顾客到达顾客离去顾客离去顾客离去队列设系统容量为设系统容量为N(Nc)。设顾客到达的速率为。设顾客到达的

27、速率为，每个服务台服务的速率为每个服务台服务的速率为，=/c。由于系统不会无。由于系统不会无限止地接纳顾客，对限止地接纳顾客，对不必加以限制。不必加以限制。第89页/共131页状态转移图与状态转移方程状态转移图与状态转移方程对状态对状态0:P0=P1对状态对状态 1:P0+2P2=(+)P1对状态对状态 c：Pc-1+cPc+1=(+c)Pc对状态对状态N PN-1=cPN 01cN第90页/共131页状态概率状态概率第91页/共131页运行指标运行指标 第92页/共131页例例6 某某旅旅馆馆有有8个个单单人人房房间间，旅旅客客到到达达服服从从Poisson流流，平平均均速速率率为为6人人天

28、天，旅旅客客平均逗留时间为平均逗留时间为2天，求：天，求：(1)每天客房平均占用数；每天客房平均占用数；(2)旅馆客满的概率。旅馆客满的概率。第93页/共131页解：解：旅馆旅馆8个房间全满的概率为个房间全满的概率为0.423 平均占用客房数为平均占用客房数为6.9间。间。第94页/共131页M/M/c:/m/FCFS模型模型 顾客到达修理速率发生故障等待修理的机器修理速率修理速率正在修理的机器到达速率(m-n)修理速率c运行的机器数 m-n第95页/共131页状态概率状态概率 其中其中 第96页/共131页运行指标运行指标有有效效到到达达速速率率e为为单单位位时时间间内内出出现现故故障的机器

29、数，有障的机器数，有e=(m-Ls)第97页/共131页例例7 7 车车间间有有5 5台台机机器器，每每台台机机器器的的故故障障率率为为1 1次次小小时时，有有2 2个个修修理理工工负负责责修修理理这这5 5台台机机器器，工作效率相同，为工作效率相同，为4 4台小时。求：台小时。求：(1)(1)等待修理的平均机器数；等待修理的平均机器数；(2)(2)正在修理的平均机器数；正在修理的平均机器数；(3)(3)每小时发生故障的平均机器数；每小时发生故障的平均机器数；(4)(4)平均等待修理的时间；平均等待修理的时间；(5)(5)平均停工时间。平均停工时间。第98页/共131页解解 可以计算得到（算式

30、略）：P1=0.394，P2=0.197，P3=0.074，P4=0.018，P5=0.002第99页/共131页由此，计算系统的各项运行指标如下：第100页/共131页第第5 5节节 一般服务时间一般服务时间M/G/1M/G/1模型模型第101页/共131页服务时间一般分布时，需要知道服务时间的均值和方差。当时，排队系统可以达到平稳状态。PK公式公式第102页/共131页1 负指数服务时间M/M/1模型只有负指数分布时排队长的一半。只有负指数分布时排队长的一半。2定长服务时间M/D/1模型第103页/共131页3k阶爱尔朗服务时间M/Ek/1模型若顾客需接受k个串行的服务台的服务后才离开，且

31、每个服务台服务时间服从负指数分布，平均服务时间相等。则总服务时间服从k阶爱尔朗分布。第104页/共131页Erlang分布的均值和方差总服务时间服从爱尔朗分布：每个服务台的平均服务时间是：每个服务台的平均服务时间是：第105页/共131页M/Ek/1系统的运行指标第106页/共131页例8有一汽车冲洗台，汽车按Poisson流到达，平均每小时到达18辆；冲洗时间T的平均值=0.05小时/辆，方差Var(T)=0.01(小时/辆)2，求该洗车台的运行指标，并对它进行评价。解：本例是M/G/1系统，且已知第107页/共131页 可见顾客等待时间太长，队列也太长。主可见顾客等待时间太长，队列也太长。

32、主要原因是服务时间的方差太大！要原因是服务时间的方差太大！第108页/共131页例例9 某单人裁缝店做西服，每套需经过某单人裁缝店做西服，每套需经过4个个不同的工序，不同的工序，4个工序完成后才开始做另一个工序完成后才开始做另一套。每一工序的时间服从负指数分布，期套。每一工序的时间服从负指数分布，期望值为望值为2小时。顾客到来服从泊松分布，平小时。顾客到来服从泊松分布，平均订货率为均订货率为5.5套套/周（设一周周（设一周6天，每天天，每天8小小时）。问一顾客为等到做好一套西服期望时）。问一顾客为等到做好一套西服期望时间有多长？时间有多长？解：解：=5.5套套/周周1/:平均每套所需时间平均每

33、套所需时间1/4:平均每工序所需时间，为平均每工序所需时间，为2小时小时1/8套套/小时小时6套套/周周第109页/共131页顾客为等到做好一套西服期望时间：第110页/共131页排队论练习题第111页/共131页练习练习1 1：某修理店只有一位修理工，来修理的顾客到达过程为Poisson流，平均每小时4人；修理时间服从负指数分布，平均需要6分钟。试求：修理店空闲的概率；店内恰有3位顾客的概率；店内至少有一位顾客的概率；在店内平均顾客数；每位在店内平均逗留时间；等待服务的平均顾客数；每位顾客平均等待服务时间；顾客在店内逗留时间超过10分钟的概率。第112页/共131页解：本例可看成一个解：本例

34、可看成一个M/M/1/M/M/1/排队问题，其中排队问题，其中 =4=4，=1/0.1=10(=1/0.1=10(人人/小时），小时），=/=2/51=2/510=ePT10=e-10(1/6-1/15)-10(1/6-1/15)=e=e-1-1=0.3677=0.3677PTt=ePTt=e-(-(-)t)tt=10t=10分钟分钟,=10=10人人/小时小时=10/60=1/6=10/60=1/6 =4=4人人/小时小时=4/60=1/15=4/60=1/15第115页/共131页 练习练习2 2：考虑一个铁路列车编组站。设待编列车到达时间间隔服从负指数分布，平考虑一个铁路列车编组站。设待

35、编列车到达时间间隔服从负指数分布，平均每小时到达均每小时到达2 2列；服务台是编组站，编组时间服从负指数分布，平均每列；服务台是编组站，编组时间服从负指数分布，平均每2020分钟分钟可编一组。已知编组站上共有可编一组。已知编组站上共有2 2股道，当均被占用时，不能接车，再来的列车只股道，当均被占用时，不能接车，再来的列车只能停在站外或前方站。求：能停在站外或前方站。求：1 1、在平衡状态下系统中列车的平均数；、在平衡状态下系统中列车的平均数；2 2、每一列车的平均逗留时间；、每一列车的平均逗留时间；3 3、等待编组的列车平均数；、等待编组的列车平均数；4 4、列车在系统中的平均等待编组时间列车

36、在系统中的平均等待编组时间；5 5、如果列车因站中、如果列车因站中2 2股道均被占用而停在站外或前方站时，每列车每小时费用为股道均被占用而停在站外或前方站时，每列车每小时费用为a a元，求每天由于列车在站外等待而造成的损失。元，求每天由于列车在站外等待而造成的损失。第116页/共131页解：解：本例可看成一个本例可看成一个M/M/1/M/M/1/排队问题，其中排队问题，其中=2=2，=3=3，=/=2/31=2/32=W1-P=WPN2=W1-P0 0-P-P1 1-P-P2 2 =W1-(=W1-(l-l-)-)-(l-l-)1 1-(l-l-)2 2 =1*=1*3 3=3 3=(2/3)

37、=(2/3)3 3=0.296=0.296（小时）（小时）故每天列车由于等待而支出的平均费用故每天列车由于等待而支出的平均费用E=24E=24 W W0 0a=24*2*0.296*a=14.2aa=24*2*0.296*a=14.2a元元第118页/共131页练习练习3 3：(病人候诊问题病人候诊问题)某单位医院的一个科室有一位医生值班，经长期观察，每某单位医院的一个科室有一位医生值班，经长期观察，每小平均有小平均有4 4个病人，医生每小时平均可诊个病人，医生每小时平均可诊5 5个病人，病人的到来服从泊松分布，医生的个病人，病人的到来服从泊松分布，医生的诊病时间服从负指数分布，试问：诊病时间

38、服从负指数分布，试问：1、该科室平均有病人数；平均排队候诊病人数；看一次病平均所需的时间；排队等候看病的平均时间 2 如果满足99%以上的病人有座，此科室至少应设多少座位?3 如果该单位每天24小时上班，病人看病1小时因耽误工作单位要损失30元，这样单位平均每天损失多少元?4 如果该科室提高看病速度，每小时平均可诊6个病人，单位每天可减少损失多少?可减少多少座位?第119页/共131页解：该模型为解：该模型为MM1MM1该科室平均有病人数为 该科室内排队候诊病人数为 看一次病平均所需的时间为 排队等候看病的平均时间为 为满足99%以上的病人有座，设科室应设m个座位，则m应满足 第120页/共1

39、31页 所以该科室至少应设20个座位 如果该单位24小时上班，则每天平均有病人244=96人，病人看病所花去的总时间为961=96小时，因看病平均每天损失3096=2880元，如果医生每小时可诊6个病人，则 LLWWsqsq=2430513()().()()人人小时小时第121页/共131页 这样单位每天的损失费为这样单位每天的损失费为960.530=1440960.530=1440元，因而单位每天平均可减元，因而单位每天平均可减少损失少损失2880-1440=14402880-1440=1440元，这时为保证元，这时为保证99%99%以以上的病人有座，应设座位数个比原来减少了上的病人有座，应

40、设座位数个比原来减少了9 9个。个。第122页/共131页练练习习4 4:某某汽汽车车加加油油站站有有两两台台加加油油泵泵为为汽汽车车加加油油，加加油油站站内内最最多多能能容容纳纳6 6辆辆汽汽车车。已已知知顾顾客客到到达达的的时时间间间间隔隔服服从从负负指指数数分分布布，平平均均每每小小时时到到达达1818辆辆汽汽车车。若若加加油油站站中中已已有有K K辆辆车车，当当K K 2 2时时，有有K K/6/6的的顾顾客客将将自自动动离离去去。加加油油时时间间服服从从负负指指数数分分布，平均每辆车需要布，平均每辆车需要5 5分钟。试求：分钟。试求：非标准的M/M/2/N模型第123页/共131页（

41、1）系统空闲的概率为多少？（2）求系统满的概率是多少？（3）求系统服务台不空的概率?（4）若服务一个顾客,加油站可以获得利润10元,问平均每小时可获得利润为多少元？（5）求每小时损失掉的顾客数？（6）加油站平均有多少辆车在等待加油？平均有多少个车位被占用？（7）进入加油站的顾客需要等多长的时间才能开始加油？进入加油站的顾 客需要多长时间才能离去？第124页/共131页（1 1）系统空闲的概率为多少？）系统空闲的概率为多少？P P0 0（2 2）求系统满的概率是多少？）求系统满的概率是多少？P P6 6（3 3）求系统服务台不空的概率）求系统服务台不空的概率 P P2 2+P+P3 3+P+P4

42、 4+P+P5 5+P+P6 6=1-P=1-P0 0-P-P1 1 （4 4）若服务一个顾客）若服务一个顾客,加油站可以获得利润加油站可以获得利润1010元元,问平均每小时可获得利润为多少元？问平均每小时可获得利润为多少元？1010e e（5 5）求每小时损失掉的顾客数？）求每小时损失掉的顾客数？损损=-=-e e （6 6）加油站平均有多少辆车在等待加油？）加油站平均有多少辆车在等待加油？L Lq q 平均有多少个车位被占用？平均有多少个车位被占用？L L（7 7）进入加油站的顾客需要等多长时间才能开始加）进入加油站的顾客需要等多长时间才能开始加油？油？W Wq q 进入加油站的顾客需要多

43、长时间才能离去？进入加油站的顾客需要多长时间才能离去？W W 第125页/共131页稳态概率关系：稳态概率关系：P P1 1=/PP0 0=1.5=1.5P P0 0=(3/2)=(3/2)P P0 0P P2 2=/(2/(2)P P1 1=0.75*1.5=0.75*1.5P P0 0=(9/8)=(9/8)P P0 0解：状态转移速度图 以小时为单位=18 =60/5=1222 2205124632(1-2/6)(1-3/6)(1-4/6)(1-5/6)第126页/共131页P P3 3=(4/6)=(4/6)/(2/(2)P P2 2=(1/2)(9/8)=(1/2)(9/8)P P0

44、 0=(9/16)=(9/16)P P P P4 4=(3/6)=(3/6)/(2/(2)P P3 3=(3/8)(9/16)=(3/8)(9/16)P P0 0=(27/128)=(27/128)P P0 0P P5 5=(2/6)=(2/6)/(2/(2)P P4 4=(1/4)(27/128)=(1/4)(27/128)P P0 0=(27/512)=(27/512)P P0 0P P6 6=(1/6)=(1/6)/(2/(2)P P5 5=(1/8)(27/512)=(1/8)(27/512)P P0 0=(27/4096)=(27/4096)P P0 0由由 P P0 0+P+P1

45、1+P P2 2+P P3 3+P P4 4+P P5 5+P P6 6=1=1解得：解得：P P0 0=0.22433=0.22433 P1 P2 P3 P4 P5 P60.33649 0.25237 0.12618 0.04732 0.01183 0.00148第127页/共131页运行指标：运行指标：(1)(1)P P0 0=0.22433=0.22433(2)(2)P P6 6=0.00148=0.00148(3)(3)P P忙忙=1-=1-P P0 0-P P1 1=0.43918=0.43918(4)(4)e e=0=0P P0 0+PP1 1+2+2(P P2 2+P P3 3+

46、P P4 4+P P5 5+P P6 6)=14.578 =14.578（辆（辆/h/h）1010e e=145.78(=145.78(元元/小时）小时）(5)(5)损损=-e e =18-14.5782 =18-14.5782 =3.4218 =3.4218（辆（辆/h/h）第128页/共131页(6)Lq=(3-2)P3+(4-2)P4+(5-2)P5+(6-2)P6 =0.26223 L=Lq+e/=0.26223+1.21485 =1.47708(7)Wq=Lq/e=0.018h=1.08分钟 W=Wq+1/=0.101h=6.08分钟第129页/共131页P342 12.2P342 12.2 12.11 12.11 12.12 12.12 12.17 12.17第130页/共131页感谢您的观看！第131页/共131页