数学建模排队模型课件

排队模型及其应用 张峰 数学建模暑期培训系列讲座 内容提纲 排队系统的优化 1排队模型 简介 背景 超市排队 为什么不多开个窗口 银行排队 1排队模型 简介 背景 服务效率忒低 购票排队 哥要回家 1排队模型 简介 背景 高速公路车辆排队 Whereisthetoilet 1排队模型 简介 背景 壮哉 购票排队 1排队模型 简介 背景 呼叫中心排队 1排队模型 简介 背景 为什么会出现排队现象 假定每小时平均有4位顾客到达 服务人员为每位顾客的平均服务时间为15分钟 如果顾客到达的间隔时间正好是15分钟 而服务人员为每位顾客的服务时间也正好是15分钟 那么 就只需要一名服务人员 顾客也根本用不着等待 在以下情况将出现排队现象 平均到达率高于平均服务率顾客到达的间隔时间不一样 随机 服务时间不一样 随机 9 1排队模型 简介 基本概念 排队论 QueuingTheory 又称随机服务系统是一门研究拥挤现象 排队 等待 的科学 具体地说 它是在研究各种排队系统概率规律性的基础上 解决相应排队系统的最优设计和最优控制问题 每个顾客的等待时间多长 选择哪个队列时间最短 多开一个窗口 顾客消费收入与超市成本之间博弈怎样设计最优 最优运行 排队模型 简介 1排队模型 简介 基本概念 一 排队模型的描述 相似的特征及数学抽象 顾客到达系统的时刻是随机的 为每一位顾客提供服务的时间是随机的 因而整个排队系统的状态也是随机的 因此排队论又称为随机服务系统 顾客 请求服务的人或者物 服务员或服务台 为顾客服务的人或者物 排队模型 简介 1排队模型 简介 基本概念 一 排队模型的描述 组成 基本排队过程 排队系统一般有三个基本组成部分 1 输入过程 2 排队规则 3 服务机构 排队模型 简介 1排队模型 简介 基本概念 一 排队模型的描述 组成 基本排队过程 1 输入过程 顾客是按怎样的规律到达排队系统的过程 有时也把它称为顾客流 1 顾客总数有限无限 2 到达方式单个成批 3 顾客流的概率分布族相继到达的顾客间的概率分布 排队模型 简介 1排队模型 简介 基本概念 一 排队模型的描述 组成 基本排队过程 2 排队规则 服务台以怎样的顺序和方式服务顾客 1 损失制如果顾客到达排队系统时 所有服务台都已被先来的顾客占用 那么他们就自动离开系统 2 等待制当顾客来到系统时 所有服务台都不空 顾客加入排队行列等待服务FCFSLCFSPRRO 3 混合制等待制与损失制的混合一般是指允许排队 但又不允许队列无限长下去 排队模型 简介 1排队模型 简介 基本概念 一 排队模型的描述 组成 基本排队过程 3 服务机构 1 服务台数量及构成方式单服务台多服务台 2 服务方式单个服务 批量服务 3 服务时间的概率分布服务过程是泊松过程 高斯过程 一个顾客的服务时间是指数分布还是一般概率分布 排队模型 简介 1排队模型 简介 基本概念 一 排队模型的描述 组成 基本排队过程 3 服务机构 结构 单队多服务台并联例如学校内的一些小超市 排队模型 简介 1排队模型 简介 基本概念 一 排队模型的描述 组成 基本排队过程 3 服务机构 结构 单队多服务台并联 银行排队 排队模型 简介 1排队模型 简介 基本概念 一 排队模型的描述 组成 基本排队过程 3 服务机构 结构 多队多服务台并联大型超市 火车站窗口 医院窗口 高速公路收费 多车道路口车辆通行等 排队模型 简介 1排队模型 简介 基本概念 一 排队模型的描述 组成 基本排队过程 3 服务机构 结构 单队列多服务台串联柔性制造业产品按工序加工 排队模型 简介 1排队模型 简介 基本概念 二 建模过程及主要指标 建模步骤 1排队系统的统计推断 确定或拟合排队系统顾客到达的时间间隔分布和服务时间分布 2模型的性态 在确定模型的基础上 求解主要性能指标 如队长分布 等待时间分布 3模型进行优化 系统的最优设计 参数选择 服务质量评价 如机场跑道数量 呼叫中心坐席量 已有系统的最优控制如从顾客和服务机构双方利益出发 对排队系统进行最优控制 排队模型 简介 1排队模型 简介 基本概念 二 建模过程及主要指标 主要指标 1队长 系统中的顾客数 平均队长LS 等待队长 系统中排队等待服务的顾客数 平均等待队长Lq 一般情形 Ls 或Lq 越大 说明服务效率越低 排队模型 简介 1排队模型 简介 基本概念 二 建模过程及主要指标 主要指标 2 逗留时间 一个顾客在系统中的停留时间 平均逗留时间WS 等待时间 一个顾客排队等待的时间 平均等待时间Wq 显然 Ws 或Wq 越大 顾客满意度越低 排队模型 简介 1排队模型 简介 基本概念 二 建模过程及主要指标 主要指标 3 忙期 从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度 可以衡量服务机构效率的指标 及工作强度 4 绝对通行能力 单位时间内被服务完的平均顾客数 5 相对通行能力 单位时间内被服务完顾客数与请求服务的顾客数之比 6 平均被占服务台数7损失率 排队模型 简介 1排队模型 简介 基本概念 三 排队模型应用 1排队论在通信领域的应用 从20世纪60年代至今对业务突发性和带有各种网络协议控制的通信系统进行性能评价 仿真及模拟 20世纪初期主要研究应用于电话网和远程通信系统等无队列的排队系统 损失制 20世纪中期主要研究通信系统中有队列 等待制 的排队系统和排队网络 排队模型 简介 1排队模型 简介 基本概念 三 排队模型应用 2排队论在资源分配问题中的应用2005研究生建模出租车最佳数量预测 2000 2005智能地雷反坦克研究 灭火兵力部署 1990 2000码头与船舶的分配 工程土方的创新 停车场面积的计算 图书馆信息处理 2005 2010公厕建筑面积的分配 教务处教务员岗位确定新的前沿应用社交网络性能评估云计算性能指标估计等 1排队模型 简介 三 排队模型应用 3排队论在医疗领域中应用2009眼科医院病床合理安排 提高医疗体系的服务效率 提高资源利用率 提高病人满意度以及缓解患者于医院之间的矛盾 提出了一些具体的优化标准如下 1 以费用作为优化指标计算最优目标值条件下最优的服务水平 总费用 排队损失费 服务费2 优先权选择或等级 来优化医院服务 眼科医院病床 3 构造合理的调度方式来进行优化4 建立了 预留病床模型 逐步优先权就诊模式 1排队模型 简介 三 排队模型应用 排队论在交通领域中应用2013年A题车道被占用对城市道路通行能力的影响 1 研究公交车发车间隔与排队长度 2 研究停车场的车辆排队 3 研究车辆排队现象 车辆延误路口通行能力分析5排队论在银行中应用 2排队模型 经典排队模型 一单服务台排队模型 1标准的模型 2模型条件 模型表示 顾客到达过程服从泊松分布 服务时间服从负指数分布 单服务台 队长和顾客来源无限 简记为 1 已知单位时间平均到达率和平均服务率 2 系统容量无限 顾客源总数无限 3 排队规则为单队 先到先服务 2排队模型 经典排队模型 一单服务台排队模型 3模型的求解 研究系统状态的概率 系统中顾客数 状态概率用Pn t 表示 即在t时刻系统中有n个顾客的概率 也称瞬态概率 实际中更关心稳态概率 稳态概率求法马尔科夫链理论母函数递推等 稳态概率求解步骤1画出稳态概率转移图 2列出稳态概率平衡方程组 3求出稳态概率或者母函数 2排队模型 经典排队模型 一单服务台排队模型 系统在稳定情况下的状态转移如图 图1 1 可以得到如下平衡方程 4稳态概率公式 2排队模型 经典排队模型 一单服务台排队模型 5模型的数量指标公式 由 1 1 和 1 2 可以递推求解 式中表示平均到达率与平均服务率之比 称为服务强度 2排队模型 经典排队模型 一单服务台排队模型 6模型的性能指标 2排队模型 经典排队模型 一单服务台排队模型 4 一位顾客花在系统里的平均逗留时间 5 一位顾客花在排队上的平均时间 等于逗留时间减去服务时间 6 顾客到达系统时 得不到及时的服务 必须等待服务的概率7 系统里正好有个顾客的概率 6模型的性能指标 2排队模型 经典排队模型 一单服务台排队模型应用举例 库存问题进货多 保管费用大 存货不足缺货会引起经济损失 假设货物需求量是参数为的泊松过程 生产一个产品实际是参数为的指数分布 单位时间库存费用c元 缺货一个产品损失为h元 确定最优库存使得库存费和损失费之和达到最小 分析将生产厂看成服务机构 需求看成输入流M M 1排队 平均缺货数 平均库存数 2排队模型 经典排队模型 一单服务台排队模型应用举例 分析将生产厂看成服务机构 需求看成输入流M M 1排队 单位时间总费用 由边际分析法 由边际分析法 最佳s满足 例 一个码头 设待卸货船到达时间间隔服从负指数分布 平均到达2艘 小时 服务台是1台吊车 卸货时间服从负指数分布 平均每20分钟可卸一艘货船 当被占用时 新到货船只能停在码头等待 求在平稳状态下码头上货船的平均数 等待卸货船只的平均数 每艘货船在码头的平均停留时间 货船平均需等待多长时间可以开始卸货 2排队模型 经典排队模型 36 解 这是一个典型的M M 1排队问题 2排队模型 经典排队模型 37 例 某医院手术室根据病人就诊和完成手术时间的记录 任意抽查100个工作小时 每小时来就诊的病人数n的出现次数如表6所示 又任意抽查了100个完成手术的病例 所用时间t出现的次数如下表所示 试分别用公式 excel和仿真求解 2排队模型 经典排队模型 38 到达病人数 手术时间 2排队模型 经典排队模型 39 解 这也是一个M M 1排队问题 1 计算平均到达率 平均手术时间 平均服务率 2排队模型 经典排队模型 40 2 取 2 1 2 5 通过统计检验方法认为病人到达数服从参数为2 1的泊松分布 手术时间服从参数为2 5的指数分布 3 服务设备利用率 这说明服务机构 手术室 有84 的时间是繁忙的 被利用 有16 的时间是空闲的 41 4 依次带入公式 算出各指标得 42 单通道Excel求解 43 2排队模型 经典排队模型 二多服务台排队模型 1标准的模型 2模型描述 模型表示 顾客到达过程服从泊松分布 服务时间服从负指数分布 C个服务台 队长和顾客来源无限 已知单位时间平均到达率 C个服务台 每个服务台的工作相互独立且平均服务率相同 都等于 顾客源无限 容量无限 排队规则为等待制 3 系统的状态概率和主要运行指标 45 PPT学习交流 2020 4 16 1 系统的状态概率系统的空闲概率 4系统的状态概率和主要运行指标 系统内有n个顾客的概率 46 PPT学习交流 2020 4 16 2排队模型 经典排队模型 二多服务台排队模型 4主要运行指标 系统平均队长 平均等待时间 平均占用服务台数 系统通行能力 损失率 系统相对通过能力 系统绝对通过能力 47 PPT学习交流 2020 4 16 例 某售票所有三个窗口 顾客的到达服从泊松分布 平均到达速率 0 9人 min 售票时间服从负指数分布 平均服务速率 0 4人 min 现设顾客到达后排成一队 依次向空闲的窗口购票 如图所示 试分别用公式 excel和仿真求解 1 整个售票所空闲概率 2 平均队列长和平均队长 3 平均等待时间和逗留时间 4 顾客到达后必须等待的概率 n 3 2排队模型 经典排队模型 48 顾客到达和服务图 2排队模型 经典排队模型 49 解 这是一个典型的M M C排队问题 1 整个售票所空闲概率 2排队模型 经典排队模型 50 2 平均排队长度和平均队列长 3 平均等待时间和逗留时间 2排队模型 经典排队模型 51 4 顾客到达后必须等待的概率 n 3 2排队模型 经典排队模型 52 M M 3Excel求解 53 例银行取号系统有用吗 就例5 如果其他条件不变 顾客到达后在每个窗口前各排一队 且进入队列后坚持不换 就形成3个队列 如下图所示 试分别用公式 excel求解 1 整个售票所空闲概率 2 平均队列长度和平均队长 3 平均等待时间和逗留时间 4 顾客到达后必须等待的概率 n 3 2排队模型 经典排队模型 54 顾客到达和服务图 2排队模型 经典排队模型 55 解 这是3个M M 1同时服务的排队问题 1 整个售票所空闲概率 每个窗口空闲 4 顾客到达必须等待的概率 每个窗口n 1 2排队模型 经典排队模型 56 2 平均排队长度和平均队列长 3 平均等待时间和逗留时间 2排队模型 经典排队模型 57 3个M M 1Excel求解 2排队模型 经典排队模型 58 结论 银行取号系统是有效的 59 2排队模型 经典排队模型 二多服务台排队模型 眼科医院病床安排 60 PPT学习交流 2020 4 16 2排队模型 经典排队模型 眼科医院病床安排 简单而言 每一类病人应安排多少床位 61 PPT学习交流 2020 4 16 2排队模型 经典排队模型 眼科医院病床安排 62 PPT学习交流 2020 4 16 2排队模型 经典排队模型 眼科医院病床安排 63 PPT学习交流 2020 4 16 2排队模型 经典排队模型 二多服务台排队模型 车道被占用对城市道路通行能力的影响 1根据视频1 附件1 描述视频中交通事故发生至撤离期间 事故所处横断面实际通行能力的变化过程 2根据问题1所得结论 结合视频2 附件2 分析说明同一横断面交通事故所占车道不同对该横断面实际通行能力影响的差异 64 PPT学习交流 2020 4 16 2排队模型 经典排队模型 二多服务台排队模型 车道被占用对城市道路通行能力的影响 65 PPT学习交流 2020 4 16 2排队模型 经典排队模型 二多服务台排队模型 车道被占用对城市道路通行能力的影响 66 PPT学习交流 2020 4 16 排队系统最优设计 成本分析1概述 排队系统的最优设计和最优控制 即排队系统的最优化问题 其目的在于使排队系统达到最大效益或者说在一定指标下使排队系统最为经济 3排队模型 排队模型的优化 67 服务成本与等待成本的权衡 成本 效益平衡 排队分析的目的是使顾客等待成本与服务能力成本这两项成本之和最小 3排队模型 排队模型的优化 68 M M 1模型中的最优服务率u 最佳服务能力是使总成本最小化 总成本 顾客等候成本 服务能力成本 3排队模型 排队模型的优化 69 M M 1模型中的最优服务率u 所以M M 1模型的最优服务率为 3排队模型 排队模型的优化 70 例 设某服务机构 单服务台 顾客到达率为每小时12位顾客 假定每位接受顾客的顾客其等待费用为每小时5元 服务成本为每位顾客2元 欲使总平均费用最小 服务率应为多少 3排队模型 排队模型的优化 71 解 这是一个标准的M M 1排队问题 3排队模型 排队模型的优化 72 Lq Ls三者的关系 1 当系统利用率增加时 队列平均等候数与顾客排队等候的平均时间呈指数增长 3排队模型 排队模型的优化 73 Lq Ls三者的关系 2 3排队模型 排队模型的优化 74 Lq Ls三者的关系 3 平均队长 和平均等待时间 与服务台利用率之间的关系不是线性的关系 资产利用率太高会造成服务质量急速下降 因而要权衡利弊 要保证服务质量 就必须保持 过剩的 生产或服务能力 3排队模型 排队模型的优化 75 M M C模型中最优服务台数C 仅讨论标准的M M C模型 且在稳态下 单位时间全部费用的期望值为 包括服务成本与等待费用 式中 每个服务台单位服务时间成本 每个顾客在系统中停留单位时间成本 L 系统中顾客的平均数Ls或队列平均数Lq 是C的函数 这里Z是C的函数 且C只能取整数解 故不能用微分法求C 而只能用边际分析法 MarginalAnalysis 3排队模型 排队模型的优化 76 PPT学习交流 2020 4 16 因为z c 是最小值 则有 将z期望费用公式代入 合并化简得 依次求C 1 2 3 的L值 即可找出符合上式的C 77 PPT学习交流 2020 4 16 例6 某检验中心 为各用户检验产品 用户每天到达按泊松流 48个 天 每个用户每天停工损失6元 服务时间服从负指数分布 25个 天 每设1个检验台每天服务成本4元 其他条件为标准M M C模型 问设几个服务台费用最少 解 4元Cw 6 48 25 下面再分别计算当服务台C 1 2 3 时Ls值 计算过程如下 78 PPT学习交流 2020 4 16 计算L C L C 1 及L C 1 L C c 1 c 218 930 相当于无穷 c 30 61218 930c 40 1160 612 见陆书239页队长表达式 79 PPT学习交流 2020 4 16 系统容量有限的模型 系统容量为N 系统中排队等待的顾客数最多为N 1 所以在某一时刻某位顾客到达时 如果系统中已有N位顾客 那么这位顾客被拒绝进入系统 如图2 2 由状态转移图 可以建立系统概率平衡方程如下 4排队模型 推广 80 PPT学习交流 2020 4 16 系统容量有限的模型 模型的各数量指标参数如下 1 系统里没有顾客的概率 4排队模型 推广 81 PPT学习交流 2020 4 16 系统容量有限的模型 2 系统里有n个顾客的概率 3 在系统里的平均顾客数 4 平均排队的顾客数 4排队模型 推广 82 PPT学习交流 2020 4 16 顾客源有限的模型 由状态转移图 可以建立系统概率平衡方程如下 以机器维修问题为例 设有m台机器 顾客总体 每台机器单位时间内发生故障的概率相同 顾客平均到达率 等待修理及正在修理的机器数为n 工人数为1 单服务台 则对系统的有效到达率为 4排队模型 推广 83 PP