2009全国数学建模比赛运筹学排队论课件

OperationResearch第八讲第十二章排队论OperationResearch第八讲排队现象火车站的售票口理发店客户服务电话乘校车港口食堂吃饭生产流水线这类现象的特点：顾客到来是随机的，服务机构对顾客的服务时间也是随机的。排队论也成为随机服务系统理论，这是对上述随机服务问题进行研究。OperationResearch第八讲随机服务系统所面临的问题服务系统要改善自身的服务质量，提高顾客满意度，减少顾客的排队等候时间。VS服务系统要控制内部运营成本，减少人力、物力资源浪费。如何两者之间取得平衡？OperationResearch第八讲排队论的研究内容性态问题运用概率统计手段，分析随机服务系统的规律，主要研究排队的队长分布、顾客等待时间分布、服务机构的忙期分布。包括瞬态和稳态两种情形。最优化问题分为静态优化和动态优化。静态优化研究服务系统的设计，动态优化研究服务系统运营。OperationResearch第八讲基本概念（1）排队过程的一般表示顾客源排队机构服务机构顾客到来排队规则服务规则离开随机服务系统OperationResearch第八讲顾客源服务系统服务对象的总体。顾客源的组成可能是有限的，也可能是无限。顾客到来（输入过程）到来方式：一个一个的、成批到来。到达的时间间隔：确定型、随机型到达事件的相互独立性：以前到达顾客的事件对以后到来顾客的事件没有影响输入过程的平稳性：顾客相继到达的间隔时间分布和所含参数（如期望值、方差等）都与时间无关。否则，输入过程是非平稳的。基本概念（2）OperationResearch第八讲排队规则即时制（损失制）与等待制即时制（损失制）：如果服务机构正在被占用，顾客到来后随即离去。等待制：如果服务机构正在被占用，顾客到来后排队等待对列容量：由于服务系统内部的空间限制或其他原因，有的系统要规定排队容量（允许进入排队系统的顾客数）的最大限。有的系统则没有这方面限制。对列数目：可以使单列也可以是多列。基本概念（3）OperationResearch第八讲基本概念（4）服务规则先到先服务后到先服务随机服务有优先权的服务服务机构服务台的布置OperationResearch第八讲OperationResearch第八讲服务方式：单个顾客服务，批量顾客服务服务时间：确定型，随机型如果输入过程中顾客相继到达的时间间隔和服务时间两者都为确定型（如生产流水线），该问题很好处理，不是排队论所讨论的问题。在排队论的研究中，两者至少有一个随机型分布。服务时间的平稳性。服务时间的分布和所含参数（如期望值、方差等）都与时间无关。基本概念（5）OperationResearch第八讲排队模型的分类X/Y/Z/A/B/CX表示顾客相继到达的间隔时间分布Y表示服务时间的分布M——负指数分布（Markov）D——确定型（Deterministic）Ek——k阶爱尔朗（Erlang）分布GI——一般相互独立（Generalindependent）的时间间隔分布G——一般服务时间分布Z表示并列服务台的数目A表示服务系统容量（服务中和排队等待的顾客总和）的限制B表示服务系统的顾客源数目C表示服务系统的服务规则，如先到先服务（FCFS），后到先服务（LCFS），随机服务（SIRO），优先权服务（PR）OperationResearch第八讲服务系统中的几个重要参数OperationResearch第八讲服务系统中的性能指标OperationResearch第八讲参数与性能指标之间的关系1/λ相邻两个顾客到达的平均时间间隔1/u对每个顾客的平均服务时间Ls=Lq+S对于单服务台来讲系统忙期=1-P00nnsnPLSnnqPSnL/qsLLOperationResearch第八讲排队论问题的求解思路根据顾客到达的时间间隔和顾客服务时间的实际数据资料进行分析，确定其理论上是属于何种概率分布类型；确定系统处于各种状态（系统中顾客数）的概率；计算反应系统特征的一系列性能指标（队长、忙期、逗留时间、等待时间等）OperationResearch第八讲顾客到达的时间间隔分布与服务时间的分布解决了顾客到达的时间间隔分布与服务时间的分布排队论问题迎刃而解；顾客到达的时间间隔分布与服务时间的分布是随机的，情况较为复杂，需拿出来单独研究；介绍几种常用的随机模型。OperationResearch第八讲泊松流（poisson）（1）设N(t)表示在时刻t服务系统内的顾客数Pn(t1,t2)表示在时间区间[t1,t2)（t1t2）内有n个顾客到达的概率，即如果满足以下三个条件，可以说顾客到达的形成泊松流：（1）无后效性：在不相重叠的时间区间内顾客到达数是相互独立；（2）平稳性：对充分小的⊿t，在时间区间[t,t+⊿t)内有一个顾客到达的概率与t无关，而几乎与区间长⊿t成正比其中o(⊿t),当⊿t→0时，是关于⊿t的高阶无穷小；λ0是常数，表示单位时间有一个顾客到达的概率。（3）普通性：对于充分小的⊿t，在时间区间[t,t+⊿t)内有2个或2个以上顾客到达的概率极小，可以忽略ntNtNPttPn1221,tottttP,12,nntotttPOperationResearch第八讲目前在排队论的研究中，顾客到达的时间分布还仅限于对泊松流分布的研究，其他分布用数学解析方法还得不到满意解。泊松流（poisson）（2）OperationResearch第八讲实例OperationResearch第八讲负指数分布(1)设顾客到达的时间间隔T为随机变量，是一个以λ为参数的负指数分布，则它的概率密度函数为：OperationResearch第八讲负指数分布(2)性质OperationResearch第八讲（2）当服务时间服从以u为参数的负指数分布则离开服务系统的顾客数概率分布为概率密度为u的泊松流OperationResearch第八讲（3）无记忆性（马尔可夫性）即一个顾客到来所需的时间间隔t与过去一个顾客到来所需的时间间隔s无关，所以在随机服务系统中，如果顾客到达的时间间隔为负指数分布，则顾客到达是存随机的。tTPsTstTP|OperationResearch第八讲实例OperationResearch第八讲爱尔朗分布（Erlang）OperationResearch第八讲单服务台负指数分布系统分析模型类型标准模型，M/M/1/∞/∞系统的容量有限制，M/M/1/N/∞顾客源为有限数，M/M/1/∞/mOperationResearch第八讲M/M/1/∞/∞（1）条件限制：OperationResearch第八讲M/M/1/∞/∞（2）系统稳定下的状态分布求出服务系统在稳定状态下，t时刻顾客数（系统状态）为n的概率分布Pn(t)OperationResearch第八讲OperationResearch第八讲OperationResearch第八讲OperationResearch第八讲OperationResearch第八讲M/M/1/∞/∞（3）性能指标OperationResearch第八讲OperationResearch第八讲OperationResearch第八讲OperationResearch第八讲M/M/1/∞/∞（4）总结OperationResearch第八讲实例OperationResearch第八讲实例2OperationResearch第八讲特点随机服务系统的容量有上限数N；单服务台；若一个顾客到达服务系统时，发现系统中已经有N个顾客，那么这个顾客就被拒绝进入系统；当N=1时，为即时制M/M/1/N/∞（1）OperationResearch第八讲M/M/1/N/∞（2）稳态下的状态转移方程OperationResearch第八讲OperationResearch第八讲M/M/1/N/∞（3）性能指标比较M/M/1/N/∞的Ls与M/M/1/∞/∞的LsOperationResearch第八讲有效到达率系统损失率PN+1OperationResearch第八讲M/M/1/N/∞（4）总结OperationResearch第八讲实例OperationResearch第八讲OperationResearch第八讲M/M/1/∞/m（1）特点随机服务系统的顾客源有上限数m；单服务台；实际上，虽然系统的容量没有限制，但系统中的顾客数永远也不会超过m，因此M/M/1/∞/m与M/M/1/m/m两类模型等同。状态转移过程中的顾客到达率。在无限顾客源情形下，顾客到达率是按顾客的全体来考虑。但在顾客源有限情形下，必须按每个顾客来考虑。假定每个顾客来到服务系统的时间间隔服从参数为λ的负指数分布，则λ表示单个顾客的平均到达率（其含义是单位时间内该顾客来到服务系统请求服务的次数）。当顾客总数为m，而系统中有n个顾客，则顾客总的平均到达率为(m-n)λ.OperationResearch第八讲M/M/1/∞/m（2）稳态下的状态转移方程OperationResearch第八讲OperationResearch第八讲M/M/1/∞/m（3）性能指标OperationResearch第八讲实例OperationResearch第八讲OperationResearch第八讲总结（1）记住每类模型P0，Pn的计算公式（2）记住每类模型λe的计算公式（3）记住每类模型的Ls指标计算公式（4）记住各类指标之间的关系