《排队论讲义建模A题专用.pptx》由会员分享，可在线阅读，更多相关《排队论讲义建模A题专用.pptx（125页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、排队论课件1CONTENTSPREPARATION:概率论与随机过程UNIT1排队模型UNIT2排队网络模型UNIT3应用之：QUICKPASS系统结束语第1页/共125页排队论课件2PREPARATION概率论和随机过程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
2、),(4,3),(5,2)和(6,1)为所求。所以NA=6，从而 p=6/36=1/6。第2页/共125页排队论课件3(2)相对频率定义：P(A)=lim nA/n n其中n是实验的次数，nA是A发生的次数 例2 投硬币 在大数量投掷后，硬币的正面在上的可能性在0.5左右，上下两面在上面具有相同的概率。(3)公理化定义：从一定数量的定义概率度量的公理出发，经过推导规则达到概率的有效计算。这些公理包括：（a）对于每一个事件A，有0P（A）1（b）P（）=1（c）如 果 A和 B是 互 斥 的，则 P（AUB）=P（A）+P（B）第3页/共125页排队论课件42 条件概率和独立性 条件概率：假定事
3、件B已经发生时，事件A发生的条件概率P(A|B)可以定义如下：P（A|B）=P（AB）/P（B）独立性：如果P(AB)=P(A)P(B)，事件A和B叫做相互独立的事件独立性的概念可以推广到三个或多个事件。第4页/共125页排队论课件53 全概率公式和贝叶斯定理全概率公式：给定一组互斥事件E1，E2，En，这些事件的并集包括所有可能的结果，同时给任一个任意事件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)也称为后验概率公式，是在已知结果发生的情况下，
4、求导致结果的某种原因的可能性的大小。第5页/共125页排队论课件6Part2.随机变量的数字特征随机变量X是样本点的函数，它的定义域是样本空间，值域是实数集R，即 X：R随机变量的数字特征对研究随机变量是很重要的，常用的数字特征有：数学期望、方差、协方差和相关系数。1 数学期望：连续情况：EX=x=xf(x)dx积分区间从-，离散情况：EX=x=kPx=k all k 它是一种统计平均值，简称均值2 方差：DX=E(X-x)2=EX2-x2 它是度量随机变量X与其均值EX的偏离程度。均方差：方差的开方称为均方差，或标准方差，记为x二阶矩：连续情况：EX2 =x2f(x)dx 积分区间从-，离散
5、情况：EX2 =k2Px=k all k第6页/共125页排队论课件73 协方差：两个随机变量X和Y的协方差定义如下：Cov(X,Y)=E(X-x)(Y-y)=EXY-EXEY4 相关系数:两个随机变量X和Y的相关系数定义如下：r(X,Y)=Cov(X,Y)/xy相关系数是两个随机变量线性相关程度的度量。例3：设随机变量（X，Y）的分布律如下：Y X 1 2 1 -10 1/4 求 E(X),D(X),E(Y),D(Y),cov(X,Y),r(X,Y)第7页/共125页排队论课件8Part3几种重要的概率分布1 贝努里分布它的概率分布为：PX=1=p，PX=0=1-p它也称两点分布或（0-1）
6、分布。它描述一次贝努里实验中，成功或失败的概率。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次贝努里实验中首次出现成功的概率。第8页/共125页排队论课件9n几何分布有一个重要的性质-后无效性：在前n次实验未出现成功的条件下，再经过m次实验（即在n+m次实验中）首次出现成功的概率，等于恰好需要进行m次实验出现首次成功的无条件概率。用式子表达：nPX=n+m|Xn=PX=m (请同学们试证明之）n这种与过去历史无关的性质称为马尔可夫性。n几何分布在我们下面讲的排队论中是非
7、常重要。它可以描述某一任务（或顾客）的服务持续时间。n4 泊松分布（Poisson）nPX=k=k e-/k!k=0,1,2,n泊松分布是最重要的离散型概率分布之一，它作为表述随机现象的一种形式，在计算机性能评价等实践中扮演了重要的角色。n在实际系统模型中，一般都要假定任务（或顾客）的到来是服从泊松分布的。实践也证明：这种假设是有效的。第9页/共125页排队论课件105 （负）指数分布它是一种连续型的概率分布，它的概率密度为f（x）=e-x x0 0 x0,t0，有 Ps+t|s=Pt 在离散型随机变量中，只有几何分布具有无后效性。这两种分布可以分别用来描绘离散等待时间和连续等待时间。在排队理
8、论中，指数分布是很重要的。第10页/共125页排队论课件11 6 k-爱尔朗分布概率密度:f(x)=(kx)n-1ke-kx/(n-1)!x0，0.0 x0数字特征：EX=1/;VarX=1/（k2）如果k个随机变量Xi，i=1，2，,k,分别服从指数分布，那么随机变量X=X1+X2+Xk服从爱尔朗分布。即：具有k-爱尔朗分布的随机变量可以看作具有同一指数分布的独立的k个随机变量之和。k-爱尔朗分布在排队模型中，得到广泛应用。如：假定顾客在到达窗口排队必须通过一个关口，这个关口由k层构成，通过每层的时间服从参数为的指数分布，这样顾客通过整个关口到达窗口排队时，就实现了爱尔朗分布。如下图：k21
9、0000窗口第11页/共125页排队论课件12Part4随机过程 随机过程是定义在给定的概率空间上的一族随机变量X(t)，t T。我们知道：一个随机变量是定义在样本空间S上的函数，则随机过程实际上就是一个函数族X（t，s）|s S，t T。若t固定，随机过程X（t，s）就是随机变量X（t）所取的值，称为在t时刻的状态。若s固定，它是t的函数，称为随机过程的样本函数或样本曲线。第12页/共125页排队论课件13随机过程的例子为了更好的理解随机过程，我们从一个例子开始。例如，n个同样的电阻，同时记录它们热噪声的电压波形。电阻上的热噪声是由于电阻中的电子的热运动引起的，因此，在t1时刻电阻上的热噪声
10、电压是一个随机变量，并记为x(t1)，也就是说t1时刻任一电阻r(i)上的噪声电压x(i,t1)是无法预先确切地知道的。这里n支电阻的热噪声电压的集合是这个随机实验的样本空间S。对于某一支电阻，其热噪声电压是一时间函数x(i，t)，是随机过程的样本函数。对所有电阻来说，其热噪声电压就是一族时间函数，记为x(t)，这族时间函数就是“随机过程”，族中每一时间函数称为随机过程的样本函数。第13页/共125页排队论课件14Part5马尔可夫过程马尔可夫过程(MarkovProcess)是具有无后效性的随机过程。无后效性是指：当过程在tn时刻所处的状态为已知时，过程在大于tn的时刻所处状态的概率特性只与
11、过程在tn时刻所处的状态有关，而与过程在tn时刻以前的状态无关。换言之，对于随机过程X（t），tT，如果对于任意参数 t0t1t2tn1有pij=0(2)连续时间生灭过程一个连续时间，状态空间S=0，1，2为可数集的齐次马尔可夫过程X(t)，t0，,称为生灭过程。时齐性转移概率Pij(t,)只与i,j,-t有关，即Pij()=Pij(t,t+)第15页/共125页排队论课件16练习练习：1。有10个电阻，其电阻值分别为1，2，10，从中取出三个，要求取出的三个电阻，一个小于5，一个等于5，另一个大于5，问：取一次就能达到要求的概率。2一袋内装有5只球，编号为1，2，3，4，5，从中任取3只，求
12、被抽取3只球中，中间号码X的分布规律。第16页/共125页排队论课件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时，则另外两只球必须分别在号码小于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.3第17页/共125页排队论
13、课件18UNIT1排队模型 排队论（queueing theory），或称随机服务系统理论，作为运筹学研究的一种有力手段，研究的内容有3个方面：系统的性态，即与排队有关的数量指标的概率规律性；系统的优化问题；统计推断，根据资料合理建立模型。目的是正确设计和有效运行各个服务系统，使之发挥最佳效益。排队论不仅在理论上达到了成熟阶段，而且其应用范围不断增加。概括起来，它已在电话交换网、公路、铁路、航空运输、工程管理、公共服务、货物存储和生产流水线过程等方面得到了广泛的应用。特别地，排队论是计算机通信网络和计算机系统中通信信息量研究的基础理论，信息系统通信问题的定量研究往往要求借助于排对论才能得到解决
14、。第18页/共125页排队论课件19排队常常是件很令人恼火的事情常常是件很令人恼火的事情尤其是在我们这样的人口大国尤其是在我们这样的人口大国电话亭1978年在北京15%的电话要在1小时后才能接通。在电报大楼打电话的人还要带着午饭去排队银行窗口，ATM游乐场的游乐项目医院、理发、火车售票在现实生活中，为了接受某种服务，排队等待是常见的现象。从排队等待得到抽象的物理模型，进一步建立数学模型的一整套理论就是所谓的排队论。第19页/共125页排队论课件20什么是排队论？排队论是专门研究带有随机因素，产生拥挤现象的优化理论。亦称为随机服务系统理论。因为被服务者到达系统的时间是不确定的。有关于由服务设施与
15、被服务者构成的排队服务系统的理论。第20页/共125页排队论课件21本讲主要掌握：基本模型M/M/1模型M/M/c模型其他模型应用：校园网的设计和调节收费第21页/共125页排队论课件22基本的排队模型基本的排队模型基本组成概念与记号指数分布和生灭过程第22页/共125页排队论课件23典型排队系统模型 顾客到达:在队列中排队服务台服务顾客离开输入源的到达规律队列大小？特性？到达方式？服务规律？服务协议？在本单元中，我们主要介绍排队系统的组成和特征，排队系统的到达和服务，经典排队模型等内容。顾客到达规律和服务规律都是通过概率来描述的，所以概率论是排队论的基础。输入源。第23页/共125页排队论课
16、件24基本组成基本组成输入来源队列服务机构排队系统排队系统顾客服务完离开排队系统的三个基本组成部分.输入过程(顾客按照怎样的规律到达);排队规则(顾客按照一定规则排队等待服务);服务机构(服务机构的设置,服务台的数量,服务的方式,服务时间分布等)第24页/共125页排队论课件25基本排队模型基本排队模型输入过程输入过程顾客来源有限/无限顾客数量有限无限经常性的顾客来源顾客到达间隔时间:到下一个顾客到达的时间.服从某一概率分布.(指数分布)顾客的行为假定在未服务之前不会离开;当看到队列很长的时候离开；从一个队列移到另一个队列。顾客到达的方式通常是一个一个到达顾客到达的方式通常是一个一个到达的，也
17、可能是成批的。顾客的到达总是有的，也可能是成批的。顾客的到达总是有一定规律，即到达过程或到达时间间隔符一定规律，即到达过程或到达时间间隔符合一定的分布，称合一定的分布，称到达分布。到达分布。顾客的到达或到达时间通常假定为相顾客的到达或到达时间通常假定为相互独立的且遵从同一分布的互独立的且遵从同一分布的随机变量。随机变量。第25页/共125页排队论课件26基本排队模型队列基本排队模型队列/排队规则排队规则d队列队列容量有限/无限排队方式单队列并联式多队列串联式多队列杂乱队列 对于一个有限大小的队列来对于一个有限大小的队列来说，顾客可能从队列中丢失。说，顾客可能从队列中丢失。有什么样的服务协议就有
18、什么有什么样的服务协议就有什么样的与之对应的排队方式。样的与之对应的排队方式。第26页/共125页排队论课件27基本排队模型服务规则基本排队模型服务规则服务机构服务设施，服务渠道与服务台服务台数量单服务台系统多服务台系统无限服务台系统服务协议先来先服务（FCFS）后来先服务（LCFS）随机服务（RSS）有优先权的服务（PR）服务时间分布指数,常数,k阶Erlang 一般服务台对顾客是一个一个一般服务台对顾客是一个一个进行服务的，且对每一个顾客的进行服务的，且对每一个顾客的服务时间服务时间长短不一。长短不一。将将服务时间服务时间看作看作随机变量随机变量，那么那么它们是相互独立的且遵循同一分它们是
19、相互独立的且遵循同一分布。因此描述服务规律时，采用布。因此描述服务规律时，采用服务时间的概率分布，即服务时间的概率分布，即服务分服务分布布。服务分布同到达分布一样，到服务分布同到达分布一样，到底属于哪一种概率分布，要根据底属于哪一种概率分布，要根据具体排队问题进行分析。具体排队问题进行分析。第27页/共125页排队论课件28服务协议（a）先来先服务 顾客到达的先后次序排队接受服务，用 FCFS（firstcomefirstserved）表示。（b）后来先服务（或称先来后服务）队列是一种堆栈形式（临时寄存货物的地方）。当某一顾客服务结束时，如果在队列中有两个以上等待的顾客，则把最后到达的顾客作为
20、下一个服务的对象。用LCFS（lastcomefirstserved）表示。（c）随机选择服务 在服务时从等待顾客中随意抽取一个进行服务。（d）优先服务和动态优先服务 预先规定优先顺序位的类别、且给到达顾客规定优先顺序位作为标记的优先权。通常按FCFS进行服务。优先权分为三类：排队优先权、中断优先权、动态优先权。如计算机中断的优先级。（e）处理器共享（processor sharing，PS）服务台的处理能力被平均分配给队列中的所有顾客，没有排队现象出现，当顾客的数量增加时，只是顾客的服务时间变长。如：网络服务系统。（f）无限服务台（infinite server，Is）在这种情况下，队列中的
21、每个顾客接受完全相同的服务，而且就好像它是唯一的一个顾客一样。好像对于每个顾客都可以“克隆”出一个新的服务台，而且克隆的数目可以无限。第28页/共125页排队论课件29排队系统的到达和服务1 到达规律的描述（1）主要描述参数（a）到达时点 将某一时刻设为t0，顾客依次到达的时刻用t-1t0t1t2表示，如果在时刻tk到达的顾客为Nk，则到达时点可用tk、Nk）表示。（b）平均到达间隔一个顾客到达时刻之间的时宽为到达间隔。（c）到达速率单位时间到达顾客的平均数叫到达速率，也称到达密度或输入速率。（2）到达规律 顾客的到达规律可以用概率来描述，两个顾客到达的时间间隔是独立的随机变量，服从同一概率分
22、布时。常用的分布规律有：（a）一般到达（b）泊松到达（c）爱尔朗到达（d）等间隔到达第29页/共125页排队论课件30泊松分布和负指数分布在排队论中的应用 泊松分布（Poisson）：PX=k=ke-/k!k=0,1,2,，x=x=泊松分布是最重要的离散型概率分布之一，也是表述随机现象的一种重要形式。在实际系统模型中，一般都要假定任务（或顾客）的到来是泊松分布的。实践也证明：这种假设有效。如果顾客到达的人数是符合泊松分布，即在时间T内到达有k个顾客到达的概率为：p=（T）ke-T/k!，在时间T内顾客到达的平均顾客数=T，平均到达速度（顾客数/秒）=服从泊松分布过程的到达被认为是随机到达，因为
23、当顾客根据泊松过程到达时，顾客在各个时刻到达的可能性相同并与其它顾客的到达无关。第30页/共125页排队论课件31（负）指数分布：它是一种连续型的概率分布，它的概率密度：f（x）=e-xx0 它的分布函数：F（x）=1-e-xx0指数分布的一个有用的性质是它的数学期望等于标准差：x=x=1/泊松分布和指数分布的关系：如果顾客以泊松到达,则顾客到达的时间间隔Ta服从指数分布，即：PTat=1-e-t,ETa=1/因此，平均到达的时间间隔是到达速率的倒数。第31页/共125页排队论课件32负指数分布负指数分布密度函数密度函数均值均值方差方差随机变量 T（两个顾客相继到达的时间间隔）分布函数分布函数
24、 fT(t)t第32页/共125页排队论课件33负指数分布性质负指数分布性质1fT(t)tttfT(t)是一个严格下降函数第33页/共125页排队论课件34负指数分布性质负指数分布性质2无后效性（无记忆性）无后效性（无记忆性）不管多长时间不管多长时间(t)已经过去，已经过去，逗留时间的概率分布与下逗留时间的概率分布与下一个事件的相同一个事件的相同.或者说，后一个顾客到来所需时间与或者说，后一个顾客到来所需时间与前一个顾客到来所需时间无关。前一个顾客到来所需时间无关。第34页/共125页排队论课件35负指数分布性质负指数分布性质3几个独立的指数分布的随机变量的最小也服从指数分布几个独立的指数分布
25、的随机变量的最小也服从指数分布几个独立的指数分布的随机几个独立的指数分布的随机变量的和还是一个服从指数变量的和还是一个服从指数分布的随机变量分布的随机变量T1(1)T1(2)T1(3)T(1+2+3)第35页/共125页排队论课件36负指数分布性质负指数分布性质4负指数分布Poisson分布在t时间内已经服务n个顾客的概率1/:平均服务时间平均服务率=相继顾客到达平均间隔时间第36页/共125页排队论课件37负指数分布性质负指数分布性质5第37页/共125页排队论课件38排队论基本概念部分练习练习1：1。指出下列排队系统中的顾客和服务台：（1）自行车修理店；（2）按客户订单进行加工的加工车间（
26、3）机场起飞的客机（4）十字路口红灯前的车辆2。判断正误（1）若到达排队系统的顾客人数服从泊松分布，则依次到达的两名顾客之间的间隔时间服从指数分布。（2）在一个排队系统中，不管顾客到达和服务时间的情况如何，只要运行时间足够长的时间后，系统将进入稳定状态。（3）在排队系统中，顾客等待时间的分布不受排队规则的影响。第38页/共125页排队论课件392服务规律的描述(1)主要描述参量 （a）平均服务时间 设服务时间的分布函数为F（t），则服务时间的平均表示为:1/=t dF(t)其中称为平均服务速率，平均一个顾客的服务时间。（b）服务速率 一般指平均服务速率，单位时间内被服务完的顾客数，用来表示。(
27、2)服务规律 服务规律通常是就服务时间的分布而言的。服务时间分布典型地有指数分布、爱尔朗分布、一般分布等。结论：顾客到达规律和服务规律都是通过概率来描述的，所以概率论是排队论的基础。第39页/共125页排队论课件40经典排队模型它的格式为：ABnSZ 其中符号的含义如下：A：顾客到达的规律；B：服务时间分布；n：服务台的数目；S：队列容量的大小；Z：服务规程。当队列的大小为无穷大、且服务规程为先来先服务时，经典排队模型可简化为ABn 不同类型的排队，A、B可用如下约定的字母表示。M：如果用于描述到达，表示泊松到达过程，到达时间间隔符合指数分布；如 果用于描述服务，则指具有指数分布的时间。M表示
28、Markov的第一个字母。G：一般分布。表示到达间隔时间或服务时间服从一般分布。G是General的第 一个字母。Ek：k-爱尔朗分布。表示到达间隔时间或服务时间服从k-爱尔朗分布。E是Erlang的第一个字母。D:定长分布(常数时间)H：超几何分布。L：H项式分布。Z代表的服务规程典型的有：FCFS：先来先服务；LCFS：后来先服务；RSS：随机选择服务；PR：优先权服务。Ba：集体（批量）服务。GD：一般规约服务，即通用规约服务。第40页/共125页排队论课件413基本排队关系在对排队进行分析时，为了便于分析，经常做一些简化假设。对一个排队系统，若满足以下三个条件：（1）排队系统能够进入统
29、计平衡状态；（2）服务员的忙期与闲期交替出现，即系统不是总处于忙的状态；（3）系统中任一顾客不会永远等待，系统也不会永无顾客到达。则下列Little公式成立（排队论中的通用公式）：（1）Lq=Wq我们知道一个顾客的平均排队等待时间是Wq，且顾客是以平均速率到达，所以在时间Wq内有Wq个顾客到达，Lq表示排队等待服务的平均顾客数量，所以有：Lq=Wq（2）L=W系统中的平均顾客数（包括等待的和正在被服务的顾客）等于顾客的平均到达速率乘以一个顾客在系统中花费的平均时间。（3）W=Wq+1/一个顾客在系统中花费的时间，就是它等待服务的时间加上被服务的时间。第41页/共125页排队论课件424队列分析
30、的任务和假设条件队列分析的基本任务是：给出如下输入信息（概率分布）：到达速率（）服务时间（1/)求出如下输出信息（均值、标准差）：等待顾客的数量（Lq,Lq）等待时间（Wq，wq）系统中顾客的数量（L，L）逗留时间（W，w）排队论中的假设：在排队分析中，最重要的一个假设是到达速率服从泊松分布，等效的说法是到达间隔时间服从指数分布，这又等价于说到达是随机的并彼此独立。我们几乎一直要作这一假定。没有它，大部分的排队分析是不可能的。在这个假定的条件下，我们会发现仅仅知道到达速率和服务时间的均值和标准差就可以得到许多有用的结果。第42页/共125页排队论课件43模型之：M/M/c排队模型1.M/M/1
31、模型顾客按照速率为的泊松过程到达，顾客的服务时间是独立同分布的随机变量，通常分布设为均值为1的指数分布。假设顾客按照到达的顺序接受服务，即FCFS服务。例如，如果“顾客”表示到达计算机系统的作业任务，那么“服务台”代表计算机系统。另外一种M/M/1队列的解释为：顾客代表消息，而服务台代表通信信道。第43页/共125页排队论课件44随机过程和概率论在排队论中的应用1.把排队过程看成生灭过程如果N（t）表示时刻t系统中的顾客数，则N（t），t0就构成了一个随机过程。如果用“生”表示顾客的到达，“灭”表示顾客的离去，则对许多排队过程来说，N（t），t0是一类特殊的随机过程-生灭过程。服务员忙的时间比
32、率：=/=顾客到达速率/服务速率，也称为服务强度。2.由生灭过程得到几何分布根据连续生灭过程稳定的条件，要求1，根据连续时间生灭过程的计算公式，以得到系统在稳定状态下，有k个顾客的概率如下：Pk=(1-)k,P0=1-对于稳定的系统(t=e(-)t第48页/共125页排队论课件492.M/M/c模型M/M/c队列模型如下：该队列系统的顾客到达为泊松流，到达速率为，有并列的c个服务台，每个服务台的服务速率为，服务规则为FCFS。所有的服务台共享一个公用的队列。该队列是一个生灭过程模型，其生灭速率为：k=，k=0,1,2,k=ckc根据的生灭过程特点，可以得到下面在M/M/c队列中的常用公式。C个
33、服务台第49页/共125页排队论课件50M/M/c模型系统运行指标系统的服务强度，所有服务台是空的概率P0,所有服务台都在忙的概率P,，平均等待顾客数量Lq,系统中平均顾客数量L，平均系统逗留时间W,平均排队等候时间Wq,分别为：第50页/共125页排队论课件51M/M/c模型系统运行指标等价地：系统中的平均顾客数量L=c+P0(c)c/c!(1-)2其中，平均等待顾客数量Lq=P0(c)c/c!(1-)2令随机变量M表示“忙”服务台的数量，EM=c=/所以，任意一个服务台的利用率=/（c）在多服务台系统中的Little公式：=/（c），L=Lq+c。请同学们思考：一个M/M/c系统与c个M/
34、M/1系统比较，那一种效率高？第51页/共125页排队论课件52基本排队模型记号方案基本排队模型记号方案ServerQueueArrival顾客到达时间间隔分布顾客到达时间间隔分布/服务时间分布服务时间分布/服务台数目服务台数目/排队系统允许的最大顾客容量排队系统允许的最大顾客容量/顾客总体数量顾客总体数量/排排队规则队规则(Kendall 记号)M/M/1/FCFS M/M/1/M:负指数分布(Markovian)D:定长分布(常数时间)Ek:k阶Erlang 分布G:普通的概率分布(任意概率分布)第52页/共125页排队论课件53基本排队模型记号基本排队模型记号系统状态系统状态:L=排队系
35、统顾客的数量排队系统顾客的数量,队长。队长。N(t)=在时间在时间 t 排队系统中顾客的数量。排队系统中顾客的数量。Lq =等待服务的顾客的数量等待服务的顾客的数量,队列长度。队列长度。Pn(t)=在时间在时间t,排队系统中恰好有排队系统中恰好有n个顾客的概个顾客的概率。率。s=服务台的数目。服务台的数目。第53页/共125页排队论课件54基本排队模型基本排队模型统计平稳条件下的记号统计平稳条件下的记号 n =系统有n个顾客时的平均到达率（单位时间内平均到达的顾客人数即是平均到达率）n =系统有n个顾客时的平均服务率（单位时间内被服务完的顾客数即是平均服务率）=对任何n都是常数的平均到达率.=
36、对任何n都是常数的平均服务率.1/=期望到达间隔时间1/=期望服务时间 =服务强度，或称使用因子，/第54页/共125页排队论课件55统计平稳条件下的系统运行指标统计平稳条件下的系统运行指标平均系统队长平均系统队长平均等待队长平均等待队长平均排队等待时间平均排队等待时间平均系统逗留时间平均系统逗留时间第55页/共125页排队论课件56L,W,Lq,Wq的关系Littlesformulae第56页/共125页排队论课件57M/M/1/或或M/M/1模型模型一个基本的排列模型.顾客到达时间间隔以及服务时间都服从负指数分布，一个服务台。称为服务强度，与到达率、服务率满足：第57页/共125页排队论课
37、件58M/M/1举例举例第58页/共125页排队论课件59M/M/1/N/单一服务台，固定长度单一服务台，固定长度固定长度排队意味着若到了最大系统容量顾客将不能进入系统.第59页/共125页排队论课件60M/M/1/N/举例举例第60页/共125页排队论课件61增加更多服务台增加更多服务台M/M/c所有服务台是空的概率P0,和所有服务台都在忙的概率P,需要下面比较复杂的公式:第61页/共125页排队论课件62M/M/c举例举例第62页/共125页排队论课件63其他模型，分类规则其他模型，分类规则M/M/c/K/K顾客来源是有限的服务系统.例如：一个饭店有X张桌子和Y个服务生服务来源有限的顾客.
38、M/D/1服务时间不变的服务系统.D/M/1确定性到达模式,及负指数分布服务时间.例如：医生赴约治病的时间表.M/Ek/1服务服从Erlang分布.例如：用相同平均时间去完成一些程序。第63页/共125页排队论课件64应用：校园网的设计和调节收费问题的提出：根据用户数量研究通信端口的设计规模，以及通过适当收取线路调节费来控制上网时间。1）m个用户，每个用户平均每天（16h计）上网1.5h，求n/m。(n为通信端口数)2）m=150,按设定的n讨论平均每个用户每天上网1h,1.5h,2h,3h,4h,5h的可能性，线路忙产生抱怨的可能性及通信端口的平均使用率3）给出一种合理的分段计时收取线路调节
39、费的方案。第64页/共125页排队论课件65问题的分析：排队系统：由信息网络和用户构成服务台：网络的通信端口，个数n顾客：用户，个数（顾客源数）m,顾客总体无限（因为上网次数不限）平均忙期：一天连续工作实际时间，16h系统服务：即时制（只要时间允许，不限制上网人数，但不允许用户在系统内排队等候）第65页/共125页排队论课件66问题的假设：1）每个用户上网随机独立，记为单位时间平均到达（上网）率2）n个通信端口的使用随机独立，记为单位时间平均服务率（上网人数）3）顾客接受一次服务后仍回顾客总体4）收费仅为了调节线路，控制上网时间，不追求经济利益。5）不考虑现实生活中要收取的线路基本费。第66页
40、/共125页排队论课件67模型的建立与求解：用户平均上网人数（顾客平均到达率）服从参数为的泊松分布平均上网（服务）时间服从参数为的负指数分布排队模型为:M/M/n/n/（容量有限系统）顾客到达时间间隔分布顾客到达时间间隔分布/服务时间分布服务时间分布/服务台数目服务台数目/排队系统允许的最大顾客容量排队系统允许的最大顾客容量/顾客总体数量顾客总体数量/排队规则排队规则第67页/共125页排队论课件68模型求解：问题1，m个用户，每个用户平均每天（16h计）上网1.5h，求n/m。(n为通信端口数)T:每天总上网时间第68页/共125页排队论课件69问题2，m=150,按设定的n讨论平均每个用户
41、每天上网1h,1.5h,2h,3h,4h,5h的可能性，线路忙产生抱怨的可能性及通信端口的平均使用率通常通信端口为通常通信端口为16口、口、32口、口、64口、口、128口等口等每个用户每天上网时间为每个用户每天上网时间为1.5h时，时，即服务时间即服务时间1/=1.5第69页/共125页排队论课件70系统满员率：系统满员率：系统可上网率系统可上网率单位时间端口的平均使用率单位时间端口的平均使用率：第70页/共125页排队论课件71其它指标值：第71页/共125页排队论课件72第72页/共125页排队论课件73UNIT2排队网络模型 在工程实践中，除遇到孤立的排队问题外，分析人员还经常遇到多个
42、互连排队的问题，如顾客流的分开与合并，队列的串并连组合等。排队网络模型就是来解决这些问题。主要包括开环排队网络和闭环排队网络，具体应用请查阅相关资料。第73页/共125页QuickPass系统排队问题UNIT3应用之：第74页/共125页排队论课件75在游乐园中的频频排队会极为扫兴DisneyLand中的FastPass(QuickPass)系统就是想解决这个问题的第75页/共125页排队论课件76WhatisQuickPass?工作原理：1.到达的顾客将自己的票插入FastPass的slot中2.FastPass计算出建议顾客返回的时间间隔(time interval)或时间点或时间窗(ti
43、me window)3.顾客无需排队，在指定的时间返回就可持票进入第76页/共125页排队论课件77怎样缩短排队的等待时间？银行的排队叫号机只是有序的组织了顾客，并没有减少等待时间如果能实现知道轮到自己需要等待多少时间，再选择合适的时间来，岂不很好？第77页/共125页排队论课件78FastPass存在的问题：预知的返回时间间隔存在误差按时返回却仍需要排队建议的返回时间间隔太长如果告诉你4小时以后再回来呢？顾客可能不会完全按照安排的时间返回如果新来的顾客不想使用FastPass系统？第78页/共125页排队论课件79我们的目的就是对FastPass系统建立合理的离散统计模型（离散统计模型（Di
44、stributedStatisticalModel），求出最优的顾客返回时间。建模的一般步骤以及：*模型的改进*启发与待解决的问题第79页/共125页排队论课件801模型的假设游乐园开放时间为8:00-18:00,一天中不同时间的顾客流量不同，比如上午10:00和下午3:00的顾客流量是最大的。顾客的到达时间符合非时间齐次泊松过程(NonhomogeneousPossionProcess)，到达速率是(t)。第80页/共125页排队论课件81PoissonProcess第81页/共125页排队论课件82PoissonProcess第82页/共125页排队论课件83分析1：能否得到准确的返回时间
45、？2 在我们开始动手建模之前，先要问几个问题：第83页/共125页排队论课件84分析2：使用FastPass后排队是不是可以避免的？FastPass给出的返回时间只是期望值，而非确定值假设所有的顾客都使用FastPass,但需考虑有的顾客可能会不遵守FastPass给出的返回时间 2 在我们开始动手建模之前，先要问几个问题：第84页/共125页排队论课件85分析3：我们优化的目标函数（或costfunction）是什么？是排队时间吗？2 在我们开始动手建模之前，先要问几个问题：第85页/共125页排队论课件86优化问题的目标函数为：3 模型的建立（1）目标函数第86页/共125页排队论课件87
46、根据排队论（queueingtheory）的分类规则,（X/Y/Z/A）代表一类排队的规则，其中X:顾客流到达所符合的分布Y:顾客接受服务的时间所服从的分布Z:服务台的个数A:服务台一次可服务的顾客数量（系统的容量）针对各个游乐项目的特点，我们主要讨论两种排队系统:模型的建立（2）排队模型的分类第87页/共125页排队论课件88特点：系统容量为1，顾客的到达是Poisson流，服务时间服从指数分布，只有一条队列模型的建立（3）电话亭模型第88页/共125页排队论课件89求出这类系统的代价函数表达式模型的建立（3）电话亭模型第89页/共125页排队论课件90近似将总的优化目标函数等效为对顾客i的
47、目标函数：模型的建立（3）电话亭模型第90页/共125页排队论课件91模型的建立（3）电话亭模型第91页/共125页排队论课件92如果简化c1,c2为常数，并计算第二个人的无需等待返回时间的期望值，得用MatLab能够作出的函数，并从图中得出结果模型的求解（4）电话亭模型第92页/共125页排队论课件93模型的求解（4）电话亭模型Average call time(min*10)U2 t2508.051617.08023.051632.5第93页/共125页排队论课件94第三个人的无需等待返回时间的期望值，同理可以算出，并用图解法求出模型的求解（4）电话亭模型第94页/共125页排队论课件95
48、但是第4个人，第5个人呢？这种方法太繁琐似乎不好用可否有近似的算法？第95页/共125页排队论课件96与前一个模型的区别在于：系统容量是c1,服务时间固定，顾客的到达仍然是Poisson流。模型的建立（5）过山车模型第96页/共125页排队论课件97还要考虑：实际的FastPass系统有两条队列：FastPass和Standby队列不考虑standby队列，将得到Greedyalgorithm模型考虑standby队列，将得到效用函数模型模型的建立（5）过山车第97页/共125页排队论课件98第98页/共125页排队论课件99最简单的情况：最简单的情况：只有一条队列，即所有的人都只用FastP
49、ass系统为了防止前面的人等的时间太长，过山车只要载满一定数量的人后就开车，假设为80c。用贪心算法（greedyalgorithm),将每个顾客尽量安排在离顾客到达时间最近的，且还没有安排满人的一班车上。假设被安排的顾客按照Beta分布到达所被安排的时间段内模型的建立（5）过山车模型第99页/共125页排队论课件100贪心算法模型的建立（5）过山车模型第100页/共125页排队论课件101很容易想到，全局优化的目标变量1.如果开车的时间不固定，则a%是多少最优？就是说顾客坐满多少就开车？2.如果开车的时间间隔是固定的，则多长时间开一次是最优的？衡量的标准：目标函数模型的建立（5）过山车模型第
50、101页/共125页排队论课件102一个区间内的顾客返回示意图第102页/共125页排队论课件103目标函数：模型的建立（5）过山车模型第103页/共125页排队论课件104模型的建立（5）过山车模型怎样求解最优的a%c和最优的开车间隔？对于这类复杂的问题，离散仿真是最好的方法了第104页/共125页排队论课件105仿真：用计算机生成一些符合某种分布的随机数据点，模拟离散时间的发生这里的仿真用MatLab完成：步骤：1.生成Poisson顾客流（模拟到达时间）2.给定不同的a%c,开车时间间隔不定，计算代价函数，画出代价函数性能曲线3.开车时间固定，给出不同的开车时间间隔，计算画出代价函数性能