运筹学－北京邮电大学-7PPT模板|运筹学－北京邮电大学-7PPT模版(幻灯片模板|Powerpoint模板)

第七章 随机服务理论概述
确定型只是随机现象的特例
7.1 随机服务系统
系统的输入与输出是随机变量
A.k.Erlang 于1909~1920年发表了一系列根据话务量计算电话机键配置的方法，为随机服务理论奠定了基础
又称为排队论(Queuing Theory)或拥塞理论(Congestion Theory)
与服务系统性能相关的特性
服务系统存在来自两个矛盾方面的要求
顾客希望服务质量好，如排队等待时间短，损失率低
系统运营方希望设备利用率高
给用户一个经济上能够承受的满意的质量
哪些系统特性会影响系统的性能？
服务机构的组织方式与服务方式
顾客的输入过程和服务时间分布
系统采用的服务规则
7.1.1 服务机构的组织方式与服务方式
单台制和多台制
并联服务
串联服务
串并联服务、网络服务
全利用度、部分利用度
与服务系统性能相关的特性
7.1.2 输入过程和服务时间
顾客单个到达或成批到达
顾客到达时间间隔的分布和服务时间的分布
顾客源是有限的还是无限的
7.1.3 服务规则
损失制
等待制：先到先服务(FIFO)，后到先服务，随机服务，优先权服务
混合制
逐个到达，成批服务；成批到达，逐个服务
7.2 随机服务过程
单台服务系统、等待制、先到先服务
顾客在系统中的总时长：逗留时间=等待时长+服务时长
等待时长与顾客到达率和服务时长有关

当服务台连续不断服务时，有如下关系：
wi+1+%26#61556;i+1= wi+hi
wi+hi 表示了累计的未完成的服务时长，一般地有

上述关系是普遍成立的，与服务台设置和服务规则无关
下面分析等待顾客数、等待时间和顾客到达率的关系
到达率定义为单位时间内平均到达的顾客数，即
%26#61548;t= %26#61537;(t) / t
令 %26#61540;(t) 表示在时段(0, t)内到达系统内顾客的总逗留时长
则每一个顾客的平均逗留时间为
Wdt= %26#61540;(t) /%26#61537;(t)
系统中平均逗留顾客数可表达为
Ldt= %26#61540;(t) / t = (%26#61537;(t) / t )(%26#61540;(t) /%26#61537;(t) ) = %26#61548;t Wdt (Little formula)

系统处于稳态时的利特尔公式：Ld= %26#61548; Wd
利特尔公式也是普遍成立的，已知其中任两个量，可以求出另一个量
利特尔公式的分解：
Ld = %26#61548; Wd = %26#61548; (Wq + h ) = Lq + Ln
Lq = %26#61548; Wq Ln = %26#61548; h
Wq 是顾客的平均排队等待时间
Lq 是排队等待的平均队长
h 是顾客的平均服务时长
Ln 是同时接受服务的平均顾客数(即平均服务台占用数)
7.3 服务时间与间隔时间
7.3.1 概述
顾客的服务时间由于多种原因具有不确定性，最好的描述方法就是概率分布；同样顾客到达的间隔时间也具有一定的概率分布
服务时间和到达间隔时间服从什么分布？可以先通过统计得到经验分布，然后再做理论假设和检验
经验分布一般采用直方图来表示，如下图

若统计区间分得越细，样本越多，则经验分布的轮廓越接近曲线
一般服务时间和间隔时间都是非负的连续实变量，令 h 代表服务时间，%26#61556; 代表间隔时间，t 为给定的时间，则它们的概率分布函数分别表示为
F(t)=P{h%26#61603; t} F(t)=P{%26#61556; %26#61603; t}
它们的概率密度函数为 f(t)=F%26#61602;(t)，具有性质：
f(t)%26#61619;0，%26#61682; f(t)dt=1
服务时间落在区间(a, c)的概率为
7.3.2 常用的概率分布
1、定长分布
流水线的加工时间
7.3.2 常用的概率分布
3、爱尔兰分布
一种代表性更广的分布
7.3.3 负指数分布的特点
负指数分布之所以常用，是因为它有很好的特性，使数学分析变得方便
无记忆性。指的是不管一次服务已经过去了多长时间，该次服务所剩的服务时间仍服从原负指数分布
7.3.3 负指数分布的特点
一个服从负指数分布的服务，在下一瞬间结束的概率
7.4 输入过程
即顾客到达的分布，可用相继到达顾客的间隔时间描述，也可以用单位时间内到达的顾客数描述
间隔时间服从定长分布
单位时间内到达的顾客数服从波松分布(法国数学家Poisson, 1837)
间隔时间服从爱尔兰分布
一般独立同分布
7.4.1 波松输入过程及其特点
(0, t)时间内到达 k 个顾客的个数服从波松分布，若
7.4.1 波松输入过程及其特点
(1) 平稳性：顾客到达数只与时间区间长度有关
(2) 无后效性：不相交的时间区间内所到达的顾客数是独立的
(3) 普通性：在 %26#61508;t 时间内到达一个顾客的概率为 %26#61548; %26#61508;t +o(%26#61508;t )，到达两个或两个以上顾客的概率为 o(%26#61508;t )；即两个顾客不可能同时到达
波松过程具有可迭加性
即独立的波松分布变量的和仍为波松分布
7.4.1 波松输入过程及其特点
波松过程的到达间隔时间为负指数分布
令 %26#61556; 代表间隔时间，则概率 P{%26#61556; %26gt; t}代表时间区间(0, t)内没有顾客来的概率；由波松分布可知
P0(t)= P{%26#61556; %26gt; t}=e%26#61485;%26#61548;t
故间隔时间 %26#61556; 的分布为 P{%26#61556; %26#61603; t}=1%26#61485;e%26#61485;%26#61548;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}
例 7.4.2
一售货员出售两种商品A和B，每日工作 8 小时。购买每种商品的顾客到达过程为波松分布，到达率分别为 %26#61548;A=8人/日， %26#61548;B=16人/日，试求：(1) 1小时内来到顾客总数为 3 人的概率；(2) 三个顾客全是购买B类商品的概率。
解：(1)总到达率为 %26#61548;A+ %26#61548;B=24人/日，1 小时=1/8 日，故
7.5 生灭过程
一种描述自然界生灭现象的数学方法，如细菌的繁殖和灭亡，人口的增减，生物种群的灭种现象等
采用马氏链
令 N(t)代表系统在时刻 t 的状态，下一瞬间 t+%26#61508;t 系统的状态只能转移到相邻状态，或维持不变，如图所示
三种转移是不相容的，三者必居其一
只有具有无记忆性和普通性的过程(分布)才适用马氏链
令 Pj(t)=P{N(t)=j}代表系统在时刻 t 处于状态 j 的概率
生灭过程的马氏链
根据马氏链，应用全概率公式，有状态转移概率方程
生灭方程的推导过程
将上述三个差分方程化为微分方程
生灭过程稳态解
方程(1), (2), (3) 与稳态状态转移图一一对应；递归解如下：
满足生灭过程的条件
系统的输入过程和服务过程具有平稳、无记忆性和普通性
服务台是独立的、相同的、并联的
波松输入过程和负指数服务时长就具有这些性质
可以用马氏链来描述系统的状态转移
这种系统称为生灭服务系统，一般用 M/M/n 表示，又称为标准服务系统；
标准服务系统的形式很多，但都是基于生灭方程，关键是找出 %26#61548;j , %26#61549;j 的不同表达式，将它们代入生灭方程
标准服务系统的表示法：(X/Y/Z: A/B/C)，X 表示输入过程，Y 表示服务过程，Z 表示并联服务台的个数，A 表示顾客源，B 表示系统容量，C 表示服务规则
(M/M/n: %26#61605;/m/FIFO) 表示波松输入，负指数服务时长，n 个并联服务台，顾客源无穷，系统容量为 m, m%26#61619;n，先到先服务
D 定长分布；Ek k阶爱尔兰分布；G 一般独立分布
7.6 纯增过程
令生灭过程中所有消亡率 %26#61549;j=0， 即只有顾客到达，没有顾客离去
令所有 %26#61548;j=%26#61548;，且系统服务台无限，即 n%26#61614;%26#61605;
容易得到下列微分方程组