数学建模排队论模型.pptx

排队论模型排队论模型 一、排队论的基本概念一、排队论的基本概念 二、单通道等待制排队问题二、单通道等待制排队问题 （MM1排队系统）排队系统）三、多通道等待制排队问题三、多通道等待制排队问题 （MMc排队系统）排队系统）第1页/共35页一、排队论的基本概念一、排队论的基本概念（一）排队过程（一）排队过程 1.1.排队系统排队系统 “排排队队”是是指指在在服服务务机机构构处处要要求求服服务务对对象象的的一一个个等等待待队队列列，而而“排排队队论论”则则是是研研究究各各种种排排队队现现象象的的理理论。论。第2页/共35页 在在排排队队论论中中，我我们们把把要要求求服服务务的的对对象象称称为为“顾顾客客”，而而将将从从事事服服务务的的机机构构或或人人称称为为“服服务务台台”。在在顾顾客客到到达达服服务务台台时时，可可能能立立即即得得到到服服务务，也可能要等待到可以利用服务台的时候为止。也可能要等待到可以利用服务台的时候为止。第3页/共35页 排队系统队列除了有形的还有无形的排队系统队列除了有形的还有无形的。排队系统中的排队系统中的“顾客顾客”与与“服务台服务台”这两个名这两个名词可以从不同的角度去理解。词可以从不同的角度去理解。排队系统排队系统顾客顾客服务台服务台上、下班的工人乘公共汽车上、下班的工人乘公共汽车工人工人公共汽车公共汽车病人到医院看病病人到医院看病病人病人医生医生高炮击退敌机高炮击退敌机敌机敌机高炮高炮机器发生故障需要维修机器发生故障需要维修机器机器修理工修理工第4页/共35页 在上述顾客在上述顾客-服务台组成的排队系统中，顾客到服务台组成的排队系统中，顾客到来的时刻与服务台进行服务的时间一般来说是随不来的时刻与服务台进行服务的时间一般来说是随不同的时机与条件而变化的，往往预先无法确定。因同的时机与条件而变化的，往往预先无法确定。因此，系统的状态是随机的，故而排队论也称此，系统的状态是随机的，故而排队论也称随机服随机服务系统务系统。第5页/共35页 各各式式各各样样的的排排队队现现象象呈呈现现的的基基本本特特征征：排排队队系系统统由输入过程、排队规则及服务机构三部分组成。由输入过程、排队规则及服务机构三部分组成。(1)(1)输入过程输入过程 输入过程就是顾客按怎样的规律到达输入过程就是顾客按怎样的规律到达包括顾客总体数，是有限的还是无限的；包括顾客总体数，是有限的还是无限的；顾客到达的方式，是成批到达顾客到达的方式，是成批到达(每批数量是随机的每批数量是随机的还是确定性的还是确定性的)还是单个到达；还是单个到达；相继到达的顾客相继到达的顾客(或批或单个或批或单个)之间的时间间隔的分之间的时间间隔的分布是什么。布是什么。2.2.排队系统的组成和特征排队系统的组成和特征第6页/共35页 排队规则是指到达的顾客以怎样的规则接受服务。排队规则是指到达的顾客以怎样的规则接受服务。1 1）损损失失制制：顾顾客客到到达达，服服务务台台不不空空立立即即离离去去，另求服务。另求服务。2 2）等等待待制制：顾顾客客到到达达，排排队队等等待待。对对等等待待制制服服务务可可分分为为：先先到到先先服服务务，后后到到先先服服务务，优优先先服服务务，随随机服务，成批服务等。机服务，成批服务等。3 3）混合制：）混合制：在现实生活中，很多服务系统介于在现实生活中，很多服务系统介于损失制和等待制之间，当顾客到达时，服务台不空就损失制和等待制之间，当顾客到达时，服务台不空就排队，若排队的位置已满就离去。排队，若排队的位置已满就离去。(2)(2)排队规则排队规则第7页/共35页服务机构主要指服务台的数目，服务机构主要指服务台的数目，多个服务台进行服务时，服务方式是并联还多个服务台进行服务时，服务方式是并联还是串联；是串联；服务时间服从什么分布等。服务时间服从什么分布等。(3)(3)服务机构服务机构第8页/共35页 1.1.排队模型的分类排队模型的分类这里仅针对并列的服务台。这里仅针对并列的服务台。记记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。（二）排队模型的分类及数量指标（二）排队模型的分类及数量指标第9页/共35页 (1)(1)队长队长队长是指系统中的顾客数队长是指系统中的顾客数(包括排队等候和正在包括排队等候和正在接受服务的顾客数接受服务的顾客数)；等待队长是指系统中等待服务的顾客数。等待队长是指系统中等待服务的顾客数。2.2.排队模型的数量指标排队模型的数量指标第10页/共35页逗留时间是指一顾客从进入系统起一直到接受服逗留时间是指一顾客从进入系统起一直到接受服务后离开系统为止所花费的时间；务后离开系统为止所花费的时间；等待时间是指一顾客从进入系统起到接受服务时等待时间是指一顾客从进入系统起到接受服务时所花费的时间。所花费的时间。(2)(2)逗留时间逗留时间第11页/共35页 忙期是指从顾客到达空闲服务机构起到服务机构忙期是指从顾客到达空闲服务机构起到服务机构再次为空闲为止的这段时间，即服务机构连续繁忙的再次为空闲为止的这段时间，即服务机构连续繁忙的时间长度。时间长度。这是服务机构最关心的数量指标，因为它直接关系到这是服务机构最关心的数量指标，因为它直接关系到服务员的工作强度，与忙期相对应的是闲期，即为服服务员的工作强度，与忙期相对应的是闲期，即为服务机构连续保持空闲的时间长度。显然，在排队系统务机构连续保持空闲的时间长度。显然，在排队系统中，忙期与闲期是交错出现的。中，忙期与闲期是交错出现的。(3)(3)忙期忙期第12页/共35页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页/共35页最简单流应最简单流应 具有以下特征称具有以下特征称(1)(1)流具有平衡性流具有平衡性 对任何对任何 和和 ,的分布只取决于的分布只取决于 而与而与 无关。无关。(2)(2)流具有无后效性流具有无后效性对互不交接的时间区间序列对互不交接的时间区间序列 ，是一组相互独立的随机变量。是一组相互独立的随机变量。(3)(3)流具有普通性流具有普通性即在即在 时间内，事件发生多于时间内，事件发生多于1 1次的概率为次的概率为 。第14页/共35页定理定理1 1设设 是最简单流，则对任何是最简单流，则对任何 和和都有都有 我们把满足这一分布规律的随机过程我们把满足这一分布规律的随机过程称为称为PoissonPoisson过程，最简单流亦称过程，最简单流亦称PoissonPoisson流，特别取流，特别取 得得故参数故参数表示单位时间内事件发生次数的平均数表示单位时间内事件发生次数的平均数。第15页/共35页2.2.PoissonPoisson流的发生时间间隔分布流的发生时间间隔分布 当当流流(过过程程)构构成成PoissonPoisson过过程程时时，就就称称为为PoissonPoisson流流。设设流流发发生生的的时时刻刻依依次次为为 ,，发生的时间间隔记为发生的时间间隔记为 ，其中其中 。定理定理2 2 事件流事件流 为为PoissonPoisson流的充要条件是流的充要条件是 的的流流发发生生时时间间间间隔隔 相相互互独独立立，且且服服从从相同的负指数分布，即相同的负指数分布，即第16页/共35页 对对于于单单通通道道等等待待制制排排队队问问题题主主要要讨讨论论输输入入过过程程为为PoissonPoisson流流，服服务务时时间间服服从从负负指指数数分分布布，单单服服务台的情形，即务台的情形，即M MM M1 1排队系统。排队系统。（一）标准模型（一）标准模型 即即为为M MM M1 1排排队队系系统统。所所谓谓标标准准模模型型，就就是是顾顾客客的的输输入入流流是是参参数数为为的的PoissonPoisson流流，每每个个顾顾客客的的服服务务时时间间是是相相互互独独立立的的且且服服从从参参数数为为的的负负指指数数分分布布，单单个个服服务务台台且且系系统统的的容容量量无无限限(排排队队模型分类第四个表示系统中允许的最大顾客数模型分类第四个表示系统中允许的最大顾客数)。二、单通道等待制排队问题二、单通道等待制排队问题 （MMMM1 1排队系统）排队系统）第17页/共35页1.1.系统的系统的MarkovMarkov特性特性 考考虑虑随随机机过过程程 ，其其中中 为为时时刻刻 时时排队系统中的顾客数。排队系统中的顾客数。对于任何对于任何 条件概率条件概率由由于于输输入入为为PoissonPoisson流流，服服务务时时间间服服从从负负指指数数分分布布，则则无无论论 在在 处处取取何何值值，上上式式条条件件概概率率仅仅依依赖于赖于 的值和区间的值和区间 的长度的长度 ，即即第18页/共35页 记时刻记时刻t t系统处于状态系统处于状态n n的概率的概率利利用用M MM M1 1对对输输入入与与服服务务时时间间分分布布的的假假设设，在在时时间间区间区间 内，新进入或离开顾客个数有以下结果：内，新进入或离开顾客个数有以下结果：内没有顾客进入内没有顾客进入 内新进入一名顾客内新进入一名顾客 内多于一名顾客进入内多于一名顾客进入 内没有顾客离开内没有顾客离开 内有一名顾客离开内有一名顾客离开 内多于一名顾客离开内多于一名顾客离开2.2.排队系统的稳态解排队系统的稳态解第19页/共35页 当当 时有时有导出导出 满足的微分方程组满足的微分方程组第20页/共35页故故 满足的微分方程组满足的微分方程组对对第21页/共35页 对于系统的稳定状态情形，对于系统的稳定状态情形，与与t t无关，无关，故故 ，记记 ，从而有从而有对于上述差分方程，利用归纳法不难求得对于上述差分方程，利用归纳法不难求得第22页/共35页 记记 为排队系统的来往强度，当为排队系统的来往强度，当 时，由时，由 可得可得 由于由于 构成概率分布，则构成概率分布，则 ，从而级数从而级数 必须收敛，故有必须收敛，故有 。第23页/共35页MMMM1 1系统的数量指标系统的数量指标 (1)(1)稳定状态下系统中顾客数的数学期望的定义为稳定状态下系统中顾客数的数学期望的定义为被称为系统中顾客的平均数，简称被称为系统中顾客的平均数，简称平均队长平均队长。稳定状态下系统中等待服务顾客数的数学期望，稳定状态下系统中等待服务顾客数的数学期望，简称平均简称平均等待队长等待队长。第24页/共35页 (2)(2)顾客在系统中的顾客在系统中的平均逗留时间平均逗留时间 则顾客在系统中的则顾客在系统中的平均等待时间平均等待时间 可以证明，顾客在系统中逗留时间服从参数为可以证明，顾客在系统中逗留时间服从参数为-的负指数分布。的负指数分布。第25页/共35页 与与 是是衡衡量量排排队队系系统统质质量量的的很很重重要要的的效效率度量率度量上式称为上式称为LittleLittle公式。公式。表明系统中的顾客数，等于一个顾客在表明系统中的顾客数，等于一个顾客在系统时间内来到的新的顾客数；系统时间内来到的新的顾客数；表明系统中处于等待状态的顾客数，等表明系统中处于等待状态的顾客数，等于一个顾客的等待时间内来到的新顾客数。于一个顾客的等待时间内来到的新顾客数。LittleLittle公式公式第26页/共35页(3)(3)稳定状态下稳定状态下忙期忙期的数学期望的数学期望由此可见，一个忙期中所服务顾客的平均数为由此可见，一个忙期中所服务顾客的平均数为忙忙第27页/共35页（二）系统容量有限的模型（二）系统容量有限的模型 即即为为M MM M1 1N N排排队队系系统统。考考虑虑排排队队系系统统的的容容量量为为N N，即即若若系系统统已已有有N N个个顾顾客客，则则再再来来新新顾顾客客即即被被拒绝进入系统。对于拒绝进入系统。对于n nN N，与与M MM M1 1相类似，相类似，有有对于对于n nN N，第28页/共35页 即即 满足微分方程满足微分方程 在稳态情况下，在稳态情况下，则则第29页/共35页 则则 由由 ，可得可得第30页/共35页系统的各项指标系统的各项指标第31页/共35页 由由于于有有容容量量的的限限制制，顾顾客客实实际际进进入入系系统统的的速速率率不不是是，而而是是 (有有效效到到达达率率)，因因而而LittleLittle公式成立：公式成立：第32页/共35页三、多通道等待制排队问题三、多通道等待制排队问题 （MMMMc c排队系统）排队系统）多多通通道道就就是是多多服服务务台台，这这里里主主要要讨讨论论M MM Mc c排排队队系系统统问问题题，即即输输入入、输输出出与与M MM M1 1相相同同，这这里里有有c c个个相相互互独独立立工工作作，且且服服务务速速率率相相同同的的服服务务台台，这时整个系统的服务能力为这时整个系统的服务能力为cc。当当 时，系统有稳定解时，系统有稳定解第33页/共35页系统指标系统指标 因而因而LittleLittle公式成立公式成立：第34页/共35页感谢您的观看！第35页/共35页