研究生入学考试上海交大运筹学期末考试考研复习珍贵PPT资料适合全国高校考研和期末考试9排队论PPT学习教案

1、会计学1 研究生入学考试上海交大运筹学期末考研究生入学考试上海交大运筹学期末考 试考研复习珍贵试考研复习珍贵PPT资料适合全国高校资料适合全国高校 考研和期末考试考研和期末考试9排队论排队论 排队系统的组成和特征 尽管排队系统是多种多样的，但从决定排队系统进 程的因素来看，它有三个基本的组成部分，这就是输入 过程、排队规则及服务机构。 1)输入过程：描述顾客来源以及顾客到达排队系统的规 律。包括： 顾客源中顾客的数量是有限还是无限； 顾客到达的方式是单个到达还是成批到达； 顾客相继到达的间隔时间分布是确定型的还是随机 型的，分布参数是什么，是否独立，是否平稳。 第1页/共63页 2)排队规则：

2、描述顾客排队等待的队列和接受服务的次 序。包括： 即时制还是等待制； 等待制下队列的情况（是单列还是多列，顾客能不 能中途退出，多列时各列间的顾客能不能相互转移）； 等待制下顾客接受服务的次序（先到先服务，后到 先服务，随机服务，有优先权的服务）。 3)服务机构：描述服务台(员)的机构形式和工作情况。 包括： 服务台（员）的数目和排列情况； 服务台（员）的服务方式； 服务时间是确定型的还是随机型的，分布参数是什 么，是否独立，是否平稳。 第2页/共63页 排队模型的分类 D.G.Kendall在1953年提出了一个分类方法，按照 系统的三个最主要的、影响最大的三个特征要素进行 分类，它们是：顾

3、客相继到达的间隔时间分布、服务 时间的分布、并列的服务台个数。按照这三个特征要 素分类的排队系统，用符号（称为Kendall记号）表示 为 X/Y/Z 其中X处填写顾客相继到达的间隔时间分布，Y处填写 服务时间的分布，Z处填写并列的服务台个数。 例如M/M/1，表示顾客相继到达的间隔时间为负指 数分布、服务时间为负指数分布、单服务台的模型。 第3页/共63页 后来，在1971年关于排队论符号标准化的会议上 决定，将Kendall符号扩充为： X/Y/Z/A/B/C 其中前三项意义不变。 A处填写系统容量限制; B处填写顾客源中的顾客数目; C处填写服务规则（如先到先服务FCFS，后到先 服务L

4、CFS）。 约定，如略去后三项，即指X/Y/Z/FCFS的 情形。 后面我们只讨论先到先服务FCFS的情形，所以略 去第六项。 第4页/共63页 排队系统的求解 对于一个排队系统，运行状况的好坏既涉及到顾 客的利益，又涉及到服务机构的利益，还有社会效果 好坏的问题。为了研究排队系统运行的效率、估计服 务质量、研究设计改进措施，必须确定一些基本指标 ，用以判断系统运行状况的优劣。下面介绍几种常用 的指标。 1)队长：把系统中的顾客数称为队长，它的期望值记 作Ls。而把系统中排队等待服务的顾客数称为排队长 （队列长），它的期望值记作Lq。显然有 队长排队长正被服务的顾客数。 第5页/共63页 2)

5、逗留时间：一个顾客从到达排队系统到服务完 毕离去的总停留时间称为逗留时间，它的期望值记 作Ws。 一个顾客在系统中排队等待的时间称为等待时 间，它的期望值记作Wq。显然有 逗留时间等待时间服务时间。 3)瞬态和稳态 把系统中的顾客数称为系统的状态。考虑在t时刻 系统的状态为n的概率，它是随时刻t而变化的，用 Pn(t)表示，称为系统的瞬态。求瞬态解是很不容易的 ，一般即使求出也很难利用，因此我们常用它的极限 lim Pn(t)Pn t 称为稳态或称统计平衡状态的解。 第6页/共63页 n =系统有n个顾客时的平均到达率（单位时 间平均到达的顾客人数即是平均到达率） n =系统有n个顾客时的平均

6、离开率 =对任何n都是常数的平均到达率. =对任何n都是常数的平均离开率. 1/ =期望到达间隔时间 1/ =期望服务时间 =服务强度， 或称使用因子, /(s) 第7页/共63页 q L q W 平均队长 平均等待队长 平均等待时间 平均逗留时间 s L s W 第8页/共63页 1 qs WW ss WL qq WL 公式Little qs LL 将前两式带入后式得将前两式带入后式得 第9页/共63页 0 n ns nPL又因为又因为 1 )( sn nq PsnL 所以，只需要求出Pn即可。 第10页/共63页 几个主要概率分布 一、POISSON分布 设N(t)表示在时间区间t0,t0

7、+t)内到达的顾客数，是随机变 量。当N(t)满足下列三个条件时，我们说顾客的到达符合 Poisson分布。这三个条件是： (1)平稳性 在时间区间t0,t0+t)内到达的顾客数N(t)，只 与区间长度t有关而与时间起点t0无关。 (2)无后效性 在时间区间t0,t0+t)内到达的顾客数N(t)， 与t0以前到达的顾客数独立。 (3)普通性 在充分短的时间区间t内，到达两个或两个 以上顾客的概率极小，可以忽略不计，即 Pn(t)o(t) n=2 第11页/共63页 在上述三个条件下可以推出 (t)n Pn(t) e-t n=0,1,2, n! 其中表示单位时间平均到达的顾客数，即为到 达率。

8、不难算出，N(t)的数学期望和方差分别是： EN(t)t VarN(t)t 第12页/共63页 二、负指数分布 随机变量T的概率密度若是 e-t t0 fT(t) 0 t0 则称T服从负指数分布，它的分布函数是 1-e-t t0 FT(t) 0 t0 T的数学期望和方差分别为： ET1/， Var(T)1/2 负指数分布具有下列性质： (1)无记忆性或马尔柯夫性，即 PTt+s / TsPTt (2)当顾客到达符合Poisson分布时，顾客相继到达 的间隔时间T必服从负指数分布。 第13页/共63页 对于Poisson分布，表示单位时间平均到达 的顾客数，所以1/表示顾客相继到达的平均间 隔时

9、间，而这正和ET的意义相符。 服务时间符合负指数分布时，设它的概率密 度函数和分布函数分别为 fv(t)e-t； Fv(t)1-e-t (t0) 其中表示单位时间能够服务完的顾客数，为服 务率；而1/表示一个顾客的平均服务时间，正 是v的期望值。 第14页/共63页 密度函数 0for t0 0 )( tfore tf t T 均值 1 )(TE 方差 2 1 )( TVar 设随机变量 T 分布函数 t etTP 1)( fT(t) t 1 )(TE 第15页/共63页 )()0(ttTtPtTP fT(t) tt t fT(t) 是一个严格下降函数 第16页/共63页 )()/(tTPtT

10、ttTP无后效性 )( )( ) ( )( ) ( )/( )( )( tTPe e ee e e tTP ttTP tTP tTandttTP tTttTP t t tt t tt 不管多长时间(t)已经过去， 逗留时间的概率分布与下 一个事件的相同. 第17页/共63页 t n n etUP TTTMinU ).( 21 21 )( ),.,.( 几个独立的指数分布的随 机变量的最小有一个指数 分布 几个独立的指数分布的随 机变量的和还是一个指数 分数的随机变量 T (1 +2 +3) T1(1) T1(2) T1(3) min 第18页/共63页 指数分布 0tfor 0 0 )( tf

11、ore tf t T 1 )( TE ! )( )( n et ntXP tn Poisson分布 ttXE )( 服务时间的概率在t时间内已经服务n个顾 客的概率 1/: 平均服务时间 平均服务率= 第19页/共63页 排队系统的状态n随时间变化的过程称为生灭过程， 设平均到达率为n,平均服务率为n,负指数分布排队系统 （M/M/1/）的生灭过程可用下面的状态转移图表示 ： 稳态概率方程如下： 0P0=1P1 n-1Pn-1+n+1Pn+1=nPn+nPn 01 n-1n n+1. 0 1 n-2 n-1 n 1 2 n-1 n n+1 . 生灭过程 第20页/共63页 0 1 0 1 PP

12、 0 12 01 1 2 1 0011 2 1 2 1 2 )( 1 PPPPPP 0 123 012 2 3 2 1122 3 2 3 2 3 )( 1 PPPPPP 0 123 0121 1 1 22111 1 )( 1 PPPPPP n n n n n nnnn n n n n n 第21页/共63页 1, 0 123 0121 CC n n n 若令若令 0 PCP nn 则则 1 0 0 0 因为因为 n n n n PCP 0 0 1 所以所以 n n C P 由前面的推导，可以求出另外的那些量的值。 第22页/共63页 最简单的排队系统的模型 最简单的排队系统：是指输入为最简单流

13、，服务时间 为负指数分布的排队服务系统 并且，此处我们假设：服务规则为：先到先服务；在 多个服务站的情况，假设顾客排成一个单一的队伍。 第23页/共63页 假定： 1. 平均到达率为常数（对所有的n,有n = ） 2. 服务机构的平均服务率也是常数 单个服务站时，有n = ， 多个服务站时，若设S为并联的服务站个数，则有 ,.)1,( ),.,2 , 1( SSnS Snn n 3. 1 S 即服务机构总的服务效率应高于顾客的平均到达 率 保证系统最终能进入稳定状态。 这样就可以把生灭过程的结论拿来用！ 一、顾客源无限、队长不受限制的排队模型 第24页/共63页 01 n-1n n+1. 稳态

14、概率方程如下： P0=P1 Pn-1+Pn+1=Pn+Pn 设=/1，考虑到Pn=1，解得 P0=1- Pn=(1-) n , n1 这里的称为服务强度，也称话务强度，它刻划了服务机构的 繁忙程度，所以又称服务机构的利用率。 此时的排队系统(M/M/1/）的生灭过程可用下面 的状态转移图表示： 1、S1时，即M/M/1模型 第25页/共63页 服务系统的其他各项运行指标计算如下 ： 平均队长： 平均排队长： 1 ) 1 1 ()1()()1( )()1()1( 0 000 d d d d d d nnPL n n n n n n n ns )( 2 sq LL 第26页/共63页 平均逗留时间

15、: 平均等待时间: 1 s s L W )( q q L W 第27页/共63页 再计算（1）顾客在系统中停留时间超过t的概率？ 假定一个顾客来到系统时，系统中已有n个人，则该 顾客在系统中的停留时间应该是系统对前n个顾客的 服务时间加上对他的服务时间。 设T1，T2，Tn表示前n个顾客的服务时间，Tn+1 表示对该顾客的服务时间。 令Sn+1=T1+T2+Tn+Tn+1,则 ,)( ! )( 1 tn n et n Sf t tn n dtet n tSP 0 1 )( ! 此时是爱尔朗分布 第28页/共63页 顾客在系统中停留时间小于t的概率（Ws平均逗留时间） 顾客在系统中停留时间超过t

16、的概率 t t tn n n n nnS edtet n tSPPtWP )1( 0 0 0 1 1)( ! )1( t SS etWPtWP )1( 1 第29页/共63页 （2）已经有人等待的情况下还要等待多久？ 1 )(1 )0E( 0 P W WW q qq 第30页/共63页 第31页/共63页 2、有S个并联服务站时， )( , !)( )/( )!()( )( ).)( ),.,2 , 1( , ! )/( 11 0121 123 0121 Sn SSSS Sn n C Sn n SSn n SSn n n n n n ,.)1,( ),.,2 , 1( SSnS Snn n 因

17、为此时有 所以 第32页/共63页 1 1 ! )/( ! )/( 1 )( ! )/( ! )/( 1 1 0 1 0 0 S n Sn S nSn Sn Sn S Sn SSn P )( , ! )/( ),.,1 , 0( , ! )/( 0 0 SnP SS SnP n P Sn S n n 第33页/共63页 因为在多个服务站的情况下， S 并令n-S=j,则有 2 0 0 00 0 0 0 )1( ! )/( ) 1 1 ( ! )/( )( ! )/( ! )/( )( S P d d P Sd d P S P S jjPPSnL S j S j S Snj j S j jSnq

18、 平均排队长： 其他参数如：平均队长Ls，平均逗留时间Ws，平均等待时 间Wq，都可以通过Little公式求出。 第34页/共63页 例：某厂有大量同一型号的车床，当该种车床损坏 后或送机修车间或由机修车间派人来修理。已知该 种车床损坏率服从泊松分布，平均每天2台。又机修 车间对每台损坏车床的修理时间为负指数分布的随 机变量，平均每台的修理时间为 天。但 是一个 与机修人员编制及维修设备配备好坏（即与机修车 间每年开支费用K）有关的函数。已知 /1 )1900( ,001. 01 . 0)(元 KKK 又已知机器损坏后，每台每天的生产损失为400元， 试决定使该厂生产最经济的K及 第35页/共

19、63页 解：问题包含两个费用：机器损坏造成的生产损失 S1机修车间的开支S2，要使整个系统最经济就是S S1S2最小。以下以一个月为期计算 S1正在修理和待修机器数每台每天的生产损失 每个月的工作日数 ) 9 . 1001. 0 2 (8800) 001. 01 . 0 (8800 )(880022400 KK LS 12 2 KS 第36页/共63页 ) 9 . 1001. 0 2 (8800 12 K K S 0 )9 . 1001. 0( 6 .17 12 1 2 KdK dS 2580,65.17,16430 2 .211)9 . 1001. 0( 2 SK K 第37页/共63页 例

20、：病人到达只有一个医生的医院门诊部的时间平 均每20分钟一个，设对每个病人的诊治时间平均为 15分钟，又知道以上两种时间均为负指数的概率分 布。若该门诊部希望到达的病人90%以上能在候诊 室找到座位，则该医院最少应该设置多少座位？ 解：设候诊室有座位C个，再加上诊治中的病人的座 位共有C1个。按照题目要求，该医院门诊部内病 人总数不多于C1个的概率为0.90,即 6 9 . 01)1( 9 . 0 2 1 0 1 0 1 0 C P P C C n n C n n C n n 第38页/共63页 二、顾客源无限、队长受限制的排队模型 当系统的容量有限制(为M)时，设顾客的平均到达 率仍为常数，

21、但由于系统中已有M个顾客时，新到的顾 客将自动离去，所以有 )( 0 )1,.,1 , 0( Mn Mn n 1、 S1时 )( 0 ),.,1( )/( n Mn Mn C n n 所以有 第39页/共63页 )1( 1 1 1 1 0 n 0 M M n P )1,( 1 1 1 MnP n M n )1( 1 )1( 1 nP 1 1 0 M MM n nS M L 其他指标的计算： 先计算有效输入率eff 由于在队长受限的情况下，当达到顾客数n大于或等 于M时，新来顾客会自动离去。因此虽然顾客以平 均为的速度来到服务系统，但由于一部分的顾客离 去，真正进入系统的的顾客的输入率是小于的。

22、 第40页/共63页 )1( 0 P eff eff s s eff q q eff Sq L W L W LL 由于系统中的平均排队的顾客数总是等于系统中的 平均顾客数平均正在接受服务的顾客数，即： )1()1( 0 1 PLPnLL S M n n eff Sq 第41页/共63页 对于队长受限制的排队模型，当系统中有M个 顾客时，新到顾客会自动离开，故不一定要求 时，有当1, 1 ),.2 , 1( 00 MnPPP n n )1( )1/(1. 0 MPP M )1( 2 0 M nPL M n nS 第42页/共63页 2、 S个并联服务站时 对于队长受限制的排队模型，当系统中有M个

23、顾客 时，新到顾客会自动离开，故当n1时 01 S+1 N (N-1) (N-S+1) (N-S) 2 S S S .N N-1.S S-1 第51页/共63页 由上图中知道，S1时，有 ),.,1( )( 0 ),.,1 , 0( ,)( Nn Nn NnnN n n S1时，有 ,.)1,( ),.,1( )( 0 ),.,1 , 0( ,)( SSnS Snn Nn NnnN n n 由于当n=N时， n=0,所以系统最终一定能达到稳定状 态，所以可用求解稳定状态的方法进行处理。 第52页/共63页 S1时 )( 0 ),.,1( )/( )!( ! Nn Nn nN N C n n )

24、,.,1( )/( )!( ! )/( )!( ! 1 0 N 0n 0 NnP nN N P nN N P n n n )1( )( )!( ! )1()1( 0 0 1 0 1 PLnPL P nN N nPnL q N n nS N n n N n nq 第53页/共63页 由于顾客输入率n随系统状态而变化，因此平均 输入率可按照下式计算： )()( 00 s N n n n nn LNPnNP 且有 q q s s L W L W , 第54页/共63页 S1时， )( 0 ),.,1,( )/( !)!( ! ),.,1( )/( !)!( ! Nn NSSn SSnN N Sn n

25、nN N C n Sn n n N 1Sn -1S 0n N Sn 0 0 0 )( )/( !)!( ! )/( )!( ! 1 )( , 0 ),.,( ,)/( !)!( ! ),.,0( ,)/( !)!( ! nq n Sn n n Sn n n PSnL SSnN N nN N P Nn NSnP SSnN N SnP nnN N P 第55页/共63页 例：设有一名工人负责照管6台自动机床。当机床需 要加料、发生故障或刀具磨损时就自动停车，等待 工人照管。设平均每台机床两次停车的时间间隔为1 小时，又设每台机床停车时，需要工人平均照管的 时间为0.1小时。以上两项时间均服从负指数分布， 试计算该系统的各项指标。 解： 6, 1 . 0 N 00 1 1 6 . 0) 1 . 0 ( )!16 ( ! 6 PPP ) 62 ( ,) 1 . 0 ( )!6 ( ! 6 0 nP n P n n 数据见下表 第56页/共63页 n 等待照管的等待照管的 机床数机床数n-1 Pn/P0Pn(n-1)PnnPn 0010.484500 100.60.290700.2907 210.30.14540.14540.2908 320.120.0582