排队论教案范文

排队论教案范文 排队论排队论是研究排队系统（又称随机服务系统）的数学理论和方法，是运筹学的一个重要分支。 有形排队现象进餐馆就餐，到图书馆借书，车站等车，去医院看病，售票处售票，到工具房领物品等现象。 无形排队现象如几个旅客同时打电话订车票；如果有一人正在通话，其他人只得在各自的电话机前等待，他们分散在不同的地方，形成一个无形的队列在等待通电话。 排队的不一定是人，也可以是物。 如生产线上的原材料，半成品等待加工；因故障而停止运行的机器设备在等待修理；码头上的船只等待装货或卸货；要下降的飞机因跑道不空而在空中盘旋等。 当然，进行服务的也不一定是人，可以是跑道，自动售货机，公共汽车等。 为了一致，统一规定为顾客要求服务的对象。 服务员提供服务的服务者（也称服务机构）。 顾客、服务员的含义是广义的。 排队的类型（见ppt）排队系统的描述排队系统的描述实际中的排队系统各不相同，但概括起来都由三个基本部分组成输入过程，排队及排队规则和服务机构。 （一）输入过程描述顾客按照什么样的规律到达系统，从三个方面描述一个输入顾客总体（顾客源）数可能是有限，也可能是无限。 到达方式是单个到达还是成批到达。 库存问题中，若把进来的货看成顾客，则为成批到达的例子。 顾客（单个或成批）相继到达的时间间隔分布这是刻划输入过程的最重要内容。 令T0=0，T n表示第n顾客到达的时刻，则有T0?T1?T2?T u?记X n?T n?T n?1,n?1,2,?，则X n是第n顾客与第n-1顾客到达的时间间隔。 一般假定Xn是独立同分布，并记分布函数为A(t)。 X n的分布A(t)常见的有定常分布（D）顾客相继到达的时间间隔为确定的。 如产品通过传送带进入包装箱就是定常分布。 最简流（或称Poisson)（M）顾客相继到达的时间间隔Xn为独立的，同为负指数分布，其密度函数为?e?t t?0a(t)?0t0（二）排队及排队规则 （1）排队有限排队排队系统中顾客数是有限的。 无限排队顾客数是无限，队列可以排到无限长（等待制排队系统）。 有限排队还可以分成损失制排队系统排队空间为零的系统，即不允许排队。 （顾客到达时，服务台占满，顾客自动离开，不再回来）（电话系统）混合制排队系统是等待制与损失制结合，即允许排队，但不允许队列无限长。 B排队规则当顾客到达时，若所有服务台都被占有且又允许排队，则该顾客将进入队列等待。 服务台对顾客进行服务所遵循的规则通常有先来先服务（FCFS）后来先服务（LCFS）。 在许多库存系统中就会出现这种情况，如钢板存入仓库后，需要时总是从最上面取出；又如在情报系统中，后来到达的信息往往更重要，首先要加以分析和利用。 具有优先权的服务（PS）。 服务台根据顾客的优先权的不同进行服务。 如病危的病人应优先治疗；重要的信息应优先处理；出价高的顾客应优先考虑。 （2）服务机制包括服务员的数量及其连接方式（串联还是并联）；顾客是单个还是成批接受服务；服务时间的分布。 记某服务台的服务时间为V，其分布函数为B(t),密度函数为b(t),则常见的分布有i.ii.定长分布（D）每个顾客接受的服务时间是一个确定的常数。 负指数分布（M）每个顾客接受的服务时间相互独立，具有相同的负指数分布i.iii.?e?t t?0b(t)?,?为常数?0t0K阶爱尔朗分布（En）k?(k?t)k?1?k?tb(t)?e(k?1)!当k=1时即为负指数分布；k?30,近似于正态分布。 当k?时，方差?0即为完全非随机的。 （三）排队系统的符号表示D.G.Kendall在1953年提出了一份分类方法，按照最主要的影响最大的特征表示为“Kendall”记号X/Y/Z其中X表示顾客相继到达的时间间隔分布；Y表示服务时间的分布；Z表示服务台个数；表示相继到达间隔时间和服务时间的各种分布的符号M负指数分布，（M是Markov的字头，因为负指数分布具有无记忆性，即Markov性）D确定型（Deterministic）E rk阶爱尔朗分布（Erlang）GI一般相互独立（General Independent）的时间间隔分布G一般（General）服务时间分布在1971年将其扩充为X/Y/Z/A/B/C前三项意义不变，而A填写系统容量限制B填写顾客源书目C填写服务规则（先到先服务FCFS，后到先服务LCFS等）如果略去后三项，则代表X/Y/Z/?/?/FCFS排队系统的主要数量指标队长记为L s，指排队系统中的顾客数（排队等待的顾客数与正在接受服务的顾客数之和）。 排队长又称为队列长，记为L q，系统中正在排队等待服务的顾客数。 逗留时间指一个顾客在系统中的停留时间，其期望值为记作W s等待时间指一个顾客在系统中排队等待的时间，其期望值记为W q系统状态系统中的顾客数。 如果系统中有n个顾客就说明系统的状态是n，其可能值为队长没有限制时，n?0,1,2,?,N队长有限制，最大数为N时，n?0,1,2,?,c即时制服务台个数是c时，n?0,1,2,到达间隔分布和服务时间分布泊松流（普阿松流）设N(t)表示在时间区间0,t)内到达的顾客数令Pn(t1,t2)表示在时间区间t1,t2)(t1?t2),内有n(n?0)个顾客到达的概率，即P n(t1,t2)?PN(t2)?N(t1)?n(t2?t1,n?0)当Pn(t1,t2)满足下列三个条件时，认为顾客的到达形成了泊松流。 这三个条件是 (1)在不相重叠的时间区间内顾客到达数是相互独立的，称此性质为无后效性； (2)对充分小的?t，在时间区间t,t?t)内有1个顾客到达的概率与t无关，而与区间长?t成正比，即P1(t,t?t)?t?(?t)，?0是常数，它表示单位时间有一个顾客到达的概率，称为概率强度； (3)对于充分小的?t，在时间区间t,t?t)内有2个或2个以上顾客到达的概率极小，以至于可以忽略，即?P(t,t?t)?(?t)nn?2?在条件2，我们可以从上时间0算起，记为Pn(0,t)?P n(t)不加证明的给出(?t)n?tP n(t)?e,t?0n!n?0,1,2?P n(t)表示长为t的时间区间内到达n个顾客的概率。 其数学期望和方差分别是EN(t)?t;VarN(t)?t其中，?表示单位时间平均到达的顾客数，所以1?表示相继顾客到达平均间隔时间，和ET的意义相符。 负指数分布随机变量T的概率密度若是?e?t,t?0f T(t)?，?0,tK?1?1k?1?1?1?其中，p0?k11?n?1?n?1?K?1可以得到当?1时，L s?nP n?n?p0?p0?n?nn?0n?1n?1K KKn?1dKn d?(1?k)?p0?p0d?(1?)d?n?1因为d f(x)(f?(x)g(x)?f(x)g?(x)()?，可以求得g2(x)dx g(x)d?(1?k)?(1?k?(1?)K?K?(1?k?1?k?1?k?(1?)K?K)L s?p0()?d?1?(1?)(1?k?1)(1?)(1?k?1)(K?1)?k?1?1?(1?k?1)?1KK当?1时，表达式变为L s?np n?n?p0?n?K?12k?0k?1k?1nK K其排队长为L q?(n?1)p n?L s?(1?p0)k?1K对于系统来说，由于容量有限，当系统的人数达到K时，由于系统满而造成顾客不能进入。 假设顾客到达率为?，当系统处于状态K时，顾客不能进入系统，即顾客可以进入的概率为1?p k，因此，单位时间内顾客可进入的平均数为?e?(1?p k)?p0?p0?n nn?0n?0K k1?k1?1?k1?k1?k?1?1?1?p0?(1?)?(1?p0)k?1k?1k?1k?11?1?1?1?1?1?根据little公式，得到平均逗留时间W s?L sL s?(1?p0)?eL q?平均等待时间W q?e?W s?1?多服务台模型M/M/K设顾客单个到达，相继到达时间服从参数为?的负指数分布，系统中共有s个服务台，每个服务台的服务时间相互独立，且服从参数为?的负指数分布。 当顾客到达时，若有空闲的服务台则马上接受服务，否则便排队等候，队列为无限制。 讨论其稳态分布记p n?pN?n(n=0,1,2?)为系统达到平稳状态后队长N的概率分布，注意到有s?n=1,2,?,s的服务台，有?n?和?n?s?n=s,s+1,?记?s?s?，则当?s1时，有以前的计算的s?(?)n?n=1,2,?,s?n!C n?n?s?()?n?s(?)s()?n?s?n?ss!s?s!s?n?1p n=1,2,?s?s?1?n?s?n!0?，其中p0?p n?nn!s!(1?)?n?0?p n?s0?s!sn?s平均排队长为p0?(n?s)?np0?(n?s)?n?s+sL q?(n?s)p n?sn?s n?ss!s s!n?s?1n?s?1n?s?1?p0?s?s!(n?s)?n?sp0?s?n?ss s!n?s?1?n?s?1?(n?s)(s?n?sn?sp0?s)?s!n?s?1?(n?s)(?)s?n?s1?1p0?s?sp0?s?sp0?s?sd1n?s?1n?s?(n?s)(?s)?(?s)?s!n?s?1s!d?s!(1?s)2在以上公式中，同理，L q?L s得以得到平均队长同样，根据Litter公式可以得到逗留时间和排队时间。 独立同分布Independent andidentically di