第五章 马尔可夫过程-4

5.5.1 随机服务系统（排队论）的基本概念
三、 随机服务系统要素
四要素：输入过程、排队规则、服务过程、服务台数目。
1. 输入过程：描述顾客到达的规律(与顾客到达率和到达时间的 随机性有关)。其特征常用相邻两个顾客到达的时间间隔的分布 函数来描述。
几种常见的输入过程：
（1）泊松过程。顾客到达间隔Tk为独立同分布的随机序列，其 分布为指数分布，概率密度为
0 λ1
0 0
0 0
0 " "⎞ 0 " "⎟⎟
⎜0
Q
=
⎜ ⎜
#
μ2 %
−(λ2 + μ2 ) λ2
0
% %%
0 " "⎟ ⎟ ⎟
⎜0
"
⎜ ⎜
#
#
0 #
μi 0
−(λi + μi ) %
λi %
0 %
"⎟ "⎟⎟
⎜⎝ 0
0
"
"
"
% % %⎟⎠
当μi =0,为纯生过程；当λi =0,为纯灭过程。
5.4 生灭过程 5.4.4 转移速率图
状态空间E={0,1,2,3,…}(状态无限); T=[0, ∞] 。
如果λi , μi 均是t的函数，则称为非齐次生灭过程； 如果λi , μi 均是t的线性函数，则称为非齐次线性生灭过程； 如果λi , μi 均与t无关，则称为齐次生灭过程。
5.4 生灭过程
5.4.2 转移概率 齐次生灭过程转移概率如下：
fT
(t)
=
(λt)n−1 λe−λt
(n −1)!
,
t≥0
（3）定长输入。顾客到达的时间间隔一定。
（4）伯努利到达。顾客的到达仅限于某一固定时间T的整数 倍时刻，在各个整数倍时刻顾客是否到达是由概率为p的伯 努利试验决定的。
预约到达、集体到达，等。
顾客源无限；顾客源有限。
5.5.1 随机服务系统（排队论）的基本概念
(1) p ii +1 (τ ) = λ iτ + o (τ ) , λ i > 0 ( 2 ) p ii −1 (τ ) = μ iτ + o (τ ) , μ i > 0 , μ 0 = 0 ( 3 ) p ii (τ ) = 1 − ( λ i + μ i )τ + o (τ ) ( 4 ) p ij (τ ) = o (τ ) , | i − j |≥ 2 .
称为整体平衡方程, 即
λ π i −1 i −1 + μ π i +1 i +1 = λiπ i + μ iπ i
它表示进入状态i的平均速率等于离开状态i的平均速率。
5.4 生灭过程
5.4.6 平稳分布
平衡方程
生灭过程的平稳分布，
πi
=
λ 0λ1 " λi−1 μ1μ 2 " μi
π
0,
从该式得到
μ iπ i = λ π i −1 i −1
i = 1, 2 , 3, ...
称为详细平衡方程，它表示从状态i-1转移到状态i的平均速 率等于从状态i转移到状态i-1的平均速率。
5.4 生灭过程
5.4.7 有限状态
状态空间E={0,1,2,3,…,N}; T=[0, ∞]
当i≥N, λi =0; 当i>N, μi =0.
（3）混合制。当顾客到达时，若队伍长度小于某个预定数 时，就排入队伍，否则就自动离去。
5.5.1 随机服务系统（排队论）的基本概念
三、随机服务系统要素
常见服务规则有： （1）先来先服务。 （2）后来先服务。 （3）随机选择服务。所有到达的顾客都有相同的概率接受 服务。 （4）优先权服务。 （5）批量服务。
π
0
∑ π 0 +
+∞ i =1
λ 0λ1 " λi−1 μ1μ 2 " μi
π
0
=1
5.4 生灭过程 5.4.6 平稳分布
∑ 当
+∞ λ0λ1 " λi−1 i=1 μ1μ2 " μi
收敛时，存在平稳分布
∑ π 0
=
⎡ ⎢1 + ⎣
+∞ i =1
λ 0λ1 " λi−1 μ1μ 2 " μi
⎤ ⎥ ⎦
生灭过程 λ0
λ1
λ2
0
μ1
纯生过程
λ0
1
μ2
λ1
2
μ3
λ2
0
1
2
0
0
0
纯灭过程
0
0
0
0ቤተ መጻሕፍቲ ባይዱ
1
2
μ1
μ2
μ3
λN-1
λN
…
N
…
μN
μN+1
λN-1
λN
…
N
…
0
0
0
…
μN
0
N
…
μN+1
5.4 生灭过程
5.4.5 微分方程
柯尔莫哥洛夫前进方程、后退方程：转移概率与转移速 率的微分关系。
前进方程
P′(t) = P(t)Q,
p −1 j−1 p0 (t)
(t
),
j ≥1
初始概率:p0(0)=1, 对i≥1,pi(0)=0
j −1
j
∏ ∑ p j (t ) =
λ jt[ clje − λlt ]
k =0
l=0
∏ clj =
1
(λl − λ j )
l≠ j
5.5 生灭过程在排队论中的应用 5.5.1 随机服务系统（排队论）的基本概念 一、随机服务系统模型
三、随机服务系统要素
四要素：输入过程、排队规则、服务过程、服务台数目。 2. 排队规则：顾客接受服务的规则，或等待服务的顾客进入 服务所规定的次序。
常见的排队规则有：
（1）消失制。当顾客到达时，见到所有服务台都已被占用， 就自行消失，不进入排队等待行列。
（2）等待制。当顾客到达时，若所有服务台都已被占用时， 多余的顾客排队等待，这是无限空间等候的情形。
5.4 生灭过程 5.4.3 转移速率矩阵
根据转移速率的定义，
⎧ λi, j = i + 1
qij
= lim τ →0
p ij (τ ) − δ ij τ
=
⎪⎪ ⎨ ⎪
−
(
μ λ
i i
, +
j=
μi ),
i
−1 j=
i
⎩⎪ 0, | j − i |≥ 2
转移速率矩阵为
⎛ ⎜ ⎜
−λ0 μ1
λ0 −(λ1 + μ1)
例如，若服务时间是参数为μ的指数分布，则平均服 务时间为1/μ, 平均服务率则为μ 。
顾客的等待时间为一个随机变量序列，其数学期望为平 均等待时间。
5.5.1 随机服务系统（排队论）的基本概念
二、有关定义、概念
系统时间：顾客从到达到离开系统所用的时间。显然，一个 顾客的系统时间为等待时间与服务时间之和。
P(0) = I
⎧⎨pi′j ⎩
(t)
=
−(λj
+μj )pij
pi′0(t)
(t)+λj−1pi, j−1(t)+μj+1pi, = −λ0 pi0(t)+μ1pi1(t)
j+1(t),
j ≥1
5.4 生灭过程
5.4.5 微分方程
柯尔莫哥洛夫前进方程、后退方程：转移概率与转移速 率的微分关系。
后退方程
P′(t) = P(t)Q
5.4 生灭过程
5.4.6 平稳分布 若极限分布存在,则存在平稳状态.
根据定理，若平稳分布{πi, i=1,2,…}存在，必满足线性
方程组
(π 0 π1 " πi ")Q = 0
又
+∞
∑πi =1
i=0
把转移速率代入，方程组化为 ⎧
⎪ ⎪⎪ ⎨
− λ0π λi −1π i
可见，在一小段时间内，忽略高阶无穷小o(τ)，生灭过程的状 态变化只有三种情况： （1）状态i转移至状态i +1，状态增加1，群体“生”了一个个体，
“生长率”为λi ；
（2）状态i转移至状态i -1，状态减少1，群体“死”了一个个体，
“灭亡率”为μi ；
（3）状态不增不减，群体个数不变。生灭过程所有状态都是相通的。
i = 1, 2, ..., N
⎪
+∞
⎪ ⎪⎩
∑πi =1
i=0
有限状态的生灭过程必存在平稳分布
5.4 生灭过程
5.4.8 纯生过程
状态空间E={0,1,2,3,…}; T=[0, ∞]
当j≥0, μj =0.
微分方程:
⎧ ⎨ ⎩
p′j
(t
)
=
−λj p j
p0′ (t
(t) )=
+ λj −λ0
⎧ ⎨ ⎩
p′j
(t)
=
−(λ j
+
μj)p
p0′ (t)
j (t) + λ j−1 p j−1(t) + μ j+1 = −λ0 p0 (t) + μ1 p1(t)
p
j +1 (t ),
j ≥1
[ p0′ (t) p1′(t) " p′N (t)"] = [ p0 (t) p1(t) " pN (t)"]Q