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

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

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

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

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

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

6、到达方式到达方式 单个单个 成批？成批？ （3 3）顾客流的概率分布族顾客流的概率分布族 相继到达的顾客间的概率分布相继到达的顾客间的概率分布排队模型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念）一、排队模型的描述（组成）一、排队模型的描述（组成）基本排队过程基本排队过程2. 排队规则排队规则 服务台以怎样的顺序和方式服务顾客服务台以怎样的顺序和方式服务顾客（1 1）损失制损失制 如果顾客到达排队系统时，所有服务台都已被先来的如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统顾客占用，那么他们就自动离开系统。（2 2）等待制等待制 当顾客来到

7、系统时，所有服务台都不空，顾客加入排队当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务行列等待服务 FCFS LCFS PR RO（3 3）混合制混合制 等待制与损失制等待制与损失制的混合的混合 一般是指允许排队，但又不一般是指允许排队，但又不允许队列无限长下去允许队列无限长下去排队模型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念）一、排队模型的描述（组成）一、排队模型的描述（组成）基本排队过程基本排队过程3. 服务机构服务机构（1 1）服务台数量及构成方式服务台数量及构成方式 单服务台单服务台 多服务台；多服务台；（2 2）服务方式服务方式 单个服务，批量

8、服务；单个服务，批量服务；（3 3）服务时间的概率分布服务时间的概率分布 服务过程是泊松过程？高斯过程？服务过程是泊松过程？高斯过程？一个顾客的服务时间是指数分布还是一般概率分布？一个顾客的服务时间是指数分布还是一般概率分布？排队模型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念）一、排队模型的描述（组成）一、排队模型的描述（组成）基本排队过程基本排队过程3. 服务机构服务机构 （结构）（结构）单队多服务台并联单队多服务台并联 例如例如 学校内的一些小超市学校内的一些小超市排队模型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念）一、排队模型的描述（组

9、成）一、排队模型的描述（组成）基本排队过程基本排队过程3. 服务机构服务机构 （结构）（结构）单队多服务台并联单队多服务台并联 （银行排队）（银行排队）排队模型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念）一、排队模型的描述（组成）一、排队模型的描述（组成）基本排队过程基本排队过程3. 服务机构服务机构 （结构）（结构）多队多服务台并联多队多服务台并联 大型超市、火车站窗口、医院窗大型超市、火车站窗口、医院窗口、口、 高速公路收费、高速公路收费、 多车道路口车辆通行等多车道路口车辆通行等排队模型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念）一、排

10、队模型的描述（组成）一、排队模型的描述（组成）基本排队过程基本排队过程3. 服务机构服务机构 （结构）（结构）单队列多服务台串联单队列多服务台串联 柔性制造业柔性制造业 产品按工序加工产品按工序加工 排队模型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念）二、建模过程及主要指标二、建模过程及主要指标 1 排队系统的统计推断排队系统的统计推断 确定或拟合排队系统顾客到达的时间间隔分布和服务时间分布确定或拟合排队系统顾客到达的时间间隔分布和服务时间分布。2 模型的性态模型的性态在确定模型的基础上，求解主要性能指标，如队长分布、等在确定模型的基础上，求解主要性能指标，如队长分布

11、、等待时间分布。待时间分布。3 模型进行优化模型进行优化系统的最优设计（系统的最优设计（参数选择，服务质量评价）如机场跑道数量，呼参数选择，服务质量评价）如机场跑道数量，呼 叫中心坐席量。叫中心坐席量。已有系统的最优控制已有系统的最优控制 如从顾客和服务机构双方利益出发，对排队如从顾客和服务机构双方利益出发，对排队系统进行最优控制系统进行最优控制排队模型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念）二、建模过程及主要指标二、建模过程及主要指标 1 队长队长: 系统中的顾客数系统中的顾客数, 平均队长平均队长LS 等待队长等待队长 : 系统中排队等待服务的顾客数系统中排队

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

13、服务时间服务时间+逗留时间逗留时间= =显然，显然，Ws(或或Wq)越大，顾客满意度越低。越大，顾客满意度越低。排队模型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念）二、建模过程及主要指标二、建模过程及主要指标 3. 忙期忙期：从顾客到达空闲服务机构起到服务机构再次为从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度。空闲这段时间长度。可以衡量服务机构效率的指标，及可以衡量服务机构效率的指标，及工作强度工作强度4. 绝对通行能力绝对通行能力：单位时间内被服务完的平均顾客数：单位时间内被服务完的平均顾客数5. 相对通行能力相对通行能力：单位时间内被服务完顾客数与请求

14、服：单位时间内被服务完顾客数与请求服务的顾客数之比务的顾客数之比6. 平均被占服务台数平均被占服务台数 7 损失率损失率 排队模型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念）三、排队模型应用三、排队模型应用从从2020世纪世纪6060年代至今年代至今 对业务突发性和带有各种网络协议控制的通信系统进行对业务突发性和带有各种网络协议控制的通信系统进行性能评价、仿真及模拟性能评价、仿真及模拟。2020世纪初期世纪初期 主要研究应用于电话网和远程通信系统等无队列的排队主要研究应用于电话网和远程通信系统等无队列的排队系统系统( (损失制损失制) )2020世纪中期世纪中期 主要

15、研究通信系统中有队列主要研究通信系统中有队列( (等待制等待制) )的排队系统和排队网络的排队系统和排队网络排队模型排队模型简介简介1 排队模型排队模型简介简介 （基本概念）（基本概念）三、排队模型应用三、排队模型应用2005 2005 研究生建模研究生建模 出租车最佳数量预测出租车最佳数量预测20002005 20002005 智能地雷反坦克研究，灭火兵力部署智能地雷反坦克研究，灭火兵力部署19902000 19902000 码头与船舶的分配，工程土方的创新，停车场面码头与船舶的分配，工程土方的创新，停车场面积的计算，图书馆信息处理积的计算，图书馆信息处理20052010 20052010

16、公厕建筑面积的分配，教务处教务员岗位确定公厕建筑面积的分配，教务处教务员岗位确定 新的前沿应用新的前沿应用 社交网络性能社交网络性能 评估评估 云计算性能指标估计等云计算性能指标估计等1 排队模型排队模型简介简介三、排队模型应用三、排队模型应用20092009眼科医院病床合理安排眼科医院病床合理安排提高医疗体系的服务效率，提高资源利用率，提高病人满意度以及缓解患者于医院之间的矛盾；提出了一些具体的优化标准如下：1、以费用作为优化指标计算最优目标值条件下最优的服务水平：总费用= 排队损失费+ 服务费 2、“优先权选择或等级”来优化医院服务 （眼科医院病床）3、构造合理的调度方式来进行优化4、建立

17、了“预留病床模型，逐步优先权就诊模式”1 排队模型排队模型简介简介三、排队模型应用三、排队模型应用20132013年年 A A题题 车道被占用对城市道路通行能力的影响车道被占用对城市道路通行能力的影响 （1） 研究公交车发车间隔与排队长度 （2）研究停车场的车辆排队 （3）研究车辆排队现象、车辆延误 路口通行能力分析 2 排队模型排队模型经典排队模型经典排队模型一 单服务台 排队模型1 标准的标准的 模型模型1/MM2 模型条件模型条件 模型模型 表示，顾客到达过程服从泊松分布，表示，顾客到达过程服从泊松分布，服务时间服从负指数分布，单服务台，队长和顾客来源无服务时间服从负指数分布，单服务台，

18、队长和顾客来源无限限.简记为简记为 ./1/ MM1/ MM1）已知单位时间平均到达率）已知单位时间平均到达率 和平均服务率和平均服务率 .2）系统容量无限，顾客源总数无限）系统容量无限，顾客源总数无限.3）排队规则为单队，先到先服务）排队规则为单队，先到先服务)(1/MM2 排队模型排队模型经典排队模型经典排队模型一 单服务台 排队模型3 模型的求解模型的求解1/MM1/MM 研究研究系统状态的概率系统状态的概率- - 系统中顾客数。状态概率用系统中顾客数。状态概率用Pn( (t) )表表示示, ,即在即在t时刻系统中有时刻系统中有n个顾客的概率，也称瞬态概率。个顾客的概率，也称瞬态概率。

19、实际中更关心实际中更关心 稳态概率稳态概率 limnntPP t稳态概率求法稳态概率求法 马尔科夫链理论马尔科夫链理论 母函数母函数 递推等递推等稳态概率求解步骤稳态概率求解步骤 1 画出稳态概率转移图画出稳态概率转移图 2 列出稳态概率平衡方程组列出稳态概率平衡方程组3 求出稳态概率或者母函数求出稳态概率或者母函数2排队模型排队模型经典排队模型经典排队模型一 单服务台 排队模型1/MM系统在稳定情况下的状态转移如图系统在稳定情况下的状态转移如图图1.1Pn 1P2P1P0PnPn 1 可以得到如下平衡方程可以得到如下平衡方程：nnnPPP11（1.1）01PP（1.2）4 稳态概率公式稳态概

20、率公式2 排队模型排队模型经典排队模型经典排队模型一 单服务台 排队模型1/MM5 5 模型的数量指标公式模型的数量指标公式由（1.1）和（1.2）可以递推求解，01PP02102)()1 (-PPPP.0)(PPnn.nnPP110式中 表示平均到达率与平均服务率之比，称为服务强度.2 排队模型排队模型经典排队模型经典排队模型一 单服务台 排队模型1/MM6 模型的性能指标模型的性能指标 1）在系统里没有顾客的概）在系统里没有顾客的概率率2011111LPLPnPPnLnnnnnnq10P000)1 ()1 (nqnnnnnsLkknPL2）平均排队的顾客数平均排队的顾客数 3）在系统里的平

21、均顾客数）在系统里的平均顾客数u2 排队模型排队模型经典排队模型经典排队模型一 单服务台 排队模型1/MM 4 4）一位顾客花在系统里的平均逗留时间）一位顾客花在系统里的平均逗留时间1)(XEWs 5 5）一位顾客花在排队上的平均时间（等于逗留时间减去服）一位顾客花在排队上的平均时间（等于逗留时间减去服 务时间）务时间） 6 6）顾客到达系统时，得不到及时的服务，必须等待服务的）顾客到达系统时，得不到及时的服务，必须等待服务的 概率概率 7 7）系统里正好有）系统里正好有 个顾客的概率个顾客的概率1qsWW 01wPP 0)(PPnnn6 模型的性能指标模型的性能指标2 排队模型排队模型经典排

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

23、排队平均缺货数平均缺货数11squenn sEns p平均库存数平均库存数1011sscunnnEsn ps2 排队模型排队模型经典排队模型经典排队模型一 单服务台 排队模型 应用举例应用举例 1/MM分析分析 将生产厂看成服务机构，需求看成输入流将生产厂看成服务机构，需求看成输入流 M/M/1 排队排队单位时间总费用单位时间总费用 1111sscunquef scEhEc sh由边际分析法由边际分析法 1f sf s 1f sf s由边际分析法由边际分析法scch1scch最佳最佳s满足满足ln/ln1ln/lnccschch 36例例一个码头，设待卸货船到达时间间隔服从负指数一个码头，设待

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

25、个典型的这是一个典型的M/M/1排队排队问题问题213r260320u 22()32sLu艘24233qsLLr(艘)423()23LqWq小时21()2LsWs小时2 排队模型排队模型经典排队模型经典排队模型38例例某医院手术室根据病人就诊和完成手术时间某医院手术室根据病人就诊和完成手术时间的记录，任意抽查的记录，任意抽查100个工作小时，每小时个工作小时，每小时来就诊的病人数来就诊的病人数n的出现次数如表的出现次数如表6所示。又所示。又任意抽查了任意抽查了100个完成手术的病例，所用时个完成手术的病例，所用时间间t出现的次数如下表所示。试分别用公式、出现的次数如下表所示。试分别用公式、ex

26、cel和仿真求解：和仿真求解：2 排队模型排队模型经典排队模型经典排队模型39 到达病人数到达病人数 n出现次数出现次数 f n0101282293164105661合计合计100到达病人数到达病人数为病人完成手术为病人完成手术时间时间t/小时小时出现次数出现次数 ft 0.00.2380.20.4250.40.6170.6 1.890.81.061.01.251.20合计合计100手术时间手术时间2 排队模型排队模型经典排队模型经典排队模型40解：解：这也是一个这也是一个M/M/1排队排队问题问题（1）计算平均到达率）计算平均到达率2.1(/)100nnf人 时 平均手术时间平均手术时间0.

27、4()100ttfT 时/人 平均服务率平均服务率12.5()0.4u 人/时2 排队模型排队模型经典排队模型经典排队模型41（2）取）取=2.1，=2.5，通过统计检验方法认为病人到达，通过统计检验方法认为病人到达数服从参数为数服从参数为2.1的泊松分布，手术时间服从参数为的泊松分布，手术时间服从参数为2.5的指数分布。的指数分布。（3）服务设备利用率服务设备利用率2.10.842.5 这说明服务机构（手术室）有这说明服务机构（手术室）有84%的时间是繁忙的时间是繁忙的的（被利用），有（被利用），有16%的时间是空闲的。的时间是空闲的。420.84ru2.12.5u 2.15.25()2.5

28、2.1sLu人5.250.844.41qsLLr(人)4.412.1()2.1LqWq小时5.252.5()2.1LsWs小时（4）依次带入公式，算出各指标得：依次带入公式，算出各指标得：43单通道单通道Excel求解求解2 排队模型排队模型经典排队模型经典排队模型二二 多服务台 排队模型1 标准的标准的 模型模型/M M c2 模型描述模型描述 模型模型 表示，顾客到达过程服从泊松分布，服表示，顾客到达过程服从泊松分布，服务时间服从负指数分布，务时间服从负指数分布，C 个服务台，队长和顾客来源无个服务台，队长和顾客来源无限限./MMC/M M C 已知单位时间平均到达率已知单位时间平均到达率

29、 ， C 个服务台，每个服务台个服务台，每个服务台的工作相互独立且平均服务率相同，都等于的工作相互独立且平均服务率相同，都等于 ，顾客源无限，顾客源无限，容量无限，排队规则为等待制容量无限，排队规则为等待制3.系统的状态概率和主要运行指标系统的状态概率和主要运行指标)1(n)1(nn20P2P1P1nPnP1nP,)(,)1(,111101cnnnnnPcPcPPnPPnPP）（),.,2, 1(cn ,.)2, 1(ccn(1) 系统的状态概率系统的状态概率系统的空闲概率4 系统的状态概率和主要运行指标系统的状态概率和主要运行指标系统内有n个顾客的概率CnPCCCnPnPnCnnn00)(!

30、1)(!11100)(11!1)(!1CkCkCkP1C2 排队模型排队模型经典排队模型经典排队模型二二 多服务台 排队模型4 主要运行指标主要运行指标/M M C02()!(1)1cqqqqqcLPLLcLLWWW系统平均队长、平均等待时间平均占用服务台数K系统通行能力 0LP损失率系统相对通过能力11LQP系统绝对通过能力AQ48例例某售票所有三个窗口，顾客的到达服从泊松分布，某售票所有三个窗口，顾客的到达服从泊松分布，平均到达速率平均到达速率 = 0.9人人/min；售票时间服从负指；售票时间服从负指数分布，平均服务速率数分布，平均服务速率= 0.4人人/min 。现设顾客到。现设顾客到

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

32、 (1) 整个售票所空闲概率整个售票所空闲概率r1100!(1)nccnrrPnc012352.2510!1!2!3!10.750.07482 排队模型排队模型经典排队模型经典排队模型51(2) 平均排队长度和平均队列长平均排队长度和平均队列长02!(1)cqrLpc322.250.750.07481.703!(10.75)1.702.253.95sqLLr(3)平均等待时间和逗留时间平均等待时间和逗留时间1.701.890.9qqLW111.894.390.4sqWWu2 排队模型排队模型经典排队模型经典排队模型52(4)顾客到达后必须等待的概率（

33、顾客到达后必须等待的概率（n3)331nnPPnP0!nrpn(0)nc01!nncrpccg()nc00.0748P 230(1)(12.252.531)0.07480.4322nrPrP2 排队模型排队模型经典排队模型经典排队模型53M/M/3 Excel求解求解54例例 银行取号系统有用吗？银行取号系统有用吗？就例就例5，如果其他条件不变，顾客到达后在每个窗，如果其他条件不变，顾客到达后在每个窗口前各排一队，且进入队列后坚持不换，就形成口前各排一队，且进入队列后坚持不换，就形成3个队列，如下图所示。试分别用公式、个队列，如下图所示。试分别用公式、excel求解：求解：u(1) 整个售票所

34、空闲概率整个售票所空闲概率u(2) 平均队列长度和平均队长平均队列长度和平均队长u(3) 平均等待时间和逗留时间平均等待时间和逗留时间u(4)顾客到达后必须等待的概率（顾客到达后必须等待的概率（n3)2 排队模型排队模型经典排队模型经典排队模型55顾客到达和服务图顾客到达和服务图2 排队模型排队模型经典排队模型经典排队模型56解：解：这是这是3个个M/M/1同时服务的同时服务的排队排队问题问题0.30.7510.4r0.30.4u (1) 整个售票所空闲概率整个售票所空闲概率(每个窗口空闲每个窗口空闲)0110.750.25p(4)顾客到达必须等待的概率（每个窗口顾客到达必须等待的概率（每个窗

35、口n1)10110.250.75npP2 排队模型排队模型经典排队模型经典排队模型57(2) 平均排队长度和平均队列长平均排队长度和平均队列长0.30.7qLu2.250.753sqLLr(3)平均等待时间和逗留时间平均等待时间和逗留时间2.257.50.3qqLW3100.3ssLW339系 统 （ 3个 窗 口 ） 队 长2 排队模型排队模型经典排队模型经典排队模型583个个M/M/1 Excel求解求解2 排队模型排队模型经典排队模型经典排队模型59结论：银行取号系统是有效的结论：银行取号系统是有效的指标指标数值数值排队长度排队长度1.70系统队长系统队长3.95平

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

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

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

39、与等待成本的权衡（成本效益平衡）总成本成本最佳能力等待成本服务成本最小值排队分析的目的是使顾客等待成本与服务能力成本这两项成本之和最小3 排队模型排队模型排队模型的优化排队模型的优化69M/M/1模型中的最优服务率模型中的最优服务率u 最佳服务能力是使总成本最小化：总成本=顾客等候成本+服务能力成本1wswssCuC uC LCz为时服务机构单位时间的费用为每个顾客在系统中逗即：留时间的费用/1SMMLu模型中 swzC uCu所以：3 排队模型排队模型排队模型的优化排队模型的优化70 M/M/1模型中的最优服务率模型中的最优服务率u swzC uCu0dzdu令20()swCCu即：所以M/

40、M/1模型的最优服务率为：wsCuC3 排队模型排队模型排队模型的优化排队模型的优化71例例设某服务机构，单服务台，顾客到达率为每设某服务机构，单服务台，顾客到达率为每小时小时12位顾客。假定每位接受顾客的顾客其位顾客。假定每位接受顾客的顾客其等待费用为每小时等待费用为每小时5元，服务成本为每位顾元，服务成本为每位顾客客2元，欲使总平均费用最小，服务率应为元，欲使总平均费用最小，服务率应为多少？多少？3 排队模型排队模型排队模型的优化排队模型的优化72解：解：这是一个标准的这是一个标准的M/M/1排队排队问题问题2sC元12/ h人5wC元因而swSzC uC L最小总费用5121217.5(

41、/ h)2wsCuC最优服务率人122.1817.512sLu*217.552.1846Z120.68617.5u最优系统利用率3 排队模型排队模型排队模型的优化排队模型的优化73、Lq 、Ls三者的关系三者的关系-1当系统利用率增加时，队列平均等候数与顾当系统利用率增加时，队列平均等候数与顾客排队等候的平均时间呈指数增长。客排队等候的平均时间呈指数增长。3 排队模型排队模型排队模型的优化排队模型的优化74队列中平均等 侯数100% 系统利用率 0、Lq 、Ls三者的关系-2qqLWqW./ 1exMM 3 排队模型排队模型排队模型的优化排队模型的优化75、Lq 、Ls三者的关系三者的关系-3

42、平均队长（和平均等待时间）与服务台利用平均队长（和平均等待时间）与服务台利用率之间的关系不是线性的关系。资产利用率率之间的关系不是线性的关系。资产利用率太高会造成服务质量急速下降，因而要权衡太高会造成服务质量急速下降，因而要权衡利弊。利弊。要保证服务质量，就必须保持要保证服务质量，就必须保持“过剩过剩的的”生产或服务能力。生产或服务能力。3 排队模型排队模型排队模型的优化排队模型的优化76 仅讨论标准的仅讨论标准的M/M/C模型，且在稳态下，单位时间全部费用模型，且在稳态下，单位时间全部费用的期望值为：的期望值为：(包括服务成本与等待费用包括服务成本与等待费用)zC sCC wL式中式中: :

43、 每个服务台单位服务时间成本；每个服务台单位服务时间成本； 每个顾客在系统中停留单位时间成本每个顾客在系统中停留单位时间成本； L系统中顾客的平均数系统中顾客的平均数Ls或队列平均数或队列平均数Lq，是是C的函的函数数。这里这里Z是是C的函数的函数,且且C只能取整数解只能取整数解,故不能用微分法求故不能用微分法求C*, 而只而只能用边际分析法能用边际分析法(Marginal Analysis)：CsCw3 排队模型排队模型排队模型的优化排队模型的优化77因为因为 z(c*) 是最小值，则有是最小值，则有：) 1 () 1*() 1*(*)(* CLCwCsCCLCwCsC)1*(*)(czcz

44、) 1*(*)(czcz将将z期望费用公式代入：期望费用公式代入：)2() 1*() 1*(*)(* CLCwCsCCLCwCsC*)()1*(/)1(CLCLCwsC得：由)1*(*)(/)2(CLCLCwsC得：由合并化简得合并化简得：*)() 1*(/) 1*(*)(CLCLCsCCLCLw依次求依次求C=1,2,3C=1,2,3，的的 L L值，即可找出符合上式的值，即可找出符合上式的C C* *。78 例例6某检验中心，为各用户检验产品，用户每天到达按泊松流某检验中心，为各用户检验产品，用户每天到达按泊松流=48个个/天，每个用户每天停工损失天，每个用户每天停工损失6元，服务时间服从

45、负指数元，服务时间服从负指数分布分布=25个个/天，每设天，每设1个检验台每天服务成本个检验台每天服务成本4元，其他条件为元，其他条件为标准标准M/M/C模型，问设几个服务台费用最少？模型，问设几个服务台费用最少？ 解：解： =4元元 Cw=6=48 =25,下面再分别计算当服务台下面再分别计算当服务台C=1,2,3,时时Ls值。计算过程如下：值。计算过程如下：C12345/cWq.Ls1.92-0.9610.255021.6100.640.39612.6800.480.07722.0680.380.01701.952Cs79 计算计算 L(CL(C* *)-L(C)-L(C* *+1)+1)

46、及及 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.612667.03/26/4/ CwsC即为所求。3* C0.612/18.930C sC w（见陆书（见陆书239239页队长表达式）页队长表达式） 系统容量有限的系统容量有限的 模型模型/1/NMM 系统容量为N，系统中排队等待的顾客数最多为N-1，所以在某一时刻某位顾客到达时，如果系统中已有N位顾客，那么这位顾客被拒绝进入系统，如图2.2N-1 N0PnP1nP2P1P图2.2由状态转移图，可以建立系统概率平衡方程如下：,)(,11101NNkkkPPPPPPP1 Nk4 排队模型排队模型推广推广 系统容量有限的系统容量有限的 模型模型/1/NMMNkNPNPkk,11110；于是时，当,11, 110NkkkkNPN得，又设NnnP011NkPPNkkN,11111110；，模型的各数量指标参数如下： 1）系统里没有顾客的概率11111110NPN4 排队模型排队模型推广推广 系统容量有限的系统容量有限的 模型模型/1/NMM 2）系统里有n个顾客的概率NnPPnn