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