运筹学教材(第六章-排队论)ppt课件(全)

1、运 筹 学运筹学（普通高等教育“十二五”经济与管理类专业核心课程规划教材） 主编：郭鹏出版社：西安交通大学出版社出版时间：2013-12-01 绪论 第1章 线性规划 第2章 线性规划的对偶理论 第3章 特殊线性规划 第4章 动态规划 第5章 图与网络分析 第6章 排队论 第7章 库存论 第8章 决策论 第9章 对策论运 筹 学 6.1 排队系统的特征与基本排队系统 6.2 单服务台指数分布排队系统 6.3 多服务台指数分布排队系统 6.4 一般服务时间的排队系统 6.5 排队系统的优化 6.6 案例分析 第6章 排队论郭鹏制作 6.1.1 排队系统及其组成 图6-1 排队系统基本模型 排队系

2、统都有三个基本组成部分：（1）输入过程：顾客按怎样的规律到达（2）排队规则：顾客接受服务的先后次序问题（3）服务机构：服务机构的特征主要包括：服务台数目和服务时间的分布6.1 排队系统的特征与基本排队 输入过程需要三个方面的内容：（1）顾客的总体数或顾客源数：可能到达服务机构的顾客总数（2）顾客到达的类型：顾客是单个到达，还是成批到达（3）顾客相继到达的时间间隔分布：顾客相继到达服务台，常常服从某种统计规律，如定长分布(D)，负指数分布(M)，K阶爱尔朗分布(Ek)等6.1.1 排队系统及其组成 排队规则所研究的是顾客接受服务的先后次序问题，可分几种情形来讨论：（1）损失制：顾客到达时，如果所

3、有的服务台都正被占用，而顾客随即离去，不再接受服务。（2）等待制：顾客到达时，如果所有的服务台都正被占用，而顾客排队等待服务。先到先服务(FCFS)；后到先服务(LCFS)；随机服务(SIRO)；优先权服务（PR）。（3）混合制：混合制是损失制和等待制的结合。队长有限制；排队等待时间有限制。6.1.1 排队系统及其组成 服务机构的特征主要包括：服务台数目和服务时间的分布。在多个服务台时，是串联还是并联；对顾客是逐个进行服务还是成批服务。服务时间所遵循的分布有：定长分布（D），指数分布(N)，K阶爱尔朗分布（Ek），一般服务（G）等。6.1.1 排队系统及其组成 排队系统的描述形式：A/B/C：

4、D/E/FA顾客到达排队系统的时间间隔分布。B服务时间的分布。C服务台数（或服务通道数）。(C=1 ，2 ，n)D排队系统的容量，即系统中允许的最大顾客数 E顾客源的总体数目 F服务规则 FCFS，LCFS，SIRO，PR 6.1.1 排队系统及其组成 排队系统研究的问题大体分为三类：（1）系统性态的研究（即数量指标的研究）（2）统计问题的研究（3）最优化问题6.1.2 排队系统研究的问题 系统数量指标的研究旨在了解系统的基本特征，其主要的数量指标如下：（1）队长（L）：系统内顾客数的期望值。（2）列长（Lq）：系统中排队顾客数的期望值，即排队等待服务顾客数的期望值。（3）顾客在系统内停留时间

5、的期望值（W）（4）顾客在系统内等待时间的期望值（Wq）（5）忙期分布（6）服务设备利用率（7）顾客损失率6.1.2 排队系统研究的问题泊松分布 设N(t)表示在时间区间0，t内到达的顾客数（t0），令 表示在时间区间 内有 个顾客到达的概率，即 泊松分布具有如下三个特性：（1）无后效性（2）平稳性（3）普遍性6.1.3 排队论中常见的几种理论分布负指数分布 随机变量T服从负指数分布，其分布密度是:分布函数为: 负指数分布有下面两条性质：（1）当单位时间内的顾客到达数服从以 为平均数的泊松分布时，则顾客相继到达的间隔时间T服从负指数分布。（2）无记忆性6.1.3 排队论中常见的几种理论分布爱尔

6、朗分布 设顾客在系统内所接受服务可以分为k个阶段，每个阶段的服务时间 为服从同一分布 的k个相互独立的随机变量，顾客在完成全部服务内容并离开系统后，另一个顾客才能进入系统服务，则顾客在系统内接受服务时间和 服从爱尔朗分布 ，其分布密度函数为：6.1.3 排队论中常见的几种理论分布 6.2.1 排队模型 适用于满足以下条件的排队系统：(1) 输入过程：顾客源是无限的，顾客单个到来，相互独立，一定时间内的到达数服从泊松分布，到达过程是平稳的。(2) 排队规则：单队，且对队长没有限制，先到先服务。(3) 服务机构：单服务台，各顾客的服务时间相互独立，服从相同的负指数分布。此外，还假定到达间隔时间和服

7、务时间是相互独立的。 6.2 单服务台指数分布排队系统 系统稳态概率 的计算已知顾客到达率为 ，服务率为 ，在时间 时，系统内n个顾客的状态由以下四种方式构成：（1）在时刻t时有n个顾客，在随后 时间内没有顾客到达，也没有顾客离去；（2）在时刻t时有n1个顾客，在随后的 时间内没有顾客离去，有一个顾客到达；（3）在时刻t时有n+1个顾客，在随后的 时间内有一个顾客离去，没有顾客到达；（4）在时刻t时有n个顾客，在随后的 时间内有一个顾客到达，同时有一个顾客离去。 6.2.1 排队模型 各种方式所发生的概率如表6-1所示：表61 四种方式所发生的概率表6.2.1 排队模型时刻t的状态概率t内发生

8、的事件发生的概率nPn(t)无到达，无离去（1 ）（1 ）n1Pn-1 (t)到达一个，无离去(1 )n1Pn-1 (t)离去一个，无到达（1 ） nPn(t)到达一个，离去一个 由于这四种方式互不相容，故由概率的加法定律得：6.2.1 排队模型 当 时， 则有差分微分方程 （6-1）求此差分微分方程的稳态解，稳态解是指系统运行的时间t充分大时所得到的解。此时系统状态的概率分布已不随时间而变化，达到了统计平衡。稳态解与时间无关，因此有6.2.1 排队模型 方程式（6-1）可以写为： （6-2） 联立求解得： 6.2.1 排队模型 令 ，由 得系统的稳态解为： （6-3） 刻画了服务效率和服务机

9、构利用程度，称为服务强度（在通讯领域里 称为话务强度）。在推导公式中限制 ，因此 是系统能够到达稳定状态的充要条件。若 ，即到达率大于等于服务率，对于系统容量和顾客源均无限，到达和服务又是随机的，将出现队列排至无限远，无法达到稳定状态的情形。 6.2.1 排队模型状态转移图 稳态方程式（62）也可以通过所谓状态转移图列出见图62），然后求解。 P0 P1 Pn-1 Pn Pn+1 图62 状态转移图( 型状态转移图) 对于状态n,转入率为 ，转出率为因此有平衡方程： 6.2.1 排队模型系统的数量指标(1) 服务台空闲的概率和服务台忙的概率：由式（63）可以得到服务台空闲的概率 ，忙的概率为(

10、2) 系统中顾客数的期望值 L： （6-4）或 （6-5）6.2.1 排队模型(3)排队等待服务顾客数的期望值 （6-6）或 （6-7）(4)顾客在系统中排队等待时间的期望值 （6-8） 6.2.1 排队模型(5)顾客在系统中逗留时间的期望值W （6-9）本模型中最主要的四个指标公式归纳如下： （6-10） 6.2.1 排队模型四个指标L，L ，W，W 之间的关系（1）里特公式从（610）很容易得到： （6-11） 6.2.1 排队模型（2）里特公式的扩展设 是平均每单位时间进入系统的顾客数，称 为有效到达率。里特证明了在很宽的条件下都有以下关系式：里特公式就变成： （6-12） 6.2.1

11、排队模型 例 61 某理发店只有一个理发师，每小时平均有4个顾客到来，为一个顾客服务所需平均时间为6分钟。到达人数服从泊松分布，服务时间服从负指数分布，求：（1）理发店空闲和忙的概率。（2）顾客在店内平均逗留时间。（3）顾客在店内必须消耗15分钟以上的概率。（4）店内至少有一个顾客的概率。 6.2.1 排队模型 分析：依题知此题为 型， (1)理发店空闲的概率(2)顾客在店内平均逗留时间 (3)由于达到间隔和服务时间均服从指数分布，所以顾客在系统内的逗留时间也服从指数分布。已知平均逗留时间为 ，则逗留时间T的概率密度为 所以(4)店内至少有一个顾客的概率相当于店内忙的概率，为0.4。 6.2.

12、1 排队模型 例 62 设有一单管汽车加油站，平均20分钟有一辆汽车来加油，每辆汽车平均需要15分钟。假设此为 型，希望有足够的停车位置给前来加油的汽车停放，要求没有位置停车的概率不超过0.01。试问至少准备多少个汽车停车等待的位置？ 6.2.1 排队模型 分析：设应准备N个汽车停车的等待位置，依题意知：在加油站中不超过N+1辆汽车的概率应不小于0.99，即要求取对数又因为 所以 ，故 ，即至少准备14个汽车停车等待位置。6.2.1 排队模型 分析：设应准备N个汽车停车的等待位置，依题意知：在加油站中不超过N+1辆汽车的概率应不小于0.99，即要求取对数又因为 所以 ，故 ，即至少准备14个汽

13、车停车等待位置。6.2.1 排队模型 排队模型图6-3 排队模型 6.2.2 排队模型和 排队模型系统稳定概率的计算 P0 P1 P2 PN-1 PN 图64 型状态转移图对于任一状态，转移率等于转出率，可求得系统的稳态概率为 （6-13） 6.2.2 排队模型和 排队模型系统的数量指标（1）服务台闲的概率和服务台忙的概率：由式（613）可以得到服务台闲的概率为 ，忙的概率为 （2）系统中顾客数的期望值6.2.2 排队模型和 排队模型 顾客数为N时，有效到达率为：利用式（612）里特公式得： （6-14）6.2.2 排队模型和 排队模型 型的数量指标如下 （6-15）6.2.2 排队模型和 排

14、队模型 例6-3 为开办一个小型汽车加油站，只设一处加油点，需要决定等待汽车使用场地的大小，设需要加油的汽车到达为泊松过程，平均每4分钟到达1辆，加油时间服从指数分布，平均每3分钟完成1辆。如果要求因等待场地不足而转向其它加油站的汽车占需加油汽车的比例接近7时，应修建几辆汽车使用场地？ 6.2.2 排队模型和 排队模型 分析：依题意知 并设应修建N辆汽车使用场地，由公式知又因为转向其它加油站的汽车数与到达加油汽车的比例为 ，而 ，所以 计算结果如表62所示，由此可知应修建5辆汽车使用场地。表62 例63 计算结果6.2.2 排队模型和 排队模型 排队模型图65 排队模型6.2.2 排队模型和

15、排队模型系统稳态概率的计算 P0 P1 P2 Pn Pm 图66 排队模型系统的稳态概率为 （6-16）6.2.2 排队模型和 排队模型系统的数量指标 设各个顾客的到达概率都是相同的 ，系统中顾客的有效到达率 又由于 ，所以 ，解之得 ，其它指标可由里特公式得到，归纳如下： （6-17）6.2.2 排队模型和 排队模型 例64 某工厂拥有许多同类型的自动机，已知每台机器的正常运转时间服从平均数为2小时的指数分布，工厂看管一台机器的时间服从平均数为12分钟的指数分布，每个人只能看管自己的机器，工厂要求每台机器的正常运转时间不得少于87.5%。问在这条件下每个工人最多能看管几台机器？6.2.2 排

16、队模型和 排队模型 分析：设每个工厂最多能够看管m台机器，则就成为排队模型，且 ，那么机器平均故障台数 ，而 ，根据要求出现故障的机器数 ，当m=1，2，3，4，5时计算结果如表63所示。结算结果为四台。 表63 例64计算结果表6.2.2 排队模型和 排队模型 6.3.1 排队模型 图6-7 排队模型 此模型是顾客按泊松过程到达，服务服从负指数分布，C个服务台，系统容量和顾客源均无限，属于等待制。6.3 多服务台指数分布排队系统系统稳态概率的计算 P0 P1 P2 PC Pn 图6-8 型状态转移图可以求出系统稳态的概率为 （6-18）6.3.1 排队模型系统的数量指标则有 ，对那如下： （

17、6-19） 6.3.1 排队模型 例65 某维修部有两个维修工人，需要修理的电器到达服从泊松分布，维修电器时间服从指数分布，电器平均每小时到达20台，平均每5分钟修理1台，已知每台电器停工一分钟的平均损失费2元，试问电器站平均每台电器损失多少？ 分析：先求一台电器在维修部的平均逗留时间。由题意知 由 ，而 ，代入数据得W=16.34分钟。所以电器站平均每台电器损失16.342=32.68元。 6.3.1 排队模型M/M/C模型系统与M/M/1的比较 例66 某纺织厂的织布机车间有两个布机维修组，它们分别负责各自承包的那部分布机的维修。若每一部分布机平均每天有4台布机需要维修，而每组平均每一天可

18、维修5台布机。那么，是两组分别负责各自承包的那部分布机的维修效率高呢，还是两组合在一起共同负责这一车间的布机的维修效率高呢？也就是说，应建立一个单队多服务台系统，还是建立两个单队单服务台系统？（见图69）。 图69 (a)单队多服务台 (b)单队单服务台6.3.1 排队模型 分析：对于两个单队系统 等待时间 （天） 对于单队多服务台系统 （天） 显然单队多服务台系统比多个单队单服务台系统的工作效率大为提高，由于单队多服务台系统的等待时间小于多个单队单服务台系统的等待时间。6.3.1 排队模型6.3.2 和 排队模型 运用“嵌入马尔可夫链”方法推导出对于任意一种服务时间分布，排队系统中顾客数的期

19、望值L有下列关系： （6-20）这就是朴拉切克欣钦（Pollazakkhintchine）公式，它是排队论中最重要的公式之一。根据这个公式，不论何种服务时间分布，只要知道 ，E(T)，和Var(T)，那么在泊松输入的系统中，就可以求出排队系统中顾客数的期望值，再利用里特公式。可求出 等数量指标。6.4 一般服务时间的排队系统 如果服务时间服从k阶爱尔朗分布 ，利用公式（6-20）可得 （6-21）如果服务时间是确定的常数 则有 （6-22）6.4 一般服务时间的排队系统 图6-10 服务水平关系图 一般情形下，提高服务水平(数量，质量) 会降低顾客的等待费用(损失)，但却常常增加了服务机构的成

20、本最优化的目标之一是使二者费用之和为最小，并确定达到这个目标的最优的服务水平。另一个常用目标是使纯收入或利润(服务收入与服务成本之差)为最大。6.5 排队系统的优化 模型中最优的总费用其中 表示每增大1单位的 所需的单位时间服务费用； 表示每个顾客在系统中停留单位时间的费用。将 代入上式得 ，为求极小值，令求得最优的 ，由知 为最小值。 6.5.1 M/M/1的最优服务率 例69 兴建一座港口码头，只有一个装卸船员的装置，要求设计装卸能力用每日装卸的船数表示。已知单位装卸能力每日平均耗费生产费用a=2千元，船只到港后如不能及时装卸，停留一日损失运输费b=1.5千元，预计船的平均到达率是。该船只

21、到达时间间隔和装卸时间均服从负指数分布，问港口装卸能力多大时，每天的总支出最少？ 分析：依题意知， ，即 ，由式（623）得则最优装卸能力为每日装5只。6.5.1 M/M/1的最优服务率 模型中最优的总费用令 得 此式是一个关于 的高次方程，要解出 是比较困难的，所以通常用数值计算来求得 或用图形法近似求出 。6.5.1 M/M/1的最优服务率 模型中最优的总费用 ，令 得其中 由上式解出 很困难，通常利用泊松分布表通过数值计算来求得或图形法近似求出 。 6.5.1 M/M/1的最优服务率 总费用函数为 其中必须有为求最优的 ，采用边际分析法。由得：依次求 时L的值，并做两相邻的L值之差，因为

22、 为已知数，根据这个数落在哪个不等式的区间里就可定出最优值 。6.5.2 模型中最优的服务台 例610 某健康检测中心为人检查身体的健康状况，来检查的人平均到达率为48人次/天，每次来检查由于请假等原因带来的损失为6元，检查时间服从负指数分布，平均服务率 为25人次/天，每安排一位医生的服务成本为每天4元，问应安排几位医生（设备）才能使总费用最小？ 分析：由题意知，首先，须满足 解得 。又因为而6.5.2 模型中最优的服务台 令 将已知数据代入上面两个式子，算得结果如下表所示： 表65 例610计算结果因为 ，故由及以上计算结果可知：故 ，即安排3位医生可使总费用最小。6.5.2 模型中最优的服务台 问题的提出：某市准备在市中心设立一家银行。已知顾客的到达服从泊松分布，顾客平均到达率为0.33人/分。