《学校数模培训课件排队论方法》由会员分享，可在线阅读，更多相关《学校数模培训课件排队论方法（85页珍藏版）》请在金锄头文库上搜索。
1、排队论方法,基本概念 排队模型问题分类 排队问题求解 排队系统的优化,排队论(Queuing Theory)，又称随机服务系统理论(Random Service System Theory),是一门研究拥 挤现象(排队、等待)的学科。 排队论内容主要有三部分: (1)性态问题:研究排队系统的概率分布规律,主要研究队长分布,等待时间分布和忙期分布等; (2)最优化问题:分为静态最优化和动态最优化,即系统的最优设计和最优运营问题; (3)排队系统的统计推断:判断一个给定的排队系统属于哪种类型,以进行研究.,1.排队论基本概念,实际上排队的过程可由下面几个图理解:,1. 排队论基本概念,1输入过程
2、(1)顾客总体数，又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。例如，到售票处购票的顾客总数可以认为是无限的，而某个工厂因故障待修的机床则是有限的。,(2)顾客到达方式。这是描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。病人到医院看病是顾客单个到达的例子。在库存问题中如将生产器材进货或产品入库看作是顾客，那么这种顾客则是成批到达的,(3)顾客相继到达的时间间隔可能是确定型的,也可能是随机型的. (4)顾客到达是相互独立的. (5)相继到达的时间间隔与时间无关,2.排队规则 (1)即时制也称损失制。这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用
3、，那么他们就自动离开系统永不再来。典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为即时制,(2)等待制。这是指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。例如，排队等待售票，故障设备等待维修等。等待制中，服务台在选择顾客进行服务时，常有如下四种规则： 先到先服务。按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形。 后到先服务。仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。,随机服务。即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。 优先权服务。如老人、儿童先进
4、车站；危重病员先就诊；遇到重要数据需要处理计算机立即中断其他数据的处理等，均属于此种服务规则。,(3)混合制这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种： 队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。例如最多只能容纳K个顾客在系统中，当新顾客到达时，若系统中的顾客数(又称为队长)小于K，则可进入系统排队或接受服务；否则，便离开系统，并不再回来。如水库的库容是有限的，旅馆的床位是有限的。, 等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾
5、客将自动离去，并不再回来。如易损坏的电子元器件的库存问题，超过一定存储时间的元器件被自动认为失效。又如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。, 逗留时间(等待时间与服务时间之和)有限。例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t时，若在这个时间内未被击落，也就不可能再被击落了。 不难注意到，损失制和等待制可看成是混合制的特殊情形.,服务机构,单队单服务台式； 单队多服务台并联式； 多队多服务台并联式； 单队多服务台串联式； 单队多服务台并串联混合式,以及 多队多服务台并串联混合式等等。 见前面图1至图5所示。,（三）排队系统的描述符号与分类 为了区别各种
6、排队系统，根据输入过程、排队规则和服务机制的变化对排队模型进行描述或分类，可给出很多排队模型。为了方便对众多模型的描述，肯道尔（DGKendall）提出了一种目前在排队论中被广泛采用的“Kendall记号”，完整的表达方式通常用到6个符号并取如下固定格式： X/Y/Z/A/B/C 各符号的意义为：,X表示相继到达间隔时间的分布，Y表示服务时间的分布，X,Y取值有以下几种情况: M表示泊松过程或负指数分布； D表示确定型分布； Ek表示k阶爱尔朗分布； G表示一般服务时间分布; GI表示一般相互独立的时间间隔分布.,Z表示服务台(员)个数：“1”则表示单个服务台，“s”。(s1)表示多个服务台。
7、 A表示系统中容量限额，或称等待空间容量； B表示顾客源数目，分有限与无限两种，表示顾客源无限，此时一般也可省略不写。 C表示服务规则,C表示服务规则，常用下列符号： (1)FCFS：表示先到先服务的排队规则； (2)LCFS：表示后到先服务的排队规则； (3)PR：表示优先权服务的排队规则。 (4)随机服务 省略时代表的是FCFS（先到先服务）。,二、排队系统的主要数量指标 研究排队系统的目的是通过了解系统运行的状况，对系统进行调整和控制，使系统处于最优运行状态。因此，首先需要弄清系统的运行状况。描述一个排队系统运行状况的主要数量指标有：,1.队长和排队长（队列长） 队长是指系统中的平均顾客
8、数(排队等待的顾客数与正在接受服务的顾客数之和)， 排队长是指系统中正在排队等待服务的平均顾客数。 队长和排队长一般都是随机变量。我们希望能确定它们的分布，或至少能确定它们的平均值(即平均队长和平均排队长)及有关的矩(如方差等)。队长的分布是顾客和服务员都关心的，特别是对系统设计人员来说，如果能知道队长的分布，就能确定队长超过某个数的概率，从而确定合理的等待空间。,2等待时间和逗留时间 从顾客到达时刻起到他开始接受服务止这段时间称为等待时间，是随机变量，也是顾客最关心的指标，因为顾客通常希望等待时间越短越好。从顾客到达时刻起到他接受服务完成止这段时间称为逗留时间，也是随机变量，同样为顾客非常关
9、心。对这两个指标的研究当然是希望能确定它们的分布，或至少能知道顾客的平均等待时间和平均逗留时间。,3忙期和闲期 忙期是指从顾客到达空闲着的服务机构起，到服务机构再次成为空闲止的这段时间，即服务机构连续忙的时间。这是个随机变量，是服务员最为关心的指标，因为它关系到服务员的服务强度。与忙期相对的是闲期，即服务机构连续保持空闲的时间。在排队系统中，忙期和闲期总是交替出现的。,4.损失率和服务强度 损失率:由于系统条件限制,使顾客被拒绝服务而使服务部门受到损失的概率. 服务强度: 绝对通过能力A,表示单位时间内被服务完顾客的均值，或称为平均服务率. 相对通过能力Q,表示单位时间内被服务完客户数于请求服
10、务客户数的比值.,1.4系统状态的概率,系统状态是求运行指标的基础,所谓系统状态是指系统中顾客的数量.如果系统中有n个顾客,则说系统的状态为n,即可能取值为: (1) 当队长无限制时,则n=0,1,2,; (2) 当队长有限制,且最大值为N时,则n=0,1,2,.N; (3) 当服务台个数为c,且服务为即时制时，则n=0,1,2,c 一般来说状态取值与时间t有关,因此在时刻t系统状态取值为n的概率记为Pn(t) ,若Pn(t) Pn 则称为稳态(或统计平衡状态)解.实际中多数平衡问题都是属于稳态的情况,并不是真正的t,即过一段时间以后就有Pn(t) Pn.,2.到达时间的间隔分布和服务时间分布
11、,到达时间的间隔分布和服务时间分布一般分为泊松分布,负指数分布和爱尔朗分布. 2.1 泊松分布 设N(t)表示在时间段0,t)内的到达的顾客数,Pn(t1,t2)表示在时间段t1,t2)(t2t1)内有n(n0)个顾客达到的概率,即Pn(t1,t2)=PN(t2)-N(t1)=n,当Pn(t1,t2)满足如下三个条件时,则称顾客到达形成泊松流;,无后效性:在不相交的时间区间内顾客到达是相互独立的,即在t,t+t到达的顾客与时刻t前到达的顾客数无关. (2)平稳性：对于充分小的t，在时间段t,t+t内有1个顾客到达的概率只与时间段长度t有关,而与起始时间t无关,且P1(t,t+t)=t+o(t)
12、,其中0称为概率强度(或平稳流强度),即单位时间内有一个顾客到达的概率.,（3）普通性:对于充分小的t,在t,t+t内有2个或2个以上顾客到达的概率极小,即,下面研究系统状态概率n的分布. 如果取时间段的 初始时间为t=0,则可记为Pn(0,t)=Pn(t),在t,t+t)内,由于,故在t,t+t)内没有顾客到达的概率为 将 0,t+t)分为0,t)和t,t+ t),则在时间段0,t+t)达到n个顾客的概率为,2.2 负指数分布,当顾客流为泊松分布时,用T表示两个相继到达的时间间隔, 是一个随机变量,其分布函数,类似的,设系统对一个顾客的服务时间为v(即在忙期内相继离开系统的两个顾客的间隔时间
13、)服从于负指数分布,分布函数为,2.3爱尔朗分布,设有如下顾客流,记k个顾客达到系统的时间间隔 同时服从于ku的负指数分布,则随机变量 服从k阶爱尔朗分布. 当k=1时爱尔朗分布为负指数分布,3.单服务台模型,单服务台模型分为3种 设系统输入过程服从泊松流,服务时间服从负指数分布,单服务台: (1)标准型:M/M/1/ / (2)系统容量有限型:M/M/1/ N / (3)顾客源有限型:M/M/1/ /m,3.1 标准型：M/M/1,标准型表示顾客源为无限的，顾客的到达相互独立， 到达规律服从参数为的泊松分布：单服务台、对长 无限、先到先服务；各顾客的服务时间相互独立，且 同服从于参数为的负指
14、数分布。 1.确定系统在任意时刻t状态为n的概率,现在考虑在t+t时刻系统中有n个顾客（即状态为n）的 概率Pn(t +t)，如下表：,M/M/1 无限源系统,系统状态转移关系图：,2.系统运行指标,运行指标之间的关系 这些关系式称为Little公式.,3.2系统容量有限制:M/M/1/N/,3.2系统容量有限制:M/M/1/N/,系统状态概率 (1)稳态方程为,2.系统运行指标,3.3顾客源为有限的:M/M/1/m,对顾客总体只有m个顾客,但每个顾客来到并接受服务后,仍然回到顾客总体,即可以再次到来,所以对顾客的容量是没有限制的,实际上系统中顾客永远不会超过m,即与模型. M/M/1/m/m
15、是相同的,于是我们得到系统概率平衡方程:,3.3 多服务台的排队模型,多服务台主要分为三种情况: (1)标准型：M/M/C (2)系统容量有限型：M/M/C/N/ (3)顾客源为有限的：M/M/C/ /m,4.1标准型：M/M/C,4.2系统容量有限制,4.3顾客源有限,5排队系统的最优化问题,最优化问题分为俩类: (1)静态最优化,指服务机构根据一定的质量指标,找出参数最优值,使系统设计最经济. (2)动态最优化,对已有的队伍系统寻求某一没表函数达到最优的运营机制. 2.费用模型,我们的目标使服务机构成本和等待费用之和最小.,M/M/1 中最优服务率,5.2系统容量有限,5.3顾客源为有限,5.3M/M/c中最优服务台数,应用举例,例:兴建一座港口码头，只有一个装卸船只的泊位。要求设计装卸能力。装卸能力单位为（只/日）船数。已知：单位装卸能力的平均生产费用a=2千元，船只逗留每日损失b=1.5千元。船只到达服从泊松分布，平均速率=3只/日。船只装卸时间服从负指数分布。目标是每日总支出最少。,解： =3 待定 模型 M/M/1/ 队长 Ls =/(-) 总费用 C=a+bLs=a+b/(-) 求极值（最小值）,求 dc/du=a+(-b)/(-)2 = 0 得:-=+ - (b/a)1/2（根据题意舍）
