为了正常的体验网站,请在浏览器设置里面开启Javascript功能!

多服务台等待制排队模型M_G_c_的蒙特卡洛模拟

2012-09-12 4页 pdf 202KB 217阅读

用户头像

is_330366

暂无简介

举报
多服务台等待制排队模型M_G_c_的蒙特卡洛模拟 第11卷 第1期 2012年3月     太 原 师 范 学 院 学 报 (自然科学版) JOURNAL OF TAIYUAN NORMAL UNIVERSITY(Natural Science Edition)   Vol.11 No.1   Mar.2012 多服务台等待制排队模型M/G/c/∞的蒙特卡洛模拟 * 王培勋 王志芳 (西安财经学院 统计学院,陕西 西安710100)   〔摘要〕 文章以排队论为基础,用蒙特卡洛在 Matlab上对多服务台等待制排队模型M/G/c/ ∞进行了模拟,得到了系统的一些...
多服务台等待制排队模型M_G_c_的蒙特卡洛模拟
第11卷 第1期 2012年3月     太 原 师 范 学 院 学 报 (自然科学版) JOURNAL OF TAIYUAN NORMAL UNIVERSITY(Natural Science Edition)   Vol.11 No.1   Mar.2012 多服务台等待制排队模型M/G/c/∞的蒙特卡洛模拟 * 王培勋 王志芳 (西安财经学院 统计学院,陕西 西安710100)   〔摘要〕 文章以排队论为基础,用蒙特卡洛在 Matlab上对多服务台等待制排队模型M/G/c/ ∞进行了模拟,得到了系统的一些指标,如系统队长,顾客逗留时间等,并通过两个实例说明了该方 法的可行性,为处理此类排队问题提供了一个新的方法. 〔关键词〕 多服台等待制模型;蒙特卡洛模拟;排队论;动态模拟 〔文章编号〕 1672-2027(2012)01-0095-04 〔中图分类号〕 TP311.1 〔文献标识码〕 A 0 引言 排队论,或称随机服务系统理论,是通过对服务对象到来及服务时间的统计研究,得出诸如等待时间排 队长度,忙期长短等这些数量指标的统计规律,然后根据这些规律来改进服务系统的结构或重新组织被服务 对象,使得服务系统能满足服务对象的需求,又能使机构的费用最经济或某些指标最优,这些指标一般可以 通过数学推导得到.但是在实际问题中所碰到的排队问题往往不具有马尔科夫性,这时用数学推导就比较困 难.随着计算机技术的发展,运用计算机仿真的方法来研究排队模型已成为解决这类排队问题的有效方法. 国内外学者在研究这类问题已经取得了一些成果,如张建航等在论文中给出了单服务台排队模型M/M/1/ ∞的蒙特卡洛模拟,得到了顾客的等待时间和系统队长[1],李鹏等通过 Matlab平台对单服务台有限队长的 排队系统进行了仿真,仿真出各个顾客到达时刻与离开时刻曲线,等待时间与停留时间曲线[2],吴可嘉在 Excel上实现了对单对多服务台的模拟,得出了学校食堂应该再增加一个窗口可以满足服务需求的结论[3]. 但是目前对多服务台等待制排队模型 M/G/c/∞的模拟还是比较少的,本文运用蒙特卡洛模拟方法,研究 M/G/c/∞模型的仿真算法. 1 排队论及 M/G/c/∞模型介绍 排队论是研究系统随机聚散现象和随机服务系统工作过程的数学理论和方法,排队论的排队规则分为 3类:损失制、等待制和混合制.其中,损失制是指顾客到达时,如果所有服务台都没有空闲,该顾客不愿等 待,就随即从系统消失;等待制是指顾客到达时,如果所有服务台都没有空闲,他们就排队等待;混合制是指 既有等待又有损失的情况,如顾客等待时考虑排队的队长、等待时间的长短等因素而决定去留. 本文所模拟的是多服务台等待制排队模型M/G/c/∞,系统空间是无限的,顾客来源也是无限的,即设 系统有c个服务窗口并联排列,各服务窗口独立工作,又各窗口的服务时间服从一般分布G,假设顾客按参 数为λ的泊松分布到达,即顾客到达的间隔服从指数分布,如果顾客到达系统时c个服务窗都忙着,则顾客 排队等待,并且假设各个服务窗口工作时相互独立的遵循先到先服务原则,允许永远排队. 2 随机数的产生 1)在各种统计计算中常需要产生各种概率分布的随机数,而大多数概率分布的随机数的产生均基于均 匀分布U(0,1)的随机数,产生随机数的基本方法有三种,逆变换法,合成方法,筛选方法.这里我们用拟变换  * 收稿日期:2011-12-24    作者简介:王培勋(1956-),男,甘肃岷县人,硕士,西安财经学院统计学院教授,主要从事统计建模研究. 法来产生分布函数的随机数.首先介绍逆变换法.设随机变量X 的分布函数为F(X),定义F-1(y)=inf x:F(x)≥ }{ y ,0≤y≤1,有如下定理: 定理 设随机变量U~U(0,1),则X=F-1(U)的分布函数为F(x)[4]. 由此定理我们可以知道要产生来自F(x)的随机数,只要先产生来自U(0,1)的随机数u,然后计算 F-1(u)即可,具体步骤是首先由U(0,1)抽取u,然后计算x=F-1(u),其中F-1如上诉中定义.当我们得到 了分布函数的随机数的产生方法以后,我们就可以进行随机模拟了,随机模拟方法也称为蒙特卡洛模拟方 法,它是以概率统计理论为基础,利用电子计算机数字模拟技术,解决一些很难直接用数学求解或用其他方 法不能解决的问题,它的实质是运用一连串的随机数来模拟可能出现的随机现象. 2)仿真系统模拟,设T为模拟系统的总服务时间,t为时间变量,t1 为顾客的到达系统的时间,d为1×c 矩阵,第j列第j个服务台上顾客的离开的时间,t2=min(d),即顾客最早离开服务台的时间,n为在t 时刻当前到达系统中的顾客数,A为在t时刻到达系统中的所有顾客总数.设循环变量为i,g(i)记录在一次 循环中不同事件发生的时间间隔,h(i)记录在一次循环中系统中的顾客数,c为1×c矩阵,记录c个服务台 的工作状态,其中元素为1示该服务台正忙,元素为0表示该服务台处于空闲状态,设变量b为系统当前 的顾客数. 模拟算法; Step1 初始化,输入模拟系统的总服务时间T,设t=0,n=0,A=0此时系统中没有顾客,所有服务台 都空闲,c矩阵各列元素都为0,d矩阵各列元素都是∞,b=0. Step2 产生第一个顾客进入系统的时间t1,这时循环变量i=0. Step3 进入循环,i=i+1,h(i)=b,如果t1<T,则有g(i)=min(t1-t2)-t,否则结束. Step4 如果t1<t2,说明顾客进入系统的时间小于服务台上顾客的离开时间,使t=t1,产生下一顾客进 入系统的时间t1,这时总顾客数多了一个,A=A+1,n=n+1,b=n,即系统中的顾客数也加1,如果有c(j) =0,说明第j个服务台空闲,将系统中的顾客分配给第j个服务台,同时产生第j个服务台上顾客的离开时 间. Step5 如果t1≥t2,说明有顾客离开服务台,使t=t2,系统中的顾客减少了一个,n=n-1,b=n,此时如 果系统中还有顾客,就上前服务,同时产生其离开时间,然后转Step3,直至t1>T. 3 实例分析 实例1 设有3个打字员,平均打印文件的速度为μ=6份/小时,文件到达率为15份/小时,试求1)在 打字室内现在有的平均文件数;2)每份文件在打字室平均停留时间;3)3个打字员均不空闲的概率. 我们可以看到这是M/M/c/∞模型,运用排队论的数学计算有: c=3,λ=15,μ=6,ρ1 = λ μ =2.5,ρ= λ cμ = 56 p0 = ∑ c-1 k=0 ρ k 1 k!+ ρ c 1 c!× 1 1-( )ρ -1 = 1+2.5+12×2.5×2.5+ 1 6×2.5 3× 1 1- 烄 烆 烌 烎 5 6 -1 =0.044 9 p1 =ρ1p0 =2.5×0.044 9=0.112 3 p2 = 1 2×ρ 2 1p0 =0.5×2.5×2,5×0.044 9=0.140 3 L= ρ c+1 1 p0 (n-1)!(n-ρ1) 2+ρ1 = 154×0.044 9 64×2×(3-0.5)2 +2.5=6.01 W =Lλ = 6.01 15 =0.440 7 ,p=1-p0-p1-p2 =0.702 5.   如果用上文给出的方法进行仿真,题中顾客的到达时间和接受服务的时间都服从泊松过程,由概率知识 可知,当随机过程是强度为λ的泊松过程时,其点间间距是相互独立的随机变量,且服从参数为λ的指数分 69 太 原 师 范 学 院 学 报(自然科学版)                第11卷  布,即 f(t)= λe-λt  t0 0 t≤烅 烄 烆 0   相应的分布函数为  F(t)= 1-λe-λt  t0 0 t≤烅 烄 烆 0 因此由上述定理我们可以得到t=-1λln (1-F(t)),由于F(t)~U(0,1)分布,因此1-F(t)~U(0,1),模拟 泊松过程到达的时间间隔公式为ti=-1λlnui ,i=1,2,…,其中ui~U(0,1),将λ=15和μ=6分别代入,就 得到顾客到达时间和服务时间的随机数,根据算法,编写 Matlab程序,模拟100次,取平均值,结果如表1: 表1 模拟结果与理论值对比 系统队长 顾客逗留时间 顾客的等待概率 排队论分析结果 6.012 1  0.440 7  0.702 5 仿真100次均值 6.008 9  0.437 8  0.700 3   对比理论计算结果和仿真结果发现,两者非常接近,说明本文提出仿真方法有效可行,我们可以通过增 加模拟次数来提高模拟精度. 实例2 某高校工商银行设有三个服务台,营业时间为早上8时到下午16时,新来的顾客到达后,若已 有顾客正在接受服务,则需要排队等待.假设顾客流为负指数分布,且顾客到来的平均时间间隔为2.5min, 窗口的服务时间服从U(2,4)分布,求系统队长,顾客的逗留时间和顾客的等待概率.由题可知,为M/G/c/ ∞模型,其中G~U(2,4),该模型不具有马尔可夫性,用数学推导的方式比较困难的,这时可以用计算机进 行模拟,首先产生窗口服务时间U(a,b)的随机数,其密度函数如下: f(t)= 1 b-a ,a≤t≤b 0 其他 烅 烄 烆 .   相应的分布函数为:F(t)= 0 t<a t-a b-a a≤tb 1 t≥ 烅 烄 烆 b 由逆变换法,有ti=a+(b-a)ui,i=1,2,…,ui~U(0,1).此题中,a=2,b=4,由U(0,1)抽得u,则t=2+2u 是来自u(2,4)的一个随机数,有了窗口服务时间的随机数,我们就可以根据前面介绍的算法编写 Matlab程 序,模拟100次,结果如表2. 表2 模拟结果 系统队长 顾客逗留时间 顾客的等待概率 仿真100次均值 1.275 6  3.156 5  0.138 8 4 结 语 本文用蒙特卡罗的思想,涉及了排队模型的仿真算法,并验证了该算法的有效性,蒙特卡洛模拟法在求 解排队系统参数中,有一定的优越性和实用性,并且在其他排队系统的模拟中均有指导意义,由于随机服务 系统本身的概率规律性,要用解析的方法来处理一个复杂的随机服务系统有时候比较困难,而模拟自身的特 点成为解决这一问题很好的方法.本文介绍的仿真方法具有一定的普遍性,可以运用于商场,银行和医院等 系统,如可以针对不同时段的顾客流量和服务水平的变化进行仿真,得到不同状况下商场应该设置多少个收 款台,多少个服务员,才能适合变化的顾客流,提高顾客流服务量,实现自身系统的优化,对于指导生产生活 有比较重要的现实意义. 参考文献: [1] 张建航,李宗成,宋晓峰.单服务员排队模型及其蒙特卡洛模拟[J].现代电子技术,2006,29(24):44-46 [2] 李 鹏,王珊珊.用 Matlab实现排队过程的仿真[J].电脑编程技巧与维护,2009,15:15-17 79 第1期             王培勋等:多服务台等待制排队模型M/G/c/∞的蒙特卡洛模拟 [3] 吴可嘉.蒙特卡洛法在解决食堂窗口排队问题上的应用[J].大连海事大学学报,2007(33):149-152 [4] 茆诗松,王静龙.高等数理统计[M].北京:高等教育出版社,2006:401-404 [5] 颜薇娜.基于蒙特卡洛模拟的商业银行排队问题研究[J].技术经济与管理研究,2009(1):20-22 [6] 高静涛.基于 Matlab的排队问题仿真[J].武汉工业学院学报,2007,26(2):89-91 Monte Carlo Simulation of M/G/c/∞ Multi Servers Queuing Model Wang Peixun Wang Zhifang (School of Statistics,Xi’an University of Finance and Economics,Xi’an 710100,China)   〔Abstract〕 Based on queuing theory for the theoretical basis,Monte Carlo simulation in Matlab to simulation on the queuing model of multi severs is used,and after analying the model same indicators are got such as mean sojourn time of a served customer,average queue length.The validity of this simulation algorithm is demonstrated and a new method to deal with problems of this category is provided. 〔Key words〕 queuing model of multi servers;Monte Carlo simulation;queuing theory;dy- namic simulation 【责任编辑:王映苗 檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪 】 (上接第52页) The Existence of Global Attractor for a Kind of Sine-Gordon Equations Luo Huxiao Wu Gaofen (Department of Mathematics,Taiyuan University of Technology,Taiyuan 030024,China)   〔Abstract〕 The existence of global attractor for a kind of Sine-Gordon equations under the certain initial-boundary value condition are proved by means of the compact embody method in the Sobolev space. 〔Key words〕 Sobolev space;compact embody;sine-Gordon;global attractor 【责任编辑:王映苗】 89 太 原 师 范 学 院 学 报(自然科学版)                第11卷 
/
本文档为【多服务台等待制排队模型M_G_c_的蒙特卡洛模拟】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索