《数学建模排队论.ppt》由会员分享，可在线阅读，更多相关《数学建模排队论.ppt（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数学建模讲座排排 队队 论论 模模 型型高秀娟高秀娟2008年年7月月1日日排队系统的描述排队系统的描述顾客总体顾客总体队伍队伍服务台服务台服务系统输出输出输入输入排队服务系统的基本概念排队服务系统的基本概念输入过程：描述顾客来源是按怎样的规律抵达排队输入过程：描述顾客来源是按怎样的规律抵达排队系统。系统。1.顾客源总体顾客源总体:有限还是无限有限还是无限2.到达类型：单个到达还是成批到达到达类型：单个到达还是成批到达 3.相继顾客到达的时间间隔：相互独立、同分布的相继顾客到达的时间间隔：相互独立、同分布的;等时间间隔的等时间间隔的;服从服从Poisson分布的；分布的；k阶阶Erlang分分
2、布布泊松分布泊松分布适合于描述单位时间内随机事件发生的次数。如某一服务设施在一适合于描述单位时间内随机事件发生的次数。如某一服务设施在一定时间内到达的人数，电话交换机接到呼叫的次数，汽车站台的候客人数，定时间内到达的人数，电话交换机接到呼叫的次数，汽车站台的候客人数，机器出现的故障数，自然灾害发生的次数等等。机器出现的故障数，自然灾害发生的次数等等。排队服务系统的基本概念排队服务系统的基本概念排队规则：指服务系统是否允许排队，顾客是否愿意排队排队规则：指服务系统是否允许排队，顾客是否愿意排队1.损失制排队系统：顾客到达若所有服务台被占，服务损失制排队系统：顾客到达若所有服务台被占，服务机构又不
3、允许顾客等待，此时该顾客就自动离去。机构又不允许顾客等待，此时该顾客就自动离去。2.等待制排队系统：顾客到达时若服务台均被占，他们等待制排队系统：顾客到达时若服务台均被占，他们就排队等待。服务顺序有：先到先服务、后到先服务、就排队等待。服务顺序有：先到先服务、后到先服务、随机服务、有优先权的服务随机服务、有优先权的服务3.混合制排队系统：损失制与等待制的混合。队长（容混合制排队系统：损失制与等待制的混合。队长（容量）有限的混合；等待时间有限的混合；逗留时间有限量）有限的混合；等待时间有限的混合；逗留时间有限的混合的混合排队服务系统的基本概念排队服务系统的基本概念服务机构：服务机构：1.服务台的
4、数目服务台的数目2.顾客所需的服务时间服从怎样的概率分布顾客所需的服务时间服从怎样的概率分布(常见顾客的服务时间分布有常见顾客的服务时间分布有:定长分布、负定长分布、负指数分布、超指数分布、指数分布、超指数分布、k阶阶Erlang分布、分布、几何分布、一般分布几何分布、一般分布)排队论模型的符号表示排队论模型的符号表示通常由通常由3-5个英文字母组成，个英文字母组成，其形式为其形式为 A/B/C/n，其中其中 A表示输入过程，表示输入过程，B表示服务时间，表示服务时间，C表示服务台数目，表示服务台数目，n表示系统空间数表示系统空间数排队模型的表示：排队模型的表示：X/Y/Z/A/B/CX顾客相
5、继到达的间隔时顾客相继到达的间隔时间的分布；间的分布；Y服务时间的分布；服务时间的分布；Z服务台个数；服务台个数；A系统容量限制（默认为系统容量限制（默认为）；）；B顾客源数目（默认为顾客源数目（默认为）；）；C服务规则服务规则（默认为先到（默认为先到先服务先服务FCFS)。M负指数分布、负指数分布、D确定确定型、型、Ek k阶爱尔朗分布。阶爱尔朗分布。描述排队论系统的主要数量指标描述排队论系统的主要数量指标1.1.队长队长(L(Ls s)：指在系统中顾客的平均数：指在系统中顾客的平均数 等待队长等待队长(L(Lq q)：指系统中等待的顾客的平均数：指系统中等待的顾客的平均数2.2.顾客的平均
6、等待时间顾客的平均等待时间(W(Wq q)：指顾客进入系统的时刻起到开始接：指顾客进入系统的时刻起到开始接 受服务止的平均时间受服务止的平均时间与平均逗留时间与平均逗留时间(W(Ws s)：指顾客在系统中平均等待时间与平均服务：指顾客在系统中平均等待时间与平均服务时间之和时间之和3.3.系统的忙期与闲期系统的忙期与闲期服务机构工作强度服务机构工作强度=由于服务顾客的时间由于服务顾客的时间/服务设施总的服务时间服务设施总的服务时间 =1-1-服务设施总的空闲时间服务设施总的空闲时间/服务设施总的服务时间服务设施总的服务时间与排队论模型有关的与排队论模型有关的LINGO函数函数1.peb(load
7、,S)该函数返回值是当到达负荷为该函数返回值是当到达负荷为load，系统中有，系统中有S个服务台且允个服务台且允许排队时系统繁忙的概率，也就是顾客等待的概率许排队时系统繁忙的概率，也就是顾客等待的概率2.pel(load,S)该函数返回值是当到达负荷为该函数返回值是当到达负荷为load，系统中有，系统中有S个服务台且不个服务台且不允许排队时系统损失的概率，也就是顾客得不到服务离开的概允许排队时系统损失的概率，也就是顾客得不到服务离开的概率率3.pfs(load,S,K)该函数的返回值是当到达负荷为该函数的返回值是当到达负荷为load，顾客数为，顾客数为K,平行服务台平行服务台数量为数量为S时，
8、有限源的时，有限源的Poisson服务系统等待或返修顾客数的期服务系统等待或返修顾客数的期望值望值等待制排队模型等待制排队模型等待制排队模型中最常见的模型是：等待制排队模型中最常见的模型是：M/M/S/,即顾客到达系统的相继到达时间间隔独立，且即顾客到达系统的相继到达时间间隔独立，且服从参数为服从参数为的负指数分布（即输入过程为过的负指数分布（即输入过程为过程），服务台的服务时间也独立同分布，且服程），服务台的服务时间也独立同分布，且服从参数为从参数为的负指数分布，而且系统空间无限，的负指数分布，而且系统空间无限，允许永远排队允许永远排队等待制排队模型等待制排队模型的基本参数的基本参数1 1.
9、顾客等待的概率顾客等待的概率:P:Pwaitwait=peb(load,S),=peb(load,S),其中其中S S是服务台或服务员的个数，是服务台或服务员的个数，load=load=/=RT,/=RT,其中其中R=,T=1/R=,T=1/，R R是顾客的平均到达率，是顾客的平均到达率，T T是平均是平均服务时间服务时间2.2.顾客的平均等待时间顾客的平均等待时间：W Wq q=P=PwaitwaitT/(S-load),T/(S-load),其中其中T/(S-load)T/(S-load)可以看成一个合理的长度间隔，可以看成一个合理的长度间隔，3.3.顾客的平均逗留时间、队长和等待队长顾客
10、的平均逗留时间、队长和等待队长（littlelittle公式）公式）W Ws s=W=Wq q+1/+1/=W=Wq q+T L+T Ls s=W Ws s=RW=RWs s Lq=Wq=R Wq等待制排队模型实例等待制排队模型实例1.S=1(M/M/1/)例例1：某维修中心在周末现只安排一名员工为顾客提供服务，：某维修中心在周末现只安排一名员工为顾客提供服务，新来维修的新来维修的 顾客到达后，若已有顾客正在接受服务，则需要顾客到达后，若已有顾客正在接受服务，则需要排队等待，假设来维修的顾客到达过程为排队等待，假设来维修的顾客到达过程为Poisson流，平均每流，平均每小时小时4人，维修时间服
11、从负指数分布，平均需要人，维修时间服从负指数分布，平均需要6min,试求该试求该系统的主要数量指标。系统的主要数量指标。2.S=3(M/M/S/)例例2：设打印室有：设打印室有3名打字员，平均每个文件的打印时间为名打字员，平均每个文件的打印时间为10min,而文件到达率为每小时而文件到达率为每小时15件，试求该打印室的主要数件，试求该打印室的主要数量指标。量指标。等待制排队模型实例等待制排队模型实例例例1：Model:S=1;R=4;T=6/60;load=R*T;Pwait=peb(load,S);W_q=Pwait*T/(S-load);L_q=R*W_q;W_s=W_q+T;L_s=W_
12、s*R;End例例2：Model:S=3;R=15;T=10/60;load=R*T;Pwait=peb(load,S);W_q=Pwait*T/(S-load);L_q=R*W_q;W_s=W_q+T;L_s=W_s*R;END损失制排队模型损失制排队模型损失制排队模型通常记为损失制排队模型通常记为 M/M/S/S,当当S个服务器被占用后，顾客自动离个服务器被占用后，顾客自动离去去损失制排队模型的基本参数损失制排队模型的基本参数1.系统损失的概率：系统损失的概率：Plost=pel(load,S)2.单位时间内平均进入系统的顾客数：单位时间内平均进入系统的顾客数：e=Re=e=Re=(1-P
13、lost)=R(1-Plost)3.系统的相对通过能力系统的相对通过能力(Q)与绝对通过能力与绝对通过能力(A)Q=1-Plost,A=eQ=(1-Plost)2=ReQ=R(1-Plost)2 4.系统在单位时间内占用服务台的均值系统在单位时间内占用服务台的均值:Ls=e/=ReT 注意：在损失制系统中，注意：在损失制系统中，Lq=0,即等待队长为即等待队长为05.系统服务台的效率：系统服务台的效率：=Ls/S6.顾客在系统内平均逗留时间顾客在系统内平均逗留时间:Ws=1/=T注意：在损失制系统中，注意：在损失制系统中，Wq=0,即等待时间为即等待时间为0损失制排队模型实例损失制排队模型实例
14、S=1(M/M/1/1)例例1：设某条电：设某条电话线，平均每话线，平均每分钟有分钟有0.6次呼次呼唤，若每次通唤，若每次通话时间平均为话时间平均为1.25min,求系求系统相应的参数统相应的参数指标。指标。model:S=1;R=0.6;T=1.25;load=R*T;Plost=pel(load,S);Q=1-Plost;R_e=Q*R;A=Q*R_e;L_s=R_e*T,eta=L_s/S;endEta-损失制排队模型实例损失制排队模型实例S1(M/M/S/S)例例2：某单位电话交换台有一台：某单位电话交换台有一台200门内线的总门内线的总机，已知在上班机，已知在上班8小时内，有小时内，
15、有20%的内线分机的内线分机平均每平均每40min要一次外线电话，要一次外线电话，80%的分机的分机平均间隔平均间隔120min要一次外线。又知外线打入要一次外线。又知外线打入内线的电话平均每分钟内线的电话平均每分钟1次。假设与外线通话次。假设与外线通话的时间为平均的时间为平均3min，并且上述时间均服从负，并且上述时间均服从负指数分布，如果要求电话的通话率为指数分布，如果要求电话的通话率为95%，问该交换台应设置多少条外线？问该交换台应设置多少条外线？损失制排队模型实例损失制排队模型实例例例2：分析：分析：1)电话交换台的服务分成两类，第一类内电话交换台的服务分成两类，第一类内线打外线，其强
16、度为线打外线，其强度为 1=（0.260/40+0.860/120）200=140第二类是外线打内线，其强度为第二类是外线打内线，其强度为 2=160=60因此总的强度为因此总的强度为 =1+2=140+60=2002)按题目要求，系统损失的概率不能超过按题目要求，系统损失的概率不能超过5%，即，即Plost0.053）外线是整数，在满足条件下，条数越）外线是整数，在满足条件下，条数越少越好少越好Model:R=200;T=3/60;load=R*T;Plost=pel(load,S);Plost=0.05;Q=1-Plost;R_e=Q*R;A=Q*R_e;L_s=R_e*T;eta=L_s
17、/S;Min=S;gin(S);end混合制排队模型混合制排队模型混合制排队模型通常记为：混合制排队模型通常记为：M/M/S/K,即有即有S个服个服务台或服务员，系统空间容量为务台或服务员，系统空间容量为K，当，当K个位置已个位置已被顾客占用时，新到的顾客自动离去，当系统中被顾客占用时，新到的顾客自动离去，当系统中有空位置时，新到的顾客进入系统排队等待。有空位置时，新到的顾客进入系统排队等待。闭合式排队模型闭合式排队模型设系统内有设系统内有M个服务台，顾客到达系统的间隔时间个服务台，顾客到达系统的间隔时间和服务台的服务时间均为负指数分布，而系统的容和服务台的服务时间均为负指数分布，而系统的容量
18、和潜在的顾客数都为量和潜在的顾客数都为K，顾客到达率为，顾客到达率为，服务，服务台的平均服务率为台的平均服务率为，这样的系统称为闭合式排队，这样的系统称为闭合式排队模型，记为：模型，记为：M/M/S/K/K闭合式排队模型的基本参数闭合式排队模型的基本参数1.平均队长：平均队长：Ls=pfs(load,S,K),load=K/=KRT即即:系统的负荷系统的负荷=系统的顾客数系统的顾客数顾客到达率顾客到达率顾客的服务时间顾客的服务时间2.单位时间平均进入系统的顾客数单位时间平均进入系统的顾客数:e=（KLs）=R(KLs)=Re3.顾客处于正常情况的概率顾客处于正常情况的概率:P=(KLs)/K4
19、.平均逗留时间、平均等待队长和平均排队等待时间平均逗留时间、平均等待队长和平均排队等待时间Ws=Ls/e=Ls/Re Lq=Ls e/=Ls-ReTWq=Ws1/=WsT5.每个服务台的工作强度每个服务台的工作强度:Pwork=e/(S)排队系统的最优化模型排队系统的最优化模型1.系统服务时间的确定系统服务时间的确定例：某工人照管例：某工人照管4台自动台自动机床，机床运转时间平均机床，机床运转时间平均为负指数分布，假定平均为负指数分布，假定平均每周有一台机床损坏需要每周有一台机床损坏需要维修，机床运转单位时间维修，机床运转单位时间内平均收入内平均收入100元，而每元，而每增加一单位增加一单位的
20、维修费用的维修费用为为75元，求使总利益达到元，求使总利益达到最大的最大的*分析分析：这是一个闭合式排队：这是一个闭合式排队系统系统M/M/1/K/K,且且K=4，设，设Ls是队长，则正常运转的机是队长，则正常运转的机器为器为KLs部，因此目标函部，因此目标函数为：数为：f=100(KLs)75 Model:S=1;K=4;R=1;L_s=pfs(K*R/mu,S,K);Max=100*(K=L_s)-75*mu;end排队系统的最优化模型排队系统的最优化模型2.系统服务台的确定系统服务台的确定例：一个大型露天矿山，例：一个大型露天矿山，正考虑修建矿石卸位的个正考虑修建矿石卸位的个数，估计运矿
21、石的车将按数，估计运矿石的车将按Poisson流到达，平均每流到达，平均每小时小时15辆，卸矿石时间服辆，卸矿石时间服从负指数分布，平均从负指数分布，平均3min卸一辆，又知每辆运送矿卸一辆，又知每辆运送矿石的卡车售价是石的卡车售价是8万元，修万元，修建一个卸位的投资是建一个卸位的投资是14万万元，问应建多少个矿石卸元，问应建多少个矿石卸位最为适宜？位最为适宜？分析：用等待制排队系统分析：用等待制排队系统M/M/S/进行分析进行分析,其费用包括其费用包括建造卸位的费用和卡车处于排建造卸位的费用和卡车处于排队状态不能工作的费用，目标队状态不能工作的费用，目标函数为：函数为：F=14S+8LsMo
22、del:R=15;T=3/60;load=R*T;Pwait=peb(load,S);W_q=Pwait*T/(S-load);W_s=W_q+T;L_s=W_s*R;Min=8*L_s+14*S;gin(S);bnd(1,S,5);end试试着着做做一一做做某售票点有两个售票窗某售票点有两个售票窗口，顾客按参数口，顾客按参数=8人人/min的的Poisson流到达，流到达，每个窗口的售票时间服每个窗口的售票时间服从参数从参数=5人人/min的负的负指数分布，试比较以下指数分布，试比较以下两种排队方案的运行指两种排队方案的运行指标，并指出哪种售票方标，并指出哪种售票方式效率更高。式效率更高。=5=5=5=5=8 1=4 2=4 1）顾客到达后，以）顾客到达后，以1/2的概率站成的概率站成两个队列，如下图两个队列，如下图=8 到达离去离去离去离去2）顾客到达后排成一个队列，顾）顾客到达后排成一个队列，顾客发现哪个窗口空闲时，他就接客发现哪个窗口空闲时，他就接受该窗口的服务，如下图受该窗口的服务，如下图到达