1、12 排队论（排队论（queuing),也称随机服务系统理论，是也称随机服务系统理论，是运筹学的一个主要分支。运筹学的一个主要分支。1909年，丹麦哥本哈根电子公司电话工程师年，丹麦哥本哈根电子公司电话工程师A.K.Erlang的开创性论文的开创性论文“概率论和电话通讯理论概率论和电话通讯理论”标志此理论的诞生。排队论的发展最早是与电话，标志此理论的诞生。排队论的发展最早是与电话，通信中的问题相联系的，并到现在是排队论的传统通信中的问题相联系的，并到现在是排队论的传统的应用领域。近年来在计算机通讯网络系统的应用领域。近年来在计算机通讯网络系统、交通、交通运输、医疗卫生系统、库存管理、作战指挥等
2、各领运输、医疗卫生系统、库存管理、作战指挥等各领域中均得到应用。域中均得到应用。38 排队论排队论 8-1 前言前言 8-2 基基 本本 概概 念念 8-3 输入过程和服务时间分布输入过程和服务时间分布 8-4 泊松输入泊松输入指数服务排队模型指数服务排队模型 8-5 M/M/1 无限源系统无限源系统 8-6 系统容量有限的排队系统系统容量有限的排队系统 8-7 顾客源有限的排队系统顾客源有限的排队系统4 排队是我们在日常生活和生产中经排队是我们在日常生活和生产中经常遇到的现象。常遇到的现象。例如，上、下班搭乘公共汽车；例如，上、下班搭乘公共汽车；顾客到商店购买物品；顾客到商店购买物品；病员到
3、医院看病；病员到医院看病；旅客到售票处购买车票；旅客到售票处购买车票；学生去食堂就餐等就常常出现排队和等学生去食堂就餐等就常常出现排队和等待现象。待现象。前前 言言5 除了上述有形的排队之外，还有大量除了上述有形的排队之外，还有大量的所谓的所谓“无形无形”排队现象。排队现象。如几个顾客打电话到出租汽车站要求如几个顾客打电话到出租汽车站要求派车，如果出租汽车站无足够车辆、则派车，如果出租汽车站无足够车辆、则部分顾客只得在各自的要车处等待，他部分顾客只得在各自的要车处等待，他们分散在不同地方，却形成了一个无形们分散在不同地方，却形成了一个无形队列在等待派车。队列在等待派车。前前 言言6 排队的不一
4、定是人，也可以是物：排队的不一定是人，也可以是物：例如，通讯卫星与地面若干待传递的例如，通讯卫星与地面若干待传递的信息；信息；生产线上原料、半成品等待加工；生产线上原料、半成品等待加工；因故障停止运转的机器等待修理；码头因故障停止运转的机器等待修理；码头的船只等待装卸货物；的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘要降落的飞机因跑道不空而在空中盘旋等等。旋等等。前前 言言7 上述各种问题虽互不相同，但却都有上述各种问题虽互不相同，但却都有要求得到某种服务的人或物和提供服务要求得到某种服务的人或物和提供服务的人或机构。的人或机构。排队论里把要求服务的对象统称为排队论里把要求服务的对象统
5、称为“顾顾客客”,提供服务的人或机构称为提供服务的人或机构称为“服务台服务台”或或“服务员服务员”。前前 言言8 不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图8-1至图8-5。图图8-1 8-1 单服务台排队系统单服务台排队系统前前 言言9图图8-2 8-2 单队列单队列S S个服务台并联的排队系统个服务台并联的排队系统图图8-3 S8-3 S个队列个队列S S个服务台的并联排队系统个服务台的并联排队系统前前 言言10图图8-4 8-4 单队单队多个服务台的串联排队系统多个服务台的串联排
6、队系统 图图8-5 8-5 多队多队多服务台混联网络系统多服务台混联网络系统前前 言言11图图8-6 8-6 随机服务系统随机服务系统前前 言言一般的排队系统，都可由下一般的排队系统，都可由下面图加以描述。面图加以描述。12 面对拥挤现象，人们总是希望尽量设法面对拥挤现象，人们总是希望尽量设法减少排队，通常的做法是增加服务设施。减少排队，通常的做法是增加服务设施。但是增加的数量越多，人力、物力的支但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费。出就越大，甚至会出现空闲浪费。如果服务设施太少，顾客排队等待的时如果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响。
7、间就会很长，这样对顾客会带来不良影响。前前 言言13 顾客排队时间的长短与服务设施规模的顾客排队时间的长短与服务设施规模的大小，就构成了设计随机服务系统中的一对大小，就构成了设计随机服务系统中的一对矛盾。矛盾。如何做到既保证一定的服务质量指标，如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾。客排队时间与服务设施费用大小这对矛盾。这就是随机服务系统理论这就是随机服务系统理论排队论所排队论所要研究解决的问题。要研究解决的问题。前前 言言14排队结构服务机构顾客源顾客到达排队规则服务规则离去图1 排
8、队系统示意图 排队系统一般有三个基本组成部分：排队系统一般有三个基本组成部分：1.1.输输入过程；入过程；2.2.排队规则；排队规则；3.3.服务机构。服务机构。15 输入即为顾客的到达，可有下列情况：输入即为顾客的到达，可有下列情况：1）顾客源可能是有限的，也可能是无限的。顾客源可能是有限的，也可能是无限的。2）顾客是成批到达或是单个到达。顾客是成批到达或是单个到达。3）顾客到达间隔时间可能是随机的或确定的。顾客到达间隔时间可能是随机的或确定的。4）顾客到达可能是相互独立或关联的。所谓独顾客到达可能是相互独立或关联的。所谓独立就是以前顾客的到达对以后顾客的到达无影响。立就是以前顾客的到达对以
9、后顾客的到达无影响。5）输入过程可以是平稳的（输入过程可以是平稳的（stationarystationary）或说）或说是对时间齐次的（是对时间齐次的（Homogeneous in timeHomogeneous in time），也可以），也可以是非平稳的。输入过程平稳的指顾客相继到达的间是非平稳的。输入过程平稳的指顾客相继到达的间隔时间分布和参数（均值、方差）与时间无关；非隔时间分布和参数（均值、方差）与时间无关；非平稳的则是与时间相关，非平稳的处理比较困难。平稳的则是与时间相关，非平稳的处理比较困难。16这是指服务台从队列中选取顾客进行服务的顺序。这是指服务台从队列中选取顾客进行服务的顺
10、序。可以分为可以分为损失制、等待制、混合制损失制、等待制、混合制3 3大类。大类。(1)(1)损失制。损失制。这是指如果顾客到达排队系统时，这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。自动离开系统永不再来。典型例子是，如电话拔号后出现忙音，顾客典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为损失制。拔号，这种服务规则即为损失制。17 (2)(2)等待制等待制。指当顾客来到系统时，所有服务台。指当顾客来到系统时
11、，所有服务台都不空，顾客加入排队行列等待服务。都不空，顾客加入排队行列等待服务。例如，排队等待售票，故障设备等待维修等。例如，排队等待售票，故障设备等待维修等。等待制中，服务台在选择顾客进行服务时，常有等待制中，服务台在选择顾客进行服务时，常有如下四种规则：如下四种规则：先到先服务（先到先服务（FCFS FCFS）。按顾客到达的先后顺。按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形。序对顾客进行服务，这是最普遍的情形。后到先服务（后到先服务（LCFSLCFS）。仓库中迭放的钢材，。仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。后迭放上去的都先被领走，就属于这种情况。18 随机
12、服务（随机服务（RAND）。即当服务台空。即当服务台空闲时，不按照排队序列而随意指定某个顾客闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就去接受服务，如电话交换台接通呼叫电话就是一例。是一例。优先权服务（优先权服务（PR）。如老人、儿童先。如老人、儿童先进车站；危重病员先就诊；遇到重要数据需进车站；危重病员先就诊；遇到重要数据需要处理计算机立即中断其他数据的处理等，要处理计算机立即中断其他数据的处理等，均属于此种服务规则。均属于此种服务规则。19 (3)(3)混合制混合制这是等待制与损失制相结合的一这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允
13、许队种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：列无限长下去。具体说来，大致有三种：队长有限。队长有限。当排队等待服务顾客人数超过当排队等待服务顾客人数超过规定数量时，后来顾客就自动离去，另求服务。规定数量时，后来顾客就自动离去，另求服务。如水库的库容、旅馆的床位等都是有限的如水库的库容、旅馆的床位等都是有限的。20 等待时间有限等待时间有限。即顾客在系统中的。即顾客在系统中的等待时间不超过某一给定的长度等待时间不超过某一给定的长度T T，当等待，当等待时间超过时间超过T T时，顾客自动离去，不再回来。时，顾客自动离去，不再回来。如易损坏的电子元器件的库存问题
14、，如易损坏的电子元器件的库存问题，超过一定存储时间被自动认为失效。超过一定存储时间被自动认为失效。又如顾客到饭馆就餐，等了一定时间后又如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。不愿再等而自动离去另找饭店用餐。21 逗留时间逗留时间(等待时间与服务时间之和等待时间与服务时间之和)有限。有限。例如用高射炮射击敌机，当敌机飞越高射例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为炮射击有效区域的时间为t t时，若在这个时时，若在这个时间内未被击落，也就不可能再被击落了。间内未被击落，也就不可能再被击落了。不难注意到，损失制和等待制可看成是不难注意到，损失制和等待制可看成
15、是混合制的特殊情形，如记混合制的特殊情形，如记c c为系统中服务台为系统中服务台的个数，则当的个数，则当K=cK=c 时，混合制即成为损失制；时，混合制即成为损失制；当当K=K=时，混合制即成为等待制。时，混合制即成为等待制。22 1 1）服务机构可以是单服务员和多服务员服务，）服务机构可以是单服务员和多服务员服务，这种服务形式与队列规则联合后形成了多种不同这种服务形式与队列规则联合后形成了多种不同队列，不同形式的排队服务机构。如前图队列，不同形式的排队服务机构。如前图8-18-1到到8-8-5 5：2)2)服务方式分为单个顾客服务和成批顾客服务。服务方式分为单个顾客服务和成批顾客服务。3)3
16、)服务时间分为确定型和随机型。服务时间分为确定型和随机型。4)4)服务时间的分布在这里我们假定是平稳的。服务时间的分布在这里我们假定是平稳的。23 上述特征中最主要的、影响最大的是：上述特征中最主要的、影响最大的是：顾客相继到达的间隔时间分布顾客相继到达的间隔时间分布服务时间的分布服务时间的分布服务台数服务台数 D.G.KendallD.G.Kendall，19531953提出了分类法，称为提出了分类法，称为KendallKendall记号记号(适用于并列服务台适用于并列服务台)即：即：X/Y/Z:d/e/fX/Y/Z:d/e/f24 式中：式中：X顾客相继到达间隔时间分布。顾客相继到达间隔时
17、间分布。M负指数分布负指数分布Markov，D确定型分布确定型分布Deterministic，EkK阶爱尔朗分布阶爱尔朗分布Erlang，GI 一般相互独立随机分布一般相互独立随机分布(General Independent)，G 一般随机分布。一般随机分布。Y填写服务时间分布（与上同）填写服务时间分布（与上同）Z填写并列的服务台数填写并列的服务台数 d排队系统的最大容量排队系统的最大容量 e顾客源数量顾客源数量 f排队规则排队规则 如如 即为顾客到达为泊松过即为顾客到达为泊松过程，服务时间为负指数分布，单台，无限容量，无程，服务时间为负指数分布，单台，无限容量，无限源，先到先服务的排队系统模
18、型。限源，先到先服务的排队系统模型。25 1.1.排队系统的统计推断排队系统的统计推断:即通过对排队系统主要参数的统计推断和对排队系统的结构分析，判断一个给定的排队系统符合于哪种模型，以便根据排队理论进行研究。2.2.系统性态问题系统性态问题:即研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布和忙期分布等统计指标,包括了瞬态和稳态两种情形。3.3.最优化问题：最优化问题：即包括最优设计最优设计(静态优化)，最优设计是指在一定质量指标下要求机构最经济，如输入结构与服务系统的最优设计，排队规则的最优设计等。最优运营最优运营（动态优化），最优运营是指对给定的系统，如何经营可使目标函数达到
19、最优值。26 求解一般排队系统问题的目的主要是通过研究求解一般排队系统问题的目的主要是通过研究排队系统运行的效率指标，估计服务质量，确定系排队系统运行的效率指标，估计服务质量，确定系统的合理结构和系统参数的合理值，以便实现对现统的合理结构和系统参数的合理值，以便实现对现有系统合理改进和对新建系统的最优设计等。有系统合理改进和对新建系统的最优设计等。排队问题的一般步骤：排队问题的一般步骤：1 1.确定或拟合确定或拟合排队系统顾客到达的时间间隔分排队系统顾客到达的时间间隔分布和服务时间分布布和服务时间分布(可实测可实测)。2 2.研究分析排队系统理论分布的概率特征。研究分析排队系统理论分布的概率特
20、征。3 3.研究研究系统状态的概率。系统状态是指系统中系统状态的概率。系统状态是指系统中顾客数。状态概率用顾客数。状态概率用P Pn n(t)(t)表示表示,即在即在t t时刻系统中有时刻系统中有n n个顾客的概率，也称瞬态概率。个顾客的概率，也称瞬态概率。27 求解状态概率求解状态概率P Pn n(t)(t)方法是建立含方法是建立含P Pn n(t)(t)的微分差的微分差分方程，通过求解微分差分方程得到系统瞬态解，由分方程，通过求解微分差分方程得到系统瞬态解，由于瞬态解一般求出确定值比较困难，即便求得一般也于瞬态解一般求出确定值比较困难，即便求得一般也很难使用。因此常常使用它的极限很难使用。
21、因此常常使用它的极限(如果存在的话如果存在的话)：nttnp)(plim 稳态的物理意义图，系稳态的物理意义图，系统的稳态一般很快都能统的稳态一般很快都能达到，但实际中达不到达到，但实际中达不到稳态的现象也存在。要稳态的现象也存在。要注意的是求稳态概率注意的是求稳态概率P Pn n并不一定求并不一定求t的极限的极限,只需求只需求P Pn n(t)=0(t)=0。过渡状态 稳定状态 pn t 图3 排队系统状态变化示意图 称为稳态称为稳态(steady state)steady state)解，解，或称统计平衡状态或称统计平衡状态 (Statistical Equilibrium State)S
22、tatistical Equilibrium State)的解的解。28 4 4.根据排队系统对应的理论模型根据排队系统对应的理论模型求用以判断系求用以判断系统运行优劣的基本数量指标的概率分布或特征数。统运行优劣的基本数量指标的概率分布或特征数。数量指标主要包括数量指标主要包括:(1)(1)平均队长（平均队长（L Ls s）:系统中的顾客数。系统中的顾客数。平均队列长（平均队列长（L Lg g）:系统中排队等待服务的顾客数。系统中排队等待服务的顾客数。系统中顾客数系统中顾客数L Ls s=系统中排队等待服务的顾客数系统中排队等待服务的顾客数L Lg g+正被正被服务的顾客数服务的顾客数c c(
23、2)(2)平均逗留时间平均逗留时间(Ws):(Ws):指一个顾客在系统中的停留时间。指一个顾客在系统中的停留时间。平均等待时间平均等待时间(Wg):(Wg):一个顾客在系统中排队等待的时间。一个顾客在系统中排队等待的时间。(3)(3)忙期：指从顾客到达空闲服务机构起到服务机构再次为忙期：指从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度。（忙期和一个忙期中平均完成服务顾客空闲这段时间长度。（忙期和一个忙期中平均完成服务顾客数都是衡量服务机构效率的指标，忙期关系到工作强度）数都是衡量服务机构效率的指标，忙期关系到工作强度）5.5.排队系统指标优化排队系统指标优化 含优化设计与优化运营（见
24、含优化设计与优化运营（见2525页）。页）。问题问题1 1 系统中顾客数系统中顾客数=平均队长（平均队长（L Ls s）+1+1？29 排队系统的组成与特征排队系统的组成与特征 排队系统的模型分类排队系统的模型分类 顾客到达间隔时间和服务时间的经验分布与顾客到达间隔时间和服务时间的经验分布与理论分布理论分布 稳态概率稳态概率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
25、/C模型模型M/M/C:/FCFS/FCFS 30 M/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/
26、1Model 系统容量为系统容量为N的情形的情形 M/M/C模型中最优服务台数模型中最优服务台数C31 一个排队系统的最主要特征参数是一个排队系统的最主要特征参数是顾客顾客的到达间隔时间分布与服务时间分布的到达间隔时间分布与服务时间分布。要研究到达间隔时间分布与服务时间分要研究到达间隔时间分布与服务时间分布需要首先根据现存系统原始资料统计布需要首先根据现存系统原始资料统计出它们的经验分布，然后与理论分布拟出它们的经验分布，然后与理论分布拟合，若能照应，我们就可以得出上述的合，若能照应，我们就可以得出上述的分布情况。分布情况。32 经验分布是对排队系统的某些时间参数根据经验分布是对排队系统的某些
27、时间参数根据经验数据进行统计分析，并依据统计分析结果假经验数据进行统计分析，并依据统计分析结果假设其统计样本的总体分布，选择合适的检验方法设其统计样本的总体分布，选择合适的检验方法进行检验，当通过检验时，我们认为时间参数的进行检验，当通过检验时，我们认为时间参数的经验数据服从该假设分布。经验数据服从该假设分布。分布的拟合检验一般采用分布的拟合检验一般采用2检验。由数理统检验。由数理统计的知识我们知：若样本量计的知识我们知：若样本量n充分大充分大(n50)，则则当假设当假设H0为真时，统计量总是近似地服从自由度为真时，统计量总是近似地服从自由度为为k-r-1的的2分布，其中分布，其中k为分组数，
28、为分组数，r为检验分布为检验分布中被估计的参数个数。中被估计的参数个数。33 式中：式中：fi实际频数实际频数 ni理论频数理论频数 上面方法的应用必须注意上面方法的应用必须注意n要要足够大，足够大，npi不能太不能太小。一般地小。一般地n要大于要大于50，而分组的，而分组的npi应不小于应不小于5。例题：某公共汽车站，统计来站的乘客流，规定例题：某公共汽车站，统计来站的乘客流，规定每隔每隔1 1分钟统计一次乘客到达情况，共统计分钟统计一次乘客到达情况，共统计100100次，次，其结果如表所示，问顾客是否服从普阿松流。其结果如表所示，问顾客是否服从普阿松流。kiiiinpnpf122)()1(
29、22rk 当当 时，在显著水平时，在显著水平 下接受假设下接受假设H H0 034状 态 i012345678910 11 12实 际 频 数 fi1516 17 26 119921210 解：先估计分布的参数解：先估计分布的参数，由极大似然估计法得：，由极大似然估计法得：2.4x!ieixPi,并根据公式并根据公式 可计算出理论频率、理论频数及项可计算出理论频率、理论频数及项iinpf iiinpnpf2)(见下页表所示见下页表所示2815.6592.12)6()1(05.0rk 查表知查表知:故可接受泊松分布假设。故可接受泊松分布假设。35fipinpifi-npi(fi-npi)2/np
30、i10.0151.550.0636.3-1.80.415160.13213.22.80.594170.18518.5-1.50.122260.19419.46.62.245110.16316.3-5.31.72390.11411.4-2.40.50590.0696.92.10.63920.0363.610.0171.720.0070.710.0030.300.0020.2-0.50.0385=6.2815=6.2815 K-r-1=K-r-1=8-1-18-1-136随机变量随机变量 数数 随着实验的结果的不同而变化随着实验的结果的不同而变化 离散型：离散型：的所有可能只有限或至多可列个的所有
31、可能只有限或至多可列个 连续型：连续型：（）取值于某个区间（）取值于某个区间（a a，b b）分布函数分布函数(连续连续):):xpxF aFbFbap 的概率分布的概率分布(离散):iixpxp i=1,2,311iixp37 数学期望数学期望:(离散)E()=1iiipxdxxxf (连续)E()=方差方差:2EED EE22=BApBpABp 条件概率条件概率:密度函数密度函数:(连续)dttfxFx 0 xf 1dttf,38tnnenttP !)(式中式中为常数为常数(0)0)，称，称X X服从参数为服从参数为的泊松分布，的泊松分布，若在上式中引入时间参数若在上式中引入时间参数t t
32、，即令，即令tt代替代替，则有：，则有：在概率论中，我们曾学过泊松分布，设随机变在概率论中，我们曾学过泊松分布，设随机变量为量为X，则有：，则有：!nenxPn n=0,1,2,（1）与时间有关的随机变量的概率与时间有关的随机变量的概率，是一个，是一个随机过程随机过程，即即泊松过程泊松过程。t0，n=0,1,2,（2）39)()(,1221ntNtNPttPn（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)(t
33、2 2tt1 1)内有内有n(0)n(0)个顾客到达的概率。即：个顾客到达的概率。即：在一定的假设条件下在一定的假设条件下 顾客的到达过程就是顾客的到达过程就是一个泊松过程。一个泊松过程。当当P Pn n(t(t1 1,t,t2 2)符合下述三个条件时，顾客到达过程符合下述三个条件时，顾客到达过程就是泊松过程就是泊松过程(顾客到达形成普阿松流顾客到达形成普阿松流)。40 无后效性：无后效性：各区间的到达相互独立各区间的到达相互独立,即即MarkovMarkov性。性。.t0 t1 t2 tn-1 tn|)(|)(11112211)()(,.,)(,)(nnnnxtxnxtxxtxxtxnntx
34、PntxP 也就是说过程在也就是说过程在t+tt+t所处的状态与所处的状态与t t以前所处的状以前所处的状态无态无关。关。平稳性：平稳性：即对于足够小的即对于足够小的tt，有：，有：)()(tttttP ，1普阿松流具有如下特性：普阿松流具有如下特性：在在t,t+tt,t+t内有一个顾客到达的概率与内有一个顾客到达的概率与t t无关无关,而与而与tt成正比。成正比。41 普通性：普通性：对充分小的对充分小的t,t,在时间区间（在时间区间（t,t+tt）内有内有2 2个或个或2 2个以上顾客到达的概率是一高阶无穷小个以上顾客到达的概率是一高阶无穷小.由此知，在由此知，在(t，t+t)t)区间内没
35、有顾客到达的概率为：区间内没有顾客到达的概率为：)(1),(0tottttP 令令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 是常数，它是常数，它表示单位时间到达的顾客数，称表示单位时间到达的顾客数，称为概率强度。为概率强度。2)(),(nntotttP 即即 P P0 0+P+P1 1+P+P22=1=142情情 形形 0 0，t t)概概 率率 t t，t t+t t)概概 率率 0 0，t t+t t ）A A n n P Pn n(t t)0 0 1 1-t t +O O(t t)
36、P Pn n(t t)(1 1-t t +O O(t t)B B n n-1 1 P Pn n-1 1(t t)1 1 t t P Pn n-1 1(t t)t t n n-2 2 P Pn n-2 2(t t)2 2 n n-3 3 P Pn n-3 3(t t)3 3 .C C 0 0 P P0 0(t t)n O O(t t)O O(t t)在在00，t+tt+t内到达内到达n n个顾客应是上面三种互不相个顾客应是上面三种互不相容的情况之一，所以有：容的情况之一，所以有：为了求为了求Pn(t),即即Pn(0,t)，需要研究它在（，需要研究它在（t，t+tt）上的改变量上的改变量,建立建立
37、P Pn n(t)(t)的微分方程。对于区间的微分方程。对于区间0,0,t+t)+t)可以分成可以分成00，t)t)和和tt，t+t),t+t),其到达总数是其到达总数是n n，不外有，不外有下列三种情况：下列三种情况：43 令令t0t0取极限（并注意初始条件）得：取极限（并注意初始条件）得：)()()(1tPtPdttdPnnn0)0(nP(3)(3)当当n=0时，没有时，没有B，C两种情况，则：两种情况，则：)()(00tPdttdP1)0(0P(4)(4)()()1)()(1tOttPttPttPnnn)()()()()(1tOttPttPtPttPnnnnttOtPtPttPttPnn
38、nn)()()()()(1 凑微分凑微分44CCt01n C C =0=0ttP )(n0（3 3）式两端乘）式两端乘e e t t并移项得：并移项得：te)t(P 0(5)(5)（没有顾客到达的概率）（没有顾客到达的概率）dtPtdP )()(000CttP )(n0 两边积分得：两边积分得：代入初始条件代入初始条件(t=0)t=0)有有：P P0 0(0)=1(0)=1)t(P)t(Pdt)t(dPnnn1 0)0(nP)()(00tPdttdP45 将将n=1,2,3代入（代入（6）得：）得：tntnetPetPdtd )()(1 11101)()(dtetPetPtnttn (6)(6
39、)110011)()(dtetPetPttt (注意利用注意利用(5)式式)tdteettt 1011tntntne)t(Pe)t(Pedt)t(dP 1tntnnte)t(Pe)t(Pdt)t(dPe 1 凑成凑成P Pn n(t)e(t)e t t两两项乘积的微分项乘积的微分 两边积分两边积分te)t(P 046 如此继续递推下去得：如此继续递推下去得：tettP !2)()(22 （2 2个顾客到达的概率）个顾客到达的概率）（n n个顾客到达的概率）个顾客到达的概率）tnnenttP !)()(即随机变量即随机变量N(t)=n服从泊松分布。它的数学期望服从泊松分布。它的数学期望和方差为：
40、和方差为：ttetP )(1 （1 1个顾客到达的概率）个顾客到达的概率）11011102111)()(dteetdtetPetPtttttt 2221t 47 级数级数.!nx.!xxenx 212tkke!k)t(0!)()()(11ntnetnPtNEnntnn )!1()(11 nttennt 令令k=n-1，则：，则：!)()(0kttetNEkkt tetetNEtt )(482121)()!1()()!2()(tntntttennnt tttttettett 22)()1()1(ttar )(N(V 即即：21221)(!)()()(tntnnettPnnntnn 22E(N(t
41、)EN(t)(tNVar 同理方差为：同理方差为：211121)()!1()()!1()()1()()!1()(tntntntetntnnennntnnt 顾客到达过程是一个顾客到达过程是一个泊松过程泊松过程(泊松流泊松流)。49 其概率密度函数为：其概率密度函数为：tTTedtdF)t(f t0t0 当输入过程是泊松流时，我们研究两顾客相继到当输入过程是泊松流时，我们研究两顾客相继到达的时间间隔的概率分布。达的时间间隔的概率分布。设设T T为时间间隔，分布函数为为时间间隔，分布函数为F FT T（t t），则：），则：F FT T（t t）=PTt=PTt 此概率等价于在此概率等价于在00，
42、t t）区间内至少有）区间内至少有1 1个顾客到个顾客到达的概率。达的概率。tTetPtF 1)(1)(0 t0t0tetP)(0 没有顾客到达的概率没有顾客到达的概率为：为：(由（由（5）式而来）式而来)50 表示单位时间内顾客平均到达数。表示单位时间内顾客平均到达数。1/表示顾客到达的平均间隔时间。表示顾客到达的平均间隔时间。可以证明，间隔时间可以证明，间隔时间T T独立且服从负指数分布与独立且服从负指数分布与顾客到达形成泊松流是等价的。顾客到达形成泊松流是等价的。对顾客的服务时间对顾客的服务时间：系统处于忙期时系统处于忙期时两顾客相继离两顾客相继离开系统的时间间隔开系统的时间间隔，一般地
43、也服从负指数分布，设：，一般地也服从负指数分布，设：即即T服从负指数分布，它的期望及方差为：服从负指数分布，它的期望及方差为：1TE21 TVar 接受服务，然后离开接受服务，然后离开服务时间的分布：服务时间的分布：51其中：其中：表示单位时间内能被服务的顾客数，即平均表示单位时间内能被服务的顾客数，即平均 服务率。服务率。1/1/表示一个顾客的平均服务时间。表示一个顾客的平均服务时间。设设v v1 1,v,v2 2，,v,vk k是是k k个独立的随机变量，服从相同个独立的随机变量，服从相同参数参数 k k 的负指数分布，那么：的负指数分布，那么：tetF 1)(tetf )(，则，则 令令
44、 ，则，则称为服务强度称为服务强度。kT 2152 串列串列k k个服务台个服务台，每台服务时间相互独立，服从，每台服务时间相互独立，服从相同负指数分布（参数相同负指数分布（参数k k），那么一顾客走完），那么一顾客走完k k个服个服务台总共所需要服务时间服从上述务台总共所需要服务时间服从上述k k阶阶ErlangErlang分布。分布。011 te)!k()kt(k)t(ftkkk 则称则称T服从服从k阶阶爱尔朗分布。其特征值为：爱尔朗分布。其特征值为：1TE21 kTVar,其概率密度是其概率密度是1/k1/k表示一个顾客一个服务台的平均服务时间。表示一个顾客一个服务台的平均服务时间。53
45、 例例:有易碎物品有易碎物品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-
46、1-1=0.0613=0.0613 即物品破碎即物品破碎3 3件的概率为件的概率为6.136.13 2.2.破碎物品少于破碎物品少于3 3件的概率件的概率:54 破碎物品少于破碎物品少于3 3件的概率为件的概率为91.9791.97 破碎物品多于破碎物品多于3 3件的概率为件的概率为:02.098.01!1330 kkekp 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.632 9197.021112120 eeknp55 对排队模型，在给定输入和服务条
47、件下，主要对排队模型，在给定输入和服务条件下，主要研究系统的下述运行指标：研究系统的下述运行指标：(1)(1)系统的系统的平均队长平均队长LsLs(期望值期望值)和和平均队列长平均队列长LqLq(期望值期望值)；(2)(2)系统中系统中顾客平均逗留时间顾客平均逗留时间WsWs与队列中与队列中平均等平均等待时间待时间WqWq；本节只研究本节只研究M/M/1M/M/1模型，下面分三种情况讨论：模型，下面分三种情况讨论：8-5 M/M/1 8-5 M/M/1 无限源系统无限源系统56 系统中有系统中有n n个顾客个顾客M/M/1:/FCFS/FCFS模型模型 在任意时刻在任意时刻t t，状态为，状态
48、为n n的概率的概率P Pn n(t)(t)（瞬态概率），（瞬态概率），它决定了系统的运行特征。它决定了系统的运行特征。已知顾客到达服从参数为已知顾客到达服从参数为的泊松过程，服务时的泊松过程，服务时间服从参数为间服从参数为的负指数分布。现仍然通过研究区间的负指数分布。现仍然通过研究区间 t，t+tt）的变化来求解。在时刻）的变化来求解。在时刻t+tt，系统中有，系统中有n n个顾客不外乎有下列四种情况（个顾客不外乎有下列四种情况（t，t+tt）内到达）内到达或离开或离开2 2个以上个以上没列入）。没列入）。？57区区间间(t t,t+t t)情情况况 时时刻刻t t的的顾顾客客 到到达达 离
49、离去去 时时刻刻t+t t的的顾顾客客 (t t,t+t t)的的概概率率 0 0,t+t t 的的概概率率 A n n 1-t+O(t)1-t+O(t)Pn(1-t+O(t)（1-t+O(t)）B n+1 n 1-t+O(t)t+O(t)Pn+1(1-t+O(t)（t+O(t)）C n-1 n t+O(t)1-t+O(t)Pn-1(t+O(t)（1-t+O(t)）D n n t+O(t)t+O(t)Pn(t+O(t)（t+O(t)）由于这四种情况是互不相容的，所以由于这四种情况是互不相容的，所以Pn(t+t)t)应应是这四项之和，则有：是这四项之和，则有：tttPtttPtttPttPnnn
50、n)1)()()1)(1)()(1)()1()(1tOtttPn58t)t(P)t(P)t(O)t(Ott)(t(Pnnn 11)t(O)t(O)t(Pt)t(P)t(O)t(Pnnn 111)t(Ot)t(Pt)t(P)tt)(t(Pnnn 111t)t(O)t(P)()t(P)t(Pt)t(P)tt(Pnnnnn 11 令令t0t0，得关于，得关于P Pn n(t)(t)的微分差分方程：的微分差分方程：)()()()()(11tPtPtPdttdPnnnn(1)当当n=0时，只有表中的（时，只有表中的（A）、（）、（B）两种情况，）两种情况，因为在较小的因为在较小的tt内不可能发生（内不可
