第十章 排队论.ppt

排队论 排队论 引言 生灭过程和Poisson过程 M/M/s等待制排队模型 负指数分布 关于顾客在系统中的逗留时间T,可说明它服从 的负指数分布 ,即有 小结 ρ = λ/ μ n=0,1,2 举例 某修理店只有一个修理工，来修理的顾客到达过程为Poisson流，平均4人/h; 修理时间服从负指数分布，平均需要6min。 试求： （1）修理店空闲的概率 （2）店内恰有3个顾客的概率 （3）店内至少有1个顾客的概率 （4）在店内的平均顾客数 （5）每位顾客在店内的平均逗留时间 （6）等待服务的平均顾客数 （7）每位顾客平均等待服务时间 （8）顾客在店内等待时间超过10min的概率 3、其他相关指标 (1)忙期服务量：指一个忙期内系统平均完成 服务的顾客数； (2)损失率: 指顾客到达排队系统，未接受服务 而离去的概率; （对损失制或系统容量有限而言） (3)服务强度：? = ?/s? ； 根据前面的约定，我们将主要分析系统的平稳分布。于是记： Pn ：当系统达到统计平衡时处于状态n的概率（pn(t)） λn :当系统处于状态n时，新来顾客的平均到达率(单位 时间内来到系统的平均顾客数) μn：当系统处于状态n时，整个系统的平均服务率。 （单位时间内可以服务完的顾客数） 当λn为常数时，记为λ；当每个服务台的平均服务率为常数时，记每个服务台的服务率为μ。 S表示系统中并行的服务台数 则当n≥s时，有μn＝s μ,于是令? = ?/s? ， 称?为服务强度 （traffic intensity） 密度函数 均值 方差 随机变量 T 分布函数 ? fT(t) t ? fT(t) ?t ?t t fT(t) 是一个严格下降函数 第二节 生灭过程和Poisson过程 一、生灭过程简介 一类非常重要其广泛存在的排队系统是生灭过程排队系统。 生灭过程是一类特殊的随机过程，在生物学、物理学、运筹学中有广泛的应用。 定义1 设{N(t)，t≥0 }为一个随机过程。 如N(t)的概率分布具有以下性质： （1）假设N(t)= n，则从时刻 t 起到下一个顾客到达时刻止的时 间服从参数为λn 的负指数分布，n=0，1，2，…。 （2）假设N(t)= n，则从时刻 t 起到下一个顾客离去时刻止的时间服从参数为μn的负指数分布，n=0，1，2，…。 （3）同一时刻只有一个顾客到达或离去。 则称设{N(t)， t≥0 }为一个生灭过程。 顾客到达——“生”； 顾客离开——“灭” 顾客到达 顾客离去 ?n ， ?n ， 生灭过程示意图： 为求平稳分布，考虑系统在 t+Δt 时刻可能处的任一状态n的概率。 状态转移图 一般说来，得到 是比较困难的，因此通常是求当系统达到平稳状态后的状态分布，记为 , n=0,1,2 (λnΔt) (μnΔt) 到达一个，离去一个 Pn(t) n 4 (1-λn+1Δt) μn+1Δt 无到达，离去一个 Pn+1(t) n +1 3 λn-1Δt (1-μn-1Δt) 到达一个，无离去 Pn-1(t) n -1 2 （1-λnΔt） (1-μnΔt) 无到达，无离去 Pn(t) n 1 发生的概率 （t,t+Δt）内发生的事件 概率 T时刻状态 方式 各种方式发生概率表 方式1，2，3，4互不相容且完备，于是： Δt2项都变为零 对上式求导有： 当n=0时，只有方式1和3，4发生，且方式1中无离去的概率为1，则: 我们假设系统是稳态的，即与时刻无关，于是可得： n=1,2,3…. 继续迭代： 记 则平稳状态的分布为： 如何求P0? 由概率分布的要求： 有： 于是： 小结 系统达到平稳状态后的状态分布---Pn 举例 某小型超市有一个收款台。交款顾客以每小时30人的负指数分布到达。当收款台前只有一名顾客时，有一名收款员单独服务，收款时间为平均1.5min的负指数分布；当有2名或以上顾客时，将增加一名助手共同为顾客服务，收款时间将缩短至平均1min的负指数分布。 求 收款台前有n 名顾客的概率Pn 解： n=1,2….. 则有 由级数可知： 当|q| 1时， 其和为 由 可知： 二、Poission过程和负指数分布 Poission过程（又称为P