第五章 排队论(Queuing Theory).ppt

1.第五章需求理论，也称为随机服务系统理论，是运筹学的一个主要分支。1909年，丹麦哥本哈根电子公司的电话工程师艾尔兰的开创性论文“概率论与电话通信理论”标志着这一理论的诞生。排队论的发展最初与电话和通信问题有关，现在是排队论的传统应用领域。近年来，它已应用于计算机通信网络系统、交通运输、医疗卫生系统、库存管理、作战指挥等各个领域。一般来说，排队系统有三个基本组成部分：1 .输入过程；2.排队规则；3.服务机构。可以描述以下三种情况：1)排队论的基本概念；3)输入的是顾客的到来；1)顾客来源。客户群体的构成(称为客户来源)可能是有限的，也可能是无限的。例如，从上游流入水库的河水可以被认为是一个无限的种群，而在工厂里停机修理的机器显然是一个有限的种群。2)客户到达方式。顾客可以一个接一个或分批到达。例如，在餐厅用餐时，会有一位新顾客和大量顾客被邀请参加宴会。1。输入过程，4，3)客户流的概率分布。顾客随机一个接一个(一批接一批)来到排队系统。顾客流的概率分布用来描述连续到达的顾客之间的时间间隔分布是确定的还是随机的，分布参数是什么，到达的时间间隔是否独立，分布是否随时间变化或稳定。(1)损失制度。当顾客到达时，如果所有服务台都有人，服务机构不允许顾客等待，顾客只能离开，这种服务规则就是损失制度。2)等待系统。当顾客到达时，如果所有的服务台都被顾客占用并且没有空余时间，那么顾客将自动加入排队等待服务，并在服务完成后离开。(1) FCFS(2)基于先到先得的原则，LCFS(3)随机服务RAND(4)优先服务PR。服务组织1)服务组织可以是单服务器和多服务器服务。该服务表单在与队列规则结合后形成许多不同的队列。不同形式的排队服务组织，如：7。上述特征中最重要和最有影响的是：顾客一个接一个到达的时间间隔，有服务时间的分布式服务台的数量，1953年肯德尔提出了分类方法。称为肯德尔符号(适用于并行服务台)，即X/Y/Z:A/B/C，2)服务模式分为单客户服务和批量客户服务。3)服务时间分为确定型和随机型。4)这里假设服务时间的分布是稳定的。1.2排队系统的模型分类，8，其中：X连续顾客到达间隔分布。m-负指数分布马尔可夫，d-确定性分布确定性，ek-k阶厄兰分布厄兰，gi-一般独立，g-一般随机分布。填写服务时间分布(同上)Z填写并行服务站数A排队系统最大容量B客户来源数量C排队规则如M/M/1:/FCFS将客户到达的排队系统模型称为泊松过程，服务时间为负指数分布，单机，无限容量，无限来源，先到先得。9、系统指标队长，指系统中的客户数量，其期望值为LS；(2)长队列是指系统中等待服务的客户数量。其期望值记录为Lq。一般来说，Ls(或Lq)越大，服务效率越低。(3)停留时间是指客户在系统中停留的时间，其期望值记录为WS；(4)等待时间是指客户在系统中排队等待的时间，其期望值记录为WQ；11，1.3排队论中的基本问题1。排队系统的统计推断：是通过对排队系统主要参数的统计推断和排队系统的结构分析，来判断给定的排队系统符合哪个模型，从而根据排队论进行研究。2.系统状态问题：是研究各种排队系统的概率规律，主要研究排队长度分布、等待时间分布和忙时分布等统计指标，包括瞬态和稳态情况。3.优化问题：包括优化设计(静态优化)和优化操作(动态优化)。12、1.4排队问题的解决(主要指行为问题)。解决一般排队系统问题的目的是研究排队系统运行的效率指标，估计服务质量，确定系统的合理结构和系统参数的合理值，从而实现对现有系统的合理改进和新建系统的优化设计。排队问题的一般步骤：1。确定或拟合到达排队系统的顾客的时间间隔分布和服务时间分布(可测量的)。2.研究系统状态的概率。系统状态是指系统中的客户数量。状态概率用Pn(t)表示，即系统中n个用户在时间t的概率，也称为瞬时概率。求解状态概率Pn(t)的方法是建立包含Pn(t)的微分差分方程，通过求解微分差分方程得到系统的暂态解。因为瞬态解通常难以获得确定的值，所以即使获得了也难以使用。因此，我们经常使用它的极限(如果有极限的话):稳态的物理意义在右图中显示。系统的稳态可以很快达到，但实际中也存在无法达到稳态的现象。值得注意的是，求稳态概率Pn不一定需要t的极限，而只需要Pn(t)=0。称为稳态解，或StatisticalEquilibriumState解。排队论的主要知识点，排队系统的构成和特征排队系统模型顾客到达间隔和服务时间的分类经验分布和理论分布计算标准，稳态概率Pn M/M/1模型(M/M/1):/FCFS系统容量受限模型M/M/1:N/FCFS顾客来源有限模型M/M/1/M/FCFS标准M/M/M/FCFS M/M/C系统和c M/M/1系统容量有限的多服务台模型(M/M/C/N/)客户来源有限的多服务台模型(M/M/C/M)一般服务时间(M/G/1)模型polaczek-khintchine (p-k)公式固定长期服务时间(M/D/1)模型erlang服务时间(M/Ek/1)模型排队系统优化(M/M/M)1模型中的最佳服务率(u)标准(M/M/1)模型为了研究到达间隔时间和服务时间的分布，我们需要首先根据现有系统的原始数据计算它们的经验分布(见P315319)，然后拟合理论分布。如果我们能协调，我们就能得到上面的分布。17、3.1经验分布，经验分布是根据经验数据对排队系统的一些时间参数进行统计分析，并根据统计分析结果假设其统计样本的总体分布，并选择合适的检验方法进行检验。当通过测试时，我们相信时间参数的经验数据服从假设的分布。分布的拟合检验一般采用二次检验。从数理统计的知识中，我们知道如果样本量n足够大(n50)，那么当H0假设为真时，统计总是近似服从自由度为k-r-1的2-分布，其中k是分组数，r是检验分布中的估计参数数。1.泊松分布在概率论中。我们研究了泊松分布。如果随机变量是x，那么有：n=0，1，2，(1)。与时间相关的随机变量的概率是一个随机过程，即泊松过程。t0，n=0，1，2，(2)，19，(t2t1，n0)。如果N(t)表示在时间间隔0，t (t0)内到达的顾客数量，则Pn(t1，t2)表示n(0)个顾客在时间间隔t1，t2)(t2t1)内到达的概率。也就是说，当Pn(t1，t2)满足以下三个条件时，客户到达过程是泊松过程一般性：对于足够小的t，两个或更多顾客在时间间隔(t，tt)内到达的概率是一个高阶无穷小。由此可知，在(T，TT)区间内没有顾客到达的概率是：如果t1=0，t2=t，那么P(t1，t2)=Pn(0，t)=Pn(t)，0是一个常数，它代表单位时间内到达的顾客数，称为概率密度。即P0 P1 P2=1，在上述假设下，系统中n个用户在时间t的概率pn (t)为：22，23， (1)。当n=0时，瞬态方程(1)和(2)被导出，导数为0，得到稳态概率：24，级数，k=n-1，然后：相同的方差为：客户到达过程是泊松过程(泊松流)。Expected，25，代表单位时间内到达的平均客户数。1/代表顾客到达的平均间隔时间。顾客服务时间：当系统处于繁忙期时，两个顾客相继离开系统的时间间隔，一般服从负指数分布，接受服务和离开后的服务时间分布：2。负指数分布可以证明当输入过程为泊松流时，两个顾客相继到达的时间间隔t是独立的，并且服从负指数分布。(等效)，则为26，其中：表示单位时间内可服务的客户数量，即平均服务率。1/代表客户的平均服务时间。3。Erlang (Erlang)分布集v1，v2，Vk是k个独立的随机变量，服从同一个参数k的负指数分布，那么：那么，那么，叫做服务强度。27，一系列的K个服务台，每个服务台的服务时间是相互独立的，并且遵循相同的负指数分布(参数K)，那么顾客走过K个服务台所需的总服务时间遵循上述的K阶Erlang分布。据说，t服从k阶埃尔隆德分布。其特征值为：概率密度为，1/k代表一个服务台对一个客户的平均服务时间。箱子：中有500件易碎物品，从甲地运输到乙地，根据以前的统计数据，易碎物品在运输过程中是按照泊松流进行破碎的，破碎率为0.002。现在，打破3篇文章的概率被计算为：1。2.断裂少于3块的概率和断裂多于3块的概率；3.至少一次破损的概率。解决方案：=0.002500=11。打破3个项目的概率是： p (k=3)=(3/3！)e-=(13/3！)e-1=0.0613，即打破3篇文章的概率为6.132。打破3篇文章的概率是：298756；打破3篇文章的概率为91.97；打破3篇文章的概率是：3。破坏至少一篇文章的概率为p k1=1-(1k/k！)e-=1-(10/0！)e-1=0.632，30。对于排队模型，在给定的输入和服务条件下，主要研究了系统的以下运行指标：(1)系统的平均队列长度Ls(期望值)和平均队列长度Lq(期望值)；(2)顾客在系统中的平均停留时间Ws和排队的平均等待时间Wq；本节仅研究M/M/1模型。讨论了以下三种情况：4 .M/M/1型号、31和4.1标准M/M/1型号。系统中有n个客户，M/M/1:/FCFS模型。1.稳态概率Pn的计算在任何时间t，状态n的概率Pn(t)(瞬时概率)决定了系统的运行特性。已知顾客到达服从参数为的泊松过程，服务时间服从参数为的负指数分布。仍然通过研究区间t、tt的变化来解决。在时间tt，系统中有n个客户，除了以下四种情况(t，tt)之外，不包括超过2个到达或离开的客户。什么？因为这四种情况是相互不相容的，Pn(tt)应该是这四个项的和，并且存在：所有高阶无穷小组合，33，当n=0时，表中只有两种情况(a)和(b)，因为(d)不能出现在较小的t(到达时离开)内，并且如果它出现，t可以被认为是小的。，生灭过程，瞬态解，34，从中可以得到排队系统的状态转移图：将其代入方程(3)并使n=1，2，(状态平衡方程也可以从状态转移图中看出)获得：Pn，35,n=1,n=2,36等的差分方程.当n=n， (5)且概率性质已知时，否则排队是无限的，系统的稳态概率为37，2。系统运行指标计算(1)队长Ls(平均队长)，(01)，期望值，38，(2)排队等候LQ的平均顾客数，(8)，(3)顾客在系统中停留的平均时间Ws顾客在系统中停留的平均时间是一个随机变量。证明了它服从参数为-的负指数分布，分布函数为、39、8756；(4)Wq顾客平均排队时间、等待时间、顾客平均排队时间应为Ws减去平均服务时间。考虑到LS和WS之间的关系，40，四个指标之间的关系是(小公式):(3)系统的忙期和空闲期，系统处于空闲状态的概率：系统处于忙期的概率：服务强度，41，队列中的平均客户数Lb:客户平均等待时间：忙期内服务的平均客户数，LbP(N0)=Lq，42，例如， 某医院手术室根据患者前来就诊和完成手术的时间记录，随机抽查100个工作小时。 表9-4显示了每小时前来就诊的病人数量。另外随机选择了100份完成手术的病历。表9-5显示了使用的次数(小时)。计算手术室的各项指标。43，表9-4，表9-5，44，1。参