数学建模排队论模型PPT学习教案

1、数学建模排队论模型数学建模排队论模型排队论模型排队论模型 一、排队论的基本概念一、排队论的基本概念 二、单通道等待制排队问题二、单通道等待制排队问题 （MM1排队系统）排队系统）三、多通道等待制排队问题三、多通道等待制排队问题 （MMc排队系统）排队系统） 第1页/共48页一、排队论的基本概念一、排队论的基本概念（一）排队过程（一）排队过程 1.1.排队系统排队系统 “排队排队”是指在服务机构处要求服务对象的一个是指在服务机构处要求服务对象的一个等待队列，而等待队列，而“排队论排队论”则是研究各种排队现象的则是研究各种排队现象的理论。理论。 到来 服服务务规规则则 服服 离离去去 顾顾客客源源

2、 排排队队机机构构 务务 机机 构构 排排队队系系统统 第2页/共48页 在排队论中，我们把要求服务的对象称为在排队论中，我们把要求服务的对象称为“顾客顾客”，而将从事服务的机构或人称为，而将从事服务的机构或人称为“服务服务台台”。 在顾客到达服务台时，可能立即得到服在顾客到达服务台时，可能立即得到服务，也可能要等待到可以利用服务台的时候为止。务，也可能要等待到可以利用服务台的时候为止。第3页/共48页 排队系统队列除了有形的还有无形的排队系统队列除了有形的还有无形的。 排队系统中的排队系统中的“顾客顾客”与与“服务台服务台”这两个名这两个名词可以从不同的角度去理解。词可以从不同的角度去理解。

3、排队系统排队系统顾客顾客服务台服务台上、下班的工人乘公共汽车上、下班的工人乘公共汽车工人工人公共汽车公共汽车病人到医院看病病人到医院看病病人病人医生医生高炮击退敌机高炮击退敌机敌机敌机高炮高炮机器发生故障需要维修机器发生故障需要维修机器机器修理工修理工第4页/共48页 在上述顾客在上述顾客- -服务台组成的排队系统中，顾客到服务台组成的排队系统中，顾客到来的时刻与服务台进行服务的时间一般来说是随不来的时刻与服务台进行服务的时间一般来说是随不同的时机与条件而变化的，往往预先无法确定。因同的时机与条件而变化的，往往预先无法确定。因此，系统的状态是随机的，故而排队论也称此，系统的状态是随机的，故而排

4、队论也称随机服随机服务系统务系统。第5页/共48页 各式各样的排队现象呈现的基本特征：排队系统各式各样的排队现象呈现的基本特征：排队系统由输入过程、排队规则及服务机构三部分组成。由输入过程、排队规则及服务机构三部分组成。(1)(1)输入过程输入过程 输入过程就是顾客按怎样的规律到达，它首先应输入过程就是顾客按怎样的规律到达，它首先应包括顾客总体数，是有限的还是无限的；其次应说明包括顾客总体数，是有限的还是无限的；其次应说明顾客到达的方式，是成批到达顾客到达的方式，是成批到达( (每批数量是随机的还每批数量是随机的还是确定性的是确定性的) )还是单个到达；最后应说明相继到达的还是单个到达；最后应

5、说明相继到达的顾客顾客( (或批或单个或批或单个) )之间的时间间隔的分布是什么。之间的时间间隔的分布是什么。 2.2.排队系统的组成和特征排队系统的组成和特征第6页/共48页 排队规则是指到达的顾客以怎样的规则接受服务。排队规则是指到达的顾客以怎样的规则接受服务。 1 1）损失制：）损失制：顾客到达，服务台不空立即离去，顾客到达，服务台不空立即离去，另求服务。另求服务。 2 2）等待制：）等待制：顾客到达，排队等待。对等待制服顾客到达，排队等待。对等待制服务可分为：先到先服务，后到先服务，优先服务，随务可分为：先到先服务，后到先服务，优先服务，随机服务，成批服务等。机服务，成批服务等。 3

6、3）混合制：）混合制：在现实生活中，很多服务系统介于在现实生活中，很多服务系统介于损失制和等待制之间，当顾客到达时，服务台不空就损失制和等待制之间，当顾客到达时，服务台不空就排队，若排队的位置已满就离去。排队，若排队的位置已满就离去。 (2)(2)排队规则排队规则第7页/共48页 服务机构主要指服务台的数目，多个服务服务机构主要指服务台的数目，多个服务台进行服务时，服务方式是并联还是串联；服台进行服务时，服务方式是并联还是串联；服务时间服从什么分布等。务时间服从什么分布等。 (3)(3)服务机构服务机构第8页/共48页 1.1.排队模型的分类排队模型的分类 D.G.KendallD.G.Ken

7、dall引进了排队模型分类符号，现已广引进了排队模型分类符号，现已广泛采用，这里仅针对并列的服务台。泛采用，这里仅针对并列的服务台。 记记X X：顾客到达的时间间隔分布；顾客到达的时间间隔分布；Y Y：服务时间的服务时间的分布；分布；Z Z：服务台数。则排队模型：服务台数。则排队模型：X XY YZ Z。 常用的记号：常用的记号：M M负指数分布；负指数分布；D D确定型；确定型；EkEkk k阶爱尔朗（阶爱尔朗（ErlangErlang）分布；分布；GIGI一般相互独立的随一般相互独立的随机分布，机分布，G G一般随机分布。这里主要讨论一般随机分布。这里主要讨论M MM M1 1，M MM

8、MC C。（二）排队模型的分类及数量指标（二）排队模型的分类及数量指标第9页/共48页 (1)(1)队长队长 队长是指系统中的顾客数队长是指系统中的顾客数( (包括排队等候和正包括排队等候和正在接受服务的顾客数在接受服务的顾客数) )；等待队长是指系统中等待；等待队长是指系统中等待服务的顾客数。无论是队长还是等待队长，都是顾服务的顾客数。无论是队长还是等待队长，都是顾客和服务机构最关心的数量指标，特别是对系统设客和服务机构最关心的数量指标，特别是对系统设计者来说，尤为重要，因为它涉及到系统等待空间计者来说，尤为重要，因为它涉及到系统等待空间的大小。的大小。2.2.排队模型的数量指标排队模型的数

9、量指标第10页/共48页 逗留时间是指一顾客从进入系统起一直到接受逗留时间是指一顾客从进入系统起一直到接受服务后离开系统为止所花费的时间；等待时间是指服务后离开系统为止所花费的时间；等待时间是指一顾客从进入系统起到接受服务时所花费的时间。一顾客从进入系统起到接受服务时所花费的时间。显然，一个顾客的逗留时间等于其等待时间与接受显然，一个顾客的逗留时间等于其等待时间与接受服务的时间之和。逗留时间与等待时间对顾客来说服务的时间之和。逗留时间与等待时间对顾客来说是最关心的，因为每个顾客都希望自己用于排队等是最关心的，因为每个顾客都希望自己用于排队等待的时间愈短愈好。待的时间愈短愈好。 (2)(2)逗留

10、时间逗留时间第11页/共48页 忙期是指从顾客到达空闲服务机构起到服务机构忙期是指从顾客到达空闲服务机构起到服务机构再次为空闲为止的这段时间，即服务机构连续繁忙再次为空闲为止的这段时间，即服务机构连续繁忙的时间长度。这是服务机构最关心的数量指标，因的时间长度。这是服务机构最关心的数量指标，因为它直接关系到服务员的工作强度，与忙期相对应为它直接关系到服务员的工作强度，与忙期相对应的是闲期，即为服务机构连续保持空闲的时间长度。的是闲期，即为服务机构连续保持空闲的时间长度。显然，在排队系统中，忙期与闲期是交错出现的。显然，在排队系统中，忙期与闲期是交错出现的。 (3)(3)忙期忙期第12页/共48页

11、1.1.最简单流与最简单流与PoissonPoisson过程过程 记随机过程记随机过程x x（t t）：）：t0t0为时间为时间0 0，t t内流内流( (事件事件) )发生的次数，例如对于随机到来某电话发生的次数，例如对于随机到来某电话交换台的呼叫，以交换台的呼叫，以x x（t t）表示该交换台在表示该交换台在0 0，t t这段时间内收到呼叫的次数；若是服务机构，可以这段时间内收到呼叫的次数；若是服务机构，可以用用x x（t t）表示该机构在表示该机构在0 0，t t时间内来到的顾客时间内来到的顾客数数。（三）（三）PoissonPoisson流与指数分布流与指数分布第13页/共48页最简单

12、流应最简单流应 具有以下特征称具有以下特征称0: )(ttx(1)(1)流具有平衡性流具有平衡性 对任何对任何 和和 , , 的分布只取决于的分布只取决于 而与而与 无关。无关。(2)(2)流具有无后效性流具有无后效性对互不交接的时间区间序列对互不交接的时间区间序列 ， 是一组相互独立的随机变量。是一组相互独立的随机变量。(3)(3)流具有普通性流具有普通性即在即在 时间内，事件发生多于时间内，事件发生多于1 1次的概率为次的概率为 。 0anttt210)1 ()()(niaxtaxinttt,21a)1 (,nibaii)()(iiaxbx01)()(Prlimtaxtaxtt)( to

13、第14页/共48页定理定理1 1设设 是最简单流，则对任何是最简单流，则对任何 和和都有都有 我们把满足这一分布规律的随机过程我们把满足这一分布规律的随机过程称为称为PoissonPoisson过程，最简单流亦称过程，最简单流亦称PoissonPoisson流，特别取流，特别取 得得故参数故参数表示单位时间内事件发生次数的平均数表示单位时间内事件发生次数的平均数。0: )(ttx0a0t), 2 , 1 , 0(!)()()(Prkekkkaxtaxtk0: )(ttx), 2 , 1 , 0(!)()(Prkekkktxtk0attxE)(第15页/共48页2.2.PoissonPoisso

14、n流的发生时间间隔分布流的发生时间间隔分布 当流当流( (过程过程) ) 构成构成PoissonPoisson过程时，就过程时，就称 为称 为 P o i s s o nP o i s s o n 流 。 设 流 发 生 的 时 刻 依 次流 。 设 流 发 生 的 时 刻 依 次为为 , ,，发生的时间间隔记为发生的时间间隔记为 ，其中其中 。定理定理2 2 事件流事件流 为为PoissonPoisson流的充要条件是流的充要条件是 的流发生时间间隔的流发生时间间隔 相互独立，且服相互独立，且服从相同的负指数分布，即从相同的负指数分布，即0: )(ttxnttt,21), 2 , 1(1nt

15、tnnn00t0: )(ttx0: )(ttx n0001Prttettn第16页/共48页3.3.负指数分布的负指数分布的MarkovMarkov特性特性定理定理3 3设设T T为连续型随机变量，且为连续型随机变量，且T0T0，那么，那么，T T服从服从负指数分布的充要条件是：对任何负指数分布的充要条件是：对任何 ，都有，都有上式可改写为：对任何上式可改写为：对任何 ，都有，都有 如果把如果把T T解释为寿命，上式表明：如果已知年龄解释为寿命，上式表明：如果已知年龄大于大于 岁，则再活岁，则再活x x年的概率与以前的年的概率与以前的 ( (年年) )无关，无关，所以有时又风趣地称指数分布是所

16、以有时又风趣地称指数分布是“永远年轻永远年轻”。 上面两式表明连续型随机变量上面两式表明连续型随机变量T T的的MarkovMarkov特性当特性当且仅当非负随机变量服从负指数分布时才具有。且仅当非负随机变量服从负指数分布时才具有。001tt0101PrPrttTtTtTxTtTxtTPrPr0000t0t0t第17页/共48页例例1 1 设某一服务系统的输入流是设某一服务系统的输入流是PoissonPoisson流，平均流，平均每每3 3分钟进入分钟进入5 5名顾客，试计算：名顾客，试计算：(1)12(1)12分钟内进入分钟内进入1515名顾客的概率；名顾客的概率；(2)(2)输入时间间隔大

17、于输入时间间隔大于1 1分钟的概率。分钟的概率。解解(1)(1)由于由于 ，在在0 0，t t内进入内进入k k名顾客的概名顾客的概率率 于是于是1212分钟内进入分钟内进入1515名顾客的概率名顾客的概率35), 2 , 1 , 0(!)()(Prkekkktxtk0516. 0)1235(!15115)12(Pr123515ex第18页/共48页(2)(2)由于输入时间间隔由于输入时间间隔服从参数为服从参数为的指数分布的指数分布则所求概率为则所求概率为0001Prttettn1888. 01Pr35en第19页/共48页 对于单通道等待制排队问题主要讨论输入过对于单通道等待制排队问题主要讨

18、论输入过程为程为PoissonPoisson流，服务时间服从负指数分布，单服流，服务时间服从负指数分布，单服务台的情形，即务台的情形，即M MM M1 1排队系统。排队系统。（一）标准模型（一）标准模型 即为即为M MM M1 1排队系统。所谓标准模型，排队系统。所谓标准模型，就是顾客的输入流是参数为就是顾客的输入流是参数为的的PoissonPoisson流，每个流，每个顾客的服务时间是相互独立的且服从参数为顾客的服务时间是相互独立的且服从参数为的的负指数分布，单个服务台且系统的容量无限负指数分布，单个服务台且系统的容量无限( (排队排队模型分类第四个表示系统中允许的最大顾客数模型分类第四个表

19、示系统中允许的最大顾客数) )。二、单通道等待制排队问题二、单通道等待制排队问题 （MMMM1 1排队系统）排队系统）第20页/共48页1.1.系统的系统的MarkovMarkov特性特性 考虑随机过程考虑随机过程 ，其中其中 为时刻为时刻 时时排队系统中的顾客数。排队系统中的顾客数。 对于任何对于任何 条件概率条件概率由于输入为由于输入为PoissonPoisson流，服务时间服从负指数分布，流，服务时间服从负指数分布，则无论则无论 在在 处取何值，上式条件概率仅依处取何值，上式条件概率仅依赖于赖于 的值和区间的值和区间 的长度的长度 ，即即0: )(ttx)(txtnttt21011221

20、1)(,)(,)()(Prnnnnitxitxitxitx)(txnttt,21)(1ntx),(1nntt1nntt11112211)()(Pr)(,)(,)()(Prnnnnnnnnitxitxitxitxitxitx第21页/共48页 直观地说，如果知道现在时刻直观地说，如果知道现在时刻 时系统的顾时系统的顾客数状况，那么从概率意义上来说，将来时刻客数状况，那么从概率意义上来说，将来时刻 时时系统的顾客数状况，与过去时刻系统的顾客数状况，与过去时刻 时顾时顾客数的状况无关。这个特性就是随机过程客数的状况无关。这个特性就是随机过程的的MarkovMarkov特性。特性。 我们把系统在某一时

21、刻的顾客数看做系统在这我们把系统在某一时刻的顾客数看做系统在这个时刻的状态。根据系统状态个时刻的状态。根据系统状态 的的MarkovMarkov特性，特性，容易研究在时间区间容易研究在时间区间 内系统状态的转移概内系统状态的转移概率，为研究系统在任一时刻的状态分布提供工具率，为研究系统在任一时刻的状态分布提供工具。1ntnt221,nttt0: )(ttx)(tx),(ttt第22页/共48页 记时刻记时刻t t系统处于状态系统处于状态n n的概率的概率利用利用M MM M1 1对输入与服务时间分布的假设，在时对输入与服务时间分布的假设，在时间区间间区间 内，新进入或离开顾客个数有以下结果：内

22、，新进入或离开顾客个数有以下结果： 内没有顾客进入内没有顾客进入 内新进入一名顾客内新进入一名顾客 内多于一名顾客进入内多于一名顾客进入 内没有顾客离开内没有顾客离开 内有一名顾客离开内有一名顾客离开 内多于一名顾客离开内多于一名顾客离开2.2.排队系统的稳态解排队系统的稳态解ntxtPn)(Pr)(),(ttt)(1),(Prtotetttt)(),(Prtottetttt)(),(Prtottt)(1),(Prtotetttt)(),(Prtottetttt)(),(Prtottt第23页/共48页 当当 时有时有导出导出 满足的微分方程组满足的微分方程组)(tpn)()1 ()()1)(

23、)(100totttpttpttp)()()()()(1000tottpttptpttp0t)()()(100tptptp第24页/共48页故故 满足的微分方程组满足的微分方程组)()()1)(1)()()(11tottptttpttpttpnnnn)()()()()(11tptptptpnnnn对对1n)()()(, 2 , 1)()()()()(10011tptptpntptptptpnnnn)(tpn第25页/共48页 对于系统的稳定状态情形，对于系统的稳定状态情形， 与与t t无关，无关，故故 ，记记 ，从而有从而有对于上述差分方程，利用归纳法不难求得对于上述差分方程，利用归纳法不难求

24、得)(tpn0)( tpn)(tppnn0, 2 , 10)(1011ppnpppnnn0)(ppnn第26页/共48页 记记 为排队系统的来往强度，当为排队系统的来往强度，当 时，由时，由 可得可得 由于由于 构成概率分布，则构成概率分布，则 ，从而级数从而级数 必须收敛，故有必须收敛，故有 。 np01nnp0)(nn1101nnp, 2 , 1 , 0)1 (npnn第27页/共48页MMMM1 1系统的数量指标系统的数量指标 (1)(1)稳定状态下系统中顾客数的数学期望的定义稳定状态下系统中顾客数的数学期望的定义为为被称为系统中顾客的平均数，简称被称为系统中顾客的平均数，简称平均队长平

25、均队长。 0nnnpL1)(1(1000nnnnnnnnpL1)1(2000nnnnnnqpnppnL 稳定状态下系统中等待服务顾客数的数学期望，稳定状态下系统中等待服务顾客数的数学期望，简称平均简称平均等待队长等待队长。第28页/共48页 (2)(2)顾客在系统中的顾客在系统中的平均逗留时间平均逗留时间则顾客在系统中的则顾客在系统中的平均等待时间平均等待时间 可以证明，顾客在系统中逗留时间服从参数为可以证明，顾客在系统中逗留时间服从参数为-的负指数分布。的负指数分布。1)(11q第29页/共48页 与与 是衡量排队系统质量的很重要的效是衡量排队系统质量的很重要的效率度量，它们之间有着有趣的联

26、系：率度量，它们之间有着有趣的联系：上式称为上式称为LittleLittle公式。公式。 对对M MM M1 1排队系统，它有着明显的直观排队系统，它有着明显的直观意义：从平均意义来说，意义：从平均意义来说， 表明系统中的顾客表明系统中的顾客数，等于一个顾客在系统时间内来到的新的顾客数；数，等于一个顾客在系统时间内来到的新的顾客数； 表明系统中处于等待状态的顾客数，等于表明系统中处于等待状态的顾客数，等于一个顾客的等待时间内来到的新顾客数。一个顾客的等待时间内来到的新顾客数。 LittleLittle公式公式qqLLLqqLqLL,q,第30页/共48页(3)(3)稳定状态下稳定状态下忙期忙期

27、的数学期望的数学期望由此可见，一个忙期中所服务顾客的平均数为由此可见，一个忙期中所服务顾客的平均数为1)(TE忙忙11)(TE第31页/共48页 例例2 2（病人候诊问题）某单位医院的一个科室有（病人候诊问题）某单位医院的一个科室有一位医生值班，经长期观察，每小时平均有一位医生值班，经长期观察，每小时平均有4 4个病人，个病人，医生每小时平均可诊断医生每小时平均可诊断5 5人，病人的到来服从人，病人的到来服从PoissonPoisson流，诊病时间服从负指数分布，试分析该科流，诊病时间服从负指数分布，试分析该科室的工作状况，如要求室的工作状况，如要求99%99%以上的病人有座，该科室以上的病人

28、有座，该科室至少设多少座位至少设多少座位? ?如果该单位每天如果该单位每天2424小时上班，病人小时上班，病人因看病因看病1 1小时而耽误工作单位要损失小时而耽误工作单位要损失3030元，这样单位元，这样单位平均损失多少元平均损失多少元? ?如果该科室提高看病速度，每小时如果该科室提高看病速度，每小时平均可诊平均可诊6 6人，单位每天可减少损失多少人，单位每天可减少损失多少? ?可减少多可减少多少座位少座位? ?第32页/共48页 解：解： 由题意可知，由题意可知， 则则该科室平均有病人数该科室平均有病人数 ( (人人) )该科室平均等待的病人数该科室平均等待的病人数 （人人) )看一次病平均

29、所需的时间看一次病平均所需的时间 （小时（小时) )看一次病平均所需的等待时间看一次病平均所需的等待时间 ( (小小时时) )医生的忙期医生的忙期 ( (小时小时) )一个忙期中平均看病人数一个忙期中平均看病人数 (人)8 . 054, 5, 4, 2 , 1 , 08 . 02 . 0)1 (npnnn2.3)1(2qL1L4)1(L8 .0qqL忙忙1)(1)(TE5)()(TE第33页/共48页 为了满足为了满足99%99%以上的病人有座，设科室应设以上的病人有座，设科室应设m m个座个座位，即：位，即：P P医务室病人数医务室病人数m m0.990.99 故该设故该设2020个座位。个

30、座位。 该单位该单位2424小时上班，平均每天有小时上班，平均每天有4 424249696人看人看病，看病所占的总时间为病，看病所占的总时间为1 196969696小时，所以因看小时，所以因看病平均每天损失病平均每天损失303096962 880(2 880(元元) )。mnmnmnnp01099. 01)1 (201)ln01. 0(lnm第34页/共48页 若医生诊病速度提高到每小时若医生诊病速度提高到每小时6 6人，即人，即6 6、 2 23 3，类似于上面的计算，有以下结果：类似于上面的计算，有以下结果： （人），人）， （人）人） ( (小时小时) )， （小时小时) )这样单位每天

31、损失：这样单位每天损失：30300.50.596961 4401 440（元），（元），比原来减少比原来减少1 4401 440元，此时只需座位：元，此时只需座位： 即即1111个座位，比原来减少个座位，比原来减少9 9个座位个座位。342qLL315 . 0q111)32ln01. 0(lnm第35页/共48页（二）系统容量有限的模型（二）系统容量有限的模型 即为即为M MM M1 1N N排队系统。考虑排队系统的容排队系统。考虑排队系统的容量为量为N N，即若系统已有即若系统已有N N个顾客，则再来新顾客即被个顾客，则再来新顾客即被拒绝进入系统。对于拒绝进入系统。对于n nN N，与与M

32、MM M1 1相类似，相类似， ，有有ntxtPn)(Pr)()()()(1, 2 , 1)()()()()(10011tptptpNntptptptpnnnn对于对于n nN N，)()1)()()(1tottpttpttpNNN)()()(1tptptpNNN第36页/共48页 即即 满足微分方程满足微分方程 在稳态情况下，在稳态情况下， ， ，则则)(tPn)()()()()()(1, 2 , 1)()()()()(110011tptptptptptpNntptptptpNNNnnnn0)( tpn)(tppnn001, 2 , 10)(11011NNnnnppppNnppp第37页/共

33、48页 则则 由由 ，可得可得0ppnnNnnp01Nnnp00111)1 (1111NnnNp11)1 (11110NNp第38页/共48页系统的各项指标系统的各项指标11) 1(112110NNnNnNNpnL111112) 1(110NNnNnqNNNNpnL第39页/共48页 由于有容量的限制，顾客实际进入系统的速率不由于有容量的限制，顾客实际进入系统的速率不是是，而是而是 ( (有效到达率有效到达率) )，因而，因而LittleLittle公式成立：公式成立：1)1 (1121)1 (NNNNNpL1)1 (121)1 (NNNqqNNpL)1 (,NeepqeqeLL第40页/共48页三、多通道等待制排队问题三、多通道等待制排队问题 （MMMMc c排队系统）排队系统） 多通道就是多服务台，这里主要讨论多通道就是多服务台，这里主要讨论M M