第八章排队论。
排队（queue）是社会活动中经常遇到的现象，如顾客到商店购物，学生去图书馆借书，病人上医院看病，仪器等待维修等等，当售货员、图书管理员、医生和修理员的数量满足不了顾客或病人及时服务的需要时，就出现了排队等待的现象．由于接受服务的顾客数和服务时间的随机性，排队现象是不可避免的．当然增加服务能力可以减少排队现象，但这样势必增加投资，有时因供大于求造成资源浪费．因此，在这样一个排队系统中，作为管理人员不但需要了解排队等待服务的顾客数，等待服务时间长度，系统内服务设施的空闲率等数量指标的变化规律，而且需要在满足顾客服务基本要求的条件下，研究如何提高服务质量、降低排队系统运行成本等问题．排队论就是解决这类问题的一门科学．在排队系统中要求得到某种服务的对象统称为顾客（customer），为顾客服务者统称为服务台（service facility）．根据顾客和服务台的不同情况，组成不同的排队系统．本章研究的主要内容是排队系统的状态概率、队长、等待时间、服务时间、服务台利用效率等运行指标，以及排队系统的优化问题．
第一节排队系统的基本概念。
一、排队系统的组成。
一个排队系统或称服务系统（service system），有三个基本组成部分：即输入过程（arrival process ）、排队规则（queue discipline）和服务规则（service discipline）．图8-1给出了排队系统的一般结构．
1． 输入过程：指顾客到达排队系统的规律，可用到达时间间隔或单位时间内顾客到达数的概率分布来描述；按到达的时间间隔分有确定的时间间隔和随机的时间间隔；按顾客到达的方式有单个到达和成批到达；从顾客源总体看，分有限源总体和无限源总体．
2．排队规则：排队系统一般分为等待制、损失制和混合制．
1) 等待制顾客到达系统时，如果服务台没有空闲，则顾客排队等候服务．等待**务的方式有：
1 先到先服务（first come first service，fcfs）：按顾客到达先后给予服务，这是最常见的服务规则．
2 后到先服务（last come first service，lcfs）：如情报收集中最后到达的信息最有价值，往往最先采用．
3 优先权服务（priority，pr）：如医院对危重病人给予优先**．
4 随机服务（service in random order，siro）：排队系统随机抽取等待服务的顾客．
2) 损失制顾客到达系统时，如果服务台没有空闲，则顾客离去，另求服务．如没有足够医生或医疗器械救治急诊患者，医院药物、卫生材料暂缺等．
3) 混合制它是介于等待制和损失制之间的形式．方式有：
1 队伍长度有限，当队伍的长度小于时，新到顾客就排队等待；当队伍长度为时，新来顾客离去．如患者住院所需要的病床数有限就属此类．
2 等待时间有限，新到顾客排队等候服务，一段时间后仍未得到服务，顾客离去．例如医院血库的血浆、生物制剂等．
3 逗留时间（等待时间与服务时间之和）有限，顾客在系统中的逗留时间不得超过确定的时间．例如药品的有效期．
3．服务机构：指排队系统中服务台的个数、排列及服务方式．
排队系统中服务台的个数可以是一个或多个．多个服务台可以是串联或并联．排列结构大体有：
1) 单服务台、单列。
2) 多服务台、单队列（多队列）
3) 多服务台串列。
4) 多服务台混合。
医院里的ct室就是(1)的例子，口腔科、理疗室就是(2)的例子，先**候诊再住院手术就是(3)或(4)的例子．
服务方式上有单个服务，也有成批服务的，如医院里的上下电梯．
二、排队系统的评价指标。
排队论研究的问题，可以分成两大类，第一类问题是在服务设施设置之前，根据顾客输入过程与服务过程的要求，结合对系统的一定数量指标与服务过程要求（如规定服务质量的必需水平），确定服务设施（如诊断室、检验科、**中心等等）的规模；第二类问题是对已有的服务系统施以最优控制，改进和提高排队系统工作效率．
排队系统的数量指标主要有：
1． 单位时间内到达的顾客数的期望值，即单位时间内的平均到达率，记作．而表示相邻两个顾客到达的平均间隔时间．
2． 单位时间内服务的顾客数的期望值，即单位时间内顾客的平均离去率，记作．同样，表示每个顾客的平均服务时间．
3． 在时刻时排队系统中恰有个顾客的概率，显然为系统空闲率．
4． 系统内的平均顾客数称为队长（queue length），记作．
5． 系统内排队等待服务的平均顾客数称为等待队长，记作．
6．顾客从进入系统到接受完服务后离开系统的平均时间称为平均逗留时间，记作．
7．顾客在系统内排队等待服务的平均时间称为平均等待时间(waiting time)，记作．
三、排队模型的符号表示。
由于排队系统的特征可以有许许多多的组合，从而形成不同的排队模型．本章采用///形式表示不同排队模型．其中：
——顾客到达间隔时间概率分布。
——服务时间的概率分布。
——服务台数。
——顾客源总数。
——系统内顾客的容量。
例如： /1 / 12排队模型的特点是：顾客到达间隔时间和服务时间均服从负指数分布（指负指数分布，具有无记忆性，即markov性），单服务台，顾客**总体数无限，系统的顾客容量为12．
四、排队系统的常见分布。
顾客到达和离开分别构成排队系统的输入与输出过程流．到达分布和离开分布确定了到达系统和离开系统的顾客数这两个随机变量的分布．求解排队系统有关数量指标问题，首先要确定顾客到达流的概率分布，即在一定的时间间隔内来个顾客的概率是多大．其次是要确定顾客离开流的概率分布，即在一定的时间内服务完个顾客的概率是多大．实际问题研究中，可根据原始资料测算顾客在单位时间平均到达流的经验分布，然后按照统计学的方法（例如，检验法）确定资料适合于哪种理论分布，并估计理论分布的参数值，这是确定排队模型的前提．
1．泊松分布（poisson distribution）
在排队论中，最基本的排队模型是在给定时间内到达系统的顾客数服从泊松分布，即顾客到达流是泊松流（也称最简单流）．它具有如下性质：
1) 平稳性：在时间△内，到达个顾客的概率只与△和的大小有关，而与时刻起点无关．
2) 无后效性：在时间△内到达个顾客的概率与起始时刻之前到达多少个顾客无关．
3) 普通性：对于充分小的时间间隔△，在时间△内最多有一个顾客到达系统．即在时间△内有2个或2个以上顾客到达的概率极小，有。
可以证明，在长为的时间内到达个顾客的概率为：
当时，即单位时间内到达个顾客的概率为：
其中为单位时间内到达系统的顾客的期望值．
2．负指数分布(negative exponential distribution)
理论上可以证明若顾客在单位时间内到达系统的个数是服从参数为的泊松分布，则顾客到达系统的间隔时间服从参数为的负指数分布，反之亦然．即同一随机过程可从两种不同的角度用两种分布来描述．负指数分布的概率密度为：
间隔时间的期望值。
同样，对顾客服务时间常用的概率分布也是负指数分布，概率密度为：
其中表示单位时间内完成服务的顾客数，也称平均服务率．
例8-1 某医院外科手术室任意抽查了100个工作小时，每小时患者到达数的出现次数如表8-1，问每小时患者的到达数是否服从泊松分布．
表8-1 患者在单位时间内到达数的频数分布。
解依题意，每小时患者平均到达率(人/小时)．现检验这个经验分布是否适合的泊松分布，利用检验法：
假设该经验分布适合的泊松分布．
计算统计量，结果如表8-2．
表8-2 泊松分布的拟合检验。
接受假设，即患者到达数的经验分布适合的泊松分布．
第二节单服务台// 1排队模型。
/ 1排队系统是指顾客的到达为最简单流，即顾客到达间隔时间和服务时间均服从负指数分布的单服务台排队系统（single channel system）．根据顾客源和系统容量的不同情况，该模型主要有// 1 / 型、//1 / 型、//1 / 型三种．排队规则适用于fcfs、lcfs和siro．
一、//1/∞/模型。
1．模型条件已知单位时间平均到达率和平均服务率，顾客源无限，容量无限，单列，fcfs排队规则．
2．系统的状态概率和主要运行指标。
1) 系统的状态概率。
对于负指数分布系统的状态概率可以通过图8-7所示的状态转移来求得系统处于稳定状态下的概率（系统内有个顾客的概率）．
在图8-7中，椭圆圈中的数字表示系统的状态（顾客数），箭头表示从一个状态到另一个状态的转移．当系统处于稳定状态时，对于每个状态来说，转入率与转出率相等．例如对于状态（），有：
而状态0，有，因此。
当时，将代入（8-2）得：
解出。设，则有
类似可得。一般地。
由概率性质知，，即，当时，有：
我们称为系统的空闲概率，为利用率（utilization rate）（服务台处于繁忙状态的概率）．
2) 系统的主要运行指标。
由（8-3）可以算出系统的主要运行指标．
系统内的平均顾客数，队长。
系统内等待服务的平均顾客数，等待队长。
任何排队模型，当系统在稳定状态时，系统内顾客逗留的平均时间和顾客等待服务的平均时间与队长、等待队长满足little公式：
证明略8-4）
管理运筹学有关最优方案的案例分析报告
第一部分。一 案例名称 北方印染公司应如何合理使用技术培训费。二 案例目的 确定培养方案，使企业增加的产值最多。三 案例分析 由案例给出的信息，可以设十三个变量，分别为x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13。其分别代表的含义是，第一年由高中生培养初级工的...