《随机过程与排队论》知识点复习PPT课件.ppt

随机过程与排队论 计算机科学与工程学院顾小丰Email guxf TEL 139800572782020年4月8日星期三 2020 4 8 教学内容 概率论的基本知识随机过程的基本概念随机过程的定义及分类随机过程的分布及数字特征独立过程与独立增量过程泊松过程更新过程 140 2 2020 4 8 教学内容 马尔可夫过程马尔可夫过程的概念离散参数马氏链齐次马氏链状态的分类连续参数马氏链生灭过程 140 3 2020 4 8 教学内容 排队系统概述M M 1 排队M M 排队系统M M c 排队系统M M c K混合制排队系统M M c m m系统及损失制系统有备用品的M M c m K m系统一般服务的M G 1 排队系统 140 4 2020 4 8 一 概率论的基本知识 概率空间及其基本概念 随机试验 样本点 样本空间 随机事件体随机事件 基本事件和可测空间概率 概率空间 概率的性质条件概率 乘法公式 事件的独立性 全概率公式与贝叶斯公式 140 5 2020 4 8 1 条件概率空间 设概率空间 F P A F B F 且P A 0 在事件A已经发生的条件下 事件B发生的条件概率定义为 给定概率空间 F P A F 且P B 0 对任意B F有P B A 对应 则条件概率P B A 是 F 上的概率 记P B A PA 则 F PA 也是一个概率空间 称为条件概率空间 140 6 2020 4 8 2 乘法公式 设概率空间 F P 如果A B F 且P AB 0 则下述乘法公式成立 P AB P A P B A P B P A B 推广 设概率空间 F P 如果Ai F i 1 2 n且P A1A2 An 0 则下述推广的乘法公式成立 P A1A2 An P A1 P A2 A1 P A3 A1A2 P An A1A2 An 1 140 7 2020 4 8 3 全概率公式与贝叶斯公式 设事件组B1 B2 Bn两两互不相容 即BiBj 1 i j n 且 P Bi 0 i 1 2 n 则对任意事件A 有 全概率公式 贝叶斯公式 j 1 2 n 140 8 2020 4 8 4 随机变量及其分布 一 随机变量设 F P 为概率空间 如果定义样本空间 上的一个单值实函数X X 满足 X x F x 则称X 为随机变量 随机变量缩写为r v 二 分布函数设X X 是概率空间 F P 上的随机变量 对任意实数x 定义函数F x P X x x 称为r v X的概率分布函数 简称分布函数 140 9 2020 4 8 5 离散型随机变量及其分布律 若r v X至多只取可列无穷多个数值 x1 x2 xn 令pk P X xk 它满足 1 pk 0 2 1 则称X为离散型随机变量 并称P X xk pk k 1 2 为X的分布律或概率分布 离散型r v X的分布函数 它是左连续单调不减的阶梯函数 在x xk处有第一类跳跃型间断点 其跳跃度为pk 140 10 2020 4 8 6 连续型随机变量 若存在非负可积函数f x 对任意实数x 使得r v X的分布函数满足 则称X为连续型随机变量 称f x 为连续型随机变量的概率密度函数 简称概率密度 140 11 2020 4 8 7 常见的随机变量及其分布 如果r v X的分布律为 则称r v X服从参数为 的泊松分布 记为X 1 泊松 S D Poisson 分布 140 12 2020 4 8 2 负 指数分布 寿命分布 如果r v X的概率密度为 则称r v X服从参数为 的 负 指数分布 寿命分布 X的分布函数为 140 13 2020 4 8 3 正态分布 高斯分布 如果r v X的概率密度为 则称r v X服从参数为 和 2的正态分布 高斯分布 记为X N 2 X的分布函数为 特别地 0 2 1时的正态分布称为标准正态分布 记为r v X N 0 1 其概率密度和分布函数特别记为 140 14 2020 4 8 4 k阶爱尔朗 Erlang 分布 如果r v X的概率密度为 则称r v X服从参数为 0 的k阶爱尔朗分布 记为X Ek 其分布函数为 140 15 2020 4 8 8 二维随机变量 向量 如果X和Y是定义在同一概率空间 F P 上的两个随机变量 则称 X Y 为二维随机变量 向量 记为二维r v X Y 设 X Y 是二维随机变量 定义函数F x y P X x Y y x y 为r v X Y 的二维联合分布函数 140 16 2020 4 8 9 离散型二维随机变量 如果二维若随机变量 X Y 至多只取可列无穷多对数值 xi yj i j 1 2 令pij P X xi Y yj 它满足 1 pij 0 2 1 则称 X Y 为离散型二维随机变量 称pij P X xi Y yj i j 1 2 为 X Y 的联合分布律 称 为 X Y 的联合分布函数 140 17 2020 4 8 边缘分布律 条件分布律 为r v X的边缘分布律 称 为r v Y的边缘分布律 称 为在已知Y yj的条件下 r v X的条件分布律 称 为在已知X xi的条件下 r v Y的条件分布律 如果pij pi p j i j 1 2 则称r v X与Y相互独立 称 140 18 2020 4 8 10 连续型二维随机变量 若存在非负可积函数f x y 使得二维r v X Y 的联合分布函数满足 则称 X Y 为连续型二维随机变量 并称f x y 为连续型二维随机变量的联合概率密度函数 简称联合概率密度 140 19 2020 4 8 11 边缘分布函数 设二维r v X Y 的联合分布函数为F x y FX x F x x 称为r v X的边缘分布函数 FY y F y y 称为r v Y的边缘分布函数 设二维r v X Y 的联合概率密度为f x y x 称为r v X的边缘概率密度函数 y 称为r v Y的边缘概率密度函数 140 20 2020 4 8 12 条件概率密度与条件分布函数 fY X y x f x y fX x x y 称为已知X x的条件下 r v Y的条件概率密度 fX Y x y f x y fY y x y 称为已知Y y的条件下 r v X的条件概率密度 称为已知X x的条件下 r v Y的条件分布函数 称为已知Y y的条件下 r v X的条件分布函数 140 21 2020 4 8 13随机变量的数字特征 1 数学期望 若离散型r v X的分布律为pk P X Xk k 1 2 当时 称 为r v X的数学期望 均值 若连续型r v X的概率密度函数为f x x 当时 称 为r v X的数学期望 均值 140 22 2020 4 8 2 方差 设X是随机变量 若E X E X 2存在 称D X E X E X 2为r v X的方差 或记为Var X 称为r v X的均方差或标准差 事实上有 D X E X E X 2 E X2 2X E X E2 X E X2 E2 X 140 23 2020 4 8 3 常见随机变量的数学期望和方差 泊松分布X E X D X 负 指数分布 E X 1 D X 1 2 正态分布X N 2 E X D X 2 爱尔朗分布X Ek E X k D X k 2 140 24 2020 4 8 3 k阶矩 设r v X有E X k E X E X k 则称 k E Xk 为X的k阶原点矩 称 k E X k 为X的k阶绝对矩 称 k E X E X k为X的k阶中心矩 称 k E X E X k 为X的k阶绝对中心矩 140 25 2020 4 8 4 协方差 若E X E X Y E Y 称cov X Y E X E X Y E Y E XY E X E Y 为随机变量X和Y的协方差 称 为随机变量X和Y的相关系数 称 XY 0为随机变量X和Y不相关 140 26 2020 4 8 5 协方差矩阵 设n维r v X1 X2 Xn 若cij cov Xi Xj E Xi E Xi Xj E Xj i j 1 2 n存在 则称 为n维随机变量 X1 X2 Xn 的协方差矩阵 140 27 2020 4 8 6 特征函数 随机变量X的特征函数定义为 X u E eiuX i 当r v X为离散型随机变量时 当r v X为连续型随机变量时 140 28 2020 4 8 二 随机过程的基本概念 1 随机过程设 F P 是一个概率空间 T是一个参数集 T R X t t T 是T 上的二元函数 如果对于每一个t T X t 是 F P 上的随机变量 则称随机变量族 X t t T 为定义在 F P 上的随机过程 或随机函数 简记为 X t t T 其中t称为参数 T称为参数集 140 29 2020 4 8 2 样本函数与状态空间 随机过程X t 是定义在T 上的二元函数 一方面 当t T固定时 X t 是定义在 上的随机变量 另一方面 当 固定时 X t 是定义在T上的函数 称为随机过程的样本函数 随机过程在时刻t所取的值X t x称为时刻t时随机过程 X t t T 处于状态x 随机过程 X t t T 所有状态构成的集合称为状态空间 记为E 即 E x X t x t T 140 30 2020 4 8 3 随机过程的分类 按状态空间和参数集分类 按概率分布规律分类 独立过程独立增量过程正态过程泊松过程 维纳过程平稳过程马尔可夫过程 140 31 2020 4 8 4 随机过程的分布 设 X t t T 是一个随机过程 对于每一个t T X t 是一个随机变量 它的分布函数F t x P X t x t T x R 称为随机过程 X t t T 的一维分布函数 如果对于每一个t T 随机变量X t 是连续型随机变量 存在非负可积函数f t x 使得 则称f t x t T x R为随机过程 X t t T 的一维概率密度 函数 此时f t x F x t x t T x R 140 32 2020 4 8 二维分布函数 设 X t t T 是一个随机过程 对任意s t T X s X t 是一个二维随机变量 它的联合分布函数F s t x y P X s x X t y t T x R称为随机过程 X t t T 的二维分布函数 140 33 2020 4 8 二维概率密度 如果 X s X t 是连续型二维随机变量 存在非负可积函数f s t x y 使得 成立 则称f s t x y s t T x y R为随机过程 X t t T 的二维概率密度 函数 此时 140 34 2020 4 8 5 随机过程的数字特征 给定随机过程 X t t T 称m t E X t t T为随机过程 X t t T 的均值函数 数学期望 若 X t t T 的状态空间是离散的 则X t t T是离散型随机变量 X t 的概率分布为pk t P X t Xk k 1 2 则 若 X t t T 的状态空间是连续的 则X t t T是连续型随机变量 X t 的一维概率密度为f t x 为 则 140 35 2020 4 8 方差函数 给定随机过程 X t t T 称D t D X t E X t m t 2 t T为随机过程 X t t T 的方差函数 显然 D t E X t m t 2 E X2 t m2 t 称为随机过程 X t t T 的均方差函数 标准方差函数 若X t t T是离散型随机变量 X t 的概率分布为pk t P X t Xk k 1 2 则 若X t t T是连续型随机变量 X t 的一维概率密度为f t x 为 则 140 36 2020 4 8 协方差函数和相关函数 给定随机过程 X t t T 称C s t cov X s X t E X s m s X t m t 为随机过程 X t t T 的协方差函数 显然 C s t E X s X t m s m t C t t D t E X t m t 2 给定随机过程 X t t T 称R s t E X s X t 为随机过程 X t t T 的相关函数 显然 C s t R s t m s m t R s t C s t m s m t 给定随机过程 X t t T 称 为随机过程 X t t T 的相关系数 140 37 2020 4 8 6 重要随机过程 1 独立过程 给定随机过程 X t t T 如果对任意正整数n及任意t1 t2 tn T 随机变量X t1 X t2 X tn 相互独立 则称随机过程 X t t T 为独立过程 特别 如果X n n 1 2 3 是相互独立的随机变量 则称 X n n 1 2 3 为独立随机序列 140 38 2020 4 8 2 独立增量过程 设随机过程 X t t T T 0 如果对任意正整数n 2 t1 t2 tn T且t1 t2 tn 随机过程的增量X t2 X t1 X t3 X t2 X tn X tn 1 是相互独立的随机变量 则称 X t t T 为独立增量过程 140 39 2020 4 8 3 平稳独立增量过程 如果独立增量过程 X t t T T 0 对所有的s t T及h 0 s h t h TX t h X s h 与X t X s 有相同的概率分布 则称 X t t T 为平稳独立增量过程 140 40 2020 4 8 4 正态过程 给定随机过程 X t t T 如果对任意正整数n及t1 t2 tn T n维随机变量X t1 X t2 X tn 的联合概率分布为n维正态分布 则称随机过程 X t t T 为正态过程 或高斯过程 设 X t t T 为正态过程 则其有限维概率分布都是正态分布 140 41 2020 4 8 正态过程的一维概率分布 均值函数方差函数一维概率分布一维概率密度函数一维特征函数 140 42 2020 4 8 正态过程的二维概率分布 均值函数向量二阶协方差矩阵二维概率分布二维概率密度函数二维特征函数 140 43 2020 4 8 5 维纳过程 Brown运动 如果随机过程 W t t 0 满足下列条件 W 0 0 E W t 0 具有平稳独立增量 t 0 W t N 0 2t 0 则称随机过程 W t t 0 是参数为 2的维纳过程 或布朗运动 140 44 2020 4 8 维纳过程的概率分布及数字特征 一维概率密度函数一维特征函数增量分布协方差函数 140 45 2020 4 8 维纳过程的二维概率分布 均值函数向量二阶协方差矩阵二维概率分布二维概率密度函数二维特征函数 140 46 2020 4 8 维纳过程的性质 维纳过程是平稳独立增量过程 维纳过程是正态过程 维纳过程是马尔可夫过程 140 47 2020 4 8 6 泊松过程 如果取非负整数值的计数过程 N t t 0 满足 N 0 0 具有独立增量 对任意0 s t N t N s 服从参数为 t s 泊松分布 则称 N t t 0 为参数 或平均率 强度 为 的 齐次 泊松过程 140 48 2020 4 8 泊松过程的定义2 如果取非负整数值得计数过程 N t t 0 满足下列条件 N 0 0 具有平稳独立增量 P N h 1 h o h P N h 2 o h 则称 N t t 0 为参数 或平均率 强度 为 的 齐次 泊松过程 140 49 2020 4 8 泊松过程的概率分布和数字特征 一维概率分布及均值和方差函数对任意t 0 N t t P N t k 均值函数m t E N t t 方差函数D t D N t t 一维特征函数 140 50 2020 4 8 泊松过程的概率分布和数字特征 二维概率分布 P N s j N t k P N s j N t N s k j t s P N s j P N t s k j 140 51 2020 4 8 泊松过程的概率分布和数字特征 协方差函数和相关函数协方差函数C s t min s t 相关函数R s t min s t 2st 140 52 2020 4 8 泊松过程的性质 泊松过程是平稳独立增量过程 设 N t t 0 是参数为 的泊松过程 Tn n 1 2 为点间间距序列 则Tn n 1 2 是相互独立同分布的随机变量 且都服从参数为 的 负 指数分布 设 N t t 0 是参数为 的泊松过程 n n 1 2 为等待时间序列 则 n n 即概率密度为 即n阶爱而朗分布 140 53 2020 4 8 7 马尔可夫过程 定义1给定随机过程 X t t T 如果对于参数中任意n个时刻ti i 1 2 n t1 t2 tn有 P X tn xn X t1 x1 X t2 x2 X tn 1 xn 1 P X tn xn X tn 1 xn 1 3 1 则称随机过程 X t t T 为马尔可夫过程 简称马氏过程 具有 3 1 式性质称为具有马尔可夫性 无后效性或无记忆性 140 54 2020 4 8 转移概率 定义2给定马氏过程 X t t T 条件概率p s t x y P X t y X s x 称为马氏过程的转移概率 若转移概率与s无关 则此过程称为齐次 时 马氏过程 马氏过程 X t t T 中 X t 的取值x称为状态 X t x表示过程在时刻t处于状态x 过程所取状态的全体E x X t x t T 称为状态空间 140 55 2020 4 8 马尔可夫过程的分类 140 56 2020 4 8 1 离散参数马氏链 设 X n n 0 1 2 为马氏链 E 0 1 2 称条件概率pij m k P X m k j X m i 为马氏链 X n n 0 1 在m时刻的k步转移概率 特别地 k 1时 pij m 1 P X m 1 j X m i 称为一步转移概率 简称转移概率 状态空间E和参数集T都是离散的马尔可夫过程称为离散参数马氏链 简称马氏链 即 140 57 2020 4 8 2 齐次马尔可夫链 若马氏链 X n n 0 1 2 的转移概率pij m k 与m 无关 即pij m k P X m k j X m i pij k pij m 1 P X m 1 j X m i pij 1 pij 则称 X n n 0 1 2 为齐次马尔可夫链 简称齐次马氏链 齐次马氏链的k步转移矩阵记为 P m k P k pij k i j E一步转移矩阵 简称转移矩阵 记为 P m 1 P 1 P pij i j E齐次马氏链的转移概率具有如下性质 0 pij k 1 0 pij 1 140 58 2020 4 8 3 齐次马氏链的性质 齐次马氏链 X n n 0 1 2 的转移概率pij k 满足C K方程 Chapman Kolmogrov 采用矩阵记号为 P k s P k P s 齐次马氏链 X n n 0 1 2 的n步转移矩阵等于一步转移矩阵的n次方 即 P n Pn 绝对分布由初始分布和转移概率确定 且满足 或记为 140 59 2020 4 8 3 齐次马氏链的性质 续 齐次马氏链的有限维分布由初始分布和转移概率确定 且满足 P X n1 i1 X n2 i1 X nk ik 其中P X n1 i1 X n2 i1 X nk ik 为齐次马氏链的k维概率分布 140 60 2020 4 8 3 齐次马氏链的性质 续 设齐次马氏链 X n n 0 1 2 的状态空间 E 1 2 s 为有限 若存在正整数n0 对任意i j E 有pij n0 0 则此马氏链是遍历的 且极限分布是方程组 在满足条件 下的唯一解 140 61 2020 4 8 3 齐次马氏链的性质 续 设齐次马氏链 X n n 0 1 2 具有遍历性 则 即遍历的齐次马氏链的绝对分布与转移概率有相同的极限 遍历的齐次马氏链的极限分布是平稳分布 设 X n n 0 1 2 的平稳分布为 vj j E 则有V VPn n 0 1 2 140 62 2020 4 8 3 齐次马氏链的性质 续 如果齐次马氏链 X n n 0 1 2 的初始分布 pj j E 恰好是平稳分布 则对一切n有pj n pj n 0 1 2 j E即 140 63 2020 4 8 3 齐次马氏链的性质 续 设齐次马氏链 X n n 0 1 2 的状态空间有 限E 1 2 s 若存在正整数n0 对任意i j E n0步转移概率pij n0 0 则此链是遍历的 且极限分布等于平稳分布 140 64 首返概率 平均返回时间 周期 以三个层次区分状态类型 状态 非常返态 常返态 零常返态 正常返态 有周期 非周期 遍历态 4 齐次马氏链状态的分类 2020 4 8 140 65 2020 4 8 5 连续参数马尔可夫链 设随机过程 X t t 0 状态空间E 0 1 2 若对于0 t1 t2 tn tn 1及非负整数i1 i2 in in 1 有P X tn 1 in 1 X t1 i1 X t2 i2 X tn in P X tn 1 in 1 X tn in 即马尔可夫性成立 则称 X t t 0 为连续参数马尔可夫链 140 66 2020 4 8 转移概率函数 设 X t t 0 为连续参数马氏链 对任意i j E 0 1 2 任意非负实数s t 条件概率pij s t P X t s j X s i 称为此马氏链 X t t 0 的转移概率函数 显然 我们称P s t pij s t i j E为此马氏链的转移矩阵 140 67 2020 4 8 连续参数齐次马氏链 若 X t t 0 为连续参数马氏链的转移概率pij s t 与 时间起点s无关 即pij s t P X s t j X s i pij t 则称 X t t 0 为连续参数齐次马氏链 类似地 P t pij t i j E称为此齐次马氏链的转移矩阵 0 pij t 1 140 68 2020 4 8 转移概率函数的性质 0 pij t 1 i j E 连续性条件 pij t 满足C K方程 矩阵形式 P t s P t P s 绝对概率满足 如果齐次马氏链 X t t 0 是遍历马氏链 则 140 69 2020 4 8 转移概率函数的性质 续1 设齐次马氏链 X t t 0 的状态有限 E 0 1 2 s 如果存在t0 0 使得对任意i j E 都有pij t0 0 则此齐次马氏链 X t t 0 为遍历的齐次马氏链 即 存在且与i无关 并且极限分布 j j E 是唯一的平稳分布 对固定的i j 函数pij t 是t 0的一致连续函数 满足连续性条件的连续参数齐次马氏链 X t t 0 存在下列极限 其中qi表示在时刻t时通过状态i的通过速度 或通过强度 qij表示时刻t时从状态i转移到状态j的速度 或强度 qij统称转移速度 140 70 2020 4 8 转移概率函数的性质 续2 设齐次马氏链 X t t 0 状态空间E 0 1 2 s 其转移速度 设 X t t 0 为连续参数齐次马氏链 当qi qi时 满足柯尔莫哥洛夫后退微分方程 即P t QP t 设 X t t 0 为连续参数齐次马氏链 当qi qri时 则有柯尔莫哥洛夫前进微分方程 即P t P t Q 140 71 2020 4 8 转移概率函数的性质 续3 绝对概率满足 福克 普朗克方程 齐次不可约连续参数马氏链 X t t 0 存在极限分布 即为平稳分布 j j E 即 Q 0 零向量 140 72 2020 4 8 8 生灭过程 设 X t t 0 是连续参数齐次马氏链 状态空间E 0 1 2 N 如果它的状态转移速度矩阵为 则称 X t t 0 为生灭过程 140 73 2020 4 8 生灭过程的转移概率 上述生灭过程 X t t 0 的定义可等价地用转移概率pij t 表示为 140 74 2020 4 8 生灭过程满足的柯尔莫哥洛夫方程 柯尔莫哥洛夫后退方程 P t QP t P 0 I 单位阵 柯尔莫哥洛夫前进方程 P t P t Q P 0 I 140 75 2020 4 8 福克 普朗克方程 绝对概率满足福克 普朗克方程 1 推广到无限状态E 0 1 2 n 为 2 140 76 2020 4 8 福克 普朗克方程解的存在性 对有限状态E 0 1 2 N 的生灭过程 若满足pj t 0 则对任给的初始条件 方程组 1 的解存在 唯一 而且 对可列无限状态E 0 1 2 n 的生灭过程 若 而且满足pj t 0 则对任给的初始条件 方程组 2 的解存在 唯一 且 140 77 2020 4 8 极限定理 对有限状态E 0 1 2 N 的生灭过程 j j 0 1 2 N 存在 与初始条件无关 且 即 j j 0 1 N 为平稳分布 对可列无限状态E 0 1 2 n 的生灭过程 若有条件 成立 则 j j 0 1 2 存在 与初始条件无关 且 令 j 0 及 即 j j 0 1 n 为平稳分布 j 0 140 78 2020 4 8 有限状态生灭过程的平稳分布 有限状态E 0 1 2 N 的生灭过程 X t t 0 是遍历的齐次连续参数马氏链 生灭过程存在极限分布即为平稳分布 j j E Q 0即 140 79 2020 4 8 有限状态生灭过程的平稳分布的解 解得生灭过程 X t t 0 E 0 1 2 N 的平稳分布 j j E 为 当 0 1 N 1 1 2 N 时 有 140 80 2020 4 8 无限状态生灭过程的平稳分布 无限状态E 0 1 2 的生灭过程 X t t 0 若满足 是遍历的齐次连续参数马氏链 生灭过程存在极限分布即为平稳分布 j j E Q 0即 及 140 81 2020 4 8 无限状态生灭过程的平稳分布的解 解得生灭过程 X t t 0 E 0 1 2 的平稳分布 j j E 为 特别 当 0 1 2 1 2 3 时 只要 1 则 j j E 存在 且有 140 82 2020 4 8 等待时间 顾客进入系统的时刻起到开始接受服务止这段时间逗留时间 顾客在系统中的等待时间与服务时间之和 三 排队论 队长 系统中的顾客数 包括正在接受服务的顾客 等待队长 系统中的排队等待的顾客数 它们都是随机变量 是顾客和服务机构双方都十分关心的数量指标 应确定它们的分布及有关矩 系统的忙期 从顾客到达空闲的系统 服务立即开始 直到系统再次变为空闲的这段系统连续繁忙的时间系统的闲期 系统连续保持空闲的时间忙期循环 相邻两次忙期开始的时间间隔 输出过程 也称离去过程 指接受服务完毕的顾客相继离开系统的过程 在假定到达与服务是彼此独立的条件下 等待时间与服务时间是相互独立的 它们是顾客最关心的数量指标 应用中关心的是统计平衡下它们的分布及期望值 忙期反映了系统中服务员的工作强度 在排队系统中 统计平衡下忙期与闲期是交替出现的 刻画输出过程的主要指标是相继离去的间隔时间和在一段已知时间内离去顾客的数目 这些指标从一个侧面反映了系统的工作效率 140 83 2020 4 8 1 M M 1 问题的叙述顾客到达为参数 0 的泊松过程 即相继到达的间隔时间序列 n n 1 独立 服从参数为 0 的负指数分布F t 1 e t t 0 顾客所需的服务时间序列 n n 1 独立 服从参数为 0 的负指数分布G t 1 e t t 0 系统中只有一个服务台 容量为无穷大 而且到达过程与服务过程彼此独立 输入过程 服务时间 排队 服务机构 系统容量 140 84 2020 4 8 1 队长 N t t 0 是可列无限状态E 0 1 2 上的生灭过程 其参数为 140 85 2020 4 8 1 队长 续 在统计平衡的条件下 1 平均队长 等待队长的分布 平均等待队长 140 86 2020 4 8 1 队长 续 在等待条件下的等待队长分布 在等待条件下的平均等待队长 根据队长分布易知 p0 1 也是系统空闲的概率 而 正是系统繁忙的概率 显然 越大 系统就越繁忙 140 87 2020 4 8 2 等待时间与逗留时间 假定顾客是先到先服务 定理在统计平衡 1 下 顾客的等待时间分布函数Wq t P Wq t 为Wq t 1 e 1 t t 0 平均等待时间为 等待时间的方差为 140 88 2020 4 8 3 忙期 忙期长度的概率密度 其中 为修正贝塞尔 Bessel 函数 忙期长度的分布函数 140 89 2020 4 8 3 忙期 续 平均忙期长度 一个忙期中所服务的平均顾客数 140 90 2020 4 8 2 具有可变输入率的M M 1 顾客到达为参数 0 的泊松过程 顾客到达看到队长为k时 进入系统的概率为ak 0 ak 1 1 a0 a1 ak 0 k 即排队越长进入的可能性越小 令ak 顾客所需的服务时间序列 n n 1 独立 服从参数为 0 的负指数分布 系统中只有一个服务台 容量为无穷大 而且到达过程与服务过程彼此独立 140 91 2020 4 8 1 队长 我们仍用N t 表示在时刻t系统中的顾客数 令 pij t P N t t j N t i i j 0 1 2 于是 N t t 0 是E 0 1 2 上的生灭过程 其参数为 140 92 2020 4 8 1 队长 续 定理令pj j 0 1 2 则对一切 pj j 0 存在 与初始条件无关 且 构成参数为 的泊松概率分布 140 93 2020 4 8 1 队长 续 在统计平衡的条件下 有 平均队长 平均等待队长 140 94 2020 4 8 2 等待时间与逗留时间 定理在统计平衡下 进入系统接受服务的顾客的等待时间分布函数为 Wq t P Wq t 平均等待时间为 平均逗留时间为 140 95 2020 4 8 3 具有可变服务率的M M 1 顾客到达为参数 0 的泊松过程 顾客所需的服务时间序列 n n 1 独立 服从负指数分布 具有两个服务率 1 2 0 1 2 当队长 m m是一个固定的正整数 时 服务员用速率 1工作 当队长 m时 服务员用速率 2工作 系统中只有一个服务台 容量为无穷大 而且到达过程与服务过程彼此独立 140 96 2020 4 8 1 队长 用N t 表示在时刻t系统中的顾客数 令 pij t P N t t j N t i i j 0 1 2 于是 N t t 0 是E 0 1 2 上的生灭过程 其参数为 140 97 2020 4 8 1 队长 续 令 当 2 1时 pj 0 j 01 2 当 2 1时 pj j 0 存在 与初始条件无关 且 则 140 98 2020 4 8 1 队长 续 在统计平衡的条件下 有 平均队长为 平均等待队长为 140 99 2020 4 8 2 等待时间与逗留时间 在统计平衡下 有pj pj j 0 1 2 顾客在系统中的平均逗留时间为 顾客在系统中的平均等待时间为 由Little公式 顾客在系统中接受的平均服务时间为 140 100 2020 4 8 4 M M 排队系统 顾客到达为参数 0 的泊松过程 顾客所需的服务时间序列 n n 1 独立 服从参数为 0 的负指数分布 系统中有无穷多 足够多 服务台 每个服务台是并行独立进行服务的 140 101 2020 4 8 1 队长 于是 N t t 0 是可列无限状态E 0 1 2 上的生灭过程 其参数为 我们用N t 表示在时刻t系统中的顾客数 140 102 2020 4 8 1 队长 续 令 pj t P N t j pj j 0 则 140 103 2020 4 8 1 队长 续 对于M M 排队系统 因为有足够多的服务台 所以 平均队长 平均等待队长 平均等待时间 逗留时间 服务时间 140 104 2020 4 8 5 M M c 排队系统 顾客到达为参数 0 的泊松过程 顾客所需的服务时间序列 n n 1 独立 服从参数为 0 的负指数分布 系统中有c c 1 个服务台独立并行服务 系统容量为无穷大 而且到达与服务是彼此独立的 140 105 2020 4 8 1 队长 我们用N t 表示在时刻t系统中的顾客数 令 pij t P N t t j N t i i j 0 1 2 于是 N t t 0 是可列无限状态E 0 1 2 上的生灭过程 其参数为 140 106 2020 4 8 1 队长 续 令 c pj P N t j j 0 则当 c 1 有 pj j 0 存在 与初始条件无关 且 证明利用生灭过程的极限定理即得 140 107 2020 4 8 1 队长 续 正在被服务的顾客数Nc 平均等待队长 由于N Nq Nc 所以平均队长为 140 108 2020 4 8 2 等待时间与逗留时间 当 c 1 在统计平衡下 平均等待时间为 平均逗留时间为 140 109 2020 4 8 6 M M c K混合制排队系统 顾客到达为参数 0 的泊松过程 每个顾客所需的服务时间独立 服从参数为 0 的负指数分布 且到达过程与服务过程彼此独立 容量为K 即系统中有K个位置 系统中有c个服务台独立地平行工作 c K 当K个位置已被顾客占用时 新到的顾客就自动离开 当系统中有空位置时 新到的顾客就进入系统排队等待服务 140 110 2020 4 8 1 队长与等待队长 我们用N t 表示在时刻t系统中的顾客数 令 pij t P N t t j N t i i j 0 1 2 于是 N t t 0 是状态空间E 0 1 2 K 上的生灭过程 其参数为 140 111 2020 4 8 1 队长 续 令 pj P N t j j 0 则对 一切 有 pj j 0 存在 与初始条件无关 且 140 112 2020 4 8 1 队长 续 由于M M c K是损失制 损失的概率为 单位时间内平均损失的顾客数为 单位时间内平均进入系统的顾客数为 平均等待队长为 c c 正在被服务的平均顾客数为 平均队长 140 113 2020 4 8 2 等待时间与逗留时间 平均等待时间为 在统计平衡下 进入系统接受服务的顾客的等待时间分布函数为 平均逗留时间为 140 114 2020 4 8 M M 1 K 140 115 2020 4 8 M M c c 爱尔朗公式 顾客损失 c个服务台均忙 的概率 由于不允许排队 所以 140 116 2020 4 8 说明 对于M M c K系统 令K 即为M M c 系统 令c 1 K 即为M M 1 系统 令c 即为M M 系统 140 117 2020 4 8 7 M M c m m系统 问题的叙述c个工人共同看管m m c 台机器 机器运转时会发生故障而停止生产 这时需要工人进行适当的维修 修复后立即投入运转 每台机器的寿命 即连续正常运转时间 均服从参数 0 的负指数分布 即P t e t t 0 m台机器各自独立运转 一旦发生故障 有空闲的工人立即对其进行修理 每个工人对每台发生故障的机器的修理时间 均服从参数为 0 的负指数分布 如果没有空闲的工人 发生故障的机器就等待修理 直到有空闲的工人为止 每台机器的运转相互独立 修理与运转相互独立 每个工人之间的修理也相互独立 140 118 2020 4 8 1 故障的机器数 于是 N t t 0 是有限状态空间E 0 1 2 m 上的生灭过程 而且顾客源是有限的 其参数为 140 119 2020 4 8 1 故障的机器数 续 令pj j 0 1 2 则 pj j 0 1 2 存 在 且 其中 特别地 当c 1时 有 140 120 2020 4 8 1 故障的机器数 续 我们仍然用N和Nq分别表示在统计平衡的条件 下发生故障的机器数和等待修复的机器数 则 平均发生故障的机器数为 平均等待修复的机器数为 平均忙的维修工人数为 140 121 2020 4 8 2 故障机器等待维修的时间分布 假定机器是先故障先维修 定理令Wq表示在统计平衡下 该故障机器的等待修理时间 则分布函数Wq t P Wq t 为 等待修理的平均时间为 140 122 2020 4 8 3 其它重要指标 平均忙的维修工人数为 平均运行的机器数为 统计平衡下单位时间内发生故障的平均机器数为 统计平衡下单位时间内平均修复的机器数为 统计平衡下单位时间内平均修复的机器数等于发生故障的平均数 即 140 123 2020 4 8 8 M M c m m损失制系统 问题的叙述c个工人共同看管m m c 台机器 机器运转时会发生故障而停止生产 这时需要工人进行适当的维修 修复后立即投入运转 每台机器的寿命 即连续正常运转时间 均服从参数 0 的负指数分布 即P t e t t 0 m台机器各自独立运转 一旦发生故障 有空闲的工人立即对其进行修理 每个工人对每台发生故障的机器的修理时间 均服从参数为 0 的负指数分布 当c个维修工人都忙于维修故障的机器时 发生故障的机器不是等待维修 而是立刻送到其它地方去修理 或者停产大修 每台机器的运转相互独立 修理与运转相互独立 每个工人之间的修理也相互独立 如果没有空闲的工人 发生故障的机器就等待修理 直到有空闲的工人为止 140 124 2020 4 8 1 故障的机器数 假定N t 表示在时刻t发生故障的机器数 令 pij t P N t t j N t i i