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

《数学建模排队模型2015-7-12》由会员分享，可在线阅读，更多相关《数学建模排队模型2015-7-12（91页珍藏版）》请在金锄头文库上搜索。

1、排队模型及其应用,中北大学理学院数学学科,张 峰,数学建模暑期培训系列讲座,内 容 提 纲,排队系统的优化,1 排队模型简介 （背景）,超市排队,为什么不多开个窗口,银行排队,1 排队模型简介 （背景）,服务效率忒低,购票排队,哥 要 回 家,1 排队模型简介 （背景）,高速公路车辆排队,Where is the toilet?,1 排队模型简介 （背景）,壮哉！,购票排队,1 排队模型简介 （背景）,呼叫中心排队,1 排队模型简介 （背景）,9,为什么会出现排队现象？,假定每小时平均有4位顾客到达，服务人员为每位顾客的平均服务时间为15分钟。如果顾客到达的间隔时间正好是15分钟，而服务人员为

2、每位顾客的服务时间也正好是15分钟，那么，就只需要一名服务人员，顾客也根本用不着等待。 在以下情况将出现排队现象： 平均到达率高于平均服务率 顾客到达的间隔时间不一样（随机） 服务时间不一样（随机）,1 排队模型简介 （基本概念）,排队论(Queuing Theory)，又称随机服务系统是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。,每个顾客的等待时间多长？,选择哪个队列时间最短？,多开一个窗口？ 顾客消费收入与超市成本之间博弈 怎样设计最优 ；最优运行（）,排队模型简介,1 排队模型简介 （基本概念）,一

3、、排队模型的描述,相似的特征及数学抽象,顾客到达系统的时刻是随机的，为每一位顾客提供服务的时间是随机的，因而整个排队系统的状态也是随机的，因此排队论又称为随机服务系统,顾客-请求服务的人或者物,服务员或服务台-为顾客服务的人或者物,排队模型简介,1 排队模型简介 （基本概念）,一、排队模型的描述（组成）,基本排队过程,排队系统一般有三个基本组成部分： 1.输入过程；2.排队规则；3.服务机构,排队模型简介,1 排队模型简介 （基本概念）,一、排队模型的描述（组成）,基本排队过程,1.输入过程,顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流,（1）顾客总数 有限 无限？,（2）到达方

4、式 单个 成批？,（3）顾客流的概率分布族 相继到达的顾客间的概率分布,排队模型简介,1 排队模型简介 （基本概念）,一、排队模型的描述（组成）,基本排队过程,2. 排队规则,服务台以怎样的顺序和方式服务顾客,（1）损失制 如果顾客到达排队系统时，所有服务台都已被先来的 顾客占用，那么他们就自动离开系统。,（2）等待制 当顾客来到系统时，所有服务台都不空，顾客加入排队 行列等待服务 FCFS LCFS PR RO,（3）混合制 等待制与损失制的混合 一般是指允许排队，但又不 允许队列无限长下去,排队模型简介,1 排队模型简介 （基本概念）,一、排队模型的描述（组成）,基本排队过程,3. 服务机

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

6、机构 （结构）,多队多服务台并联 大型超市、火车站窗口、医院窗口、 高速公路收费、 多车道路口车辆通行等,排队模型简介,1 排队模型简介 （基本概念）,一、排队模型的描述（组成）,基本排队过程,3. 服务机构 （结构）,单队列多服务台串联 柔性制造业 产品按工序加工,排队模型简介,1 排队模型简介 （基本概念）,二、建模过程及主要指标,建模步骤： 1 排队系统的统计推断,确定或拟合排队系统顾客到达的时间间隔分布和服务时间分布。,2 模型的性态,在确定模型的基础上，求解主要性能指标，如队长分布、等待时间分布。,3 模型进行优化,系统的最优设计（参数选择，服务质量评价）如机场跑道数量，呼 叫中心坐

7、席量。 已有系统的最优控制 如从顾客和服务机构双方利益出发，对排队系统进行最优控制,排队模型简介,1 排队模型简介 （基本概念）,二、建模过程及主要指标,主要指标： 1 队长: 系统中的顾客数, 平均队长LS,等待队长 : 系统中排队等待服务的顾客数, 平均等待队长Lq,一般情形，Ls(或Lq)越大，说明服务效率越低。,排队模型简介,1 排队模型简介 （基本概念）,二、建模过程及主要指标,主要指标：,2. 逗留时间:一个顾客在系统中的停留时间,平均逗留时间 WS,等待时间: 一个顾客排队等待的时间,平均等待时间Wq,显然，Ws(或Wq)越大，顾客满意度越低。,排队模型简介,1 排队模型简介 （

8、基本概念）,二、建模过程及主要指标,主要指标：,3. 忙期：从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度。可以衡量服务机构效率的指标，及工作强度,4. 绝对通行能力：单位时间内被服务完的平均顾客数,5. 相对通行能力：单位时间内被服务完顾客数与请求服务的顾客数之比,6. 平均被占服务台数 7 损失率,排队模型简介,1 排队模型简介 （基本概念）,三、排队模型应用,1 排队论在通信领域的应用,从20世纪60年代至今 对业务突发性和带有各种网络协议控制的通信系统进行性能评价、仿真及模拟。,20世纪初期 主要研究应用于电话网和远程通信系统等无队列的排队系统(损失制),20世纪中期 主要研

9、究通信系统中有队列(等待制)的排队系统和排队网络,排队模型简介,1 排队模型简介 （基本概念）,三、排队模型应用,2 排队论在资源分配问题中的应用 2005 研究生建模 出租车最佳数量预测,20002005 智能地雷反坦克研究，灭火兵力部署,19902000 码头与船舶的分配，工程土方的创新，停车场面积的计算，图书馆信息处理,20052010 公厕建筑面积的分配，教务处教务员岗位确定 新的前沿应用 社交网络性能 评估 云计算性能指标估计等,1 排队模型简介,三、排队模型应用,3 排队论在医疗领域中应用 2009眼科医院病床合理安排,提高医疗体系的服务效率，提高资源利用率，提高病人满意度以及缓解

10、患者于医院之间的矛盾；提出了一些具体的优化标准如下： 1、以费用作为优化指标计算最优目标值条件下最优的服务水平：总费用= 排队损失费+ 服务费 2、“优先权选择或等级”来优化医院服务 （眼科医院病床） 3、构造合理的调度方式来进行优化 4、建立了“预留病床模型，逐步优先权就诊模式”,1 排队模型简介,三、排队模型应用,排队论在交通领域中应用 2013年 A题 车道被占用对城市道路通行能力的影响,（1） 研究公交车发车间隔与排队长度 （2）研究停车场的车辆排队 （3）研究车辆排队现象、车辆延误 路口通行能力分析 5 排队论在银行中应用,2 排队模型经典排队模型,一 单服务台 排队模型,1 标准的

11、 模型,2 模型条件,模型 表示，顾客到达过程服从泊松分布，服务时间服从负指数分布，单服务台，队长和顾客来源无限.简记为 .,1）已知单位时间平均到达率 和平均服务率 . 2）系统容量无限，顾客源总数无限. 3）排队规则为单队，先到先服务,2 排队模型经典排队模型,一 单服务台 排队模型,3 模型的求解,研究系统状态的概率- 系统中顾客数。状态概率用Pn(t)表示,即在t时刻系统中有n个顾客的概率，也称瞬态概率。,实际中更关心 稳态概率,稳态概率求法 马尔科夫链理论 母函数 递推等,稳态概率求解步骤 1 画出稳态概率转移图,2 列出稳态概率平衡方程组,3 求出稳态概率或者母函数,2排队模型经典

12、排队模型,一 单服务台 排队模型,系统在稳定情况下的状态转移如图,图1.1,可以得到如下平衡方程：,4 稳态概率公式,2 排队模型经典排队模型,一 单服务台 排队模型,5 模型的数量指标公式,由（1.1）和（1.2）可以递推求解，,式中 表示平均到达率与平均服务率 之比，称为服务强度.,2 排队模型经典排队模型,一 单服务台 排队模型,6 模型的性能指标,2 排队模型经典排队模型,一 单服务台 排队模型,4）一位顾客花在系统里的平均逗留时间,5）一位顾客花在排队上的平均时间（等于逗留时间减去服 务时间） 6）顾客到达系统时，得不到及时的服务，必须等待服务的 概率 7）系统里正好有 个顾客的概率

13、,6 模型的性能指标,2 排队模型经典排队模型,一 单服务台 排队模型 应用举例,库存问题 进货多，保管费用大；存货不足缺货会引起经济损失，假设货物需求量是参数为 的泊松过程，生产一个产品实际是参数为 的指数分布，单位时间库存费用c元，缺货一个产品损失为h元，确定最优库存使得库存费和损失费之和达到最小.,分析 将生产厂看成服务机构，需求看成输入流 M/M/1 排队,平均缺货数,平均库存数,2 排队模型经典排队模型,一 单服务台 排队模型 应用举例,分析 将生产厂看成服务机构，需求看成输入流 M/M/1 排队,单位时间总费用,由边际分析法,由边际分析法,最佳s满足,36,例,一个码头，设待卸货船

14、到达时间间隔服从负指数分布，平均到达 2 艘/小时；服务台是1台吊车，卸货时间服从负指数分布，平均每 20 分钟可卸一艘货船，当被占用时，新到货船只能停在码头等待。求在平稳状态下码头上货船的平均数；等待卸货船只的平均数；每艘货船在码头的平均停留时间；货船平均需等待多长时间可以开始卸货。,2 排队模型经典排队模型,37,解：,这是一个典型的M/M/1排队问题,2 排队模型经典排队模型,38,例,某医院手术室根据病人就诊和完成手术时间的记录，任意抽查100个工作小时，每小时来就诊的病人数n的出现次数如表6所示。又任意抽查了100个完成手术的病例，所用时间t出现的次数如下表所示。试分别用公式、exc

15、el和仿真求解：,2 排队模型经典排队模型,39,到达病人数,手术时间,2 排队模型经典排队模型,40,解：,这也是一个M/M/1排队问题 （1）计算平均到达率,平均手术时间,平均服务率,2 排队模型经典排队模型,41,（2）取=2.1，=2.5，通过统计检验方法认为病人到达数服从参数为2.1的泊松分布，手术时间服从参数为2.5的指数分布。,（3）服务设备利用率,这说明服务机构（手术室）有84%的时间是繁忙的（被利用），有16%的时间是空闲的。,42,（4）依次带入公式，算出各指标得：,43,单通道Excel求解,2 排队模型经典排队模型,二 多服务台 排队模型,1 标准的 模型,2 模型描述,模型 表示，顾客到达过程服从泊松分布，服务时间服从负指数分布，C 个服务台，队长和顾客来源无限.,已知单位时间平均到达率 ， C 个服务台，每个服务台的工作相互独立且平均服务率相同，都等于 ，顾客源无限，容量无限，排队规则为等待制,3.系统的状态概率和主要运行指标,(1) 系统的状态概率 系统的空闲概率,4 系统的状态概率和主要运行指