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

1、排 队 论 模 型 1第一页，共三十五页。排队论模型 一、排队论的基本概念 二、单通道等待制排队问题 （MM1排队系统）三、多通道等待制排队问题 （MMc排队系统） 2第二页，共三十五页。一、排队论的基本概念（一）排队过程 1.排队系统 “排队”是指在服务机构处要求服务对象的一个等待队列，而“排队论”则是研究各种排队现象的理论。 3第三页，共三十五页。 在排队论中，我们把要求服务的对象称为“顾客”，而将从事服务的机构或人称为“服务台”。 在顾客到达服务台时，可能立即得到服务，也可能要等待到可以利用服务台的时候为止。4第四页，共三十五页。 排队系统队列除了有形的还有无形的。 排队系统中的“顾客”

2、与“服务台”这两个名词可以从不同的角度去理解。排队系统顾客服务台上、下班的工人乘公共汽车工人公共汽车病人到医院看病病人医生高炮击退敌机敌机高炮机器发生故障需要维修机器修理工5第五页，共三十五页。 在上述顾客-服务台组成的排队系统中，顾客到来的时刻与服务台进行服务的时间一般来说是随不同的时机与条件而变化的，往往预先无法确定。因此，系统的状态是随机的，故而排队论也称随机服务系统。6第六页，共三十五页。 各式各样的排队现象呈现的基本特征：排队系统由输入过程、排队规则及服务机构三部分组成。(1)输入过程 输入过程就是顾客按怎样的规律到达包括顾客总体数，是有限的还是无限的；顾客到达的方式，是成批到达(每

3、批数量是随机的还是确定性的)还是单个到达；相继到达的顾客(或批或单个)之间的时间间隔的分布是什么。 2.排队系统的组成和特征7第七页，共三十五页。 排队规则是指到达的顾客以怎样的规则接受服务。 1）损失制：顾客到达，服务台不空立即离去，另求服务。 2）等待制：顾客到达，排队等待。对等待制服务可分为：先到先服务，后到先服务，优先服务，随机服务，成批服务等。 3）混合制：在现实生活中，很多服务系统介于损失制和等待制之间，当顾客到达时，服务台不空就排队，若排队的位置已满就离去。 (2)排队规则8第八页，共三十五页。服务机构主要指服务台的数目，多个服务台进行服务时，服务方式是并联还是串联；服务时间服从

4、什么分布等。 (3)服务机构9第九页，共三十五页。 1.排队模型的分类这里仅针对并列的服务台。 记X：顾客到达的时间间隔分布；Y：服务时间的分布；Z：服务台数。则排队模型：XYZ。 常用的记号：M负指数分布；D确定型；Ekk阶爱尔朗（Erlang）分布；GI一般相互独立的随机分布，G一般随机分布。这里主要讨论MM1，MMC。（二）排队模型的分类及数量指标10第十页，共三十五页。 (1)队长队长是指系统中的顾客数(包括排队等候和正在接受服务的顾客数)；等待队长是指系统中等待服务的顾客数。 2.排队模型的数量指标11第十一页，共三十五页。逗留时间是指一顾客从进入系统起一直到接受服务后离开系统为止所

5、花费的时间；等待时间是指一顾客从进入系统起到接受服务时所花费的时间。 (2)逗留时间12第十二页，共三十五页。 忙期是指从顾客到达空闲服务机构起到服务机构再次为空闲为止的这段时间，即服务机构连续繁忙的时间长度。这是服务机构最关心的数量指标，因为它直接关系到服务员的工作强度，与忙期相对应的是闲期，即为服务机构连续保持空闲的时间长度。显然，在排队系统中，忙期与闲期是交错出现的。 (3)忙期13第十三页，共三十五页。1.最简单流与Poisson过程 记随机过程x（t）：t0为时间0，t内流(事件)发生的次数，例如对于随机到来某电话交换台的呼叫，以x（t）表示该交换台在0，t这段时间内收到呼叫的次数；

6、若是服务机构，可以用x（t）表示该机构在0，t时间内来到的顾客数。（三）Poisson流与指数分布14第十四页，共三十五页。最简单流应 具有以下特征称(1)流具有平衡性 对任何 和 , 的分布只取决于 而与 无关。(2)流具有无后效性对互不交接的时间区间序列 ， 是一组相互独立的随机变量。(3)流具有普通性即在 时间内，事件发生多于1次的概率为 。 15第十五页，共三十五页。定理1设 是最简单流，则对任何 和都有 我们把满足这一分布规律的随机过程称为Poisson过程，最简单流亦称Poisson流，特别取 得故参数表示单位时间内事件发生次数的平均数。16第十六页，共三十五页。2.Poisson

7、流的发生时间间隔分布 当流(过程) 构成Poisson过程时，就称为Poisson流。设流发生的时刻依次为 ,，发生的时间间隔记为 ，其中 。定理2 事件流 为Poisson流的充要条件是 的流发生时间间隔 相互独立，且服从相同的负指数分布，即17第十七页，共三十五页。 对于单通道等待制排队问题主要讨论输入过程为Poisson流，服务时间服从负指数分布，单服务台的情形，即MM1排队系统。（一）标准模型 即为MM1排队系统。所谓标准模型，就是顾客的输入流是参数为的Poisson流，每个顾客的服务时间是相互独立的且服从参数为的负指数分布，单个服务台且系统的容量无限(排队模型分类第四个表示系统中允许

8、的最大顾客数)。二、单通道等待制排队问题 （MM1排队系统）18第十八页，共三十五页。1.系统的Markov特性 考虑随机过程 ，其中 为时刻 时排队系统中的顾客数。 对于任何 条件概率由于输入为Poisson流，服务时间服从负指数分布，则无论 在 处取何值，上式条件概率仅依赖于 的值和区间 的长度 ，即19第十九页，共三十五页。 记时刻t系统处于状态n的概率利用MM1对输入与服务时间分布的假设，在时间区间 内，新进入或离开顾客个数有以下结果： 内没有顾客进入 内新进入一名顾客 内多于一名顾客进入 内没有顾客离开 内有一名顾客离开 内多于一名顾客离开2.排队系统的稳态解20第二十页，共三十五页

9、。 当 时有导出 满足的微分方程组21第二十一页，共三十五页。故 满足的微分方程组对22第二十二页，共三十五页。 对于系统的稳定状态情形， 与t无关，故 ，记 ，从而有对于上述差分方程，利用归纳法不难求得23第二十三页，共三十五页。 记 为排队系统的来往强度，当 时，由 可得 由于 构成概率分布，则 ，从而级数 必须收敛，故有 。24第二十四页，共三十五页。MM1系统的数量指标 (1)稳定状态下系统中顾客数的数学期望的定义为被称为系统中顾客的平均数，简称平均队长。 稳定状态下系统中等待服务顾客数的数学期望，简称平均等待队长。25第二十五页，共三十五页。 (2)顾客在系统中的平均逗留时间 则顾客

10、在系统中的平均等待时间 可以证明，顾客在系统中逗留时间服从参数为-的负指数分布。26第二十六页，共三十五页。 与 是衡量排队系统质量的很重要的效率度量上式称为Little公式。 表明系统中的顾客数，等于一个顾客在系统时间内来到的新的顾客数； 表明系统中处于等待状态的顾客数，等于一个顾客的等待时间内来到的新顾客数。 Little公式27第二十七页，共三十五页。(3)稳定状态下忙期的数学期望由此可见，一个忙期中所服务顾客的平均数为忙忙28第二十八页，共三十五页。（二）系统容量有限的模型 即为MM1N排队系统。考虑排队系统的容量为N，即若系统已有N个顾客，则再来新顾客即被拒绝进入系统。对于nN，与MM1相类似， ，有对于nN，29第二十九页，共三十五页。 即 满足微分方程 在稳态情况下， ， ，则30第三十页，共三十五页。 则 由 ，可得31第三十一页，共三十五页。系统的各项指标32第三十二页，共三十五页。 由于有容量的限制，顾客实际进入系统的速率不是，而是 (有效到达率)，因而Little公式成立：33第三十