?管理与人文学院 忻展红
1999,4
第七章 随机服务理论概述
确定型只是随机现象的特例
2
7.1 随机服务系统
? 系统的输入与输出是随机变量
? A.k.Erlang 于 1909~1920年发表了一系列根据话务量计
算电话机键配置的方法，为随机服务理论奠定了基础
? 又称为 排队论 (Queuing Theory)或 拥塞理论 (Congestion
Theory)
顾
客
源
三个服务台
离
去
的
顾
客
随机服务系统
排队等待顾客
...
3
与服务系统性能相关的特性
? 服务系统存在来自两个矛盾方面的要求
– 顾客希望服务质量好，如排队等待时间短，损失率低
– 系统运营方希望设备利用率高
? 给用户一个经济上能够承受的满意的质量
? 哪些系统特性会影响系统的性能？
– 服务机构的组织方式与服务方式
– 顾客的输入过程和服务时间分布
– 系统采用的服务规则
7.1.1 服务机构的组织方式与服务方式
– 单台制和多台制
– 并联服务
– 串联服务
– 串并联服务、网络服务
– 全利用度、部分利用度
4
与服务系统性能相关的特性
7.1.2 输入过程和服务时间
– 顾客单个到达或成批到达
– 顾客到达时间间隔的分布和服务时间的分布
– 顾客源是有限的还是无限的
7.1.3 服务规则
– 损失制
– 等待制, 先到先服务 (FIFO)，后到先服务，随机服务，优
先权服务
– 混合制
– 逐个到达，成批服务；成批到达，逐个服务
5
7.2 随机服务过程
? 单台服务系统、等待制、先到先服务
? 顾客在系统中的总时长：逗留时间 =等待时长 +服务时长
? 等待时长与顾客到达率和服务时长有关
顾客
到达时刻
开始
服务时刻
服务
终结时刻
t
1 2 3 4
?
1
?
2
?
3
?
4
w
2
w
3
h
1
h
2
h
3
h
4
空
1 2 3 4
6
? 当服务台连续不断服务时，有如下关系：
wi+1+?i+1= wi+hi
? wi+hi 表示了累计的未完成的服务时长，一般地有
?
?
?
???
??????
?
??
? 0 if0
0 if
1
11
1
iii
iiiiii
i hw
hwhww
?
??
? ?i,wi,hi 可通过 写实 来获得，另一种写实法
?(t) 代表时段 (0,t)中累计到达顾客数
?(t) 代表时段 (0,t)中累计接受服务的顾客数
?(t) 代表时段 (0,t)中累计服务完毕的顾客数
? 则在任意考察时刻 t，有
正在等待的顾客数,L(t)= ?(t) ??(t)
正在接受服务的顾客数,Ls(t)= ?(t) ? ?(t)
系统中逗留的顾客数,N(t)= ?(t) ??(t)
7
? 上述关系是普遍成立的，与服务台设置和服务规则无关
? 下面分析等待顾客数、等待时间和顾客到达率的关系
– 到达率 定义为单位时间内平均到达的顾客数，即
?t= ?(t) / t
– 令 ?(t) 表示在时段 (0,t)内到达系统内顾客的 总逗留时长
– 则每一个顾客的 平均逗留时间 为
Wdt= ?(t) /?(t)
– 系统中 平均逗留顾客数 可表达为
Ldt= ?(t) / t = (?(t) / t )(?(t) /?(t) ) = ?t Wdt (Little formula)
t
系统中逗
留顾客数
平均逗留
顾客数
8
? 系统处于稳态时的利特尔公式,Ld= ?Wd
? 利特尔公式也是普遍成立的，已知其中任两个量，可以
求出另一个量
? 利特尔公式的分解：
Ld = ?Wd = ?(Wq + h ) = Lq + Ln
Lq = ?Wq Ln = ?h
– Wq 是顾客的 平均排队等待时间
– Lq 是排队等待的 平均队长
– h 是顾客的 平均服务时长
– Ln 是同时接受服务的平均顾客数 (即 平均服务台占用数 )
9
7.3 服务时间与间隔时间
7.3.1 概述
? 顾客的服务时间由于多种原因具有不确定性，最好的描述
方法就是概率分布；同样顾客到达的间隔时间也具有一定
的概率分布
? 服务时间和到达间隔时间服从什么分布？可以先通过统计
得到经验分布，然后再做理论假设和检验
? 经验分布一般采用直方图来表示，如下图
频率 %
30
20
10
2 4 6 8
通话分钟
10
? 若统计区间分得越细，样本越多，则经验分布的轮廓越接
近曲线
? 一般服务时间和间隔时间都是非负的连续实变量，令 h代
表服务时间,?代表间隔时间,t为给定的时间，则它们的
概率分布函数分别表示为
F(t)=P{h? t} F(t)=P{? ? t}
? 它们的概率密度函数为 f(t)=F?(t)，具有性质：
f(t)?0,? f(t)dt=1
? 服务时间落在区间 (a,c)的概率为
? ? )()()( aFcFdttfchaP ca ????? ?
? 服务时间落在区间 (t,t+?t)的概率为 P{t < h ? t+?t}= f(t)?t
? 平均服务时长和平均间隔时长
?? ?? ???? 00 )(][)(][ dtttfEdtttfhEh ??
? 平均服务时长的倒数为服务率，平均间隔时长的倒数为到达率
??? 11 ?? h
11
7.3.2 常用的概率分布
1、定长分布
– 流水线的加工时间
t
l
f ( t )
F ( t )
1
t
f ( t )
F ( t )
1
0 0
?
定长分布
负指数分布
2、负指数分布
一类最常用的分布，如上述通话时长，可靠性
??
?
?
??
lt
lttF
0
1)(
当
当
??? ??
?
/1)(
1)(
0 ???
??
?
? ??
?
dtethetf
etF
tt
t
12
7.3.2 常用的概率分布
3、爱尔兰分布
– 一种代表性更广的分布
t
f ( t )
0 ? ??
k = 1
k = 2
k = 3
k = 20
k 为整数，称为 k 阶爱尔兰分布； 当 k=1 时，退化为负
指数分布； k?? 时趋向定长分布
爱尔兰分布实际上是 k 个独立同分布的负指数分布随机变
量的和的分布，即 k 个服务台的串联，每个服务台的平均
服务时长为 1/k?
ktk e
k
ktktf 1
)!1(
) ( )( ??? ??
??
13
7.3.3 负指数分布的特点
? 负指数分布之所以常用，是因为它有很好的特性，使数学
分析变得方便
? 无记忆性 。指的是不管一次服务已经过去了多长时间，该
次服务所剩的服务时间仍服从原负指数分布 ? ? ? ?
? ?
? ?
? ? ? ?
? ?
Q,E,D 1
)1(1
)1(1
,
,,:
)(
0
00
0
00
0000
0
0
0
00
t
t
ttt
e
e
ee
thP
thPtthP
thP
tthtP
thtthPthtthP
th
th
?
?
??
?
?
???
??
??
???
?
?
????
?
?
???
?
???????
? 它的分布函数为则服务剩余时间为
代表服务已过去的时间代表服务时间令证
14
7.3.3 负指数分布的特点
? 一个服从负指数分布的服务，在下一瞬间结束的概率
? ?
)(
]!3) (!2) ( 1[1
1
32
00
tot
ttt
ethtthP
t
????
?????????
??????
??
?
???
?
?
应用无记忆性
? 在 ?t 内服务终结的概率只与 ?和 ?t 成正比，与 t0 无关；因
此 ? 又称为 终结率,或 离去率
? 同理，在 ?t 内服务不终结的概率为 1–??t +o(?t )
? n 个独立同分布 (负指数 )的服务台同时被占用，在 ?t内只有
一个服务台终结的概率为
)( ))( 1))(( ( 11 totntottotC nn ??????????? ? ???
? 在 ?t 内有 k >1 个服务台终结的概率为 o(?t )，称为 普通性
)())( 1())( ( totottotC knkkn ????????? ???
15
7.4 输入过程
? 即顾客到达的分布，可用相继到达顾客的间隔时间描述，
也可以用单位时间内到达的顾客数描述
– 间隔时间服从定长分布
– 单位时间内到达的顾客数服从 波松分布 (法国数学家
Poisson,1837)
– 间隔时间服从爱尔兰分布
– 一般独立同分布
7.4.1 波松输入过程及其特点
? (0,t)时间内到达 k 个顾客的个数服从波松分布，若
tk
k ek
ttP
!
) ()( ?? ??
?为 到达率
电话呼叫的到达，商店的顾客到达，十字路口的汽车流，
港口到达的船只，机场到达的飞机等
16
7.4.1 波松输入过程及其特点
(1) 平稳性,顾客到达数只与时间区间长度有关
(2) 无后效性,不相交的时间区间内所到达的顾客数是独立的
(3) 普通性,在 ?t 时间内到达一个顾客的概率为 ??t +o(?t )，
到达两个或两个以上顾客的概率为 o(?t )；即两个顾客不可
能同时到达
? 波松过程具有 可迭加性
– 即独立的波松分布变量的和仍为波松分布
? ? ? ? ? ?
t
nn
t
jn
j
t
j
j
t
j
j
t
i
i
e
n
t
e
jn
t
e
j
t
jnxPjxPnxxP
ntjin
e
j
t
tPe
i
t
tP
)(21 2
0
1
2
0
121
2 1
2121
21
!
)(
)!(
)(
!
)(
),0(,
!
)(
)(,
!
)(
)(,
????
??
????
??
???
??
?
?
?
?
??
?
?
?
??
???????
??
??
?
?
个顾客的概率为内来到在令
设两个波松分布为
17
7.4.1 波松输入过程及其特点
? 波松过程的到达间隔时间为负指数分布
– 令 ? 代表间隔时间，则概率 P{? > t}代表时间区间 (0,t)内
没有顾客来的概率；由波松分布可知
P0(t)= P{? > t}=e??t
– 故间隔时间 ?的分布为 P{?? t}=1?e??t
7.4.2 马尔科夫链
? 马尔科夫链 (Markov Chain)又简称 马氏链,是一种 离散事件
随机过程。用数学式表达为
P{Xn+1=xn+1| X1=x1,X2=x2,...,Xn=xn}= P{Xn+1=xn+1| Xn=xn}
– Xn+1的状态只与 Xn的状态有关，与 Xn 前的状态无关，
具有 无记忆性,或 无后效性,又称 马氏性
– 状态转移是一步一步发生的，一步状态转移概率
Pij(t)=P{Xn+1=j| Xn=i}
18
例 7.4.2
一售货员出售两种商品 A和 B，每日工作 8 小时。购买每种
商品的顾客到达过程为波松分布，到达率分别为 ?A=8人 /日，
?B=16人 /日，试求,(1) 1小时内来到顾客总数为 3 人的概率；
(2) 三个顾客全是购买 B类商品的概率。
解, (1)总到达率为 ?A+ ?B=24人 /日,1 小时 =1/8 日，故
(2) 3 个顾客全是购买 B 类商品的概率为
224.0!3 )8/124()8/1( 8/124
3
3 ?
?? ??eP
0 6 6 4.0
!3
)8/116()8/1()8/1( 8/188/1163
03
?
??? ???? eePP AB
19
7.5 生灭过程
? 一种描述自然界生灭现象的数学方法，如细菌的繁殖和灭
亡，人口的增减，生物种群的灭种现象等
? 采用马氏链
– 令 N(t)代表系统在时刻 t的状态，下一瞬间 t+?t 系统的
状态只能转移到相邻状态，或维持不变，如图所示
– 三种转移是不相容的，三者必居其一
– 只有具有无记忆性和普通性的过程 (分布 )才适用马氏链
– 令 Pj(t)=P{N(t)=j}代表系统在时刻 t 处于状态 j 的概率
j j
j+ 1
j ? 1
t t+ ? t
?
j
? t
? ? ? ?
? j
+ ?
j
) ? t
?
j
? t
20
生灭过程的马氏链
0 1 j +1 njj ? 1.,,,,,
?
0
? t ?
j ? ?
? t ?
j
? t? 1 ? t
?
j
? t ?
j ? ?
? t?
1
? t ?
j ? ?
? t
?
n ? ?
? t
?
n
? t
? ? ? ?
1
+ ?
1
) ? t ? ? ? ?
j- 1
+ ?
j- 1
) ? t ? ? ? ?
j
+ ?
j
) ? t ? ? ? ?
j+ 1
+ ?
j+ 1
) ? t
? 根据马氏链，应用全概率公式，有状态转移概率方程
1,,2,1)()1)((
)()()( 1111
?????????
?????? ????
njtotttp
ttpttpttp
jjj
jjjjj
???
??
? 另有两个边界方程
)()1)(()()( 00110 tottpttpttp ????????? ??
)()1)(()()( 11 tottpttpttp nnnnn ????????? ?? ??
21
生灭方程的推导过程
? 将上述三个差分方程化为微分方程
)()()()()(
1,,2,1)()(
)()(
)()(
lim
1111
1111
0
tptptptp
njtp
tptp
t
tpttp
jjjjjjjj
jjj
jjjj
jj
t
????
??
??
?????
????
??
?
???
????
????
??
即
?
? 上述三个方程是动态方程，当系统处于稳态时，系统处于
统计平衡状态，即状态概率不随时间变化，从而状态概率
导数为 0；令上三个方程左侧为 0，得稳态方程组
)()()(
)()()(
11
00110
tptptp
tptptp
nnnnn ??
??
???
???
??
同理有
)3(0
)2(10)(
)1(00
11
1111
0011
njpp
njppp
jpp
nnnn
jjjjjjj
???
??????
???
??
????
??
????
??
22
生灭过程稳态解
0 1 j +1 njj ? 1.,,,,,
? 0 ? j ? ? ? j? 1
? j ? j ? ?? 1 ? j ? ?
? n ? ?
? n
? 方程 (1),(2),(3) 与稳态状态转移图一一对应；递归解如下：
)3(0
)2(10)(
)1(00
11
1111
0011
njpp
njppp
jpp
nnnn
jjjjjjj
???
??????
???
??
????
??
????
??
1
1 21
110
00
0
21
110
1
1
0
21
10
210
1
0
1
1,1
)(,
,)2(,1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
??
???
??
n
j j
jn
j
j
j
j
j
j
j
pp
ppp
pppjpp
???
???
???
???
?
?
??
??
?
?
?
?
?
?
得由
归纳法得依次递推
式得代入将令
23
满足生灭过程的条件
? 系统的输入过程和服务过程具有平稳、无记忆性和普通性
? 服务台是独立的、相同的、并联的
? 波松输入过程和负指数服务时长就具有这些性质
– 可以用马氏链来描述系统的状态转移
– 这种系统称为 生灭服务系统,一般用 M/M/n 表示，又
称为 标准服务系统 ；
– 标准服务系统的形式很多，但都是基于生灭方程，关键
是找出 ?j,?j 的不同表达式，将它们代入 生灭方程
? 标准服务系统的表示法,(X/Y/Z,A/B/C),X 表示输入过程，
Y 表示服务过程,Z 表示并联服务台的个数,A 表示顾客
源,B 表示系统容量,C 表示服务规则
– (M/M/n,?/m/FIFO) 表示波松输入，负指数服务时长，
n 个并联服务台，顾客源无穷，系统容量为 m,m?n，先
到先服务
– D 定长分布； Ek k阶爱尔兰分布； G 一般独立分布
24
7.6 纯增过程
? 令生灭过程中所有消亡率 ?j=0,即只有顾客到达，没有顾
客离去
? 令所有 ?j=?，且系统服务台无限，即 n??
? 容易得到下列微分方程组
?,2,1
!
)(
)(
,
)(
1)()(
)(
0)(
)(
0
1
0
0
??
?
????
???
?
?
?
je
j
t
tP
etP
jtPtP
dt
tdP
jtP
dt
tdP
t
j
j
t
jj
j
?
?
?
??
?
并递推得解一次型微分方程
由此解出
该问题没有稳态解，正是波松过程
1999,4
第七章 随机服务理论概述
确定型只是随机现象的特例
2
7.1 随机服务系统
? 系统的输入与输出是随机变量
? A.k.Erlang 于 1909~1920年发表了一系列根据话务量计
算电话机键配置的方法，为随机服务理论奠定了基础
? 又称为 排队论 (Queuing Theory)或 拥塞理论 (Congestion
Theory)
顾
客
源
三个服务台
离
去
的
顾
客
随机服务系统
排队等待顾客
...
3
与服务系统性能相关的特性
? 服务系统存在来自两个矛盾方面的要求
– 顾客希望服务质量好，如排队等待时间短，损失率低
– 系统运营方希望设备利用率高
? 给用户一个经济上能够承受的满意的质量
? 哪些系统特性会影响系统的性能？
– 服务机构的组织方式与服务方式
– 顾客的输入过程和服务时间分布
– 系统采用的服务规则
7.1.1 服务机构的组织方式与服务方式
– 单台制和多台制
– 并联服务
– 串联服务
– 串并联服务、网络服务
– 全利用度、部分利用度
4
与服务系统性能相关的特性
7.1.2 输入过程和服务时间
– 顾客单个到达或成批到达
– 顾客到达时间间隔的分布和服务时间的分布
– 顾客源是有限的还是无限的
7.1.3 服务规则
– 损失制
– 等待制, 先到先服务 (FIFO)，后到先服务，随机服务，优
先权服务
– 混合制
– 逐个到达，成批服务；成批到达，逐个服务
5
7.2 随机服务过程
? 单台服务系统、等待制、先到先服务
? 顾客在系统中的总时长：逗留时间 =等待时长 +服务时长
? 等待时长与顾客到达率和服务时长有关
顾客
到达时刻
开始
服务时刻
服务
终结时刻
t
1 2 3 4
?
1
?
2
?
3
?
4
w
2
w
3
h
1
h
2
h
3
h
4
空
1 2 3 4
6
? 当服务台连续不断服务时，有如下关系：
wi+1+?i+1= wi+hi
? wi+hi 表示了累计的未完成的服务时长，一般地有
?
?
?
???
??????
?
??
? 0 if0
0 if
1
11
1
iii
iiiiii
i hw
hwhww
?
??
? ?i,wi,hi 可通过 写实 来获得，另一种写实法
?(t) 代表时段 (0,t)中累计到达顾客数
?(t) 代表时段 (0,t)中累计接受服务的顾客数
?(t) 代表时段 (0,t)中累计服务完毕的顾客数
? 则在任意考察时刻 t，有
正在等待的顾客数,L(t)= ?(t) ??(t)
正在接受服务的顾客数,Ls(t)= ?(t) ? ?(t)
系统中逗留的顾客数,N(t)= ?(t) ??(t)
7
? 上述关系是普遍成立的，与服务台设置和服务规则无关
? 下面分析等待顾客数、等待时间和顾客到达率的关系
– 到达率 定义为单位时间内平均到达的顾客数，即
?t= ?(t) / t
– 令 ?(t) 表示在时段 (0,t)内到达系统内顾客的 总逗留时长
– 则每一个顾客的 平均逗留时间 为
Wdt= ?(t) /?(t)
– 系统中 平均逗留顾客数 可表达为
Ldt= ?(t) / t = (?(t) / t )(?(t) /?(t) ) = ?t Wdt (Little formula)
t
系统中逗
留顾客数
平均逗留
顾客数
8
? 系统处于稳态时的利特尔公式,Ld= ?Wd
? 利特尔公式也是普遍成立的，已知其中任两个量，可以
求出另一个量
? 利特尔公式的分解：
Ld = ?Wd = ?(Wq + h ) = Lq + Ln
Lq = ?Wq Ln = ?h
– Wq 是顾客的 平均排队等待时间
– Lq 是排队等待的 平均队长
– h 是顾客的 平均服务时长
– Ln 是同时接受服务的平均顾客数 (即 平均服务台占用数 )
9
7.3 服务时间与间隔时间
7.3.1 概述
? 顾客的服务时间由于多种原因具有不确定性，最好的描述
方法就是概率分布；同样顾客到达的间隔时间也具有一定
的概率分布
? 服务时间和到达间隔时间服从什么分布？可以先通过统计
得到经验分布，然后再做理论假设和检验
? 经验分布一般采用直方图来表示，如下图
频率 %
30
20
10
2 4 6 8
通话分钟
10
? 若统计区间分得越细，样本越多，则经验分布的轮廓越接
近曲线
? 一般服务时间和间隔时间都是非负的连续实变量，令 h代
表服务时间,?代表间隔时间,t为给定的时间，则它们的
概率分布函数分别表示为
F(t)=P{h? t} F(t)=P{? ? t}
? 它们的概率密度函数为 f(t)=F?(t)，具有性质：
f(t)?0,? f(t)dt=1
? 服务时间落在区间 (a,c)的概率为
? ? )()()( aFcFdttfchaP ca ????? ?
? 服务时间落在区间 (t,t+?t)的概率为 P{t < h ? t+?t}= f(t)?t
? 平均服务时长和平均间隔时长
?? ?? ???? 00 )(][)(][ dtttfEdtttfhEh ??
? 平均服务时长的倒数为服务率，平均间隔时长的倒数为到达率
??? 11 ?? h
11
7.3.2 常用的概率分布
1、定长分布
– 流水线的加工时间
t
l
f ( t )
F ( t )
1
t
f ( t )
F ( t )
1
0 0
?
定长分布
负指数分布
2、负指数分布
一类最常用的分布，如上述通话时长，可靠性
??
?
?
??
lt
lttF
0
1)(
当
当
??? ??
?
/1)(
1)(
0 ???
??
?
? ??
?
dtethetf
etF
tt
t
12
7.3.2 常用的概率分布
3、爱尔兰分布
– 一种代表性更广的分布
t
f ( t )
0 ? ??
k = 1
k = 2
k = 3
k = 20
k 为整数，称为 k 阶爱尔兰分布； 当 k=1 时，退化为负
指数分布； k?? 时趋向定长分布
爱尔兰分布实际上是 k 个独立同分布的负指数分布随机变
量的和的分布，即 k 个服务台的串联，每个服务台的平均
服务时长为 1/k?
ktk e
k
ktktf 1
)!1(
) ( )( ??? ??
??
13
7.3.3 负指数分布的特点
? 负指数分布之所以常用，是因为它有很好的特性，使数学
分析变得方便
? 无记忆性 。指的是不管一次服务已经过去了多长时间，该
次服务所剩的服务时间仍服从原负指数分布 ? ? ? ?
? ?
? ?
? ? ? ?
? ?
Q,E,D 1
)1(1
)1(1
,
,,:
)(
0
00
0
00
0000
0
0
0
00
t
t
ttt
e
e
ee
thP
thPtthP
thP
tthtP
thtthPthtthP
th
th
?
?
??
?
?
???
??
??
???
?
?
????
?
?
???
?
???????
? 它的分布函数为则服务剩余时间为
代表服务已过去的时间代表服务时间令证
14
7.3.3 负指数分布的特点
? 一个服从负指数分布的服务，在下一瞬间结束的概率
? ?
)(
]!3) (!2) ( 1[1
1
32
00
tot
ttt
ethtthP
t
????
?????????
??????
??
?
???
?
?
应用无记忆性
? 在 ?t 内服务终结的概率只与 ?和 ?t 成正比，与 t0 无关；因
此 ? 又称为 终结率,或 离去率
? 同理，在 ?t 内服务不终结的概率为 1–??t +o(?t )
? n 个独立同分布 (负指数 )的服务台同时被占用，在 ?t内只有
一个服务台终结的概率为
)( ))( 1))(( ( 11 totntottotC nn ??????????? ? ???
? 在 ?t 内有 k >1 个服务台终结的概率为 o(?t )，称为 普通性
)())( 1())( ( totottotC knkkn ????????? ???
15
7.4 输入过程
? 即顾客到达的分布，可用相继到达顾客的间隔时间描述，
也可以用单位时间内到达的顾客数描述
– 间隔时间服从定长分布
– 单位时间内到达的顾客数服从 波松分布 (法国数学家
Poisson,1837)
– 间隔时间服从爱尔兰分布
– 一般独立同分布
7.4.1 波松输入过程及其特点
? (0,t)时间内到达 k 个顾客的个数服从波松分布，若
tk
k ek
ttP
!
) ()( ?? ??
?为 到达率
电话呼叫的到达，商店的顾客到达，十字路口的汽车流，
港口到达的船只，机场到达的飞机等
16
7.4.1 波松输入过程及其特点
(1) 平稳性,顾客到达数只与时间区间长度有关
(2) 无后效性,不相交的时间区间内所到达的顾客数是独立的
(3) 普通性,在 ?t 时间内到达一个顾客的概率为 ??t +o(?t )，
到达两个或两个以上顾客的概率为 o(?t )；即两个顾客不可
能同时到达
? 波松过程具有 可迭加性
– 即独立的波松分布变量的和仍为波松分布
? ? ? ? ? ?
t
nn
t
jn
j
t
j
j
t
j
j
t
i
i
e
n
t
e
jn
t
e
j
t
jnxPjxPnxxP
ntjin
e
j
t
tPe
i
t
tP
)(21 2
0
1
2
0
121
2 1
2121
21
!
)(
)!(
)(
!
)(
),0(,
!
)(
)(,
!
)(
)(,
????
??
????
??
???
??
?
?
?
?
??
?
?
?
??
???????
??
??
?
?
个顾客的概率为内来到在令
设两个波松分布为
17
7.4.1 波松输入过程及其特点
? 波松过程的到达间隔时间为负指数分布
– 令 ? 代表间隔时间，则概率 P{? > t}代表时间区间 (0,t)内
没有顾客来的概率；由波松分布可知
P0(t)= P{? > t}=e??t
– 故间隔时间 ?的分布为 P{?? t}=1?e??t
7.4.2 马尔科夫链
? 马尔科夫链 (Markov Chain)又简称 马氏链,是一种 离散事件
随机过程。用数学式表达为
P{Xn+1=xn+1| X1=x1,X2=x2,...,Xn=xn}= P{Xn+1=xn+1| Xn=xn}
– Xn+1的状态只与 Xn的状态有关，与 Xn 前的状态无关，
具有 无记忆性,或 无后效性,又称 马氏性
– 状态转移是一步一步发生的，一步状态转移概率
Pij(t)=P{Xn+1=j| Xn=i}
18
例 7.4.2
一售货员出售两种商品 A和 B，每日工作 8 小时。购买每种
商品的顾客到达过程为波松分布，到达率分别为 ?A=8人 /日，
?B=16人 /日，试求,(1) 1小时内来到顾客总数为 3 人的概率；
(2) 三个顾客全是购买 B类商品的概率。
解, (1)总到达率为 ?A+ ?B=24人 /日,1 小时 =1/8 日，故
(2) 3 个顾客全是购买 B 类商品的概率为
224.0!3 )8/124()8/1( 8/124
3
3 ?
?? ??eP
0 6 6 4.0
!3
)8/116()8/1()8/1( 8/188/1163
03
?
??? ???? eePP AB
19
7.5 生灭过程
? 一种描述自然界生灭现象的数学方法，如细菌的繁殖和灭
亡，人口的增减，生物种群的灭种现象等
? 采用马氏链
– 令 N(t)代表系统在时刻 t的状态，下一瞬间 t+?t 系统的
状态只能转移到相邻状态，或维持不变，如图所示
– 三种转移是不相容的，三者必居其一
– 只有具有无记忆性和普通性的过程 (分布 )才适用马氏链
– 令 Pj(t)=P{N(t)=j}代表系统在时刻 t 处于状态 j 的概率
j j
j+ 1
j ? 1
t t+ ? t
?
j
? t
? ? ? ?
? j
+ ?
j
) ? t
?
j
? t
20
生灭过程的马氏链
0 1 j +1 njj ? 1.,,,,,
?
0
? t ?
j ? ?
? t ?
j
? t? 1 ? t
?
j
? t ?
j ? ?
? t?
1
? t ?
j ? ?
? t
?
n ? ?
? t
?
n
? t
? ? ? ?
1
+ ?
1
) ? t ? ? ? ?
j- 1
+ ?
j- 1
) ? t ? ? ? ?
j
+ ?
j
) ? t ? ? ? ?
j+ 1
+ ?
j+ 1
) ? t
? 根据马氏链，应用全概率公式，有状态转移概率方程
1,,2,1)()1)((
)()()( 1111
?????????
?????? ????
njtotttp
ttpttpttp
jjj
jjjjj
???
??
? 另有两个边界方程
)()1)(()()( 00110 tottpttpttp ????????? ??
)()1)(()()( 11 tottpttpttp nnnnn ????????? ?? ??
21
生灭方程的推导过程
? 将上述三个差分方程化为微分方程
)()()()()(
1,,2,1)()(
)()(
)()(
lim
1111
1111
0
tptptptp
njtp
tptp
t
tpttp
jjjjjjjj
jjj
jjjj
jj
t
????
??
??
?????
????
??
?
???
????
????
??
即
?
? 上述三个方程是动态方程，当系统处于稳态时，系统处于
统计平衡状态，即状态概率不随时间变化，从而状态概率
导数为 0；令上三个方程左侧为 0，得稳态方程组
)()()(
)()()(
11
00110
tptptp
tptptp
nnnnn ??
??
???
???
??
同理有
)3(0
)2(10)(
)1(00
11
1111
0011
njpp
njppp
jpp
nnnn
jjjjjjj
???
??????
???
??
????
??
????
??
22
生灭过程稳态解
0 1 j +1 njj ? 1.,,,,,
? 0 ? j ? ? ? j? 1
? j ? j ? ?? 1 ? j ? ?
? n ? ?
? n
? 方程 (1),(2),(3) 与稳态状态转移图一一对应；递归解如下：
)3(0
)2(10)(
)1(00
11
1111
0011
njpp
njppp
jpp
nnnn
jjjjjjj
???
??????
???
??
????
??
????
??
1
1 21
110
00
0
21
110
1
1
0
21
10
210
1
0
1
1,1
)(,
,)2(,1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
??
???
??
n
j j
jn
j
j
j
j
j
j
j
pp
ppp
pppjpp
???
???
???
???
?
?
??
??
?
?
?
?
?
?
得由
归纳法得依次递推
式得代入将令
23
满足生灭过程的条件
? 系统的输入过程和服务过程具有平稳、无记忆性和普通性
? 服务台是独立的、相同的、并联的
? 波松输入过程和负指数服务时长就具有这些性质
– 可以用马氏链来描述系统的状态转移
– 这种系统称为 生灭服务系统,一般用 M/M/n 表示，又
称为 标准服务系统 ；
– 标准服务系统的形式很多，但都是基于生灭方程，关键
是找出 ?j,?j 的不同表达式，将它们代入 生灭方程
? 标准服务系统的表示法,(X/Y/Z,A/B/C),X 表示输入过程，
Y 表示服务过程,Z 表示并联服务台的个数,A 表示顾客
源,B 表示系统容量,C 表示服务规则
– (M/M/n,?/m/FIFO) 表示波松输入，负指数服务时长，
n 个并联服务台，顾客源无穷，系统容量为 m,m?n，先
到先服务
– D 定长分布； Ek k阶爱尔兰分布； G 一般独立分布
24
7.6 纯增过程
? 令生灭过程中所有消亡率 ?j=0,即只有顾客到达，没有顾
客离去
? 令所有 ?j=?，且系统服务台无限，即 n??
? 容易得到下列微分方程组
?,2,1
!
)(
)(
,
)(
1)()(
)(
0)(
)(
0
1
0
0
??
?
????
???
?
?
?
je
j
t
tP
etP
jtPtP
dt
tdP
jtP
dt
tdP
t
j
j
t
jj
j
?
?
?
??
?
并递推得解一次型微分方程
由此解出
该问题没有稳态解，正是波松过程
