第六章-排队论

数学建模简明教程国家精品课程第六章排队论一、问题引入与分析二、排队论的基本概念三、几类排队论模型四、模型的建立与求解目录下页返回上页结束1.2001年全国数学竞赛的B题“公交车调度”某条公交线路上行方向共14站，下行方向共13站.公交公司配给该线路同一型号的大客车，每辆标准载客100人，据统计客车在该线路上运行的平均速度为20公里/小时.运营调度要求，乘客候车时间一般不要超过10分钟，早高峰一般不要超过是这样的：一、问题引入与分析目录下页返回上页结束5分钟，车辆满载率不应超过120%，一般也不要低于50%.试根据这些材料和要求，为该线路设计一个便于操作的全天（工作日）的公交车调度方案包括两个起点站的发车时刻表；一共需要多少辆车；这个方案以怎样的程度照顾到了乘客和公交公司双方的利益；等等.目录下页返回上页结束2.问题分析：目录下页返回上页结束对于第一个问题，关于公交车的调度方案，可以利用各种的不同的方法，比如多目标规划，去求得在一定原则下的最优方案，得到一个满足实际情况的分配方案，但要建立具体的明确、完整的数学模型，以及求解模型的方法，如何采集运营数据是关键的.在实际中，公交车具有随机性，特别是顾客的到来是随机的，是无法精确预目录下页返回上页结束测的，这就决定了公交车的数量并不是完全确定的固定不变的，而是随着不同时段顾客的多少而变化.因此顾客和公交车之间存在随机因素.很明显，顾客和公交车是一个服务和被服务的关系.如果公交车数量过多，也就是已有的资源大于需求，虽然公交车的数量能够满足顾客需求，减少了顾客排队等待的时间，公交车提供的服务使顾客的满意度很高，却会造成公交车公目录下页返回上页结束司的浪费，比如某一时段某一线路所发公交车上没有顾客或很少的顾客，个别时段个别线路如此，公交车公司也许可以接受，但长时间的空跑或入不敷出，最终会使公交车公司不堪重负，甚至倒闭；另一方面，如果公交车数量较少，很多顾客得不到服务，或者很多顾客花了很长的时间去排队等候，造成顾客的不满意度提高，这样公交车公司会失去顾客.如何考虑随机因素，设计合理方案，建立数学模型，一方面提供服务的服务机构即公交公司的线路设计合理，能够赢得顾客，获得利益；另一方面被服务的顾客能够在被服务的过程中，排队等候的时间最短，这都是上述问题要解决的，也是排队论的主要研究内容.目录下页返回上页结束二、排队论的基本知识目录下页返回上页结束2.排队系统描述3.基本组成部分4.数量指标5.排队模型的记号1.背景介绍1.背景介绍排队论是研究排队现象的理论和应用的学科，是专门研究由于随机因素影响而产生的拥挤现象的科学.20世纪初丹麦数学家、电气工程师爱尔朗把概率论应用于电话通话问题，从而开创了这门应用数学科学.20世纪30年代中期，费勒引进了生灭过程，排队论才被数学界承认为一门重要的学科.20世纪40年代排对论在运筹学这个新领域中成了一个重要的部分.20世纪50年代初肯德尔对排对论作了系统的研究，他用目录下页返回上页结束马尔科夫链方法研究排队论，使排队论得到进一步发展.20世纪60年代起排队论研究的课题日趋复杂，很多问题很难求得精确解，因此开始了近似方法的研究.排队论应用范围很广，它适用于一切服务系统.尤其在通信系统、交通系统、计算机存储系统和生产管理系统等方面应用的最多.排队是日常生活和工作中常见的现象.例如等公共汽车排队，到商店购物排队，交款排队，到医院看病目录下页返回上页结束等待排队，买火车票排队，托运行李排队，取货排队，这是人的排队.还有另一种排队，例如文件等待打印或发送，报告等首长批示，路口红红灯下的汽车、自行车等待通过路口，这是物或设备排队.总之，凡是具有公共服务性质的事业和工作，凡是出现拥挤现象的领域，都是排队论的用武之地.目录下页返回上页结束2.排队系统描述排队系统又称为随机服务系统，是研究服务•请求服务的人或者物——顾客；排队系统的共同特征：•顾客到达系统的时刻是随机的，为每一位顾客•有为顾客服务的人或者物，即服务员或服务台；目录下页返回上页结束过程和拥挤现象的随机模型.提供服务的时间是随机的，因而整个排队系统的状态也是随机的.排队系统的几种形式：目录下页返回上页结束目录下页返回上页结束目录下页返回上页结束目录下页返回上页结束目录下页返回上页结束基本排队过程：从图6—6可知，每个顾客由顾客源按一定方式目录下页返回上页结束到达服务系统，首先加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务的顾客立即离开.排队论所要研究解决的问题：面对拥挤现象，人们通常的做法是增加服务设施但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费，如果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响.如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾，就是随机服务系统理论——排队论所要研究解决的问题。目录下页返回上页结束3.排队系统的基本组成部分排队系统是由输入过程、排对规则和服务机构组成.(1).输入过程指要求服务的顾客是按怎样的规律(i)顾客总体数.又称顾客源、输入源.这是指顾客(ii)顾客到达方式.这是描述顾客是怎样来到系统目录下页返回上页结束到达排队系统的过程，有时也把它称为顾客流.一般可以从3个方面来描述—个输入过程.的来源.顾客源可以是有限的，也可以是无限的.的，是单个到达，还是成批到达.(iii)顾客流的概率分布.或称相继顾客到达的时间(2).排对规则指服务台从队列中选取顾客进行(i)损失制指如果顾客到达排队系统时，所有目录下页返回上页结束间隔的分布.这是求解排队系统有关运行指标问题时，首先需要确定的指标.顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种.服务的顺序.一般可以分为损失制、等待制和混合制等3大类.服务台都被先到的顾客占用，那么他们就自动离开系统永不再来.(ii)等待制指当顾客来到系统时，所有服务台a.先到先服务按顾客到达的先后顺序对顾客b.先到后服务c.随机服务即当服务台空闲时，不按照排队d.优先权服务目录下页返回上页结束都不空，顾客加入排队行列等待服务.等待制中，服务台在选择顾客进行服务时常有如下四种规则：进行服务.序列而随意指定某个顾客接受服务.(iii)混合制这是等待制与损失制相结合的一种服a.队长有限.当排队等待服务的顾客人数超b.等待时间有限.即顾客在系统中的等待时c.逗留时间(等待时间与服务时间之和)有限.目录下页返回上页结束务规则，一般是指允许排队，但又不允许队列无限长下去.具体说来，大致有三种：过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的.间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来.(3).服务机构(i)服务台数量及构成形式.从数量上说，服务台有单(ii)服务方式.这是指在某一时刻接受服务的顾客数，(iii)服务时间的分布.在多数情况下，对每一个顾客的目录下页返回上页结束服务台和多服务台之分.从构成形式上看，服务台有：①单队一---单服务台式；②单队一---多服务台并联式；③多队一---多服务台并联式；④单队一---多服务台串联式；⑤单队一---多服务台并串联混合式，以及多队多服务台并串联混合式等等.它有单个服务和成批服务两种.服务时间是一随机变量.4.排队系统的主要数量指标排队论主要研究系统的性态，即与排队有关(1).排队系统主要数量指标等待时间、忙期、队长.目录下页返回上页结束的数量指标的概率规律性；系统的优化问题；统计推断，根据资料合理建立模型.目的是正确设计和有效运行各个服务系统，使之发挥最佳效益.所以必须确定判断系统运行优劣的基本数量指标.(i).等待时间从顾客到达时刻起到他开始接受服务止这(ii).忙期忙期是指从顾客到达空闲着的服务机构起，到(iii).队长队长是指系统中的顾客数(排队等待的顾客数与目录下页返回上页结束段时间称为等待时间.等待时间是个随机变量.从顾客到达时刻起到他接受服务完成止这段时间称为逗留时间，也是随机变量.服务机构再次成为空闲止的这段时间，即服务机构连续忙的时间.这是个随机变量，是服务员最为关心的指标，因为它关系到服务员的服务强度.与忙期相对的是闲期,即服务机构连续保持空闲的时间.在排队系统中，忙期和闲期总是交替出现的.正在接受服务的顾客数之和)；排队长是指系统中正在排队等待服务的顾客数.队长和排队长一般都是随机变量.(2).数量指标的常用记号(i).主要数量指标W——平均逗留时间，即(在任意时刻)进入目录下页返回上页结束所有顾客数的期望值；等待服务的顾客数的期望值；稳态系统的顾客逗留时间的期望值；稳态系统的顾客等待时间的期望值.L-----平均队长，即稳态系统任一时刻的qW——平均等待时间，即(在任意时刻)进入qW——平均等待队长，即稳态系统任一时刻qL(ii).其它常用数量指标s——系统中并联服务台的数目；N——稳态系统任一时刻的状态（即系统中U——任一顾客在稳态系统中的逗留时间；Q——任一顾客在稳态系统中的等待时间；目录下页返回上页结束所有顾客数）；——平均到达率；λ——平均到达间隔；1λ——平均服务率；μ——平均服务时间；1μ有服务台全部空闲的概率；目录下页返回上页结束繁忙程度的重要尺度.——服务强度，即每个服务台单位时间内的平ρ均服务时间，一般有，这是衡量排队系统ρλμs:稳态系统任意时刻状态为n的概率；{}nPPNn特别当n=0时(系统中顾客数为0)，即稳态系统所0P5.排队系统的描述符号描述符号：X/Y/Z/A/B/CX—顾客相继到达的间隔时间的分布；常用下M——表示到达的过程为泊松过程或负指数分布；D——表示定长输入；G——表示一般相互独立的随机分布.Y—服务时间的分布；所用符号与表示顾客目录下页返回上页结束列符号：到达间隔时间分布相同.——表示K阶爱尔朗分布；kEZ—服务台个数；“1”表示单个服务台，“s”(s1)A－系统容量限制(默认为∞)；如系统有K个等待位子，则B－顾客源数目（默认为∞）；分有限与无限两种，∞表C－服务规则；常用下列符号：FCFS：表示先到先服务的排队规则；LCFS：表示后到先服务的排队规则；PR：表示优先权服务的排队规则。目录下页返回上页结束表示多个服务台.0K∞，当K=0时，说明系统不允许等待，即为损失制.K=∞时为等待制系统，此时一般∞省略不写.K为有限整数时，表示为混合制系统.示顾客源无限，一般∞也可省略不写.例如：某排队问题为M／M／S／∞／∞/FCFS，则某些情况下，排队问题仅用上述表达形式如不特别说明则均理解为系统等待空间容量目录下页返回上页结束表示顾客到达间隔时间为负指数分布(泊松流)；服务时间为负指数分布；有s(s1)个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则.中的前3个符号.例如，某排队问题为M／M／S.无限；顾客源无限，先到先服务，单个服务的等待制系统.三、几类排队论模型1.M/M/S模型2.GI/M/n模型目录下页返回上页结束1.M/M/s排队模型M/M/s排队模型是指s个服务员的排队系统，•顾客到来间隔时间是独立同分布的；•服务时间也是独立同分布的；•并且独立于输入过程；•排队规则是等待制；目录下页返回上页结束含假定：顾客到来间隔时间服从参数为的指数分布，λ服务时间服从参数为的负指数分布，且有隐μ按排队论的基本构成特征，来求解该排队模型(1).基本构成(i)顾客到达规律()(()),0,1,2!kλtλtPXtkekk目录下页返回上页结束的主要数量指标：平均到达率.表示在时间到达的顾客数，称为排队系统的输入过程.()Xt(,)ttΔt其平均值为，即单位时间内到达的顾客数为，并称为λtλ它服从参数为的泊松分布，即：λt(ii)服务时间目录下页返回上页结束服务率.表示顾客到达间隔时间序列，其1{|}nnnnssττ中表示第n个顾客的到来时刻.nτ可以证明：服从参数为的泊松分布的充(