运筹学
状态转移图
0
1
. . . n-1
n
n+1 . . .
. . . Ｎ-1
Ｎ
运筹学
2 系统容量有限制的情形 (M/M/1/N/∞/FCFS）
状态转移方程
P1 P0 Pn1 Pn1 ( )Pn PN PN 1
n 0 n N -1
n N
运筹学
pn Cn p0 , n 1,2,...
0 1
运筹学
队列长
Lq (n 1)Pn nPn Pn
n0
n 1
n 1
Ls
2 1
运筹学
逗留时间: 可以证明, Ws服从参数为μλ的负指数分布. 则:
Ws
1
等待时间 Wq Ws W服务
Wq
Ws
1
运筹
Wq
Little公式（相互关系）
Ls Ws
1
Ws Wq
Lq Wq
Ls Lq
运筹学
例15-2：某医院手术室每小时就诊病人数和手术时间的 记录如下：
到达的病人数
n 0 1 2 3 4 5 6 以上 合计
出现次数
un 10 28 29 16 10 6
1 100
完成手术时间
r 0.0~0.2 0.2~0.4 0.4~0.6 0.6~0.8 0.8~1.0 1.0~1.2 1.2 以上
2.11
Lq Ls (1 P0 ) 2.11 (1 0.2778) 1.39
运筹学
求有效到达率 e （1 PN）或 e （1 P0） e 4(1 0.2778) 2.89 人/小时
顾客在理发馆内逗留的期望时间
Ws Ls / e 2.11/ 2.89 0.73 小时
43.8 分钟
运筹学
可能的顾客中有百分之几不等待就离 开，即求系统中有7个顾客的概率。
P7
(
)
1 / 1 ( / )8
(
3 4
)
13/ 4 1 (3/ 4)8
3.7%
2.1 5.25 2.5
4.41
Ws
1
Wq
运筹学
2 系统容量有限制的情形 (M/M/1/N/∞/FCFS）
系统的最大容量为N，排队等待的顾客最 多为N - 1，在某一时刻顾客到达时，如 果系统中已有Ｎ个顾客，那么这个顾客 就被拒绝进入系统。
当Ｎ＝1时，为即时制；
当Ｎ 时，容量无限制的情形。
队列长
N
运筹学
Lq (n 1)Pn Ls (1 P0 )
n1
逗留时间
有效到达率：e （1 PN）或 e （1 P0）
根据Little 公式
Ws
Ls
e
Ls
（1
P0）
Lq
（1
PN）
1
等待时间
1
Wq Ws
运筹学
例：单人理发馆排队问题 有6个椅子接待人们排队，超过6人顾 客就离开，平均到达率3人/小时，理发 需时平均15分钟。
Ｎ＝7为系统中的最大顾客数。
平均到达率， 平均服务率 ＝3人/小时，＝4人/小时。
运筹学
顾客到达就能理发的概率 相当于理发店内没有顾客
P0
1
1
N 1
1
1 3/ 4 (3 / 4)8
0.2778
等待顾客数的期望值
Ls
1
(N 1) N 1 N 1
1
1
3
/4 3/
4
8(3 / 1 (3
4)8 / 4)8
(3) 1 p0 ——服务强度
(4) 1, 即顾客平均到达率
小于顾客平均服务率时， 运筹学 系统才能达到统计平稳。
计算有关指标
队长
Ls nPn n(1 ) n
n0
n 1
( 2 2 3 3 ...) ( 2 2 3 ...)
2 3 ... 1
Ls
平衡方程：
pn 1 p0
n
PnP10
P1 0 Pn1 (
)Pn
0
n 0 n 1
求解：令 : ，且当 1 时
P0 Pn
1 (1 ) n
n 1
运筹学
关于 的几点说明：
(1) 顾客平均到达率 顾客平均服务率
(2) ••1系 服/ 统务 中台 至处一少于个有忙顾一的客个状服务顾态时客 的间的 概概 率率 ；； •1反/ 映 系统一繁个忙顾程客度到达。时间
其中
Cn
n 1 n2 ...0 n n1...1
pn 1 p0
n
pn Cn p0 , n 1,2,...
where
Cn
n 1 n2...0 n n1...1
n
n
N
pn 1 p0 p0 2 p0 n p 1 0 运筹学
n0
求解得 :
P1 P0 P2 2 P0
单服务台负指数分布排队系统分析
本节讨论输入过程服从Poisson过程，服务 时间服从负指数分布单服务台的排队系统，分 三种情况讨论： 1 M/M/1模型
2 M/M/1/N/ 模型(即系统的容量有限) 3 M/M/1/ /m 模型（即顾客源为有限）
运筹学
1 M/M/1模型
输入过程服从
顾客源 参数为 的
100 每次手术平均时间
rvr 0.（4 小时/人）
100
0.8~41.0
160
1.0~51.2
56
16.2以以上上 01
合计
100
每小时完成手术人数
（平均服务率）
1 2.5（人/小时）
0.4
运筹学
解： 2.1, 2.5
2.1
Ls 2.5 2.1 5.25
Lq
Ls
合计
出现次数
vr 38 25 17 9 6 5 0 100 运筹学
解： 2.1, 2.5每小时病人平均到达率
到完达成的手病术人时数间
nr 0.0~00.2 0.2~10.4 0.4~20.6 0.6~30.8
出现次数
vurn 3180 2258 1279 196
nun 2.1（人/小时）
...
PN N P0
P0 P1 ... PN 1
P0 P0 ... N P0 1
P0 (1 ... N ) 1
P0
1
N 1 1
1
运筹学
P0
1 1 N 1
Pn
1 1 N 1
n
计算有关指标
n 1,2,..., N
队长
Ls
N
nPn
n0
1
(N 1) N 1 1 N 1
Poisson过程
服务时间服从
生灭过程 参数为 的
负指数分布
排队系统
接受服务
无 限
排队结构
排队规则
服务 机构
服务规则
后离去
单队
队长无限
运筹学
先到先服务
状态转移图
0
1
. . . n-1
n
n+1 . . .
运筹学
p pn Cn p0 , n 1,2,...
n :系统达到平稳后，其系中统有Cnn个顾客nn1的nn概12.....率.1。0