随机过程与排队论17-18讲述.ppt

随机过程与排队论 计算机科学与工程学院 顾小丰 Email：guxf@uestc.edu.cn 2017年4月10日星期一 2017-4-10 计算机科学与工程学院　顾小丰 上一讲内容回顾 M/M/c/m/m损失制系统 问题的引入 队长——故障的机器数 有备用品的M/M/c/m+K/m系统 问题的引入 故障的机器数 二阶段循环排队系统 问题的引入 Ⅰ号台的队长 车辆在Ⅰ号台的等待时间 60－2 2017-4-10 计算机科学与工程学院　顾小丰 本讲主要内容 一般服务的M/G/1/?排队系统 嵌入马尔可夫链 对长 等待时间与逗留时间 忙期 输出过程 60－3 2017-4-10 计算机科学与工程学院　顾小丰 第七章 一般服务的M/G/1/?排队系统 前面内容着重讨论了按泊松流到达与负指数服务时间的简单排队系统，它的主要特点是在任何时刻系统都具有较好的马尔可夫性，能比较容易地得到队长分布的平稳解，因此部分内容相对讲可以看作是初等的。 对于一般服务或一般到达的排队系统，并不是任何时刻系统都具有马尔可夫性，只是在某些特殊的随机时刻系统才具有这种性质，我们称这种随机时刻为再生点，即从这个时刻起，系统好像又重新开始一样。利用再生点，一般服务或一般到达的排队系统可化成马尔可夫链，用马尔可夫链的方法来解决，这种方法叫做嵌入马尔可夫链法。此方法的精髓在于找到再生点。 60－4 2017-4-10 计算机科学与工程学院　顾小丰 §7.1 嵌入马尔可夫链 M/G/1/?排队系统的叙述 顾客按参数?(?＞0)的泊松流到达，即相继到达的间隔时间序列{?n，n≥1}独立、服从参数为?(?＞0)的负指数分布F(t)＝1-e-?t，t≥0； 顾客所需的服务时间序列{?i，i≥1}独立、同一般分布G(t)，t≥0，记平均服务时间为 ； 系统中只有一个服务台，容量为无穷大； 顾客到达时，若服务台空闲就立即接受服务，否则就排队等待，并按先到先服务的顺序接受服务，而且到达过程与服务过程彼此独立。 60－5 2017-4-10 计算机科学与工程学院　顾小丰 2.嵌入马尔可夫链 假定N(t)表示在时刻t系统中的顾客数(队长)，对于M/G/1/? 排队系统，由于服务时间是一般分布，对任选的一个时刻t正在接受服务的顾客可能还没有服务完。从时刻t起的剩余服务时间分布可能不具有无记忆性，于是队长{N(t)，t≥0}不再具有马尔可夫性。但是，若令Nn+表示第n个顾客服务完毕离开时留在系统中的顾客数，即留下的队长，n≥1，则下面定理表明{Nn+，n≥1}是马尔可夫链，被称为队长过程{N(t)，t?0}的嵌入马尔可夫链。 60－6 2017-4-10 计算机科学与工程学院　顾小丰 定理 {Nn+，n≥1}为一不可约、非周期的齐次马尔 可夫链，其一步转移概率为 60－7 2017-4-10 计算机科学与工程学院　顾小丰 证明 设vn表示在第n个顾客的服务时间?n内到达的顾客数，则容易看出{vn，n≥1}相互独立同分布 而且 由于{vn，n≥1}相互独立同分布，所以令vn ＝v ，n≥1，有 60－8 2017-4-10 计算机科学与工程学院　顾小丰 证明(续1) 其一步转移概率为： 当i≥1时， 从上式可以看出，当已知Nn+时， Nn+1+只与到达过程有关，而与N1+, N2+,…, Nn-1+无关，所以是马尔可夫链，其状态空间E＝{0,1,2,…}。 60－9 2017-4-10 计算机科学与工程学院　顾小丰 证明(续2) 当i＝0时， 从一步转移概率表达式容易看出，pij，i,j=0,1,2,…与时间的起点无关，而且任意两个状态是互通的，pii＞0， {Nn+，n≥1}为一不可约、非周期的齐次马尔可夫链。 60－10 2017-4-10 计算机科学与工程学院　顾小丰 Vn的均值 vn表示在第n个顾客的服务时间?n内到达的顾客数，vn分布函数为 Vn均值为 60－11 2017-4-10 计算机科学与工程学院　顾小丰 Vn的二阶矩 Vn的二阶矩为 60－12 2017-4-10 计算机科学与工程学院　顾小丰 Vn的方差 Vn的方差为 60－13 2017-4-10 计算机科学与工程学院　顾小丰 一步转移概率 嵌入马尔可夫链{Nn+，n≥1}的一步转移概率矩 其中： 阵为： 60－14 2017-4-10 计算机科学与工程学院　顾小丰 引理 对于不可约非周期的马尔可夫链，令{pij，i,j = 0,1,2,…}为一步转移概率，若不等式组 存在一个满足条件 的非负解，则此马尔可夫链是正常返的。 60－15 2017-4-10 计算机科学与工程学院　顾小丰 定理 嵌入马尔可夫链{Nn+，n≥1}为正常返 的充分必要