第11章-排队论-管理运筹学-课件.pptx
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《第11章-排队论-管理运筹学-课件.pptx》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 11 排队 管理 运筹学 课件
- 资源描述:
-
1、重 庆 三 峡 学 院重 庆 三 峡 学 院管理运筹学管理运筹学课件课件本章主要内容基本概念基本概念1生死过程生死过程2单服务台排队系统模型单服务台排队系统模型3多服务台排队系统模型多服务台排队系统模型4其他排队系统模型其他排队系统模型5排队系统的优化排队系统的优化6本章小结本章小结教学目标1理解下列基本概念:排队系统构成、特征、分类、主要性能指标及相互关系2掌握以下三种排队系统主要性能指标的计算:M/M/s/;M/M/s/N/;M/M/s/m。3了解M/G/1、M/D/1的主要指标计算公式 知识结构教学目标与要求导入案例:主任医师招聘问题某三甲医院肝胆内科有主任医师1名,由于他的存在而使前来
2、诊疗的患者大增。根据一个月的统计,平均每h到达医院的患者6名,并对各时间段统计,经拟合优度检验符合泊松分布;该医生每h可诊疗4名,但患者病情不同,分布也不是均匀的,对每位患者就诊时间的统计,经拟合优度检验,符合指数分布。医院配备有电子回馈信息系统,及时观察到已挂号排队等候的患者数量。当排队等候人数少于5人时,挂号系统可以挂号。当前来就诊的患者挂上号若医生空闲则可直接就诊,否则排队等候。医生采取先到先服务的规则。若前来就诊的患者挂不上号,则立即到邻近的一家医院就诊。经统计,经该主任医师诊疗的患者,其诊疗费、检验费、医药费等医院可获纯收入100元;主任医师可高薪聘请,其薪金及住房和各种福利年均25
3、万元,医院实行每周5天工作制,年工作日250天,平均每天支付1000元的成本。当医生过少,由于患者得不到服务离去而产生的损失增加;当医生过多,由于医生空闲时间的增加也使医院的成本增加。问:医院应招聘多少名肝胆内科主任医师可使得盈利最大?此类排队现象在日常生活中经常遇到,如客户到银行排队办理存贷款业务,出纳员为客户提供服务;汽车到加油站排队,加注系统为汽车提供加油服务;超市顾客到收银台前排队,收款员为顾客提供交款服务;旅客到公交车站排队,公交车为旅客提供位移服务。排队论的基本思想是1910年丹麦电话工程师A.K.埃尔朗在解决自动电话设计问题时开始形成的,当时称为话务理论。他在热力学统计平衡理论的
4、启发下,成功地建立了电话统计平衡模型,并由此得到一组递推状态方程,从而导出著名的埃尔朗电话损失率公式。自20世纪初以来,电话系统的设计一直在应用这个公式。20世纪30年代前苏联数学家欣钦把处于统计平衡的电话呼叫流称为最简单流;瑞典数学家巴尔姆又引入有限后效流等概念和定义;美国数学家费勒(W.Feller)关于生灭过程的研究;20世纪50年代初,英国数学家D.G.肯德尔提出嵌入马尔可夫链理论,以及对排队队型的分类方法,为排队论奠定了理论基础;20世纪70年代以来,人们开始研究排队网络和复杂排队问题的渐近解等,成为研究现代排队论的新趋势。11.1.1 排队系统的一般表示排队系统的一般表示11.1.
5、2 排队系统的三个特征排队系统的三个特征11.1.3 排队系统模型的分类排队系统模型的分类11.1.4 排队的主要性质指标排队的主要性质指标11.1.5 排队系统的输入和输出排队系统的输入和输出11.1.1 排队系统的一般表示队伍服务机构顾客源服务规则排队规则顾客到来(输入)顾客离去(输出)服务系统一个排队系统都具有以下三个特征:输入过程 在一定时间内顾客平均到来多少?按什么规律到来;排队规则 进入系统的顾客按什么规则排队;服务机构 设置多少服务设施?排列形式?服务时间服从什么分布?11.1.2 排队系统的三个特征输入是指顾客到达服务系统的情况。可能有下列情况,但并不相互排斥:(1)按顾客源总
6、数划分为有限和无限两大类。如工厂需要检修的机器是有限的,准备进京观光旅游的游客是无限的。(2)按顾客到达的人数可以划分为单个到达和成批到达。如到超市购买商品的顾客是单个的,到港国际航班等待安检的旅客是成批的。(3)按顾客到达时间间隔是否固定可以划分为确定型和随机型。如定期运行的班车、班轮、班机是确定的,到加油站加油的汽车是随机的。对随机的顾客到达需要知道单位时间到达的顾客数或时间间隔的概率分布。(4)按接受过服务的顾客对顾客到达数是否有影响,划分为相互独立到达和非相互独立到达。如提供优质服务的餐饮业所产生了大量“回头客”,就属于非相互独立到达。我们只讨论独立到达情况。(5)按顾客相继到达间隔时
7、间的分布及其数字特征是否与时间有关可分为平稳与非平稳的。相继到达的间隔时间分布及其数学期望、方差等数字特征都与时间无关,称为平稳的,否则是非平稳的。一般非平稳情况的数学处理很困难,我们只讨论平稳状况。1输入过程排队规则指到达排队系统的顾客按怎样的规则排队等待。(1)按顾客到达排队系统时发现服务设施已被占用是否离去可分为损失制,等待制和混合制三种。当顾客到达时,所有的服务台均被占用,顾客随即离去,称为损失制(或称即时制、消失制);当顾客到达时,所有的服务台均被占用,顾客就排队等待,直到接受完服务才离去,称为等待制,例如出故障的机器排队等待维修就是这种情况;介于损失制和等待制之间的是混合制。对于等
8、待制,有下列服务规则:先到先服务(FCFS)、先到后服务(LCFS)、带优先服务权(PR)、随机服务(SIRO)等。在后面研究的问题中均假设采取FCFS服务规则。(2)按队列长度是否有限,可分为队长有限和队长无限两种情况。在限度以内就排队等待,超过一定限度就离去。(3)按排队方式分为单列、多列。对于多列排队的顾客有的可以相互转移,有的则不能(用栏杆等隔开);有的排队顾客因等候时间过长而离开,有的则不能(如在高速公路行驶的汽车必须坚持到高速出口)。我们所讨论的问题限制在队列间不能相互转移,中途不能退出的情形。2排队规则从机构形式和工作情况来看有以下几种:(1)服务机构可以没有服务员,也可以有一个
9、或多个服务员(服务台、窗口)。如超市的货架可以没有服务员,但交款时可能有多个服务员。(2)多个服务台的情况中,可以是平行排列的(并联),也可以是前后排列的(串联),也可以是混合的。(3)服务方式可以对单个顾客进行,也可成批进行。我们只讨论单个服务情况。(4)服务时间可分为确定型的和随机型的。如旅客列车对乘客的服务是按列车时刻表进行位移服务的,是确定型的;因患者病情不同,医生诊断的时间不是确定的,是随机型的。(5)服务时间的分布总假定是平稳的,即分布的期望值、方差等参数不受时间的影响。3服务机构SS1S2S3S1S2S3S1S2S1S2S3S4S5(a)单台单队(b)多队多台并联(c)单队多台并
10、联(d)单队多台串联(e)多台混合11.1.3 排队系统模型的分类输入/输出/并联的服务站数肯德尔(Kendall)于1953年提出了排队服务系统的分类记号 输入/输出/并联的服务站数/系统容量(队长)/系统状态(顾客源数)/服务规则1971年国际排队符号标准会上肯德尔将上述分类记号扩充到六项,记为符号含义输入(顾客到达分布)MDGI泊松(Poisson)输入定长输入(确定型输入Deterministic)一般相互独立(General independent)的时间间隔分布输出(服务时间分布)MEkG指数分布(negative exponential)k阶埃尔朗分布(Erlang distri
11、bution)一般(General)服务时间分布服务规则FCFSLCFSPRSIRO先到先服务后到先服务带优先服务权随机服务如如:M/M/1/FCFS(1)队长(Ls)和排队长(Lq)11.1.4 排队系统的主要性能指标 1.常用指标常用指标求解排队问题的目的,是研究排队系统运行的效率,估计服务质量,确定系统参数的最优值,以决定系统结构是否合理、研究设计改进措施等。因此必须确定用以判断系统运行优劣的基本数量指标。常用的指标包括:队长和排队长、逗留时间和等待时间、服务机构强度。系统中的顾客数(队长Ls)排队等候服务的顾客数(排队长Lq)正在接受服务的顾客数 逗留时间指顾客在排队服务系统中从进入到
12、服务完毕离去的平均逗留时间;等待时间指顾客排队等待服务的平均等待时间。这对顾客来讲是最关心的,每个顾客希望逗留时间或等待时间越短越好。(2)逗留时间(Ws)和等待时间(Wq)指服务机构累计的工作时间占全部时间的比例,是衡量服务机构利用效率的指标。即:(3)服务机构工作强度11.1.4 排队系统的主要性能指标 1 服务机构用于服务顾客的时间服务设施总的空闲时间工作强度服务设施总的服务时间服务设施总的服务时间11.1.4 排队系统的主要性能指标 2指标间的关系指标间的关系 设:表示单位时间内顾客的平均到达数,则1/表示相邻两个顾客到达的平均间隔时间;表示单位时间内被服务完毕离去的平均顾客数,则1/
13、表示对每个顾客的平均服务时间;s表示服务系统中并联的服务台数;Pn(t)在时刻t系统中恰好有n个顾客的概率。则有下列关系:,ssssLLWW或,()qqqqLLWWLittle或公式1,sqsqWWLL01,()snqnnn sLnP Lns P 11.1.5 排队系统的输入和输出排队系统的输入和输出是指顾客到达流和服务时间流,它们的分布一般都是非负的随机变量。最常见的是泊松分布、指数分布和埃尔朗分布、经验分布。然而在研究具体问题时,究竟是服从哪种分布?通常抽取到达时间间隔和服务时间样本,统计其频数,并进行拟合优度检验,以确定服从哪种理论分布。1.最简单流(泊松分布)所谓最简单流,是指在t这段
14、时间内有k个顾客来到服务系统的概率服从泊松(Poisson)分布,故也称为泊松流。即:当k=0时有:均值和方差为:()()(0,1,2,.)!ktktP tekk0()tP te()()E TVar Tt(1)平稳性 指在一定时间间隔内,来到服务系统有k个顾客的概率仅与这段时间间隔的长短有关,而与这段时间的起始时刻无关;(2)无后效性 指在不相交的时间区间内到达的顾客数是相互独立的,或者说在区间a,a+t来到k个顾客的概率与时间a之前来到多少个顾客无关;(3)普通性 指在足够小的时间区间内只能有一个顾客到达,不可能有两个以上顾客同时到达。最简单流需要满足三个条件最简单流需要满足三个条件 证 由
15、于考虑单位时间,取t=1,其数学期望为:(1)参数代表单位时间内到达顾客的平均数 证 在时间t 没有顾客到达的概率为 P0(t)=e-t,将右端展开为麦克劳林级数有:当t0 时,从第3项开始为t 的高阶无穷小,故结论得证。(2)在t,t+t 没有顾客到达的概率为1-t+o(t)证 在 t,t+t内恰好有1个顾客到达的概率为 P1(t)=e-tt,将e-t的麦克劳林级数代入,结论得证。(3)在t,t+t 内恰好有1个顾客到达的概率为 t+o(t)最简单流的一些性质1001(1)!(1)!kkkkkkkPkeekk23()0()()(0)1().:()2!3!ntnnttfetf xxn 麦克劳林
16、级数2指数分布的服务时间 如果随机变量T的概率密度为则称T服从指数分布,其分布函数是:数学期望和方差为:0246810121416180.000.100.200.30指数分布指数分布f(t)=Exp(-t)f(t)=Exp(-t)=10=15=202()1/()1/E TVar T()()10tF tP Ttet()0tf tet指数分布的性质()()|P Tts TsP TtsP Tts TsP TsP Ts ()11 111(1)t stsP TtseeP TtP Tse(1)不管对某一个顾客的服务已进行了多久,剩下来的服务时间的概)不管对某一个顾客的服务已进行了多久,剩下来的服务时间的概
17、率分布仍为同原先一样的指数分布(称为无记忆性或马尔柯夫性)率分布仍为同原先一样的指数分布(称为无记忆性或马尔柯夫性)。证 设刚刚服务完一个顾客所用的时间为s,对t0,有:PTt+s|Ts,根据条件概率公式有:于是结论得证。证。(2)当输入为泊松流时,顾客相继到达时间间隔必是指数分布。)当输入为泊松流时,顾客相继到达时间间隔必是指数分布。证 对于泊松流,在0,t)内至少一个顾客到达的概率=1没有顾客到达的概率.即:1P0(t)=1e-t,结论得证。因此,相继到达的间隔时间是独立的且为相同的指数分布,与输入过程为泊松流是等价的。所以(Kendall)记号中都用M表示。(3)当服务设施对顾客的服)当
18、服务设施对顾客的服务务时间时间t为参数为参数的指数分布时,与泊松流类的指数分布时,与泊松流类似也有:似也有:在在t,t+t内没有顾客离去的概率为内没有顾客离去的概率为1-t+o(t);在在t,t+t内恰有一个顾客离去的概率是内恰有一个顾客离去的概率是t+o(t);当如果当如果t足够小,在足够小,在t,t+t内有多于两个以上顾客离去的概率为内有多于两个以上顾客离去的概率为o(t)。(4)数学期望)数学期望 表示表示对每个顾客的平均服务时间对每个顾客的平均服务时间,1/为为平均服务率,平均服务率,即单位时间完成服务的顾客数。即单位时间完成服务的顾客数。(5)若干独立的指数分布的最小值是指数分布。)
19、若干独立的指数分布的最小值是指数分布。证 设T1,T2,Tn分别表示参数为1,2,n的独立的随机变量,U是这些随机变量的最小值,即U=minT1,T2,Tn,对任意t0,有 P(Ut)=PT1t,T2t,Tnt=P(T1t)P(T2t),P(Tnt)=e-1te-2te-nt=e-it即U是参数为=it的指数分布。这一性质说明:第一,如果来到服务机构的有n类不同类型的顾客,第i类顾客来到服务站的间隔时间具有参数i的指数分布,则作为总体来讲,到达服务机构的顾客的间隔时间仍为指数分布;第二,如果一个服务机构中有s个服务设施,各服务设施对顾客的服务时间为具有相同参数的指数分布,于是整个服务机构的输出
20、就是一个具有参数s的指数分布。这样对具有多个并联服务站的服务机构就可以同具有单个服务站的服务机构一样处理。3K阶埃尔朗(ERLANG)分布k个相互独立具有相同参数的指数分布的和的分布称为k阶Erlang分布。k阶Erlang分布的概率密度为:数学期望和方差为:1()()0(1)!kk tk k tf tetk211()()E TVar TkErlang分布族提供了更为广泛的模型类,比指数分布有更大的适应性。当k=1时,Erlang分布即为指数分布;当k增大时,Erlang分布的图形逐渐变为对称;当k30时Erlang分布近似于正态分布;当k时,Erlang分布化为确定型分布。4经验分布所谓的经
21、验分布,就是根据样本确定的分布。设(X1,X2,Xn)是来自总体X的简单随机样本,以vn(x)表示事件Xx在n次简单随机抽样(独立重复观测)中出现的次数,即样本的n个观测值X1,X2,Xn中不大于x的观测值的个数,则称为总体X的经验分布函数对于给定的x,经验分布函数是随机变量;对于给定的样本值,经验分布函数具有随机变量的分布函数的一切性质。()()nnxFxn 求出频率和组中组,得经验分布求出频率和组中组,得经验分布由由frequencyfrequency函数或直方图工具或数函数或直方图工具或数据透视表统计频数据透视表统计频数计算组距计算组距d=R/n,d=R/n,确定组上限确定组上限确定组数
22、确定组数n n。若无实际要求,可由斯。若无实际要求,可由斯特奇斯公式特奇斯公式n=1+3.322lgNn=1+3.322lgN确定确定求最小值、最大值、计算全距求最小值、最大值、计算全距R R经验分布律确定步骤:经验分布律确定步骤:例:产生10列30行平均数为20,标准差为3的正态分布随机数视为观察数据,利用上述方法求得经验分布。11.2 生死过程nn+1n-1生死过程(生灭过程)是用来处理输入为最简单流,服务时间为指数分布这样一类最简单排队模型的方法。它是分析后面各类排队问题的方法论,在排队论中有重要意义,什么是生死过程呢?举一个例子:某地区当前人口数为n,该年人口出生数n,则根据泊松流的性
23、质,在t 时间内出生一个人的概率为nt+o(t);n为该年人口死亡数,则根据指数分布的性质,在t时间内死亡一个人的概率为nt+o(t),那么在经过 t时间后,人口将变成多少?当前人口nt后人口t后生0死0nt后生1死0n+1t后生1死1nt后生0死1n-1t后死1生1n设系统处于状态i的概率为Pi当i=0时,输入区仅仅来自状态1,状态0的输入率为1P1;输出也只有一个,输出率为0P0,状态0的平衡方程为:当i=1时,输入和输出各有两个,分别是状态0和状态2;状态1的平衡方程为:生死过程的平衡方程01 100101PPPP00221 11 1PPPP221 11 100PPPP11 11 101
24、1 10PPPP101210221PPP 110021nnnPP 同理依次推得11021nnnC 0(1,2,.)nnPC Pn0001nnnnPPC根据概率的性质001/nnPC令11.3.1 M/M/1/FCFS(标准系统)标准系统)11.3.2 M/M/1/N/FCFS(系统容量有限)系统容量有限)11.3.3 M/M/1/m/FCFS(顾客源有限)顾客源有限)11.3.1 标准的M/M/1/系统1M/M/1/模型需要满足的条件模型需要满足的条件标准的M/M/1/模型是指满足下列条件的排队系统:(1)输入过程:顾客源无限,单个到来,相互独立,到达平均数为常数,且服从泊松分布,到达过程是平
25、稳的。(2)排队规则:单队,队长不受限制,先到先服务。(3)服务机构:单服务台、平均服务率为常数,对各顾客服务时间相互独立,服从相同的指数分布,服务过程也是平稳的。2M/M/1/系统运行指标系统运行指标由于到达平均数和服务平均数均为常数,即01112.,.nn11021nnnnnC 于是有1式中称为业务密度0011nnnnC001/1nnPC 00(1)nnnnPC PP0snnLnP0(1)nnn10(1)nnn 0(1)nndd 0(1)nndd 1(1)1dd 11ssLW111()qsWW qqLW在系统中的平均顾客数(队长):在队列中等待的平均顾客数:在系统中顾客平均逗留时间:在队列
展开阅读全文