(七)排队论 | 您所在的位置:网站首页 › 概率分布excel等待时间 › (七)排队论 |
排队论
排队论(Queuing Theory)也称随机服务系统理论,就是为解决一些生活问题而发展的一门学科。它研究的内容有下列三部分: (i)性态问题,即研究各种排队系统的概率规律性,主要是研究队长分布、等待时间分布和忙期分布等,包括了瞬态和稳态两种情形 (ii)最优化问题,又分静态最优和动态最优,前者指最优设计。后者指现有排队系统的最优运营 (iii)排队系统的统计推断,即判断一个给定的排队系统符合于哪种模型,以便根据排队理论进行分析研究。这里将介绍排队论的一些基本知识,分析几个常见的排队模型 基本概念 排队过程的一般表示各个顾客从顾客源出发,随机地来到服务机构,按一定的排队规则等待服务,直到按一定的服务规则接受完服务后离开排队系统 排队系统的组成和特征 输入过程 顾客的组成可能是有限的,也可能是无限的顾客到达的方式可能是一个—个的,也可能是成批的顾客到达可以是相互独立的,即以前的到达情况对以后的到达没有影响;否则是相关的输入过程可以是平稳的,即相继到达的间隔时间分布及其数学期望、方差等数字特征都与时间无关,否则是非平稳的排队规则 损失制:当顾客到达时,所有的服务台均被占用,顾客随即离去等待制。当顾客到达时,所有的服务台均被占用,顾客就排队等待,直到接受完服务才离去混合制。介于损失制和等待制之间的是混合制服务过程 服务机构:单服务台;多服务台并联(每个服务台同 时为不同顾客服务);多服务台串联(多服务台依次为同一顾客服务);混合型服务规则: 先到先服务,这是通常的情形。后到先服务,如情报系统中,最后到的情报信息往往最有价值,因而常被优先处理随机服务,服务台从等待的顾客中随机地取其一进行服务,而不管到达的先后优先服务,如医疗系统对病情严重的病人给予优先治疗排队模型的符号表示( X/Y/Z/A/B/C ) 第一个符号X 表示顾客到达流或顾客到达间隔时间的分布;第二个符号Y 表示服务时间的分布;第三个符号Z 表示服务台数目;第四个符号A 是系统容量限制;第五个符号B 是顾客源数目;第六个符号C 是服务规则,如先到先服务FCFS,后到先服务LCFS 等。并约定,如略去后三项,即指 X /Y / Z /∞/∞/ FCFS的情形。我们只讨论先到先服务 FCFS的情形,所以略去第六项间隔时间和服务时间的分布M —指数分布(M 是Markov 的字头,因为指数分布具有无记忆性,即Markov性)D —确定型(Deterministic)k E — k 阶爱尔朗(Erlang)分布G —一般(general)服务时间的分布GI —一般相互独立(General Independent)的时间间隔的分布排队系统的运行指标平均队长:指系统内顾客数(包括正被服务的顾客与排队等待服务的顾客)的数学期望,记作 Ls 平均排队长:指系统内等待服务的顾客数的数学期望,记作 Lq 平均逗留时间:顾客在系统内逗留时间(包括排队等待的时间和接受服务的时间)的数学期望,记作 Ws 平均等待时间:指一个顾客在排队系统中排队等待时间的数学期望,记作 Wq 平均忙期:指服务机构连续繁忙时间(顾客到达空闲服务机构起,到服务机构再次空闲止的时间)长度的数学期望.记为 Tb 服务强度等 输入过程与服务时间的分布排队系统中的事件流包括顾客到达流和服务时间流。由于顾客到达的间隔时间和服务时间不可能是负值,因此,它的分布是非负随机变量的分布。最常用的分布有泊松分布、确定型分布,指数分布和爱尔朗分布 泊松流与指数分布设 N(t) 表示在时间区间 [0,t) 内到达的顾客数 (t>0) ,令 Pn(t1,t2) 表示在时间区间 [t1,t2) 内有 n(n≥0) 个顾客到达的概率。当 Pn(t1,t2) 符合于下列三个条件时,我们说顾客的到达形成泊松流。 在不相重叠的时间区间内顾客到达数是相互独立的,我们称这性质为无后效性。对于充分小的Δt,在时间区间[t,t + Δt)内有两个或两个以上顾客到达的概率极小,以致可以忽略,即 对充分小的 △t ,在时间区间 [t,t+△t) 内有一个顾客到达的概率与 t 无关,而约与区间长△t成正比,即 P1(t,t+△t)=λ△t+o(△t) 其中 o(Δt) ,当 Δt→0 时,是关于 Δt 的高阶无穷小。 λ>0 是常数,它表示单位时间有一个顾客到达的概率,称为概率强度μ 表示单位时间能被服务完成的顾客数,称为平均服务率 常用的几种概率分布及其产生连续型 均匀分布 正态分布 正态分布还可以作为二项分布一定条件下的近似 指数分布 Gamma 分布 Weibull 分布 Beta 分布 离散型 Bernoulli 分布(两点分布) 泊松(Poisson)分布 二项分布 在独立进行的每次试验中,某事件发生的概率为p,则 n 次试验中该事件发生的次数K服从二项分布 生灭过程未完待续~ 产生给定分布的随机数的方法Matlab 可以产生常用分布的随机数。下面我们介绍按照给定的概率分布产生随机数的一般方法,这些方法都以 U(0,1) 分布的随机变量为基础 反变换法 卷积法 取舍法 排队模型的计算机模拟 确定随机变量概率分布的常用方法根据一般知识和经验,可以假定其概率分布的形式: 顾客到达间隔服从指数分布 Exp(λ) 产品需求量服从正态分布 N(μ,σ2) 订票后但未能按时前往机场登机的人数服从二项分布 B(n,p) 然后由实际数据估计分布的参数λ,μ,σ 等,参数估计 可用极大似然估计、矩估计等方法 未完待续~ 直接由大量的实际数据作直方图,得到经验分布,再通过假设检验,拟合分布函数,可用 χ2 检验等方法 既缺少先验知识,又缺少数据时,对区间 (a,b) 内变化的随机变量,可选用 Beta 分布(包括均匀分布)。先根据经验确定随机变量的均值 μ 和频率最高时的数值(即密度函数的最大值点)m,则 Beta 分布中的参数 α1,α2 可以求出见^162页^ 计算机模拟当排队系统的到达间隔时间和服务时间的概率分布很复杂时,或不能用公式给出时,那么就不能用解析法求解。这就需用随机模拟法求解,现举例说明。 设某仓库前有一卸货场,货车一般是夜间到达,白天卸货,每天只能卸货2车,若一天内到达数超过2 车,那么就推迟到次日卸货。根据下表所示的数据,货车到达数的概率分布(相对频率)平均为1.5 车/天,求每天推迟卸货的平均车数 到达车数012345 ≥ 6概率0.230.30.30.10.050.020.00这是单服务台的排队系统,可验证到达车数不服从泊松分布,服务时间也不服从指数分布(这是定长服务时间)。随机模拟法首先要求事件能按历史的概率分布规律出现。一定范围随机数对应一定区间的到达车辆数 这里直接用概率就行 程序如下: clear rand('state',sum(100*clock)); n=50000; m=2 a1=rand(n,1); a2=a1; %a2初始化 a2(find(a1 |
CopyRight 2018-2019 实验室设备网 版权所有 |