《排队论(讲义)》由会员分享，可在线阅读，更多相关《排队论(讲义)（126页珍藏版）》请在金锄头文库上搜索。
1、排队论排队论Queueing Theory主讲：周在莹主讲：周在莹2021/6/161排队论课件CONTENTSPREPARATION:概率论与随机过程概率论与随机过程UNIT1排队模型排队模型UNIT2排队网络模型排队网络模型UNIT3应用之：应用之：QUICKPASS系统系统结束语结束语2021/6/162排队论课件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。2021/6/163排队论课件(2)相对频率定义相对频率定义：P(A)=limnA/nn其中其
3、中n是实验的次数，是实验的次数，nA是是A发生的次数发生的次数例例2投硬币投硬币在在大大数数量量投投掷掷后后，硬硬币币的的正正面面在在上上的的可可能能性性在在0.5左左右右，上上下下两面在上面具有相同的概率。两面在上面具有相同的概率。(3)公公理理化化定定义义：从从一一定定数数量量的的定定义义概概率率度度量量的的公公理理出出发发，经经过过推导规则达到概率的有效计算。这些公理包括：推导规则达到概率的有效计算。这些公理包括：（a）对于每一个事件对于每一个事件A，有，有0P（A）1（b）P（）=1（c）如果如果A和和B是互斥的，则是互斥的，则P（AUB）=P（A）+P（B）2021/6/164排队论
4、课件2条件概率和独立性条件概率和独立性条件概率：条件概率：假假定定事事件件B已已经经发发生生时时，事事件件A发发生生的的条条件件概概率率P(A|B)可以定义如下：可以定义如下：P（A|B）=P（AB）/P（B）独立性：独立性：如果如果P(AB)=P(A)P(B)，事件，事件A和和B叫做相互独立的事件叫做相互独立的事件独立性的概念可以推广到三个或多个事件。独立性的概念可以推广到三个或多个事件。2021/6/165排队论课件3全概率公式和贝叶斯定理全概率公式和贝叶斯定理全全概概率率公公式式：给给定定一一组组互互斥斥事事件件E1，E2，En，这这些些事事件件的的并并集集包包括括所所有有可可能能的的结
5、结果果，同同时时给给任任一一个个任任意事件意事件A，那么全概率公式可以表示为：，那么全概率公式可以表示为：n P(A)=P(A|Ei)P(Ei)i=1把计算把计算A的概率分解为一些容易计算的概率之和。的概率分解为一些容易计算的概率之和。贝叶斯定理：贝叶斯定理： P(Ei|A)= P(A|Ei)P(Ei) P(A|Ei)P(Ei) 也称为后验概率公式，是在已知结果发生的情况下，求导也称为后验概率公式，是在已知结果发生的情况下，求导致结果的某种原因的可能性的大小。致结果的某种原因的可能性的大小。2021/6/166排队论课件Part2.随机变量的数字特征随机变量的数字特征随随机机变变量量X是是样样
6、本本点点的的函函数数，它它的的定定义义域域是是样样本本空空间间，值值域域是实数集是实数集R，即，即X：R随随机机变变量量的的数数字字特特征征对对研研究究随随机机变变量量是是很很重重要要的的，常常用用的的数数字字特征有：数学期望、方差、协方差和相关系数。特征有：数学期望、方差、协方差和相关系数。1数学期望数学期望：连续情况：连续情况：EX = x =xf(x)dx积分区间从积分区间从-，离散情况：离散情况：EX =x = kPx=k all k 它是一种统计平均值，简称它是一种统计平均值，简称均值均值2方差方差：DX=E(X-x)2=EX2-x2它是度量随机变量它是度量随机变量X与其均值与其均值
7、EX的的偏离程度偏离程度。均方差均方差：方差的开方称为均方差，或标准方差，记为：方差的开方称为均方差，或标准方差，记为x二阶矩二阶矩：连续情况：连续情况：EX2 =x2f(x)dx积分区间从积分区间从-，离散情况：离散情况：EX2 = k2Px=k all k2021/6/167排队论课件3协方差：协方差：两个随机变量两个随机变量X和和Y的协方差定义如下：的协方差定义如下：Cov(X,Y)=E(X-x)(Y-y)=EXY-EXEY4相关系数相关系数:两个随机变量两个随机变量X和和Y的相关系数定义如下：的相关系数定义如下：r(X,Y)=Cov(X,Y)/xy相关系数是两个随机变量线性相关程度的度
8、量。相关系数是两个随机变量线性相关程度的度量。例例3：设随机变量（：设随机变量（X，Y）的分布律如下：）的分布律如下：YX121 -10 1/4 0 1/4 求求 E(X),D(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)2021/6/168排队论课件Part3几种重要的概率分布几种重要的概率分布1贝努里分布贝努里分布它的概率分布为：它的概率分布为：PX=1=p，PX=0=1-p它它也也称称两两点点分分布布或或（0-1）分分布布。它它描描述述一一次次贝贝努努里里实实验验中中，成成功或失败的概率。功或失败的概率。
9、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,2,它描述在它描述在k次贝努里实验中首次出现成功的概率。次贝努里实验中首次出现成功的概率。2021/6/169排队论课件n几何分布有一个重要的性质几何分布有一个重要的性质-后无效性后无效性：在前：在前n次实验未出现次实验未出现成功的条件下，再经过成功的条件下，再经过m次实验（即在次实验（即在n+m次实验中）首次出现成次实验中）首次出现成功的概率，等于恰好需要进行功的概率，等于恰好需要进行m次实
10、验出现首次成功的无条件概率。次实验出现首次成功的无条件概率。用式子表达：用式子表达：nPX=n+m|Xn=PX=m(请同学们试证明之）n这种与过去历史无关的性质称为这种与过去历史无关的性质称为马尔可夫性马尔可夫性。n几何分布在我们下面讲的排队论中是非常重要。它可以几何分布在我们下面讲的排队论中是非常重要。它可以描述某一描述某一任务（或顾客）的服务持续时间任务（或顾客）的服务持续时间。n4泊松分布（泊松分布（Poisson）nPX = k = k e -/ k! k=0,1,2,n泊泊松松分分布布是是最最重重要要的的离离散散型型概概率率分分布布之之一一，它它作作为为表表述述随随机机现现象象的一种
11、形式，在计算机性能评价等实践中扮演了重要的角色。的一种形式，在计算机性能评价等实践中扮演了重要的角色。n在在实实际际系系统统模模型型中中，一一般般都都要要假假定定任任务务（或或顾顾客客）的的到到来来是是服服从从泊松分布的泊松分布的。实践也证明：这种假设是有效的。实践也证明：这种假设是有效的。2021/6/1610排队论课件5（负）指数分布指数分布它是一种连续型的概率分布，它的概率密度为它是一种连续型的概率分布，它的概率密度为f（x）= e-x x0 0 x0,t0，有，有Ps+t|s=Pt在离散型随机变量中，只有几何分布具有无后效性。这两种在离散型随机变量中，只有几何分布具有无后效性。这两种分
12、布可以分别用来描绘离散等待时间和连续等待时间。分布可以分别用来描绘离散等待时间和连续等待时间。在排队理论中，指数分布是很重要的。在排队理论中，指数分布是很重要的。2021/6/1611排队论课件6k-爱尔朗分布爱尔朗分布概率密度概率密度:f(x)=(kx)n-1ke-kx/(n-1)!x0，0.0x0数数字字特征：特征：EX=1/;VarX=1/（k2）如如果果k个个随随机机变变量量Xi，i=1，2，,k,分分别别服服从从指指数数分分布布，那那么么随随机机变变量量X=X1+X2+Xk服服从从爱爱尔尔朗朗分分布布。即即：具具有有k-爱爱尔尔朗朗分分布布的的随随机机变变量量可可以以看看作作具具有有
13、同同一一指指数数分分布布的的独独立立的的k个个随随机机变量之和。变量之和。k-爱尔朗分布在排队模型中，得到广泛应用。如：假定顾客爱尔朗分布在排队模型中，得到广泛应用。如：假定顾客在到达窗口排队必须通过一个关口，这个关口由在到达窗口排队必须通过一个关口，这个关口由k层构成，通层构成，通过每层的时间服从参数为过每层的时间服从参数为的指数分布，这样顾客通过整个关的指数分布，这样顾客通过整个关口到达窗口排队时，就实现了爱尔朗分布。口到达窗口排队时，就实现了爱尔朗分布。如下图：如下图：k210000窗口窗口2021/6/1612排队论课件Part4随机过程随机过程随随机机过过程程是是定定义义在在给给定定
14、的的概概率率空空间间上上的的一一族族随机变量随机变量X(t)，tT。我我们们知知道道：一一个个随随机机变变量量是是定定义义在在样样本本空空间间S上上的的函函数数，则则随随机机过过程程实实际际上上就就是是一一个个函函数数族族X（t，s）|sS，tT。若若t固定，随机过程固定，随机过程X（t，s）就是随机变量）就是随机变量X（t）所取的值）所取的值，称为在称为在t时刻的状态时刻的状态。若若s固定，它是固定，它是t的函数，的函数，称称为随机过程的样为随机过程的样本函数或样本曲线。本函数或样本曲线。2021/6/1613排队论课件随机过程的例子随机过程的例子为为了了更更好好的的理理解解随随机机过过程程
15、，我我们们从从一一个个例例子子开开始始。例例如如，n个同样的电阻，同时记录它们热噪声的电压波形。个同样的电阻，同时记录它们热噪声的电压波形。电阻上的热噪声是由于电阻中的电子的热运动引起的，因此，电阻上的热噪声是由于电阻中的电子的热运动引起的，因此，在在t1时刻电阻上的热噪声电压是一个时刻电阻上的热噪声电压是一个随机变量随机变量，并记为，并记为x(t1)，也就是说，也就是说t1时刻任一电阻时刻任一电阻r(i)上的噪声电压上的噪声电压x(i,t1)是无法预先是无法预先确切地知道的。确切地知道的。这里这里n支电阻的热噪声电压的集合是这个随机实验的样本空支电阻的热噪声电压的集合是这个随机实验的样本空间
16、间S。对于某一支电阻，其热噪声电压是一时间函数。对于某一支电阻，其热噪声电压是一时间函数x(i，t)，是，是随机过程的样本函数随机过程的样本函数。对所有电阻来说，其热噪声电压就是一族时间函数，记为对所有电阻来说，其热噪声电压就是一族时间函数，记为x(t)，这族时间函数就是，这族时间函数就是“随机过程随机过程”，族中每一时间函数称为，族中每一时间函数称为随机过程的样本函数随机过程的样本函数。2021/6/1614排队论课件Part5马尔可夫过程马尔可夫过程马尔可夫过程马尔可夫过程(MarkovProcess)是具有无后效性的随机过程。是具有无后效性的随机过程。无无后后效效性性是是指指：当当过过程
17、程在在tn时时刻刻所所处处的的状状态态为为已已知知时时，过过程程在在大大于于tn的的时时刻刻所所处处状状态态的的概概率率特特性性只只与与过过程程在在tn时时刻刻所所处处的的状状态态有有关，而与过程在关，而与过程在tn时刻以前的状态无关。时刻以前的状态无关。换换言言之之，对对于于随随机机过过程程X（t），t T，如如果果对对于于任任意意参参数数t0t1t2tn1有有pij =0(2)连续时间生灭过程连续时间生灭过程一一个个连连续续时时间间，状状态态空空间间S=0，1，2为为可可数数集集的的齐齐次次马马尔可夫尔可夫过程过程X(t)，t0，,称为生灭过程。称为生灭过程。时齐性时齐性转移概率转移概率P
18、ij(t,)只与只与i,j,-t有关，即有关，即Pij()=Pij(t,t+)2021/6/1616排队论课件练习练习练习：练习：1。有有10个个电电阻阻，其其电电阻阻值值分分别别为为1，2，10，从从中中取取出出三三个个，要要求求取取出出的的三三个个电电阻阻，一一个个小小于于5，一一个个等等于于5，另另一一个个大大于于5，问问：取取一次就能达到要求的概率。一次就能达到要求的概率。2一一袋袋内内装装有有5只只球球，编编号号为为1，2，3，4，5，从从中中任任取取3只只，求求被被抽抽取取3只只球球中中，中中间间号号码码X的的分分布布规律。规律。2021/6/1617排队论课件习题解答习题解答1把
19、把从从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时时，则则另另外外两两只只球球必必须须分分别别在在号号码码小小于于k的的k-1个个中中取取一一个个，和和在在号码大于号码大于k的的5-k个中取一个，于是：个中取一个，于是：pk=PX=k=C(k-1,1)C(5
20、-k,1)/C(5,3),k=2,3,4所以，所以，X的分布律为：的分布律为：X234Pk0.30.40.32021/6/1618排队论课件UNIT1排队模型排队模型排排队队论论（queueingtheory），或或称称随随机机服服务务系系统统理理论论，作作为为运运筹筹学学研研究究的的一一种种有有力力手手段段，研研究究的的内内容容有有3个个方方面面：系系统统的的性性态态，即即与与排排队队有有关关的的数数量量指指标标的的概概率率规规律律性性；系系统统的的优优化化问问题题；统统计计推推断断，根根据据资资料料合合理理建建立立模模型型。目目的的是是正正确确设设计计和和有有效效运运行行各各个个服服务务系
21、系统统，使使之之发发挥挥最最佳佳效效益益。排排队队论论不不仅仅在在理理论论上上达达到到了了成成熟熟阶阶段段，而而且且其其应应用用范范围围不不断断增增加加。概概括括起起来来，它它已已在在电电话话交交换换网网、公公路路、铁铁路路、航航空空运运输输、工工程程管管理理、公公共共服服务务、货货物物存存储储和和生生产产流流水水线线过过程程等等方方面面得得到到了了广广泛泛的的应应用用。特特别别地地，排排队队论论是是计计算算机机通通信信网网络络和和计计算算机机系系统统中中通通信信信信息息量量研研究究的的基基础础理理论论，信信息息系系统统通通信信问题的问题的定量定量研究往往要求借助于排对论才能得到解决。研究往往
22、要求借助于排对论才能得到解决。2021/6/1619排队论课件排队排队常常是件很令人恼火的事情常常是件很令人恼火的事情尤其是在我们这样的人口大国尤其是在我们这样的人口大国电话亭电话亭1978年在北京年在北京15%的电话要在的电话要在1小时后才能接通。小时后才能接通。在电报大楼打电话的人还要带着午饭去排队在电报大楼打电话的人还要带着午饭去排队银行窗口，银行窗口，ATM游乐场的游乐项目游乐场的游乐项目医院、理发、火车售票医院、理发、火车售票在现实生活中，为了接受某种服务，排队等待是在现实生活中，为了接受某种服务，排队等待是常见的现象。常见的现象。从排队等待得到抽象的物理模型，进从排队等待得到抽象的
23、物理模型，进一步建立数学模型的一整套理论就是所谓的排队论。一步建立数学模型的一整套理论就是所谓的排队论。2021/6/1620排队论课件什么是排队论？什么是排队论？排队论是专门研究带有随机因素，产生排队论是专门研究带有随机因素，产生拥挤现象的优化理论。拥挤现象的优化理论。亦称为亦称为随机服务系统理论随机服务系统理论。因为被服务。因为被服务者到达系统的时间是不确定的。者到达系统的时间是不确定的。有关于由有关于由服务设施服务设施与与被服务者被服务者构成的构成的排排队服务系统队服务系统的理论。的理论。2021/6/1621排队论课件本讲主要掌握：本讲主要掌握：基本模型基本模型M/M/1模型模型M/M
24、/c模型模型其他模型其他模型应用：校园网的设计和调节收费应用：校园网的设计和调节收费2021/6/1622排队论课件基本的排队模型基本的排队模型基本组成基本组成概念与记号概念与记号指数分布和生灭过程指数分布和生灭过程2021/6/1623排队论课件典型典型排队系统模型排队系统模型顾客到达顾客到达:在队列中排队在队列中排队服务台服务服务台服务顾客离开顾客离开输入源的输入源的到达规律到达规律队列大小？队列大小？特性？特性？到达方式？到达方式？服务规律？服务规律？ 服务协议？服务协议？在在本本单单元元中中，我我们们主主要要介介绍绍排排队队系系统统的的组组成成和和特特征征，排排队队系系统统的的到到达达
25、和和服服务务，经经典典排排队队模模型型等等内内容容。顾顾客客到到达达规规律律和和服服务务规规律律都是通过概率来描述的，所以概率论是排队论的基础。都是通过概率来描述的，所以概率论是排队论的基础。输入源。2021/6/1624排队论课件基本组成基本组成输入来源队 列服务机构排队系统排队系统顾客服务完离开排队系统的三个基本组成部分.输入过程 (顾客按照怎样的规律到达);排队规则 (顾客按照一定规则排队等待服务);服务机构 (服务机构的设置,服务台的数量,服务的方式,服务时间分布等)2021/6/1625排队论课件基本排队模型基本排队模型输入过程输入过程顾客来源顾客来源有限有限/无限无限顾客数量顾客数
26、量有限有限无限无限经常性的顾客来源经常性的顾客来源顾客到达间隔时间顾客到达间隔时间:到下一个顾客到达的时间到下一个顾客到达的时间.服从某一概率分布服从某一概率分布.(指数分布指数分布)顾客的行为假定顾客的行为假定在未服务之前不会离开在未服务之前不会离开;当看到队列很长的时候离开；当看到队列很长的时候离开；从一个队列移到另一个队列。从一个队列移到另一个队列。 顾客到达的方式通常是一个一个到达顾客到达的方式通常是一个一个到达的，也可能是成批的。顾客的到达总是有的，也可能是成批的。顾客的到达总是有一定规律，即到达过程或到达时间间隔符一定规律，即到达过程或到达时间间隔符合一定的分布，称合一定的分布，称
27、到达分布。到达分布。顾客的到达或到达时间通常假定为相顾客的到达或到达时间通常假定为相互独立的且遵从同一分布的互独立的且遵从同一分布的随机变量。随机变量。2021/6/1626排队论课件基本排队模型队列基本排队模型队列/排队规则排队规则d队列队列队列容量队列容量有限有限/无限无限排队方式排队方式单队列单队列并联式多队列并联式多队列串联式多队列串联式多队列杂乱队列杂乱队列 对于一个有限大小的队列来对于一个有限大小的队列来说，顾客可能从队列中丢失。说，顾客可能从队列中丢失。有什么样的服务协议就有什么有什么样的服务协议就有什么样的与之对应的排队方式。样的与之对应的排队方式。2021/6/1627排队论
28、课件基本排队模型服务规则基本排队模型服务规则服务机构服务机构服务设施，服务设施，服务渠道与服务台服务渠道与服务台服务台数量服务台数量单服务台系统单服务台系统多服务台系统多服务台系统无限服务台系统无限服务台系统服务协议服务协议先来先服务（先来先服务（FCFS）后来先服务（后来先服务（LCFS）随机服务（随机服务（RSS）有优先权的服务（有优先权的服务（PR）服务时间分布服务时间分布指数指数,常数常数,k阶阶Erlang 一般服务台对顾客是一个一个一般服务台对顾客是一个一个进行服务的，且对每一个顾客的进行服务的，且对每一个顾客的服务时间服务时间长短不一。长短不一。将将服务时间服务时间看作看作随机变
29、量随机变量，那么那么它们是相互独立的且遵循同一分它们是相互独立的且遵循同一分布。因此描述服务规律时，采用布。因此描述服务规律时，采用服务时间的概率分布，即服务时间的概率分布，即服务分服务分布布。服务分布同到达分布一样，到服务分布同到达分布一样，到底属于哪一种概率分布，要根据底属于哪一种概率分布，要根据具体排队问题进行分析。具体排队问题进行分析。2021/6/1628排队论课件服务协议服务协议（a）先来先服务先来先服务顾顾客客到到达达的的先先后后次次序序排排队队接接受受服服务务，用用FCFS（firstcomefirstserved）表示。）表示。（b）后来先服务（或称先来后服务）后来先服务（或
30、称先来后服务）队队列列是是一一种种堆堆栈栈形形式式（临临时时寄寄存存货货物物的的地地方方）。当当某某一一顾顾客客服服务务结结束束时时，如如果果在在队队列列中中有有两两个个以以上上等等待待的的顾顾客客，则则把把最最后后到到达达的的顾顾客客作作为为下下一一个个服服务的对象。用务的对象。用LCFS（lastcomefirstserved）表示。）表示。（c）随机选择服务随机选择服务在服务时从等待顾客中随意抽取一个进行服务。在服务时从等待顾客中随意抽取一个进行服务。（d）优先服务和动态优先服务优先服务和动态优先服务预预先先规规定定优优先先顺顺序序位位的的类类别别、且且给给到到达达顾顾客客规规定定优优先
31、先顺顺序序位位作作为为标标记记的的优优先先权权。通通常常按按FCFS进进行行服服务务。优优先先权权分分为为三三类类：排排队队优优先先权权、中中断断优优先权、动态优先权先权、动态优先权。如计算机中断的优先级。如计算机中断的优先级。（e）处理器共享（处理器共享（processorsharing，PS）服服务务台台的的处处理理能能力力被被平平均均分分配配给给队队列列中中的的所所有有顾顾客客，没没有有排排队队现现象象出出现现，当顾客的数量增加时，只是顾客的服务时间变长。如：网络服务系统。当顾客的数量增加时，只是顾客的服务时间变长。如：网络服务系统。（f）无限服务台（无限服务台（infiniteserv
32、er，Is）在在这这种种情情况况下下，队队列列中中的的每每个个顾顾客客接接受受完完全全相相同同的的服服务务，而而且且就就好好像像它它是是唯唯一一的的一一个个顾顾客客一一样样。好好像像对对于于每每个个顾顾客客都都可可以以“克克隆隆”出出一一个个新新的的服服务务台，而且克隆的数目可以无限。台，而且克隆的数目可以无限。2021/6/1629排队论课件排队系统的到达和服务排队系统的到达和服务1到达规律的描述到达规律的描述（1）主要描述参数）主要描述参数（a）到达时点）到达时点将将某某一一时时刻刻设设为为t0，顾顾客客依依次次到到达达的的时时刻刻用用t-1t0t1t2表表示示，如如果果在在时刻时刻tk到
33、达的顾客为到达的顾客为Nk，则到达时点可用，则到达时点可用tk、Nk）表示。）表示。（b）平均到达间隔）平均到达间隔一个顾客到达时刻之间的时宽为到达间隔。一个顾客到达时刻之间的时宽为到达间隔。（c）到达速率）到达速率单位时间到达顾客的平均数叫到达速率，也称到达密度或输入速率。单位时间到达顾客的平均数叫到达速率，也称到达密度或输入速率。（2）到达规律）到达规律顾顾客客的的到到达达规规律律可可以以用用概概率率来来描描述述，两两个个顾顾客客到到达达的的时时间间间间隔隔是是独独立立的的随随机变量，服从同一概率分布时。常用的分布规律有：机变量，服从同一概率分布时。常用的分布规律有：（a）一般到达）一般到
34、达（b）泊松到达）泊松到达（c）爱尔朗到达）爱尔朗到达（d）等间隔到达）等间隔到达2021/6/1630排队论课件泊松分布和负指数分布在排队论中的应用泊松分布和负指数分布在排队论中的应用泊松分布（泊松分布（Poisson）：）：PX=k=ke-/k!k=0,1,2,，x=x=泊泊松松分分布布是是最最重重要要的的离离散散型型概概率率分分布布之之一一，也也是是表表述述随随机机现现象象的的一一种种重重要要形形式式。在在实实际际系系统统模模型型中中，一一般般都都要要假假定定任任务务（或顾客）的到来是泊松分布的。实践也证明：这种假设有效。（或顾客）的到来是泊松分布的。实践也证明：这种假设有效。如如果果顾
35、顾客客到到达达的的人人数数是是符符合合泊泊松松分分布布，即即在在时时间间T内内到到达达有有k个顾客到达的概率为：个顾客到达的概率为：p=（T）ke-T/k!，在时间在时间T内顾客到达的平均顾客数内顾客到达的平均顾客数=T，平均到达速度（顾客数平均到达速度（顾客数/秒）秒）=服服从从泊泊松松分分布布过过程程的的到到达达被被认认为为是是随随机机到到达达，因因为为当当顾顾客客根根据据泊泊松松过过程程到到达达时时，顾顾客客在在各各个个时时刻刻到到达达的的可可能能性性相相同同并并与与其它顾客的到达无关。其它顾客的到达无关。2021/6/1631排队论课件（负）指数分布：（负）指数分布：它是一种连续型的概
36、率分布，它的概率密度：它是一种连续型的概率分布，它的概率密度：f（x）=e-xx0它的分布函数：它的分布函数：F（x）=1-e-xx0指指数数分分布布的的一一个个有有用用的的性性质质是是它它的的数数学学期期望望等等于于标标准准差差：x=x=1/泊松分布和指数分布的关系：泊松分布和指数分布的关系：如如果果顾顾客客以以泊泊松松到到达达,则则顾顾客客到到达达的的时时间间间间隔隔Ta服服从从指指数数分分布布，即：即：PTat=1-e-t,ETa=1/因此，平均到达的时间间隔是到达速率的倒数。因此，平均到达的时间间隔是到达速率的倒数。2021/6/1632排队论课件负指数分布负指数分布密度函数密度函数均
37、值均值方差方差随机变量随机变量 T（两个顾客相继到达的时间间隔）（两个顾客相继到达的时间间隔）分布函数分布函数 fT(t)t2021/6/1633排队论课件负指数分布性质负指数分布性质1fT(t)tttfT(t) 是一个严格下降函数2021/6/1634排队论课件负指数分布性质负指数分布性质2无后效性（无记忆性）无后效性（无记忆性）不管多长时间不管多长时间( t)已经过去，已经过去，逗留时间的概率分布与下逗留时间的概率分布与下一个事件的相同一个事件的相同.或者说，后一个顾客到来所需时间与或者说，后一个顾客到来所需时间与前一个顾客到来所需时间无关。前一个顾客到来所需时间无关。2021/6/163
38、5排队论课件负指数分布性质负指数分布性质3几个独立的指数分布的随机变量的最小也服从指数分布几个独立的指数分布的随机变量的最小也服从指数分布几个独立的指数分布的随机几个独立的指数分布的随机变量的和还是一个服从指数变量的和还是一个服从指数分布的随机变量分布的随机变量T1(1)T1(2)T1(3)T (1 +2 +3)2021/6/1636排队论课件负指数分布性质负指数分布性质4负指数分布Poisson分布 在t时间内已经服务n个顾客的概率1/: 平均服务时间平均服务率= 相继顾客到达平均间隔时间2021/6/1637排队论课件负指数分布性质负指数分布性质52021/6/1638排队论课件排队论基本
39、概念部分练习排队论基本概念部分练习练习练习1：1。指出下列排队系统中的顾客和服务台：。指出下列排队系统中的顾客和服务台：（1）自行车修理店；（）自行车修理店；（2）按客户订单进行加工的加工车间）按客户订单进行加工的加工车间（3）机场起飞的客机）机场起飞的客机（4）十字路口红灯前的车辆）十字路口红灯前的车辆2。判断正误。判断正误（1）若到达排队系统的顾客人数服从泊松分布，则依次到达的两名顾客之间的间）若到达排队系统的顾客人数服从泊松分布，则依次到达的两名顾客之间的间隔时间服从指数分布。隔时间服从指数分布。（2）在一个排队系统中，不管顾客到达和服务时间的情况如何，只要运行时间）在一个排队系统中，不
40、管顾客到达和服务时间的情况如何，只要运行时间足够长的时间后，系统将进入稳定状态。足够长的时间后，系统将进入稳定状态。（3）在排队系统中，顾客等待时间的分布不受排队规则的影响。）在排队系统中，顾客等待时间的分布不受排队规则的影响。2021/6/1639排队论课件2服务规律的描述服务规律的描述(1)主要描述参量主要描述参量（a）平均服务时间）平均服务时间设设服服务务时时间间的的分分布布函函数数为为F（t），则则服服务务时时间间的的平平均均表表示示为为:1/=tdF(t)其中其中称为平均服务速率，平均一个顾客的服务时间。称为平均服务速率，平均一个顾客的服务时间。（b）服务速率）服务速率一一般般指指平
41、平均均服服务务速速率率，单单位位时时间间内内被被服服务务完完的的顾顾客客数数，用用来表示。来表示。(2)服务规律服务规律服服务务规规律律通通常常是是就就服服务务时时间间的的分分布布而而言言的的。服服务务时时间间分分布布典典型地有指数分布、爱尔朗分布、一般分布等。型地有指数分布、爱尔朗分布、一般分布等。结结论论：顾顾客客到到达达规规律律和和服服务务规规律律都都是是通通过过概概率率来来描描述述的的，所所以以概概率论是排队论的基础。率论是排队论的基础。2021/6/1640排队论课件经典排队模型经典排队模型它的格式为：它的格式为：ABnSZ其中符号的含义如下：其中符号的含义如下：A：顾客到达的规律；
42、顾客到达的规律；B：服务时间分布；服务时间分布；n：服务台的数目；服务台的数目；S：队列容量的大小；队列容量的大小；Z：服务规程。服务规程。当队列的大小为无穷大、且服务规程为先来先服务时，经典排队模型可简化为当队列的大小为无穷大、且服务规程为先来先服务时，经典排队模型可简化为ABn不同类型的排队，不同类型的排队，A、B可用如下约定的字母表示可用如下约定的字母表示。M：如如果果用用于于描描述述到到达达，表表示示泊泊松松到到达达过过程程，到到达达时时间间间间隔隔符符合合指指数数分分布布；如如 果用于描述果用于描述服务，则指具有指数分布的时间。服务，则指具有指数分布的时间。M表示表示Markov的第
43、一个字母。的第一个字母。G：一一般般分分布布。表表示示到到达达间间隔隔时时间间或或服服务务时时间间服服从从一一般般分分布布。G是是General的的第第一个字母。一个字母。Ek：k-爱爱尔尔朗朗分分布布。表表示示到到达达间间隔隔时时间间或或服服务务时时间间服服从从k-爱爱尔尔朗朗分分布布。E是是Erlang的第一个字母。的第一个字母。D:定长分布定长分布(常数时间常数时间)H：超几何分布。：超几何分布。L：H项式分布。项式分布。Z代表的服务规程典型的有：代表的服务规程典型的有：FCFS：先来先服务；先来先服务；LCFS：后来先服务；后来先服务；RSS：随机选择服务；随机选择服务；PR：优先权服
44、务。优先权服务。Ba：集体（批量）服务。集体（批量）服务。GD：一般规约服务，即通用规约服务。一般规约服务，即通用规约服务。2021/6/1641排队论课件3基本排队关系基本排队关系在对排队进行分析时，为了便于分析，经常做一些简化假设。对一个排队系在对排队进行分析时，为了便于分析，经常做一些简化假设。对一个排队系统，若满足以下三个条件：统，若满足以下三个条件：（1）排队系统能够进入统计平衡状态；）排队系统能够进入统计平衡状态；（2）服务员的忙期与闲期交替出现，即系统不是总处于忙的状态；）服务员的忙期与闲期交替出现，即系统不是总处于忙的状态；（3）系统中任一顾客不会永远等待，系统也不会永无顾客到
45、达。）系统中任一顾客不会永远等待，系统也不会永无顾客到达。则下列则下列Little公式成立（排队论中的通用公式）：公式成立（排队论中的通用公式）：（1）Lq=Wq我们知道一个顾客的平均排队等待时间是我们知道一个顾客的平均排队等待时间是Wq，且顾客是以平均速率，且顾客是以平均速率到到达，所以在时间达，所以在时间Wq内有内有Wq个顾客到达，个顾客到达，Lq表示排队等待服务的平均顾客表示排队等待服务的平均顾客数量，所以有：数量，所以有：Lq=Wq（2）L=W系统中的平均顾客数（包括等待的和正在被服务的顾客）等于顾客的平系统中的平均顾客数（包括等待的和正在被服务的顾客）等于顾客的平均到达速率乘以一个顾
46、客在系统中花费的平均时间。均到达速率乘以一个顾客在系统中花费的平均时间。（3）W=Wq+1/ 一个顾客在系统中花费的时间，就是它等待服务的时间加上被服务的时间。一个顾客在系统中花费的时间，就是它等待服务的时间加上被服务的时间。2021/6/1642排队论课件4队列分析的任务和假设条件队列分析的任务和假设条件队列分析的基本任务是：队列分析的基本任务是：给出如下输入信息（概率分布）：给出如下输入信息（概率分布）：到达速率（到达速率（）服务时间（服务时间（1/ )求出如下输出信息（均值、标准差）：求出如下输出信息（均值、标准差）：等待顾客的数量（等待顾客的数量（Lq,Lq）等待时间（等待时间（Wq，
47、wq）系统中顾客的数量（系统中顾客的数量（L，L）逗留时间（逗留时间（W，w）排队论中的假设：排队论中的假设：在排队分析中，最重要的一个假设是到达速率服从泊松分布，在排队分析中，最重要的一个假设是到达速率服从泊松分布，等效的说法是到达间隔时间服从指数分布，这又等价于说到达等效的说法是到达间隔时间服从指数分布，这又等价于说到达是随机的并彼此独立。我们几乎一直要作这一假定。没有它，是随机的并彼此独立。我们几乎一直要作这一假定。没有它，大部分的排队分析是不可能的。在这个假定的条件下，我们会大部分的排队分析是不可能的。在这个假定的条件下，我们会发现仅仅知道到达速率和服务时间的均值和标准差就可以得到发现
48、仅仅知道到达速率和服务时间的均值和标准差就可以得到许多有用的结果。许多有用的结果。2021/6/1643排队论课件模型之：模型之：M/M/c排队模型排队模型1.M/M/1模型模型顾客按照速率为顾客按照速率为的泊松过程到达，顾客的服务时间的泊松过程到达，顾客的服务时间是独立同分布的随机变量，通常分布设为均值为是独立同分布的随机变量，通常分布设为均值为1的的指数分布。假设顾客按照到达的顺序接受服务，即指数分布。假设顾客按照到达的顺序接受服务，即FCFS服务。例如，如果服务。例如，如果“顾客顾客”表示到达计算机系统表示到达计算机系统的作业任务，那么的作业任务，那么“服务台服务台”代表计算机系统。代表
49、计算机系统。另外一种另外一种M/M/1队列的解释为：顾客代表消息，而队列的解释为：顾客代表消息，而服务台代表通信信道。服务台代表通信信道。2021/6/1644排队论课件随机过程和概率论在排队论中的应用随机过程和概率论在排队论中的应用1.把排队过程看成生灭过程把排队过程看成生灭过程如果如果N（t）表示时刻）表示时刻t系统中的顾客数，则系统中的顾客数，则N（t），），t0就构成了一个随机过程。如就构成了一个随机过程。如果用果用“生生”表示顾客的到达，表示顾客的到达，“灭灭”表示顾客的离去，则对许多排队过程来说，表示顾客的离去，则对许多排队过程来说，N（t），），t0是一类特殊的随机过程是一类特殊
50、的随机过程-生灭过程生灭过程。服务员忙的时间比率：服务员忙的时间比率：=/=顾客到达速率顾客到达速率/服务速率，也称为服务强度服务速率，也称为服务强度。2.由生灭过程得到几何分布由生灭过程得到几何分布根据连续生灭过程稳定的条件，要求根据连续生灭过程稳定的条件，要求1，根据连续时间生灭过程的计算公式，以，根据连续时间生灭过程的计算公式，以得到系统在稳定状态下，有得到系统在稳定状态下，有k个顾客的概率如下：个顾客的概率如下：Pk=(1-)k,P0=1-对于稳定的系统对于稳定的系统(t=e(-)t2021/6/1649排队论课件2.M/M/c模型模型M/M/c队列模型如下队列模型如下：该队列系统的顾
51、客到达为泊松流，到达速率为该队列系统的顾客到达为泊松流，到达速率为，有并列的，有并列的c个服务台，每个服务台，每个服务台的服务速率为个服务台的服务速率为，服务规则为，服务规则为FCFS。所有的服务台共享一个公用。所有的服务台共享一个公用的队列。该队列是一个生灭过程模型，其生灭速率为：的队列。该队列是一个生灭过程模型，其生灭速率为：k=，k=0,1,2,k=ckc根据的生灭过程特点，可以得到下面在根据的生灭过程特点，可以得到下面在M/M/c队列中的常用公式。队列中的常用公式。C个服务台2021/6/1650排队论课件M/M/c模型系统运行指标模型系统运行指标系统的服务强度系统的服务强度，所有服务
52、台是空的概率，所有服务台是空的概率P0,所有服务所有服务台都在忙的概率台都在忙的概率P ,，平均等待顾客数量平均等待顾客数量Lq,系统中平均系统中平均顾客数量顾客数量L，平均系统逗留时间，平均系统逗留时间W,平均排队等候时间平均排队等候时间Wq,分别为：分别为：2021/6/1651排队论课件M/M/c模型系统运行指标模型系统运行指标等价地：系统中的平均顾客数量等价地：系统中的平均顾客数量L=c+P0(c)c/c!(1-)2其中，平均等待顾客数量其中，平均等待顾客数量Lq=P0(c)c/c!(1-)2令随机变量令随机变量M表示表示“忙忙”服务台的数量，服务台的数量，EM=c=/所以，任意一个服
53、务台的利用率所以，任意一个服务台的利用率=/（c）在多服务台系统中的在多服务台系统中的Little公式：公式：=/（c），L=Lq+c。 请同学们思考：一个M/M/c系统与c个M/M/1系统比较，那一种效率高？2021/6/1652排队论课件基本排队模型记号方案基本排队模型记号方案ServerQueueArrival顾客到达时间间隔分布顾客到达时间间隔分布/ /服务时间分布服务时间分布/ /服务台数目服务台数目/ /排队系统允许的最大顾客容量排队系统允许的最大顾客容量/ /顾客总体数量顾客总体数量/ /排排队规则队规则 ( (Kendall记号记号) )M/M/1/ / /FCFSM/M/1/
54、 M:负指数分布负指数分布(Markovian)D:定长分布定长分布(常数时间常数时间)Ek:k阶阶Erlang分布分布G:普通的概率分布普通的概率分布(任意概率分布任意概率分布)2021/6/1653排队论课件基本排队模型记号基本排队模型记号系统状态系统状态 : L=排队系统顾客的数量排队系统顾客的数量,队长。队长。 N(t) =在时间在时间 t 排队系统中顾客的数量。排队系统中顾客的数量。 Lq =等待服务的顾客的数量等待服务的顾客的数量,队列长度。队列长度。 Pn(t) =在时间在时间t,排队系统中恰好有排队系统中恰好有n个顾客的概率。个顾客的概率。 s = 服务台的数目。服务台的数目。
55、2021/6/1654排队论课件基本排队模型基本排队模型统计平稳条件下的记号统计平稳条件下的记号 n = 系统有系统有n个顾客时的平均到达率（单位时间内平均到个顾客时的平均到达率（单位时间内平均到达的顾客人数即是平均到达率）达的顾客人数即是平均到达率） n = 系统有系统有n个顾客时的平均服务率（单位时间内被服务个顾客时的平均服务率（单位时间内被服务完的顾客数即是平均服务率）完的顾客数即是平均服务率） =对任何对任何n都是常数的平均到达率都是常数的平均到达率.m =对任何对任何n都是常数的平均服务率都是常数的平均服务率.1/ =期望到达间隔时间期望到达间隔时间1/ =期望服务时间期望服务时间
56、=服务强度，服务强度， 或称使用因子，或称使用因子， / 2021/6/1655排队论课件统计平稳条件下的系统运行指标统计平稳条件下的系统运行指标平均系统队长平均系统队长平均等待队长平均等待队长平均排队等待时间平均排队等待时间平均系统逗留时间平均系统逗留时间2021/6/1656排队论课件L,W,Lq,Wq的关系的关系Littles formulae2021/6/1657排队论课件M/M/1/ / 或或M/M/1模型模型一个基本的排列模型一个基本的排列模型.顾客到达时间间隔以及服务时间都服从负指数分布，一个服顾客到达时间间隔以及服务时间都服从负指数分布，一个服务台。务台。 称为服务强度，与到达
57、率称为服务强度，与到达率 、服务率、服务率 满足：满足：2021/6/1658排队论课件M/M/1举例举例2021/6/1659排队论课件M/M/1/N/ 单一服务台，固定长度单一服务台，固定长度固定长度排队意味着若到了最大系统容量顾客将不能进固定长度排队意味着若到了最大系统容量顾客将不能进入系统入系统.2021/6/1660排队论课件M/M/1/N/ 举例举例2021/6/1661排队论课件增加更多服务台增加更多服务台M/M/c所有服务台是空的概率所有服务台是空的概率P0,和所有服务台都和所有服务台都在忙的概率在忙的概率P ,需要下面比较复杂的公式需要下面比较复杂的公式:2021/6/166
58、2排队论课件M/M/c举例举例2021/6/1663排队论课件其他模型，分类规则其他模型，分类规则M/M/c/K/K顾客来源是有限的服务系统顾客来源是有限的服务系统.例如：例如：一个饭店有一个饭店有X张桌子和张桌子和Y个服务生服务来源有限的顾客个服务生服务来源有限的顾客.M/D/1服务时间不变的服务系统服务时间不变的服务系统.D/M/1确定性到达模式确定性到达模式,及负指数分布服务时间及负指数分布服务时间.例如：例如：医生赴约治病的时间表医生赴约治病的时间表.M/Ek/1服务服从服务服从Erlang分布分布.例如：用相同平均时间例如：用相同平均时间去完成一些程序。去完成一些程序。2021/6/
59、1664排队论课件应用：应用：校园网的设计和调节收费校园网的设计和调节收费问题的提出：问题的提出：根据用户数量研究通信端口的设计规模，以及根据用户数量研究通信端口的设计规模，以及通过适当收取线路调节费来控制上网时间。通过适当收取线路调节费来控制上网时间。1）m个用户，每个用户平均每天（个用户，每个用户平均每天（16h计）上计）上网网1.5h，求，求n/m。(n为通信端口数为通信端口数)2）m=150,按设定的按设定的n讨论平均每个用户每天讨论平均每个用户每天上网上网1h,1.5h,2h,3h,4h,5h的可能性，线路忙的可能性，线路忙产生抱怨的可能性及通信端口的平均使用率产生抱怨的可能性及通信
60、端口的平均使用率3）给出一种合理的分段计时收取线路调节费）给出一种合理的分段计时收取线路调节费的方案。的方案。2021/6/1665排队论课件问题的分析：问题的分析：排队系统：由信息网络和用户构成排队系统：由信息网络和用户构成服务台服务台：网络的通信端口，个数：网络的通信端口，个数n顾客：用户，个数（顾客源数）顾客：用户，个数（顾客源数）m,顾客顾客总体无限（因为上网次数不限）总体无限（因为上网次数不限）平均忙期：一天连续工作实际时间，平均忙期：一天连续工作实际时间，16h系统服务：即时制（只要时间允许，不系统服务：即时制（只要时间允许，不限制上网人数，但不允许用户在系统内限制上网人数，但不允
61、许用户在系统内排队等候排队等候）2021/6/1666排队论课件问题的假设：问题的假设：1）每个用户上网随机独立，）每个用户上网随机独立，记记 为单位时间平均为单位时间平均到达（上网）率到达（上网）率2）n个通信端口的使用随机独立，记个通信端口的使用随机独立，记 为单位时为单位时间平均服务率（上网人数）间平均服务率（上网人数）3）顾客接受一次服务后仍回顾客总体）顾客接受一次服务后仍回顾客总体4）收费仅为了调节线路，控制上网时间，不追求）收费仅为了调节线路，控制上网时间，不追求经济利益。经济利益。5）不考虑现实生活中要收取的线路基本费。）不考虑现实生活中要收取的线路基本费。2021/6/1667
62、排队论课件模型的建立与求解：模型的建立与求解：用户平均上网人数（顾客平均到达率）服从参用户平均上网人数（顾客平均到达率）服从参数为数为 的泊松分布的泊松分布平均上网（服务）时间服从参数为平均上网（服务）时间服从参数为 的负指数的负指数分布分布排队模型为排队模型为:M/M/n/n/ （容量有限系统）（容量有限系统）顾客到达时间间隔分布顾客到达时间间隔分布/服务时间分布服务时间分布/服务台数目服务台数目/排队系统允许的最大顾客容量排队系统允许的最大顾客容量/顾客总体数量顾客总体数量/排队规则排队规则2021/6/1668排队论课件模型求解：模型求解：问题问题1，m个用户，每个用户平均每天（个用户，
63、每个用户平均每天（16h计）上网计）上网1.5h，求，求n/m。(n为通信端口数为通信端口数)T:每天总上网时间每天总上网时间2021/6/1669排队论课件问题问题2，m=150,按设定的按设定的n讨论平均每个用户讨论平均每个用户每天上网每天上网1h,1.5h,2h,3h,4h,5h的可能性，线路的可能性，线路忙产生抱怨的可能性及通信端口的平均使用率忙产生抱怨的可能性及通信端口的平均使用率通常通信端口为通常通信端口为16口、口、32口、口、64口、口、128口等口等每个用户每天上网时间为每个用户每天上网时间为1.5h时，时，即服务时间即服务时间1/=1.52021/6/1670排队论课件系统
64、满员率：系统满员率：系统可上网率系统可上网率单位时间端口的平均使用率单位时间端口的平均使用率 ：2021/6/1671排队论课件=12.4263-16*0.3906*0.8837=6.9035其它指标值：2021/6/1672排队论课件2021/6/1673排队论课件UNIT2排队网络模型排队网络模型在在工工程程实实践践中中，除除遇遇到到孤孤立立的的排排队队问问题题外外，分分析析人人员员还还经经常常遇遇到到多多个个互互连连排排队队的的问问题题，如如顾顾客客流流的的分分开开与与合合并并，队队列列的的串串并并连连组合等组合等。排队网络模型排队网络模型就是来解决这些问题。就是来解决这些问题。主主要要
65、包包括括开开环环排排队队网网络络和和闭闭环环排排队队网网络络，具体应用具体应用请查阅相关资料请查阅相关资料。2021/6/1674排队论课件QuickPassQuickPass系统系统排队问题排队问题UNIT3应用之：应用之：2021/6/1675排队论课件在游乐园中的频频排队在游乐园中的频频排队会极为扫兴会极为扫兴DisneyLand中中的的FastPass(QuickPass)系统系统就是想解决这就是想解决这个问题的个问题的2021/6/1676排队论课件WhatisQuickPass?工作原理：工作原理：v到达的顾客将自己的票插入到达的顾客将自己的票插入FastPass的的slot中中v
66、FastPass计算出建议顾客返回计算出建议顾客返回的时间间隔的时间间隔(time interval)或或时间点或时间窗时间点或时间窗(time window)v顾客无需排队，在指定的时间顾客无需排队，在指定的时间返回就可持票进入返回就可持票进入2021/6/1677排队论课件怎样缩短排队的等待时间？怎样缩短排队的等待时间？银行的排队叫号机银行的排队叫号机只是有序的组织了顾客，并没有减少等待时只是有序的组织了顾客，并没有减少等待时间间如果能实现知道轮到自己需要等待多少时间，如果能实现知道轮到自己需要等待多少时间，再选择合适的时间来，岂不很好？再选择合适的时间来，岂不很好？2021/6/1678
67、排队论课件FastPass存在的问题：存在的问题：预知的返回时间间隔存在误差预知的返回时间间隔存在误差按时返回却仍需要排队按时返回却仍需要排队建议的返回时间间隔太长建议的返回时间间隔太长如果告诉你如果告诉你4小时以后再回来呢？小时以后再回来呢？顾客可能不会完全按照安排的时间返回顾客可能不会完全按照安排的时间返回如果新来的顾客不想使用如果新来的顾客不想使用FastPass系统？系统？2021/6/1679排队论课件我们的目的我们的目的就是对就是对FastPass系统建立系统建立合理的合理的离散统计模型（离散统计模型（DistributedStatisticalModel），求出最优的顾客返回时，
68、求出最优的顾客返回时间。间。 建模的一般步骤建模的一般步骤以及：以及：* * 模型的改进模型的改进* * 启发与待解决的问题启发与待解决的问题2021/6/1680排队论课件1模型的假设模型的假设游乐园开放时间为游乐园开放时间为8:00-18:00,一天中不同时一天中不同时间的顾客流量不同，比如上午间的顾客流量不同，比如上午10:00和下午和下午3:00的顾客流量是最大的。的顾客流量是最大的。顾客的到达时间符合非时间齐次泊松过程顾客的到达时间符合非时间齐次泊松过程(NonhomogeneousPossionProcess)，到达速率是到达速率是(t)。2021/6/1681排队论课件Poiss
69、onProcess2021/6/1682排队论课件PoissonProcess2021/6/1683排队论课件分析分析1：能否得到准确的返回时间？：能否得到准确的返回时间？ 2 在我们开始动手建模之前，先要问几个问题：2021/6/1684排队论课件分析分析2：使用：使用FastPass后排队是不是可以避免的后排队是不是可以避免的？FastPass给出的返回时间只是期望值，而非确定给出的返回时间只是期望值，而非确定值值假设所有的顾客都使用假设所有的顾客都使用FastPass,但需考虑有的顾但需考虑有的顾客可能会不遵守客可能会不遵守FastPass给出的返回时间给出的返回时间 2 在我们开始动手
70、建模之前，先要问几个问题：2021/6/1685排队论课件分析分析3：我们优化的目标函数（或：我们优化的目标函数（或costfunction）是什么？是排队时间吗？）是什么？是排队时间吗？ 2 在我们开始动手建模之前，先要问几个问题：2021/6/1686排队论课件优化问题的目标函数为：优化问题的目标函数为：3 模型的建立（1）目标函数2021/6/1687排队论课件根据排队论（根据排队论（queueingtheory）的分类规则）的分类规则,（X/Y/Z/A）代表一类排队的规则，其中）代表一类排队的规则，其中X:顾客流到达所符合的分布顾客流到达所符合的分布Y:顾客接受服务的时间所服从的分布顾
71、客接受服务的时间所服从的分布Z:服务台的个数服务台的个数A:服务台一次可服务的顾客数量（系统的容量）服务台一次可服务的顾客数量（系统的容量）针对各个游乐项目的特点，我们主要讨论两种排队针对各个游乐项目的特点，我们主要讨论两种排队系统系统:模型的建立（2） 排队模型的分类2021/6/1688排队论课件特点：系统容量为特点：系统容量为1，顾客的到达是，顾客的到达是Poisson流，流，服务时间服从指数分布，只有一条队列服务时间服从指数分布，只有一条队列模型的建立（3） 电话亭模型2021/6/1689排队论课件求出这类系统的代价函数表达式求出这类系统的代价函数表达式模型的建立（3）电话亭模型20
72、21/6/1690排队论课件近似将总的优化目标函数等效为对顾客近似将总的优化目标函数等效为对顾客i的目的目标函数：标函数：模型的建立（3）电话亭模型2021/6/1691排队论课件模型的建立（3）电话亭模型2021/6/1692排队论课件如果简化如果简化c1,c2为常数，并计算第二个人的无为常数，并计算第二个人的无需等待返回时间的期望值，得需等待返回时间的期望值，得用用MatLab能够作出能够作出的函数，并从图中的函数，并从图中得出结果得出结果模型的求解（4）电话亭模型2021/6/1693排队论课件模型的求解（4）电话亭模型Averagecalltime(min*10)U2t2508.051
73、617.08023.051632.52021/6/1694排队论课件第三个人的无需等待返回时间的期望值，同第三个人的无需等待返回时间的期望值，同理可以算出，并用图解法求出理可以算出，并用图解法求出模型的求解（4）电话亭模型2021/6/1695排队论课件但是第但是第4个人，第个人，第5个个人人呢？呢？这种方法太繁琐似乎不这种方法太繁琐似乎不好用好用可否有近似的算法？可否有近似的算法？2021/6/1696排队论课件与前一个模型的区别在于：与前一个模型的区别在于：系统容量是系统容量是c1,服务时间服务时间固定，顾客的到达仍然是固定，顾客的到达仍然是Poisson流。流。模型的建立（5） 过山车模
74、型2021/6/1697排队论课件还要考虑：还要考虑：实际的实际的FastPass系统系统有两条队列：有两条队列：FastPass和和Standby队列队列不考虑不考虑standby队列，队列，将得到将得到Greedyalgorithm模型模型考虑考虑standby队列，队列，将得到效用函数模型将得到效用函数模型模型的建立（5）过山车2021/6/1698排队论课件2021/6/1699排队论课件最简单的情况：最简单的情况：最简单的情况：最简单的情况：只有一条队列，即所有的人都只用只有一条队列，即所有的人都只用FastPass系统系统为了防止前面的人等的时间太长，过山车只要载满为了防止前面的人
75、等的时间太长，过山车只要载满一定数量的人后就开车，假设为一定数量的人后就开车，假设为80c。用用贪心算法（贪心算法（greedyalgorithm),将每个顾客尽量将每个顾客尽量安排在离顾客到达时间最近的，且还没有安排满人安排在离顾客到达时间最近的，且还没有安排满人的一班车上。的一班车上。假设被安排的顾客按照假设被安排的顾客按照Beta分布到达所被安排的时分布到达所被安排的时间段内间段内模型的建立（5）过山车模型2021/6/16100排队论课件贪心算法贪心算法模型的建立（5）过山车模型2021/6/16101排队论课件很容易想到，全局优化的目标变量很容易想到，全局优化的目标变量1.如果开车的
76、时间不固定，则如果开车的时间不固定，则a%是多少最优？是多少最优？就是说顾客坐满多少就开车？就是说顾客坐满多少就开车？2.如果如果开车的时间间隔开车的时间间隔是固定的，则多长时间开是固定的，则多长时间开一次是最优的？一次是最优的？衡量的标准：目标函数衡量的标准：目标函数模型的建立（5）过山车模型2021/6/16102排队论课件一个区间内的顾客返回示意图一个区间内的顾客返回示意图2021/6/16103排队论课件目标函数：目标函数：模型的建立（5）过山车模型2021/6/16104排队论课件模型的建立（5）过山车模型怎样求解最优的a%c和最优的开车间隔？对于这类复杂的问题，离散仿真是最好的方法
77、了2021/6/16105排队论课件仿真：用计算机生成一些符合某种分布的随机数据仿真：用计算机生成一些符合某种分布的随机数据点，模拟离散时间的发生点，模拟离散时间的发生这里的仿真用这里的仿真用MatLab完成：完成：步骤：步骤：1.生成生成Poisson顾客流（模拟到达时间）顾客流（模拟到达时间）2.给定不同的给定不同的a%c,开车时间间隔不定，计算开车时间间隔不定，计算代价函数，画出代价函数性能曲线代价函数，画出代价函数性能曲线3.开车时间固定，给出不同的开车时间间隔，开车时间固定，给出不同的开车时间间隔，计算画出代价函数性能曲线计算画出代价函数性能曲线4.得出最优的结论得出最优的结论模型的
78、仿真（5）过山车模型2021/6/16106排队论课件过山车模型的仿真（5.1）得到在第在第j天的某一固天的某一固定时刻定时刻i采集样本采集样本,i=1m,j=1100形成样本空间的形成样本空间的矩阵矩阵2021/6/16107排队论课件过山车模型的仿真（5.1）用列向量的均值用列向量的均值估计参数估计参数样本的更新用时间序列样本的更新用时间序列的方法（的方法（timeserialanalysis）,计算列向计算列向量的量的Eucilid距离距离dthreshold就更新一次就更新一次2021/6/16108排队论课件对某一个或一组变量对某一个或一组变量x(t)进行观察测量，将在进行观察测量，
79、将在一系列时刻一系列时刻t1,t2,tn (t为自变量且为自变量且t1t2tn )所得到的离散数字组成序列集合所得到的离散数字组成序列集合x(t1),x(t2),x(tn)称为时间序列，这种有时间意义的序列也称为称为时间序列，这种有时间意义的序列也称为动态数据。时间序列分析是根据系统观测得动态数据。时间序列分析是根据系统观测得到的时间序列数据，通过曲线拟合和参数估到的时间序列数据，通过曲线拟合和参数估计来建立数学模型的理论和方法计来建立数学模型的理论和方法时间序列分析（time serial analysis）2021/6/16109排队论课件生成的生成的样本空样本空间间过山车模型的仿真（5.
80、1）实用的一种模拟Poisson流的方法：某个区间 个顾客到达时间Uniform2021/6/16110排队论课件Poisson流顾客到达时间流顾客到达时间过山车模型的仿真（5.2）按照贪心算法指定的顾客乘坐的过山车的班次2021/6/16111排队论课件两种两种a%c的情况下顾客等待时间的情况下顾客等待时间过山车模型的仿真（5.3）2021/6/16112排队论课件a%c的性能曲线：可见的性能曲线：可见a%c=70最优最优过山车模型的仿真（5.3）2021/6/16113排队论课件开车间隔的优化：开车间隔的优化：但但costfunction是间隔的单是间隔的单增增函数？怎么办？函数？怎么办？
81、过山车模型的仿真（5.4）2021/6/16114排队论课件解决：考虑开车的成本：开车的时间间隔越短，解决：考虑开车的成本：开车的时间间隔越短，次数愈多，运行成本越大找次数愈多，运行成本越大找平衡点平衡点4.67min最优最优过山车模型的仿真（5.4）2021/6/16115排队论课件6 模型的稳健性与优缺点电话亭模型较精确，虽可行但复杂电话亭模型较精确，虽可行但复杂过山车模型的贪心算法，简单，但不是最优过山车模型的贪心算法，简单，但不是最优（quasi-optimal）Standby队列会有什么影响？队列会有什么影响？每个人的每个人的c1和和c2可能不同可能不同2021/6/16116排队论
82、课件将顾客的到达看成是顾客流将顾客的到达看成是顾客流(traffic),用用TrunkingTheory中的中的ErlangC公式，能够得出阻塞概率公式，能够得出阻塞概率P(Block)，系统容量，系统容量C，顾客流的强度，顾客流的强度A（）三）三者的关系者的关系平均队列长度为：平均队列长度为：可将顾客安排在一天之内平均队列短的时刻可将顾客安排在一天之内平均队列短的时刻7 过山车模型的改进 2021/6/16117排队论课件ErlangC的图形的图形7 过山车模型的改进2021/6/16118排队论课件统计得出的队列长统计得出的队列长度，以及仿真得出度，以及仿真得出的实际队列长度的实际队列长度
83、说明可以用统计说明可以用统计曲线作安排返回时曲线作安排返回时间的依据间的依据7 过山车模型的改进2021/6/16119排队论课件改进算法的效果改进算法的效果7 过山车模型的改进2021/6/16120排队论课件7 过山车模型的改进统计队列长度曲线应该实时更新！但是：可能所有的顾客都被安排到同一个队列长度短的时段了2021/6/16121排队论课件如果考虑如果考虑Standby队列？队列？7 过山车模型的改进使用边际效用函数(Marginal Utility Function)的思想：FastPass队列中每增加一个人，会对Standby队列中的人造成目标函数的损失2021/6/16122排队
84、论课件使用使用IC卡门票，记录顾客的特点，数据集中在卡门票，记录顾客的特点，数据集中在中心数据库中心数据库给顾客提供预计的当天实时队列长度表，顾客给顾客提供预计的当天实时队列长度表，顾客可自己选择返回时间，选择可自己选择返回时间，选择t1,t2时间的长度时间的长度你的更好的办法？你的更好的办法？8 将来的工作：设计更好的FastPass系统2021/6/16123排队论课件怎样写数学建模论文？怎样写数学建模论文？怎样求解没有显式表达的式子？怎样求解没有显式表达的式子？如何模拟离散随机时间？如何模拟离散随机时间？如何通过仿真的结果求参数的优化如何通过仿真的结果求参数的优化使用数学软件，仿真的过程
85、中常常也会使用数学软件，仿真的过程中常常也会得到得到新的想法与结新的想法与结论论灵活借鉴其他学科中的方法：如灵活借鉴其他学科中的方法：如Queueingtheory(排队论排队论),TrunkingTheory(复用论复用论),GreedyAlgorithm（贪心算法）（贪心算法）,MarginalUtilityFunction(边际效用函数边际效用函数)9 启发与收获2021/6/16124排队论课件结束语结束语排队论排队论(queueingtheory),或称随机服务系统理论或称随机服务系统理论,是数学是数学运筹学的分支学科。它是研究服务系统中排队现象随机规律运筹学的分支学科。它是研究服务
86、系统中排队现象随机规律的学科。广泛应用于计算机网络的学科。广泛应用于计算机网络,生产生产,运输运输,库存等各项库存等各项资源共享的随机服务系统。资源共享的随机服务系统。排队论研究的内容有排队论研究的内容有3个方面：统计推断，根据资料建立模个方面：统计推断，根据资料建立模型；系统的性态，即和排队有关的数量指标的概率规律性；型；系统的性态，即和排队有关的数量指标的概率规律性；系统的优化问题。其目的是正确设计和有效运行各个服务系系统的优化问题。其目的是正确设计和有效运行各个服务系统，使之发挥最佳效益。统，使之发挥最佳效益。实际建模中常和图论，时间序列分析等等其它方法结合使用，实际建模中常和图论，时间序列分析等等其它方法结合使用，同学们可参考历年真题。同学们可参考历年真题。最后，预祝大家竞赛取得突出成绩！最后，预祝大家竞赛取得突出成绩！_2021/6/16125排队论课件 结束语结束语若有不当之处，请指正，谢谢！若有不当之处，请指正，谢谢！
