运筹学——7.约束极值问题.ppt

1 第十二章排队论 2 一 排队系统的一般表示 例1各个顾客由顾客源出发 到达服务机构前排队等候服务 服务完了后就离开 排队结构指队列的数目和排列方式 排队规则和服务规则是说明顾客在排队系统中按怎样的规则 次序接受服务的 排队规则 排队系统 第一节基本概念 3 现实生活中的排队系统 4 二 排队系统的组成和特征 输入即指顾客到达排队系统 可能有以下不同情况 1 输入过程 5 2 排队规则 顾客在排队系统中按怎样的规则 次序接受服务的 1 顾客到达时 所有服务台被占用 6 3 服务机构 2 多服务台时 单队 单服务台 多队 多服务台 并列 单队 多服务台 并列 7 5 服务时间的分布我们总假定是平稳的 即分布的期望值 方差等参数都不受时间的影响 多服务台 串列 多服务台混合 8 三 排队模型的分类 1 1953年 D G Kendall提出第一种分类方法 X Y Z X处填写表示相继到达间隔时间的分布 Y处填写表示服务时间的分布 Z处填写并列的服务台的数目 表示相继到达间隔时间和服务时间的各种分布的符号 M 负指数分布 D 确定型 Ek k阶爱尔朗分布 GI 一般相互独立的时间间隔的分布 G 一般服务时间的分布 9 2 1971年关于排队论符号的标准化会议上决定 将Kendall符号扩展成为 X Y Z A B C 前三项意义不变 而 A处填写系统容量限制N B处填写顾客源数m C处填写服务规则 约定 10 四 排队系统的参数 1 队长 Ls 指在系统中的顾客数 2 排队长 Lq 指系统中排队等候服务的顾客数 3 逗留时间 Ws 指一个顾客在系统中的停留时间 4 等待时间 Wq 指一个顾客在系统中排队等待的时间 Ls Lq 正被服务的顾客数 Ws Wq 服务时间 5 忙期 指从顾客到达空闲服务机构起到服务机构再次空闲止这段时间长度 即服务机构连续繁忙的时间长度 6 系统的状态概率 Pn t 指系统中的顾客数为n的概率 7 稳定状态 limPn t Pn 11 一 经验分布 例2某服务机构单服务台 先到先服务 对41顾客记录到达时刻 和服务时间s 单位 分钟 如下表 表中第1号顾客到达时刻为0 全部服务时间为127 分钟 第二节时间分布 12 13 到达间隔分布表 服务时间分布表 平均间隔时间 142 40 3 55 分钟 人 平均到达率 41 142 0 28 人 分钟 平均服务率 41 127 0 32 人 分钟 平均服务时间 127 41 3 12 分钟 人 14 二 Passion分布 设N t 表示在时间 0 t 内到达顾客数 令Pn t1 t2 表示在时间区间 t1 t2 t2 t1 内有n 0 个顾客到达的概率 即 Pn t1 t2 P N t2 N t1 n t2 t1 n 0 Passion分布的三条件 1 无后效性 不相重叠的时间区间内顾客到达数相互独立 15 Pn t t Pn t 1 t o t Pn 1 t t o t 在上述条件下 研究顾客到达数n的概率分布 16 Pn t t Pn t 1 t Pn 1 t t o t Pn t t Pn t t Pn t Pn 1 t o t t 令 t 0 P0 t e t Pn t t ne t n t 0 n 0 1 2 17 三 负指数分布 18 一 M M 1模型 1 假设 第三节单服务台负指数分布排队系统的分析 19 2 Pn的计算 O表示发生 1个 表示没有发生 Pn t t Pn t 1 t 1 t Pn 1 t 1 t t Pn 1 t t 1 t Pn t t t 20 整理得 Pn t t Pn t 1 t t Pn 1 t t Pn 1 t t o t Pn t t Pn t t Pn 1 t Pn 1 t Pn t 1 t 0 dPn t dt Pn 1 t Pn 1 t Pn t 考虑P0 t 的情况 P0 t t P0 t 1 t P1 t 1 t t t 0 dP0 t dt P0 t P1 t 2 由dPn t dt 0得到 21 由式 3 得 通过求解可得 单位时间内到达的平均顾客数 单位时间内服务的平均顾客数 服务强度 参数意义 22 3 M M 1参数计算 1 系统中平均顾客数 Ls 记 23 2 队列中等待的平均顾客数 Lq 3 顾客逗留时间 Ws 4 队列中顾客等待时间 Wq 24 它们的相互关系如下 25 例3100个工作小时内每小时来就诊的病人数n出现次数如下 100个完成手术的病例所用时间v 小时 出现的次数如下 26 解 27 假定系统最大容量为N 单服务台情形排队等待的顾客最多为N 1 下面只考虑稳态情形 二 M M 1 N 模型 解得 28 根据上式我们可以推导出系统的各项指标 有效到达率 e 1 PN 可以验证 1 P0 e 4 顾客等待时间 3 顾客逗留时间 1 队长 2 队列长 29 例4单人理发馆有六个椅子接待客人 当6个椅子都坐满时 后来的顾客不进店就离开 顾客平均到达率为3人 小时 理发需时平均15分钟 则 N 7为系统中最大的顾客数 3人 小时 4人 小时 1 求某顾客一到达就能理发的概率 2 求需要等待的顾客数的期望值 30 3 求有效到达率 4 求一顾客在理发馆内逗留的时间 5 在可能到达的顾客中有百分之几不等待就离开 人 小时 31 机器故障问题 设共有m台机器 机器故障停机表示到达 待修机器形成队列 修理工是服务员 顾客总体虽然只有m个 但每个顾客服务后仍回到总体 仍然可以到来 三 顾客源为有限的情形 M M 1 m 32 根据上式我们可以推导出系统的各项指标 在机器故障问题中Ls就是平均故障台数 而 33 例5某车间有5台机器 每台机器的连续运转时间服从负指数分布 平均连续运转时间15分钟 有一个修理工 每次修理时间服从负指数分布 平均每次12分钟 求 1 修理工空闲的概率 2 五台机器都出故障的概率 3 出故障的平均台数 4 等待修理的台数 5 平均停工时间 6 平均等待时间 7 评价这些结果 34 解 7 机器停工时间过长 修理工几乎没有空闲时间 应当提高服务率减少修理时间或增加修理工人 35 一 M M c 第四节多服务台指数分布排队系统的分析 36 用递推法解上述差分方程 可求得状态概率 根据上式我们可以推导出系统的各项指标 37 例6某售票所有三个窗口 顾客到达服从Passion过程 平均到达率每分钟 0 9 人 服务 售票 时间服从负指数分布 平均服务率每分钟 0 4 人 0 9 38 代入公式得 1 整个售票所空闲的概率 2 平均队长 3 平均等待时间和逗留时间 4 顾客到达后必须等待 即系统中顾客数已有3人 的概率 39 M M c型系统和c个M M 1系统的比较 上例中 排队方式不变 但顾客到达后在每个窗口前各排一队 且进入队列后坚持不换 这就形成3个队列 如下图二每个队列平均到达率为 0 9 3 0 3 每分钟 这样原来的系统就变成3个M M 1型的子系统 40 现按M M 1型解决这个问题 并与上表比较 从表中各指标的对比可以看出单队比三队有显著的优越性 41 系统的状态概率和运行指标如下 二 M M c N 42 三 M M c m 2 平均故障台数 有效到达率 43 1 等待修理的机器平均数 2 需要修理的机器平均数 3 有效损坏数 4 等待修理时间 5 停工时间 例7设有两个修理工人 负责5台机器的正常运行 每台机器平均损坏的概率为每运转一小时1次 两个工人能以相同的平均修复率4 次 小时 修好机器 求 44 1 Lq P3 2P4 3P5 0 118 3 e 1 5 1 094 3 906 4 Wq 0 118 3 906 0 03小时 5 Ws 1 094 3 906 0 28小时 45 服务时间是任意分布的情形 一 M G 1 服务时间T的分布是一般的其它的条件和标准的M M 1型相同 为了达到稳态 1这一条件是必要的 其中 E T 第五节一般服务时间M G 1模型 46 例8有一售票口 已知顾客按平均为2分30秒的时间间隔的负指数分布到达 顾客在售票口前服务时间平均为2分钟 1 若服务时间也服从负指数分布 求顾客为购票所需的平均逗留时间和等待时间 2 若经过调查 顾客在售票口前至少要占用1分钟 且认为服从服务时间服从负指数分布是不恰当的 而应服从以下概率密度分布 47 2 令y为服务时间 那么Y 1 X X服从均值为1的负指数分布 于是 48 二 M D 1 服务时间是确定的常数 例如在一条装配线上完成一件工作的时间应是常数 自动的汽车的冲洗台 冲洗一台汽车的时间也是常数 这时 例9某实验室有一台自动检验机器性能的仪器 要求检验机器的顾客按Passion分布到达 每小时平均4个顾客 检验每台机器所需时间为6分钟 求 1 在检验室内机器台数Ls 期望值 2 等候检验的机器台数Lq 3 每台机器在室内消耗 逗留 时间Ws 4 每台机器平均等待检验的时间Wq 49 注 在一般服务时间分布的Lq和Wq中以定长服务时间的为最小 这符合我们通常的理解 服务时间越有规律 等候的时间就越短 50 三 M Ek 1模型 51 对于M Ek 1模型 除服务时间外 其它条件与标准的M M 1型相同 52 例10某单人裁缝店做西服 每套需经过4个不同的工序 4个工序完成后才开始另一套 每一套工序的时间服从负指数分布 期望值为2小时 顾客到来服从Passion分布 平均订货率为5 5套 周 设一周6天 每天8小时 以顾客为等到做好一套西服期望时间有多少 解顾客到达 5 5套 周 设 为平均服务率 单位时间完成的套数 1 为平