（-数学建模）排队论模型

（ - 数学建模）排队论模型第五讲 排队论模型【修理工录用问题】工厂平均每天有一台机器发生故障而需要修理，机器的故障数服从泊松分布。修理一台机器平均花费20元。现有技术水平不同的修理工人A和B，A种修理工平均每天能修理1.2台机器，每天工资3元；B种修理工平均每天能修理1.5台机器，每天工资5元，两种修理工修理机器的时间为负指数分布。问工厂录用哪种工人较合算？本讲主要内容1. 排队论的基本概念2. 单服务台的排队模型3. 多服务台的排队模型4. 排队系统的最优化问题5. 数学建模实例：校园网的设计和调节收费问题5.1 排队论的基本概念5.1.1 什么是排队系统排队论也称随机服务系统理论，它是20世纪初由丹麦数学家Erlang应用数学方法在研究电话话务理论过程中而发展起来的一门学科，在实际中有广泛的应用。它涉及的是建立一些数学模型，藉以对随机发生的需求提供服务的系统预测其行为。现实世界中排队的现象比比皆是，如到商店购货、轮船进港、病人就诊、机器等待修理等等。排队的内容虽然不同，但有如下共同特征：（1）有请求服务的人或物，如候诊的病人、请求着陆的飞机等，我们将此称为“顾客”。（2）有为顾客提供服务的人或物，如医生、飞机跑道等，我们称此为“服务员”。由顾客和服务员就组成服务系统。（3）顾客随机地一个一个（或者一批一批）来到服务系统，每位顾客需要服务的时间不一定是确定的，服务过程的这种随机性造成某个阶段顾客排长队，而某些时候服务员又空闲无事。为了叙述一个给定的排队系统，必须规定系统的下列组成部分：1.输入过程 即顾客来到服务台的概率分布。排队问题首先要根据原始资料，由顾客到达的规律、作出经验分布，然后按照统计学的方法（如卡方检验法）确定服从哪种理论分布，并估计它的参数值。我们主要讨论顾客来到服务台的概率分布服从泊松分布，且顾客的达到是相互独立的、平稳的输入过程。所谓“平稳”是指分布的期望值和方差参数都不受时间的影响。2.排队规则 即顾客排队和等待的规则。排队规则一般有即时制和等待制两种。所谓即时制就是服务台被占用时顾客便随即离去；等待制就是服务台被占用时，顾客便排队等候服务。等待制服务的次序规则有先到先服务、随机服务、有优先权的先服务等，我们主要讨论先到先服务的系统3.服务机构 服务机构可以是没有服务员的，也可以是一个或多个服务员的；可以对单独顾客进行服务，也可以对成批顾客进行服务。和输入过程一样，多数的服务时间都是随机的，且我们总是假定服务时间的分布是平稳的。若以n表示服务员为第n个顾客提供服务所需的时间，则服务时间所构成的序列n，n=1，2，所服从的概率分布表达了排队系统的服务机制，一般假定，相继的服务时间1，2，是独立同分布的，并且任意两个顾客到来的时间间隔序列Tn也是独立的。如果按服务系统的以上三个特征的各种可能情形来对服务系统进行分类，那么分类就太多了。因此，现在已被广泛采用的是按顾客相继到达时间间隔的分布、服务时间的分布和服务台的个数进行分类。排队论主要是对服务系统建立数学模型，研究如下内容：（1）排队系统的概率分布问题，主要是研究队长分布、等待时间分布和忙期分布等；（2）最优化问题：分为静态最优化和动态最优化，即为系统的最优设计和系统的最优运行问题；（3）排队系统的统计推断：判断一个给定的排队系统符合哪种模型，以便于根据排队理论进行分析研究。5.1.2 排队模型的标准形式排队模型的标准形式为X/Y/Z/A/B/C，其中：X 表示顾客来到时间间隔的分布类型；Y 表示服务时间的分布类型；Z 表示服务员个数；A 系统容量;B 顾客源个数;C 服务规则.例如先来先服务的等待排队模型主要由三参数法即X/Y/Z，“M/M/1/k/FCFS”表示顾客到达间隔时间和服务时间均服从负指数分布，一个服务台，系统至多容纳k个顾客潜在的顾客数不限，先来先服务的排队系统。“M/M/c”即Poisson输入，负指数服务时间分布，c个服务台的等待制排队模型。 “M/G/1”即Poisson输入，一般服务时间分布，单个服务台的等待制排队模型。5.1.3 排队系统的运行指标研究排队问题的目的，是研究排队系统的运行效率，估计服务质量，确定系统参数的最优值，以决定系统的结构是否合理，设计改进措施等。所以，必须确定用来判断系统运行优劣的基本数量指标，这些数量指标通常是：（1）队长 指排队系统中的顾客数，它的期望值记为Ls；排队长，指在排队系统中排队等待服务的顾客数，其期望值记为Lq。系统中的顾客数 = 等待服务的顾客数 + 正被服务的顾客数所以Lq（或Ls）越大，说明服务效率越低。（2）逗留时间 指一个顾客在排队系统中的停留时间，即顾客从进入服务系统到服务完毕的整个时间。其期望值记为Ws。等待时间，指一个顾客在排队系统中等待服务的时间，其期望值记为Wq。逗留时间 = 等待时间 + 服务时间（3）忙期 指从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度，即服务机构连续工作的时间长度。它关系到服务员的工作长度，即服务机构连续工作的时间长度。它关系到服务员的工作强度、忙期的长度和一个忙期中平均完成服务的顾客数，这些都是衡量服务效率的指标。要计算以上这些指标必须知道系统状态的概率，所谓系统状态即时刻t时排队系统中的顾客数。如果时刻t时排队系统中有n个顾客，就说系统的状态是n，其概率一般用Pn(t)表示。求Pn(t)的方法，首先要建立含Pn(t)的关系式，因t为连续变量而n只取非负整数，所以建立的Pn(t)的关系式一般是微分差分方程，这时要求方程的解是不容易的，有时即使求出也很难利用。因此，往往只求稳态解Pn，求Pn并不一定求t时的Pn(t)极限，而只需由Pn(t)=0，用Pn代替Pn(t)即可。5.2 单服务台的排队模型设系统的输入过程服从泊松分布，服务时间服从负指数分布，单服务台的排队系统有以下三种情形：（1）标准型：M/M/1(M/M/1/);（2）系统容量有限制：M/M/1/N/;（3）顾客源为有限的：M/M/1/m.5.2.1标准型：M/M/1M/M/1模型是指顾客源为无限，顾客到达相互独立，到达过程是平稳的，到达率数服从参数为 的泊松分布：单服务台、队长无限、先到先服务；各顾客的服务时间服从参数为的负指数分布，且相互独立。首先求出排队系统在任意时刻t的、状态为n的概率Pn(t)，已知顾客到达率服从参数为的泊松分布，服务时间服从参数为的负指数分布，由此决定了t，t +t时间间隔内：（1）有1个顾客到达的概率为t+o(t)，没有顾客到达的概率是1-t+o(t)。（2）当有顾客在接受服务时，1个顾客被服务完了的概率是 /3 t+o(t)，没有服务完的概率是1-t+o(t)。（3）多于一个顾客到达或服务完的概率为o(t)，均可忽略。注1：因为单位时间内顾客到达数XP（），所以t时间间隔内顾客到达数Y P（t），因而在t时间间隔内有1个顾客到达的概率为：P Y=1 =te-t=t + o(t)，没有顾客到达的概率为PY=0= e-t=1-t + o(t)。注2：由于服务时间TE（），故在有顾客接受服务时，1个顾客被服务完的概率为PTt =1 -e-t=t + o(t)，没有被服务完的概率为1-t + o(t)。在t+t时刻，系统中有n个顾客的状态由t时刻的以下状态转化而来：t时刻系统中有n个顾客，没有顾客到达且没有顾客服务完毕，其概率为：1-t+o(t) 1-t+o(t)= (1-t-t)+o(t)；t时刻系统中有n+1个顾客，没有顾客到达且有1个顾客服务完毕，其概率为：1-t+o(t)t+o(t)= t+o(t)； t时刻系统中有n-1个顾客，有1个顾客到达且没有顾客服务完毕，其概率为：t+o(t)1-t+o(t)= t+o(t)；其他状态的概率为o(t)。因此，在t+t时刻，系统中有n个顾客的概率Pn(t+t)满足：Pn(t+ t)=Pn(t)(1 t t)+Pn+1(t) t+Pn 1(t) t+( t).移项整理，两边同除以t，得Pn(t+ t) Pn(t)( t)=Pn 1(t)+Pn+1(t) (+)Pn(t)+. t t令t0，得dPn(t)=Pn 1(t)+Pn+1(t) (+)Pn(t)dt当n=0时，因为 n=1,2L.P0(t+ t)=P0(t)(1 t)+P1(t)(1 t) t+( t)所以有dP0(t)= P0(t)+P1(t). dt对于稳态情形，与t无关，其导数为零。因此，得到Pn 1+Pn+1 (+)Pn=0,n1 P0+P1=0这是关于Pn的差分方程，也反映出了系统状态的转移关系，即每一状态都是平衡的，求解得P1=(/)P0，递推可得Pn=(/)P0(n1). n由概率的性质知Pn=0n=1，将上式代入 / 1时可得到P0=1 /Pn=(1 /)(/). n因为顾客到达规律服 从参数为的泊松分布，服务时间服从参数为的负指数分布，其 期望值就分别为，1/。所以表示单位时间内平均到达的顾客数，表示单位时间内能服务完的顾客数。如果令=/，这时就表示相同时间内顾客到达的平均数与能被服务的平均数之比，它是刻画服务效率和服务机构利用程度的重要标志，称为服务强度。上面在1，可以证明排队长度将是无限增加的，即使=1的情况下，P0(t)也是随时间而变化的，系统达不到稳定状态.因此，这里只讨论1时情况，从上面的推导知Pn=(1-) n n=0,1,2,.下面计算出系统的运行指标.(1) 队长（平均顾客数）：由于系统的状态为n时即系统中有n个顾客，由期望的定义得Ls=npn=n(1 )n=/(1 )=/( ).n=0n=1(2) 排队长：（等待的平均顾客数）Lq=(n 1)pn=(n 1)n(1 )n=1n=1=2/(1 )=/( ).可以证明，顾客在系统中逗留时间服从参数为-的负指数分布。因此，有(3) 系统中顾客的平均逗留时间：Ws=1/( ).(4) 系统中顾客的平均等待时间：Wq=Ws 1=/( ) 由以上结论可以看出，各指标之间有如下关系：；Lq=Wq； Ls=Ws；Ws=Wq+1/,Ls=Lq+/，这些关系式称为Little公式.在指标的计算过程中，一般只要计算其中一个，其它的指标便可随之导出。5.2.2系统容量有限制：M/M/1/N/ 因为是单服务台，排队系统的容量为N，即是排队等待的顾客最多为N-1，在某时刻一顾客到达时，如系统中已有N个顾客，那么这个顾客就被拒绝进入系统。假设顾客平均到达率为，平均服务率为，在研究系统中有n个顾客的概率Pn(t)时，和标准型M/M/1研究方法相同，当n=N时有PN(t)=PN 1(t) PN(t)在稳态情形下，令=，得 P1=P0 Pn+1+Pn 1=(1+)Pn,n=1,2,L,N 1P=PN 1 N在条件P=1下解上式得到 ii=0N1 P= 01 N+1,1 P=1 n1nN.nN+1 1 注：（1）如果=1（即=），由P0=P1=L=PN=1，即到达率和服务率相等，在N+1稳态情况下系统不会出现排队等待现象；（2）这里因为是有限项的和，所以不要求1（）时，表示单位时间内到达率大于服务率，系统的损失率增加，即被拒绝排队的数量增大.下面给出系统的各种指标的计算结果：（1） 队长：Ls=nP=N+1=nn=0Nn=0NNNnN,=1 2n(1 )nLs=npn=N+1n=1n=01 =(N+1) 1 1 N+1= L s -(1-P0) N+1; ,1（2）排队长：Lq=(n 1)Pn=1NnN N ,=12+1N = ； N+1 N ,1N+1 11（3）逗留时间： Ws=Ls/(1 P0)；（4）等待时间：Wq=Ws 1. 应该指出，Ws，Wq的导出过程中不是采用平均达到率，而是采用有效到达率效。这主要是由于当系统已满时，顾客的实际到达率为零，因为正在被服务的顾客的平均数为1 P0=效/，于是效=(1 P0).5.2.3顾客源为有限的：M/M/1/m对该模型的顾客总体虽只有m个顾客，但每个顾客的到来并接受服务后，仍然回到顾客总体，即可以再次到来，所以对系统的容量是没有限制的，实际上系统中的顾客数永远不会超过m，即与模型M/M/1/m/m的意义相同。与前面情况类似，假设每个顾客的到达率相同为，在系统外的平均顾客数为m-Ls,故系统的有效到达率为e=(m-Ls).考虑稳态的情况，可得系统状态概率的平衡方程为P1=mP0, Pn+1+(m n+1)Pn 1=(m n)+Pn,(1nm 1)P=P.m 1 m注意到Pn=0mn=1，由递推关系不难求得系统状态的概率为1 =,Pi 0mm! i=0(m i)! n !m P= P0,1nm.n (m n)! 该系统的运行指标为Ls=npn=mn=1mN11m(1 P0),Ws= ,Wq=Ws , (1 P0)(+)(1 P0)= L s-(1-P0). Lq=(n 1)Pn=mn=1【例5-1】病人候诊问题 某单位医院的一个科室有一位医生值班，经长期观察，每小时平均有4个病人，医生每小时平均可诊5个病人，病人的到来服从泊松分布，医生的诊病时间服从负指数分布。试分析该科室的工作状况。如果满足99%以上的病人有座，此科室至少应设多少个座位？如果该单位每天24h上班，病人看病1h因耽误工作单位要损失30元，这样单位平均每天损失多少元？如果该科室提高看病速度，每小时平均可诊6个病人，单位每天可减少损失多多少？可减少多少个座位？解 由题意知=4，=5，=4/5，=4/5=0.8C).n+1n 1n其中Pn=0n=1，且=1，由递推关系可得系统状态概率 CC 1k111C 1P0=()+() C!1 k=0k!1nnCn!(P0, Pn=1(nP,nC0n C C!C系统的运行指标为(C)CLs=Lq+，Lq=(n C)Pn=kPk+C=P, 20!(1)C n=C+1k=1Wq=Lq/，Ws=Wq+1/=Ls/.5.3.2系统容量有限制：M/M/C/N/假设系统中有C个服务台，系统的最大容量为N(NC),其它假设同前面一样。当系统客满（即系统中有N个顾客）时，有C个接受服务，N-C个在排队，再有顾客到来将被拒绝而离去，系统将有损失率。当系统的状态为n时，每个服务台的服务率为,则系统的的总服务率：当0nc时为n；当nc时为c，系统的服务强度为= c.类似地，可以得到系统的状态概率平衡方程P1=P0, (n+1)P+P=(+n)P,(1nC) n+1n 1n CP+P=(+C)P,(Cnn)n+1n 1n= pn= 1=CPN.其中Pn=0Nn=1，且=1，由递推关系可得系统状态概率 C1CCN C 11 C( )k (C)+,1, 1 k!C! P0= k=0 CC 1C 1k(C)+(N C+1),=1, k!C k=01n(C)P0,0nC n!Pn= C C()nP,Cnn.0 c!系统的运行指标为Ls=Lq+C(1 PN)，(C)CN CN C1()(1), Lq=(n C)Pn=P N C 02C!(1 )n=C+1NWq=Lq(1 PN),Ws=Wq+1/.CCN系统满员的损失率为P损=PN=P0. C!特别地，当N=C时，即M/M/C/C/,此时系统为即时制服务，不允许顾客在系统内排队，亦即系统的状态概率为1 1(C)nP0=(),Pn=P0, k!C!k=0C 1k相应地运行指标为C1Lq=Wq=0,Ws=,Ls=nPn=C(1 PC). n=15.3.3顾客源为有限的：M/M/C/m假设同前面的模型相同，系统的状态概率的平衡方程为P1=mP0, (n+1)P+(m n+1)P=(m n)+nP,(1nC) n+1n 1n CP+(m C+1)P=(m C)+CP,(Cnm)n+1n 1n= pm= 1=CPm.由递推关系可得状态概率