第五章 马尔可夫过程-4

1、 5.4 生灭过程5.4.1 定义如果连续参数马尔可夫链X (t , t 0满足:(1状态转移仅限于从一个状态向其邻近状态转移;(2若X (t = i ,则在t, t+内由状态i 转移状态i +1的概率为;由状态i 转移状态i -1的概率为;状态i 不变的概率为;(3若X (t = i ,则在t,t+内由状态i 转移二个或二个以上状态的概率为o (。则称该链X (t , t 0为生灭过程。状态空间E=0,1,2,3,(状态无限; T=0, 。如果i , i 均是t 的函数,则称为非齐次生灭过程;如果i , i 均是t 的线性函数,则称为非齐次线性生灭过程;如果i , i 均与t 无关,则称为齐

2、次生灭过程。(i t +(i t +1(i i t t + 5.4 生灭过程5.4.2 转移概率齐次生灭过程转移概率如下:可见,在一小段时间内,忽略高阶无穷小o (,生灭过程的状态变化只有三种情况:(1状态i 转移至状态i +1,状态增加1,群体“生”了一个个体,“生长率”为i ;(2状态i 转移至状态i -1,状态减少1,群体“死”了一个个体,“灭亡率”为i ;(3状态不增不减,群体个数不变。生灭过程所有状态都是相通的。110(1(, >0(2 (, >0, =0(3 (1(4(, | 2.ii i i ii i i ii i i ij p o p o p o p o i j +

3、=+=+=+= 5.4 生灭过程5.4.5 微分方程柯尔莫哥洛夫前进方程、后退方程:转移概率与转移速率的微分关系。(, (0t t =P P Q P I1,11,100011(,1(ij j j ij j i j j i j i i i p t p t p t p t j p t p t p t +=+=+前进方程 5.4 生灭过程5.4.5 微分方程柯尔莫哥洛夫前进方程、后退方程:转移概率与转移速率的微分关系。(, (0t t =P QP P I1,1,00001(, 1(ij i i ij i i j j i j j j j p t p t p t p t i p t p t p t +=

4、+=+后退方程 5.4 生灭过程5.4.5 微分方程福克-普朗克方程:绝对概率与转移速率的微分关系。111100011(,1(j j j j j j j j p t p t p t p t j p t p t p t +=+=+0101( ( ( ( (N N p t p t p t p t p t p t =Q """"(t t =P P Q 5.4 生灭过程5.4.6 平稳分布若极限分布存在,则存在平稳状态.根据定理,若平稳分布i , i =1,2,存在,必满足线性方程组又把转移速率代入,方程组化为(01i =Q 0""01i i

5、 +=0011111100 (0, 1,2,.1 i i i i i i i i i i +=+=+= 5.4 生灭过程5.4.6 平稳分布平衡方程当过程渐近平稳状态时,有称为整体平衡方程,即它表示进入状态i 的平均速率等于离开状态i 的平均速率。001111110(0, 1,2,.i i i i i i i i +=+=1111i i i i i i i i+=+ 5.4 生灭过程5.4.7 有限状态状态空间E=0,1,2,3,N; T=0, 当i N, i =0; 当i >N,i =0.微分方程:1111000111111(,(j j j j j j j j N N N N N j

6、N p t p t p t p t p t p t p t p t p t p t +=+=+=(t t =P P Q 5.4 生灭过程5.4.7 有限状态状态空间E=0,1,2,3,N; T=0, 当i N, i =0; 当i >N,i =0.平稳分布:001111111100(0, 1,2,.,01i i i i i i i N N N N i i i N +=+=+=有限状态的生灭过程必存在平稳分布 5.5.1 随机服务系统(排队论的基本概念二、有关定义、概念若顾客在时刻t k 到达,则称t k 为到达时间;随机变量T k =t k+1-t k 称为到达间隔;若T k 是独立同分布

7、的,则称ET k 为平均到达间隔;若顾客在0,t内到达的数目为随机过程N(t,则称N(t/t 为该区间上的平均到达率(,即单位时间内平均到达系统的顾客数量,反映了顾客到达系统的快慢程度。=1/ ET k 例如,强度为泊松过程的平均到达间隔为1/,平均到达率则为。 5.5.1 随机服务系统(排队论的基本概念二、有关定义、概念服务台对第k个顾客的服务时间t是一个随机变量序k便是平均服务列,若该序列是独立同分布的,则期望Etk时间,其倒数则为平均服务率(,即单位时间内由一个服务台进行服务所离开系统的平均顾客数。例如,若服务时间是参数为的指数分布,则平均服务时间为1/, 平均服务率则为。顾客的等待时间

8、为一个随机变量序列,其数学期望为平均等待时间。 5.5.1 随机服务系统(排队论的基本概念二、有关定义、概念系统时间:顾客从到达到离开系统所用的时间。显然,一个顾客的系统时间为等待时间与服务时间之和。系统容量:系统所容许的最大顾客数。系统的总顾客数可分成两种状态:排队状态和接受服务状态。显然,总顾客数为排队顾客数与接受服务顾客数之和。平均拒绝率:当请求服务的顾客数目超过系统容量时,则将有部分顾客被系统拒绝。单位时间内被系统拒绝的平均顾客数称为系统的平均拒绝率。服务台利用率:若系统共有m个服务台,某时刻被占用的服务台数为r(t,则服务台利用率定义为Er(t/m。 5.5.1 随机服务系统(排队论

9、的基本概念三、随机服务系统要素四要素:输入过程、排队规则、服务过程、服务台数目。2. 排队规则:顾客接受服务的规则,或等待服务的顾客进入服务所规定的次序。常见的排队规则有:(1消失制。当顾客到达时,见到所有服务台都已被占用,就自行消失,不进入排队等待行列。(2等待制。当顾客到达时,若所有服务台都已被占用时,多余的顾客排队等待,这是无限空间等候的情形。(3混合制。当顾客到达时,若队伍长度小于某个预定数时,就排入队伍,否则就自动离去。 5.5.1 随机服务系统(排队论的基本概念三、随机服务系统要素常见服务规则有:(1先来先服务。(2后来先服务。(3随机选择服务。所有到达的顾客都有相同的概率接受服务

10、。(4优先权服务。(5批量服务。 5.5.1 随机服务系统(排队论的基本概念三、随机服务系统要素四要素:输入过程、排队规则、服务过程、服务台数目。3.服务过程:指各个顾客接受服务的时间的分布规律(取决于服务机构的效率和服务时间。其特征用服务时间的分布函数来描述。服务时间常常是独立同分布的,其概率分布常有:指数分布、Erlang分布、定长分布等,对应的服务称为指数服务、Erlang服务、定长服务等。4.服务台数目:系统内可以同时提供服务的设备或窗口数。可以有1个、N个或个。各服务台之间彼此独立地工作。 5.5.1 随机服务系统(排队论的基本概念四、排队系统的表示一个排队系统常按下列特征和顺序,并

11、用记号表示:顾客到达分布/服务时间分布/服务台数目/系统容量/顾客源数/服务规则顾客到达间隔分布和服务时间分布用下列字母表示:M-指数分布;D-定长时间分布;G-一般分布;E-Erlang分布。例如:M/M/ n /N/FIFO (First In First Out表示输入过程为泊松过程,顾客到达间隔服从指数分布;服务时间为指数分布;服务台n个;系统容量N个;顾客来源无限;服务规则是先到先服务。 5.5.1 随机服务系统(排队论的基本概念五、评价随机服务系统的指标评价一个随机服务系统性能优劣的标准:从顾客的角度来说,平均系统时间和平均等待时间越短越好;平均拒绝率与平均到达率之比越小越好。从系

12、统资源利用率的角度来看,服务台利用率越大越好。 5.5.1 随机服务系统(排队论的基本概念六、排队系统的需要研究的主要问题排队系统的指标(1在排队系统中的顾客数(队长、平均顾客数(平均队长;(2在排队等候的顾客数、平均顾客数;(3顾客在系统中所花费的系统时间、平均系统时间;(4顾客在排队中的等待时间、平均等待时间。(5系统效率(可用平均服务台占用率表示,即各时刻服务台占用数的均值与服务台总数的比值 5.5.1 随机服务系统(排队论的基本概念六、排队系统的需要研究的主要问题解决思路:若设X(t为时刻t系统中的顾客数,X(t,t0便为一连续参数马尔可夫链(生灭过程. 已知到达率、服务率,建立系统状

13、态概率微分方程,求出该过程的绝对概率(瞬态分布、稳态分布,再求系统的其它各项指标。Little公式:系统平均顾客数=平均到达率×平均系统时间排队平均顾客数=平均到达率×平均等待时间 5.5.2 生灭过程在排队系统中的应用一、不同排队系统的状态空间和转移速率生灭过程要素:状态空间状态转移矩阵生长率(顾客到达率为,灭亡率(平均服务率为 5.5.2 生灭过程在排队系统中的应用一、不同排队系统的状态空间和转移速率消失制/损失制:顾客不需排队等待,当顾客到达时,若服务台有空闲,就立即接受服务,否则自行消失。若服务台n个,状态空间为E=0,1,2,n。等待制:顾客到达时,若所有服务台都

14、忙时,便排队等待。当顾客源无限时,状态空间无限E=0,1,2,;当顾客源有限,总数为m时,状态空间有限E=0,1,2,m。混合制。系统中容纳的排队顾客数有限。当顾客到达时,若排队队伍长度小于该容量时,就排入队伍,否则就自动离去。当排队容量为N,服务台n个时,状态空间有限E=0,1,2,N+n 5.5.2 生灭过程在排队系统中的应用一、不同排队系统的状态空间和转移速率若顾客按泊松分布到达,平均到达率为;服务时间服从平均服务率为的指数分布,状态转移速率如下:当顾客源无限时,到达率为i = ;当顾客源有限时,总数为m 时,到达率i = (m-i 。当服务台为1个时,服务率为i = ;当服务台为n 个

15、时,服务率为, 1,ii i n n i n => 0000(00(0000(0000+=+Q """"""#%""#%""""%5.5.2 生灭过程在排队系统中的应用二、M/M/1等待制排队系统转移概率矩阵: 5.5.2 生灭过程在排队系统中的应用二、M/M/1等待制排队系统状态微分方程:稳态解:当t ,p i (t趋于稳定,即p i (t=0, 有00111( (,0i i i i p t p t p t p t p t p t p t i +=+=+>011

16、1=0 (0,i i i i +=>01ki = 5.5.2 生灭过程在排队系统中的应用三、M/M/n 等待制排队系统该系统为输入过程为泊松过程,顾客到达间隔为指数分布,顾客到达率为;有n 个服务台,每个服务台的服务时间均为指数分布的随机变量,平均服务率为,平均服务时间为1/;当n 个服务台均在服务时,再到达的顾客参加排队,并按先到达先服务的规则服务;顾客源无限制;顾客到达和各服务台的服务时间均是统计独立的。M/M/ n /FIFO设时刻t 该系统的顾客数为X(t,则X(t,t 0是一生灭过程。状态空间E=0,1,2,i , i+1,转移速率:顾客到达率i = ;顾客离去率:, 1,ii i n n i n => 5.5.2 生灭过程在排队系统中的应用三、M/M/n 等待制排队系统转移速率矩阵0000(00002(20000(00(00n n n n +=+Q """"""#%""#""""% 5.5.2 生灭过程在排队系统中的应用三、M/M/n 等待制排队系统状态微分方程011111( (1(, 1,2,.,1(, i i i i i i i i p t p t p t p t p t i p t i p t i n p t p