数学建模-排队论ppt课件.ppt

《数学建模-排队论ppt课件.ppt》由会员分享，可在线阅读，更多相关《数学建模-排队论ppt课件.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六讲 排队论及排队系统优化排队现象与排队系统;排队模型与系统参数;排队系统时间参数分布规律;排队系统的生灭过程与状态转移方程;排队系统分析;单服务台负指数分布模型 多服务台负指数分布模型 排队系统优化分析;烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人排队论发源于上世纪初。当时美国贝尔电话公司发明了自动电话，以适应日益繁忙的工商业电话通讯需要。这个新发明带来了一个新问题，即通话线路与电话用户呼叫的数量关系应如何妥善解决，这个问题久久未能解决。1909年，丹麦的哥本哈根电话公司A.K.埃尔浪(Erlang)在热力学

2、统计平衡概念的启发下予以解决了。6.1 6.1 排队现象与排队系统排队现象与排队系统一、排队现象一、排队现象到达顾客到达顾客 服务内容服务内容 服务机构服务机构病病 人人 诊断诊断/手术手术 医生医生/手术台手术台进港的货船进港的货船 装货装货/卸货卸货 码头泊位码头泊位到港的飞机到港的飞机 降落降落 机场跑道机场跑道电话拨号电话拨号 通话通话 交换台交换台故障机器故障机器 修理修理 修理技工修理技工修理技工修理技工 领取修配零件领取修配零件 仓库管理员仓库管理员上游河水上游河水 入库入库 水闸管理员水闸管理员 （1 1）由于顾客到达和服务时间的）由于顾客到达和服务时间的随机性随机性，现实中的

3、排队现象几乎不可避免；现实中的排队现象几乎不可避免；（2 2）排队过程，通常是一个）排队过程，通常是一个随机过程随机过程，排队论又称排队论又称“随机服务系统理论随机服务系统理论”；二、排队系统二、排队系统（一）排队服务过程（一）排队服务过程排队系统排队系统顾客源顾客源排队结构排队结构顾客到来顾客到来排队规则排队规则服务规则服务规则顾客离去顾客离去服务机构服务机构。（二）排队系统的要素及其特征（二）排队系统的要素及其特征1 1、排队系统的要素：、排队系统的要素：（1 1）顾客输入过程；）顾客输入过程；（2 2）排队结构与排队规则；）排队结构与排队规则；（3 3）服务机构与服务规则；）服务机构与服

4、务规则；2 2、排队系统不同要素的主要特征：、排队系统不同要素的主要特征：（1 1）顾客输入过程顾客输入过程顾客源顾客源(总体总体)：有限有限/无限无限;顾客到达方式：顾客到达方式：逐个逐个/逐批逐批;(;(仅研究逐个情形仅研究逐个情形)顾客到达间隔：顾客到达间隔：随机型随机型/确定型确定型;顾客前后到达是否独立：顾客前后到达是否独立：相互独立相互独立/相互关联相互关联；输入过程是否平稳：输入过程是否平稳：平稳平稳/非平稳非平稳；(仅研究平稳性仅研究平稳性)顾客到达时刻顾客到达时刻 i i相继到达间隔时间相继到达间隔时间t ti i（2 2）排队结构与排队规则排队结构与排队规则顾客排队方式：顾

5、客排队方式：等待制等待制/即时制即时制(损失制损失制);排队系统容量：排队系统容量：有限制有限制/无限制无限制;排队队列数目排队队列数目:单列单列/多列多列;是否中途退出是否中途退出:允许允许/禁止禁止;是否列间转移是否列间转移:允许允许/禁止禁止;(仅研究禁止退出和转移的情形仅研究禁止退出和转移的情形)（3 3）服务机构与服务规则服务机构与服务规则服务台服务台(员员)数目数目;单个单个/多个多个;服务台服务台(员员)排列形式排列形式;并列并列/串列串列/混合混合;服务台服务台(员员)服务方式服务方式;逐个逐个/逐批逐批;(;(研究逐个情形研究逐个情形)服务时间分布服务时间分布;随机型随机型/

6、确定型确定型;服务时间分布是否平稳服务时间分布是否平稳:平稳平稳/非平稳非平稳;(;(研究平稳情形研究平稳情形)1 11 12 2c c 1 12 2c c 1 12 2c c 服务台服务台(员员)为顾客服务的顺序为顾客服务的顺序:a)a)先到先服务先到先服务(FCFS);FCFS);b)b)后到先服务后到先服务(LCFS)LCFS);c)c)随机服务随机服务;d)d)优先服务优先服务;6.2 6.2 排队模型与系统参数排队模型与系统参数一、排队模型一、排队模型(一一)排队模型表示方法排队模型表示方法1 1、D.G.Kendall(1953)D.G.Kendall(1953)表示法表示法 X/

7、Y/ZX/Y/Z依据排队系统依据排队系统3 3个主要特征：个主要特征：（1 1）X X 顾客到达间隔时间分布；顾客到达间隔时间分布；（2 2）Y Y 服务台（员）服务时间分布；服务台（员）服务时间分布；（3 3）Z Z 服务台（员）个数服务台（员）个数（单个或多个并列）（单个或多个并列）；2 2、国际排队论标准化会议、国际排队论标准化会议(1971)(1971)表示法表示法 X/Y/Z/A/B/CX/Y/Z/A/B/C（1 1）A A 系统容量限制；系统容量限制；（2 2）B B 顾客源（总体）数目；顾客源（总体）数目；（3 3）C C 服务规则（服务规则（FCFSFCFS，LCFSLCFS等

8、）；等）；略去后三项，即指略去后三项，即指 “X/Y/Z/X/Y/Z/FCFS”/FCFS”；这里仅研究这里仅研究FCFSFCFS的情形；的情形；(二二)到达间隔和服务时间典型分布到达间隔和服务时间典型分布（1 1）泊松分布泊松分布 M M；（2 2）负指数分布负指数分布 M M；（3 3）k k阶爱尔朗分布阶爱尔朗分布 E Ek k；（4 4）确定型分布确定型分布 D D；（5 5）一般服务时间分布一般服务时间分布 G G；M/M/1M/M/1，M/D/1M/D/1，M/Ek/1M/Ek/1；M/M/cM/M/c，M/M/c/M/M/c/m/m，M/M/c/N/M/M/c/N/，。，。(三三

9、)排队模型示例排队模型示例二、系统参数二、系统参数(一一)系统运行状态参数系统运行状态参数1 1、系统状态、系统状态 N(t)N(t)指排队系统在时刻指排队系统在时刻t t时的全部顾客数时的全部顾客数 N(t)N(t)，包括包括“排队顾客数排队顾客数”和和“正被服务顾客数正被服务顾客数”；系统状态的可能值如下：系统状态的可能值如下：（1 1）系统容量无限制，）系统容量无限制，N(t)N(t)=0=0，1 1，2 2，;(2)(2)系统容量为系统容量为N N时时,N(t)=0,1,2,N;N(t)=0,1,2,N;(3)(3)服务台个数为服务台个数为c/c/损失制损失制,N(t)N(t)=0,1

10、,2,c;=0,1,2,c;一般一般,系统状态系统状态N(t)N(t)是随机的。是随机的。2 2、系统状态概率、系统状态概率：(1)(1)瞬态概率瞬态概率P Pn n(t)(t)表示时刻系统状态表示时刻系统状态 N(t)N(t)=n n 的概率的概率;(2)(2)稳态概率稳态概率P Pn n P Pn n=P Pn n(t)(t);一般，排队系统运行了一定长的时一般，排队系统运行了一定长的时 间后，系统状态的概率分布不再随时间间后，系统状态的概率分布不再随时间 t t变化，即初始时刻（变化，即初始时刻（t=0t=0）系统状态的系统状态的 概率分布概率分布(P Pn n(0)(0)，n0n0）的

11、影响将消失。的影响将消失。(二二)系统运行指标参数系统运行指标参数 评价排队系统的优劣。评价排队系统的优劣。1 1、队长与排队长、队长与排队长 (1)(1)队长队长:系统中的顾客数（系统中的顾客数（n n）；）；期望值期望值 L Ls s=n*Pn*Pn n (2)(2)排队长排队长:系统中排队等待服务的顾客数系统中排队等待服务的顾客数;期望值期望值 L Lq q=L Lq q=L Ls s-正被服务的顾客数正被服务的顾客数 2 2、逗留时间与等待时间、逗留时间与等待时间 (1)(1)逗留时间逗留时间:指一个顾客在系统中的全部停留时间指一个顾客在系统中的全部停留时间；期望值，记为期望值，记为

12、W Ws s (2)(2)等待时间等待时间:指一个顾客在系统中的排队等待时间；指一个顾客在系统中的排队等待时间；期望值，记为期望值，记为 W Wq qW Ws s=W Wq q+EE服务时间服务时间 3 3、其他相关指标、其他相关指标 (1)(1)忙忙 期期:指从顾客到达空闲服务机构起到服务指从顾客到达空闲服务机构起到服务 机构再次空闲的时间长度；机构再次空闲的时间长度；(2)(2)忙期服务量：忙期服务量：指一个忙期内系统平均完成指一个忙期内系统平均完成 服务的顾客数；服务的顾客数；(3)(3)损失率损失率:指顾客到达排队系统，未接受服务指顾客到达排队系统，未接受服务 而离去的概率；而离去的概

13、率；(4)(4)服务强度：服务强度：=/c c ；6.3 6.3 排队系统时间参数分布规律排队系统时间参数分布规律一、顾客到达时间间隔分布一、顾客到达时间间隔分布(一一)泊松流与泊松分布泊松流与泊松分布如果顾客到达满足如下条件如果顾客到达满足如下条件,则称为则称为泊松流泊松流:(1)在不相互重叠的时间区间内，到达顾客数在不相互重叠的时间区间内，到达顾客数 相互独立相互独立(无后效性无后效性).(2)对于充分小的时间间隔对于充分小的时间间隔 内，到达内，到达 1个顾客的概率与个顾客的概率与t无关，仅与时间间隔无关，仅与时间间隔 成正比成正比 (平稳性平稳性)：(3)对于充分小的时间间隔对于充分小

14、的时间间隔 ，2个及以个及以 上顾客到达的概率可忽略不计上顾客到达的概率可忽略不计(普通性普通性)。对泊松流，在时间t系统内有n个顾客的概率服从如下泊松分布 EN(t)=t;Var N(t)=t;单位时间平均到达的顾客数；若顾客到达间隔若顾客到达间隔T的概率密度为的概率密度为则称则称T服从负指数分布，分布函数如下：服从负指数分布，分布函数如下：若顾客流是泊松流时，顾客到达的时间间隔若顾客流是泊松流时，顾客到达的时间间隔显然服从上述负指数分布显然服从上述负指数分布(WHY);ET=1/;Var T=1/2;T=1/(二二)泊松流到达间隔服从负指数分布泊松流到达间隔服从负指数分布二、顾客服务时间分

15、布二、顾客服务时间分布(一一)负指数分布负指数分布(1)对一个顾客的服务时间对一个顾客的服务时间Ts，等价于相邻两个顾客等价于相邻两个顾客离开排队系统的时间间隔。若离开排队系统的时间间隔。若Ts服从负指数分布，服从负指数分布，其概率密度和分布函数分别为其概率密度和分布函数分别为则则ETs=1/;Var Ts=1/2;Ts=1/(2)ETs=1/：每个顾客的平均每个顾客的平均(期望期望)服务时间；服务时间；:单位时间服务的顾客数，平均单位时间服务的顾客数，平均(期望期望)服务率；服务率；(二二)爱尔朗爱尔朗(Erlang)Erlang)分布分布(1)设设v1,v2,vk是是k个相互独立的随机变量

16、个相互独立的随机变量,服从服从相同参数相同参数1/k的负指数分布的负指数分布,则则:T=v1+v2+vk的的概率密度为概率密度为称称T服从服从k阶爱尔朗分布。阶爱尔朗分布。(2)ET=1/;Var T=1/(k2)(3)T的意义之一的意义之一:k个串联服务台的总服务时间！个串联服务台的总服务时间！6.4 6.4 排队系统的生灭过程与状态转移方程排队系统的生灭过程与状态转移方程一、排队系统的生灭过程一、排队系统的生灭过程(一一)生灭过程的背景与定义生灭过程的背景与定义设某系统具有状态集设某系统具有状态集S=0,1,2,或或S=0,1,2,k,N(t)表示系统在时刻表示系统在时刻t(t=0)的状态

17、。的状态。若在若在N(t)=n的条件下，随机过程的条件下，随机过程N(t),t=0满足满足以下条件以下条件:(1)N(t+t)转移到转移到“n+1”的概率为的概率为n(t);(2)N(t+t)转移到转移到“n-1”的概率为的概率为n(t);(3)N(t+t)转移到转移到其他状态其他状态“S-n+1,n-1”的概的概率为率为o(t)(高阶无穷小高阶无穷小);则称则称随机过程随机过程N(t),t=0为为生灭过程生灭过程。n，n，t(？)(二二)生灭过程状态变化的性质生灭过程状态变化的性质(1)在无穷小在无穷小 t内内,系统或生长系统或生长1个个;或灭亡或灭亡1个个;或既或既不生长又不灭亡不生长又不

18、灭亡（概率概率:1-n(t)-n(t)）;(2)系统生长一个的概率系统生长一个的概率n(t)与与 t有关，而与有关，而与t无无关关;与系统当前状态与系统当前状态n有关，而与以前的状态无关；有关，而与以前的状态无关；(3)系统灭亡一个的概率系统灭亡一个的概率n(t)与与 t有关，而与有关，而与t无无关关;与系统当前状态与系统当前状态n有关，而与以前的状态无关；有关，而与以前的状态无关；马尔可夫性质马尔可夫性质(三三)排队系统的生灭过程排队系统的生灭过程顾客到达顾客到达“生生”；顾客离开顾客离开“灭灭”顾客到达顾客到达顾客离去顾客离去n，n，(1)(1)生灭过程示意生灭过程示意若排队系统具有下列性

19、质若排队系统具有下列性质:(1)顾客到达为泊松流，时间间隔服从参顾客到达为泊松流，时间间隔服从参数为数为n的负指数分布的负指数分布;(2)顾客服务时间服从参数为顾客服务时间服从参数为 n的负指的负指数分布数分布;则排队系统的随机过程则排队系统的随机过程N(t),t=0具有具有马马 尔可夫性质尔可夫性质,为为一个生灭过程一个生灭过程.(2)(2)生灭过程定义生灭过程定义二、排队系统的状态转移方程二、排队系统的状态转移方程(一一)排队系统状态的概率及其分布排队系统状态的概率及其分布 (1)(1)瞬态概率瞬态概率P Pn n(t)(t)表示时刻系统状态表示时刻系统状态N(t)N(t)=n n的概率的

20、概率;(2)(2)稳态概率稳态概率P Pn n P Pn n=P Pn n(t)(t);一般，稳态概率一般，稳态概率P Pn n的分布，是分析计算的分布，是分析计算排队系统运行优劣的基础。排队系统运行优劣的基础。三、三、排队系统稳态概率排队系统稳态概率P Pn n的求解的求解对一般排队系统，均有下式成立其中有效到达率为四、四、排队系统性能参数的一般关系排队系统性能参数的一般关系 Little Little 公式公式6.4 6.4 典型排队系统分析典型排队系统分析6.4.1 6.4.1 单服务台负指数分布单服务台负指数分布M/M/1M/M/1排队系统排队系统模型的条件是：1、输入过程顾客源是无限

21、的，顾客到达完全是随机的，单个到来，到达过程服从普阿松分布，且是平稳的；2、排队规则单队，且队长没有限制，先到先服务；3、服务机构单服务台，服务时间的长短是随机的，服从相同的指数分布。烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人对于对于M MM M1 1模型有如下公式：模型有如下公式：烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人例例1 某某医医院院急急诊诊室室同同时时只只能能诊诊治治一一个个病病人人，诊诊治治时时间间服服从从指指数数

22、分分布布，每每个个病病人人平平均均需需要要1515分分钟钟。病病人人按按泊泊松松分分布布到到达达，平平均均每每小小时时到到达达3 3人人。试试对此排队队系统进行分析。对此排队队系统进行分析。解解 对此排队队系统分析如下：对此排队队系统分析如下：（1 1）先确定参数值先确定参数值：这是单服务台系统，有：这是单服务台系统，有：故服务强度为：故服务强度为：烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人（2）计算稳态概率：计算稳态概率：这就是急诊室空闲的概率，也是病人不这就是急诊室空闲的概率，也是病人不必等待立即就能就诊的

23、概率。必等待立即就能就诊的概率。而病人需要等待的概率则为：而病人需要等待的概率则为：这这也是急也是急诊诊室繁忙的概率。室繁忙的概率。烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人（2）计算系统主要工作指标。计算系统主要工作指标。急诊室内外的病人平均数：急诊室内外的病人平均数：急急诊诊室外排室外排队队等待的病人平均数：等待的病人平均数：病人在急病人在急诊诊室内外平均逗留室内外平均逗留时间时间：病人平均等候病人平均等候时间时间：烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有

24、限，请同学们想一想如何来治疗该病人（4）为使病人平均逗留时间不超过半为使病人平均逗留时间不超过半小时，那么平均服务时间应减少多少？小时，那么平均服务时间应减少多少？由于由于代入代入=3=3，解得，解得55，平均服，平均服务时间务时间为为：151512123min3min即平均服即平均服务时间务时间至少至少应应减少减少3min3min烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人(5)(5)若医院希望候诊的病人若医院希望候诊的病人90%90%以上都能有以上都能有座位座位,则候诊室至少应安置多少座位则候诊室至少应安置多

25、少座位?设应该设应该安置安置个座位个座位,加上急加上急诊诊室的一个室的一个座位座位,共有共有+1+1个。要使个。要使90%90%以上的候以上的候诊诊病病人有座位，相当于使人有座位，相当于使“来来诊诊的病人数不多于的病人数不多于+1+1个个”的概率不少于的概率不少于90%90%，即，即烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人两两边边取取对对数数（x2 2）lglg lg0.1lg0.1因因 1 1，故，故所以所以 x 66即候诊室至少应安置即候诊室至少应安置6 6个座位。个座位。烧伤病人的治疗通常是取烧伤病人的

26、健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人第三节第三节M/M/S模型模型此模型与M/M/1模型不同之处在于有S个服务台，各服务台的工作相互独立，服务率相等，如果顾客到达时，S个服务台都忙着，则排成一队等待，先到先服务的单队模型。整个系统的平均服务率为s，*/s，（*0Q0）0.750.750 02020L Lq q2.252.25人人0 01212人人L Ls s3 3人人0 08787人人W Ws s60min60min17174min4minW Wq q45min45min2 24min4min烧伤病人的治疗通常是取烧伤病人的健康皮肤进行

27、自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人例例3某医院挂号室有三个窗口，就诊者的到某医院挂号室有三个窗口，就诊者的到达服从泊松分布，平均到达率为每分钟达服从泊松分布，平均到达率为每分钟0.9人，挂人，挂号员服务时间服从指数分布，平均服务率每分钟号员服务时间服从指数分布，平均服务率每分钟0.4人，现假设就诊者到达后排成一队，依次向空人，现假设就诊者到达后排成一队，依次向空闲的窗口挂号，显然系统的容量和顾客源是不限闲的窗口挂号，显然系统的容量和顾客源是不限的，属于的，属于M/M/SM/M/S型的排队服务模型。求：该系统型的排队服务模型。求：该系统的运行指标的

28、运行指标解解烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人 如果在例如果在例3 3中，就诊者到达后在每个挂中，就诊者到达后在每个挂号窗口各自排成一队，即排成号窗口各自排成一队，即排成3 3队，且进入队，且进入队列后不离开，各列间也互不串换，这就队列后不离开，各列间也互

29、不串换，这就形成形成3 3个队列，而例个队列，而例3 3中的其它条件不变。中的其它条件不变。假设每个队列平均到达率相等且为：假设每个队列平均到达率相等且为：1 12 23 30.9/30.9/30.30.3（人（人/分钟）分钟）这样，原来的这样，原来的M/M/3M/M/3系统就变成了系统就变成了3 3个个M/M/1M/M/1型的子系统。型的子系统。现按现按M/M/1M/M/1型计算主要运行指标，并与型计算主要运行指标，并与上面的例子进行对比分析，结果见表上面的例子进行对比分析，结果见表6 62 2烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请

30、同学们想一想如何来治疗该病人 表表6 62 2 两个模型的比较两个模型的比较指标指标（1 1）M/M/3M/M/3型型（2 2）M/M/1M/M/1型型挂号间空闲挂号间空闲的概率的概率0.07480.07480.250.25（各子系统）（各子系统）就诊者必须等待就诊者必须等待的概率的概率P(N3)=0.57P(N3)=0.570.750.75平均队列长平均队列长1.71.7（人）（人）2.252.25（人）（人）（各子系统）（各子系统）平均队长平均队长3.953.95（人）（人）9 9（人）（人）（整个系统）（整个系统）平均逗留时间平均逗留时间4.394.39（分钟）（分钟）1010（分钟）（分钟）平均等待时间平均等待时间1.891.89（分钟）（分钟）7.57.5（分钟）（分钟）6.6 6.6 排队系统实例分析排队系统实例分析（1 1）快餐店的学问；）快餐店的学问；