数学建模排队论课件.ppt

排队论课件,1,现实生活中的实例：,进餐馆就餐,到图书馆借书,去售票处购票,在车站等车等等,排队论课件,2,一、排队系统的特征及排队论：,顾客为了得到某中服务而到达系统，若不能获得服务而允许排队等待，则加入等待队伍，待获得服务后离开系统。,排队论课件,3,排队的形式：,排队论课件,4,随机服务系统：,排队论课件,5,二、排对系统的描述,系统由三个部分组成：,输入过程,排队和排队规则,服务机制,排队论课件,6,1、输入过程,（1）顾客总数量：,有限或者无限,（2）到达方式：,单个到达或成批到达,（3）到达方式：,顾客相继到达时间间隔的分布，,这是刻画,输入过程的最主要内容。,令,表示第n个顾客到达的时刻，,则有：,记,假设：,是独立同分布的，并记其分布函数为,关于,的分布，,排队论中经常用到以下几种：,排队论课件,7,定长分布（D）：,顾客相继到达时间间隔为确定的常数，,如产品通过传输带进入包装箱,最简流（或称poisson分布）（M）：,顾客相继到达时间,间隔,为独立，,同负指数分布，其密度函数为：,排队论课件,8,2、排队及排队规则,（1）排队,分为有限和无限排队,损失制排队系统：,排队空间为零的系统,混合制排队系统：,等待制和损失制的结合，是指允许,排队，但是不允许队列无限长下去，具体的又分三种情况：,（）,队长有限，即等待空间有限,（）,等待时间有限，即顾客在系统中等待时间不超过某一,给定的长度T,（）,逗留时间（等待时间和服务时间之和）,（系统只能容纳K个顾客）,排队论课件,9,不难注意到损失制和等待制可以看成是混合制的特殊情况,如记,为系统中服务台的个数，,当,时，,混合制即为损失制,当,时，,即成为等待制。,(2)排队规则：,先来先服务（FCFS）,排队论课件,10,3、服务机制,主要包括：服务员的数量及其连接形式（串联或并联）；,顾客是单个还是成批接受服务的；服务时间的分布。,记某服务台的服务时间为V，,其分布函数为B(t),密度函数,为b(t),则常见的分布有：,定长分布（D）：,每位顾客接受的服务的时间是常数；,负指数分布（M）：,每位顾客接受服务时间相互独立，,具有相同的负指数分布：,排队论课件,11,其中,为一常数。,k阶爱尔朗分布,密度函数为,排队论课件,12,三、排队系统的符号表示,为了方便对众多的模型的描述，D.G.Kendall提出了一种,目前在排队论中被广泛的使用的“Kendall记号”，,一般形式为：,X/Y/Z/A/B/C,其中X表示顾客相继到达时间间隔的分布，,Y表示服务时间分,布，,Z表示服务台的个数；,A表示系统的容纳，即可容纳最多顾客数,B表示顾客源的数目；,C表示服务规则；,排队论课件,13,表示了一个顾客的到达时间间隔服从相同的负指数分布，,服务时间为负指数分布、,单个服务台、,系统容量为无限、,顾客量无限、,排队规则为先来先服务的排队模型。,排队论课件,14,四、排队系统的主要数量指标和记号,1、队长和排队长,2、等待时间和逗留时间,3、忙期和闲期,排队论课件,15,下面给出上述一些主要数量指标的常用记法：,时刻 t 系统中的顾客数，即队长,时刻 t 系统中排队的顾客数，即排队长,时刻 t 到达系统的顾客在系统中的逗留时间,时刻 t 到达系统的顾客在系统中的等待时间,上述数量指标与时间有关的随机变量，求它们的瞬时分布,非常困难。,排队论课件,16,讨论系统处于平衡状态下的性质：,记,为时刻t时系统处于状态n概率，即系统的瞬时分布,根据前面的约定，我们将主要分析系统的平衡分布，即当系统到,达统计平衡时时所处状态 n 概率，记为,又记：,系统处于平衡状态时队长，其均值为L，称为平均队长,系统处于平衡状态时排队长，其均值为,称为平均,排队长；,系统处于平衡状态时顾客的逗留时间，,均值为,称为,逗留时间；,排队论课件,17,系统处于平衡状态时顾客的等待时间，,其均值记为,称为平均等待时间；,当系统处于状态n时，新来顾客的平均到达率,（单位时,间内来到系统的平均顾客数）,当系统处于状态n时，整个系统的平均服务率（单位,时间内完成的顾客数）,当,为常数时，,记为,当每个服务台的平均服务率为,常数时，记为,当,时，有：,排队论课件,18,1/期望到达间隔时间1/期望服务时间 服务强度，或称使用因子,/(s),五、排队论原理,排队论课件,19,为了使系统中各个状态保持平衡，得到下列方程：,对状态,对状态,对状态,记,则平稳状态分布：,排队论课件,20,则概率分布的要求：,有：,于是：,排队论课件,21,六、M/M/S等待制排队模型,1、单服务台模型,队长的分布,记,为系统到达平衡状态后队长,N的概率分布，,注意到,记,并设,则：,排队论课件,22,因此：,其中：,排队论课件,23,几个主要数量指标,平均队长：,平均排队长：,排队论课件,24,的负指数分布，,关于顾客在系统中的逗留时间T，说明服从参数,因此，平均逗留时间W为：,顾客在系统中逗留时间为等待时间和接受服务时间之和：,排队论课件,25,其中V为服务时间，故由：,可得平均等待时间,为：,平均队长与平均逗留时间具有的关系：,平均排队长与平均等待时间的关系：,称为little公式,排队论课件,26,2、多服务台模型,记,为系统到达平衡状态后队长,N的概率分布，,注意到对个数s个服务台系统，有：,记,并设,则：,排队论课件,27,其中：,排队论课件,28,几个主要数量指标,平均排队长：,平均队长：,Little公式：,排队论课件,29,其他模型,M/M/c/K/K顾客来源是有限的服务系统.例如：一个饭店有 X 张桌子和 Y个服务生服务来源有限的顾客.M/D/1服务时间不变的服务系统.D/M/1确定性到达模式,及指数分布服务时间.例如：医生赴约治病的时间表.M/E k/1服务服从 Erlang 分布.例如：用相同平均时间去完成一些程序。,排队论课件,30,结束语,排队论是专门研究带有随机因素，产生拥挤现象的优化理论。也称为随机服务系统。排队论应用十分广泛。,