(完整)2011数学建模排队论

数学建模之排队论ChinaUndergraduateMathematicalContestinModeling建模群号：617711621.CUMCM的历年赛题浏览：1992年:(Ａ)作物生长的施肥效果问题(北理工：叶其孝）

(B)化学试验室的实验数据分解问题（复旦：谭永基）1993年:(Ａ)通讯中非线性交调的频率设计问题（北大:谢衷洁）

(Ｂ)足球甲级联赛排名问题（清华：蔡大用）1994年:(Ａ)山区修建公路的设计造价问题（西电大：何大可）

(Ｂ)锁具的制造、销售和装箱问题（复旦:谭永基等）1995年:(Ａ)飞机的安全飞行管理调度问题（复旦:谭永基等）

(Ｂ)天车与冶炼炉的作业调度问题（浙大:刘祥官等）

一、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%。农业类：１个题，占3.1%。工程设计类:3个题，占9.4%。交通运输类：4个题，占12.5%经济管理类：5个题，占15.6%生物医学类：5个题，占15.6%社会事业类:6个题，占18.8%

有的问题属于交叉的，或者是边缘的。

一、CUMCM历年赛题的简析3、从问题的解决方法上分析

从问题的解决方法上分析，涉及到的数学建模方法：几何理论、组合概率、统计(回归)分析、优化方法（规划）、图论与网络优化、层次分析、插值与拟合、差分方法、微分方程、排队论、模糊数学、随机决策、多目标决策、随机模拟、灰色系统理论、神经网络、时间序列、综合评价、机理分析等方法。

一、CUMCM历年赛题的简析

用的最多的方法是优化方法和概率统计的方法.

用到优化方法的共有22个题，占总数的68.8%，其中整数规划4个，线性规划6个，非线性规划14个,多目标规划6个。用到概率统计方法的有16个题，占50%，平均每年至少有一个题目用到概率统计的方法。用到图论与网络优化方法的问题有6个；用到层次分析方法的问题有３个；3、从问题的解决方法上分析

一、CUMCM历年赛题的简析

用到插值拟合的问题有6个；用到神经网络的4个；用灰色系统理论的4个;

用到时间序列分析的至少2个;

用到综合评价方法的至少3个；机理分析方法和随机模拟都多次用到;

其他的方法都至少用到一次。大部分题目都可以用两种以上的方法来解决,即综合性较强的题目有26个，占81.3%。3、从问题的解决方法上分析

一、CUMCM历年赛题的简析两个引例：

问题1:校园网的设计和调节收费问题随着计算机技术的飞速发展，校园信息网已经在全国高校中普及。某高校拟建一个校园信息网，并与Internet连接，用户可以通过网络通信端口拨号上网。因此，需要用户的数量，研究通信端口的设计规模。问题1:校园网的设计和调节收费问题通常的通信端口分为16口，32口，64口，128口。实际中，随着通信端口数量的增加，其成本费将成倍增加。如何根据实际情况，在保证基本满足用户需求的条件下，确定合适的通信端口数，以减少费用的开支和资源的浪费。当网络建成以后。为了保证用户有效的使用信息网，必须要通过适当的收取线路调节费，以控制上网时间。问题1:校园网的设计和调节收费问题一般认为，采用分段计时收费比较合理，例如按上网时间长短分为“免费－半费－全费－2倍－3倍－4倍……”等时段。现在的问题是：（1）假设有m个用户，每个用户每天（按16h计算）平均上网1.5h，试确定通信端口数n与m的比例问题1:校园网的设计和调节收费问题（2）假设m＝150，按所设定的通信端口数n，试讨论平均每天每个用户上网1h，2h，3h，4h，5h的可能性，出现因线路忙，导致用户想上网而上不去产生抱怨的可能性，以及通信端口的平均使用率；（3）为了控制上网时间，学校要求适当收取线路调节费，试给出一种合理的分段计时收费方案。问题2:眼科病床的合理安排问题09B医院是一个复杂的系统，病人从挂号、就诊、划价、取药需遍历每一个服务机构,当某项服务的现有需求超过提供该服务的现有能力时,排队现象就会发生,由于患者到达时间和诊治患者所需时间的随机性,可控性小,排队几乎不可避免。因此如何合理科学安排医护人员及医疗设备,使医院不会盲目增加医生和设备造成不必要的空闲,形成资源浪费,又使患者排队等待时间尽可能减少,如何在这两者之间取得平衡,以便提高服务质量,降低服务费用,这是现代医院管理者必须面对的课题。问题2:眼科病床的合理安排问题09B本题给出了病床数与眼科手术类别及要求，附录中还提供了一段时间的统计数据，要求回答五个问题。（1）确定合理的评价指标评价该问题的病床安排模型，即评价FCFS模型；（2）建立合理的病床安排模型，确定第二天应该安排那些病人入院，并用上述指标进行检验；问题2:眼科病床的合理安排问题09B

(3)通过统计分析，求得病人的入住时间的区间；（4）在周六、周日不手术时，重新计算评价指标，判断优劣后对手术时间安排做适当调整；（5）固定各类病人占用病床的比例，使得所有病人在系统内的平均逗留时间（含等待入院及住院时间）最短。CUMCM09年B题

“眼科病床的合理安排”主要考点：1.分布拟合检验；2.合理的评价指标体系；3.仿真方法应用；4.满足一定置信度的统计预测模型的建立；5.排队论优化模型的建立。排队论(QueuingTheory)

排队论（queuing),也称随机服务系统理论，是运筹学的一个主要分支。

1909年，丹麦哥本哈根电子公司电话工程师A.K.Erlang的开创性论文“概率论和电话通讯理论”标志此理论的诞生。排队论的发展最早是与电话，通信中的问题相联系的，近年来在计算机通讯网络系统、交通运输、医疗卫生系统、库存管理、作战指挥等各领域中均得到应用。排队论前言基本概念到达时间间隔分布和服务时间分布M/M/1单服务台的排队系统M/M/c多服务台的排队系统校园网的设计和调节收费问题

排队是我们在日常生活和生产中经常遇到的现象。例如，上、下班搭乘公共汽车；顾客到商店购买物品；病员到医院看病；旅客到售票处购买车票；学生去食堂就餐等就常常出现排队和等待现象。前言

除了上述有形的排队之外，还有大量的所谓“无形”排队现象。如几个顾客打电话到出租汽车站要求派车，如果出租汽车站无足够车辆、则部分顾客只得在各自的要车处等待，他们分散在不同地方，却形成了一个无形队列在等待派车。

前言

排队的不一定是人，也可以是物：例如，通讯卫星与地面若干待传递的信息；生产线上原料、半成品等待加工；因故障停止运转的机器等待修理；码头的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋等等。前言

上述各种问题虽互不相同，但却都有要求得到某种服务的人或物和提供服务的人或机构。排队论里把要求服务的对象统称为“顾客”,提供服务的人或机构称为“服务台”或“服务员”。前言图1单服务台排队系统（去代售点买火车票）前言不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图1至图5。图2单队列——S个服务台并联的排队系统（找工作）图3S个队列——S个服务台的并联排队系统（火车站买火车票）前言图4单队——多个服务台的串联排队系统（报名）

图5多队——多服务台混联网络系统（体检）前言图6随机服务系统前言一般的排队系统，都可由下面图加以描述。通常称由图6表示的系统为一随机聚散服务系统。任一排队系统都是一个随机聚散服务系统。“聚”表示顾客的到达，“散”表示顾客的离去。

面对拥挤现象，人们总是希望尽量设法减少排队，通常的做法是增加服务设施。但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费。如果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响。前言

顾客排队时间的长短与服务设施规模的大小，就构成了设计随机服务系统中的一对矛盾。如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾。这就是随机服务系统理论——排队论所要研究解决的问题。前言一、排队系统的组成与特征排队系统一般有三个基本组成部分：1.输入过程；2.排队规则；3.服务机构。§1排队系统的基本概念输入即为顾客的到达，可能有下列情况：

1）顾客源可能是有限的，也可能是无限的。

2）顾客是成批到达或是单个到达。

3）顾客到达间隔时间可能是随机的或确定的。

4）顾客到达可能是相互独立或关联的。所谓独立就是以前顾客的到达对以后顾客的到达无影响。

5）输入过程可以是平稳的（stationary）或说是对时间齐次的（Homogeneousintime），也可以是非平稳的。输入过程平稳的指顾客相继到达的间隔时间分布和参数（均值、方差）与时间无关；非平稳的则是与时间相关，非平稳的处理比较困难。

1.输入过程排队规则指服务台从队列中选取顾客进行服务的顺序。可以分为损失制、等待制、混合制3大类。

(1)损失制。这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为损失制。2.排队规则

(2)等待制。指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。例如，排队等待售票，故障设备等待维修等。等待制中，服务台在选择顾客进行服务时，常有如下四种规则：

①先到先服务（FCFS）。按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形。②后到先服务（LCFS）。仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。2.排队规则

③随机服务（RAND）。即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。

④优先权服务（PR）。如老人、儿童先进车站；危重病员先就诊；遇到重要数据需要处理计算机立即中断其他数据的处理等，均属于此种服务规则。2.排队规则

(3)混合制．这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：

①队长有限。当排队等待服务顾客人数超过规定数量时，后来顾客就自动离去，另求服务。如水库的库容、旅馆的床位等都是有限的。2.排队规则

②等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客自动离去，不再回来。如易损坏的电子元器件的库存问题，超过一定存储时间被自动认为失效。又如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。2.排队规则

③逗留时间(等待时间与服务时间之和)有限。例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t时，若在这个时间内未被击落，也就不可能再被击落了。不难注意到，损失制和等待制可看成是混合制的特殊情形，如记c为系统中服务台的个数，K为系统容量,则当K=c

时，混合制即成为损失制；当K=∞时，混合制即成为等待制。2.排队规则3.服务机构

1）服务机构可以是单服务员和多服务员服务，这种服务形式与队列规则联合后形成了多种不同队列，不同形式的排队服务机构。如前图1到5：2)服务方式分为单个顾客服务和成批顾客服务。3)服务时间分为确定型和随机型。4)服务时间的分布在这里我们假定是平稳的。：上述特征中最主要的、影响最大的是：顾客相继到达的间隔时间分布服务时间的分布服务台数1953年D.G.Kendall提出了分类法，称为Kendall记号(适用于并列服务台)即：X/Y/Z/d/e/f其中：X——顾客相继到达间隔时间分布Y——服务时间分布，X和Y主要有以下几种分布二、排队系统的描述符号与模型分类M—负指数分布Markov，D—确定型分布Deterministic，

Ek—K阶爱尔朗分布Erlang，

GI—一般相互独立随机分布

(GeneralIndependent)，G—一般随机分布。Z——并列的服务台数d——排队系统的最大容量e——顾客源数量f——排队规则如M/M/1/

∞/∞/FCFS即为顾客到达为泊松过程，服务时间为负指数分布，单台，无限容量，无限源，先到先服务的排队系统模型。三、排队论研究的基本问题

1.系统性态问题:即研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布和忙期分布等统计指标,包括了瞬态和稳态两种情形。

2.最优化问题：即包括最优设计(静态优化)，最优运营（动态优化）。

3.排队系统的统计推断:即通过对排队系统主要参数的统计推断和对排队系统的结构分析，判断一个给定的排队系统符合哪种模型，以便根据排队理论进行研究。

四排队问题求解(主要指性态问题)求解一般排队系统问题的目的主要是通过研究排队系统运行的效率指标，估计服务质量，确定系统的合理结构和系统参数的合理值，以便实现对现有系统合理改进和对新建系统的最优设计等。排队问题求解的一般步骤：

1.确定或拟合排队系统顾客到达的时间间隔分布和服务时间分布(可实测)。

2.研究分析排队系统理论分布的概率特征。

3.研究系统状态的概率。系统状态是指系统中顾客数。状态概率用Pn(t)表示,即在t时刻系统中有n个顾客的概率，也称瞬态概率。求解状态概率Pn(t)方法是建立含Pn(t)的微分差分方程，通过求解微分差分方程得到系统瞬态解，由于瞬态解一般求出确定值比较困难，即便求得一般也很难使用。因此常常使用它的极限(如果存在的话)：稳态的物理意义图，系统的稳态一般很快都能达到，但实际中达不到稳态的现象也存在。要注意的是求稳态概率Pn并不一定求t→∞的极限,只需求Pn’(t)=0。过渡状态稳定状态pnt图3排队系统状态变化示意图称为稳态(steadystate)解，或称统计平衡状态(StatisticalEquilibriumState)的解。

4.求用以判断系统运行优劣的基本数量指标的概率分布或特征数。数量指标主要包括:(1)平均队长（Ls）:系统中顾客数的期望值。平均队列长（Lq）:系统中排队等待服务顾客数的期望值。(2)平均逗留时间(Ws):一个顾客在系统中停留时间的期望值。平均等待时间(Wq):一个顾客在系统中排队等待时间的期望值。(3)忙期：指从顾客到达空闲服务机构起到服务机构再次空闲这段时间长度。（忙期和一个忙期中平均完成服务顾客数都是衡量服务机构效率的指标，忙期关系到工作强度）(4)损失率：由于系统的条件限制，使顾客被拒绝服务而使服务部门受到损失的概率

5.排队系统指标优化含优化设计与优化运营。课间休息§2到达间隔时间分布和服务时间分布一个排队系统的最主要特征参数是顾客的到达间隔时间分布与服务时间分布。要研究到达间隔时间分布与服务时间分布需要首先根据现存系统原始资料统计出它们的经验分布，然后与理论分布拟合，若能照应，我们就可以得出上述的分布情况。一、经验分布经验分布是对排队系统的某些时间参数根据经验数据进行统计分析，并依据统计分析结果假设其统计样本的总体分布，选择合适的检验方法进行检验，当通过检验时，我们认为时间参数的经验数据服从该假设分布。分布的拟合检验一般采用χ2检验。由数理统计的知识我们知：若样本量n充分大(n≥50)，则当假设H0为真时，统计量总是近似地服从自由度为k-r-1的χ2分布，其中k为分组数，r为检验分布中被估计的参数个数。式中：fi——实际频数

ni——理论频数上面方法的应用必须注意n要足够大，npi不能太小。一般地n要大于50，而分组的npi应不小于5。例题：某公共汽车站，统计来站的乘客流，规定每隔1分钟统计一次乘客到达情况，共统计100次，其结果如表所示，问顾客是否服从泊松流？当时，在显著水平α下接受假设H0解：先估计分布的参数λ，由极大似然估计法得：,并根据公式可计算出理论频率、理论频数及项见下页表所示查表知:故可接受泊松分布假设。∑=6.2815K-r-1=8-1-1随机变量数

随着实验的结果的不同而变化离散型：

的所有可能只有限或至多可列个连续型：

（

）取值于某个区间（a，b）分布函数(连续):

的概率分布(离散):i=1,2,3……二、概率论知识复习数学期望:(离散)E(ξ)=

(连续)E(ξ)=

方差:=条件概率:密度函数:(连续),,三、理论分布

式中λ为常数(λ>0)，称X服从参数为λ的泊松分布，若在上式中引入时间参数t，即令λt代替λ，则有：

1.泊松分布

在概率论中，我们曾学过泊松分布，设随机变量为X，则有：n=0,1,2,…（1）与时间有关的随机变量的概率，是一个随机过程，即泊松过程。t>0，n=0,1,2,…（2）（t2>t1，n≥0）

若设N(t)表示在时间区间[0,t)内到达的顾客数(t>0),Pn(t1,t2)表示在时间区间[t1,t2)(t2>t1)内有n(≥0)个顾客到达的概率。即：

在一定的假设条件下，顾客的到达过程就是一个泊松过程。当Pn(t1,t2)符合下述三个条件时，顾客到达过程就是泊松过程(顾客到达形成泊松流)：①

无后效性：各区间的到达相互独立,即Markov性。也就是说过程在t+Δt所处的状态与t以前所处的状态无关。②平稳性：即对于足够小的Δt，有：在[t,t+Δt]内有一个顾客到达的概率与t无关,而与Δt成正比。

③

普通性：对充分小的Δt,在时间区间（t,t+Δt）内有2个或2个以上顾客到达的概率是一高阶无穷小.由此知，在(t，t+Δt)区间内没有顾客到达的概率为：令t1=0,t2=t,则P(t1,t2)=Pn(0,t)=Pn(t)

λ>0是常数，它表示单位时间到达的顾客数，称为概率强度。即P0+P1+P≥2=1在[0，t+Δt]内到达n个顾客应是上面三种互不相容的情况之一，所以有：为了求Pn(t),即Pn(0,t)，需要研究它在（t，t+Δt）上的改变量,建立Pn(t)的微分方程。对于区间[0,t+Δt)可以分成[0，t)和[t，t+Δt),其到达总数是n，不外有下列三种情况：令Δt→0取极限（并注意初始条件）得：………(3)当n=0时，没有B，C两种情况，则：………(4)凑微分区间长度（0，0）有n个顾客到达(0,t)有n-1,n-2个顾客到达∴

C

=0（3）式两端乘et并移项得：∴……(5)（没有顾客到达的概率）两边积分得：代入初始条件(t=0)有：P0(0)=1将n=1,2,3…代入（6）得：∴………(6)(注意利用(5)式)凑成Pn(t)et两项乘积的微分两边积分如此继续递推下去得：∴（2个顾客到达的概率）（n个顾客到达的概率）即随机变量N(t)=n服从泊松分布。它的数学期望和方差为：∴（1个顾客到达的概率）∴令k=n-1，则：即：同理方差为：顾客到达过程是一个泊松过程(泊松流)。其概率密度函数为：t>0

2.负指数分布当输入过程是泊松流时，我们研究两顾客相继到达的时间间隔的概率分布。设T为时间间隔，分布函数为FT（t），则：FT（t）=P{T≤t}

此概率等价于在[0，t）区间内至少有1个顾客到达的概率。∴t>0

∵没有顾客到达的概率为：(由（5）式而来)间隔：间隔：间隔对分布函数微分

λ表示单位时间内顾客平均到达数。

1/λ表示顾客到达的平均间隔时间。可以证明，间隔时间T独立且服从负指数分布与顾客到达形成泊松流是等价的。对顾客的服务时间

：系统处于忙期时两顾客相继离开系统的时间间隔，一般地也服从负指数分布，设：即T服从负指数分布，它的期望及方差为：接受服务，然后离开服务时间的分布：其中：μ表示单位时间内能被服务的顾客数，即平均服务率。

1/μ表示一个顾客的平均服务时间。

3.爱尔朗(Erlang)分布设v1,v2，…,vk是k个独立的随机变量，服从相同参数

k

的负指数分布，那么：，则令，则ρ称为服务强度。

串列k个服务台，每台服务时间相互独立，服从相同负指数分布（参数k

），那么一顾客走完k个服务台总共所需要服务时间服从上述k阶Erlang分布。则称T服从k阶爱尔朗分布。其特征值为：,其概率密度是1/kμ表示一个顾客一个服务台的平均服务时间。课间休息对排队模型，在给定输入和服务条件下，主要研究系统的下述运行指标：

(1)系统的平均队长Ls(期望值)和平均队列长Lq(期望值)；

(2)系统中顾客平均逗留时间Ws与队列中平均等待时间Wq；

本节研究M/M/1模型，下面分三种情况讨论：

§3M/M/1单服务台的排队系统

一、标准的M/M/1模型

M/M/1/∞/∞/FCFS模型系统中有n个顾客1.稳态概率Pn的计算

在任意时刻t，状态为n的概率Pn(t)（瞬态概率），它决定了系统的运行特征。已知顾客到达服从参数为λ的泊松过程，服务时间服从参数为μ的负指数分布。现仍然通过研究区间[t，t+Δt）的变化来求解。在时刻t+Δt，系统中有n个顾客不外乎有下列四种情况（[t，t+Δt）内到达或离开2个以上没列入）。？由于这四种情况是互不相容的，所以Pn(t+Δt)应是这四项之和，则有：所有的高阶无穷小和并令Δt→0，得关于Pn(t)的微分差分方程：……(1)当n=0时，只有表中的（A）、（B）两种情况，因为在较小的Δt内不可能发生（D）（到达后即离去），若发生可将Δt取小即可。∴∴………(2)这种系统状态(n)随时间变化的过程就是生灭过程（BirthandDeathProcess）。

方程(1)、(2)解是瞬态解,无法应用。它对时间的导数为0，所以由(1)、(2)两式得：稳态时，Pn(t)与时间无关,可以写成Pn,………(3)………(4)由此可得该排队系统的状态转移图：由（4）得：其中ρ——服务强度将其代入（3）式并令n=1,2,…(也可从状态转移图中看出状态平衡方程)得：………(3)………(4)关于Pn的差分方程n-1nn+1201……

状态转移图n=1∴n=2∴以此类推…，当n=n时，………(5)∵及概率性质知：(数列的极限为)∴………(6)∴否则排队无限远系统稳态概率系统的运行指标2.系统的运行指标计算

(1)系统中的队长Ls（平均队长）(0<ρ<1)即:………(7)期望(2)队列中等待的平均顾客数Lq………(8)

(3)顾客在系统中的平均逗留时间Ws

顾客在系统中的逗留时间是随机变量，可以证明，它服从参数为μ-λ的负指数分布，分布函数和密度函数为：（w≥0）∴

(4)顾客在队列中的平均等待时间Wq

等待时间顾客在队列中的平均等待时间应为Ws减去平均服务时间。考虑LS与WS的关系四个指标的关系为(Little公式)：

3.系统的忙期与闲期系统处于空闲状态的概率：系统处于繁忙状态的概率：服务强度？？？例1某医院急诊室同时只能诊治一个病人，诊治时间服从指数分布，每个病人平均需要15分钟。病人按泊松分布到达，平均每小时到达3人。试对此排队队系统进行分析。解对此排队队系统分析如下：（1）先确定参数值：这是单服务台系统，有：

故服务强度为：（2）计算稳态概率：

这就是急诊室空闲的概率，也是病人不必等待立即就能就诊的概率。

而病人需要等待的概率则为：

这也是急诊室繁忙的概率。

（3）计算系统主要工作指标：

急诊室内外的病人平均数：

急诊室外排队等待的病人平均数：

病人在急诊室内外平均逗留时间：

病人平均等候时间：

（4）为使病人平均逗留时间不超过半小时，那么平均服务时间应减少多少？

由于

代入λ=3，解得μ≥5，平均服务时间为：

15－12＝3min

即平均服务时间至少应减少3min

(5)若医院希望候诊的病人90%以上都能有座位,则候诊室至少应安置多少座位?

设应该安置χ个座位,加上急诊室的一个座位,共有χ+1个。要使90%以上的候诊病人有座位，相当于使“来诊的病人数不多于χ+1个”的概率不少于90%，即

两边取对数

（x＋2）lgρ

≤

lg0.1

因

ρ

<

1，故

所以ⅹ≥6

即候诊室至少应安置6个座位。

二系统容量有限制的模型

M/M/1/N/∞/FCFS模型当系统容量最大为N时，排队多于N个的顾客将被拒绝。当N=1时，即为瞬时制，N→∞时，即为容量无限制的情况。现在研究系统中有n个顾客的概率Pn(t)。………(2)对于(1)式，当n=1,2,…N-1时，仍能成立。……(1)(n=1,2,…N-1)但当n=N时，有下面两种情况：对于P0(t)，前面的（2）式仍然成立。∴………(8)0N-112N-2λλλλμμμμN在稳态情况下有：………(9)解（9）式得：………∵而等比数列(ρ≠1,n≤N)……(10)∴

注：当ρ=1时，试讨论其概率Pn。(1)平均队长Ls：(ρ≠1)试证ρ=1时,Ls=N/2其运行指标：

(2)有效到达率λe

系统容量有限，当满员时，顾客将被拒绝，实际的顾客到达率与λ不一样，还可验证：∴

此种情况的公式与前类似,只有Ls不同,λe与λ不同。求λe必须先求得P0或PN才行。有效到达率为λe。

可以证明：Ls例2．某单人理发馆共有六把椅子接待顾客排队，无座时将离去，顾客平均到达率为3人/h，理发时间平均为15分钟，求：(1)求某一顾客到达就能理发的概率;(2)求需要等待的顾客数的期望值;(3)求有效到达率;(4)求一顾客在系统中的逗留时间和排队时间平均值;(5)在可能到来的顾客中，有百分之几不等待就离开？解：N=?N=6+1=7，λ=3，μ=4(1)求某一顾客到达就能理发的概率:(2)求需要等待的顾客数的期望值:(3)求有效到达率:(4)求一顾客在系统中的逗留时间和排队时间平均值:P0=0.27780P1=0.20836P2=0.15627P3=0.11720=0.9629=96.29%P4=0.08790故拒绝的概率为3.71%P5=0.06593P6=0.04944(5)在可能到来的顾客中，有百分之几不等待就离开？顾客为何不等待就离去？因为系统已经满员三顾客源有限的模型

M/M/1/∞/m以机器修理模型为例，设有m台机器(总体)，故障待修表示机器到达，修理工是服务员。机器修好后有可能再坏，形成循环。虽然系统没有容量限制，但系统中的顾客也不会超过m，故又可写成：[M/M/1/m/m]对于有限源应按每个顾客单独考虑，求出其有效到达率λe。∴这样λe是随系统内顾客数而变化的。其状态转移图为：设系统内顾客数为Ls，则系统外的顾客为m-Ls。设每个顾客的平均到达率是相同的λ。

(这里λ的含义是单台机器在单位时间里发生故障的概率或平均次数)由状态转移图可得状态转移方程：1≤n≤m-10状态n状态m状态用递推方法解此差分方程，并注意条件，可以得到如下公式：10=å=miiP(1≤n≤m)各项运行指标为：例3某车间有5台机器，每台机器的连续运转时间服从负指数分布。平均连续运转时间15分钟，有一个修理工，修理时间服从负指数分布，平均每次12分钟。求：(1)修理工空闲时间解:(1)∵m=5,λ=1/15,μ=1/12,ρ=4/5=0.8(2)五台机器都出现故障的概率台台(3)出故障的平均台数(4)等待修理的平均台数(5)平均停工时间分钟分钟机器等待过长，忙期长，应增加维修工人或提高效率。(6)平均等待修理时间(8)评价这些结果(7)系统的有效到达率即该工人每小时可修理机器的平均数为0.0827*60=4.96台.课间休息一.标准的M/M/C模型§4

多服务台的排队模型当n<c时，Pn=[λ/(nμ)]Pn-1当n

c时，Pn

=[λ/(cμ)]Pn-1标准的M/M/C模型特征规定同M/M/1。另外规定各服务台工作相互独立且平均服务率相同μ1=μ2=μ3=……=μc

=μ整个服务机构的平均服务率为cμ(n

c);nμ(n<c)令ρ=λ/（cμ）系统负荷强度系数0n12n-1λλλλμcμ2μcμn+1nn-1λλnμ(n+1)μn+1λλλλ

状态转移图中：1转移到0，即系统中有一名顾客被服务完离去的转移率为μp1，状态2转移到1

，这就是在2个服务台上被服务的顾客有1个被服务完离去。因为不限哪一个，那么这时的状态转移率为2μp2。n>cn

c同理考虑n转移n-1的情况。n

c时，转移率为nμpnn>c时，有c个服务台，最多有c个顾客被服务,n-c个等待，则这时状态转移率为cμpn用递推法解上差分方程，可求得状态概率：系统运行指标求得如下：二.M/M/c/k

顾客来到的时间间隔服从参数的负指数分布服务员为顾客服务时间服从参数的指数分布，C个服务台，系统容量为k的等待制排队模型.

因为是多服务台，系统容量为，即系统状态为时，当时，个服务台空闲。当时，服务台正忙着，有个正等候着，在某一时刻一顾客到达时，系统中已有个顾客，那么这个顾客就被拒绝进入系统。

得此模型微分差分方程组(1)稳态情况差分方程为(2)由

，解式(2)差分方程组得(3)其中

(4)(5)(6)(7)

(8)

(9)例:某火车站售票处有三个窗口，同时售各车次的车票。顾客到达服从泊松布，平均每分钟到达λ=0.9（人），服务时间服从负指数分布，平均服务率μ=24（人/h），分两种情况：1.顾客排成一队，依次购票；2.顾客在每个窗口排一队，不准串队。求:（1）售票处空闲的概率。

（2）队长和队列长。例题解析（3）平均等待时间和逗留时间。例题解析

解：1.M/M/3/∞/∞μ=0.4（人/分钟）记ρ=λ/（3μ）=0.75本题属于？n<cn>c则（1）售票处空闲的概率为：例题解析

解：1.M/M/3/∞/∞（2）队长和队列长：例题解析售票处的空闲的概率为0.0748有1个窗口空闲0.18934平均等待时间Wq=1.89分钟，平均逗留时间Ws=4.39分钟队长Ls=3.95(人)Lq=1.70(人)

2.相当于3个M/M/1/三个系统并联：λ=0.3μ=0.4ρ=λ/μ=0.75P0=1-ρ=0.25

（每个子系统）三个服务台都有空的时候，P03=0.0156Ls=ρ/(1-ρ)=3(子系统）整个系统为9Lq=Ls-λ/μ=2.25（每个子系统）Ws=Ls/λ=10Wq=Ws-1/μ=7.5例题解析故售票处空闲的概率为0.0156例题解析平均等待时间Wq=7.5分钟平均逗留时间Ws=10分钟队长

Ls=3三个队共3+3+3=9队列长Lq=2.25共6.75（人）有1个窗口空闲0.25相比之下，排一队共享三个服务台效率好课间休息§5校园网的设计和调节收费问题1.1问题的提出随着计算机技术的飞速发展，校园信息网已经在全国高校中普及。某高校拟建一个校园信息网，并与Internet连接，用户可以通过网络通信端口拨号上网。因此，需要用户的数量，研究通信端口的设计规模。§5校园网的设计和调节收费问题通常的通信端口分为16口，32口，64口，128口。实际中，随着随着通信端口数量的增加，其成本费将成倍增加。如何根据实际情况，在保证基本满足用户需求的条件下，确定合适的通信端口数，以减少费用的开支和资源的浪费。当网络建成以后。为了保证用户有效的使用信息网，必须要通过适当的收取线路调节费，以控制上网时间。§5校园网的设计和调节收费问题一般认为，采用分段计时收费比较合理，例如按上网时间长短分为“免费－半费－全费－2倍－3倍－4倍……”等时段。现在的问题是：（1）假设有m个用户，每个用户每天（按16h计算）平均上网1.5h，试确定通信端口数n与m的比§5校园网的设计和调节收费问题（2）假设m＝150，按所设定的通信端口数n，试讨论平均每天每个用户上网1h，2h，3h，4h，5h的可能性，出现因线路忙，导致用户想上网而上不去产生抱怨的可能性，以及通信端口的平均使用率；（3）为了控制上网时间，学校要求适当收取线路调节费，试给出一种合理的分段计时收费方案。1.2问题的分析与假设根据题目中给出的信息，我们可以用排队论来研究这个问题。假设校园信息网络和用户构成一个排队系统，网络的通信端口为服务台，个数为n，用户为顾客，顾客源数为m，平均忙期为16h（即一天连续工作时间）但是要注意到：实际中不限制用户的上网次数，虽然实际用户数为m，但我们可以认为顾客总体是无限的。§5校园网的设计和调节收费问题另一方面，在同一时间，当n个用户端全部被占用时，再有用户上网，系统将会拒绝。此时，用户将产生抱怨，只有当网上的用户下网后才能有新的用户上网，可以这样周而复始的进行下去。这表明，只要时间允许，系统不限制上网人数，但不允许顾客在系统内排队等候，即系统的服务是即时制的。给出如下几个假设：§5校园网的设计和调节收费问题(1)每个用户的上网是随机、且相互独立的，单位时间的平均到达（上网）率为；(2)n个通信端口的使用是随机独立的，即任一用户可以使用空闲的任一端口，单位时间的平均服务（上网人数）率为；(3)不限制用户每天的上网次数，即顾客接受一次服务后仍回到服务总体；(4)学校对用户一般要收取一定数量的线路基本费，在模型中不考虑此费用；(5)学校的目的不是营利，完全是为了调节线路，控制上网时间。因此，不需要追求经济利益。§5校园网的设计和调节收费问题1.3模型的建立与求解由上面分析，假设用户平均上网的人数（即顾客平均到达率）服从于参数为的泊松分布，平均上网时间服从参数为的指数分布，故问题的排队模型为M/M/n/n/问题(1):已知每个用户每天平均的上网1.5h则每天的总上网时间为T=1.5m(h)§5校园网的设计和调节收费问题一天按16h计算，根据题意，要求在基本满足需要的条件下节省费用，通讯端口数尽量少为好。为此，设想让所有的端口满负荷运转，则每天每个通信端口占用的时间为

故，即通信端口数n与用户数m的比为，与实际中通常采用1：10相符§5校园网的设计和调节收费问题问题(2)：由问题1的结果，当m＝150时，通信端口数n＝16.由假设1，用户的平均上网率为.由假设2，各端口的平均服务率（单位时间上网人数）为，即每个用户平均上网时间为t＝1/记＝P｛系统的状态为k｝（k＝0,1,2……，n）（k个用户在网上）则由§4,二(2)式，可得状态平衡方程为§5校园网的设计和调节收费问题

,其中解方程，得到其中而且通信端口的平均使用数为§5校园网的设计和调节收费问题§5校园网的设计和调节收费问题系统满员的概率为于是，通信端口有空闲用户能上网的概率为当(人/h)，n＝16，平均每天单个用户上网1h、1.5h、2h、3h、4h、5h，即，计算结果如下表：10.014666710.9853339.23752/30.1163520.88364812.42631/20.2574030.74259713.92371/30.4671740.53282614.98571/40.5906680.40933215.351/50.6687930.33120715.5253§5校园网的设计和调节收费问题问题3根据问题的要求，采用分段计时收费方案。分为“免费－半费－全费－2倍－3倍……”等时段，首先应确定免费时段。按m＝150人，n＝16口保证平均每天每端口为150/16＝9.375人次，平均上网时间大约为1.7h。为了保证一定的可靠性，同时考虑到问题1中的端口设计按照1.5h设计。于是,不妨确定免费上网时间为1.5h，则抱怨概率为§5校园网的设计和调节收费问题§5校园网的设计和调节收费问题满员的概率为随着时间t＝1/的增大，也增大，因此按照随时间t对增加的倍数来确定对应的上网时间段.由和可以求出根据问题2中的结果，拟合数据得到的近似表达式，则得到分段计时收费的时间段为：于是可以得到分段收费方案：t<1.5时，免费；1.5t<1.7时，半费2.4t<3.4，全费；3.4t<5.2，2倍5.2t<6.1，4倍，t6.1，依此类推§5校园网的设计和调节收费问题x=[0.014666710.1163520.2574030.4671740.5906680.668793];>>y=[11.52345];>>y1=interp1(x,y,0.346774)y1=2.42601.4两点说明（1）实际中，用户上网数量的多少一定与时间有关系，早中晚的人数一定是不均衡的，因此，因在收费方案中考虑时间因素。对早上、上午、中午、下午、晚上分时间段赋予不同权重。得到“分段加权计时”的收费方案；（2）实践证明该模型是符合实际的，并且具有一定的应用和推广价值。§5校园网的设计和调节收费问题

排队论主要知识点排队系统的组成与特征,模型分类顾客到达间隔时间和服务时间的分布稳态概率Pn的计算标准的M/M/1模型([M/M/1/

∞/∞/FCFS])