第六章-排队论详解.ppt

数学建模简明教程 国家精品课程 第六章排队论 一 问题引入与分析 二 排队论的基本概念 三 几类排队论模型 四 模型的建立与求解 1 2001年全国数学竞赛的B题 公交车调度 某条公交线路上行方向共14站 下行方向共 13站 公交公司配给该线路同一型号的大客车 每 辆标准载客100人 据统计客车在该线路上运行的 平均速度为20公里 小时 运营调度要求 乘客候车 时间一般不要超过10分钟 早高峰一般不要超过 是这样的 一 问题引入与分析 5分钟 车辆满载率不应超过120 一般也不要 低于50 试根据这些材料和要求 为该线路设计一个 便于操作的全天 工作日 的公交车调度方案 包括两个起点站的发车时刻表 一共需要多少 辆车 这个方案以怎样的程度照顾到了乘客和 公交公司双方的利益 等等 2 问题分析 对于第一个问题 关于公交车的调度方案 可以利用各种的不同的方法 比如多目标规划 去求得在一定原则下的最优方案 得到一个满足 实际情况的分配方案 但要建立具体的明确 完 整的数学模型 以及求解模型的方法 如何采集 运营数据是关键的 在实际中 公交车具有随机 性 特别是顾客的到来是随机的 是无法精确预 测的 这就决定了公交车的数量并不是完全确定 的固定不变的 而是随着不同时段顾客的多少而 变化 因此顾客和公交车之间存在随机因素 很明显 顾客和公交车是一个服务和被服务 的关系 如果公交车数量过多 也就是已有的资 源大于需求 虽然公交车的数量能够满足顾客 需求 减少了顾客排队等待的时间 公交车提供 的服务使顾客的满意度很高 却会造成公交车公 司的浪费 比如某一时段某一线路所发公交车上没 有顾客或很少的顾客 个别时段个别线路如此 公 交车公司也许可以接受 但长时间的空跑或入不敷 出 最终会使公交车公司不堪重负 甚至倒闭 另 一方面 如果公交车数量较少 很多顾客得不到服 务 或者很多顾客花了很长的时间去排队等候 造 成顾客的不满意度提高 这样公交车公司会失去顾客 如何考虑随机因素 设计合理方案 建立数学模 型 一方面提供服务的服务机构即公交公司的线 路设计合理 能够赢得顾客 获得利益 另一方 面被服务的顾客能够在被服务的过程中 排队等 候的时间最短 这都是上述问题要解决的 也是 排队论的主要研究内容 二 排队论的基本知识 2 排队系统描述 3 基本组成部分 4 数量指标 5 排队模型的记号 1 背景介绍 1 背景介绍 排队论是研究排队现象的理论和应用的学科 是 专门研究由于随机因素影响而产生的拥挤现象的科学 20世纪初丹麦数学家 电气工程师爱尔朗把概率论应 用于电话通话问题 从而开创了这门应用数学科学 20世纪30年代中期 费勒引进了生灭过程 排队论 才被数学界承认为一门重要的学科 20世纪40年代排 对论在运筹学这个新领域中成了一个重要的部分 20 世纪50年代初肯德尔对排对论作了系统的研究 他用 马尔科夫链方法研究排队论 使排队论得到进一步发 展 20世纪60年代起排队论研究的课题日趋复杂 很 多问题很难求得精确解 因此开始了近似方法的研究 排队论应用范围很广 它适用于一切服务系统 尤 其在通信系统 交通系统 计算机存储系统和生产管理 系统等方面应用的最多 排队是日常生活和工作中常见的现象 例如等公共 汽车排队 到商店购物排队 交款排队 到医院看病 等待排队 买火车票排队 托运行李排队 取货排队 这是人的排队 还有另一种排队 例如文件等待打印或 发送 报告等首长批示 路口红红灯下的汽车 自行车 等待通过路口 这是物或设备排队 总之 凡是具有公共服务性质的事业和工作 凡 是出现拥挤现象的领域 都是排队论的用武之地 2 排队系统描述 排队系统又称为随机服务系统 是研究服务 请求服务的人或者物 顾客 排队系统的共同特征 顾客到达系统的时刻是随机的 为每一位顾客 有为顾客服务的人或者物 即服务员或服务台 过程和拥挤现象的随机模型 提供服务的时间是随机的 因而整个排队系统 的状态也是随机的 排队系统的几种形式 基本排队过程 从图6 6可知 每个顾客由顾客源按一定方式 到达服务系统 首先加入队列排队等待接受服务 然后服务台按一定规则从队列中选择顾客进行服 务 获得服务的顾客立即离开 排队论所要研究解决的问题 面对拥挤现象 人们通常的做法是增加服务设施 但是增加的数量越多 人力 物力的支出就越大 甚 至会出现空闲浪费 如果服务设施太少 顾客排队等 待的时间就会很长 这样对顾客会带来不良影响 如 何做到既保证一定的服务质量指标 又使服务设施费 用经济合理 恰当地解决顾客排队时间与服务设施费 用大小这对矛盾 就是随机服务系统理论 排队论 所要研究解决的问题 3 排队系统的基本组成部分 排队系统是由输入过程 排对规则和服务机构组成 1 输入过程指要求服务的顾客是按怎样的规律 i 顾客总体数 又称顾客源 输入源 这是指顾客 ii 顾客到达方式 这是描述顾客是怎样来到系统 到达排队系统的过程 有时也把它称为顾客流 一 般可以从3个方面来描述 个输入过程 的来源 顾客源可以是有限的 也可以是无限的 的 是单个到达 还是成批到达 iii 顾客流的概率分布 或称相继顾客到达的时间 2 排对规则指服务台从队列中选取顾客进行 i 损失制指如果顾客到达排队系统时 所有 间隔的分布 这是求解排队系统有关运行指标问题 时 首先需要确定的指标 顾客流的概率分布一般 有定长分布 二项分布 泊松流 最简单流 爱尔 朗分布等若干种 服务的顺序 一般可以分为损失制 等待制和混 合制等3大类 服务台都被先到的顾客占用 那么他们就自动 离开系统永不再来 ii 等待制指当顾客来到系统时 所有服务台 a 先到先服务按顾客到达的先后顺序对顾客 b 先到后服务 c 随机服务即当服务台空闲时 不按照排队 d 优先权服务 都不空 顾客加入排队行列等待服务 等待制中 服务台在选择顾客进行服务时常有如下四种规则 进行服务 序列而随意指定某个顾客接受服务 iii 混合制这是等待制与损失制相结合的一种服 a 队长有限 当排队等待服务的顾客人数超 b 等待时间有限 即顾客在系统中的等待时 c 逗留时间 等待时间与服务时间之和 有限 务规则 一般是指允许排队 但又不允许队列无限 长下去 具体说来 大致有三种 过规定数量时 后来的顾客就自动离去 另 求服务 即系统的等待空间是有限的 间不超过某一给定的长度T 当等待时间超 过T时 顾客将自动离去 并不再回来 3 服务机构 i 服务台数量及构成形式 从数量上说 服务台有单 ii 服务方式 这是指在某一时刻接受服务的顾客数 iii 服务时间的分布 在多数情况下 对每一个顾客的 服务台和多服务台之分 从构成形式上看 服务台有 单队一 单服务台式 单队一 多服务台并联 式 多队一 多服务台并联式 单队一 多服 务台串联式 单队一 多服务台并串联混合式 以及多队多服务台并串联混合式等等 它有单个服务和成批服务两种 服务时间是一随机变量 4 排队系统的主要数量指标 排队论主要研究系统的性态 即与排队有关 1 排队系统主要数量指标 等待时间 忙期 队长 的数量指标的概率规律性 系统的优化问题 统 计推断 根据资料合理建立模型 目的是正确设 计和有效运行各个服务系统 使之发挥最佳效益 所以必须确定判断系统运行优劣的基本数量指标 i 等待时间从顾客到达时刻起到他开始接受服务止这 ii 忙期忙期是指从顾客到达空闲着的服务机构起 到 iii 队长队长是指系统中的顾客数 排队等待的顾客数与 段时间称为等待时间 等待时间是个随机变量 从顾客 到达时刻起到他接受服务完成止这段时间称为逗留时 间 也是随机变量 服务机构再次成为空闲止的这段时间 即服务机构连续忙 的时间 这是个随机变量 是服务员最为关心的指标 因 为它关系到服务员的服务强度 与忙期相对的是闲期 即 服务机构连续保持空闲的时间 在排队系统中 忙期和闲 期总是交替出现的 正在接受服务的顾客数之和 排队长是指系统中正在排队 等待服务的顾客数 队长和排队长一般都是随机变量 2 数量指标的常用记号 i 主要数量指标 W 平均逗留时间 即 在任意时刻 进入 所有顾客数的期望值 等待服务的顾客数的期望值 稳态系统的顾客逗留时间的期望值 稳态系统的顾客等待时间的期望值 L 平均队长 即稳态系统任一时刻的 平均等待时间 即 在任意时刻 进入 平均等待队长 即稳态系统任一时刻 ii 其它常用数量指标 s 系统中并联服务台的数目 N 稳态系统任一时刻的状态 即系统中 U 任一顾客在稳态系统中的逗留时间 Q 任一顾客在稳态系统中的等待时间 所有顾客数 平均到达率 平均到达间隔 平均服务率 平均服务时间 有服务台全部空闲的概率 繁忙程度的重要尺度 服务强度 即每个服务台单位时间内的平 均服务时间 一般有 这是衡量排队系统 稳态系统任意时刻状态为n的概率 5 排队系统的描述符号 描述符号 X Y Z A B C X 顾客相继到达的间隔时间的分布 常用下 M 表示到达的过程为泊松过程或负指数分布 D 表示定长输入 G 表示一般相互独立的随机分布 Y 服务时间的分布 所用符号与表示顾客 列符号 到达间隔时间分布相同 表示K阶爱尔朗分布 Z 服务台个数 1 表示单个服务台 s s 1 A 系统容量限制 默认为 如系统有K个等待位子 则 B 顾客源数目 默认为 分有限与无限两种 表 C 服务规则 常用下列符号 FCFS 表示先到先服务的排队规则 LCFS 表示后到先服务的排队规则 PR 表示优先权服务的排队规则 表示多个服务台 0 K 当K 0时 说明系统不允许等待 即为损失制 K 时为等待制系统 此时一般 省略不写 K为有限整数 时 表示为混合制系统 示顾客源无限 一般 也可省略不写 例如 某排队问题为M M S FCFS 则 某些情况下 排队问题仅用上述表达形式 如不特别说明则均理解为系统等待空间容量 表示顾客到达间隔时间为负指数分布 泊松流 服务时间为负指数分布 有s s 1 个服务台 系 统等待空间容量无限 等待制 顾客源无限 采 用先到先服务规则 中的前3个符号 例如 某排队问题为M M S 无限 顾客源无限 先到先服务 单个服务的等 待制系统 三 几类排队论模型 1 M M S模型 2 GI M n模型 1 M M s排队模型 M M s排队模型是指s个服务员的排队系统 顾客到来间隔时间是独立同分布的 服务时间也是独立同分布的 并且独立于输入过程 排队规则是等待制 含假定 顾客到来间隔时间服从参数为的指数分布 服务时间服从参数为的负指数分布 且有隐 按排队论的基本构成特征 来求解该排队模型 1 基本构成 i 顾客到达规律 的主要数量指标 平均到达率 表示在时间到达的顾客数 称为排队系统的输入过程 其平均值为 即单位时间内到达的顾客数为 并称为 它服从参数为的泊松分布 即 ii 服务时间 服务率 表示顾客到达间隔时间序列 其 中表示第n个顾客的到来时刻 可以证明 服从参数为的泊松分布的充 负指数分布 要条件是到达间隔时间序列独立同分布且服从 记Z为服务时间 Z服从参数为的负指数分布 则 即为每个顾客平均服务时间为 从 而单位时间内被服务的顾客的平均数为 称为平均 iii 排队规则 按顾客的到达的先后顺序服务 即先到先服务 满足以上三个条件的模型在排队论中记为模型 2 数量特征 只讨论s 1情形 i 平均队长 稳态下系统内等待服务的顾客数 其数学期 望称为平均等待队长 即 M M s模型 其中s为服务员的个数 ii 平均逗留时间和平均等待时间 平均逗留时间为 平均等待时间为 则公式 称为Little公式 3 M M s排队模型 i 当s 2时服务强度 平均队长 平均等待时间 ii 当s是任意的 服务强度 平均队长 平均等待时间 例1 某医院急诊室同时只能诊治一个病人 诊治时间 服从指数分布 每个病人平均需要15分钟 病人按泊 松分布到达 平均每小时到达3人 试对此排队系统 进行分析 解 对此排队系统分析如下 先确定参数值 这是单服务系统有 3人 h 60 15人 h 4人 h 故服务强度为 计算稳态概率 这就是急诊室空闲的概率 也是病人不必等待立 即就能就诊的概率 而病人需要等待的概率则为 这也是急诊室繁忙的概率 计算系统主要工作指标 急诊室内外的病人平均数 急诊室外排队等待的病人平均数 病人在急诊室内外平均逗留时间 病人平均等候时间 为使病人平均逗留时间不超过半小时 那么平均 15 12 3min 即平均服务时间至少应减少3min 服务时间应减少多少 由于 平均服务时间为 若医院希望候诊的病人90 以上都能有座位 则 候诊室至少应安置多少座位 设应该安置 个座位 加上急诊室的一个座位 共有 1个 要使90 以上的候诊病人有座位 相当于使 来诊的病人数不多于 1个 的概率 不少于90 即 上式两边取对数 即候诊室至少应安置6个座位 所以 例2承接例1 假设医院增强急诊室的服务能力 使 其同时能诊治两个病人 且平均服务率相同 试分析 该系统工作情况 并且 例1 例2的结果进行比较 解这相当于增加了一个服务台 故有 病人必须等候的概率 即系统状态N 2的概率 表6 1两个系统的比较 2 GI M n排队模型 满足下述三个条件的随机服务系统称为GI M n排队模型 1 GI M s系统的构成 b 服务系统由n个并联的服务台所组成 c 各顾客的服务时间之间是相互独立同分布的 服 是相互独立同分布的随机变量 务时间与到达间隔时间相互独立 且服务时间的分 a 顾客到达时刻的间隔 布服从参数为的负指数分布 2 数量特征 存在且与初始条件无关 其表达式为 i 队长 定理6 1设为第m个乘客到达时系统的队长 当 时 队长的分布极限 a 该系统的平稳分布下的平均队长为 b 系统的平均队长为 c 系统服务台平均占有数 其中 ii 等待时间 存在且与初始条件无关 其表达式为 令第m个顾客的等待时间为 其分布为 定理6 2对GI M n系统 当时 队长的分布极限 其中都与定理 6 1 中的一致 定理6 3在GI M n系统中 设各顾客服务的时间相互独 在平衡状态下 顾客到达是不需要等待的概率为 平均等待时间为 等待的时间内 每台服务设施的输出过程 即服务完成 离开服务机构的顾客 是一个以为强度的泊松过程 立且具有公共的以为参数