三2010暑期培训排队论

《三2010暑期培训排队论》由会员分享，可在线阅读，更多相关《三2010暑期培训排队论（188页珍藏版）》请在文档大全上搜索。

1、董 珺排队论排队论（ Queuing theory）排队论排队论一、概率论及随机过程回顾n随机变量随机变量离散型随机变量n概率分布和概率分布图概率分布和概率分布图n数学期望和方差数学期望和方差n常见离散型随机变量的概率分布常见离散型随机变量的概率分布A二点分布二点分布?A二项式分布二项式分布?APoisson分布分布?1.1、随机变量与概率分布一、概率论及随机过程复习n随机变量随机变量离散型随机变量n概率分布和概率分布图概率分布和概率分布图n数学期望和方差数学期望和方差n常见离散型随机变量的概率分布常见离散型随机变量的概率分布A二点分布二点分布?A二项式分布二项式分布?APoisson分布分布

2、?一、随机变量与概率分布pXPpXP1)0(,) 1(), 1 , 0( ,)(nkqpCkXPknkkn)(,)(0;, 1 ,0!)(XDXEkekkXPkn随机变量随机变量连续型随机变量连续型随机变量n概率密度函数概率密度函数n概率分布函数概率分布函数n数学期望和方差数学期望和方差n常见连续型随机变量的概率分布常见连续型随机变量的概率分布A均匀分布均匀分布A指数分布？指数分布？A正态正态分布？分布？Ak阶爱尔朗分布？阶爱尔朗分布？一、随机变量与概率分布2/1)(,/1)()0(0,00,)(XDXExxexax 随机变量随机变量X X为时间间隔，如顾客到达的为时间间隔，如顾客到达的时间间

3、隔、电话呼叫的时间、产品的寿命等。时间间隔、电话呼叫的时间、产品的寿命等。密度函数密度函数),()(,)()0,( ,21)(222)(22NXXDXERRxexax 随机变量随机变量X X为时间为时间( (长度），如产品的尺寸、长度），如产品的尺寸、重量、测量误差等。重量、测量误差等。密度函数密度函数? 爱尔朗分布211)(,1)(0,)!1()()(kTDTEtekktktbktkkkXXX,21k 为为k k个相互独立的随机变量；个相互独立的随机变量；服从相同参数服从相同参数 的负指数分布；的负指数分布；kXXXT21设设 ，则，则T T的密度函数为的密度函数为 如如k k个服务台串联（

4、个服务台串联（k k个服务阶段），个服务阶段），一个顾客接受一个顾客接受k k个服务共需的服务时间个服务共需的服务时间T T，T T 爱尔朗分布。爱尔朗分布。若顾客连续接受串联的若顾客连续接受串联的k k个服务台的服个服务台的服务，各服务台的服务时间相互独立，务，各服务台的服务时间相互独立，且均服从负指数分布，则且均服从负指数分布，则顾客接受顾客接受k k个服务共需的服务时间个服务共需的服务时间T T k k阶阶爱尔朗爱尔朗分布。分布。1.2 随机过程的有关概念n随机过程随机过程(Random process)的定义的定义),(TttX 设设 ，是一族随机变量，是一族随机变量，T T是一个实数

5、集，对是一个实数集，对 是一个是一个随机变量，则称随机变量，则称 为随机过程。为随机过程。)(,tXTt),(TttXTt T T：参数集合参数集合 当当T=0,1,n,T=0,1,n,时，称为随机序列时，称为随机序列 ：随机过程的一个状态：随机过程的一个状态 状态空间状态空间E=X(t)E=X(t)全体可能取值，全体可能取值， ktX)(n随机过程的基本类型随机过程的基本类型二阶矩过程二阶矩过程平稳过程平稳过程平稳独立增量过程平稳独立增量过程常见随机过程常见随机过程A马尔可夫过程？马尔可夫过程？APoisson过程？过程？A生灭过程？生灭过程？1.2 随机过程的有关概念n定义： 若满足如下性

6、质： 对任意非负整数 ，只要就有 则称 具有马尔可夫性，马尔可夫性，或或无后效性。无后效性。马尔可夫过程 马尔可夫链离散离散,.2 , 1 , 0),(nnXttttr.21)()()(,.,)(,)()(2211rrrritXjtXPitXitXitXjtXP0)(,.,)(,)(2211rritXitXitXP)(nX1t2trt1rtt过去过去现在现在 将来将来 “ “将来将来”的情况与的情况与“过去过去”无关，无关，只是通过只是通过“现在现在”与与“过去过去”发生联系，若发生联系，若“现在现在”已知，已知，“将来将来”与与“过去过去”无关。无关。)(nXn时齐的马氏链时齐的马氏链：马氏

7、链 若满足： 则称 为时齐马尔可夫链时齐马尔可夫链)(mPiXjXPijnmn,.2 , 1 , 0),(nnX,.2 , 1 , 0),(nnX)(mPij 系统由状态系统由状态i i经过经过m m 个时间间隔个时间间隔（或或m m 步）转移到状态步）转移到状态j j 的的转移概率转移概率n其中其中PoissonPoisson过程过程是应用最为广泛的是应用最为广泛的一类随机过程，常用来描述派对系一类随机过程，常用来描述派对系统中顾客到达的过程、城市中的交统中顾客到达的过程、城市中的交通事故、保险公司的理赔次数等。通事故、保险公司的理赔次数等。Poisson过程n定义：设 为时间 内到达系统的

8、顾客数，若满足下面三个条件：n独立性：在任意两个不相交的区间内顾客到 达的情况相互独立；n平稳性：在 内有一个顾客到达的 概率为n普通性：在 内多于一个顾客到达 的率为 。则称 为Poisson过程。且N(t)服从Poisson分布。)(tNt ,00),(ttNttt , );( tt)( tttt , （1 1）只与区间长度与）只与区间长度与 起点无关。起点无关。（2 2）单位时间内一个）单位时间内一个 顾客到达的概率顾客到达的概率 为为 。Poisson过程与过程与Poisson分布分布定理定理1 1：设：设 为时间为时间 内到达系统的顾客数内到达系统的顾客数 则则 为为PoissonP

9、oisson过程的充要条件是过程的充要条件是)(tNt ,00),(ttN,.2 , 1!)()(nentntNPtn数理统计方法数理统计方法容易初步判断容易初步判断: :期望期望= =方差方差ttNDttNE)(,)(Poisson过程与负指数分布过程与负指数分布tTPsTstTP定理定理2 2：设：设 为时间为时间 内到达系统的顾客数内到达系统的顾客数 则则 为参数为为参数为 的的PoissonPoisson过程的过程的 充要条件是相继到达的时间间隔充要条件是相继到达的时间间隔T T服从相互服从相互 独立的参数为独立的参数为 的负指数分布。的负指数分布。)(tNt ,00),(ttN0,

10、00,)(ttetatT负指数分布的性质负指数分布的性质: 2/1)(,/1tNDTE马尔可夫马尔可夫性，性，或或无无后效性后效性对于对于PoissonPoisson流：流： 单位时间平均到达的顾客数单位时间平均到达的顾客数 顾客相继到达的平均间隔时间顾客相继到达的平均间隔时间/1n定义：定义：设设 为一个随机过程，若为一个随机过程，若N(t)N(t)的概率分布具有以下性质：的概率分布具有以下性质： (1) (1)假设假设N(t)=nN(t)=n，则从时刻到下一个顾客则从时刻到下一个顾客到达到达时刻止的时间服从参数为时刻止的时间服从参数为 的负指数分布；的负指数分布； (2) (2)假设假设N

11、(t)=nN(t)=n，则从时刻到下一个顾客则从时刻到下一个顾客离开离开时刻止的时间服从参数为时刻止的时间服从参数为 的负指数分布；的负指数分布； (3) (3)同一时刻是只有一个同一时刻是只有一个 顾客到达或离去。顾客到达或离去。 则称则称 为一个为一个生灭过程生灭过程。 0),(ttN0),(ttNnn生灭生灭过程过程1 10 001nn-1n+11nnn1n平稳生灭过程系统状态平稳生灭过程系统状态n n平衡方程：平衡方程：“流入流入= =流出流出”nnnnnnnppppp)(011111100系统达到平稳状态时：系统达到平稳状态时：.)2 , 1 , 0(),(ntppnn)(tN的分布