数学建模排队模型2015-7-12

1、排队模型及其应用 中北大学理学院数学学科 张张 峰峰 数学建模暑期培训系列讲座 排队模型简介排队模型简介 经典排队模型经典排队模型 布传播的风险因素以及动力学建模布传播的风险因素以及动力学建模 1 2 3 推广的排队模型推广的排队模型 3 4 排队系统的优化排队系统的优化 1 排队模型排队模型简介简介 （背景）（背景） 超市排队 为什么不多开个窗口 银行排队 1 排队模型排队模型简介简介 （背景）（背景） 服务效率忒低 购票排队 哥 要 回 家 1 排队模型排队模型简介简介 （背景）（背景） 高速公路车辆排队 Where is the toilet? 1 排队模型排队模型简介简介 （背景）（背

2、景） 壮哉！壮哉！ 购票排队 1 排队模型排队模型简介简介 （背景）（背景） 呼叫中心排队 1 排队模型排队模型简介简介 （背景）（背景） 9 为什么会出现排队现象？为什么会出现排队现象？ 假定每小时平均有假定每小时平均有4位顾客到达，服务人员为每位顾客的平均服务时间位顾客到达，服务人员为每位顾客的平均服务时间 为为15分钟。如果顾客到达的间隔时间正好是分钟。如果顾客到达的间隔时间正好是15分钟，而服务人员为每位顾分钟，而服务人员为每位顾 客的服务时间也正好是客的服务时间也正好是15分钟，那么，就只需要一名服务人员，顾客也根分钟，那么，就只需要一名服务人员，顾客也根 本用不着等待。本用不着等待

3、。 在以下情况将出现排队现象：在以下情况将出现排队现象： 平均到达率高于平均服务率平均到达率高于平均服务率 顾客到达的间隔时间不一样（随机）顾客到达的间隔时间不一样（随机） 服务时间不一样（随机）服务时间不一样（随机） 顾客离开顾客离开 顾客顾客 顾客排队顾客排队 服务设施服务设施 1 排队模型排队模型简介简介 （基本概念）（基本概念） 排队论排队论(Queuing Theory)，又称随机服务随机服务 系统系统是一门研究拥挤现象(排队、等待)的科 学。具体地说，它是在研究各种排队系统概 率规律性的基础上，解决相应排队系统的最 优设计和最优控制问题。 每个顾客的等待时间多长？每个顾客的等待时间

4、多长？ 选择哪个队列时间最短？选择哪个队列时间最短？ 多开一个窗口？多开一个窗口？ 顾客消费收入与超市成本之间博弈顾客消费收入与超市成本之间博弈 怎样设计最优怎样设计最优 ；最优运行（）；最优运行（） 排队模型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念） 一、排队模型的描述一、排队模型的描述 相似的特征及数学抽象相似的特征及数学抽象 顾客到达系统的时刻是随机的，为每一位顾客提 供服务的时间是随机的，因而整个排队系统的状 态也是随机的，因此排队论排队论又称为随机服务系统随机服务系统 顾客顾客-请求服务的人或者物 服务员或服务台服务员或服务台-为顾客服务的人或者物 排队模

5、型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念） 一、排队模型的描述（组成）一、排队模型的描述（组成）基本排队过程基本排队过程 排队系统一般有三个基本组成部分：排队系统一般有三个基本组成部分： 1.输入过程；输入过程；2.排队规则；排队规则；3.服务机构服务机构 排队结构服务机构顾客源 顾客到达 排队规则 服务规则离去 图1 排 队系统示意图 排队模型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念） 一、排队模型的描述（组成）一、排队模型的描述（组成）基本排队过程基本排队过程 1.输入过程输入过程 顾客是按怎样的规律到达排队系统的过程，有时也顾客是

6、按怎样的规律到达排队系统的过程，有时也 把它称为把它称为顾客流顾客流 （1 1）顾客顾客总数总数 有限有限 无限？无限？ （2 2）到达方式到达方式 单个单个 成批？成批？ （3 3）顾客流的概率分布族顾客流的概率分布族 相继到达的顾客间的概率分布相继到达的顾客间的概率分布 排队模型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念） 一、排队模型的描述（组成）一、排队模型的描述（组成）基本排队过程基本排队过程 2. 排队规则排队规则 服务台以怎样的顺序和方式服务顾客服务台以怎样的顺序和方式服务顾客 （1 1）损失制损失制 如果顾客到达排队系统时，所有服务台都已被先来的如果顾

7、客到达排队系统时，所有服务台都已被先来的 顾客占用，那么他们就自动离开系统顾客占用，那么他们就自动离开系统。 （2 2）等待制等待制 当顾客来到系统时，所有服务台都不空，顾客加入排队当顾客来到系统时，所有服务台都不空，顾客加入排队 行列等待服务行列等待服务 FCFS LCFS PR RO （3 3）混合制混合制 等待制与损失制等待制与损失制的混合的混合 一般是指允许排队，但又不一般是指允许排队，但又不 允许队列无限长下去允许队列无限长下去 排队模型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念） 一、排队模型的描述（组成）一、排队模型的描述（组成）基本排队过程基本排队过程

8、 3. 服务机构服务机构 （1 1）服务台数量及构成方式服务台数量及构成方式 单服务台单服务台 多服务台；多服务台； （2 2）服务方式服务方式 单个服务，批量服务；单个服务，批量服务； （3 3）服务时间的概率分布服务时间的概率分布 服务过程是泊松过程？高斯过程？服务过程是泊松过程？高斯过程？ 一个顾客的服务时间是指数分布还是一般概率分布？一个顾客的服务时间是指数分布还是一般概率分布？ 排队模型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念） 一、排队模型的描述（组成）一、排队模型的描述（组成）基本排队过程基本排队过程 3. 服务机构服务机构 （结构）（结构） 单队多服

9、务台并联单队多服务台并联 例如例如 学校内的一些小超市学校内的一些小超市 排队模型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念） 一、排队模型的描述（组成）一、排队模型的描述（组成）基本排队过程基本排队过程 3. 服务机构服务机构 （结构）（结构） 单队多服务台并联单队多服务台并联 （银行排队）（银行排队） 排队模型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念） 一、排队模型的描述（组成）一、排队模型的描述（组成）基本排队过程基本排队过程 3. 服务机构服务机构 （结构）（结构） 多队多服务台并联多队多服务台并联 大型超市、火车站窗口、医院窗大型

10、超市、火车站窗口、医院窗 口、口、 高速公路收费、高速公路收费、 多车道路口车辆通行等多车道路口车辆通行等 排队模型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念） 一、排队模型的描述（组成）一、排队模型的描述（组成）基本排队过程基本排队过程 3. 服务机构服务机构 （结构）（结构） 单队列多服务台串联单队列多服务台串联 柔性制造业柔性制造业 产品按工序加工产品按工序加工 排队模型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念） 二、建模过程及主要指标二、建模过程及主要指标 1 排队系统的统计推断排队系统的统计推断 确定或拟合排队系统顾客到达的时间间

11、隔分布和服务时间分布确定或拟合排队系统顾客到达的时间间隔分布和服务时间分布。 2 模型的性态模型的性态 在确定模型的基础上，求解主要性能指标，如队长分布、等在确定模型的基础上，求解主要性能指标，如队长分布、等 待时间分布。待时间分布。 3 模型进行优化模型进行优化 系统的最优设计（系统的最优设计（参数选择，服务质量评价）如机场跑道数量，呼参数选择，服务质量评价）如机场跑道数量，呼 叫中心坐席量。叫中心坐席量。 已有系统的最优控制已有系统的最优控制 如从顾客和服务机构双方利益出发，对排队如从顾客和服务机构双方利益出发，对排队 系统进行最优控制系统进行最优控制 排队模型排队模型简介简介1 排队模型

12、排队模型简介简介 （基本概念）（基本概念） 二、建模过程及主要指标二、建模过程及主要指标 1 队长队长: 系统中的顾客数系统中的顾客数, 平均队长平均队长LS 等待队长等待队长 : 系统中排队等待服务的顾客数系统中排队等待服务的顾客数, 平均等待队长平均等待队长Lq 系统系统 中顾中顾 客客 数数 在队列中等在队列中等 待服务的顾待服务的顾 客数客数 正 被 服正 被 服 务 的 顾务 的 顾 客数客数 + = 一般情形，一般情形，Ls(或或Lq)越大，说明服务效率越低。越大，说明服务效率越低。 排队模型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念） 二、建模过程及主要

13、指标二、建模过程及主要指标 2. 逗留时间逗留时间:一个顾客在系统中的停留时间一个顾客在系统中的停留时间,平均逗留时间平均逗留时间 WS 等待时间等待时间: 一个顾客排队等待的时间一个顾客排队等待的时间,平均等待时间平均等待时间Wq 等待时间等待时间服务时间服务时间 + 逗留时间逗留时间 = = 显然，显然，Ws(或或Wq)越大，顾客满意度越低。越大，顾客满意度越低。 排队模型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念） 二、建模过程及主要指标二、建模过程及主要指标 3. 忙期忙期：从顾客到达空闲服务机构起到服务机构再次为从顾客到达空闲服务机构起到服务机构再次为 空闲

14、这段时间长度。空闲这段时间长度。可以衡量服务机构效率的指标，及可以衡量服务机构效率的指标，及 工作强度工作强度 4. 绝对通行能力绝对通行能力：单位时间内被服务完的平均顾客数：单位时间内被服务完的平均顾客数 5. 相对通行能力相对通行能力：单位时间内被服务完顾客数与请求服：单位时间内被服务完顾客数与请求服 务的顾客数之比务的顾客数之比 6. 平均被占服务台数平均被占服务台数 7 损失率损失率 排队模型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念） 三、排队模型应用三、排队模型应用 从从2020世纪世纪6060年代至今年代至今 对业务突发性和带有各种网络协议控制的通信系统

15、进行对业务突发性和带有各种网络协议控制的通信系统进行 性能评价、仿真及模拟性能评价、仿真及模拟。 2020世纪初期世纪初期 主要研究应用于电话网和远程通信系统等无队列的排队主要研究应用于电话网和远程通信系统等无队列的排队 系统系统( (损失制损失制) ) 2020世纪中期世纪中期 主要研究通信系统中有队列主要研究通信系统中有队列( (等待制等待制) )的排队系统和排队网络的排队系统和排队网络 排队模型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念） 三、排队模型应用三、排队模型应用 2005 2005 研究生建模研究生建模 出租车最佳数量预测出租车最佳数量预测 20002

16、005 20002005 智能地雷反坦克研究，灭火兵力部署智能地雷反坦克研究，灭火兵力部署 19902000 19902000 码头与船舶的分配，工程土方的创新，停车场面码头与船舶的分配，工程土方的创新，停车场面 积的计算，图书馆信息处理积的计算，图书馆信息处理 20052010 20052010 公厕建筑面积的分配，教务处教务员岗位确定公厕建筑面积的分配，教务处教务员岗位确定 新的前沿应用新的前沿应用 社交网络性能社交网络性能 评估评估 云计算性能指标估计等云计算性能指标估计等 1 排队模型排队模型简介简介 三、排队模型应用三、排队模型应用 20092009眼科医院病床合理安排眼科医院病床合

17、理安排 提高医疗体系的服务效率，提高资源利用率，提高病人满 意度以及缓解患者于医院之间的矛盾；提出了一些具体的优 化标准如下： 1、以费用作为优化指标计算最优目标值条件下最优的服务水 平：总费用= 排队损失费+ 服务费 2、“优先权选择或等级”来优化医院服务 （眼科医院病床） 3、构造合理的调度方式来进行优化 4、建立了“预留病床模型，逐步优先权就诊模式” 1 排队模型排队模型简介简介 三、排队模型应用三、排队模型应用 20132013年年 A A题题 车道被占用对城市道路通行能力的影响车道被占用对城市道路通行能力的影响 （1） 研究公交车发车间隔与排队长度 （2）研究停车场的车辆排队 （3）

18、研究车辆排队现象、车辆延误 路口通行能力分析 2 排队模型排队模型经典排队模型经典排队模型 一 单服务台 排队模型 1 标准的标准的 模型模型1/MM 2 模型条件模型条件 模型模型 表示，顾客到达过程服从泊松分布，表示，顾客到达过程服从泊松分布， 服务时间服从负指数分布，单服务台，队长和顾客来源无服务时间服从负指数分布，单服务台，队长和顾客来源无 限限.简记为简记为 . /1/ MM 1/ MM 1）已知单位时间平均到达率）已知单位时间平均到达率 和平均服务率和平均服务率 . 2）系统容量无限，顾客源总数无限）系统容量无限，顾客源总数无限. 3）排队规则为单队，先到先服务）排队规则为单队，先

19、到先服务 )( 1/MM 2 排队模型排队模型经典排队模型经典排队模型 一 单服务台 排队模型 3 模型的求解模型的求解1/MM 1/MM 研究研究系统状态的概率系统状态的概率- - 系统中顾客数。状态概率用系统中顾客数。状态概率用Pn( (t) )表表 示示, ,即在即在t时刻系统中有时刻系统中有n个顾客的概率，也称瞬态概率。个顾客的概率，也称瞬态概率。 实际中更关心实际中更关心 稳态概率稳态概率 lim nn t PP t 稳态概率求法稳态概率求法 马尔科夫链理论马尔科夫链理论 母函数母函数 递推等递推等 稳态概率求解步骤稳态概率求解步骤 1 画出稳态概率转移图画出稳态概率转移图 2 列出

20、稳态概率平衡方程组列出稳态概率平衡方程组 3 求出稳态概率或者母函数求出稳态概率或者母函数 2排队模型排队模型经典排队模型经典排队模型 一 单服务台 排队模型1/MM 系统在稳定情况下的状态转移如图系统在稳定情况下的状态转移如图 图1.1 Pn 1P2P1P0PnPn 1 可以得到如下平衡方程可以得到如下平衡方程： nnn PPP 11（1.1） 01 PP （1.2） 4 稳态概率公式稳态概率公式 2 排队模型排队模型经典排队模型经典排队模型 一 单服务台 排队模型1/MM 5 5 模型的数量指标公式模型的数量指标公式 由（1.1）和（1.2）可以递推求解， 01 PP 0 2 102 )(

21、)1 (-PPPP . 0 )(PP n n . n n P P 1 1 0 式中 表示平均到达率与平均服务率 之比，称为服务强度. 2 排队模型排队模型经典排队模型经典排队模型 一 单服务台 排队模型1/MM 6 模型的性能指标模型的性能指标 1）在系统里没有顾客的概）在系统里没有顾客的概率率 2 0 111 11LPLPnPPnL n n n nn n q 1 0 P 000 )1 ()1 ( n q n nn n ns LkknPL 2）平均排队的顾客数平均排队的顾客数 3）在系统里的平均顾客数）在系统里的平均顾客数 u 2 排队模型排队模型经典排队模型经典排队模型 一 单服务台 排队模

22、型1/MM 4 4）一位顾客花在系统里的平均逗留时间）一位顾客花在系统里的平均逗留时间 1 )(XEWs 5 5）一位顾客花在排队上的平均时间（等于逗留时间减去服）一位顾客花在排队上的平均时间（等于逗留时间减去服 务时间）务时间） 6 6）顾客到达系统时，得不到及时的服务，必须等待服务的）顾客到达系统时，得不到及时的服务，必须等待服务的 概率概率 7 7）系统里正好有）系统里正好有 个顾客的概率个顾客的概率 1 qs WW 0 1 w PP 0 )(PP n n n 6 模型的性能指标模型的性能指标 2 排队模型排队模型经典排队模型经典排队模型 一 单服务台 排队模型 应用举例应用举例 1/M

23、M 库存问题库存问题 进货多，保管费用大；存货不足缺货会引起经济进货多，保管费用大；存货不足缺货会引起经济 损失，假设货物需求量是参数为损失，假设货物需求量是参数为 的泊松过程，生产一个的泊松过程，生产一个 产品实际是参数为产品实际是参数为 的指数分布，单位时间库存费用的指数分布，单位时间库存费用c元，元， 缺货一个产品损失为缺货一个产品损失为h元，确定最优库存使得库存费和损失元，确定最优库存使得库存费和损失 费之和达到最小费之和达到最小. 分析分析 将生产厂看成服务机构，需求看成输入流将生产厂看成服务机构，需求看成输入流 M/M/1 排队排队 平均缺货数平均缺货数 1 1 s quen n

24、s Ens p 平均库存数平均库存数 1 0 1 1 s s cunn n Esn ps 2 排队模型排队模型经典排队模型经典排队模型 一 单服务台 排队模型 应用举例应用举例 1/MM 分析分析 将生产厂看成服务机构，需求看成输入流将生产厂看成服务机构，需求看成输入流 M/M/1 排队排队 单位时间总费用单位时间总费用 1 1 11 s s cunque f scEhEc sh 由边际分析法由边际分析法 1f sf s 1f sf s 由边际分析法由边际分析法 s c ch 1s c ch 最佳最佳s满足满足 ln/ln1ln/ln cc s chch 36 例例 一个码头，设待卸货船到达时

25、间间隔服从负指数一个码头，设待卸货船到达时间间隔服从负指数 分布，平均到达分布，平均到达 2 艘艘/小时；服务台是小时；服务台是1台吊车，卸台吊车，卸 货时间服从负指数分布，平均每货时间服从负指数分布，平均每 20 分钟可卸一艘分钟可卸一艘 货船，当被占用时，新到货船只能停在码头等待。货船，当被占用时，新到货船只能停在码头等待。 求在平稳状态下码头上货船的平均数；等待卸货求在平稳状态下码头上货船的平均数；等待卸货 船只的平均数；每艘货船在码头的平均停留时间；船只的平均数；每艘货船在码头的平均停留时间； 货船平均需等待多长时间可以开始卸货。货船平均需等待多长时间可以开始卸货。 2 排队模型排队模

26、型经典排队模型经典排队模型 37 解：解： 这是一个典型的这是一个典型的M/M/1排队排队问题问题 2 1 3 r 2 60 3 20 u 2 2() 32 s L u 艘 24 2 33 qs LLr(艘) 4 2 3 () 23 Lq Wq 小时 2 1() 2 Ls Ws 小时 2 排队模型排队模型经典排队模型经典排队模型 38 例例 某医院手术室根据病人就诊和完成手术时间某医院手术室根据病人就诊和完成手术时间 的记录，任意抽查的记录，任意抽查100个工作小时，每小时个工作小时，每小时 来就诊的病人数来就诊的病人数n的出现次数如表的出现次数如表6所示。又所示。又 任意抽查了任意抽查了10

27、0个完成手术的病例，所用时个完成手术的病例，所用时 间间t出现的次数如下表所示。试分别用公式、出现的次数如下表所示。试分别用公式、 excel和仿真求解：和仿真求解： 2 排队模型排队模型经典排队模型经典排队模型 39 到达病人数到达病人数 n 出现次数出现次数 f n 010 128 229 316 410 56 61 合计合计100 到达病人数到达病人数 为病人完成手术为病人完成手术 时间时间t/小时小时 出现次数出现次数 ft 0.00.238 0.20.425 0.40.617 0.6 1.89 0.81.06 1.01.25 1.20 合计合计100 手术时间手术时间 2 排队模型排

28、队模型经典排队模型经典排队模型 40 解：解： 这也是一个这也是一个M/M/1排队排队问题问题 （1）计算平均到达率）计算平均到达率 2.1(/) 100 n nf 人 时 平均手术时间平均手术时间 0.4() 100 t tf T 时/人 平均服务率平均服务率 1 2.5() 0.4 u 人/时 2 排队模型排队模型经典排队模型经典排队模型 41 （2）取）取=2.1，=2.5，通过统计检验方法认为病人到达，通过统计检验方法认为病人到达 数服从参数为数服从参数为2.1的泊松分布，手术时间服从参数为的泊松分布，手术时间服从参数为 2.5的指数分布。的指数分布。 （3）服务设备利用率服务设备利用

29、率 2.1 0.84 2.5 这说明服务机构（手术室）有这说明服务机构（手术室）有84%的时间是繁忙的时间是繁忙的的 （被利用），有（被利用），有16%的时间是空闲的。的时间是空闲的。 42 0.84r u 2.1 2.5u 2.1 5.25() 2.52.1 s L u 人 5.250.844.41 qs LLr(人) 4.41 2.1() 2.1 Lq Wq 小时 5.25 2.5() 2.1 Ls Ws 小时 （4）依次带入公式，算出各指标得：依次带入公式，算出各指标得： 43 单通道单通道Excel求解求解 2 排队模型排队模型经典排队模型经典排队模型 二二 多服务台 排队模型 1 标

30、准的标准的 模型模型/M M c 2 模型描述模型描述 模型模型 表示，顾客到达过程服从泊松分布，服表示，顾客到达过程服从泊松分布，服 务时间服从负指数分布，务时间服从负指数分布，C 个服务台，队长和顾客来源无个服务台，队长和顾客来源无 限限. /MMC /M M C 已知单位时间平均到达率已知单位时间平均到达率 ， C 个服务台，每个服务台个服务台，每个服务台 的工作相互独立且平均服务率相同，都等于的工作相互独立且平均服务率相同，都等于 ，顾客源无限，顾客源无限， 容量无限，排队规则为等待制容量无限，排队规则为等待制 3.系统的状态概率和主要运行指标系统的状态概率和主要运行指标 )1(n)1

31、(nn 2 0 P 2 P 1 P 1n P n P 1n P ,)( ,)1( , 11 11 01 cnn nnn PcPcP PnPPn PP ）（),.,2, 1(cn ,.)2, 1(ccn (1) 系统的状态概率系统的状态概率 系统的空闲概率 4 系统的状态概率和主要运行指标系统的状态概率和主要运行指标 系统内有n个顾客的概率 CnP CC CnP n P n Cn n n 0 0 )( ! 1 )( ! 1 1 1 0 0 )( 1 1 ! 1 )( ! 1 C k Ck Ck P 1 C 2 排队模型排队模型经典排队模型经典排队模型 二二 多服务台 排队模型 4 主要运行指标主

32、要运行指标 /M M C 0 2 () !(1) 1 c qq q qq c LPLL c L L WWW 系统平均队长、平均等待时间 平均占用服务台数 K 系统通行能力 0 L P 损失率系统相对通过能力 11 L QP 系统绝对通过能力 AQ 48 例例 某售票所有三个窗口，顾客的到达服从泊松分布，某售票所有三个窗口，顾客的到达服从泊松分布， 平均到达速率平均到达速率 = 0.9人人/min；售票时间服从负指；售票时间服从负指 数分布，平均服务速率数分布，平均服务速率= 0.4人人/min 。现设顾客到。现设顾客到 达后排成一队，依次向空闲的窗口购票，如图所达后排成一队，依次向空闲的窗口购

33、票，如图所 示。试分别用公式、示。试分别用公式、excel和仿真求解：和仿真求解： u(1) 整个售票所空闲概率整个售票所空闲概率 u(2) 平均队列长和平均队长平均队列长和平均队长 u(3)平均等待时间和逗留时间平均等待时间和逗留时间 u(4)顾客到达后必须等待的概率（顾客到达后必须等待的概率（n3) 2 排队模型排队模型经典排队模型经典排队模型 49 顾客到达和服务图顾客到达和服务图 顾客离去 排队 = 0.9 顾客到达 窗口1 = 0.4 窗口2 = 0.4 窗口3 = 0.4 2 排队模型排队模型经典排队模型经典排队模型 50 解：解： 这是一个典型的这是一个典型的M/M/C 排队排队

34、问题问题 0.9 0.751 30.4C 0.90.4u (1) 整个售票所空闲概率整个售票所空闲概率 0.9 2.25 0.4 r 1 1 0 0 !(1) nc c n rr P nc 0123 1 52.251 0!1!2!3!10.75 0.0748 2 排队模型排队模型经典排队模型经典排队模型 51 (2) 平均排队长度和平均队列长平均排队长度和平均队列长 0 2 !(1) c q r Lp c 3 2 2.250.75 0.07481.70 3!(10.75) 1.702.253.95 sq LLr (3)平均等待时间和逗留时间平均等待时间和逗留时间 1.70

35、 1.89 0.9 q q L W 11 1.894.39 0.4 sq WW u 2 排队模型排队模型经典排队模型经典排队模型 52 (4)顾客到达后必须等待的概率（顾客到达后必须等待的概率（n3) 33 1 nn PP n P 0 ! n r p n (0)nc 0 1 ! n nc rp cc g ()nc 0 0.0748P 2 30 (1)(12.252.531)0.07480.432 2 n r PrP 2 排队模型排队模型经典排队模型经典排队模型 53 M/M/3 Excel求解求解 54 例例 银行取号系统有用吗？银行取号系统有用吗？ 就例就例5，如果其他条件不变，顾客到达后在

36、每个窗，如果其他条件不变，顾客到达后在每个窗 口前各排一队，且进入队列后坚持不换，就形成口前各排一队，且进入队列后坚持不换，就形成3 个队列，如下图所示。试分别用公式、个队列，如下图所示。试分别用公式、excel求解：求解： u(1) 整个售票所空闲概率整个售票所空闲概率 u(2) 平均队列长度和平均队长平均队列长度和平均队长 u(3) 平均等待时间和逗留时间平均等待时间和逗留时间 u(4)顾客到达后必须等待的概率（顾客到达后必须等待的概率（n3) 2 排队模型排队模型经典排队模型经典排队模型 55 顾客到达和服务图顾客到达和服务图 顾客离去 = 0.3 顾客到达 = 0.9 窗口1 = 0.

37、4 窗口2 = 0.4 窗口3 = 0.4 = 0.3 = 0.3 2 排队模型排队模型经典排队模型经典排队模型 56 解：解： 这是这是3个个M/M/1同时服务的同时服务的排队排队问题问题 0.3 0.751 0.4 r 0.3 0.4u (1) 整个售票所空闲概率整个售票所空闲概率(每个窗口空闲每个窗口空闲) 0 110.750.25p (4)顾客到达必须等待的概率（每个窗口顾客到达必须等待的概率（每个窗口n1) 10 110.250.75 n pP 2 排队模型排队模型经典排队模型经典排队模型 57 (2) 平均排队长度和平均队列长平均排队长度和平均队列长 0.3 0.752.25 0.

38、40.3 q L u 2.250.753 sq LLr (3)平均等待时间和逗留时间平均等待时间和逗留时间 2.25 7.5 0.3 q q L W 3 10 0.3 s s L W 339系统（3个窗口）队长 2 排队模型排队模型经典排队模型经典排队模型 58 3个个M/M/1 Excel求解求解 2 排队模型排队模型经典排队模型经典排队模型 59 结论：银行取号系统是有效的结论：银行取号系统是有效的 指标指标数值数值 排队长度排队长度1.70 系统队长系统队长3.95 平均排队时间平均排队时间1.89 服务台空闲概率服务台空闲概率0.075 顾客必须等待的概率顾客必须等待的概率0.57 指

39、标指标数值数值 排队长度排队长度2.25 系统队长系统队长9 平均排队时间平均排队时间7.5 服务台空闲概率服务台空闲概率0.25 顾客必须等待的概率顾客必须等待的概率0.75 2 排队模型排队模型经典排队模型经典排队模型 二二 多服务台 排队模型/M M C 眼科医院病床安排眼科医院病床安排 2 排队模型排队模型经典排队模型经典排队模型 眼科医院病床安排眼科医院病床安排 简单而言：每一类病人应安排多少床位简单而言：每一类病人应安排多少床位 2 排队模型排队模型经典排队模型经典排队模型 眼科医院病床安排眼科医院病床安排 2 排队模型排队模型经典排队模型经典排队模型 眼科医院病床安排眼科医院病床

40、安排 2 排队模型排队模型经典排队模型经典排队模型 二二 多服务台 排队模型/M M C 车道被占用对城市道路通行能力的影响车道被占用对城市道路通行能力的影响 1 根据视频1（附件1），描述视频中交通事故发生至撤离期间,事故 所处横断面实际通行能力的变化过程。 2 根据问题1所得结论，结合视频2（附件2），分析说明同一横断 面交通事故所占车道不同对该横断面实际通行能力影响的差异。 2 排队模型排队模型经典排队模型经典排队模型 二二 多服务台 排队模型/M M C 车道被占用对城市道路通行能力的影响车道被占用对城市道路通行能力的影响 2 排队模型排队模型经典排队模型经典排队模型 二二 多服务台

41、排队模型/M M C 车道被占用对城市道路通行能力的影响车道被占用对城市道路通行能力的影响 123 /3,/1M MM MMM 67 排队系统最优设计排队系统最优设计成本分析成本分析 1 概述概述 排队系统的最优设计和最优控制，即排队系排队系统的最优设计和最优控制，即排队系 统的最优化问题，其目的在于使排队系统达统的最优化问题，其目的在于使排队系统达 到到最大效益最大效益或者说在一定指标下使排队系统或者说在一定指标下使排队系统 最为经济最为经济。 3 排队模型排队模型排队模型的优化排队模型的优化 68 服务成本与等待成本的权衡（成本效益平衡）服务成本与等待成本的权衡（成本效益平衡） 总成本 成

42、本 最佳能力 等待成本 服务成本 最小值 排队分析的目的是使顾客等待成本与服务能力成本这两项成本 之和最小 3 排队模型排队模型排队模型的优化排队模型的优化 69 M/M/1模型中的最优服务率模型中的最优服务率u 最佳服务能力是使总成本最小化： 总成本=顾客等候成本+服务能力成本 1 w s w ss Cu C uC L C z 为时服务机构单位时间的费用 为每个顾客在系统中逗 即： 留时间的费用 /1 S MML u 模型中 sw zC uC u 所以： 3 排队模型排队模型排队模型的优化排队模型的优化 70 M/M/1模型中的最优服务率模型中的最优服务率u sw zC uC u 0 dz

43、du 令 2 0 () sw CC u 即： 所以M/M/1模型的最优服务率为： w s C u C 3 排队模型排队模型排队模型的优化排队模型的优化 71 例例 设某服务机构，单服务台，顾客到达率为每设某服务机构，单服务台，顾客到达率为每 小时小时12位顾客。假定每位接受顾客的顾客其位顾客。假定每位接受顾客的顾客其 等待费用为每小时等待费用为每小时5元，服务成本为每位顾元，服务成本为每位顾 客客2元，欲使总平均费用最小，服务率应为元，欲使总平均费用最小，服务率应为 多少？多少？ 3 排队模型排队模型排队模型的优化排队模型的优化 72 解：解： 这是一个标准的这是一个标准的M/M/1排队排队问

44、题问题 2 s C元12/ h人5 w C元 因而 swS zC uC L 最 小 总 费 用 512 1217.5(/ h) 2 w s C u C 最优服务率人 12 2.18 17.512 s L u * 217.552.1846Z 12 0.686 17.5u 最 优 系 统 利 用 率 3 排队模型排队模型排队模型的优化排队模型的优化 73 、Lq 、Ls三者的关系三者的关系-1 当系统利用率增加时，队列平均等候数与顾当系统利用率增加时，队列平均等候数与顾 客排队等候的平均时间呈指数增长。客排队等候的平均时间呈指数增长。 3 排队模型排队模型排队模型的优化排队模型的优化 74 队列

45、中平 均等 侯数 100% 系统利用率 0 、Lq 、Ls三者的关系-2 qq LW q W ./ 1exMM 3 排队模型排队模型排队模型的优化排队模型的优化 75 、Lq 、Ls三者的关系三者的关系-3 平均队长（和平均等待时间）与服务台利用平均队长（和平均等待时间）与服务台利用 率之间的关系不是线性的关系。资产利用率率之间的关系不是线性的关系。资产利用率 太高会造成服务质量急速下降，因而要权衡太高会造成服务质量急速下降，因而要权衡 利弊。利弊。要保证服务质量，就必须保持要保证服务质量，就必须保持“过剩过剩 的的”生产或服务能力。生产或服务能力。 3 排队模型排队模型排队模型的优化排队模型

46、的优化 76 仅讨论标准的仅讨论标准的M/M/C模型，且在稳态下，单位时间全部费用模型，且在稳态下，单位时间全部费用 的期望值为：的期望值为：(包括服务成本与等待费用包括服务成本与等待费用) zC sCC wL 式中式中: : 每个服务台单位服务时间成本；每个服务台单位服务时间成本； 每个顾客在系统中停留单位时间成本每个顾客在系统中停留单位时间成本； L系统中顾客的平均数系统中顾客的平均数Ls或队列平均数或队列平均数Lq，是是C的函的函 数数。 这里这里Z是是C的函数的函数,且且C只能取整数解只能取整数解,故不能用微分法求故不能用微分法求C*, 而只而只 能用边际分析法能用边际分析法(Marg

47、inal Analysis)： Cs Cw 3 排队模型排队模型排队模型的优化排队模型的优化 77 因为因为 z(c*) 是最小值，则有是最小值，则有： ) 1 () 1*() 1*(*)(* CLCwCsCCLCwCsC )1*(*)(czcz ) 1*(*)(czcz 将将z期望费用公式代入：期望费用公式代入： )2() 1*() 1*(*)(* CLCwCsCCLCwCsC *)()1*(/)1(CLCLCwsC得：由 )1*(*)(/)2(CLCLCwsC得：由 合并化简得合并化简得： *)() 1*(/) 1*(*)(CLCLCsCCLCLw 依次求依次求C=1,2,3C=1,2,3

48、，的的 L L值，即可找出符合上式的值，即可找出符合上式的C C* *。 78 例例6某检验中心，为各用户检验产品，用户每天到达按泊松流某检验中心，为各用户检验产品，用户每天到达按泊松流 =48个个/天，每个用户每天停工损失天，每个用户每天停工损失6元，服务时间服从负指数元，服务时间服从负指数 分布分布=25个个/天，每设天，每设1个检验台每天服务成本个检验台每天服务成本4元，其他条件为元，其他条件为 标准标准M/M/C模型，问设几个服务台费用最少？模型，问设几个服务台费用最少？ 解：解： =4元元 Cw=6=48 =25,下面再分别计算当服务台下面再分别计算当服务台 C=1,2,3,时时Ls

49、值。计算过程如下：值。计算过程如下： C12345 /c Wq. Ls 1.92 - 0.96 10.2550 21.610 0.64 0.3961 2.680 0.48 0.0772 2.068 0.38 0.0170 1.952 Cs 79 计算计算 L(CL(C* *)-L(C)-L(C* *+1)+1)及及 L(CL(C* *-1)-L(C-1)-L(C* *) ) c=1 - c=1 - c=2 18.930 c=2 18.930 （相当于无穷）（相当于无穷） c=3 0.612 18.930 c=3 0.612 18.930 c=4 0.116 0.612c=4 0.116 0.6

50、12 667.03/26/4/ CwsC 即为所求。3* C 0.612/18.930CsCw （见陆书（见陆书239239页队长表达式）页队长表达式） 系统容量有限的系统容量有限的 模型模型/1/NMM 系统容量为N，系统中排队等待的顾客数最多为N-1，所以在某一时刻 某位顾客到达时，如果系统中已有N位顾客，那么这位顾客被拒绝进入系 统，如图2.2 N-1 N 0 P n P 1n P 2 P 1 P 图2.2 由状态转移图，可以建立系统概率平衡方程如下： , ,)( , 1 11 01 NN kkk PP PPP PP 1 Nk 4 排队模型排队模型推广推广 系统容量有限的系统容量有限的

51、模型模型 /1/NMM Nk N P N P k k , 1 1 1 1 0 ；于是时，当, 1 1 , 11 0 N k k k k N PN 得，又设 N n n P 0 11 NkPP N k k N , 1 1 1 1 1 11 0 ；， 模型的各数量指标参数如下： 1）系统里没有顾客的概率 1 1 1 1 1 1 1 0 N P N 4 排队模型排队模型推广推广 系统容量有限的系统容量有限的 模型模型/1/NMM 2）系统里有n个顾客的概率 NnPP n n ， 0 3）在系统里的平均顾客数 1 2 1 11 11 1 1 N NN L N NN s 4）平均排队的顾客数 1 12 1 11 0 N NN PL L s q 4 排队模型排队模型推广推广 顾客源有限的顾客源有限的 模型模型mmMM/1/ 0 P