数学建模之排队论.pdf

数学建模之China Undergraduate Mathematical Contest in Modeling一、CUMCM历年赛题的简析1.CUMCM的历年赛题浏览:1992年：（A）作物生长的施肥效果问题（北理工：叶其孝）（B）化学试验室的实验数据分解问题（复旦：谭永基）1993年：（A）通讯中非线性交调的频率设计问题（北大:谢衷洁）（B）足球甲级联赛排名问题（清华：蔡大用）1994年：（A）山区修建公路的设计造价问题（西电大：何大可）（B）锁具的制造、销售和装箱问题（复旦:谭永基等）1995年：（A）飞机的安全飞行管理调度问题（复旦:谭永基等）（B）天车与冶炼炉的作业调度问题（浙大:刘祥官等）一、CUMCM历年赛题的简析1.CUMCM的历年赛题浏览:1996年：（A）最优捕鱼策略问题（北师大：刘来福）（B）节水洗衣机的程序设计问题（重大：付鹉）1997年：（A）零件参数优化设计问题（清华：姜启源）（B）金刚石截断切割问题（复旦：谭永基等）1998年：（A）投资的收益和风险问题（浙大：陈淑平）（B）灾情的巡视路线问题（上海海运学院:丁颂康）1999年：（A）自动化机床控制管理问题（北大：孙山泽）（B）地质堪探钻井布局问题（郑州大学：林诒勋）一、CUMCM历年赛题的简析1.CUMCM的历年赛题浏览：2000年：（A）DNA序列的分类问题（北工大：孟大志）（B）钢管的订购和运输问题（武大：费甫生）2001年：（A）三维血管的重建问题（浙大：汪国昭）（B）公交车的优化调度问题（清华：谭泽光）2002年：（A）汽车车灯的优化设计问题（复旦:谭永基等）（B）彩票中的数学问题（信息工程大学：韩中庚）2003年:（A）SARS的传播问题（集体）（B）露天矿生产的车辆安排问题（吉林大：方沛辰）一、CUMCM历年赛题的简析1.CUMCM的历年赛题浏览2004年：（A）奥运会临时超市网点设计问题（北工大：孟大志）（B）电力市场的输电阻塞管理问题（浙大:刘康生）2005年：（A）长江水质的评价与预测问题（信息工大:韩中庚）（B）DVD在线租赁问题（清华大学：谢金星等）2006年:（A）出版社的资源管理问题（北工大:孟大志）（B）艾滋病疗法的评价及预测问题（天大：边馥萍）2007年:（A）中国人口增长预测问题（清华大学:唐云）（B）“乘公交，看奥运”问题（吉大：方沛辰，国防科大：吴孟达）一、CUMCM历年赛题的简析2、从问题的实际意义分析32个问题从实际意义分析大体上可分为：工业、农业、工程设计、交通运输、经济管理、生物医学和社会事业等七个大类。工业类：电子通信、机械加工 与制造、机械设计与 控制等行业，共有8个 题，占25%。农业类：1个题，占3.1%。工程设计类：3个题，占9.4%。交通运输类：4个题，占12.5%经济管理类：5个题，占15.6%生物医学类：5个题，占15.6%社会事业类：6个题，占18.8%有的问题属于交叉的，或者是边缘的。一、CUMCM历年赛题的简析3、从问题的解决方法上分析从问题的解决方法上分析，涉及到的数学 建模方法：几何理论、组合概率、统计（回归）分析、优化方法（规划）、图论与网络优化、层次分 析、插值与拟合、差分方法、微分方程、排队 论、模糊数学、随机决策、多目标决策、随机 模拟、灰色系统理论、神经网络、时间序列、综合评价、机理分析等方法。一、CUMCM历年赛题的简析3、从问题的解决方法上分析用的最多的方法是优化方法和概率统计的方法.用到优化方法的共有22个题，占总数的68.8%,其中整数规划4个，线性规划6个，非线性规划14 个，多目标规划6个。用到概率统计方法的有16个题，占50%,平均每 年至少有一个题目用到概率统计的方法。用到图论与网络优化方法的问题有6个；用到层次分析方法的问题有3个；一、CUMCM历年赛题的简析3、从问题的解决方法上分析 用到插值拟合的问题有6个；用到神经网络的4个；用灰色系统理论的4个；用到时间序列分析的至少2个；用到综合评价方法的至少3个；机理分析方法和随机模拟都多次用到；其他的方法都至少用到一次。大部分题目都可以用两种以上的方法来解决,即综合性较强的题目有26个，占81.3%。两个引例：问题1:校园网的设计和调节收费问题随着计算机技术的飞速发展，校园信息网 已经在全国高校中普及。某高校拟建一个校园信息网，并与Internet 连接，用户可以通过网络通信端口拨号上 网。因此，需要用户的数量，研究通信端口的 设计规模。问题1:校园网的设计和调节收费问题 通常的通信端口分为16口，32口，64口，128 口。实际中，随着通信端口数量的增加，其成 本费将成倍增加。如何根据实际情况，在保证基本满足用户 需求的条件下，确定合适的通信端口数，以减少费用的开支和资源的浪费。当网络建成以后。为了保证用户有效的使 用信息网，必须要通过适当的收取线路调 节费，以控制上网时间。问题1:校园网的设计和调节收费问题 一般认为，采用分段计时收费比较合理，例如按上网时间长短分为“免费一半费一全 费一2倍3倍4倍.,”等时段。现在的问题是：（1）假设有m个用户，每个用户每天（按 16h计算）平均上网L 5h,试确定通信端口 数11与171的比例问题1:校园网的设计和调节收费问题(2)假设m=150,按所设定的通信端口数n,试讨论平均每天每个用户上网lh,2h,3h,4h,5h的可能性，出现因线路忙，导致用户想 上网而上不去产生抱怨的可能性，以及通信端 口的平均使用率；(3)为了控制上网时间，学校要求适当收取 线路调节费，试给出一种合理的分段计时收费 方案。问题2:眼科病床的合理安排问题09B医院是一个复杂的系统，病人从挂号、就 诊、划价、取药需遍历每一个服务机构，当 余项服务的现有需求超过提供该服务的现 宥能力时,排队现象就会发生，由于患者到 达肝而和诊治患手所需时间的随机性,可袅 性小，排队几乎不可避免。因此如何合理科 学安排医护人员及医疗设备，使医院不会 盲目增加医生和设备造成不必要的空闲，形 成资源浪费,又使患者排队等待时间尽可能 减少，如何在这两者之间取得平衡,以便提 高服务质量,降低服务费用，这是现代医院 管理著必须面对的课题。问题2:眼科病床的合理安排问题09B本题给出了病床数与眼科手术类别及要 求，附录中还提供了一段时间的统计数 据，要求回答五个问题。(1)确定合理的评价指标评价该问题的病 床安排模型，即评价FCFS模型；(2)建立合理的病床安排模型，确定第二 天应该安排那些病人入院，并用上述指标 进行检验；问题2:眼科病床的合理安排问题09B(3)通过统计分析，求得病人的入住时间 的区间；(4)在周六、周日不手术时，重新计算评 价指标，判断优劣后对手术时间安排做适 当调整；(5)固定各类病人占用病床的比例，使得所有病人在系统内的平均逗留时间(含等 待入院及住院时间)最短。CUMCM09 年 B题“眼科病床的合理安排住要考点:1.分布拟合检验；2.合理的评价指标体系；3.仿真方法应用;4.满足一定置信度的统计预测模型的建立;5.排队论优化模型的建立。排队论(Queuing Theory)排队论（queuing）,也称随机服务系统理 论，是运筹学的一个主要分支。1909年，丹麦哥本哈根电子公司电话工 程师A.K.Erlang的开创性论文“概率论和电 话通讯理论”标志此理论的诞生。排队论的发 展最早是与电话，通信中的问题相联系的，近年来在计算机通讯网络系统、交通运输、医疗卫生系统、库存管理、作战指挥等各领 域中均得到应用。排队论 前言 基本概念 到达时间间隔分布和服务时间分布 M/M/1 单服务台的排队系统 M/M/c 多服务台的排队系统 校园网的设计和调节收费问题前含排队是我们在日常生活和生产中经常遇到的现象。例如，上、下班搭乘公共汽车；顾客到 商店购买物品；病员到医院看病；旅客 到售票处购买车票；学生去食堂就餐等 就常常出现排队和等待现象。为富除了上述有形的排队之外，还有 大量的所谓“无形”排队现象。如几个顾客打电话到出租汽车站 要求派车，如果出租汽车站无足够车辆、则部分顾客只得在各自的要车处等待，他们分散在不同地方，却形成了一个无形队列在等待派 车。前言排队的不一定是人，也可以是物：例如，通讯卫星与地面若干待传递的信 息；生产线上原料、半成品等待加工；因故障停止运转的机器等待修理；码头的船 只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋等 等。前言上述各种问题虽互不相同，但却都有 要求得到某种服务的人或物和提供服务 的人或机构。排队论里把要求服务的对象统称为“顾客”，提供服务的人或机构称为“服务台”或“服务 员。前言不同的顾客与服务组成了各式各样的服务系统 O顾客为了得到某种服务而到达系统、若不能 立即获得服务而又允许排队等待，则加入等待 队伍，待获得服务后离开系统，见图1至图5。顽客能-服务完而后离去 00-o I服务台|-正在向服务躯客图1 单服务台排队系统（去 代售点买火车票）前含顾客到达 队列-o O服务台1服务台20服务台S服务完成后离去-服务完成后离去-服务完成后离去-图2 单队列-S个服务台并联的排队系统（找工作）队列2队列s.O队列1.oO服务台1O服务台2O服务台S服务完成后离去服务完成后离去服务完成后离去O图3 S个队列-S个服务台的并联排队系统（火车站买火车票）前含顾客到达 队列 I-0.O o服务台1队列-0.o o服务台2服务完成后离去-图4 单队-多个服务台的串联排队系统（报名）顾客到达4型列1 C顾客到达“队列2c-U.u服务台服务孤后酷，图5 多队-多服务台混联1络系统（体检）前含任一排队系统都是一个随机聚散服务系统。一般的排队系统，都可由下面图加以描述。聚 厂_I散顾客离开-（输出）图6 般机服务系统“聚”表示顾客的到达，“散”表示顾客的离去。通特称由 图6表示的系统为一随机聚散服务系统前才面对拥挤现象，人们总是希望尽量设法 减少排队，通常的做法是增加服务设施。但是增加的数量越多，人力、物力的支 出就越大，甚至会出现空闲浪费。如果服务设施太少，顾客排队等待的时 间就会很长，这样对顾客会带来不良影响。前才顾客排队时间的长短与服务设施规模的 大小，就构成了设计随机服务系统中的一对 矛盾。如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾 客排队时间与服务设施费用大小这对矛盾。这就是随机服务系统理论排队论所 要研究解决的问题。1排队系统的基本概念,、排队系统的组成与特征排队系统一般有三个基本组成部分：1.输 入过程；2.排队规则；3.服务机构。图1排队系统示意图1.输入过程输入即为顾客的到达，可能有下列情况：1）顾客源可能是有限的，也可能是无限的。2）顾客是成批到达或是单个到达。3）顾客到达间隔时间可能是随机的或确定的。4）顾客到达可能是相互独立或关联的。所谓独 立就是以前顾客的到达对以后顾客的到达无影响。5）输入过程可以是平稳的（st a t io n a ry）或说 是对时间齐次的（Ho mo gen eo us in t ime）,也可以 是非平稳的。输入过程平稳的指顾客相继到达的间 隔时间分布和参数（均值、方差）与时间无关；非 平稳的则是与时间相关，非平稳的处理比较困难。2.排队规则排队规则指服务台从队列中选取顾客进行服务的顺 序。可以分为损失制、等待制、混合制3大类。(1)损失制。这是指如果顾客到达排队系统 时，所有服务台都已被先来的顾客占用，那么他 们就自动离开系统永不再来。典型例子是，如电话拔号后出现忙音，顾客 不愿等待而自动挂断电话，如要再打，就需重新 拔号，这种服务规则即为损失制。2.排队规则(2)等待制。指当顾客来到系统时，所有服务台 都不空，顾客加入排队行列等待服务。例如，排队等待售票，故障设备等待维修等。等待制中，服务台在选择顾客进行服务时，常有 如下四种规则：先到先服务(FCFS)o按顾客到达的先后顺 序对顾客进行服务，这是最普遍的情形。后到先服务(LCFS)o仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。2.排队规则随机服务(RAND)o即当服务台空 闲时，不按照排队序列而随意指定某个顾客 去接受服务，如电话交换台接通呼叫电话就 是一例。优先权服务(PR)。如老人、儿童 先进车站；危重病员先就诊；遇到重要数据 需要处理计算机立即中断其他数据的处理 等，均属于此种服务规则。2.排队规则(3)混合制.这是等待制与损失制相结合的一种 服务规则，一般是指允许排队，但又不允许队列 无限长下去。具体说来，大致有三种：队长有限。当排队等待服务顾客人数超过 规定数量时，后来顾客就自动离去，另求服务。如水库的库容、旅馆的床位等都是有限的。2.排队规则等待时间有限。即顾客在系统中的 等待时间不超过某一给定的长度T,当等待 时间超过T时，顾客自动离去，不再回来。如易损坏的电子元器件的库存问题，超过一定存储时间被自动认为失效。又如顾客到饭馆就餐，等了一定时间后 不愿再等而自动离去另找饭店用餐。2.排队规则逗留时间（等待时间与服务时间之和）有限。例如用高射炮射击敌机，当敌机飞越高射 炮射击有效区域的时间为t时，若在这个时 间内未被击落，也就不可能再被击落了。不难注意到，损失制和等待制可看成是 混合制的特殊情形，如记C为系统中服务台 的个数，K为系统容量，则当K=c时，混合制 即成为损失制；当K=8时，混合制即成为等 待制。3.服务机构1）服务机构可以是单服务员和多服务员 服务，这种服务形式与队列规则联合后形成 了多种不同队列，不同形式的排队服务机 构。如前图1到5：2）服务方式分为单个顾客服务和成批顾客 服务。3）服务时间分为确定型和随机型。4）服务时间的分布在这里我们假定是平稳 的。二、排队系统的描述符号与模型分类:上述特征中最主要的、影响最大的是：顾客相继到达的间隔时间分布 服务时间的分布 服务台数1953年D.G.Ken d a l l提出了分类法，称为Ken d a l l记号（适 用于并列服务台）即：X/Y/Z/d/e/f其中：X顾客相继到达间隔时间分布Y服务时间分布，X和Y主要有以下几种分布M一负指数分布Markov,D确定型分布 D eterministic,EkK阶爱尔朗分布Erlang,GI 一般相互独立随机分布(General Independent),G一般随机分布。Z并列的服务台数d排队系统的最大容量e顾客源数量 f排队规则如M/M/1/8/8/FCFS即为顾客到达为泊松过 程，服务时间为负指数分布，单台，无限容量，无 限源，先到先服务的排队系统模型。三、排队论研究的基本问题1.系统性态问题:即研究各种排队系统的概率 规律性，主要研究队长分布、等待时间分布和忙 期分布等统计指标,包括了瞬态和稳态两种情形。2.最优化问题：即包括最优设计（静态优 化），最优运营（动态优化）。3.排队系统的统计推断:即通过对排队系统主 要参数的统计推断和对排队系统的结构分析，判 断一个给定的排队系统符合哪种模型，以便根据 排队理论进行研究。I排队问题求解（主要指性态问题）求解一般排队系统问题的目的主要是通过研究 排队系统运行的效率指标，估计服务质量，确定系 统的合理结构和系统参数的合理值，以便实现对现 有系统合理改进和对新建系统的最优设计等。排队问题求解的一般步骤：1.确定或拟合排队系统顾客到达的时间间隔分 布和服务时间分布（可实测）。2.研究分析排队系统理论分布的概率特征。3.研究系统状态的概率。系统状态是指系统中 顾客数。状态概率用P”表示，即在t时刻系统中有 n个顾客的概率，也称瞬态概率。求解状态概率Pn(t)方法是建立含Pn(t)的微分差 分方程，通过求解微分差分方程得到系统瞬态解，由 于瞬态解一般求出确定值比较困难，即便求得一般也 很难使用。因此常常使用它的极限(如果存在的话)：阿P 二P，称为稳态(st ea d y st a t e)解，或称统计平衡状态(St a t ist ica l Equil ibrium St a t e)的解。稳态的物理意义图，系K统的稳态一般很快都能 M*aA”A/W达到，但实际中达不到*产w稳态的现象也存在。要(J U注意的是求稳态概率Pn U _七个二昌求I：的极|过渡状态|I稳定状态I r限,只需求Pn(t)=0 o 图3排队系统状态变化示意图4.求用以判断系统运行优劣的基本数量指标的概率分布或特征数。数量指标主要包括：(1)平均队长(虫):系统中顾客数的期望值。平均队 列长(Lq):系统中排队等待服务顾客数的期望值。(2)平均逗留时间(Ws):一个顾客在系统中停留时间的期望值。平均等待时间(Wq):一个顾客在系统中排队 等待时间的期望值。(3)忙期：指从顾客到达空闲服务机构起到服务机构再 次空闲这段时间长度。(忙期和一个忙期中平均完 成服务顾客数都是衡量服务机构效率的指标，忙期 关系到工作强度)损失率：由于系统的条件限制，使顾客被拒绝服务 而使服务部门受到损失的概率5.排队系统指标优化含优化设计与优化运营。圜间筹思 2到达间隔时间分布和服务时间分布一个排队系统的最主要特征参数是顾客 的到达间隔时间分布与服务时间分布。要研究到达间隔时间分布与服务时间分 布需要首先根据现存系统原始资料统计 出它们的经验分布，然后与理论分布拟 合，若能照应，我们就可以得出上述的 分布情况。、经验分布经验分布是对排队系统的某些时间参数根 据经验数据进行统计分析，并依据统计分析结果 假设其统计样本的总体分布，选择合适的检验方 法进行检验，当通过检验时，我们认为时间参数 的经验数据服从该假设分布。分布的拟合检验一般采用x 2检验。由数理 统计的知识我们知：若样本量n充分大(n250),则当假设%为真时，统计量总是近似地服从自由 度为的x2分布，其中k为分组数，r为检验 分布中被估计的参数个数。（力一呼 咱ki=l时，在显著水平a下接受假设“式中：fj实际频数rij理论频数上面方法的应用必须注意n要足够大，nR不能 太小。一般地n要大于50,而分组的npj应不小于 5o例题：某公共汽车站，统计来站的乘客流，规定 每隔1分钟统计一次乘客到达情况，共统计100 次，其结果如表所示，问顾客是否服从泊松流？状态i0123456789101112实际频数15161726119921210解：先估计分布的参数人，由极大似然估计法得:A=x=4.2，并根据公式 Px i-可计算出理论频率、理论频数及项Z-nPi 21n pi见下页表所示查表知：心（女厂1）=a.。5=12.592,6.2815故可接受泊松分布假设。fiPin Pi10.0151.550.0636.3160.13213.2170.18518.5260.19419.4110.16316.390.11411.490.0696.920.0363.610.0171.720.0070.710.0030.300.0020.2fi-n pi(fi-n pi)2/n Pi-1.80.4152.8-1.56.6 5.3-2.42.10.5940.1222.2451.7230.5050.639K-r-l=8-1-1HO.50.0385X=6.2815二、概率论知识复习随机变量 数匕随着实验的结果的不同而变化 离散型：匕的所有可能只有限或至多可列个连续型：g（D）取值于某个区间（a,b）分布函数（连续）：尸=p化（）xpa J（）b=F（b）-F（a）匕的概率分布（离散）：履二%二 仁1,2,3.00E(%)=1i=lX 8密度函数：（连续）F（x）=1八 000000数学期望：（离散）EG）二E xiPii=l00(连续)E(,)=j xf(x yixco方差：右6）（二（0）2条件概率：p（AB）=p（B）p（A/B）三、理论分布1.泊松分布在概率论中，我们曾学过泊松分布，设随机变 量为X,则有：2几 一2Px n-n=0J2(1)n式中人为常数(人 0)，称X服从参数为X的泊松分布，若在上式中引入时间参数3即令人t代替人，则有:)W-Pnt=e t0,n=0J,2-11 与时间有关的随机变量的概率，是一个随机过 程，即泊松过程。在一定的假设条件下口龈客的到达过程就是一 个泊松过程。若设N(t)表示在时间区间0,t)内到达的顾客数(t 0),Pn(G，t 2)表示在时间区间出,t 2)内有 n(20)个顾客到达的概率。即：Pntl,t2=PN(t2)N(tl)=n当Pn(t i2)符合下述三个条件时，顾客到达过程 就是泊松过程(顾客到达形成泊松流)：无后效性：各区间的到达相互独立，即Ma rk o v性。_%t 2 t rl 11(%)=X,X2)=-2,)=Xn-1 尸M匕)竺把L=_2P(t)+2Pti At)区间长度(o,dt-。)有n对嬴客到达JG(o)=o当n=o时，没有B,C号里况二贝手、dP _ p(0,t)有n-l,n-2f dT 1 l 个顾客到达,U(o)=i阳P0(0)=dt与J温at两边积分得：nP.(t)=-kt+C代入初始条件日也色一 P()(O)=1 1nl=-Ai+C=-A 04 C=0 2=一?1P)+九尸1(口at，心。)=7 C(o)=o工 尸0 二顾客到达的概率)局 gx两端乘并移项得：dPn(t)Feu=-XPn(t)eu+XPn_1(t)eu at*dPn(t)+h其()*=人P dt凑成R（t）e枇两 两边积分P 九%（。）0助忆(6)0将n=l,2,3代入(6)得:Pi）e忒=九1Po（0）e储比i(eU1 edt1=U（注率利用式）P.（t）=e-UPJf)=九te-t(1个顾客到达的概率)P2(f)eu=x舄(B)。叫&1二九.九十遇 储e叫比122=X2/22(Xt)2 n.P2(t)=-Le一股(2个顾客到达的概率)2!如此继续递推下去得：(Itr-PJt)=-e-U(n个顾客到达的概率)加-即随机变量N(t)=n服从泊松分布。它的数学期望 和方差为：00 00 7、EN=E nPn(t)=.n=l n=l”00=n=l(很)1(H-l)!令k=n-L则：00EN(t)=e-u-kt-k=0g)k k.ex=l+x+2!n!y(M)k=*h k!EN(t)=e-u-Xf-eu=Xf同理方差Var(N(t)=EN(t)2 -E(N(t)2为:0000=Z n2-Pn(t)-(U)2=e-uXn=l00Qtyn=l00at)n,H,tl-St)nl11=1nn-(h-1)!-函)2=&*Z(H-1)n=lw1 w1(n-l)!+(n-l)!（时00丘n=l=UeuQ旷 2(xt)-1(n-2)!+(n-l)!、-an27=人tet 0.其概率密度函数 fT(t)=Xeu t 0为 出即T服从负指数分布，它的期望及方差为：ET=%VarT=人表示单位时间内顾客平均到达数。1/人表示顾客到达的平均间隔时间。可以证明，间隔时间T独立且服从负指数分布与 顾客到达形成泊松流是等价的。服务时间的分布：接受服务，然后离开二对顾客的服务时间R系统处于忙期时两顾客相继离 开系统的时间间隔，一般地也服从负指数分布，设：Fv(t)=l-e，则九(十)=匿2其中：表示单位时间内能被服务的顾客数，即平均 服务率。1/表示一个顾客的平均服务时间。令p=%，则0称为服务强度。3.爱尔朗(Erl a n g)分布设Vi,V2,，Vk是k个独立的随机变量，服从相同 参数阵的负指数分布，那么：r=v1+v2+-+vJt其概率密度是fk(t)=一 t 0Jk(k-1)!则称T服从k阶爱尔朗分布。其特征值为：ET=-VarT=-|li，ki1/k 表示一个顾客一个服务台的平均服务时间。串列k个服务台，每台服务时间相互独立，服从 相同负指数分布(参数印)，那么一顾客走完k个服 务台总共所需要服务时间服从上述k阶Er 1 a n g分布。圜间筹思3 M/M/1 单服务台的排队系统对排队模型，在给定输入和服务条件下，主要研究系统的下述运行指标:系统的平均队长Ls（期望值）和平均队列长Lq（期望值）；系统中顾客平均逗留时间Ws与队列中平均等待时间Wq；本节研究M/M/1模型，下面分三种情况讨论:,、标准的M/M/1模型M/M/1/8/8/FCFS模型玄纬山有1.稳态概率Pn的计算一-一一W n个顾客在任意时刻3状态为n的概率Pn（t）t w怒瞬f,它决定了系统的运行特征。已知顾客到达服从参数为X的泊松过程，服务时 间服从参数为的负指数分布。现仍然通过研究区间 t,t+At）的变化来求解。在时刻t+At,系统中有n 个顾客不外乎有下列四种情况（t,t+At）内到达 或离开2个以上没列入）。厂二o o 情况客区间(t,t+At)时亥（It+At 客(t,t+At)的概率0,t+At的概率达AnXXn1-X At-+O(At)1-U At+O(At)Pn(l-XAt+O(At)*(1-U At-+O(At)Bn+lXVn1-X At+O(At)U At+O(At)Pn+1(l-X At-rfXAt)(U At-+O(At)Cn-1VXnX At+O(At)1-U At+O(At)Pn4(X At+O(At)-(17 At+O(At)DnVVnX At+O(At)li At+O(At)Pn(XAt+O(At)-(U At+O(At)由于这四种情况是互不相容平 是这四项之和，则有：一一I所有的高阶无;穷和并 J尺。+&）=c。）（1-尬）（1-心）+匕公心+月+1。）（1-尬）心+Pn_x M(1 岫)+0(4)=a-他-河+a&)+a&)记+4+1河P”t)0(X)+Pnt 人及 一 Pnt 0(X)+0()=Pn(t)(l-)+Pn+l(t)+PnJt)+O(一+?玖“=叫_1+吗/)-仅+/；)+%M M令At-O,得关于P“(t)的微分差分方程：粤=狙_甘)+阳同(九+田匕(t)(1)d t_当n=0时，只有表中的(A)、(B)两种情 况，因为在较小的At内不可能发生(D)(到达后 即离去)，若发生可将At取小即可。）（1 一九&）+p1（t）（1 一九&）（四）+叫 at这种系统状态(n)随时间变化的过程就是生灭过程(Birth and Death Process)。方程(1)、(2)解是瞬态解，无法应用。稳态时，Pn(t)与时间无关，可以写成Pn,它对时 间的导数为0,所以由(1)、(2)两式得：/t+阳+1-仅+四阳=。.(3)一叫+叫=0.(4):吸_1+吗仅+|Ll阳=0 关于Pn的差1,一郎+=0 分寸程，由此可得该排队系统的状态转移图：状态转移图由（4）得：4=&品=品其中p服务强度将其代入（3）式并令n=l,2,（也可从状态转移 图中看出状态平衡方程）得：n=l 码+%一（九+（Li*=0 叫+叫仅+M2片=01，九（九十|1）九线=（一）2 宾=p2=n2 入P+|Li?_（九+|Li）P2 0i i Vx,Pq+|nf（九十|li）k=o1|7九+日）九2八 四 H J一一P.=（-）3P.=P3P.系统 稳态 概率）以此类推，当11=11时,及概率性质知：pn=i=000 1M i-pJ 4=i-p（数列的极限为）石.(6)系统的运行指标2.系统的运行指标计算 甘,(1)系统中的队长Ls(平均队长)上00 00Ls=2=,(1-p),pw=0 w=0=(1p),p+2fl-pj,p2+3fl-p)p3+p)p+=p-p2+2P之-2p3+3P3-3p4+.+npn-npn+1+.=p+p2+p3+.pn(0 P 0)=l-4=p P(N k)=.+i?例1某医院急诊室同时只能诊治一个病人，诊 治时间服从指数分布，每个病人平均需要15分 钟。病人按泊松分布到达，平均每小时到达3 人。试对此排队队系统进行分析。解 对此排队队系统分析如下：(1)先确定参数值：这是单服务台系统，有：2=3人/=人/6=4 人/h15故服务强度为：/?=-=-=0.75 4(2)计算稳态概率:Po=1 =1 0.75=0.25这就是急诊室空闲的概率，也是病人不 必等待立即就能就诊的概率。而病人需要等待的概率则为：p=l-PQ=0.75这也是急诊室繁忙的概率。（3）计算系统主要工作指标：急诊室内外的病人平均数：Ls=-=人=3 人 2 4 3急诊室外排队等待的病人平均数：L=Lp=3x 0.75A=2.25A病人在急诊室内外平均逗留时间：1 1.VK=-=-h=lh=6 0 min-2 4 3病人平均等候时间：K=也夕=1 x 0.75/z=0.75/z=45 min（4）为使病人平均逗留时间不超过半小时，那么平均服务时间应减少多少?由于Ws=-i-5,平均服务时间 为：h=12min4 515-12=3min即平均服务时间至少应减少3min若医院希望候诊的病人90%以上都能有座 位,则候诊室至少应安置多少座位？设应该安置x个座位,加上急诊室的一个 座位，共有x+1个。要使90%以上的候诊病人 有座位，相当于使“来诊的病人数不多于 x+1个”的概率不少于90%,即P(N x+1)0.9尸(Nx+1)0.1（1=pm 0,1P(x+D+l 二夕x+2 0j两边取对数(x+2)lgP W IgO.1因P-=-=oIgp lg0.75所以 x26即候诊室至少应安置6个座位。二系统容量有限制的模型 M/M/1/N/8 便CF 嫌型当系统容量最大为N时，排队多于N个的顾客将被拒绝。当 N=1时，即为瞬时制，N-8时，即为容量无限制的情况。排队系统现在研究系统中有n个顾客的概率Pn(t)。对于p0(t),前面的(2)式仍然成立。学=-？+囱.(2)at对于式，当n=l,2,N-L时，仍能成立。掣=/比 at(n=l,2,-N-l)但当n二N时，有下面两种情况:情 况时刻 t的顾 客区间t,t+At时亥（I t+A t 的顾客数概率AN无离去（肯定不到达）NPn(t)*(1-U A t)BN-l一人到达（无离去）NPn l(t)*A A t=叫+九Pnt at(8)PN(t+At)=PN(r).(1-MO+PN-iA在稳态情况下有：研+=0,置.1+第+i(2+4比=。.(9)-+九R-i=解(9)式 P=p P。得：鸟=炉片Pn=P。N N N 巴=用=分=1n=0 n=0 n=0-1 1而等比数列号=0 1 一2(p Wl,n WN)(10)注：当P=1时，试讨论其概率Pn11 o其运行指标:平均队长Ls：N N人=,只=为=0 n=Q 岂l_p”N+1 P-P试证 P=1 时,Ls=N/2_lzy n.p_ p(N+D-p1 1-PR P 1-P 1-PN+1(p Wl)(2)有效到达率X e系统容量有限，当满员时，顾客将被拒绝，实际 的顾客到达率与人不一样，有效到达率为入e。可以证明：=口(1 一招)还可验证：1=忒1 R)p(N+DpN+i此种情况的公式与 前类似，只有Ls不同，入e 与人不同。耒入e必须 先求得P。或Pn才行。例2.某单人理发馆共有六把椅子接待顾客排队，无 座时将离去，顾客平均到达率为3人/h,理发时间平 均为15分钟，求：(1)求某一顾客到达就能理发的概率；(2)求需要等待的顾客数的期望值；(3)求有效到达率；(4)求一顾客在系统中的逗留时间和排队时间 平均值；(5)在可能到来的顾客中，有百分之几不等待 就离开？解：N=？N=6+l=7,入=3,u=4(1)求某一顾客到达就能理发的概率:p _ l_P _ 1 _75 _ 2778 0-l-pN+1-1-0.758-.求需要等待的顾客数的期望值:_p_(N+l)pN+i _0.75 8x0.758 _s-彳-l-pN+1-025-1-0.758-Lq=Ls-pe=2.11一(1 一品)=2.11-(1-0.2778)=1.39求有效到达率：。=Ml M)=4 X(1 0.2778)=2.89(4)求一顾客在系统中的逗留时间和排队时间平均值:顾客为何不等待b 就离去？2.因为系统已 经满员minmin 在可能到来的顾客中，有百分之几不等待就离开？P7=NP=1一,：P4=0.08790P5=0.06593P6=0.04944九九e3-2.893=0.037=0.9629=96.29%故拒绝的概率为3.71%三顾客源有限的模型M/M/1/8/m以机器修理模型为例，设有m台机器（总体），故障待修表示机器到达，修理工 是服务员。机器修好后有可能再坏，形成 循环。虽然系统没有容量限制，但系统中 的顾客也不会超过m,故又可写成：一面-1a f服务台1-m设每个顾客的平均到达率是相同的人O(这里人的含义是单台机器在单位时间里发生故障的概率或平均次数)设系统内顾客数为Ls，则系统外的顾客为mLs。对于有限源应按每个顾客单独考虑，求出其有 效到达率入e。九 e=X(m-Ls)=|Ll(l-I)这样入e是随系统内顾客数而变化的。其状态转 移图为：状态转换图由状态转移图可得状态转移方程：0状态r尸1=m 2Pon状态 J/nPn+i+2(m-n+l)_1=(m-n)2+/m状态1叫=2 Pm_ilWnWmlm用递推方法解此差分方程，并注意条件,24=1可以得到如下公式:z=0B=m z i=0ml各项运行指标为彳 口 H、Lsr T D （四+九）（1 一旦）=4 _（1E）=m-A%=叱-%=%1_尸。）例3某车间有5台机器，每台机器的连续运转时间服从负指数 分布。平均连续运转时间15分钟，有一个修理工，修理时间 服从负指数分布，平均每次12分钟。求：（1）修理工空闲时间解:/m=5,入=1/15,u=1/12,P=4/5=0.8p=1+-x0.8+-x0.82+-x0.83+-x0.84+-x0.854!3!2!1!0!120ko.8 120k0.82+-+-24 6笔蟠+12械a+12以0东i136.80.0073五台机器都出现故障的概率R=-p5R=-x0.85 x0.0073=120 x0.85 x0.0073=0.2875(m-5)!K 0 0!(3)出故障的平均台数Ls=m-(l-I)=5-|(l-0.0073)=3.76 台(4)等待修理的平均台数%=L-(1-R)=3.76-0.9927=2.77 台 平均停工时间叱=_ 及广 3,76 X 1%.9927=46 分钟(6)平均等待修理时间W-L夕/-2.77x 12/_ 34 八心“一/g(l-P0)-为.9927一 54 分钟(7)系统的有效到达率儿=2(m-4)=XI-)=0.0827即该工人每小时可修理机器的平均数为0.082760=4.96台.(8)评价这些结果机器等待过长，忙期长，应增加维修工人 或提高效率。圜间筹思1 4多服务台的排队模型一.标准的M/M/C模型标准的M/M/C模型特征规定同M/M/1。另外规 定各服务台工作相互独立且平均服务率相同尸 U 2=H 3=.=整个服务机构的平均服务率为Cu(n c)nu(ncn cU 2/z n 仇(n+1)/c/z c/状态转移图中：1转移到0,即系统中有一名顾客被 服务完离去的转移率为 Pi状态2转移到1,这就 是在2个服务台上被服务的顾客有1个被服务完离 去。因为不限哪一个，那么这时的状态转移率为2 同理考虑n转移n-1的情况。时,转移率为 n ppn 时，有c个服务台，最多有c个顾客被 服务,C个等待，则这时状态转移率为C4P,NP=2Po(H+1)4P+1+=(2+H Pn(in c)00Ea=1，且1i=0Pl=九 Po(+1)P+1+=(2+n2Pn(xn c)=1,/?0p b+匕-+(/ln!PnAi a”力一6 Jn-c4Pa(n c)系统运行指标求得如 下：LqT,2Ls=L+一00=Z(C)P”=n=c+l(cpY pd(l-p)受Po以4Ws42二.M/M/c/k顾客来到的时间间隔S服从参数2的负指 数分布服务员为顾客服务时间服从参数的 指数分布，C个服务台，系统容量为k的等待 制排队模型.因为是多服务台，系统容量为左，即系统 状态为时，当V。时，c-个服务台空 闲夕淮上 时，服务台正忙着有 个正等候着，在某一时刻一顾客到达时，系统中左 已有 个顾客，那么这个顾客就被拒绝