数学建模排队论模型学习教案.pptx

《数学建模排队论模型学习教案.pptx》由会员分享，可在线阅读，更多相关《数学建模排队论模型学习教案.pptx（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数学数学(shxu)建模排队论模型建模排队论模型第一页，共35页。一、排队一、排队(pi du)论的基本概念论的基本概念（一）排队过程（一）排队过程 1.1.排队系统排队系统 “排排队队”是是指指在在服服务务机机构构处处要要求求服服务务对对象象的的一一个个等等待待队队列列，而而“排排队队论论”则则是是研研究究各各种种排排队队现现象象的的理理论。论。第2页/共35页第二页，共35页。在排队论中，我们把要求服务的对象称为“顾客(gk)”，而将从事服务的机构或人称为“服务台”。在顾客(gk)到达服务台时，可能立即得到服务，也可能要等待到可以利用服务台的时候为止。第3页/共35页第三页，共35

2、页。排队(pi du)系统队列除了有形的还有无形的。排队系统中的“顾客”与“服务台”这两个名词(mng c)可以从不同的角度去理解。排队系统排队系统顾客顾客服务台服务台上、下班的工人乘公共汽车上、下班的工人乘公共汽车工人工人公共汽车公共汽车病人到医院看病病人到医院看病病人病人医生医生高炮击退敌机高炮击退敌机敌机敌机高炮高炮机器发生故障需要维修机器发生故障需要维修机器机器修理工修理工第4页/共35页第四页，共35页。在上述顾客-服务台组成的排队系统中，顾客到来的时刻与服务台进行服务的时间一般来说是随不同的时机与条件而变化的，往往(wngwng)预先无法确定。因此，系统的状态是随机的，故而排队论也

3、称随机服务系统。第5页/共35页第五页，共35页。各式各样的排队现象呈现的基本特征：排队系统由输入过程、排队规则及服务机构三部分组成。(1)输入过程 输入过程就是顾客按怎样的规律到达包括顾客总体数，是有限(yuxin)的还是无限的；顾客到达的方式，是成批到达(每批数量是随机的还是确定性的)还是单个到达；相继到达的顾客(或批或单个)之间的时间间隔的分布是什么。2.2.排队系统排队系统(xtng)(xtng)的组成和特征的组成和特征第6页/共35页第六页，共35页。排队规则是指到达的顾客以怎样的规则接受服务。1）损失制：顾客到达，服务台不空立即离去，另求服务。2）等待(dngdi)制：顾客到达，排

4、队等待(dngdi)。对等待(dngdi)制服务可分为：先到先服务，后到先服务，优先服务，随机服务，成批服务等。3）混合制：在现实生活中，很多服务系统介于损失制和等待(dngdi)制之间，当顾客到达时，服务台不空就排队，若排队的位置已满就离去。(2)(2)排队排队(pi du)(pi du)规则规则第7页/共35页第七页，共35页。服务机构主要指服务台的数目，服务机构主要指服务台的数目，多个服务台进行多个服务台进行(jnxng)(jnxng)服务时，服务方式是服务时，服务方式是并联还是串联；并联还是串联；服务时间服从什么分布等。服务时间服从什么分布等。(3)(3)服务服务(fw)(fw)机构机

5、构第8页/共35页第八页，共35页。1.排队模型的分类这里仅针对并列的服务台。记X：顾客到达的时间间隔分布；Y：服务时间的分布；Z：服务台数。则排队模型：XYZ。常用的记号：M负指数分布；D确定型；Ekk阶爱尔朗（Erlang）分布；GI一般相互独立的随机分布，G一般随机分布。这里主要(zhyo)讨论MM1，MMC。（二）排队模型的分类（二）排队模型的分类(fn li)(fn li)及数量指标及数量指标第9页/共35页第九页，共35页。(1)(1)队长队长队队长长是是指指系系统统中中的的顾顾客客数数(包包括括排排队队等等候候(dnghu)(dnghu)和正在接受服务的顾客数和正在接受服务的顾客

6、数)；等待队长是指系统中等待服务的顾客数。等待队长是指系统中等待服务的顾客数。2.2.排队模型的数量指标排队模型的数量指标第10页/共35页第十页，共35页。逗留时间逗留时间(shjin)(shjin)是指一顾客从进入系统起一直到是指一顾客从进入系统起一直到接受服务后离开系统为止所花费的时间接受服务后离开系统为止所花费的时间(shjin)(shjin)；等待时间等待时间(shjin)(shjin)是指一顾客从进入系统起到接受是指一顾客从进入系统起到接受服务时所花费的时间服务时所花费的时间(shjin)(shjin)。(2)(2)逗留逗留(duli)(duli)时间时间第11页/共35页第十一页

7、，共35页。忙期是指从顾客到达空闲服务机构起到服务机构再次为空闲为止的这段时间，即服务机构连续繁忙的时间长度。这是服务机构最关心(gunxn)的数量指标，因为它直接关系到服务员的工作强度，与忙期相对应的是闲期，即为服务机构连续保持空闲的时间长度。显然，在排队系统中，忙期与闲期是交错出现的。(3)(3)忙期忙期第12页/共35页第十二页，共35页。1.1.最简单流与最简单流与PoissonPoisson过程过程 记记随随机机过过程程x x（t t）：t0t0为为时时间间0 0，t t内内流流(事事件件)发发生生的的次次数数，例例如如对对于于随随机机到到来来(doli)(doli)某某电电话话交交

8、换换台台的的呼呼叫叫，以以x x（t t）表表示示该该交交换换台台在在0 0，t t这这段段时时间间内内收收到到呼呼叫叫的的次次数数；若若是是服服务务机机构构，可可以以用用x x（t t）表表示示该该机机构构在在0 0，t t时时间间内内来来到到的的顾顾客客数。数。（三）（三）PoissonPoisson流与指数分布流与指数分布第13页/共35页第十三页，共35页。最简单流应最简单流应 具有以下特征称具有以下特征称(1)(1)流具有平衡性流具有平衡性 对任何对任何 和和 ,的分布只取决于的分布只取决于 而与而与 无关。无关。(2)(2)流具有无后效性流具有无后效性对互不交接的时间区间序列对互不

9、交接的时间区间序列 ，是一组相互独立的随机变量。是一组相互独立的随机变量。(3)(3)流具有普通性流具有普通性即在即在 时间内，事件发生多于时间内，事件发生多于1 1次的概率为次的概率为 。第14页/共35页第十四页，共35页。定理定理1 1设设 是最简单流，则对任何是最简单流，则对任何 和和都有都有 我们把满足这一分布规律的随机过程我们把满足这一分布规律的随机过程称为称为PoissonPoisson过程，最简单流亦称过程，最简单流亦称PoissonPoisson流，特别取流，特别取 得得故参数故参数表示单位时间内事件发生次数的平均数表示单位时间内事件发生次数的平均数。第15页/共35页第十五

10、页，共35页。2.Poisson2.Poisson流的发生流的发生(fshng)(fshng)时间间隔分布时间间隔分布 当当流流(过过程程)构构成成PoissonPoisson过过程程时时，就就称称为为PoissonPoisson流流。设设流流发发生生的的时时刻刻依依次次为为 ,，发生的时间间隔记为发生的时间间隔记为 ，其中其中 。定理定理2 2 事件流事件流 为为PoissonPoisson流的充要条件是流的充要条件是 的的流流发发生生时时间间间间隔隔 相相互互独独立立，且且服服从从相同的负指数分布，即相同的负指数分布，即第16页/共35页第十六页，共35页。对于单通道等待制排队问题主要讨论

11、输入过程为Poisson流，服务时间服从负指数分布，单服务台的情形，即MM1排队系统。（一）标准模型 即为MM1排队系统。所谓标准模型，就是顾客的输入流是参数为的Poisson流，每个顾客的服务时间是相互独立(dl)的且服从参数为的负指数分布，单个服务台且系统的容量无限(排队模型分类第四个表示系统中允许的最大顾客数)。二、单通道等待制排队问题二、单通道等待制排队问题(wnt)(wnt)（MMMM1 1排队系统）排队系统）第17页/共35页第十七页，共35页。1.1.系统系统(xtng)(xtng)的的MarkovMarkov特性特性 考考虑虑随随机机过过程程 ，其其中中 为为时时刻刻 时时排队

12、系统中的顾客数。排队系统中的顾客数。对于任何对于任何 条件概率条件概率由由于于输输入入为为PoissonPoisson流流，服服务务时时间间服服从从负负指指数数分分布布，则则无无论论 在在 处处取取何何值值，上上式式条条件件概概率率仅仅依依赖于赖于 的值和区间的值和区间 的长度的长度 ，即即第18页/共35页第十八页，共35页。记时刻记时刻t t系统处于状态系统处于状态n n的概率的概率利利用用M MM M1 1对对输输入入与与服服务务时时间间分分布布的的假假设设，在在时时间区间间区间 内，新进入或离开顾客个数有以下结果：内，新进入或离开顾客个数有以下结果：内没有顾客进入内没有顾客进入 内新进

13、入一名顾客内新进入一名顾客 内多于一名顾客进入内多于一名顾客进入 内没有顾客离开内没有顾客离开 内有一名顾客离开内有一名顾客离开 内多于一名顾客离开内多于一名顾客离开2.2.排队系统的稳态解排队系统的稳态解第19页/共35页第十九页，共35页。当当 时有时有导出导出 满足的微分方程组满足的微分方程组第20页/共35页第二十页，共35页。故故 满足的微分方程组满足的微分方程组对对第21页/共35页第二十一页，共35页。对于系统的稳定状态情形，对于系统的稳定状态情形，与与t t无关，无关，故故 ，记记 ，从而有从而有对于上述差分方程，利用归纳法不难求得对于上述差分方程，利用归纳法不难求得第22页/

14、共35页第二十二页，共35页。记 为排队系统的来往(liwng)强度，当 时，由 可得 由于由于 构成概率分布，则构成概率分布，则 ，从而级数从而级数 必须收敛，故有必须收敛，故有 。第23页/共35页第二十三页，共35页。MMMM1 1系统系统(xtng)(xtng)的数量指标的数量指标 (1)(1)稳定状态下系统中顾客数的数学期望的定义为稳定状态下系统中顾客数的数学期望的定义为被称为系统中顾客的平均数，简称被称为系统中顾客的平均数，简称平均队长平均队长。稳定状态下系统中等待服务顾客数的数学期望，稳定状态下系统中等待服务顾客数的数学期望，简称平均简称平均等待队长等待队长。第24页/共35页第

15、二十四页，共35页。(2)(2)顾客在系统中的顾客在系统中的平均逗留时间平均逗留时间 则顾客在系统中的则顾客在系统中的平均等待时间平均等待时间 可以证明，顾客在系统中逗留时间服从参数为可以证明，顾客在系统中逗留时间服从参数为-的负指数分布。的负指数分布。第25页/共35页第二十五页，共35页。与与 是是衡衡量量排排队队系系统统质质量量的的很很重重要要的的效效率度量率度量上式称为上式称为LittleLittle公式。公式。表明系统中的顾客数，等于一个顾客表明系统中的顾客数，等于一个顾客在系统时间内来到的新的顾客数；在系统时间内来到的新的顾客数；表明系统中处于等待状态的顾客数，表明系统中处于等待状

16、态的顾客数，等于一个顾客的等待时间内来到的新顾客数。等于一个顾客的等待时间内来到的新顾客数。LittleLittle公式公式第26页/共35页第二十六页，共35页。(3)(3)稳定状态下稳定状态下忙期忙期的数学期望的数学期望由此可见，一个忙期中所服务顾客的平均数为由此可见，一个忙期中所服务顾客的平均数为忙忙第27页/共35页第二十七页，共35页。（二）系统容量有限（二）系统容量有限(yuxin)(yuxin)的模型的模型 即即为为M MM M1 1N N排排队队系系统统。考考虑虑排排队队系系统统的的容容量量为为N N，即即若若系系统统已已有有N N个个顾顾客客，则则再再来来新新顾顾客客即即被被

17、拒绝进入系统。对于拒绝进入系统。对于n nN N，与与M MM M1 1相类似，相类似，有有对于对于n nN N，第28页/共35页第二十八页，共35页。即即 满足微分方程满足微分方程 在稳态情况下，在稳态情况下，则则第29页/共35页第二十九页，共35页。则则 由由 ，可得可得第30页/共35页第三十页，共35页。系统系统(xtng)(xtng)的各项指标的各项指标第31页/共35页第三十一页，共35页。由由于于有有容容量量的的限限制制，顾顾客客实实际际进进入入系系统统的的速速率率不不是是，而而是是 (有有效效到到达达率率)，因因而而LittleLittle公式成立：公式成立：第32页/共3

18、5页第三十二页，共35页。三、多通道等待制排队三、多通道等待制排队(pi du)(pi du)问题问题 （MMMMc c排队排队(pi du)(pi du)系统）系统）多多通通道道就就是是多多服服务务台台，这这里里主主要要讨讨论论M MM Mc c排排队队系系统统问问题题，即即输输入入、输输出出与与M MM M1 1相相同同，这这里里有有c c个个相相互互独独立立工工作作，且且服服务务速速率率相相同同的的服服务务台台，这时整个系统的服务能力为这时整个系统的服务能力为cc。当当 时，系统有稳定解时，系统有稳定解第33页/共35页第三十三页，共35页。系统系统(xtng)(xtng)指标指标 因而因而LittleLittle公式成立公式成立：第34页/共35页第三十四页，共35页。感谢您的观看感谢您的观看(gunkn)！第35页/共35页第三十五页，共35页。