排队论(讲义).ppt
《排队论(讲义).ppt》由会员分享,可在线阅读,更多相关《排队论(讲义).ppt(125页珍藏版)》请在咨信网上搜索。
1、排队论排队论Queueing TheoryQueueing Theory主讲:周在莹主讲:周在莹1.CONTENTSPREPARATION:概率论与随机过程概率论与随机过程UNIT1排队模型排队模型UNIT2排队网络模型排队网络模型UNIT3应用之:应用之:QUICKPASS系统系统结束语结束语2.PREPARATION概率论和随机过程概率论和随机过程Part1概率论基础概率论基础1。概率的定义概率的定义概概率率关关系系着着对对时时间间的的数数量量分分配配。一一个个事事件件A的的概概率率P(A)是是对对应应事事件件A要要发发生生可可能能性性的的数数量量分分配配。概概率率有有很多不同的定义,常用
2、的有三种:很多不同的定义,常用的有三种:(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。3.(2)相对频率定义相对频率定义:P(A)=limnA/nn其中其中n是实验的次数,是实验的次数,nA是是A发生的次
3、数发生的次数例例2投硬币投硬币在在大大数数量量投投掷掷后后,硬硬币币的的正正面面在在上上的的可可能能性性在在0.5左左右右,上上下下两面在上面具有相同的概率。两面在上面具有相同的概率。(3)公公理理化化定定义义:从从一一定定数数量量的的定定义义概概率率度度量量的的公公理理出出发发,经经过过推导规则达到概率的有效计算。这些公理包括:推导规则达到概率的有效计算。这些公理包括:(a)对于每一个事件对于每一个事件A,有,有0P(A)1(b)P()=1(c)如果如果A和和B是互斥的,则是互斥的,则P(AUB)=P(A)+P(B)4.2条件概率和独立性条件概率和独立性条件概率:条件概率:假假定定事事件件B
4、已已经经发发生生时时,事事件件A发发生生的的条条件件概概率率P(A|B)可以定义如下:可以定义如下:P(A|B)=P(AB)/P(B)独立性:独立性:如果如果P(AB)=P(A)P(B),事件,事件A和和B叫做相互独立的事件叫做相互独立的事件独立性的概念可以推广到三个或多个事件。独立性的概念可以推广到三个或多个事件。5.3全概率公式和贝叶斯定理全概率公式和贝叶斯定理全全概概率率公公式式:给给定定一一组组互互斥斥事事件件E1,E2,En,这这些些事事件件的的并并集集包包括括所所有有可可能能的的结结果果,同同时时给给任任一一个个任任意事件意事件A,那么全概率公式可以表示为:,那么全概率公式可以表示
5、为:n P(A)=P(A|Ei)P(Ei)i=1把计算把计算A的概率分解为一些容易计算的概率之和。的概率分解为一些容易计算的概率之和。贝叶斯定理:贝叶斯定理:P(Ei|A)=P(A|Ei)P(Ei)P(A|Ei)P(Ei)也称为后验概率公式,是在已知结果发生的情况下,求导也称为后验概率公式,是在已知结果发生的情况下,求导致结果的某种原因的可能性的大小。致结果的某种原因的可能性的大小。6.Part2.随机变量的数字特征随机变量的数字特征随随机机变变量量X是是样样本本点点的的函函数数,它它的的定定义义域域是是样样本本空空间间,值值域域是实数集是实数集R,即,即X:R随随机机变变量量的的数数字字特特
6、征征对对研研究究随随机机变变量量是是很很重重要要的的,常常用用的的数数字字特征有:数学期望、方差、协方差和相关系数。特征有:数学期望、方差、协方差和相关系数。1数学期望数学期望:连续情况:连续情况:EX=x=xf(x)dx积分区间从积分区间从-,离散情况:离散情况:EX=x=kPx=k all k 它是一种统计平均值,简称它是一种统计平均值,简称均值均值2方差方差:DX=E(X-x)2=EX2-x2它是度量随机变量它是度量随机变量X与其均值与其均值EX的的偏离程度偏离程度。均方差均方差:方差的开方称为均方差,或标准方差,记为:方差的开方称为均方差,或标准方差,记为x二阶矩二阶矩:连续情况:连续
7、情况:EX2 =x2f(x)dx积分区间从积分区间从-,离散情况:离散情况:EX2 =k2Px=k all k7.3协方差:协方差:两个随机变量两个随机变量X和和Y的协方差定义如下:的协方差定义如下:Cov(X,Y)=E(X-x)(Y-y)=EXY-EXEY4相关系数相关系数:两个随机变量两个随机变量X和和Y的相关系数定义如下:的相关系数定义如下:r(X,Y)=Cov(X,Y)/xy相关系数是两个随机变量线性相关程度的度量。相关系数是两个随机变量线性相关程度的度量。例例3:设随机变量(:设随机变量(X,Y)的分布律如下:)的分布律如下:YX121 -10 1/4 0 1/4 求求 E(X),D
8、(X),E(E(X),D(X),E(Y Y),D(Y),cov(X,Y),r(X,Y),D(Y),cov(X,Y),r(X,Y)8.Part3几种重要的概率分布几种重要的概率分布1贝努里分布贝努里分布它的概率分布为:它的概率分布为:PX=1=p,PX=0=1-p它它也也称称两两点点分分布布或或(0-1)分分布布。它它描描述述一一次次贝贝努努里里实实验验中中,成成功或失败的概率。功或失败的概率。2二项分布二项分布PX=k=Cnkpk(1-p)n-k,k=0,1,n它描述它描述n次贝努里实验中事件次贝努里实验中事件A出现出现k次概率。次概率。3几何分布几何分布PX=k=p(1-p)k-1,k=1,
9、2,它描述在它描述在k次贝努里实验中首次出现成功的概率。次贝努里实验中首次出现成功的概率。9.n几何分布有一个重要的性质几何分布有一个重要的性质-后无效性后无效性:在前:在前n次实验未出现次实验未出现成功的条件下,再经过成功的条件下,再经过m次实验(即在次实验(即在n+m次实验中)首次出现成次实验中)首次出现成功的概率,等于恰好需要进行功的概率,等于恰好需要进行m次实验出现首次成功的无条件概率。次实验出现首次成功的无条件概率。用式子表达:用式子表达:nPX=n+m|Xn=PX=m(请同学们试证明之)n这种与过去历史无关的性质称为这种与过去历史无关的性质称为马尔可夫性马尔可夫性。n几何分布在我们
10、下面讲的排队论中是非常重要。它可以几何分布在我们下面讲的排队论中是非常重要。它可以描述某一描述某一任务(或顾客)的服务持续时间任务(或顾客)的服务持续时间。n4泊松分布(泊松分布(Poisson)nPX=k=k e-/k!k=0,1,2,n泊泊松松分分布布是是最最重重要要的的离离散散型型概概率率分分布布之之一一,它它作作为为表表述述随随机机现现象象的一种形式,在计算机性能评价等实践中扮演了重要的角色。的一种形式,在计算机性能评价等实践中扮演了重要的角色。n在在实实际际系系统统模模型型中中,一一般般都都要要假假定定任任务务(或或顾顾客客)的的到到来来是是服服从从泊松分布的泊松分布的。实践也证明:
11、这种假设是有效的。实践也证明:这种假设是有效的。10.5(负)指数分布(负)指数分布它是一种连续型的概率分布,它的概率密度为它是一种连续型的概率分布,它的概率密度为f(x)=e-x x0 0 x0,t0,有,有Ps+t|s=Pt在离散型随机变量中,只有几何分布具有无后效性。这两种在离散型随机变量中,只有几何分布具有无后效性。这两种分布可以分别用来描绘离散等待时间和连续等待时间。分布可以分别用来描绘离散等待时间和连续等待时间。在排队理论中,指数分布是很重要的。在排队理论中,指数分布是很重要的。11.6k-爱尔朗分布爱尔朗分布概率密度概率密度:f(x)=(kx)n-1ke-kx/(n-1)!x0,
12、0.0 x0数数字字特征:特征:EX=1/;VarX=1/(k2)如如果果k个个随随机机变变量量Xi,i=1,2,,k,分分别别服服从从指指数数分分布布,那那么么随随机机变变量量X=X1+X2+Xk服服从从爱爱尔尔朗朗分分布布。即即:具具有有k-爱爱尔尔朗朗分分布布的的随随机机变变量量可可以以看看作作具具有有同同一一指指数数分分布布的的独独立立的的k个个随随机机变量之和。变量之和。k-爱尔朗分布在排队模型中,得到广泛应用。如:假定顾客爱尔朗分布在排队模型中,得到广泛应用。如:假定顾客在到达窗口排队必须通过一个关口,这个关口由在到达窗口排队必须通过一个关口,这个关口由k层构成,通层构成,通过每层
13、的时间服从参数为过每层的时间服从参数为的指数分布,这样顾客通过整个关的指数分布,这样顾客通过整个关口到达窗口排队时,就实现了爱尔朗分布。口到达窗口排队时,就实现了爱尔朗分布。如下图:如下图:k210000窗口窗口12.Part4随机过程随机过程随随机机过过程程是是定定义义在在给给定定的的概概率率空空间间上上的的一一族族随机变量随机变量X(t),tT。我我们们知知道道:一一个个随随机机变变量量是是定定义义在在样样本本空空间间S上上的的函函数数,则则随随机机过过程程实实际际上上就就是是一一个个函函数数族族X(t,s)|sS,tT。若若t固定,随机过程固定,随机过程X(t,s)就是随机变量)就是随机
14、变量X(t)所取的值)所取的值,称为在称为在t时刻的状态时刻的状态。若若s固定,它是固定,它是t的函数,的函数,称称为随机过程的样为随机过程的样本函数或样本曲线。本函数或样本曲线。13.随机过程的例子随机过程的例子为为了了更更好好的的理理解解随随机机过过程程,我我们们从从一一个个例例子子开开始始。例例如如,n个同样的电阻,同时记录它们热噪声的电压波形。个同样的电阻,同时记录它们热噪声的电压波形。电阻上的热噪声是由于电阻中的电子的热运动引起的,因此,电阻上的热噪声是由于电阻中的电子的热运动引起的,因此,在在t1时刻电阻上的热噪声电压是一个时刻电阻上的热噪声电压是一个随机变量随机变量,并记为,并记
15、为x(t1),也就是说,也就是说t1时刻任一电阻时刻任一电阻r(i)上的噪声电压上的噪声电压x(i,t1)是无法预先确是无法预先确切地知道的。切地知道的。这里这里n支电阻的热噪声电压的集合是这个随机实验的样本空支电阻的热噪声电压的集合是这个随机实验的样本空间间S。对于某一支电阻,其热噪声电压是一时间函数。对于某一支电阻,其热噪声电压是一时间函数x(i,t),是,是随机过程的样本函数随机过程的样本函数。对所有电阻来说,其热噪声电压就是一族时间函数,记为对所有电阻来说,其热噪声电压就是一族时间函数,记为x(t),这族时间函数就是,这族时间函数就是“随机过程随机过程”,族中每一时间函数称为,族中每一
16、时间函数称为随随机过程的样本函数机过程的样本函数。14.Part5马尔可夫过程马尔可夫过程马尔可夫过程马尔可夫过程(MarkovProcess)是具有无后效性的随机过程。是具有无后效性的随机过程。无无后后效效性性是是指指:当当过过程程在在tn时时刻刻所所处处的的状状态态为为已已知知时时,过过程程在在大大于于tn的的时时刻刻所所处处状状态态的的概概率率特特性性只只与与过过程程在在tn时时刻刻所所处处的的状状态态有有关,而与过程在关,而与过程在tn时刻以前的状态无关。时刻以前的状态无关。换换言言之之,对对于于随随机机过过程程X(t),t T,如如果果对对于于任任意意参参数数t0t1t2tn1有有p
17、ij=0(2)连续时间生灭过程连续时间生灭过程一一个个连连续续时时间间,状状态态空空间间S=0,1,2为为可可数数集集的的齐齐次次马马尔可夫尔可夫过程过程X(t),t0,,称为生灭过程。称为生灭过程。时齐性时齐性转移概率转移概率Pij(t,)只与只与i,j,-t有关,即有关,即Pij()=Pij(t,t+)16.练习练习练习:练习:1。有有10个个电电阻阻,其其电电阻阻值值分分别别为为1,2,10,从从中中取取出出三三个个,要要求求取取出出的的三三个个电电阻阻,一一个个小小于于5,一一个个等等于于5,另另一一个个大大于于5,问问:取取一次就能达到要求的概率。一次就能达到要求的概率。2一一袋袋内
18、内装装有有5只只球球,编编号号为为1,2,3,4,5,从从中中任任取取3只只,求求被被抽抽取取3只只球球中中,中中间间号号码码X的的分分布布规律。规律。17.习题解答习题解答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/62依依题题意意,X的的可可能能值值为为2,3,4,当当取取中中间间号号码码为为k时时,则则另另外外两两只只球球必
19、必须须分分别别在在号号码码小小于于k的的k-1个个中中取取一一个个,和和在在号码大于号码大于k的的5-k个中取一个,于是:个中取一个,于是:pk=PX=k=C(k-1,1)C(5-k,1)/C(5,3),k=2,3,4所以,所以,X的分布律为:的分布律为:X234Pk0.30.40.318.UNIT1排队模型排队模型排排队队论论(queueingtheory),或或称称随随机机服服务务系系统统理理论论,作作为为运运筹筹学学研研究究的的一一种种有有力力手手段段,研研究究的的内内容容有有3个个方方面面:系系统统的的性性态态,即即与与排排队队有有关关的的数数量量指指标标的的概概率率规规律律性性;系系
20、统统的的优优化化问问题题;统统计计推推断断,根根据据资资料料合合理理建建立立模模型型。目目的的是是正正确确设设计计和和有有效效运运行行各各个个服服务务系系统统,使使之之发发挥挥最最佳佳效效益益。排排队队论论不不仅仅在在理理论论上上达达到到了了成成熟熟阶阶段段,而而且且其其应应用用范范围围不不断断增增加加。概概括括起起来来,它它已已在在电电话话交交换换网网、公公路路、铁铁路路、航航空空运运输输、工工程程管管理理、公公共共服服务务、货货物物存存储储和和生生产产流流水水线线过过程程等等方方面面得得到到了了广广泛泛的的应应用用。特特别别地地,排排队队论论是是计计算算机机通通信信网网络络和和计计算算机机
21、系系统统中中通通信信信信息息量量研研究究的的基基础础理理论论,信信息息系系统统通通信信问题的问题的定量定量研究往往要求借助于排对论才能得到解决。研究往往要求借助于排对论才能得到解决。19.排队排队常常是件很令人恼火的事情常常是件很令人恼火的事情尤其是在我们这样的人口大国尤其是在我们这样的人口大国电话亭电话亭1978年在北京年在北京15%的电话要在的电话要在1小时后才能接通。小时后才能接通。在电报大楼打电话的人还要带着午饭去排队在电报大楼打电话的人还要带着午饭去排队银行窗口,银行窗口,ATM游乐场的游乐项目游乐场的游乐项目医院、理发、火车售票医院、理发、火车售票在现实生活中,为了接受某种服务,排
22、队等待是常在现实生活中,为了接受某种服务,排队等待是常见的现象。见的现象。从排队等待得到抽象的物理模型,进一从排队等待得到抽象的物理模型,进一步建立数学模型的一整套理论就是所谓的排队论。步建立数学模型的一整套理论就是所谓的排队论。20.什么是排队论?什么是排队论?排队论是专门研究带有随机因素,产生排队论是专门研究带有随机因素,产生拥挤现象的优化理论。拥挤现象的优化理论。亦称为亦称为随机服务系统理论随机服务系统理论。因为被服务。因为被服务者到达系统的时间是不确定的。者到达系统的时间是不确定的。有关于由有关于由服务设施服务设施与与被服务者被服务者构成的构成的排排队服务系统队服务系统的理论。的理论。
23、21.本讲主要掌握:本讲主要掌握:基本模型基本模型M/M/1模型模型M/M/c模型模型其他模型其他模型应用:校园网的设计和调节收费应用:校园网的设计和调节收费22.基本的排队模型基本的排队模型基本组成基本组成概念与记号概念与记号指数分布和生灭过程指数分布和生灭过程23.典型典型排队系统模型排队系统模型顾客到达顾客到达:在队列中排队在队列中排队服务台服务服务台服务顾客离开顾客离开输入源的输入源的到达规律到达规律队列大小?队列大小?特性?特性?到达方式?到达方式?服务规律?服务规律?服务协议?服务协议?在在本本单单元元中中,我我们们主主要要介介绍绍排排队队系系统统的的组组成成和和特特征征,排排队队
24、系系统统的的到到达达和和服服务务,经经典典排排队队模模型型等等内内容容。顾顾客客到到达达规规律律和和服服务务规规律律都是通过概率来描述的,所以概率论是排队论的基础。都是通过概率来描述的,所以概率论是排队论的基础。输入源。24.基本组成基本组成输入来源队 列服务机构排队系统排队系统顾客服务完离开排队系统的三个基本组成部分.输入过程(顾客按照怎样的规律到达);排队规则(顾客按照一定规则排队等待服务);服务机构(服务机构的设置,服务台的数量,服务的方式,服务时间分布等)25.基本排队模型基本排队模型输入过程输入过程顾客来源顾客来源有限有限/无限无限顾客数量顾客数量有限有限无限无限经常性的顾客来源经常
25、性的顾客来源顾客到达间隔时间顾客到达间隔时间:到下一个顾客到达的时间到下一个顾客到达的时间.服从某一概率分布服从某一概率分布.(指数分布指数分布)顾客的行为假定顾客的行为假定在未服务之前不会离开在未服务之前不会离开;当看到队列很长的时候离开;当看到队列很长的时候离开;从一个队列移到另一个队列。从一个队列移到另一个队列。顾客到达的方式通常是一个一个到达顾客到达的方式通常是一个一个到达的,也可能是成批的。顾客的到达总是有的,也可能是成批的。顾客的到达总是有一定规律,即到达过程或到达时间间隔符一定规律,即到达过程或到达时间间隔符合一定的分布,称合一定的分布,称到达分布。到达分布。顾客的到达或到达时间
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 排队 讲义
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【天****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【天****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。