泊松分布与生灭过程.ppt

1 第二节顾客到达分布 2 系统的组成 顾客 服务机构 顾客到达有先后 服务时间有长短 存在随机性 3 要想预测在某一时刻将有多少顾客要求服务系统服务 或者预测某一顾客的服务时间将要延误多久这都是不可能的对单位时间内到达系统的顾客数和服务时间这两个随机变量进行概率的描述描述顾客到达和服务时间的方法 要求出单位时间内有K个顾客到达系统要求服务的概率 以及服务时间不少于某一时间长度的概率 4 最简单流 泊松流 流的平稳性对于任意的t 0及 t 0 在时间区间 t t t 内有n个顾客到达的概率只与 t有关 与时间区间的起点t无关 当 t充分小时 在 t t t 内有一个顾客到达的概率与 t成正比 即其中 O t 是当 t 0时 关于 t高阶无穷小 为单位时间内的顾客到达平均数 5 流的无后效性在时间轴上 互不相交的时间区段和内 顾客的到达数是相互独立的 即前一顾客的到达不影响后一顾客的到达 6 流的普遍性在同一时刻 有两个及两个以上顾客到达的概率与有一个顾客到达的概率相比小到可以忽略的程度 即当 t充分小时 在时间区间 t t t 内有2个及2个以上顾客到达的概率是关于的高阶无穷小 7 流的平稳性 流的普遍性 在区间 t t t 内没有顾客到达的概率 8 在长为 t t t 的时间区间内 到达n个顾客的概率 设把长为 t的时间区间分成m等分 每段长度为 若在dt内 有一个顾客到达 则称被 占着 如果在dt内 没有顾客到达 则称为 空着 被 占着 的概率近似为被 空着 的概率近似 根据流的无后效性 在m个dt中 有顾客到达与没有顾客到达可以看成是m次独立的试验 9 在长为 t t t 的时间区间内 到达n个顾客的概率 在m个dt中 有n个dt被顾客 占着 的概率 利用二项定律 10 dt 0 m 11 符合最简单流 泊松流 的随机事件发生规律称为泊松分布 单位时间发生n个随机时间的概率 参数1个 顾客的平均到达率 思考 交叉口交通流量 排队车辆 12 泊松分布的另外一种表达方式 负指数分布 若n 0 在 t的时间段内没有顾客达到的概率 前后两次随机事件发生的时间间隔大于 t 13 负指数分布 泊松分布 在单位时间 t内 发生n次随机事件的概率 随机事件发生时间间隔大于单位时间 t的概率 随机事件发生时间间隔小于单位时间 t的概率 参数1个 顾客的平均到达率 14 如果顾客的到达过程服从最简单流 则顾客单位时间内的到达数服从泊松分布 如果顾客的到达过程服从最简单流 则顾客到达的时间间隔服从负指数分布 从本质上看 泊松分布与负指数分布是同一个过程的不同表现形式 15 第三节生灭过程 16 研究系统内部状态变化的过程 系统状态i 状态i 1 状态i 1 在 t时刻内发生两个或两个以上事件的概率为O t 一个事件 一个事件 一 生灭过程定义 t 0 O t 0 如在 t 0内 交叉口一条车道到达两辆车的概率为O t 0 17 系统具有0 1 2 个状态 在任何时刻 若系统处于状态i 并且系统状态随时间变化的过程满足以下条件 称为一个生灭过程 1 在 t t t 内系统由状态i转移到状态i 1的概率为 i t O t 平稳性条件 t内有一个顾客到达的概率 2 在 t t t 内系统由状态i转移到状态i 1的概率为 i t O t 平稳性条件 t内有一个顾客离开的概率 18 3 在 t t t 内系统发生两次以上转移的概率为O t 即有2个以上顾客到达或离开的概率为 普遍性条件 只要排队系统的输入过程和服务过程符合泊松分布 排队过程符合生灭过程 19 二 生灭过程状态转移图 状态 顾客到达率 系统服务率 t 时 Pi t 趋向于常数 系统达到稳定 20 系统达到稳定后 每个状态转入率的期望值与转出率的期望值相等 对于状态i 转出率的期望值为 转入率的期望值为 P0 P1 P2 Pi 21 有 对于S0 转入 转出 转出 转入 对于Sk P0 P1 P2 Pi 22 状态转移方程 求解该方程 可以获得各状态对应的概率 23 对于S0 对于S1 依次类推 且有 24 例 某排队系统 M M 1 3 FCFS 2 3 求解各状态对应的概率 首先 做出相应的状态转移图 对于S0 对于S1 对于S2 25 生灭过程求解排队系统各状态概率过程 建立状态转移图 建立状态转移方程 求解状态转移方程 各状态转入率期望值与转出率期望值相等 各状态概率 26 作业 利用生灭过程求解以下排队系统各状态的概率 S0 S1 S2 S3 2 2 3 2 4 3 27 第三节M M 1排队系统 顾客到达服从泊松分布 顾客到达率为 服务过程服从泊松分布 负指数分布 系统服务率为 单通道 先到先服务 最简单的M M 1排队系统 M M 1 M M 1 m 28 M M 1 排队系统 系统容量无限 顾客源无限 最基本的排队系统 排队过程为生灭过程过程 29 列状态转移方程组求各状态概率 30 M M 1 排队系统各状态概率归结为无穷等比数列求和 1 数列收敛 P0 1 1 数列发散 系统稳定 系统不稳定 称 为服务强度 若服务强度大于1 说明单位时间内到达的顾客数比完成服务的顾客数多 系统中排队长度越来越大 产生阻塞 31 利用排队系统各状态概率计算运行指标 1 队长 系统中的顾客数量 队长 32 2 排队长 系统中等待的顾客数量 通道数 33 3 逗留时间 顾客在排队系统中的总时间 李太勒公式 前后2名顾客到达系统的时间间隔 34 4 排队时间 顾客在排队系统中的等待时间 李太勒公式 前后2名顾客到达系统的时间间隔 35 M M 1 m 排队系统 系统容量有限 顾客源无限 36 列状态转移方程组求各状态概率 37 并不要求 1 特别地 当 1时 P0 1 m 1 1 38 利用排队系统各状态概率计算运行指标 1 队长 系统中的顾客数量 队长 39 2 排队长 系统中等待的顾客数量 通道数 40 3 逗留时间 顾客在排队系统中的总时间 李太勒公式 前后2名顾客到达系统的时间间隔 41 有效到达率 e 当排队长度未满容量时 平均到达率为 当排队容量已满容量时 平均到达率为0 42 逗留时间 43 4 排队时间 顾客在排队系统中的等待时间 李太勒公式 前后2名顾客到达系统的时间间隔 44 作业 汽车通过一检查站时进行验证 汽车按泊松分布到达检查站 平均间隔0 6分钟 验证时间平均为15秒 验证时间服从负指数分布 请分析该排队系统 求该排队系统各状态对应的概率 以及队长 排队长 顾客逗留时间 顾客等待时间等运行指标 45 顾客的到达是服务参数 的泊松分布 顾客的服务时间是服从参数为 的负指数分布 有S个服务台 顾客按到达的先后次序接受服务 第四节M M S排队系统 46 当顾客到达时 若有空闲的服务台就立即接受服务 若所有的服务台都忙着 则顾客排成一个队列等待服务 47 常见的M M S 及M M S m 两类 48 M M S 排队系统 标准M M S系统 49 系统中个服务台的服务率均为 于是整个服务机构的最大服务率为S 与M M 1 系统类似 只有当时 才能使服务系统达到稳态而不排成无限的队列 系统的服务强度 50 当系统中只有一个顾客时 则有S 1个服务台空闲着 仅一个服务台在服务 这时的服务率为 当系统有2个顾客时 就有2个服务台工作 其服务率为2 当系统中有S个顾客时 则服务率达到最大值S 当系统中的顾客数超过S时 由于个服务台都忙着 其余顾客必须排队 这时的服务率仍为S 51 M M 1系统 M M S系统 52 M M S系统 53 根据正则条件 54 利用排队系统各状态概率计算运行指标 1 排队长 55 2 平均等候时间 56 3 逗留时间 平均顾客数 57 系统容量受限制 顾客源无限 先到先服务的M M S系统 该系统共有m S个位置可供顾客排队 当顾客到达时 若系统饱和 即服务台都忙着 排队位置已排满 则后到的顾客立即离去 另求服务 因此 该系统中只可能有m 1个状态 M M S m 排队系统 58 与M M S 系统的推导类似 可得M M S m 系统的状态指标及运行指标 59 第五节排队服务系统的最优化问题 排队系统设计最优化的目标在于使系统设施达到最大使用效益 或者说 在一定的质量指标下要求服务机构最为经济一般要求系统最优 60 对于顾客来说 总是要求提高服务水平 如增设服务台数 加快服务时间 以减少排队费用 若要完全满足顾客的要求 则会导致服务机构过大 使用效率降低 造成浪费 从服务机构来说 总是希望服务机构能达到最高的使用效率 每个服务