排队论(讲义)

排队论QueueingTheory主讲：周在莹排队论课件2CONTENTSPREPARATION:概率论与随机过程UNIT1排队模型UNIT2排队网络模型UNIT3应用之：QUICKPASS系统结束语排队论课件3PREPARATION概率论和随机过程Part1．概率论基础1。概率的定义概率关系着对时间的数量分配。一个事件A的概率P(A)是对应事件A要发生可能性的数量分配。概率有很多不同的定义，常用的有三种：(1)古典定义：P(A)=NA/N其中N是可能结果的总个数，NA是事件A在其中发生的结果的个数。例1.求抛两个骰子并且决定和为7的概率p。总共有36种可能的结果，所以N=36有6种结果(1,6),(2,5),(3,4),(4,3),(5,2)和(6,1)为所求。所以NA=6，从而p=6/36=1/6。排队论课件4(2)相对频率定义：P(A)=limnA/nn→∞其中n是实验的次数，nA是A发生的次数例2投硬币在大数量投掷后，硬币的正面在上的可能性在0.5左右，上下两面在上面具有相同的概率。(3)公理化定义：从一定数量的定义概率度量的公理出发，经过推导规则达到概率的有效计算。这些公理包括：（a）对于每一个事件A，有0≤P（A）≤1（b）P（Ω）=1（c）如果A和B是互斥的，则P（AUB）=P（A）+P（B）排队论课件52条件概率和独立性条件概率：假定事件B已经发生时，事件A发生的条件概率P(A|B)可以定义如下：P（A|B）=P（AB）/P（B）独立性：如果P(AB)=P(A)P(B)，事件A和B叫做相互独立的事件独立性的概念可以推广到三个或多个事件。排队论课件63全概率公式和贝叶斯定理全概率公式：给定一组互斥事件E1，E2，，…，En，这些事件的并集包括所有可能的结果，同时给任一个任意事件A，那么全概率公式可以表示为：nP(A)=∑P(A|Ei)P(Ei)i=1把计算A的概率分解为一些容易计算的概率之和。贝叶斯定理：P(Ei|A)=P(A|Ei)P(Ei)∑P(A|Ei)P(Ei)也称为后验概率公式，是在已知结果发生的情况下，求导致结果的某种原因的可能性的大小。排队论课件7Part2.随机变量的数字特征随机变量X是样本点的函数，它的定义域是样本空间Ω，值域是实数集R，即X：Ω→R随机变量的数字特征对研究随机变量是很重要的，常用的数字特征有：数学期望、方差、协方差和相关系数。1数学期望：连续情况：E[X]=μx=∫xf(x)dx积分区间从[-∞，∞]离散情况：E[X]=μx=∑kP{x=k}allk它是一种统计平均值，简称均值2方差：D[X]=E[(X-μx)2]=E[X2]-μx2它是度量随机变量X与其均值E[X]的偏离程度。均方差：方差的开方称为均方差，或标准方差，记为σx二阶矩：连续情况：E[X2]=∫x2f(x)dx积分区间从[-∞，∞]离散情况：E[X2]=∑k2P{x=k}allk排队论课件83协方差：两个随机变量X和Y的协方差定义如下：Cov(X,Y)=E[(X-μx)(Y-μy)]=E[XY]-E[X]E[Y]4相关系数:两个随机变量X和Y的相关系数定义如下：r(X,Y)=Cov(X,Y)/σxσy相关系数是两个随机变量线性相关程度的度量。例3：设随机变量（X，Y）的分布律如下：YX121¼½-101/4求E(X),D(X),E(Y),D(Y),cov(X,Y),r(X,Y)排队论课件9Part3几种重要的概率分布1贝努里分布它的概率分布为：P{X=1}=p，P{X=0}=1-p它也称两点分布或（0-1）分布。它描述一次贝努里实验中，成功或失败的概率。2二项分布P{X=k}=Cnkpk(1-p)n-k,k=0,1,…,n它描述n次贝努里实验中事件A出现k次概率。3几何分布P{X=k}=p(1-p)k-1,k=1,2,…它描述在k次贝努里实验中首次出现成功的概率。排队论课件10几何分布有一个重要的性质-----后无效性：在前n次实验未出现成功的条件下，再经过m次实验（即在n+m次实验中）首次出现成功的概率，等于恰好需要进行m次实验出现首次成功的无条件概率。用式子表达：P{X=n+m|Xn}=P{X=m}(请同学们试证明之）这种与过去历史无关的性质称为马尔可夫性。几何分布在我们下面讲的排队论中是非常重要。它可以描述某一任务（或顾客）的服务持续时间。4泊松分布（Poisson）P{X=k}=λke-λ/k!k=0,1,2,…泊松分布是最重要的离散型概率分布之一，它作为表述随机现象的一种形式，在计算机性能评价等实践中扮演了重要的角色。在实际系统模型中，一般都要假定任务（或顾客）的到来是服从泊松分布的。实践也证明：这种假设是有效的。排队论课件115（负）指数分布它是一种连续型的概率分布，它的概率密度为f（x）=λe-λxx≥00x0分布函数：F（x）=1-e-λxx≥0指数分布的一个有用的性质是它的数学期望等于标准差：μx=σx=1/λ在连续型随机变量中，只有指数分布具有无后效性。即：若随机变量ζ服从指数分布，对任意的s0,t0，有P{ζs+t|ζs}=P{ζt}在离散型随机变量中，只有几何分布具有无后效性。这两种分布可以分别用来描绘离散等待时间和连续等待时间。在排队理论中，指数分布是很重要的。排队论课件126k-爱尔朗分布概率密度:f(x)=(λkx)n-1λke-λkx/(n-1)!x≥0，λ0.0x0数字特征：E[X]=1/λ;Var[X]=1/（kλ2）如果k个随机变量Xi，i=1，2，…,k,分别服从指数分布，那么随机变量X=X1+X2+…+Xk服从爱尔朗分布。即：具有k-爱尔朗分布的随机变量可以看作具有同一指数分布的独立的k个随机变量之和。k-爱尔朗分布在排队模型中，得到广泛应用。如：假定顾客在到达窗口排队必须通过一个关口，这个关口由k层构成，通过每层的时间服从参数为λ的指数分布，这样顾客通过整个关口到达窗口排队时，就实现了爱尔朗分布。如下图：k…2100…00窗口排队论课件13Part4随机过程随机过程是定义在给定的概率空间上的一族随机变量{X(t)，t∈T}。我们知道：一个随机变量是定义在样本空间S上的函数，则随机过程实际上就是一个函数族{X（t，s）|s∈S，t∈T}。若t固定，随机过程X（t，s）就是随机变量X（t）所取的值，称为在t时刻的状态。若s固定，它是t的函数，称为随机过程的样本函数或样本曲线。排队论课件14随机过程的例子为了更好的理解随机过程，我们从一个例子开始。例如，n个同样的电阻，同时记录它们热噪声的电压波形。电阻上的热噪声是由于电阻中的电子的热运动引起的，因此，在t1时刻电阻上的热噪声电压是一个随机变量，并记为x(t1)，也就是说t1时刻任一电阻r(i)上的噪声电压x(i,t1)是无法预先确切地知道的。这里n支电阻的热噪声电压的集合是这个随机实验的样本空间S。对于某一支电阻，其热噪声电压是一时间函数x(i，t)，是随机过程的样本函数。对所有电阻来说，其热噪声电压就是一族时间函数，记为x(t)，这族时间函数就是“随机过程”，族中每一时间函数称为随机过程的样本函数。排队论课件15Part5马尔可夫过程马尔可夫过程(MarkovProcess)是具有无后效性的随机过程。无后效性是指：当过程在tn时刻所处的状态为已知时，过程在大于tn的时刻所处状态的概率特性只与过程在tn时刻所处的状态有关，而与过程在tn时刻以前的状态无关。换言之，对于随机过程{X（t），t∈T}，如果对于任意参数t0t1t2…tnt,在X(t0),X(t1),…X(tn)的值已知的情况下，X(t)的条件分布只与X(tn)的状态有关，即：P{X(t)≤x|X(tn)=xn,X(tn-1)=xn-1,…,X(t0)=x0}=P{X(t)≤x|X(tn)=xn}此条件称为过程的无后效性或过程的马尔可夫性。t0t1tn-1tnt排队论课件16Part6生灭过程生灭过程是一种特殊类型的马尔可夫过程，在系统性能评价等实际模型中是非常重要的。（1）离散时间生灭过程对于离散时间生灭过程，所有的一步转移只发生在相邻的状态之间。转移概率矩阵P是一个夹层的矩阵，其中，对于所有的|i-j|1有pij=0(2)连续时间生灭过程一个连续时间，状态空间S={0，1，2…}为可数集的齐次马尔可夫过程{X(t)，t≥0}，,称为生灭过程。时齐性转移概率Pij(t,τ)只与i,j,τ-t有关，即Pij(τ)=Pij(t,t+τ)排队论课件17练习练习：1。有10个电阻，其电阻值分别为1Ω，2Ω，…，10Ω，从中取出三个，要求取出的三个电阻，一个小于5Ω，一个等于5Ω，另一个大于5，Ω，问：取一次就能达到要求的概率。2．一袋内装有5只球，编号为1，2，3，4，5，从中任取3只，求被抽取3只球中，中间号码X的分布规律。排队论课件18习题解答1．把从10个电阻中取出3个的各种可能取法作为样本点全体，这是古典概率，其总数为C（10，3），有利场合为C（4，1）C（1，1）C（5，1）故，所求概率为：P=C（4，1）C（1，1）C（5，1）/C（10，3）=1/62．依题意，X的可能值为2，3，4，当取中间号码为k时，则另外两只球必须分别在号码小于k的k-1个中取一个，和在号码大于k的5-k个中取一个，于是：pk=P{X=k}=C(k-1,1)C(5-k,1)/C(5,3),k=2,3,4所以，X的分布律为：X234Pk0.30.40.3♂排队论课件19UNIT1排队模型排队论（queueingtheory），或称随机服务系统理论，作为运筹学研究的一种有力手段，研究的内容有3个方面：系统的性态，即与排队有关的数量指标的概率规律性；系统的优化问题；统计推断，根据资料合理建立模型。目的是正确设计和有效运行各个服务系统，使之发挥最佳效益。排队论不仅在理论上达到了成熟阶段，而且其应用范围不断增加。概括起来，它已在电话交换网、公路、铁路、航空运输、工程管理、公共服务、货物存储和生产流水线过程等方面得到了广泛的应用。特别地，排队论是计算机通信网络和计算机系统中通信信息量研究的基础理论，信息系统通信问题的定量研究往往要求借助于排对论才能得到解决。排队论课件20排队常常是件很令人恼火的事情……尤其是在我们这样的人口大国电话亭－1978年在北京15%的电话要在1小时后才能接通。在电报大楼打电话的人还要带着午饭去排队银行窗口，ATM游乐场的游乐项目医院、理发、火车售票…在现实生活中，为了接受某种服务，排队等待是常见的现象。从排队等待得到抽象的物理模型，进一步建立数学模型的一整套理论就是所谓的排队论。排队论课件21什么是排队论？排队论是专门研究带有随机因素，产生拥挤现象的优化理论。亦称为随机服务系统理论。因为被服务者到达系统的时间是不确定的。有关于由服务设施与被服务者构成的排队服务系统的理论。排队论课件22本讲主要掌握：基本模型M/M/1模型M/M/c模型其他模型应用：校园网的设计和调节收费♂※排队论课件23基本的排队模型基本组成概念与记号指数分布和生灭过程♂排队论课件24典型排队系统模型顾客到达:在队列中排队服务台服务顾客离开输入源的到达规律队列大小？特性？到达方式？服务规律？服务协议？在本单元中，我们主要介绍排队系统的组成和特征，排队系统的到达和服务，经典排队模型等内容。顾客到达规律和服务规律都是通过概率来描述的，所以概率论是排队论的基础。输入源。。。排队论课件25基本组成输入来源队列服务机构排队系统顾客服务完离开排队系统的三个基本组成部分.•输入过程(顾客按照怎样的规律到达);•排队规则(顾客按照一定规则排队等待服务);•服务机构(服务机构的设置,服务台的数量,服务的方式,服务时间分布等)♂排队论课件26基本排队模型－输入过程顾客来源有限/无限顾客数量有限无限经常性的顾客来源顾客到达间隔时间:到下一个顾客到达的时间.服从某一概率分布.