数学建模排队论模型课件

排排 队队 论论 模模 型型 朱建青朱建青（苏州科技学院信息与计算科学系）（苏州科技学院信息与计算科学系）排队论模型排队论模型 一、排队论的基本概念一、排队论的基本概念 二、单通道等待制排队问题二、单通道等待制排队问题 （MM1排队系统）排队系统）三、多通道等待制排队问题三、多通道等待制排队问题 （MMc排队系统）排队系统）一、排队论的基本概念一、排队论的基本概念（一）排队过程（一）排队过程 1.1.排队系统排队系统 “排排队队”是是指指在在服服务务机机构构处处要要求求服服务务对对象象的的一一个个等等待待队队列列，而而“排排队队论论”则则是是研研究究各各种种排排队队现现象象的的理理论。论。在在排排队队论论中中，我我们们把把要要求求服服务务的的对对象象称称为为“顾顾客客”，而而将将从从事事服服务务的的机机构构或或人人称称为为“服服务务台台”。在在顾顾客客到到达达服服务务台台时时，可可能能立立即即得得到到服服务务，也可能要等待到可以利用服务台的时候为止。也可能要等待到可以利用服务台的时候为止。排队系统队列除了有形的还有无形的排队系统队列除了有形的还有无形的。排队系统中的排队系统中的“顾客顾客”与与“服务台服务台”这两个名这两个名词可以从不同的角度去理解。词可以从不同的角度去理解。排队系统排队系统顾客顾客服务台服务台上、下班的工人乘公共汽车上、下班的工人乘公共汽车工人工人公共汽车公共汽车病人到医院看病病人到医院看病病人病人医生医生高炮击退敌机高炮击退敌机敌机敌机高炮高炮机器发生故障需要维修机器发生故障需要维修机器机器修理工修理工 在上述顾客在上述顾客-服务台组成的排队系统中，顾客到服务台组成的排队系统中，顾客到来的时刻与服务台进行服务的时间一般来说是随不来的时刻与服务台进行服务的时间一般来说是随不同的时机与条件而变化的，往往预先无法确定。因同的时机与条件而变化的，往往预先无法确定。因此，系统的状态是随机的，故而排队论也称此，系统的状态是随机的，故而排队论也称随机服随机服务系统务系统。各各式式各各样样的的排排队队现现象象呈呈现现的的基基本本特特征征：排排队队系系统统由输入过程、排队规则及服务机构三部分组成。由输入过程、排队规则及服务机构三部分组成。(1)(1)输入过程输入过程 输入过程就是顾客按怎样的规律到达，它首先应输入过程就是顾客按怎样的规律到达，它首先应包括顾客总体数，是有限的还是无限的；其次应说明包括顾客总体数，是有限的还是无限的；其次应说明顾客到达的方式，是成批到达顾客到达的方式，是成批到达(每批数量是随机的还每批数量是随机的还是确定性的是确定性的)还是单个到达；最后应说明相继到达的还是单个到达；最后应说明相继到达的顾客顾客(或批或单个或批或单个)之间的时间间隔的分布是什么。之间的时间间隔的分布是什么。2.2.排队系统的组成和特征排队系统的组成和特征 排队规则是指到达的顾客以怎样的规则接受服务。排队规则是指到达的顾客以怎样的规则接受服务。1 1）损损失失制制：顾顾客客到到达达，服服务务台台不不空空立立即即离离去去，另求服务。另求服务。2 2）等等待待制制：顾顾客客到到达达，排排队队等等待待。对对等等待待制制服服务务可可分分为为：先先到到先先服服务务，后后到到先先服服务务，优优先先服服务务，随随机服务，成批服务等。机服务，成批服务等。3 3）混合制：）混合制：在现实生活中，很多服务系统介于在现实生活中，很多服务系统介于损失制和等待制之间，当顾客到达时，服务台不空就损失制和等待制之间，当顾客到达时，服务台不空就排队，若排队的位置已满就离去。排队，若排队的位置已满就离去。(2)(2)排队规则排队规则 服务机构主要指服务台的数目，多个服务服务机构主要指服务台的数目，多个服务台进行服务时，服务方式是并联还是串联；服台进行服务时，服务方式是并联还是串联；服务时间服从什么分布等。务时间服从什么分布等。(3)(3)服务机构服务机构 1.1.排队模型的分类排队模型的分类 D.G.KendallD.G.Kendall引引进进了了排排队队模模型型分分类类符符号号，现现已已广广泛采用，这里仅针对并列的服务台。泛采用，这里仅针对并列的服务台。记记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 MC C。（二）排队模型的分类及数量指标（二）排队模型的分类及数量指标 (1)(1)队长队长 队队长长是是指指系系统统中中的的顾顾客客数数(包包括括排排队队等等候候和和正正在在接接受受服服务务的的顾顾客客数数)；等等待待队队长长是是指指系系统统中中等等待待服服务务的的顾顾客客数数。无无论论是是队队长长还还是是等等待待队队长长，都都是是顾顾客客和和服服务务机机构构最最关关心心的的数数量量指指标标，特特别别是是对对系系统统设设计计者者来来说说，尤尤为为重重要要，因因为为它它涉涉及及到到系系统统等等待待空空间间的大小。的大小。2.2.排队模型的数量指标排队模型的数量指标 逗留时间是指一顾客从进入系统起一直到接受逗留时间是指一顾客从进入系统起一直到接受服务后离开系统为止所花费的时间；等待时间是指服务后离开系统为止所花费的时间；等待时间是指一顾客从进入系统起到接受服务时所花费的时间。一顾客从进入系统起到接受服务时所花费的时间。显然，一个顾客的逗留时间等于其等待时间与接受显然，一个顾客的逗留时间等于其等待时间与接受服务的时间之和。逗留时间与等待时间对顾客来说服务的时间之和。逗留时间与等待时间对顾客来说是最关心的，因为每个顾客都希望自己用于排队等是最关心的，因为每个顾客都希望自己用于排队等待的时间愈短愈好。待的时间愈短愈好。(2)(2)逗留时间逗留时间 忙期是指从顾客到达空闲服务机构起到服务机构忙期是指从顾客到达空闲服务机构起到服务机构再次为空闲为止的这段时间，即服务机构连续繁忙的再次为空闲为止的这段时间，即服务机构连续繁忙的时间长度。这是服务机构最关心的数量指标，因为它时间长度。这是服务机构最关心的数量指标，因为它直接关系到服务员的工作强度，与忙期相对应的是闲直接关系到服务员的工作强度，与忙期相对应的是闲期，即为服务机构连续保持空闲的时间长度。显然，期，即为服务机构连续保持空闲的时间长度。显然，在排队系统中，忙期与闲期是交错出现的。在排队系统中，忙期与闲期是交错出现的。(3)(3)忙期忙期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流与指数分布流与指数分布最简单流应最简单流应 具有以下特征称具有以下特征称(1)(1)流具有平衡性流具有平衡性 对任何对任何 和和 ,的分布只取决于的分布只取决于 而与而与 无关。无关。(2)(2)流具有无后效性流具有无后效性对互不交接的时间区间序列对互不交接的时间区间序列 ，是一组相互独立的随机变量。是一组相互独立的随机变量。(3)(3)流具有普通性流具有普通性即在即在 时间内，事件发生多于时间内，事件发生多于1 1次的概率为次的概率为 。定理定理1 1设设 是最简单流，则对任何是最简单流，则对任何 和和都有都有 我们把满足这一分布规律的随机过程我们把满足这一分布规律的随机过程称为称为PoissonPoisson过程，最简单流亦称过程，最简单流亦称PoissonPoisson流，特别取流，特别取 得得故参数故参数表示单位时间内事件发生次数的平均数表示单位时间内事件发生次数的平均数。2.2.PoissonPoisson流的发生时间间隔分布流的发生时间间隔分布 当当流流(过过程程)构构成成PoissonPoisson过过程程时时，就就称称为为PoissonPoisson流流。设设流流发发生生的的时时刻刻依依次次为为 ,，发生的时间间隔记为发生的时间间隔记为 ，其中其中 。定理定理2 2 事件流事件流 为为PoissonPoisson流的充要条件是流的充要条件是 的的流流发发生生时时间间间间隔隔 相相互互独独立立，且且服服从从相同的负指数分布，即相同的负指数分布，即3.3.负指数分布的负指数分布的MarkovMarkov特性特性定定理理3 3设设T T为为连连续续型型随随机机变变量量，且且T0T0，那那么么，T T服服从从负指数分布的充要条件是：对任何负指数分布的充要条件是：对任何 ，都有，都有上式可改写为：对任何上式可改写为：对任何 ，都有，都有 如如果果把把T T解解释释为为寿寿命命，上上式式表表明明：如如果果已已知知年年龄龄大大于于 岁岁，则则再再活活x x年年的的概概率率与与以以前前的的 (年年)无无关关，所以有时又风趣地称指数分布是所以有时又风趣地称指数分布是“永远年轻永远年轻”。上上面面两两式式表表明明连连续续型型随随机机变变量量T T的的MarkovMarkov特特性性当当且仅当非负随机变量服从负指数分布时才具有。且仅当非负随机变量服从负指数分布时才具有。例例1 1 设设某某一一服服务务系系统统的的输输入入流流是是PoissonPoisson流流，平平均均每每3 3分钟进入分钟进入5 5名顾客，试计算：名顾客，试计算：(1)12(1)12分钟内进入分钟内进入1515名顾客的概率；名顾客的概率；(2)(2)输入时间间隔大于输入时间间隔大于1 1分钟的概率。分钟的概率。解解(1)(1)由于由于 ，在在0 0，t t内进入内进入k k名顾客的概率名顾客的概率 于是于是1212分钟内进入分钟内进入1515名顾客的概率名顾客的概率(2)(2)由于输入时间间隔由于输入时间间隔服从参数为服从参数为的指数分布的指数分布则所求概率为则所求概率为 对对于于单单通通道道等等待待制制排排队队问问题题主主要要讨讨论论输输入入过过程程为为PoissonPoisson流流，服服务务时时间间服服从从负负指指数数分分布布，单单服服务台的情形，即务台的情形，即M MM M1 1排队系统。排队系统。（一）标准模型（一）标准模型 即即为为M MM M1 1排排队队系系统统。所所谓谓标标准准模模型型，就就是是顾顾客客的的输输入入流流是是参参数数为为的的PoissonPoisson流流，每每个个顾顾客客的的服服务务时时间间是是相相互互独独立立的的且且服服从从参参数数为为的的负负指指数数分分布布，单单个个服服务务台台且且系系统统的的容容量量无无限限(排排队队模型分类第四个表示系统中允许的最大顾客数模型分类第四个表示系统中允许的最大顾客数)。二、单通道等待制排队问题二、单通道等待制排队问题 （M MM M1 1排队系统）排队系统）1.1.系统的系统的MarkovMarkov特性特性 考考虑虑随随机机过过程程 ，其其中中 为为时时刻刻 时时排队系统中的顾客数。排队系统中的顾客数。对于任何对于任何 条件概率条件概率由由于于输输入入为为PoissonPoisson流流，服服务务时时间间服服从从负负指指数数分分布布，则则无无论论 在在 处处取取何何值值，上上式式条条件件概概率率仅仅依依赖于赖于 的值和区间的值和区间 的长度的长度 ，即即 直直观观地地说说，如如果果知知道道现现在在时时刻刻 时时系系统统的的顾顾客客数数状状况况，那那么么从从概概率率意意义义上上来来说说，将将来来时时刻刻 时时系系统统的的顾顾客客数数状状况况，与与过过去去时时刻刻 时时顾顾客客数的状况无关。这个特性就是随机过程数的状况无关。这个特性就是随机过程的的MarkovMarkov特性。特性。我我们们把把系系统统在在某某一一时时刻刻的的顾顾客客数数看看做做系系统统在在这这个个时时刻刻的的状状态态。根根据据系系统统状状态态 的的MarkovMarkov特特性性，容容易易研研究究在在时时间间区区间间 内内系系统统状状态态的的转转移移概概率率，为研究系统在任一时刻的状态分布提供工具为研究系统在任一时刻的状态分布提供工具。记时刻记时刻t t系统处于状态系统处于状态n n的概率的概率利利用用M MM M1 1对对输输入入与与服服务务时时间间分分布布的的假假设设，在在时时间间区间区间 内，新进入或离开顾客个数有以下结果：内，新进入或离开顾客个数有以下结果：内没有顾客进入内没有顾客进入 内新进入一名顾客内新进入一名顾客 内多于一名顾客进入内多于一名顾客进入 内没有顾客离开内没有顾客离开 内有一名顾客离开内有一名顾客离开 内多于一名顾客离开内多于一名顾客离开2.2.排队系统的稳态解排队系统的稳态解 当当 时有时有导出导出 满足的微分方程组满足的微分方程组故故 满足的微分方程组满足的微分方程组对对 对于系统的稳定状态情形，对于系统的稳定状态情形，与与t t无关，无关，故故 ，记记 ，从而有从而有对于上述差分方程，利用归纳法不难求得对于上述差分方程，利用归纳法不难求得 记记 为排队系统的来往强度，当为排队系统的来往强度，当 时，由时，由 可得可得 由于由于 构成概率分布，则构成概率分布，则 ，从而级数从而级数 必须收敛，故有必须收敛，故有 。M MM M1 1系统的数量指标系统的数量指标 (1)(1)稳定状态下系统中顾客数的数学期望的定义为稳定状态下系统中顾客数的数学期望的定义为被称为系统中顾客的平均数，简称被称为系统中顾客的平均数，简称平均队长平均队长。稳定状态下系统中等待服务顾客数的数学期望，稳定状态下系统中等待服务顾客数的数学期望，简称平均简称平均等待队长等待队长。(2)(2)顾客在系统中的顾客在系统中的平均逗留时间平均逗留时间则顾客在系统中的则顾客在系统中的平均等待时间平均等待时间 可以证明，顾客在系统中逗留时间服从参数为可以证明，顾客在系统中逗留时间服从参数为-的负指数分布。的负指数分布。与与 是是衡衡量量排排队队系系统统质质量量的的很很重重要要的的效效率度量，它们之间有着有趣的联系：率度量，它们之间有着有趣的联系：上式称为上式称为LittleLittle公式。公式。对对M MM M1 1排队系统，它有着明显的直观意排队系统，它有着明显的直观意义：从平均意义来说，义：从平均意义来说，表明系统中的顾客数，表明系统中的顾客数，等于一个顾客在系统时间内来到的新的顾客数；等于一个顾客在系统时间内来到的新的顾客数；表明系统中处于等待状态的顾客数，等于一表明系统中处于等待状态的顾客数，等于一个顾客的等待时间内来到的新顾客数。个顾客的等待时间内来到的新顾客数。LittleLittle公式公式(3)(3)稳定状态下稳定状态下忙期忙期的数学期望的数学期望由此可见，一个忙期中所服务顾客的平均数为由此可见，一个忙期中所服务顾客的平均数为忙忙 例例2 2（病病人人候候诊诊问问题题）某某单单位位医医院院的的一一个个科科室室有有一一位位医医生生值值班班，经经长长期期观观察察，每每小小时时平平均均有有4 4个个病病人人，医医生生每每小小时时平平均均可可诊诊断断5 5人人，病病人人的的到到来来服服从从PoissonPoisson流流，诊诊病病时时间间服服从从负负指指数数分分布布，试试分分析析该该科科室室的的工工作作状状况况，如如要要求求99%99%以以上上的的病病人人有有座座，该该科科室室至至少少设设多多少少座座位位?如如果果该该单单位位每每天天2424小小时时上上班班，病病人人因因看看病病1 1小小时时而而耽耽误误工工作作单单位位要要损损失失3030元元，这这样样单单位位平平均均损损失失多多少少元元?如如果果该该科科室室提提高高看看病病速速度度，每每小小时时平平均均可可诊诊6 6人人，单位每天可减少损失多少单位每天可减少损失多少?可减少多少座位可减少多少座位?解：解：由题意可知，由题意可知，则则该科室平均有病人数该科室平均有病人数 (人人)该科室平均等待的病人数该科室平均等待的病人数 （人人)看一次病平均所需的时间看一次病平均所需的时间 （小时（小时)看看一一次次病病平平均均所所需需的的等等待待时时间间 (小小时时)医生的忙期医生的忙期 (小时小时)一个忙期中平均看病人数一个忙期中平均看病人数 (人)忙忙 为为了了满满足足99%99%以以上上的的病病人人有有座座，设设科科室室应应设设m m个个座座位，即：位，即：P P医务室病人数医务室病人数m m0.990.99 故该设故该设2020个座位。个座位。该该单单位位2424小小时时上上班班，平平均均每每天天有有4244249696人人看看病病，看看病病所所占占的的总总时时间间为为1961969696小小时时，所所以以因因看看病平均每天损失病平均每天损失309630962 880(2 880(元元)。若医生诊病速度提高到每小时若医生诊病速度提高到每小时6 6人，即人，即6 6、2 23 3，类似于上面的计算，有以下结果：类似于上面的计算，有以下结果：（人），人），（人）人）(小时小时)，（小时小时)这这样样单单位位每每天天损损失失：300.596300.5961 1 440440（元元），比原来减少比原来减少1 4401 440元，此时只需座位：元，此时只需座位：即即1111个座位，比原来减少个座位，比原来减少9 9个座位个座位。（二）系统容量有限的模型（二）系统容量有限的模型 即即为为M MM M1 1N N排排队队系系统统。考考虑虑排排队队系系统统的的容容量量为为N N，即即若若系系统统已已有有N N个个顾顾客客，则则再再来来新新顾顾客客即即被被拒绝进入系统。对于拒绝进入系统。对于n nN N，与与M MM M1 1相类似，相类似，有有对于对于n nN N，即即 满足微分方程满足微分方程 在稳态情况下，在稳态情况下，则则 则则 由由 ，可得可得系统的各项指标系统的各项指标 由由于于有有容容量量的的限限制制，顾顾客客实实际际进进入入系系统统的的速速率率不不是是，而而是是 (有有效效到到达达率率)，因因而而LittleLittle公式成立：公式成立：三、多通道等待制排队问题三、多通道等待制排队问题 （M MM Mc c排队系统）排队系统）多多通通道道就就是是多多服服务务台台，这这里里主主要要讨讨论论M MM Mc c排排队队系系统统问问题题，即即输输入入、输输出出与与M MM M1 1相相同同，这这里里有有c c个个相相互互独独立立工工作作，且且服服务务速速率率相相同同的的服服务务台台，这时整个系统的服务能力为这时整个系统的服务能力为cc。当当 时，系统有稳定解时，系统有稳定解系统指标系统指标 因而因而LittleLittle公式成立公式成立：例例3 3 某某火火车车站站售售票票处处有有三三个个窗窗口口，顾顾客客的的到到达达服服从从PoissonPoisson分分布布，平平均均每每分分钟钟0.90.9人人到到达达，服服务务时时间间服服从从负负指指数数分分布布，每每个个窗窗口口每每分分钟钟可可售售票票0.40.4人人，现现假假设设排排成成一一队队，依依次次向向空空闲闲的的窗窗口口购购票票，试试分分析析该该排队系统；若排成三队，与前面的情形比较。排队系统；若排成三队，与前面的情形比较。解解 假假设设排排成成一一队队(如如图图)，由由题题意意可可知知：c c3 3，0.90.9，0.40.4，则则 ，即即整整个个售售票票处处空闲的概率为空闲的概率为0.074 30.074 3。图图7-27-2假设排成一队示意图假设排成一队示意图平均等待队长：平均等待队长：1.7(1.7(人人)；平均队长：平均队长：L L3.95(3.95(人人)；平均等待时间：平均等待时间：1.891.89（分钟分钟)；平均逗留时间：平均逗留时间：4.39(4.39(分钟分钟)。假假设设排排成成三三队队，即即3 3个个M MM M1 1排排队队系系统统。如如图图假假设排成三队示意图。设排成三队示意图。0.40.4，0.30.3则整个售票处空闲的概率则整个售票处空闲的概率整个系统的平均等待队长：整个系统的平均等待队长：3 3 6.75(6.75(人人)整个系统的平均队长：整个系统的平均队长：33L L9(9(人人)平均逗留时间：平均逗留时间：10(10(分钟分钟)平均等待时间：平均等待时间：7.5(7.5(分钟分钟)从顾客及服务效率来说排成一队优于排成三队。