(-数学建模)排队论模型--课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,ppt课件,排 队 论 模 型,1,ppt课件,排队论模型,一、排队论的基本概念,二、单通道等待制排队问题,（,MM1,排队系统）,三、多通道等待制排队问题,（,MMc,排队系统）,2,ppt课件,一、排队论的基本概念,（一）排队过程,1.排队系统,“,排队,”,是指在服务机构处要求服务对象的一个等待队列，而,“,排队论,”,则是研究各种排队现象的理论。,3,ppt课件,在排队论中，我们把要求服务的对象称为,“,顾客,”,，而将从事服务的机构或人称为,“,服务台,”,。在顾客到达服务台时，可能立即得到服务，也可能要等待到可以利用服务台的时候为止。,4,ppt课件,排队系统队列除了有形的还有无形的,。,排队系统中的,“,顾客,”,与,“,服务台,”,这两个名词可以从不同的角度去理解。,排队系统,顾客,服务台,上、下班的工人乘公共汽车,工人,公共汽车,病人到医院看病,病人,医生,高炮击退敌机,敌机,高炮,机器发生故障需要维修,机器,修理工,5,ppt课件,在上述顾客-服务台组成的排队系统中，顾客到来的时刻与服务台进行服务的时间一般来说是随不同的时机与条件而变化的，往往预先无法确定。因此，系统的状态是随机的，故而排队论也称,随机服务系统,。,6,ppt课件,各式各样的排队现象呈现的基本特征：排队系统由输入过程、排队规则及服务机构三部分组成。,(1)输入过程,输入过程就是顾客按怎样的规律到达，它首先应包括顾客总体数，是有限的还是无限的；其次应说明顾客到达的方式，是成批到达(每批数量是随机的还是确定性的)还是单个到达；最后应说明相继到达的顾客(或批或单个)之间的时间间隔的分布是什么。,2.排队系统的组成和特征,7,ppt课件,排队规则是指到达的顾客以怎样的规则接受服务。,1）损失制：,顾客到达，服务台不空立即离去，另求服务。,2）等待制：,顾客到达，排队等待。对等待制服务可分为：先到先服务，后到先服务，优先服务，随机服务，成批服务等。,3）混合制：,在现实生活中，很多服务系统介于损失制和等待制之间，当顾客到达时，服务台不空就排队，若排队的位置已满就离去。,(2)排队规则,8,ppt课件,服务机构主要指服务台的数目，多个服务台进行服务时，服务方式是并联还是串联；服务时间服从什么分布等。,(3)服务机构,9,ppt课件,1.排队模型的分类,D.G.Kendall,引进了排队模型分类符号，现已广泛采用，这里仅针对并列的服务台。,记,X：,顾客到达的时间间隔分布；,Y：,服务时间的分布；,Z：,服务台数。则排队模型：,XYZ。,常用的记号：,M,负指数分布；,D,确定型；,Ek,k,阶爱尔朗（,Erlang,）,分布；,GI,一般相互独立的随机分布，,G,一般随机分布。这里主要讨论,MM1，MMC。,（二）排队模型的分类及数量指标,10,ppt课件,(1)队长,队长是指系统中的顾客数(包括排队等候和正在接受服务的顾客数)；等待队长是指系统中等待服务的顾客数。无论是队长还是等待队长，都是顾客和服务机构最关心的数量指标，特别是对系统设计者来说，尤为重要，因为它涉及到系统等待空间的大小。,2.排队模型的数量指标,11,ppt课件,逗留时间是指一顾客从进入系统起一直到接受服务后离开系统为止所花费的时间；等待时间是指一顾客从进入系统起到接受服务时所花费的时间。显然，一个顾客的逗留时间等于其等待时间与接受服务的时间之和。逗留时间与等待时间对顾客来说是最关心的，因为每个顾客都希望自己用于排队等待的时间愈短愈好。,(2)逗留时间,12,ppt课件,忙期是指从顾客到达空闲服务机构起到服务机构再次为空闲为止的这段时间，即服务机构连续繁忙的时间长度。这是服务机构最关心的数量指标，因为它直接关系到服务员的工作强度，与忙期相对应的是闲期，即为服务机构连续保持空闲的时间长度。显然，在排队系统中，忙期与闲期是交错出现的。,(3)忙期,13,ppt课件,1.最简单流与,Poisson,过程,记随机过程,x（t）：t0,为时间0，,t,内流(事件)发生的次数，例如对于随机到来某电话交换台的呼叫，以,x（t）,表示该交换台在0，,t,这段时间内收到呼叫的次数；若是服务机构，可以用,x（t）,表示该机构在0，,t,时间内来到的顾客数,。,（三）,Poisson,流与指数分布,14,ppt课件,最简单流应 具有以下特征称,(1)流具有平衡性,对任何 和 ,的分布只取决于 而与 无关。,(2)流具有无后效性,对互不交接的时间区间序列,，,是一组相互独立的随机变量。,(3)流具有普通性,即在 时间内，事件发生多于1次的概率为,。,15,ppt课件,定理1,设 是最简单流，则对任何 和,都有,我们把满足这一分布规律的随机过程,称为,Poisson,过程，最简单流亦称,Poisson,流，特别取,得,故参数,表示单位时间内事件发生次数的平均数,。,16,ppt课件,2.,Poisson,流的发生时间间隔分布,当流(过程)构成,Poisson,过程时，就称为,Poisson,流。设流发生的时刻依次为 ,，,发生的时间间隔记为,，,其中,。,定理2,事件流 为,Poisson,流的充要条件是,的流发生时间间隔 相互独立，且服从相同的负指数分布，即,17,ppt课件,3.负指数分布的,Markov,特性,定理3,设,T,为连续型随机变量，且,T0，,那么，,T,服从负指数分布的充要条件是：对任何 ，都有,上式可改写为：对任何 ，都有,如果把,T,解释为寿命，上式表明：如果已知年龄大于 岁，则再活,x,年的概率与以前的,(,年)无关，所以有时又风趣地称指数分布是,“,永远年轻,”,。,上面两式表明连续型随机变量,T,的,Markov,特性当且仅当非负随机变量服从负指数分布时才具有。,18,ppt课件,例1,设某一服务系统的输入流是,Poisson,流，平均每3分钟进入5名顾客，试计算：,(1)12分钟内进入15名顾客的概率；,(2)输入时间间隔大于1分钟的概率。,解,(1)由于,，,在0，,t,内进入,k,名顾客的概率,于是12分钟内进入15名顾客的概率,19,ppt课件,(2),由于输入时间间隔,服从参数为,的指数分布,则所求概率为,20,ppt课件,对于单通道等待制排队问题主要讨论输入过程为,Poisson,流，服务时间服从负指数分布，单服务台的情形，即,MM1,排队系统。,（一）标准模型,即为,MM1,排队系统。所谓标准模型，就是顾客的输入流是参数为,的,Poisson,流，每个顾客的服务时间是相互独立的且服从参数为,的负指数分布，单个服务台且系统的容量无限(排队模型分类第四个表示系统中允许的最大顾客数)。,二、单通道等待制排队问题,（,MM1,排队系统）,21,ppt课件,1.系统的,Markov,特性,考虑随机过程,，,其中 为时刻 时排队系统中的顾客数。,对于任何 条件概率,由于输入为,Poisson,流，服务时间服从负指数分布，则无论 在 处取何值，上式条件概率仅依赖于 的值和区间 的长度,，,即,22,ppt课件,直观地说，如果知道现在时刻 时系统的顾客数状况，那么从概率意义上来说，将来时刻 时系统的顾客数状况，与过去时刻 时顾客数的状况无关。这个特性就是随机过程,的,Markov,特性。,我们把系统在某一时刻的顾客数看做系统在这个时刻的状态。根据系统状态 的,Markov,特性，容易研究在时间区间 内系统状态的转移概率，为研究系统在任一时刻的状态分布提供工具,。,23,ppt课件,记时刻,t,系统处于状态,n,的概率,利用,MM1,对输入与服务时间分布的假设，在时间区间 内，新进入或离开顾客个数有以下结果：,内没有顾客进入,内新进入一名顾客,内多于一名顾客进入,内没有顾客离开,内有一名顾客离开,内多于一名顾客离开,2.排队系统的稳态解,24,ppt课件,当 时有,导出 满足的微分方程组,25,ppt课件,故 满足的微分方程组,对,26,ppt课件,对于系统的稳定状态情形，与,t,无关，,故,，,记,，,从而有,对于上述差分方程，利用归纳法不难求得,27,ppt课件,记 为排队系统的来往强度，当,时，由 可得,由于 构成概率分布，则,，,从而级数 必须收敛，故有,。,28,ppt课件,MM1,系统的数量指标,(1)稳定状态下系统中顾客数的数学期望的定义为,被称为系统中顾客的平均数，简称,平均队长,。,稳定状态下系统中等待服务顾客数的数学期望，简称平均,等待队长,。,29,ppt课件,(2)顾客在系统中的,平均逗留时间,则顾客在系统中的,平均等待时间,可以证明，顾客在系统中逗留时间服从参数为,-,的负指数分布。,30,ppt课件,与 是衡量排队系统质量的很重要的效率度量，它们之间有着有趣的联系：,上式称为,Little,公式。,对,MM1,排队系统，它有着明显的直观意义：从平均意义来说，表明系统中的顾客数，等于一个顾客在系统时间内来到的新的顾客数；,表明系统中处于等待状态的顾客数，等于一个顾客的等待时间内来到的新顾客数。,Little,公式,31,ppt课件,(3)稳定状态下,忙期,的数学期望,由此可见，一个忙期中所服务顾客的平均数为,忙,忙,32,ppt课件,例2,（病人候诊问题）某单位医院的一个科室有一位医生值班，经长期观察，每小时平均有4个病人，医生每小时平均可诊断5人，病人的到来服从,Poisson,流，诊病时间服从负指数分布，试分析该科室的工作状况，如要求99%以上的病人有座，该科室至少设多少座位?如果该单位每天24小时上班，病人因看病1小时而耽误工作单位要损失30元，这样单位平均损失多少元?如果该科室提高看病速度，每小时平均可诊6人，单位每天可减少损失多少?可减少多少座位?,33,ppt课件,解：,由题意可知，则,该科室平均有病人数,(,人),该科室平均等待的病人数,（,人),看一次病平均所需的时间 （小时),看一次病平均所需的等待时间,(,小时),医生的忙期,(,小时),一个忙期中平均看病人数,(人),忙,忙,34,ppt课件,为了满足99%以上的病人有座，设科室应设,m,个座位，即：,P,医务室病人数,m0.99,故该设20个座位。,该单位24小时上班，平均每天有4,2496人看病，看病所占的总时间为1,9696小时，所以因看病平均每天损失30,962 880(元)。,35,ppt课件,若医生诊病速度提高到每小时6人，即,6、,23，,类似于上面的计算，有以下结果：,（,人），,（,人）,(,小时)，,（,小时),这样单位每天损失：30,0.5,961 440（元），比原来减少1 440元，此时只需座位：,即11个座位，比原来减少9个座位,。,36,ppt课件,（二）系统容量有限的模型,即为,MM1N,排队系统。考虑排队系统的容量为,N，,即若系统已有,N,个顾客，则再来新顾客即被拒绝进入系统。对于,nN，,与,MM1,相类似，,，,有,对于,nN,，,37,ppt课件,即 满足微分方程,在稳态情况下，,，,则,38,ppt课件,则,由 ，,可得,39,ppt课件,系统的各项指标,40,ppt课件,由于有容量的限制，顾客实际进入系统的速率不是,，,而是,(,有效到达率)，因而,Little,公式成立：,41,ppt课件,三、多通道等待制排队问题,（MMc,排队系统）,多通道就是多服务台，这里主要讨论,MMc,排队系统问题，即输入、输出与,MM1,相同，这里有,c,个相互独立工作，且服务速率相同的服务台，这时整个系统的服务能力为,c。,当 时，系统有稳定解,42,ppt课件,系统指标,因而,Little,公式成立,：,43,ppt课件,例3,某火车站售票处有三个窗口，顾客的到达服从,Poisson,分布，平均每分钟0.9人到达，服务时间服从负指数分布，每个窗口每分钟可售票0.4人，现假设排成一队，依次向空闲的窗口购票，试分析该排队系统；若排成三队，与前面的情形比较。,4