数学建模之排队论课件

1 排排队队论论（queuing),也也称称随随机机服服务务系系统统理理论论，是是运筹学的一个主要分支。运筹学的一个主要分支。1909年年，丹丹麦麦哥哥本本哈哈根根电电子子公公司司电电话话工工程程师师A.K.Erlang的的开开创创性性论论文文“概概率率论论和和电电话话通通讯讯理理论论”标标志志此此理理论论的的诞诞生生。排排队队论论的的发发展展最最早早是是与与电电话话，通通信信中中的的问问题题相相联联系系的的，并并到到现现在在是是排排队队论论的的传传统统的的应应用用领领域域。近近年年来来在在计计算算机机通通讯讯网网络络系系统统、交交通通运运输输、医医疗疗卫卫生生系系统统、库库存存管管理理、作作战战指指挥挥等等各各领领域中均得到应用。域中均得到应用。28 排队论排队论8-1 前言前言8-2 基基 本本 概概 念念8-3 输入过程和服务时间分布输入过程和服务时间分布8-4 泊松输入泊松输入指数服务排队模型指数服务排队模型8-5 M/M/1 无限源系统无限源系统8-6 系统容量有限的排队系统系统容量有限的排队系统8-7 顾客源有限的排队系统顾客源有限的排队系统3排排队队是是我我们们在在日日常常生生活活和和生生产产中中经经常遇到的现象。常遇到的现象。例如，上、下班搭乘公共汽车；例如，上、下班搭乘公共汽车；顾客到商店购买物品；顾客到商店购买物品；病员到医院看病；病员到医院看病；旅客到售票处购买车票；旅客到售票处购买车票；学学生生去去食食堂堂就就餐餐等等就就常常常常出出现现排排队队和和等等待待现象。现象。前前 言言4 除除了了上上述述有有形形的的排排队队之之外外，还还有有大大量量的所谓的所谓“无形无形”排队现象。排队现象。如如几几个个顾顾客客打打电电话话到到出出租租汽汽车车站站要要求求派派车车，如如果果出出租租汽汽车车站站无无足足够够车车辆辆、则则部部分分顾顾客客只只得得在在各各自自的的要要车车处处等等待待，他他们们分分散散在在不不同同地地方方，却却形形成成了了一一个个无无形形队列在等待派车。队列在等待派车。前前 言言5 排队的不一定是人，也可以是物：排队的不一定是人，也可以是物：例例如如，通通讯讯卫卫星星与与地地面面若若干干待待传传递递的的信息；信息；生产线上原料、半成品等待加工；生产线上原料、半成品等待加工；因因故故障障停停止止运运转转的的机机器器等等待待修修理理；码码头头的船只等待装卸货物；的船只等待装卸货物；要要降降落落的的飞飞机机因因跑跑道道不不空空而而在在空空中中盘盘旋等等。旋等等。前前 言言6 上上述述各各种种问问题题虽虽互互不不相相同同，但但却却都都有有要要求求得得到到某某种种服服务务的的人人或或物物和和提提供供服服务务的的人或机构。人或机构。排排队队论论里里把把要要求求服服务务的的对对象象统统称称为为“顾顾客客”,提提供供服服务务的的人人或或机机构构称称为为“服服务务台台”或或“服务员服务员”。前前 言言7 不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图8-1至图8-5。图图8-1 8-1 单服务台排队系统单服务台排队系统前前 言言8图图8-2 8-2 单队列单队列SS个服务台并联的排队系统个服务台并联的排队系统图图8-3 S8-3 S个队列个队列SS个服务台的并联排队系统个服务台的并联排队系统前前 言言9图图8-4 8-4 单队单队多个服务台的串联排队系统多个服务台的串联排队系统图图8-5 8-5 多队多队多服务台混联网络系统多服务台混联网络系统前前 言言10图图8-6 8-6 随机服务系统随机服务系统前前 言言一一般般的的排排队队系系统统，都都可可由由下下面图加以描述。面图加以描述。通常称由图通常称由图8-68-6表示的系统为一随机聚散服务系统。表示的系统为一随机聚散服务系统。任一排队系统都是一个随机聚散服务系统。任一排队系统都是一个随机聚散服务系统。“聚聚”表示顾客的到达，表示顾客的到达，“散散”表示顾客的离去表示顾客的离去。11 面面对对拥拥挤挤现现象象，人人们们总总是是希希望望尽尽量量设设法法减少排队，通常的做法是增加服务设施。减少排队，通常的做法是增加服务设施。但但是是增增加加的的数数量量越越多多，人人力力、物物力力的的支支出就越大，甚至会出现空闲浪费。出就越大，甚至会出现空闲浪费。如如果果服服务务设设施施太太少少，顾顾客客排排队队等等待待的的时时间就会很长，这样对顾客会带来不良影响。间就会很长，这样对顾客会带来不良影响。前前 言言12 顾顾客客排排队队时时间间的的长长短短与与服服务务设设施施规规模模的的大大小小，就就构构成成了了设设计计随随机机服服务务系系统统中中的的一一对对矛盾。矛盾。如如何何做做到到既既保保证证一一定定的的服服务务质质量量指指标标，又又使使服服务务设设施施费费用用经经济济合合理理，恰恰当当地地解解决决顾顾客排队时间与服务设施费用大小这对矛盾。客排队时间与服务设施费用大小这对矛盾。这这就就是是随随机机服服务务系系统统理理论论排排队队论论所所要研究解决的问题。要研究解决的问题。前前 言言13 一、排队系统的组成与特征一、排队系统的组成与特征 排队系统一般有三个基本组成部分：排队系统一般有三个基本组成部分：1.1.输输入过程；入过程；2.2.排队规则；排队规则；3.3.服务机构。服务机构。8-2 8-2 排队系统的基本概念排队系统的基本概念14 输入即为顾客的到达，可有下列情况：输入即为顾客的到达，可有下列情况：1）顾客源可能是有限的，也可能是无限的。顾客源可能是有限的，也可能是无限的。2）顾客是成批到达或是单个到达。顾客是成批到达或是单个到达。3）顾客到达间隔时间可能是随机的或确定的。顾客到达间隔时间可能是随机的或确定的。4）顾客到达可能是相互独立或关联的。所谓独顾客到达可能是相互独立或关联的。所谓独立就是以前顾客的到达对以后顾客的到达无影响。立就是以前顾客的到达对以后顾客的到达无影响。5）输入过程可以是平稳的（输入过程可以是平稳的（stationarystationary）或说或说是对时间齐次的（是对时间齐次的（Homogeneous in timeHomogeneous in time），），也可以也可以是非平稳的。输入过程平稳的指顾客相继到达的间是非平稳的。输入过程平稳的指顾客相继到达的间隔时间分布和参数（均值、方差）与时间无关；非隔时间分布和参数（均值、方差）与时间无关；非平稳的则是与时间相关，非平稳的处理比较困难。平稳的则是与时间相关，非平稳的处理比较困难。1.1.输入过程输入过程15这是指服务台从队列中选取顾客进行服务的顺序。这是指服务台从队列中选取顾客进行服务的顺序。可以分为可以分为损失制、等待制、混合制损失制、等待制、混合制3 3大类。大类。(1)(1)损损失失制制。这这是是指指如如果果顾顾客客到到达达排排队队系系统统时时，所所有有服服务务台台都都已已被被先先来来的的顾顾客客占占用用，那那么么他他们们就就自动离开系统永不再来。自动离开系统永不再来。典典型型例例子子是是，如如电电话话拔拔号号后后出出现现忙忙音音，顾顾客客不不愿愿等等待待而而自自动动挂挂断断电电话话，如如要要再再打打，就就需需重重新新拔号，这种服务规则即为损失制。拔号，这种服务规则即为损失制。2 2.排队规则排队规则16 (2)(2)等等待待制制。指指当当顾顾客客来来到到系系统统时时，所所有有服服务务台台都不空，顾客加入排队行列等待服务。都不空，顾客加入排队行列等待服务。例如，排队等待售票，故障设备等待维修等。例如，排队等待售票，故障设备等待维修等。等等待待制制中中，服服务务台台在在选选择择顾顾客客进进行行服服务务时时，常常有有如下四种规则：如下四种规则：先先到到先先服服务务（FCFS FCFS）。按按顾顾客客到到达达的的先先后后顺顺序对顾客进行服务，这是最普遍的情形。序对顾客进行服务，这是最普遍的情形。后后到到先先服服务务（LCFSLCFS）。仓仓库库中中迭迭放放的的钢钢材材，后迭放上去的都先被领走，就属于这种情况。后迭放上去的都先被领走，就属于这种情况。2 2.排队规则排队规则17 随随机机服服务务（RAND）。即即当当服服务务台台空空闲闲时时，不不按按照照排排队队序序列列而而随随意意指指定定某某个个顾顾客客去去接接受受服服务务，如如电电话话交交换换台台接接通通呼呼叫叫电电话话就就是一例。是一例。优优先先权权服服务务（PR）。如如老老人人、儿儿童童先先进进车车站站；危危重重病病员员先先就就诊诊；遇遇到到重重要要数数据据需需要要处处理理计计算算机机立立即即中中断断其其他他数数据据的的处处理理等等，均属于此种服务规则。均属于此种服务规则。2 2.排队规则排队规则18 (3)(3)混混合合制制这这是是等等待待制制与与损损失失制制相相结结合合的的一一种种服服务务规规则则，一一般般是是指指允允许许排排队队，但但又又不不允允许许队队列列无限长下去。具体说来，大致有三种：无限长下去。具体说来，大致有三种：队队长长有有限限。当当排排队队等等待待服服务务顾顾客客人人数数超超过过规定数量时，后来顾客就自动离去，另求服务。规定数量时，后来顾客就自动离去，另求服务。如水库的库容、旅馆的床位等都是有限的如水库的库容、旅馆的床位等都是有限的。2 2.排队规则排队规则19 等等待待时时间间有有限限。即即顾顾客客在在系系统统中中的的等等待待时时间间不不超超过过某某一一给给定定的的长长度度T T，当当等等待待时时间超过间超过T T时，顾客自动离去，不再回来。时，顾客自动离去，不再回来。如如易易损损坏坏的的电电子子元元器器件件的的库库存存问问题题，超过一定存储时间被自动认为失效。超过一定存储时间被自动认为失效。又又如如顾顾客客到到饭饭馆馆就就餐餐，等等了了一一定定时时间间后后不愿再等而自动离去另找饭店用餐。不愿再等而自动离去另找饭店用餐。2 2.排队规则排队规则20 逗逗留留时时间间(等等待待时时间间与与服服务务时时间间之之和和)有限。有限。例例如如用用高高射射炮炮射射击击敌敌机机，当当敌敌机机飞飞越越高高射射炮炮射射击击有有效效区区域域的的时时间间为为t t时时，若若在在这这个个时时间间内未被击落，也就不可能再被击落了。内未被击落，也就不可能再被击落了。不难注意到，损失制和等待制可看成是不难注意到，损失制和等待制可看成是混合制的特殊情形，如记混合制的特殊情形，如记c c为系统中服务台的为系统中服务台的个数，则当个数，则当K=cK=c 时，混合制即成为损失制；时，混合制即成为损失制；当当K=K=时，混合制即成为等待制。时，混合制即成为等待制。2 2.排队规则排队规则213 3.服务机构服务机构 1 1）服服务务机机构构可可以以是是单单服服务务员员和和多多服服务务员员服服务务，这这种种服服务务形形式式与与队队列列规规则则联联合合后后形形成成了了多多种种不不同同队队列列，不不同同形形式式的的排排队队服服务务机机构构。如如前前图图8-18-1到到8-8-5 5：2)2)服务方式分为单个顾客服务和成批顾客服务。服务方式分为单个顾客服务和成批顾客服务。3)3)服务时间分为确定型和随机型。服务时间分为确定型和随机型。4)4)服务时间的分布在这里我们假定是平稳的。服务时间的分布在这里我们假定是平稳的。22 上述特征中最主要的、影响最大的是：上述特征中最主要的、影响最大的是：顾客相继到达的间隔时间分布顾客相继到达的间隔时间分布服务时间的分布服务时间的分布服务台数服务台数 D.G.KendallD.G.Kendall，19531953提出了分类法，称为提出了分类法，称为KendallKendall记号记号(适用于并列服务台适用于并列服务台)即：即：X/Y/Z:d/e/fX/Y/Z:d/e/f二、排队系统的描述符号与模型分类二、排队系统的描述符号与模型分类二、排队系统的描述符号与模型分类二、排队系统的描述符号与模型分类23式中：式中：X顾客相继到达间隔时间分布。顾客相继到达间隔时间分布。M负指数分布负指数分布Markov，D确定型分布确定型分布Deterministic，EkK阶爱尔朗分布阶爱尔朗分布Erlang，GI 一般相互独立随机分布一般相互独立随机分布(GeneralIndependent)，G 一般随机分布。一般随机分布。Y填写服务时间分布（与上同）填写服务时间分布（与上同）Z填写并列的服务台数填写并列的服务台数d排队系统的最大容量排队系统的最大容量e顾客源数量顾客源数量 f排队规则排队规则 如如 M/M/1M/M/1:/FCFS/FCFS/FCFS/FCFS即即为为顾顾客客到到达达为为泊泊松松过过程程，服服务务时时间间为为负负指指数数分分布布，单单台台，无无限限容容量量，无无限源，先到先服务的排队系统模型。限源，先到先服务的排队系统模型。24 三三 、排队论研究的基本问题排队论研究的基本问题 1.1.排排队队系系统统的的统统计计推推断断:即通过对排队系统主要参数的统计推断和对排队系统的结构分析，判断一个给定的排队系统符合于哪种模型，以便根据排队理论进行研究。2.2.系系统统性性态态问问题题:即研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布和忙期分布等统计指标,包括了瞬态和稳态两种情形。3.3.最最优优化化问问题题：即包括最最优优设设计计(静态优化)，最优设计是指在一定质量指标下要求机构最经济，如输入结构与服务系统的最优设计，排队规则的最优设计等。最最优优运运营营（动态优化），最优运营是指对给定的系统，如何经营可使目标函数达到最优值。25排队问题求解排队问题求解(主要指性态问题主要指性态问题)求求解解一一般般排排队队系系统统问问题题的的目目的的主主要要是是通通过过研研究究排排队队系系统统运运行行的的效效率率指指标标，估估计计服服务务质质量量，确确定定系系统统的的合合理理结结构构和和系系统统参参数数的的合合理理值值，以以便便实实现现对对现现有有系统合理改进和对新建系统的最优设计等。系统合理改进和对新建系统的最优设计等。排队问题的一般步骤：排队问题的一般步骤：1 1.确确定定或或拟拟合合排排队队系系统统顾顾客客到到达达的的时时间间间间隔隔分分布和服务时间分布布和服务时间分布(可实测可实测)。2 2.研究分析排队系统理论分布的概率特征。研究分析排队系统理论分布的概率特征。3 3.研研究究系系统统状状态态的的概概率率。系系统统状状态态是是指指系系统统中中顾顾客客数数。状状态态概概率率用用P Pn n(t)(t)表表示示,即即在在t t时时刻刻系系统统中中有有n n个顾客的概率，也称瞬态概率。个顾客的概率，也称瞬态概率。26 求解状态概率求解状态概率P Pn n(t)(t)方法是建立含方法是建立含P Pn n(t)(t)的微分差的微分差分方程，通过求解微分差分方程得到系统瞬态解，由分方程，通过求解微分差分方程得到系统瞬态解，由于瞬态解一般求出确定值比较困难，即便求得一般也于瞬态解一般求出确定值比较困难，即便求得一般也很难使用。因此常常使用它的极限很难使用。因此常常使用它的极限(如果存在的话如果存在的话)：稳态的物理意义图，系稳态的物理意义图，系统的稳态一般很快都能统的稳态一般很快都能达到，但实际中达不到达到，但实际中达不到稳态的现象也存在。要稳态的现象也存在。要注意的是求稳态概率注意的是求稳态概率P Pn n并不一定求并不一定求t的极限的极限,只需求只需求P Pn n(t)=0(t)=0。过渡状态 稳定状态 pn t 图3 排队系统状态变化示意图 称为稳态称为稳态(steady state)steady state)解，解，或称统计平衡状态或称统计平衡状态 (Statistical Equilibrium State)Statistical Equilibrium State)的解的解。27 4 4.根据排队系统对应的理论模型根据排队系统对应的理论模型求用以判断系求用以判断系统运行优劣的基本数量指标的概率分布或特征数。统运行优劣的基本数量指标的概率分布或特征数。数量指标主要包括数量指标主要包括:(1)(1)平均队长（平均队长（L Ls s）:系统中的顾客数。系统中的顾客数。平均队列长（平均队列长（L Lg g）:系统中排队等待服务的顾客数。系统中排队等待服务的顾客数。系统中顾客数系统中顾客数L Ls s=系统中排队等待服务的顾客数系统中排队等待服务的顾客数L Lg g+正被正被服务的顾客数服务的顾客数c c(2)(2)平均逗留时间平均逗留时间(Ws):(Ws):指一个顾客在系统中的停留时间。指一个顾客在系统中的停留时间。平均等待时间平均等待时间(Wg):(Wg):一个顾客在系统中排队等待的时间。一个顾客在系统中排队等待的时间。(3)(3)忙期：指从顾客到达空闲服务机构起到服务机构再次为空忙期：指从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度。（忙期和一个忙期中平均完成服务顾客数闲这段时间长度。（忙期和一个忙期中平均完成服务顾客数都是衡量服务机构效率的指标，忙期关系到工作强度）都是衡量服务机构效率的指标，忙期关系到工作强度）5.5.排队系统指标优化排队系统指标优化 含优化设计与优化运营（见含优化设计与优化运营（见2525页）。页）。问题问题1 1 系统中顾客数系统中顾客数=平均队长（平均队长（L Ls s）+1+1？28四、四、排队论主要知识点排队论主要知识点排队系统的组成与特征排队系统的组成与特征排队系统的模型分类排队系统的模型分类顾客到达间隔时间和服务时间的经验分布与顾客到达间隔时间和服务时间的经验分布与理论分布理论分布稳态概率稳态概率P Pn n的计算的计算标准的标准的M/M/1M/M/1模型模型(M/M/1:/FCFS)/FCFS)系统容量有限制的系统容量有限制的模型模型M/M/1:N/FCFS/FCFS顾客源有限模型顾客源有限模型M/M/1/M/M/FCFSFCFS标准的标准的M/M/CM/M/C模型模型M/M/C:/FCFS/FCFS 29M/M/C型系统和型系统和C个个M/M/1型系统型系统系统容量有限制的多服务台模型系统容量有限制的多服务台模型(M/M/C/N/)顾客源为有限的顾客源为有限的多服务台模型多服务台模型(M/M/C/M)(M/M/C/M)一般服务时间的（一般服务时间的（M/G/1M/G/1）模型模型Pollaczek-Khintchine(P-K)公式公式定长服务时间定长服务时间 M/D/1M/D/1模型模型爱尔朗服务时间爱尔朗服务时间M/Ek/1模型模型排队系统优化排队系统优化M/M/1 模型中的最优服务率模型中的最优服务率u标准的标准的M/M/1Model系统容量为系统容量为N的情形的情形M/M/C模型中最优服务台数模型中最优服务台数C308-3 8-3 到达间隔时间分布和服务时间到达间隔时间分布和服务时间的分布的分布 一一个个排排队队系系统统的的最最主主要要特特征征参参数数是是顾顾客客的的到到达达间间隔隔时时间间分分布布与与服服务务时时间间分分布布。要要研研究究到到达达间间隔隔时时间间分分布布与与服服务务时时间间分分布布需需要要首首先先根根据据现现存存系系统统原原始始资资料料统统计计出出它它们们的的经经验验分分布布，然然后后与与理理论论分分布布拟拟合合，若若能能照照应应，我我们们就就可可以以得得出出上上述述的的分布情况。分布情况。31一、经验分布一、经验分布 经验分布是对排队系统的某些时间参数根据经验分布是对排队系统的某些时间参数根据经验数据进行统计分析，并依据统计分析结果假经验数据进行统计分析，并依据统计分析结果假设其统计样本的总体分布，选择合适的检验方法设其统计样本的总体分布，选择合适的检验方法进行检验，当通过检验时，我们认为时间参数的进行检验，当通过检验时，我们认为时间参数的经验数据服从该假设分布。经验数据服从该假设分布。分布的拟合检验一般采用分布的拟合检验一般采用2检验。由数理统检验。由数理统计的知识我们知：若样本量计的知识我们知：若样本量n充分大充分大(n50)，则则当假设当假设H0为真时，统计量总是近似地服从自由度为真时，统计量总是近似地服从自由度为为k-r-1的的2分布，其中分布，其中k为分组数，为分组数，r为检验分布为检验分布中被估计的参数个数。中被估计的参数个数。32式中：式中：fi实际频数实际频数 ni理论频数理论频数 上面方法的应用必须注意上面方法的应用必须注意n要要足够大，足够大，npi不能太不能太小。一般地小。一般地n要大于要大于50，而分组的，而分组的npi应不小于应不小于5。例例题题：某某公公共共汽汽车车站站，统统计计来来站站的的乘乘客客流流，规规定定每每隔隔1 1分分钟钟统统计计一一次次乘乘客客到到达达情情况况，共共统统计计100100次次，其其结果如表所示，问顾客是否服从普阿松流。结果如表所示，问顾客是否服从普阿松流。当当 时，在显著水平时，在显著水平 下接受假设下接受假设H H0 033 解：先估计分布的参数解：先估计分布的参数，由极大似然估计法得：由极大似然估计法得：,并根据公式并根据公式 可计算出理论频率、理论频数及项可计算出理论频率、理论频数及项 见下页表所示见下页表所示 查表知查表知:故可接受泊松分布假设。故可接受泊松分布假设。34=6.2815=6.2815 K-r-1=K-r-1=8-1-18-1-135随机变量随机变量 数数 随着实验的结果的不同而变化随着实验的结果的不同而变化 离散型：离散型：的所有可能只有限或至多可列个的所有可能只有限或至多可列个 连续型：连续型：（）取值于某个区间（）取值于某个区间（a a，b b）分布函数分布函数(连续连续):):的概率分布的概率分布(离散):i=1,2,3二、二、概率论知识复习概率论知识复习36 数学期望数学期望:(离散)E()=(连续)E()=方差方差:=条件概率条件概率:密度函数密度函数:(连续),37三、三、理论分布理论分布 式中式中为常数为常数(0)0)，称，称X X服从参数为服从参数为的泊松分布，的泊松分布，若在上式中引入时间参数若在上式中引入时间参数t t，即令即令tt代替代替，则有：则有：1.泊松分布泊松分布 在概率论中，我们曾学过泊松分布，设随机变在概率论中，我们曾学过泊松分布，设随机变量为量为X，则有：则有：n=0,1,2,（1）与与时时间间有有关关的的随随机机变变量量的的概概率率，是是一一个个随随机机过过程程，即即泊松过程泊松过程。t0，n=0,1,2,（2）38（t2t1，n0）若若设设N(t)N(t)表表示示在在时时间间区区间间0,t)0,t)内内到到达达的的顾顾客客数数(t0),P(t0),Pn n(t(t1 1,t,t2 2)表表示示在在时时间间区区间间tt1 1,t,t2 2)(t)(t2 2tt1 1)内内有有n(0)n(0)个顾客到达的概率。即：个顾客到达的概率。即：在在一一定定的的假假设设条条件件下下 顾顾客客的的到到达达过过程程就就是是一个泊松过程。一个泊松过程。当当P Pn n(t(t1 1,t,t2 2)符合下述三个条件时，顾客到达过程符合下述三个条件时，顾客到达过程就是泊松过程就是泊松过程(顾客到达形成普阿松流顾客到达形成普阿松流)。39 无后效性：无后效性：各区间的到达相互独立各区间的到达相互独立,即即MarkovMarkov性。性。也就是说过程在也就是说过程在t+tt+t所处的状态与所处的状态与t t以前所处的状以前所处的状态无态无关。关。平稳性：平稳性：即对于足够小的即对于足够小的tt，有：有：普阿松流具有如下特性：普阿松流具有如下特性：在在t,t+tt,t+t内有一个顾客到达的概率与内有一个顾客到达的概率与t t无关无关,而与而与tt成正比。成正比。40 普普通通性性：对对充充分分小小的的t,t,在在时时间间区区间间（t,t+tt）内有内有2 2个或个或2 2个以上顾客到达的概率是一高阶无穷小个以上顾客到达的概率是一高阶无穷小.由此知，在由此知，在(t，t+t)t)区间内没有顾客到达的概率为：区间内没有顾客到达的概率为：令令t1 1=0,t=0,t2 2=t,=t,则则P(tP(t1 1,t,t2 2)=P)=Pn n(0,t)=P(0,t)=Pn n(t)(t)0 0 是常数，它是常数，它表示单位时间到达的顾客数，称表示单位时间到达的顾客数，称为概率强度。为概率强度。即即 P P0 0+P+P1 1+P+P22=1=141 在在00，t+tt+t内到达内到达n n个顾客应是上面三种互不相个顾客应是上面三种互不相容的情况之一，所以有：容的情况之一，所以有：为了求为了求Pn(t),即即Pn(0,t)，需要研究它在（需要研究它在（t，t+tt）上的改变量上的改变量,建立建立P Pn n(t)(t)的微分方程。对于区间的微分方程。对于区间0,0,t+t)+t)可以分成可以分成00，t)t)和和tt，t+t),t+t),其到达总数是其到达总数是n n，不外有下列三种情况：不外有下列三种情况：42令令t0t0取极限（并注意初始条件）得：取极限（并注意初始条件）得：(3)(3)当当n=0时，没有时，没有B，C两种情况，则：两种情况，则：(4)(4)凑微分凑微分43 C C =0=0（3 3）式两端乘）式两端乘e e t t并移项得：并移项得：(5(5)（没有顾客到达的概率）（没有顾客到达的概率）两边积分得：两边积分得：代入初始条件代入初始条件(t=0)t=0)有有：P P0 0(0)=1(0)=144将将n=1,2,3代入（代入（6）得：）得：(6)(6)(注意利用注意利用(5)式式)凑成凑成P Pn n(t)e(t)e t t两两项项乘积的微分乘积的微分 两边积分两边积分45 如此继续递推下去得：如此继续递推下去得：（2 2个顾客到达的概率）个顾客到达的概率）（n n个顾客到达的概率）个顾客到达的概率）即随机变量即随机变量N(t)=n服从泊松分布。它的数学期望服从泊松分布。它的数学期望和方差为：和方差为：（1 1个顾客到达的概率）个顾客到达的概率）46 级数级数令令k=n-1，则：则：47 即即：同理方差为：同理方差为：顾客到达过程是一个顾客到达过程是一个泊松过程泊松过程(泊松流泊松流)。48其概率密度函数为：其概率密度函数为：t0t0 2.2.负指数分布负指数分布 当当输输入入过过程程是是泊泊松松流流时时，我我们们研研究究两两顾顾客客相相继继到到达的时间间隔的概率分布。达的时间间隔的概率分布。设设T T为时间间隔，分布函数为为时间间隔，分布函数为F FT T（t t），），则：则：F FT T（t t）=PTt=PTt 此此概概率率等等价价于于在在00，t t）区区间间内内至至少少有有1 1个个顾顾客客到到达的概率。达的概率。t0t0 没有顾客到达的概率没有顾客到达的概率为：为：(由（由（5）式而来）式而来)49 表示单位时间内顾客平均到达数。表示单位时间内顾客平均到达数。1/表示顾客到达的平均间隔时间。表示顾客到达的平均间隔时间。可可以以证证明明，间间隔隔时时间间T T独独立立且且服服从从负负指指数数分分布布与与顾客到达形成泊松流是等价的。顾客到达形成泊松流是等价的。对对顾顾客客的的服服务务时时间间：系系统统处处于于忙忙期期时时两两顾顾客客相相继继离离开系统的时间间隔开系统的时间间隔，一般地也服从负指数分布，设：，一般地也服从负指数分布，设：即即T服从负指数分布，它的期望及方差为：服从负指数分布，它的期望及方差为：接受服务，然后离开接受服务，然后离开服务时间的分布：服务时间的分布：50其中：其中：表示单位时间内能被服务的顾客数，即平均表示单位时间内能被服务的顾客数，即平均 服务率。服务率。1/1/表示一个顾客的平均服务时间。表示一个顾客的平均服务时间。3.3.爱尔朗爱尔朗(Erlang)(Erlang)分布分布 设设v v1 1,v v2 2，,v vk k是是k k个个独独立立的的随随机机变变量量，服服从从相相同同参数参数 k k 的负指数分布，那么：的负指数分布，那么：，则，则令令 ，则，则称为服务强度称为服务强度。51 串列串列k k个服务台个服务台，每台服务时间相互独立，服从，每台服务时间相互独立，服从相同负指数分布（参数相同负指数分布（参数k k），），那么一顾客走完那么一顾客走完k k个个服务台总共所需要服务时间服从上述服务台总共所需要服务时间服从上述k k阶阶ErlangErlang分布。分布。则称则称T服从服从k阶阶爱尔朗分布。其特征值为：爱尔朗分布。其特征值为：,其概率密度是其概率密度是1/k1/k表示一个顾客一个服务台的平均服务时间。表示一个顾客一个服务台的平均服务时间。52 例例:有有易易碎碎物物品品500500件件,由由甲甲地地运运往往乙乙地地,根根据据以以往往统统计计资资料料,在在运运输输过过程程中中易易碎碎物物品品按按普普阿阿松松流流发发生生破破碎碎,其其概概率率为为0.002,0.002,现现求求:1.:1.破破碎碎3 3件件物物品品的的概概率率;2.;2.破破碎碎少少于于3 3件件的的概概率率和和多多于于3 3件件的的概概率率;3.;3.至至少有一件破损的概率少有一件破损的概率.解解:=0.002500=1 1 1破碎破碎3 3件物品的概率为件物品的概率为:P(k=3)=(P(k=3)=(3 3/3/3！)e)e-=(1=(13 3/3/3！)e)e-1-1=0.0613=0.0613 即物品破碎即物品破碎3 3件的概率为件的概率为6.136.13 2.2.破碎物品少于破碎物品少于3 3件的概率件的概率:53 破碎物品少于破碎物品少于3 3件的概率为件的概率为91.9791.97 破碎物品多于破碎物品多于3 3件的概率为件的概率为:3.3.至少有一件破碎的概率为至少有一件破碎的概率为 PkPk 1=1-(11=1-(1k k/k!)e/k!)e-=1-(1=1-(10 0/0!)e/0!)e-1-1=0.632=0.63254 对对排排队队模模型型，在在给给定定输输入入和和服服务务条条件件下下，主主要要研究系统的下述运行指标：研究系统的下述运行指标：(1)(1)系系统统的的平平均均队队长长LsLs(期期望望值值)和和平平均均队队列列长长LqLq(期望值期望值)；(2)(2)系系统统中中顾顾客客平平均均逗逗留留时时间间WsWs与与队队列列中中平平均均等等待时间待时间WqWq；本节只研究本节只研究M/M/1M/M/1模型，下面分三种情况讨论：模型，下面分三种情况讨论：8-5 M/M/1 8-5 M/M/1 无限源系统无限源系统55一、标准的一、标准的M/M/1M/M/1模型模型 系统中有系统中有n n个顾客个顾客M/M/1:/FCFS/FCFS模型模型 1.1.稳态概率稳态概率P Pn n的计算的计算 在任意时刻在任意时刻t t，状态为状态为n n的概率的概率P Pn n(t(t)（瞬态概率），瞬态概率），它决定了系统的运行特征。它决定了系统的运行特征。已知顾客到达服从参数为已知顾客到达服从参数为的泊松过程，服务时的泊松过程，服务时间服从参数为间服从参数为的负指数分布。现仍然通过研究区间的负指数分布。现仍然通过研究区间 t，t+tt）的变化来求解。在时刻的变化来求解。在时刻t+tt，系统中有系统中有n n个个顾客不外乎有下列四种情况（顾客不外乎有下列四种情况（t，t+tt）内到达或内到达或离开离开2 2个以上个以上没列入）。没列入）。？56 由于这四种情况是互不相容的，所以由于这四种情况是互不相容的，所以Pn(t+t)t)应应是这四项之和，则有：是这四项之和，则有：57令令t0t0，得关于得关于P Pn n(t)(t)的微分差分方程：的微分差分方程：(1)当当n=0时，只有表中的（时，只有表中的（A）、（）、（B）两种情况，两种情况，因为在较小的因为在较小的tt内不可能发生（内不可能发生（D D）（）（到达后即离到达后即离去），若发生可将去），若发生可将tt取小即可。取小即可。58 (2)(2)这这种种系系统统状状态态(n)随随时时间间变变化化的的过过程程就就是是生生灭灭过程（过程（Birth and Death Process）。）。方程方程(1)、(2)解是瞬态解解是瞬态解,无法应用。无法应用。它它对对时时间的导数为间的导数为0，所以由，所以由(1)、(2)两式得：两式得：稳态时，稳态时，Pn(t)与时间无关与时间无关,可以写成可以写成Pn,(3)(3)(4)(4)59由此可得该排队系统的状态转移图：由此可得该排队系统的状态转移图：由（由（4）得：）得：其中其中服务强度服务强度 将其代入（将其代入（3）式并令）式并令n=1,2,(也可从状态转移也可从状态转移图中看出状态平衡方程图中看出状态平衡方程)得：得：(3)(3)(4)(4)n-1n-1 n n n+1n+1 2 2 0 0 1 1 状态转移图状态转移图60 n=1n=1 n=2n=2 61以此类推以此类推，当，当n=n时，时，(5)(5)及概率性质知：及概率性质知：(数列的极限为数列的极限为 )(6)(6)否则排队无限远否则排队无限远系统系统稳态稳态概率概率系统的运行指标系统的运行指标622.系统的运行指标计算系统的运行指标计算 (1)系统中的队长系统中的队长Ls（平均队长）平均队长）(01)即即:(7)(7)期望期望63(2)队列中等待的平均顾客数队列中等待的平均顾客数Lq(8)(8)(3)顾客在系统中的平均逗留时间顾客在系统中的平均逗留时间Ws 顾顾客客在在系系统统中中的的逗逗留留时时间间是是随随机机变变量量，可可以以证证明，它服从参数为明，它服从参数为-的负指数分布，分布函数的负指数分布，分布函数64 和密度函数为：和密度函数为：（w00）(4)(4)顾客在队列中的平均逗留时间顾客在队列中的平均逗留时间W Wq q 顾客在队列中的平均逗留时间应为顾客在队列中的平均逗留时间应为W Ws s减去平均服减去平均服务时间。务时间。考虑考虑L LS S与与W WS S的的关关系系65四个指标的关系为四个指标的关系为(Little Little 公式公式)：3.系统的忙期与闲期系统的忙期与闲期系统处于空闲状态的概率：系统处于空闲状态的概率：系统处于繁忙状态的概率：系统处于繁忙状态的概率：服服务务强强度度66 在繁忙状态下，队列中的平均顾客数在繁忙状态下，队列中的平均顾客数L Lb b：顾客平均等待时间顾客平均等待时间:忙期的平均长度忙期的平均长度:(由由 来来)一个忙期平均服务顾客数为：一个忙期平均服务顾客数为：L Lb bPP(N0)(N0)=L Lq q678-6 8-6 系统容量有限制的系统容量有限制的系统容量有限制的系统容量有限制的模型模型模型模型 M/M/1M/M/1：NN/FCFS/FCFS/FCFS/FCFS 当当系系统统容容量量最最大大为为N N时时，排排队队多多于于N N个个的的顾顾客客将将被被拒拒绝绝。当当N=1N=1时时，即即为为瞬瞬时时制制，NN时时，即即为为容容量量无限制的情况。无限制的情况。68 现在研究系统中有现在研究系统中有n n个顾客的概率个顾客的概率P Pn n(t(t)。(2)(2)对于对于(1)(1)式，当式，当n=1,2,N-1n=1,2,N-1时，仍能成立。时，仍能成立。(1)(1)(n=1,2,N-1)(n=1,2,N-1)但当但当n=Nn=N时，有下面两种情况：时，有下面两种情况：对于对于P P0 0(t)(t)，前面的（前面的（2 2）式仍然成立。）式仍然成立。69(8)(8)0N-112N-2N70在稳态情况下有：在稳态情况下有：(9)(9)解（解（9）式得：）式得：而等比数列而等比数列71(1,(1,nN)(10)nN)(10)注：当注：当=1=1时，试讨论其概率时，试讨论其概率P Pn n。(1)平均平均队长队长Ls：(1)试证试证=1=1时时,Ls=N/2,Ls=N/2其运行指标：其运行指标：72 (2)有效到达率有效到达率e 系系统统容容量量有有限限，当当满满员员时时，顾顾客客将将被被拒拒绝绝，实实际际的顾客到达率与的顾客到达率与不一样，不一样，还可验证：还可验证：此种情况的公式与此种情况的公式与前类似前类似,只有只有Ls不同不同,e与与 不同。求不同。求e必须必须先求得先求得P0或或PN才行。才行。有效到达率为有效到达率为e。可以证明：可以证明：LsLs73例例2某某单单人人理理发发馆馆共共有有六六把把椅椅子子接接待待顾顾客客排排队队，无无座座时时将将离离去去，顾顾客客平平均均到到达达率率为为3人人/h，理理发发时时间间平平均为均为15分钟，求：分钟，求：(1)求某一顾客到达就能理发的概率求某一顾客到达就能理发的概率;(2)求需要等待的顾客数的期望值求需要等待的顾客数的期望值;(3)求有效到达率求有效到达率;(4)求求一一顾顾客客在在系系统统中中的的逗逗留留时时间间和和排排队队时时间间平均值平均值;(5)在在可可能能到到来来的的顾顾客客中中，有有百百分分之之几几不不等等待待就离开？就离开？解：解：N=6+1=7，=3=3，=4=474(1)求某一顾客到达就能理发的概率求某一顾客到达就能理发的概率:(2)求需要等待的顾客数的期望值求需要等待的顾客数的期望值:(3)求有效到达率求有效到达率:(4)求一顾客在系统中的逗留时间和排队时间平均求一顾客在系统中的逗留时间和排队时间平均值值:75P0=0.27780P1=0.20836P2=0.15627P3=0.11720 =0.9629=96.29%P4=0.08790 故拒绝的概率为故拒绝的概率为3.71%P5=0.06593P6=0.04944(5)在在可可能能到到来来的的顾顾客客中中，有有百百分分之之几几不不等等待待就就离离开开？768-7 顾客源有限的模型顾客源有限的模型 M/M/1/m/m 以以机机器器修修理理模模型型为为例例，设设有有m台台机机器器(总总体体)，故故障障待待修修表表示示机机器器到到达达，修修理理工工是是服服务务员员。机机器器修修好好后后有有可可能能再再坏坏，形形成成循循环环。虽虽然然系系统统没没有有容容量量限限制制，但但系系统统中中的的顾顾客客也也不不会会超超过过m，故故又又可可写写成成：M/M/1/m/mm/m77 对于有限源应按每个顾客单独考虑，求出其有效对于有限源应按每个顾客单独考虑，求出其有效到达率到达率e。这样这样e是随系统内顾客数而变化的。其状态转是随系统内顾客数而变化的。其状态转移图为：移图为：设系统内顾客数为设系统内顾客数为Ls，则系统外的顾客为则系统外的顾客为m-Ls。设每个顾客的平均到达率是相同的设每个顾客的平均到达率是相同的。(这里这里的含义是单台机器在单位时间里发生故的含义是单台机器在单位时间里发生故障的概率或平均次数障的概率或平均次数)78由状态转移图可得状态转移方程：由状态转移图可得状态转移方程：1nm-1 0 0状态状态 n n状态状态 m m状态状态 用递推方法解此差分方程，并注意条件，用递推方法解此差分方程，并注意条件，可以得到如下公式：可以得到如下公式：10=miiP(1nm)79各项运行指标为：各项运行指标为：例例3 某车间有某车间有5台机器，每台机器的连续运转时间服从负指数台机器，每台机器的连续运转时间服从负指数分布。平均连续运转时间分布。平均连续运转时间15分钟，有一个修理工，修理时间分钟，有一个修理工，修理时间服从负指数分布，平均每次服从负指数分布，平均每次12分钟。求：分钟。求：(1)修理工空闲时间修理工空闲时间80解解:(1)m=5,=1/15,=1/12,=4/5=0.8 m=5,=1/15,=1/12,=4/5=0.8(2)五台机器都出现故障的概率五台机器都出现故障的概率81 台台 台台(3)出故障的平均台数出故障的平均台数(4)等待修理的平均台数等待修理的平均台数(5)平均停工时间平均停工时间 分钟分钟82 分钟分钟 机器等待过长，忙期长，应增加维修工人机器等待过长，忙期长，应增加维修工人或提高效率。或提高效率。(6)平均等待修理时间平均等待修理时间(7)评价这些结果评价这些结果83 1.标准的标准的M/M/C模型模型8-8 多服务台负指数分布排队系统分析多服务台负指数分布排队系统分析当nc时，Pn=/(n)Pn-1当nc时，Pn=/(c)Pn-1标准的标准的 M/M/CM/M/C模型个特征规定同模型个特征规定同M/M/1M/M/1。另外。另外规定各服务台工作相互独立且平均服务率相同规定各服务台工作相互独立且平均服务率相同1 1=2 2=3 3=c c =整个服务机构的平均服务率为整个服务机构的平均服务率为c(nc(n c c););n n(n(n cncn c同理考虑同理考虑n转移转移n-1 的情况。的情况。n c时，时，转移率为转移率为np nnc时，有时，有c个服务台，最多有个服务台，最多有c个个顾客被服务顾客被服务,n-c个等待，则这时状态转移率为个等待，则这时状态转移率为cpn85用递推法解上差分方程，用递推法解上差分方程，可求得状态概率：可求得状态概率：86M/M/C 无限源系统无限源系统系统运行指标求得如下：87例例:某火车站售票处有三个窗口，同时某火车站售票处有三个窗口，同时售各车次的车票。顾客到达服从泊松布，售各车次的车票。顾客到达服从泊松布，平均每分钟到达平均每分钟到达=0.9（人），服务时人），服务时间服从负指数分布，平均服务率间服从负指数分布，平均服务率=24（人人/h），），分两种情况：分两种情况：1.顾客排成一队，依次购票；顾客排成一队，依次购票；2.顾客在每个窗口排一队，不准串队。顾客在每个窗口排一队，不准串队。求求:（1）售票处空闲的概率。）售票处空闲的概率。（2）队长和队列长。）队长和队列长。例例 题题 解解 析析（3 3）平均等待时间和逗留时间。）平均等待时间和逗留时间。88例例 题题 解解 析析 解：解：1.M/M/3/=0.4（人人/分钟）分钟）记记=/=/（33）=0.75=0.75本题属于？本题属于？n n c c 则（则（1 1）售票处空闲的概率为：）售票处空闲的概率为：89例例 题题 解解 析析 解：解：1.M/M/3/（2 2）队长和队列长：）队长和队列长：90例例 题题 解解 析析售票处的空闲的概率为售票处的空闲的概率为0.07480.0748平均等待时间平均等待时间 W W q q=1.89=1.89分钟，分钟，平均逗留时间平均逗留时间 W W s s=4.39=4.39分钟分钟队长队长 L L s s=3.95(=3.95(人人)L L q q=1.70(=1.70(人人)91 2.2.相当于相当于3 3个个M/M/1/M/M/1/三个系统并联：三个系统并联：=0.3 =0.4 =/=0.75=0.3 =0.4 =/=0.75P P0 0=1-=0.25=1-=0.25 （每个子系统）三个服务台都有空的时候，P03=0.0156Ls=/(1-)=3(子系统）整个系统为9 Lq=Ls-/=2.25（每个子系统）W Ws s=L=Ls s/=10 /=10 W Wq q=W=Ws s-1/=7.5-1/=7.5例例 题题 解解 析析92故售票处空闲的概率为故售票处空闲的概率为 0.01560.0156例例 题题 解解 析析平均等待时间平均等待时间 W Wq q=7.5=7.5分钟分钟 平均逗留时间平均逗留时间 W Ws s=10=10分钟分钟队长队长 L Ls s=3 =3 三个队三个队 共共3+3+3=93+3+3=9队列长队列长 L Lq q=2.25 =2.25 共共6.756.75（人）（人）相比之下，排一队共享三个服务台效率好相比之下，排一队共享三个服务台效率好93