中南大学随机过程第十章.ppt

随机过程与排队论,数学科学与计算技术学院胡朝明Email：math_2023年8月30日星期三,2023/8/30,胡朝明,462,上一讲内容回顾,连续参数马尔可夫链转移概率函数、转移矩阵连续参数齐次马氏链初始分布、绝对分布、遍历性、平稳分布转移概率函数的性质状态转移速度矩阵生灭过程,2023/8/30,胡朝明,463,本讲主要内容,排队论简介排队的概念排队系统的基本组成经典排队系统的符号表示方法无限源的简单排队问题的引入等待时间与逗留时间忙期,基本的排队系统 系统M/M/1/队长Little公式输出过程,2023/8/30,胡朝明,464,第四章 排队论简介,排队论，又称为随机服务系统理论，是研究拥挤现象的一门学科，它通过研究各种服务系统在排队等待中的概率特性，来解决系统的最优设计和最优控制。排队论起源于20世纪初丹麦电信工程师A.K.Erlang对电信系统的研究，现已发展成为一门应用广泛的学科，在电信、交通运输、生产与库存管理、计算机系统设计、计算机通信网络、军事作战、柔性制造系统和系统可靠性等众多领域，有着非常重要的应用。,2023/8/30,胡朝明,465,排队的概念,排队是日常生活和工作中常见的现象，由两个方面构成：要求得到服务顾客提供服务服务员或服务台顾客与服务台(二者缺一不可)就构成一个排队系统，或称为随机服务系统。,2023/8/30,胡朝明,466,基本的排队系统,单服务员(台)的排队系统,多服务员(台)的排队系统,2023/8/30,胡朝明,467,排队系统的基本组成,输入过程排队规则服务机构,描述顾客来源及顾客按怎样的规律抵达。,服务是否允许排队，顾客是否愿意排队。在排队等待的情况下服务的顺序是什么。,服务台的数目 服务时间分布,2023/8/30,胡朝明,468,输入过程,描述顾客来源及顾客按怎样的规律抵达。顾客总体数顾客的来源可能是有限的，也可能是无限的到达类型顾客是单个到达，还是成批到达顾客相继到达的间隔时间服从什么概率分布，分布函数是什么，到达的间隔时间之间是否独立在排队论中，一般假定顾客到达的间隔时间序列n|n1相互独立、同分布。,2023/8/30,胡朝明,469,排队规则,服务是否允许排队，顾客是否愿意排队。在排队等待的情况下服务的顺序是什么。损失制 顾客到达时，若所有服务台均被占，服务机构不允许顾客等待，此时该顾客就自动离去等待制 顾客到达时，若所有服务台均被占，他们就排队等待服务先到先服务后到先服务随机服务有优先权服务：强拆型优先权、非强拆型优先权混合制 损失制与等待制的混合对长(容量)有限的混合制等待时间有限的混合制逗留时间有限的混合制,2023/8/30,胡朝明,4610,服务机构,服务台的数目 在多个服务台的情况下，是串联或是并联顾客所需的服务时间服从什么概率分布，每个顾客所需的服务时间是否相互独立，是成批服务或是单个服务,2023/8/30,胡朝明,4611,经典排队系统的符号表示方法,一个排队系统是由许多条件决定的，为简明起见，在经典的排队系统中，常采用35个英文字母表示一个排队系统，字母之间用斜线隔开：,第一个字母表示输入的分布类型第二个字母表示服务时间的分布类型第三个字母表示服务台的数目第四个字母表示系统的容量第五个字母表示顾客源中的顾客数目。,2023/8/30,胡朝明,4612,几个经典排队系统的符号表示,M/M/c/：输入过程是泊松流，服务时间服从负指数分布，有c个服务台平行服务(0c)，容量为无穷的等待制系统M/G/1/：输入过程是泊松流，服务时间独立、服从一般概率分布，只有1个服务台，容量为无穷的等待制系统Ek/G/1/K：相继到达的间隔时间独立、服从k阶爱尔朗分布，服务时间独立、服从一般概率分布，只有1个服务台，容量为k(0k)的混合制系统D/M/c/K：相继到达的间隔时间独立、服从定长分布，服务时间独立、服从负指数分布，有c个服务台平行服务，容量为k(ck)的混合制系统Mr/M/1/：顾客以每批为固定的r个成批到达，批与批的到达间隔时间独立、服从负指数分布，服务时间独立、服从负指数分布，有1个服务台，容量为无穷的等待制系统MX/Mr/1/：顾客成批到达，每批到达的数量X是具有某个离散型概率分布律的随机变量，批与批的到达间隔时间独立、服从负指数分布；顾客成批服务、每批为r个顾客，且服务时间独立、服从负指数分布；有1个服务台；容量为无穷的等待制系统,2023/8/30,胡朝明,4613,等待时间：顾客进入系统的时刻起到开始接受服务止这段时间逗留时间：顾客在系统中的等待时间与服务时间之和,描述排队系统的主要数量指标,队长：系统中的顾客数(包括正在接受服务的顾客)等待队长：系统中的排队等待的顾客数,它们都是随机变量，是顾客和服务机构双方都十分关心的数量指标，应确定它们的分布及有关矩。,系统的忙期：从顾客到达空闲的系统，服务立即开始，直到系统再次变为空闲的这段系统连续繁忙的时间系统的闲期：系统连续保持空闲的时间忙期循环：相邻两次忙期开始的时间间隔,输出过程：也称离去过程，指接受服务完毕的顾客相继离开系统的过程。,在假定到达与服务是彼此独立的条件下，等待时间与服务时间是相互独立的。它们是顾客最关心的数量指标，应用中关心的是统计平衡下它们的分布及期望值。,忙期反映了系统中服务员的工作强度。在排队系统中，统计平衡下忙期与闲期是交替出现的。,刻画输出过程的主要指标是相继离去的间隔时间和在一段已知时间内离去顾客的数目，这些指标从一个侧面反映了系统的工作效率。,。,2023/8/30,胡朝明,4614,第五章 无限源的简单排队系统,顾客来源是无限的输入过程是简单流服务时间服从负指数分布,2023/8/30,胡朝明,4615,5.1 M/M/1/,问题的叙述顾客到达为参数(0)的泊松过程，即相继到达的间隔时间序列n，n1独立、服从参数为(0)的负指数分布F(t)1-e-t，t0；顾客所需的服务时间序列n,n1独立、服从参数为(0)的负指数分布G(t)1-e-t，t0；系统中只有一个服务台；容量为无穷大，而且到达过程与服务过程彼此独立。,2023/8/30,胡朝明,4616,2.队长,假定N(t)表示在时刻t系统中的顾客数，包括正在被服务的顾客数，即N(t)表示时刻t系统的队长，t0，且令,pij(t)PN(t+t)j|N(t)i，i,j0,1,2,则,1)pi,i+1(t)P在t内到达一个而服务未完成 在t内到达j个而服务完j-1个 P1t，1t 1+jt1+j+1，1+j-1t1+j(1-e-t)e-to(t)to(t)i0,1,2,2023/8/30,胡朝明,4617,队长(续1),pi,i-1(t)P在t内未到达而服务完成一个 在t内到达j个而服务完j+1个 P1t，1t 1+jt1+j+1，1+j+1t1+j+2(1-e-t)e-to(t)to(t)i1,2,3,类似分析可得pij(t)o(t)，|i-j|2,2023/8/30,胡朝明,4618,队长(续2),综合上述1)2)3)得,N(t)，t0是可列无限状态E0,1,2,上的生灭过程，其参数为,此生灭过程的绝对分布pj(t)PN(t)=j，j=0,1,2,的福克普朗克方程组为,2023/8/30,胡朝明,4619,队长(续3),令，则称为系统的交通强度(Trafficindensity)。,有如下结论：令pj，j=0,1,2,，则1)当1时，pj0，j=0,1,2,不构成概率分布；2)当1时，pj，j=0,1,2,存在，与初始条件无关，且pj(1-)j，j=0,1,2,构成一个几何概率分布。,2023/8/30,胡朝明,4620,结论,在统计平衡的条件下(1)，,平均队长,等待队长的分布,平均等待队长,2023/8/30,胡朝明,4621,结论(续),在等待条件下的等待队长分布,在等待条件下的平均等待队长,根据队长分布意知：p0=1也是系统空闲的概率，而正是系统繁忙的概率。显然，越大，系统就越繁忙。,2023/8/30,胡朝明,4622,3.等待时间与逗留时间,假定顾客是先到先服务。,定理 在统计平衡(1)下，顾客的等待时间分布函数Wq(t)PWqt为Wq(t)1e-(1-)t，t0,平均等待时间为,等待时间的方差为,2023/8/30,胡朝明,4623,证明,1)当t=0时，有Wq(0)PWq=0P顾客到达时看到的队长为0p0-2)当t0时，有Wq(t)PWq=0P0Wqtp0-0Wqt顾客到达时看到的队长为jpj-其中，pj-表示顾客到达时看到有j个顾客的平稳概率。对于M/M/1/排队系统，有pj-pj，j=0,1,2,于是Wq(t)p0-,2023/8/30,胡朝明,4624,证明(续),平均等待时间,等待时间的方差,。,2023/8/30,胡朝明,4625,逗留时间,由于顾客的逗留时间等于等待时间加上服务时间，即WWq且Wq与相互独立，于是,平均逗留时间,逗留时间的方差,2023/8/30,胡朝明,4626,Little公式,对于一个排队系统，如果在它达到统计平衡,状态后，系统中任一时刻的平均队长、平均等待队长，与每一顾客在系统中的平均逗留时间、平均等待时间 之间有关系式：,成立，则称该排队系统满足Little公式。其中e表示单位时间内实际进入系统的平均顾客数。,2023/8/30,胡朝明,4627,服务的顾客，在他后面排队等待服务的平均顾客数等于在他的平均等待时间内实际进入系统的平均顾客数，即；又考虑一个刚服务结束的顾客，在他离开系统时留在系统中的平均顾客数等于在他的平均逗留时间内实际进入系统的平均顾客数，即。,Little公式的直观解释,在系统达到统计平衡下，可虑一个刚开始接受,显然，M/M/1/排队系统中，Little公式是成立的，且e等于泊松过程的参数。,2023/8/30,胡朝明,4628,4.忙期,从N(t)由0变到1的时刻开始到N(t)第一次又变回0时结束忙期的长度与忙期的起点无关,忙期长度的概率密度,其中，,为修正贝塞尔(Bessel)函数。,忙期长度的分布函数,2023/8/30,胡朝明,4629,忙期(续),平均忙期长度,一个忙期中所服务的平均顾客数,2023/8/30,胡朝明,4630,5.输出过程,在忙期内相继输出的间隔时间是独立、同参数(0)的随机变量，即参数为的泊松流。当系统空闲后，从开始空闲时刻起，到下一个顾客服务完毕离去时之间的间隔时间不与服务时间同分布。,令Tn+表示第n个顾客服务完毕的离去时刻，则Tn+1+-Tn+表示离去的时间间隔，n1，于是，对t0有 PTn+1+Tn+tPNn+=0PTn+1+Tn+t|Nn+=0 PNn+1PTn+1+Tn+t|Nn+1PNn+=0Pn+1n+1t PNn+1Pn+1t其中n+1表示剩余到达间隔时间，与n+1独立，而Nn+表示第n个离去顾客服务完毕离开系统时的队长。,2023/8/30,胡朝明,4631,输出过程(续),因此,由于,此式表示在统计平衡下，相继输出的间隔时间服从参数为（0）的负指数分布。,另外，在统计平衡下，输出的间隔时间相互独立，因此对M/M/1/系统，其统计平衡下的输出过程与到达过程相同。,2023/8/30,胡朝明,4632,例1,某火车站一个售票窗口，若到达该窗口购票的,顾客按泊松流到达，平均每分钟到达1人，假定售票时间服从负指数分布，平均每分钟可售2人，试研究该售票窗口前的排队情况。,解 由题设知，1(人/分)，2(人/分)，该系统按M/M/1/型处理，于是在统计平衡下，有,平均队长为,(人),平均等待队长为,(人),2023/8/30,胡朝明,4633,例1(续),平均等待时间为,(分钟),平均逗留时间为,(分钟),顾客到达不需要等待的概率为,等待队长超过5人的概率为,2023/8/30,胡朝明,4634,例2,考虑某种产品的库存问题。如果进货过多，则会带来,过多的保管费，如果存货不足，则缺货时影响生产，造成经济损失。最好的办法是能及时供应，但由于生产和运输等方面的因素，一般讲这是难以满足的，因此希望找到一种合理的库存s，使得库存费与缺货损失费的总和达到最小。假定需求是参数的泊松流，生产是一个一个产品生产的，每生产一个产品所需时间为参数的负指数分布。库存一个产品的单位时间费用为c元，缺一个产品造成的损失费为h元，寻找一个最优库存量s，使得库存费与损失费之和达到最小（不考虑产品的运输时间）。,2023/8/30,胡朝明,4635,例2(续1),解 把生产产品的工厂看成是服务机构，需求看作是输入,流，于是把问题化成M/M/1/系统，需求量表示队长，pk表示生产厂有k个订货未交的概率。设库存量为s，则缺货时的平均缺货数为,平均库存数为,2023/8/30,胡朝明,4636,例2(续2),单位时间的期望总费用为,用边际分析法解上式，使上式最小的s应满足f(s-1)f(s)，f(s+1)f(s),，于是,由f(s+1)f(s)得,，于是,由f(s-1)f(s)得,因此取最佳s*为最靠近,的正整数即可。,2023/8/30,胡朝明,4637,例3,设船按泊松流进港口，平均每天到达2条，装卸时间,服从负指数分布，平均每天装卸3条船，求：,平均等待对长与平均等待时间；如果船在港口的停留时间超过一个值t0就要罚款，求遭罚款的概率；若每超过一天罚款c元，提前一天奖励b元。假定服务费与服务率成正比，每天h元，装卸一条船收入a元，求使港口每天收入最大的服务率*的值。,2023/8/30,胡朝明,4638,例3(续1),解 由题设知，2(条/天)，3(条/天)，该,系统按M/M/1/型处理。,平均等待对长为,(条船),平均等待时间为,(天),由于遭到罚款当且仅当船在港口的逗留时间超过t0，所以遭到罚款的概率为,从费用方面考虑，每天装卸完条船收入a元，每天服务费为h元。,2023/8/30,胡朝明,4639,例3(续2),平均提前完成时间为,平均延后时间为,所以，港口一天的总收入为,2023/8/30,胡朝明,4640,例3(续3),对f求导得,讨论：,bc时，,bc时，由于 的符号在时完全由括号内的两项决定。令,2023/8/30,胡朝明,4641,例3(续4),由上图看出，y1与y2两曲线有唯一交点，其横坐标为*，,b,(b-c),*,y,y2,y1,且*唯一存在、有限，,2023/8/30,胡朝明,4642,例3(续5),b,(b-c),*,y,y2,y1,bc时，由下图看出，y1与y2两曲线仍有唯一交点，,其横坐标为*，且*唯一存在、有限，,2023/8/30,胡朝明,4643,例4,设顾客到达为泊松流，平均每小时到达个顾客是已知的。一个,顾客在系统内逗留每小时损失c1元，服务机构的费用正比于服务率，每小时每位顾客的费用为c2元。假定服务时间为参数的负指数分布，求最佳服务率*，使得整个系统总费用最少。,解 由于平均对长，所以每小时顾客的平均损失费为 元，每小时服务机构的平均费用为c2元，于是单位时间内平均总费用为,由,得,因为,，所以最佳服务率为*，此时,2023/8/30,胡朝明,4644,本讲主要内容,排队论简介排队的概念排队系统的基本组成经典排队系统的符号表示方法无限源的简单排队问题的引入等待时间与逗留时间忙期,基本的排队系统 系统M/M/1/队长Little公式输出过程,2023/8/30,胡朝明,4645,下一讲内容预告,无限源的简单排队系统M/M/1/具有可变输入率的M/M/1/问题的引入队长等待时间与逗留时间Little公式具有可变服务率的M/M/1/问题的引入队长等待时间与逗留时间,2023/8/30,胡朝明,4646,病人以每小时3人的泊松流到达医院，假设该医院只有一个医生服务，他的服务时间服从负指数分布，并且平均服务一个顾客时间为15分钟。医生空闲时间的比例？有多少病人等待看医生？病人的平均等待时间？一个病人等待超过一个小时的概率？,本节习题,