单服务员排队模型及其蒙特卡洛模拟.doc

单服务员排队模型及其蒙特卡洛模拟张建航等:单服务员排队模型及其蒙特卡洛模拟单服务员排队模型及其蒙特卡洛模拟张建航,李宗成,宋晓峰(西安通信学院陕西西安710106)摘要:单服务员的排队模型(M/M/1模型)是排队论中重要的排队系统.介绍排队论的基本概念,讨论和研究单服务员排队模型的过程和基本原理,通过数学计算得出单服务员排队模型中重要的运行指标.针对典型实例,借助于计算机软件包Matlab6.5进行了蒙特卡洛模拟.关键词:单服务员排队模型;Matlab6.5;蒙特卡洛方法;排队论中图分类号:0226;TP311.12文献标识码:B文章编号:1004373X(2006)2404402M/M/1ModelandtheSolvingbyUsingtheMonteCarloMethodZHANGJianhang,LIZongcheng,SONGXiaofeng(Xifl,nCommunicationInstitute.Xian.710106.China)Abstract=M/M/1modelistheimportantqueuesystemofqueuingtheory.Thebasicconceptionsofqueuingtheoryareintroduced.ThebasicprinciplesandprocessesofM/M/1modelarediscussedandstudied.WehavedrawntheimportantoperationindexformulasinM/M/1modelbymathematicalcalculating.WiththehelpofcomputersoftwareMatlab6.5,atypicalexampleissolvedbyusingtheMonteCarlomethod.Keywords=M/M/1modelMatlab6.5;MonteCarlomethodlqueuingtheory1引言排队论(queuingtheory)也称为随机服务系统理论.随机服务系统是指对随机发生的需求提供服务的系统.现实世界中排队现象比比皆是,如商店购物,轮船进港,病人候诊,银行存取款,机器等待维修,电话等待转接,计算机数据等待处理等.排队论的内容包罗万象,但都具有3个共同特征:(1)有请求服务的人和物,如候诊的病人,称之为"顾客".(2)有为顾客提供服务的人和物,如医生,称之为"服务员".(3)顾客到来的时刻及需要服务的时间均是随机的.排队论的主要任务是,建立数学模型描述排队系统的概率规律性,研究诸如顾客平均的排队时间,排队顾客的平均数,服务员平均接待的顾客等数量规律,为系统的最优设计和最优控制提供决策依据.2单服务员的排队模型(M/M/1)M/M/1模型是指适合以下3个条件的排队系统:(1)输入过程:顾客源是无限的,顾客单个到来,相互独立,一定时间的到达数服从普阿松分布(Poisson分布).收稿日期:2006061644(2)排队规则;单队且对队长没有限制,先到先服务.(3)服务机构:单服务台,各顾客的服务时间是相互独立的,服从相同的负指数分布.此外,还假定到达间隔时间和服务时间是相互独立的.设单位时间内顾客到达数服从参数为的Poisson分布每位顾客的服务时间服从参数为的负指数分布.于是在It,t+at时间区间内分为:(1)顾客到达数服从参数为RAt的Poisson分布,故在该区间内有一个顾客到达的概率为).Atexp-RAtRAt+O(At);没有顾客到达的概率是1一AAtO(At)(2)设顾客接受服务时间为T,则在该区间内有一个顾客接受完服务离去的概率为:P(Tr+TlT>r)一l_P(T>r+丁l丁>r)一1一P(T>At)=1一exp一FAt一FAt+O(At)没有顾客离去的概率为1一FAtO(At).(3)多于一个顾客到达或离去的概率为O(At),可以忽略.因此,在t+At时刻,系统中有"个顾客的概率P(t十At)满足:P(t+At)一P()(1一AAt)(1FAt)+P()2At?FAt+P.()(1一)FAt+P()(1一FAt)一P()(1一RAtFAt)+P1(t)FAt+P,卜()AAt+O(At)于是有:2006年第24期总第239!±.垒!二!一¨-(+)+令一o,得到方程:一()+()一(+)P(f)df其中一1,2,;当一0时可以得到:一一.()+()dt'对于稳态情形,P(f)与t无关,其导数为0.因此可得差分方程如下:ftP1+1一(+)P一011一.+一0解此方程得到:一(丢)"?P.,+gto=丢<1,由于P=l'故一丢一一I.,从而得到:/P.一一P(1)lP(1一I.).一1,2,式(1)中J.有其实际意义,称为服务强度.他表示平均到达率与平均服务率之比;他也是一个顾客的平均服务时间1/和平均到达间隔1/Z之比.以式(1)为基础计算系统运行的指标如下:(1)在系统中的平均顾客数(队长的期望值):Ls一一n=Or一(2)在队列中等待的平均顾客数(队列长的期望值):L.一-1)P一可以证明,在M/M/1系统条件下,顾客在系统中的逗留时间服从参数为一的负指数分布.(3)在系统中顾客逗留时间的期望值:w一(4)在队列中顾客等待时间的期望值:w一P_3M/M/l模型的蒙特卡洛模拟举例在某商店有一个售货员,顾客陆续到来,当顾客到来的较多时,一部分顾客便需排队等待,被接待后的顾客便离开商店.设:(1)顾客到来时间间隔0服从均值为0.1的负指数分布;(2)对顾客的服务时间T服从E4,15上的均匀分布(3)排队按先到先服务规则,队长无限制.假定时间1min为单位,一个工作日为8h.问题一,模拟一个工作日内完成服务的个数及顾客平均等待时间;问题二,模拟100个工作日,求出每日完成服务的个数及每日顾客的平均等待时间.蒙特卡洛(MonteCarlo)方法是一种应用随机数来进行模拟试验的方法口对于所求问题,模拟过程见图1流程图:图1模拟过程流程图在Matlab6.5软件包中提供了用于生成服从一定分布规律的随机数的函数.采用Matlab6.5软件包编程求解此问题.用Matlab6.5编程如下(对于问题一):(下转第48页)45).-锄一一一一;:,一._唧m一一一一一一一一一一一.蠹一一王文娟:机械振动分析的Matlab/Simulink仿真研究一些S函数模板打开,对其进行修剪就可以了.将S函数以M文件的形式保存起来,然后建立振动系统的SFunction模型,如图4所示.图4和图2得到的模型外观上基本一样,但是却选用不同的模块来建立的.直接启动仿真过程,所得结果同上.图4Simulink模型图为了将仿真结果绘在一张图上便于分析,建立一个名为zhdwy的M文件如下;subplot(2,1,1)plot(tout,your(:,I),b,tOut,your(1,2),r,tout,yout(:,3),k)ylabel(振动物体的位移)legend(xl,x2,x3,4)lgridminorsubplot(2,1,2)plot(tout,yout(:,4),b,tout,yout("5),r,tout,yout(,6),k)ylabel(振动物体的速度)xlabel(t的取值范围)legend(vl,v2,v3,2)f在Matlab命令窗口中输入zhdwy,按回车键,得到图5所示的结果.上边的图为系统的位移图,下边的图为系统的速度图.从图上可以很清楚地看到系统中各个物体的振动情况,具体数值可在Matlab的工作空问中查看.05星.萎5囊.l萋.释.0,5需螭?1rrrrrr.rI,的取值范围4结语图5振动系统的位移和速度图通过对机械振动系统的Matlab/Simulink建模研究,可以看出采用SFunction模块建模其模型非常简单,可读性好,而且S函数的编写只要对系统自带的S函数模板进行适当的修改就行了,这样的建模方法非常灵活.Sireulink的仿真功能非常强大,利用他来解决工程实际问题,非常高效.把设计工作的非风险降到最低.同时,通过对现有系统进行仿真,可对系统进行适当的维修和保护.参考文献El-1李南南,吴清,曹辉林.Matlab7简明教程M.北京t清华大学出版社,2006.E23黄永安,马路,刘慧敏.Matlab7.O/Simulink6.0建模仿真开发与高级工程应用M.北京:清华大学出版社,2006.3张淼,张正亮.Matlab仿真技术与实例应用教程I-M.北京:机械工,I出版社,2004.(上接第45页)对于问题二,将此程序略加修改即可.经过计算可得采用蒙特卡洛方法对M/M/1模型进行模拟是一种行之模拟结果:一个工作日内完成服务的个数为45人,顾客平有效的方法,和实际的结果比较吻合,为进一步复杂系统均等待时间为33min;100个工作日,平均每日完成服务的求解提供思路.的个数为44人,每日顾客的平均等待时间为28min.4结语在M/M/1模型中,服务规则是先到先服务.实际上对于不同的服务规则(先到先服务,后到先服务,随机服务)他们的不同点主要反映在等待时间的分布函数的不同,而一些期望值是相同的,上述的各种指标都是期望值,所以这些指标的计算公式对3种服务规则都是适应的.48参考文献El3钱颂迪.运筹学I-M.北京:清华大学出版社,1999.I-2-1徐仲济.蒙特卡罗方法M.上海.上海科学技术出版社,1985.f3赵静,但琦.数学建模与数学实验EM.jE京:高等教育出版社,2002.作奢简介张建航男,1979年出生,陕西札泉县人,助教.主要从事计算数学和运筹学与控制论方向的研究