随机过程与排队论17-18

随机过程与排队论课程部分习题答案第一章1－1 解：因为，,)1()1,()1|(>>=>x p x x p x x p 其中， ⎰∞+--==>1)1(λλλe dx e x p x所以，{=>)1|(x x p )1(0--x e λλ 11>≤x x ，[]λλλ11)1|(1|1)1(+==>=>⎰⎰∞+--∞+∞-dx e x dx x x xp x x E x1－3 解：因为，y dx ye y e y Yf y x f y Y x f y y y y 1)(),()|(0=====⎰--,其中，+∞<<<<y yx 00所以，[]31|2022y dx y x y Y x E y =⋅==⎰1－4解：令，{=Y 210迷宫第一次选择左边，走出分钟徊第一次选择左边，但徘第一次选择右边561,31,21210===p p p令N 为耗子徘徊的时间均值；[]27][65][]|[+====∑N E i Y p i Y N E N E i所以，[]N E ＝21。

平均徘徊21分钟1－8解：Y 的概母函数qZ pZZ P -=1)(所以，[]()p q p P Y E 11)1(2'=-==，222][][][p qY E Y E Y Var =-=1－10 证明：（略）1－11 解：a ）N S 的概母函数为：⎥⎦⎤⎢⎣⎡--==λλqZ p Z P G Z H 1exp ))(()(N S 的均值：p q S E N λ=][，方差，2)1(][p q qS Var N +=λb ）（1）证明：N S 的概率母函数为))1(exp())(exp()(-=-+=Z p Zp q Z H λλλ所以，N S 是均值为p λ的泊松分布。

（2）)()(),(y S P n N P y S n N P n N =⋅==== yn y n q p y n y n e n --⋅-⋅⋅=λλλ)!(!!!)!(!y n y q p e yn y n -=--λλ 得证（3）!)(),()(),()|(y e p yS n N P y S p y S n NP y S n N P py N N N N λλ-⋅=========()y n y n q e yn q ≥-=--,)!(λλ，证毕1－13 解：)()('x F x f =，且[]θλλθθ+==-K e E f x )(*所有, []λθθθKd df x E =⎥⎦⎤⎢⎣⎡-==0*)(1－15解：[]()22*1)(θθθθ---==e e E f x第二章2－2 解：na a a a a a n p qq p p q p q U ⎪⎪⎭⎫⎝⎛-+--=2－5 证明：（略）2－7 证明：（略）2－8 解：)(1t N 时间t 内通过的小车数，)(2t N 时间t 内通过的大车数 a ）950.011)1)((36005.01≈-=-=≥-⨯-e e t N Pb ）[])(67105710)(|)(1辆=+==t N t N Ec ）066.0)5)(45)((12＝，＝=t N t N P2－9解：a ）顾客到达的时间的分布是均匀分布，所以，3/1)20(=p p ＝分钟内到达顾客在开始9/1)202(2=p p ＝分钟内到达个顾客在开始b ）至少有一个顾客在开始20分钟内到达的概率95)1(12=--=p p b2－11解：)1)1(exp())(()(qZ Z Z P G t M --=λ的概母函数：所以，p tP t X tE t M E i λλλ=⋅==)1(][)](['同时， 22)2(][)]([p p q t X tE t M Var +==λλ第三章3－1 解：1）根据定义，此过程为马氏链。

排队论公式推导过程排队论是研究系统随机聚散现象和随机服务系统工作过程的数学理论和方法。

在咱们生活中，排队的现象随处可见，比如在超市结账、银行办业务、餐厅等座位等等。

咱们先来说说排队论中的一些基本概念。

想象一下，你去一家热门的奶茶店买奶茶，顾客就是“输入”，奶茶店的服务员就是“服务台”，制作奶茶的过程就是“服务时间”，而排队等待的队伍就是“队列”。

排队论中的一个重要公式就是 M/M/1 排队模型的平均排队长度公式。

咱们来一步步推导一下。

假设平均到达率为λ，平均服务率为μ。

如果λ < μ，系统是稳定的，也就是队伍不会无限长下去。

首先，咱们来求一下系统中的空闲概率P₀。

因为没有顾客的概率，就等于服务台空闲的概率。

P₀ = 1 - λ/μ接下来，咱们算一下系统中的平均顾客数 L。

L = λ/(μ - λ)那平均排队长度 Lq 怎么算呢？这就要稍微动点脑筋啦。

Lq = λ²/(μ(μ - λ))推导过程是这样的：咱们先考虑一个时间段 t 内新到达的顾客数 N(t)，它服从参数为λt的泊松分布。

在这个时间段内完成服务离开的顾客数 M(t) 服从参数为μt 的泊松分布。

假设在时刻 0 系统为空，经过时间 t 后系统中的顾客数为 n 的概率Pn(t) 满足一个微分方程。

对这个微分方程求解，就能得到上面的那些公式啦。

我记得有一次，我去一家新开的面包店，人特别多，大家都在排队。

我站在那里，心里就琢磨着这排队的情况，不就和咱们学的排队论很像嘛。

我看着前面的人，计算着大概的到达率，再瞅瞅店员的动作，估计着服务率。

那时候我就在想，要是店家能根据这些数据合理安排人手，大家等待的时间就能大大缩短啦。

总之，排队论的公式推导虽然有点复杂，但只要咱们耐心琢磨，就能搞明白其中的道理。

而且这些公式在实际生活中的应用可广泛啦，能帮助我们优化各种服务系统，让大家的生活更加便捷高效！。

随机过程与排队论任课教师:魏静萱副教授wjx@曾勇副教授第一节排队现象例一：电话系统：主叫用户和被叫用户之间提供语音服务，该服务承载于某条通信信道之上，即两个用户c个通道。

地需要一条通道，3个用户需要3个通道，4个用户需要6个通道。

一般的，n个用户需要2n球人口60亿，需要？通道。

海量通信接近天文数字。

解决：信道“公用”导致拥挤排队现象例二：排队现象举例排队系统的三大要素：1. 输入过程 2. 排队规则：队列允许的最大长度 3. 服务窗：顾客是怎样接受服务的1．输入过程：顾客按什么规则进入系统？一个个？成批？到达过程和到达时间间隔符合一定的分布，称到达分布。

假设：到达过程和到达时间是独立同分布的。

到达过程假定为平稳的，对时间是齐次的。

注：Markov 齐次过程 如果一个过程只依赖于现在，而不是过去。

表1 输入过程的三种随机过程描述按顾客到达过程的不同概率特性分类： ① 定长输入（D ）：顾客等间隔到达，nc τ=n τ的分布函数为 1()()0n t c F t P t t cτ≥⎧=≤=⎨<⎩②Poisson 流输入(M): 系统的输入过程{M(t)>0}是Poission 流 满足4个条件：a) M(t)取值为非负数b) P(M(0)=0)=1, 即时间间隔为0时到达系统 的人数为0 c) 过程{M(t)} 具有平稳独立增量性 d) 每一个增量M(a+t)-M(a)非负，且服从参数为tλ的泊松分布(){()()}!k a t P M t a M a k e K λλ-+-==③ k 阶Erlang 输入(Ek)④ 一般独立输入(G)：顾客的到达过程{n τ}是独立同分布的随机变量序列，其分布函数可以是任意函数。

⑤ 成批到达系统：顾客一批批到达系统，每批相继到达的时间间隔为上述各种分布之一。

2．排队与服务规则① 损失制 （无排队队列）：顾客到达时，系统被占用，顾客离去，不再回来。

排队论第⼀节引⾔⼀、排队系统的特征及排队论排队论（queueing theory）是研究排队系统（⼜称为随机服务系统）的数学理论和⽅法，是运筹学的⼀个重要分⽀。

在⽇常⽣活中，⼈们会遇到各种各样的排队问题。

如进餐馆就餐，到图书馆借书，在车站等车，去医院看病，去售票处购票，上⼯具房领物品等等。

在这些问题中，餐馆的服务员与顾客、公共汽车与乘客、图书馆的出纳员与借阅者、医⽣与病⼈、售票员与买票⼈、管理员与⼯⼈等，均分别构成⼀个排队系统或服务系统（见表10-1）。

排队问题的表现形式往往是拥挤现象，随着⽣产与服务的⽇益社会化，由排队引起的拥挤现象会愈来愈普遍。

表排队除了是有形的队列外，还可以是⽆形的队列。

如⼏个顾客打电话到出租汽车站要求派车，如果出租汽车站⽆⾜够车辆，则部分顾客只得在各⾃的要车处等待，他们分散在不同地⽅，却形成了⼀个⽆形队列在等待派车。

排队的可以是⼈，也可以是物。

如⽣产线上的原材料或半成品在等待加⼯；因故障⽽停⽌运转的机器在等待修理；码头上的船只等待装货或卸货；要降落的飞机因跑道被占⽤⽽在空中盘旋等等。

当然，提供服务的也可以是⼈，也可以是跑道、⾃动售货机、公共汽车等。

为了⼀致起见，下⾯将要求得到服务的对象统称为“顾客”，将提供服务的服务者称为“服务员”或“服务机构”。

因此，顾客与服务机构（服务员）的含义完全是⼴义的，可根据具体问题⽽不同。

实际的排队系统可以千差万别，但都可以⼀般地描述如下：顾客为了得到某种服务⽽到达系统，若不能⽴即获得服务⽽⼜允许排队等待，则加⼊等待队伍，待获得服务后离开系统，见图10-1⾄图10-4。

类似地还可画出许多其他形式的排队系统，如串并混联的系统，⽹络排队系统等。

尽管各种排队系统的具体形式不同，但都可由图10-5加以描述。

图10-1 单服务台排队系统图10-2 s 个服务台，⼀个队列的排队系统图10-3 s 个服务台，s 个队列的排队系统图10-4 多个服务台得串联排队系统顾客到达顾客到达图10-5 随机服务系统通常称由10-5表⽰的系统为⼀个随机聚散服务系统，任⼀排队系统都是⼀个随机聚散服务系统。

第9章 排队论排队论是我们每个人都很熟悉的现象。

因为人或物或是信息为了得到某种服务必须排队。

有一类排队是有形的，例如在售票处等待买票的排队，加油站前汽车等待加油的排队等；还有一类排队是无形的，例如电话交换机接到的电话呼叫信号的排队，等待计算机中心处理机处理的信息的排队等。

为了叙述的方便，排队者无论是人、物、或信息，以后统称为“顾客”。

服务者无论是人，或事物，例如一台电子计算机也可以是排队系统中的服务者，我们以后统称为“服务员”。

排队现象是我们不希望出现的现象，因为人的排队意味着至少是浪费时间；物的排队则说明了物资的积压。

但是排队现象却无法完全消失，这是一种随即现象。

由于顾客到达间隔时间的随机性和为顾客服务时间的随机性是排队现象产生的原因。

如果上述的两个时间是固定的，我们就可以通过妥善安排来完全消除排队现象。

排队论是研究排队系统在不同的条件下（最主要的是顾客到达的随机规律和服务时间的随机规律）产生的排队现象的随机规律性。

也就是要建立反映这种随机性的数学模型。

研究的最终目的是为了运用这些规律，对实际的排队系统的设计与运行做出最优的决策。

排队论中的数学模型是根据概率和随机过程的理论建立起来的，我们先来讨论泊松过程和生灭过程，然后,再此基础上研究排队系统的结构及其主要的数学模型，最后研究排队系统的优化问题。

9.1泊松过程和生灭过程9.1.1 泊松过程如果用表示在[0时间内顾客到达的总数，则对于每个给定的时刻，都是一个随机变量。

随即变量族()N t ,]t t ()N t {(称作是一个随机过程。

)[0,]}N t t T ∈若对，有12n n t t t t +<<<"1111122(()(),(),,()n n n P N N N N t i t i t i t ++==="n i =11(()())n n n P N N t i t ++==n i = (9-1)则称随即过程{(为马尔柯夫过程。

目录前言 (1)第一章概率与随机变量 (2)1、随机事件及其概率 (2)2、随机变量及分布函数 (3)3、数字特征 (4)4、特征函数 (5)第二章随机过程概述 (6)1、随机过程的概念 (6)2、平稳随机过程 (7)3、平稳随机过程的各态历经性 (8)4、平稳过程的功率谱密度 (9)第三章随机过程的线性变换 (10)1、随机过程变换的基本概念 (10)2、均方微积分 (10)3、随机过程线性变换的微分方程法 (13)4、随机过程的冲激响应法和频谱法 (14)第四章窄带随机过程 (15)1、窄带随机过程的基本概念 (15)2、窄带平稳随机过程的数字特征 (16)第五章高斯随机过程 (18)1、高斯随机过程 (18)2、窄带平稳实高斯随机过程 (18)第六章泊松随机过程 (20)1、泊松计数过程 (20)2、泊松过程的基本概念 (21)第七章总结 (24)前言随机过程(Stochastic Process)是一连串随机事件动态关系的定量描述。

数学上的随机过程可以简单的定义为一组随机变量，即指定一参数集，对于其中每一参数点t指定一个随机变量x(t)。

如果回忆起随机变量自身就是一个函数，以ω表示随机变量x(t)的定义域中的一点，并以x(t，ω)表示随机变量在ω的值，则随机过程就由刚才定义的点偶(t，ω)的函数以及概率的分配完全确定。

如果固定t，这个二元函数就定义一个ω的函数，即以x(t)表示的随机变量。

如果固定ω，这个二元函数就定义一个t的函数，这是过程的样本函数。

随机过程论与其他数学分支如位势论、微分方程、力学及复变函数论等有密切的联系，是在自然科学、工程科学及社会科学各领域研究随机现象的重要工具。

随机过程论目前已得到广泛的应用，在诸如天气预报、统计物理、天体物理、运筹决策、经济数学、安全科学、人口理论、可靠性及计算机科学等很多领域都要经常用到随机过程的理论来建立数学模型。

随机过程整个学科的理论基础是由柯尔莫哥洛夫和杜布奠定的。

在我们的日常生活中，常常遇到资源有限而需要按一定规则排队的情况，例如到超市购物付款，买火车票，数据的传输，电路交换等等，资源的有限性以及服务的随机性是排队现象存在的基础，研究这一类问题具有普遍意义。

数学中，通过随机过程分析来研究排队问题的方法论称为排队论，本文就是利用数学的随机过程理论来分析排队问题，讲述最基本的排队模型，标准的M/M/1 模型，分析代表其系统运行情况的指标。

排队系统一般来说是由等待资源的顾客和提供服务的服务员构成，由于顾客的到达与服务完毕的时间是不确定的，所以排队系统存在随机性。

为了既能保证服务质量又不浪费服务资源，人们在随机过程的基础上发展起来了一种数学方法—排队论。

任何排队系统都有三个基本参数，服务员的数目也称窗口数m ，顾客的到达速率λ，系统的服务速率μ。

除此之外，为了很好的描述系统的运行状态，还要研究顾客到达的时间间隔ti ，以及服务时间τi 的统计分布和排队规则。

最常用的方法也是比较合适的方法是认为它们服从指数分布，因为指数分布具有无记忆性，与现实中的一大类情况相似，并且使得排队过程称为马尔可夫过程。

所以要对排列规则做如下的假设：平稳性：到达k 个顾客的概率只和顾客到达的时间间隔t 有关，与起始时刻无关。

无后效性：顾客到达的时刻无相独立疏稀性：在无限小的时间间隔内，到达两个及以上顾客的概率为0，且在有限时间区间内到达的顾客数是有限的。

上面说做的假设，可以保证顾客到达的时间间隔t 为指数分布的随机变量，在现实生活中的排队系统里上述假设也是成立或者近似成立的。

t 的概率密度函数为 a(t)= λe −λt 式中的λ是顾客的到达率。

可以证明在T 时间间隔内，有k 个顾客到达的概率符合泊松分布：P k (T)=(λT)kk ! e −λT由于已经说明两个顾客服务所需的时间是互不相关的，平稳的，疏稀的，则服务时间τ的分布也服从指数分布b(τ)= μe −μτ类似的，在T 时间内，有k 个顾客被服务后离去的概率为Q k (T)=(μT)k k!e −μT 有了这些基础后，下面开始介绍一种基本的排队模型。

实用排队论排队论又称随机服务系统，它应用于一切服务系统，包括生产管理系统、通信系统、交通系统、计算机存储系统。

它通过建立一些数学模型，以对随机发生的需求提供服务的系统预测。

现实生活中如排队买票、病人排队就诊、轮船进港、高速路上汽车通过收费站、机器等待修理等等。

一、排队论的基本构成（1）输入过程输入过程是描述顾客是按照怎样的规律到达排队系统的。

包括①顾客总体：顾客的来源是有限的还是无限的。

②到达的类型：顾客到达是单个到达还是成批到达。

③相继顾客到达的时间间隔：通常假定是相互独立同分布，有的是等间隔到达，有的是服从负指数分布，有的是服从k 阶Erlang 分布。

（2）排队规则排队规则指顾客按怎样的规定的次序接受服务。

常见的有等待制，损失制，混合制，闭合制。

当一个顾客到达时所有服务台都不空闲，则此顾客排队等待直到得到服务后离开，称为等待制。

在等待制中，可以采用先到先服务，如排队买票；也有后到先服务，如天气预报；也有随机服务，如电话服务；也有有优先权的服务，如危重病人可优先看病。

当一个顾客到来时，所有服务台都不空闲，则该顾客立即离开不等待，称为损失制。

顾客排队等候的人数是有限长的，称为混合制度。

当顾客对象和服务对象相同且固定时是闭合制。

如几名维修工人固定维修某个工厂的机器就属于闭合制。

(3)服务机构服务机构主要包括：服务台的数量；服务时间服从的分布。

常见的有定长分布、负指数分布、几何分布等。

二、排队系统的数量指标(1)队长与等待队长队长（通常记为s L ）是指系统中的平均顾客数（包括正在接受服务的顾客）。

等待队长（通常记为q L ）指系统中处于等待的顾客的数量。

显然，队长等于等待队长加上正在服务的顾客数。

(2)等待时间等待时间包括顾客的平均逗留时间（通常记为s W ）和平均等待时间（通常记为q W ）。

顾客的平均逗留时间是指顾客进入系统到离开系统这段时间，包括等待时间和接受服务的时间。

顾客的平均等待时间是指顾客进入系统到接受服务这段时间。