数学建模算法大全排队论.doc

第六章 排队论模型排队论起源于1909年丹麦工程师A. K．爱尔朗的工作，他对通话拥挤问题进行了研究1917年，爱尔朗发表了他的著名的文章—“自动交换中的概率理论的几个问题的解决”排队论已广泛应用于解决军事、运输、维修、生产、服务、库存、医疗卫生、教育、水利灌溉之类的排队系统的问题，显示了强大的生命力排队是在日常生活中经常遇到的现象，如顾客到商店购买物品、病人到医院看病常常要排队此时要求服务的数量超过服务机构（服务台、服务员等）的容量也就是说，到达的顾客不能立即得到服务，因而出现了排队现象这种现象不仅在个人日常生活中出现，局的占线问题，车站、码头等交通枢纽的车船堵塞和疏导，故障机器的停机待修，水库的存贮调节等都是有形或无形的排队现象由于顾客到达和服务时间的随机性可以说排队现象几乎是不可避免的 排队论（Queuing Theory）也称随机服务系统理论，就是为解决上述问题而发展的一门学科它研究的内容有下列三部分：（i）性态问题，即研究各种排队系统的概率规律性，主要是研究队长分布、等待时间分布和忙期分布等，包括了瞬态和稳态两种情形。

（ii）最优化问题，又分静态最优和动态最优，前者指最优设计后者指现有排队系统的最优运营 （iii）排队系统的统计推断，即判断一个给定的排队系统符合于那种模型，以便根据排队理论进行分析研究 这里将介绍排队论的一些基本知识，分析几个常见的排队模型§1 基本概念1.1 排队过程的一般表示 下图是排队论的一般模型服务机构（服务时间随机）顾客排队 顾客随机达到 顾客离去 图中虚线所包含的部分为排队系统各个顾客从顾客源出发，随机地来到服务机构，按一定的排队规则等待服务，直到按一定的服务规则接受完服务后离开排队系统 凡要求服务的对象统称为顾客，为顾客服务的人或物称为服务员，由顾客和服务员组成服务系统对于一个服务系统来说，如果服务机构过小，以致不能满足要求服务的众多顾客的需要，那么就会产生拥挤现象而使服务质量降低 因此，顾客总希望服务机构越大越好，但是，如果服务机构过大，人力和物力方面的开支也就相应增加，从而会造成浪费，因此研究排队模型的目的就是要在顾客需要和服务机构的规模之间进行权衡决策，使其达到合理的平衡。

1.2 排队系统的组成和特征 一般的排队过程都由输入过程、排队规则、服务过程三部分组成，现分述如下：1.2.1 输入过程输入过程是指顾客到来时间的规律性，可能有下列不同情况：（i）顾客的组成可能是有限的，也可能是无限的 （ii）顾客到达的方式可能是一个—个的，也可能是成批的 （iii）顾客到达可以是相互独立的，即以前的到达情况对以后的到达没有影响；否则是相关的 （iv）输入过程可以是平稳的，即相继到达的间隔时间分布及其数学期望、方差等数字特征都与时间无关，否则是非平稳的1.2.2 排队规则 排队规则指到达排队系统的顾客按怎样的规则排队等待，可分为损失制，等待制和混合制三种 （i）损失制（消失制）当顾客到达时，所有的服务台均被占用，顾客随即离去 （ii）等待制当顾客到达时，所有的服务台均被占用，顾客就排队等待，直到接受完服务才离去例如出故障的机器排队等待维修就是这种情况 （iii）混合制介于损失制和等待制之间的是混合制，即既有等待又有损失有队列长度有限和排队等待时间有限两种情况，在限度以内就排队等待，超过一定限度就离去 排队方式还分为单列、多列和循环队列。

1.2.3 服务过程（i）服务机构主要有以下几种类型：单服务台；多服务台并联（每个服务台同时为不同顾客服务）；多服务台串联（多服务台依次为同一顾客服务）；混合型ii）服务规则按为顾客服务的次序采用以下几种规则：①先到先服务，这是通常的情形 ②后到先服务，如情报系统中，最后到的情报信息往往最有价值，因而常被优先处理 ③随机服务，服务台从等待的顾客中随机地取其一进行服务，而不管到达的先后④优先服务，如医疗系统对病情严重的病人给予优先治疗1.3 排队模型的符号表示排队模型用六个符号表示，在符号之间用斜线隔开，即第一个符号表示顾客到达流或顾客到达间隔时间的分布；第二个符号表示服务时间的分布；第三个符号表示服务台数目；第四个符号是系统容量限制；第五个符号是顾客源数目；第六个符号是服务规则，如先到先服务FCFS，后到先服务LCFS等并约定，如略去后三项，即指的情形我们只讨论先到先服务FCFS的情形，所以略去第六项表示顾客到达间隔时间和服务时间的分布的约定符号为：—指数分布（是Markov的字头，因为指数分布具有无记忆性，即Markov性）；—确定型（Deterministic）；—阶爱尔朗(Erlang)分布；—一般（general）服务时间的分布；—一般相互独立（General Independent）的时间间隔的分布。

例如，表示相继到达间隔时间为指数分布、服务时间为指数分布、单服务台、等待制系统表示确定的到达时间、服务时间为指数分布、个平行服务台（但顾客是一队）的模型 1.4 排队系统的运行指标 为了研究排队系统运行的效率，估计其服务质量，确定系统的最优参数，评价系统的结构是否合理并研究其改进的措施，必须确定用以判断系统运行优劣的基本数量指标，这些数量指标通常是： (i)平均队长：指系统内顾客数（包括正被服务的顾客与排队等待服务的顾客）的数学期望，记作 (ii)平均排队长:指系统内等待服务的顾客数的数学期望，记作 (iii)平均逗留时间：顾客在系统内逗留时间（包括排队等待的时间和接受服务的时间）的数学期望，记作 （iv）平均等待时间：指一个顾客在排队系统中排队等待时间的数学期望，记作v）平均忙期：指服务机构连续繁忙时间（顾客到达空闲服务机构起，到服务机构再次空闲止的时间）长度的数学期望，记为还有由于顾客被拒绝而使企业受到损失的损失率以及以后经常遇到的服务强度等，这些都是很重要的指标计算这些指标的基础是表达系统状态的概率所谓系统的状态即指系统中顾客数，如果系统中有个顾客就说系统的状态是，它的可能值是（i）队长没有限制时，，（ii）队长有限制，最大数为时，，（iii）损失制，服务台个数是时，。

这些状态的概率一般是随时刻而变化，所以在时刻、系统状态为的概率用表示稳态时系统状态为的概率用表示§2 输入过程与服务时间的分布排队系统中的事件流包括顾客到达流和服务时间流由于顾客到达的间隔时间和服务时间不可能是负值，因此，它的分布是非负随机变量的分布最常用的分布有泊松分布、确定型分布，指数分布和爱尔朗分布2.1 泊松流与指数分布设表示在时间区间内到达的顾客数（），令表示在时间区间内有个顾客到达的概率，即当合于下列三个条件时，我们说顾客的到达形成泊松流这三个条件是：1o 在不相重叠的时间区间内顾客到达数是相互独立的，我们称这性质为无后效性2o 对充分小的，在时间区间内有一个顾客到达的概率与无关，而约与区间长成正比，即 （1）其中，当时，是关于的高阶无穷小是常数，它表示单位时间有一个顾客到达的概率，称为概率强度3o 对于充分小的，在时间区间内有两个或两个以上顾客到达的概率极小，以致可以忽略，即 （2）在上述条件下，我们研究顾客到达数的概率分布。

由条件2o，我们总可以取时间由0算起，并简记由条件1o和2o，有 由条件2o和3o得 因而有 ，.在以上两式中，取趋于零的极限，当假设所涉及的函数可导时，得到以下微分方程组：，.取初值，，容易解出；再令，可以得到及其它所满足的微分方程组，即 ，.由此容易解得 .正如在概率论中所学过的，我们说随机变量服从泊松分布它的数学期望和方差分别是；当输入过程是泊松流时，那么顾客相继到达的时间间隔必服从指数分布这是由于内呼叫次数为零那么，以表示的分布函数，则有而分布密度函数为.对于泊松流,表示单位时间平均到达的顾客数,所以就表示相继顾客到达平均间隔时间，而这正和的意义相符对一顾客的服务时间也就是在忙期相继离开系统的两顾客的间隔时间，有时也服从指数分布这时设它的分布函数和密度函数分别是，我们得到 这表明，在任何小的时间间隔内一个顾客被服务完了（离去）的概率是表示单位时间能被服务完成的顾客数，称为平均服务率，而表示一个顾客的平均服务时间2.2 常用的几种概率分布及其产生2.2.1 常用的连续型概率分布我们只给出这些分布的参数、记号和通常的应用范围，更详细的内容参看专门的概率论书籍。

i）均匀分布区间内的均匀分布记作服从分布的随机变量又称为随机数，它是产生其它随机变量的基础如若为分布，则服从ii）正态分布以为期望，为方差的正态分布记作正态分布的应用十分广泛正态分布还可以作为二项分布一定条件下的近似iii）指数分布指数分布是单参数的非对称分布，记作，概率密度函数为：它的数学期望为，方差为指数分布是唯一具有无记忆性的连续型随机变量，即有，在排队论、可靠性分析中有广泛应用iv）Gamma分布Gamma分布是双参数的非对称分布，记作，期望是时蜕化为指数分布个相互独立、同分布（参数）的指数分布之和是Gamma分布（Gamma分布可用于服务时间，零件寿命等Gamma分布又称爱尔朗分布v）Weibull分布 Weibull分布是双参数的非对称分布，记作时蜕化为指数分布作为设备、零件的寿命分布在可靠性分析中有着非常广泛的应用vi）Beta分布Beta分布是区间内的双参数、非均匀分布，记作2.2.2 常用的离散型概率分布（i）离散均匀分布（ii）Bernoulli分布（两点分布）Bernoulli分布是处取值的概率分别是和的两点分布，记作用于基本的离散模型iii）泊松（Poisson）分布泊松分布与指数分布有密切的关系。

当顾客平均到达率为常数的到达间隔服从指数分布时，单位时间内到达的顾客数服从泊松分布，即单位时间内到达位顾客的概率为 记作反过来也是这样泊松分布在排队服务、产品检验、生物与医学统计、天文、物理等领域都有广泛应用iv）二项分布在独立进行的每次试验中，某事件发生的概率为，则次试验中该事件发生的次数服从二项分布，即发生次的概率为 .记作二项分布是个独立的Bernoulli分布之和它在产品检验、保险、生物和医学统计等领域有着广泛的应用当很大时，近似于正态分布；当很大、很小，且约为常数时，近似于§3 标准的模型标准的模型是指适合下列条件的排队系统：（i）输入过程—顾客源是无限的，顾客单个到来，相互独立，一定时间的到达数服从泊松分布。