运筹学-第十章-排队论定稿资料.ppt

定义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 ，... 方式 T时刻状态 概率 （t,t+Δt）内发生的事件 发生的概率 1 n Pn(t) 无到达，无离去 （1-λnΔt） (1-μnΔt) 2 n -1 Pn-1(t) 到达一个，无离去 λn-1Δt (1-μn-1Δt) 3 n +1 Pn+1(t) 无到达，离去一个 (1-λn+1Δt) μn+1Δt 4 n Pn(t) 到达一个，离去一个 (λnΔt) (μnΔ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过程（又称为Poisson流，最简流）是排队论中经常用来描述顾客到达的特殊随机过程。实际上它是一个纯生过程，与概率论中的Poisson分布和负指数分布有密切的联系。 下面结合排对论的术语，给出Poisson过程的定义： 定义2 设N(t)为时间 [0, t] 内到达系统的顾客数，如果满足下面三个条件： （1）平稳性： 在[t, t + Δt]内有一个顾客到达的概率为 即 其中常数λ0称为过程N(t)的强度，而o(Δt)为当Δt-0时关于Δt 的高阶无穷小。 注： （2） 独立性 任意两个不相交区间内顾客到达情况相互独立 （3） 普通性 在 [t, t+Δt] 内多于一个顾客到达的概率为 亦即对于充分小的Δt，在 [t, t+Δt] 内出现2个或2个以上质点的概率与出现一个质点的概率相比可以忽略不计。 则称 { N(t), t ≥0 } 为Poisson过程（强度为λ ）。 定理1 设N(t)为时间 [ 0, t ]内到达系统的顾客数，则 { N(t), t ≥0 } 为Poisson过程的充分必要条件是： n=1,2… 定理1说明，如果顾客的到达为Poisson流的话，则到达顾客数的分布恰为Poisson分布。 举例 顾客按泊松流到达餐厅，平均每小时20人，在上午11：07餐厅内有18人 试求：到11：12餐厅内有20名顾客的概率 分析： 依题意知 λ＝20 （人/小时） 由公式 可知： 在（1/12）h内到达顾客2人的概率为： 但无论是从Poisson过程的定义，还是根据其概率分布去对顾客的到达情况进行分析，都有许多不便之处。 实际问题中比较容易得到和进行分析的往往是顾客相继到达系统的时刻，或相继到达的时间间隔。 定理2 设N(t)为时间 [ 0, t ] 内到达系统的顾客数，则 { N(t), t ≥0 }为参数为λ的Poisson过程的充分必要条件是：相续到达时间间隔服从相互独立的参数为λ的负指数分布。 定理2说明，顾客相续到达时间间隔服从相互独立的参数为λ的负指数分布，与到达过程为参数λ的Poisson过程是等价的。 举例 某排队系统，顾客到达为泊松流，平均1人/h。假如有一名顾客于