运筹学——7.约束极值问题

*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第十二章 排队论,1,一、排队系统的一般表示,例,1,各个顾客由顾客源出发，到达服务机构前排队等候 服务，服务完了后就离开。,排队结构,指队列的数目和排列方式,排队规则,和,服务规则,是说明顾客在排队系统中按怎样的规则、次序接受服务的。,顾客源,排队结构,排队规则,服务规则,服务机构,离去,顾客到来,排队系统,第一节 基本概念,2,现实生活中的排队系统,序号,到达的顾客,要求服务内容,服务机构,1,不能运转的机器,修理,修理技工,2,修理技工,领取修配零件,发放修配零件的管理员,3,病人,诊断或做手术,医生,(,或包括手术台,),4,电话呼唤,通话,交换台,5,文件搞,打字,打字员,6,提货单,提取存货,仓库管理员,7,驶入港口的货船,装,(,卸,),货,装,(,卸,),货码头,(,泊位,),8,上游河水进入水库,放水，调整水位,水闸管理员,3,二、排队系统的组成和特征,输入即指顾客到达排队系统，可能有以下不同情况。,1,、输入过程,（,1,）,顾客源的组成,有限的,无限的,（,2,）顾客到来的方式,一个一个的,成批的,（,3,）顾客相继到达的间隔时间,确定型的,随机型的,（,4,）顾客的到来,相互独立的,关联的,（,5,）输入过程,平稳的，或称对时间是齐次的,非平稳的,4,2,、排队规则,顾客在排队系统中按怎样的规则、次序接受服务的。,（,1,）顾客到达时，所有服务台被占用,随即离去的 称为,即时制（损失制）,排队等候称为,等待制,先到先服务,后到先服务,随机服务,有优先权,（,2,）从队列占用空间,有限的,无限的,（,3,）从队列的数量,单列,多列,5,3,、服务机构,（,1,）服务员数量,没有,一个或多个,（,2,）多服务台时,1,单队,单服务台,多队,多服务台（并列）,单队,多服务台（并列）,1,2,c,1,2,c,6,（,3,）服务方式,对单个顾客进行,对成批顾客进行,（,4,）服务时间,确定型,随机型,（,5,）服务时间的分布我们总假定是平稳的，即 分布的期望值、方差等参数都不受时间的影响,多服务台（串列）,1,2,3,1,2,多服务台混合,1,2,c,7,三、排队模型的分类,1,、,1953,年，,D.G.Kendall,提出第一种分类方法,X/Y/Z,X,处填写表示相继到达间隔时间的分布,;,Y,处填写表示服务时间的分布,;,Z,处填写并列的服务台的数目,.,表示相继到达间隔时间和服务时间的各种分布的符号,:,M,负指数分布,D,确定型,E,k,k,阶爱尔朗分布,GI,一般相互独立的时间间隔的分布,G,一般服务时间的分布,8,2,、,1971,年关于排队论符号的标准化会议上决定，将,Kendall,符号扩展成为：,X/Y/Z/A/B/C,前三项意义不变，而,A,处填写系统容量限制,N,；,B,处填写顾客源数,m,；,C,处填写服务规则。,约定：,9,四、排队系统的参数,1,、队长,(Ls),：,指在系统中的顾客数。,2,、排队长,(,L,q,),：,指系统中排队等候服务的顾客数。,3,、逗留时间,(W,s,),：,指一个顾客在系统中的停留时间。,4,、等待时间,(,W,q,),：,指一个顾客在系统中排队等待的时间。,L,s,=,L,q,+,正被服务的顾客数,W,s,=,W,q,+,服务时间,5,、忙期：,指从顾客到达空闲服务机构起到服务机构再次空闲止 这段时间长度，即服务机构连续繁忙的时间长度。,6,、系统的状态概率,P,n,( t ),：,指系统中的顾客数为,n,的概率。,7,、稳定状态：,limP,n,(t),P,n,10,一、经验分布,例,2,某服务机构单服务台，先到先服务，对,41,顾客记录到达时刻,和服务时间,s,（,单位：分钟）如下表，表中第,1,号顾客到达时刻为,0,。全部服务时间为,127,（分钟）。,(1),i,(2),i,(3),s,i,(4),t,i,(5),w,i,(1),i,(2),i,(3),s,i,(4),t,i,(5),w,i,(1),i,(2),i,(3),s,i,(4),t,i,(5),w,i,1,0,5,2,0,5,12,2,7,10,9,36,1,2,0,2,2,7,4,3,6,19,4,3,5,10,38,2,7,0,3,6,1,5,6,7,22,3,4,6,11,45,5,2,0,4,11,9,1,2,8,26,3,10,5,12,47,4,2,3,第二节 时间分布,11,(1),i,(2),i,(3),s,i,(4),t,i,(5),w,i,(1),i,(2),i,(3),s,i,(4),t,i,(5),w,i,(1),i,(2),i,(3),s,i,(4),t,i,(5),w,i,13,49,1,3,5,23,86,6,2,2,33,117,4,4,7,14,52,2,9,3,24,88,5,4,6,34,121,2,6,7,15,61,1,1,0,25,92,1,3,7,35,127,1,2,3,16,62,2,3,0,26,95,3,6,5,36,129,6,1,2,17,65,1,5,0,27,101,2,4,2,37,130,3,3,7,18,70,3,2,0,28,105,2,1,0,38,133,5,2,7,19,72,4,8,1,29,106,1,3,1,39,135,2,4,10,20,80,3,1,0,30,109,2,5,0,40,139,4,3,8,21,81,2,2,2,31,114,1,2,0,41,142,1,9,22,83,3,3,2,32,116,8,1,0,12,到达间隔分布表,服务时间分布表,平均间隔时间：,=142/40=3.55(,分钟,/,人,),平均到达率：,41/142=0.28(,人,/,分钟,),平均服务率：,41/127=0.32(,人,/,分钟,),平均服务时间：,127/41=3.12(,分钟,/,人,),到达间隔,(,分钟,),次数,1,2,3,4,5,6,7,8,9,10,以上,6,10,8,6,3,2,2,1,1,1,合计,40,服务时间,(,分钟,),次数,1,2,3,4,5,6,7,8,9,以上,10,10,7,5,4,2,1,1,1,合计,41,13,二、,Passion,分布,设,N(,t,),表示在时间,0, t),内到达顾客数；,令,P,n,(,t,1,t,2,),表示在时间区间,t,1,t,2,),（,t,2,t,1,）,内有,n,（,0,）,个顾客到达的概率，即,P,n,(,t,1,t,2,)=P N(,t,2,) N(,t,1,)=,n,（,t,2,t,1,，,n,0,）,Passion,分布的三条件：,(1),无后效性：不相重叠的时间区间内顾客到达数相互独立,14,P,n,(,t,+,t,)=,P,n,(,t,) ( 1-,t,+o(,t,),+ P,n,-1,(,t,),t,+,o(,t,),情况,0,t,),t,t,+,t,),0,t,+,t,),个数,概率,个数,概率,个数,概率,(,A),(B),(C),n,n,-1,n,-2,n-,3,0,P,n,(,t,),P,n,-1,(,t,),P,n,-2,(,t,),P,n,-3,(,t,),P,0,(,t,),0,1,2,3,n,1-,t,+o(,t,),t,o(,t,),n,n,n,n,n,P,n,(,t,) ( 1-,t,+o(,t,),P,n,-1,(,t,),t,o(,t,),在上述条件下，研究顾客到达数,n,的概率分布,15,P,n,(,t,+,t,)= P,n,(,t,)(1-,t,)+P,n,-1,(,t,),t,+,o(,t,),P,n,(,t,+,t,)-P,n,(,t,)/,t,=-,P,n,(,t,)+,P,n,-1,(,t,)+o(,t,)/,t,令,t,0,d,P,n,(,t,)/d,t,= -,P,n,(,t,) +,P,n,-1,(,t,),P,n,(0)=0,（,n,1,）,d P,0,(,t,)/d,t,= -,P,0,(,t,),P,0,(0)=1,（,n,=0,）,P,0,(,t,)=,e,-,t,P,n,(,t,)=(,t,),n,e,-,t,/,n,t,0,n,=0,，,1,，,2,16,三、负指数分布,f,T,（,t,）,=,e,-,t,，,t,0,0,，,t0,17,一、,M/M/1,模型,1,、假设,（,1,）顾客到达的间隔时间满足参数为,的负指数分布,（,2,）服务时间满足参数为,的负指数分布（,）,（,3,）服务机构是单服务台,（,4,）顾客源是无限的，顾客相互独立,（,5,）单队排列，且对队长没有限制,第三节 单服务台负指数分布排队系统的分析,18,2,、,P,n,的计算,O,表示发生（,1,个） ，,表示没有发生,P,n,(,t,+,t,)= P,n,(,t,)(1-,t,)(1-,t,),+ P,n,+1,(,t,)(1-,t,),t,+ P,n,-1,(,t,),t,(1-,t,),+,P,n,(,t,),t,t,情况,在时刻,t,顾客数,在区间（,t,t,+,t,）,在时刻,t,+,t,顾客数,到达,离去,(,A),(B),(C),(D),n,n,+1,n,-1,n,O,O,O,O,n,n,n,n,19,整理得：,P,n,(,t,+,t,)=P,n,(,t,)(1-,t,-,t,)+P,n,+1,(,t,),t,+P,n,-1,(,t,),t,+o(,t,),P,n,(,t,+,t,)-P,n,(,t,)/,t,=,P,n,-1,(,t,)+,P,n,+1,(,t,)-(,+,),P,n,(,t,) (1),t,0,dP,n,(,t,)/d,t,=,P,n,-1,(,t,)+,P,n,+1,(,t,)(,+,),P,n,(,t,),考虑,P,0,(,t,),的情况：,P,0,(,t,+,t,)=P,0,(,t,)(1-,t,)+P,1,(,t,)(1-,t,),t,t,0, dP,0,(,t,)/d,t,=-,P,0,(,t,)+,P,1,(,t,),(2),由,dP,n,(,t,)/d,t,=0,得到,-,P,0,+,P,1,=0 (3),P,n,-1,+,P,n,+1,-(,+,),P,n,=0 (4),20,由式(3)得,通过求解可得,单位时间内到达的平均顾客数,单位时间内服务的平均顾客数,服务强度,参数意义：,21,3,、,M/M/1,参数计算,（,1,）系统中平均顾客数（,L,s,）,记,22,（,2,）队列中等待的平均顾客数（,L,q,）,（,3,）顾客逗留时间（,W,s,）,（,4,）队列中顾客等待时间（,W,q,）,23,它们的相互关系如下：,24,例3,100个工作小时内每小时来就诊的病人数,n,出现次数如下,100个完成手术的病例所用时间,v,(,小时)出现的次数如下,到达的病人数,n,出现次数,t,n,0,1,2,3,4,5,6,10,28,29,16,10,6,1,合计,100,为病人完成手术时间,v,(,小时),出现次数,t,v,0.0-0.2,0.2-0.4,0.4-0.6,0.6-0.8,0.8-1.0,1.0-1.2,1.2,以上,38,25,17,9,6,5,0,合计,100,25,解：,26,假定系统最大容量为,N,，单服务台情形排队等待的顾客最多为,N-1,，,下面只考虑稳态情形：,二、,M/M/1/N/,模型,解得：,27,根据上式我们可以推导出系统的各项指标：,有效到达率,e,=,(1-P,N,),可以验证：1-,P,0,=,e,/,(4) 顾客等待时间,(3) 顾客逗留时间,(1) 队长,(2) 队列长,28,例,4,单人理发馆有六个椅子接待客人。当,6,个椅子都坐满时，后来的顾客不进店就离开。顾客平均到达率为,3,人,/,小时，理发需时平均,15,分钟。则：,N=7,为系统中最大的顾客数，,=3,人,/,小时，,=4,人,/,小时,（,1,）求某顾客一到达就能理发的概率。,（,2,）求需要等待的顾客数的期望值。,29,（,3,）求有效到达率。,（,4,）求一顾客在理发馆内逗留的时间。,（,5,）在可能到达的顾客中有百分之几不等待就离开。,（人,/,小时）,30,机器故障问题：,设共有,m,台机器，机器故障停机表示到达，待修机器形成队列，修理工是服务员。,顾客总体虽然只有,m,个，但每个顾客服务后仍回到总体，仍然可以到来。,三、顾客源为有限的情形（,M/M/1/m,）,31,根据上式我们可以推导出系统的各项指标：,在机器故障问题中,L,s,就是平均故障台数，而,32,例,5,某车间有,5,台机器，每台机器的连续运转时间服从负指数分布，平均连续运转时间,15,分钟，有一个修理工，每次修理时间服从负指数分布，平均每次,12,分钟。,求 （,1,）修理工空闲的概率；,（,2,）五台机器都出故障的概率；,（,3,）出故障的平均台数；,（,4,）等待修理的台数；,（,5,）平均停工时间；,（,6,）平均等待时间；,（,7,）评价这些结果。,33,解：,（,7,） 机器停工时间过长，修理工几乎没有空闲时间，应当提高服务率减少修理时间或增加修理工人。,34,一、,M/M/c,第四节 多服务台指数分布排队系统的分析,规定各服务台工作相互独立且平均分配服务率相同，即,1,=,2,=,c,=,整个服务机构的平均服务率为,c,(,n,c,),n,(,n,c,),35,用递推法解上述差分方程，可求得状态概率。,根据上式我们可以推导出系统的各项指标：,36,例,6,某售票所有三个窗口，顾客到达服从,Passion,过程，平均到达率每分钟,=0,.9(,人,),服务,(,售票,),时间服从负指数分布,平均服务率每分钟,=0.4(,人,).,=0.9,窗口,(1),=0.4,窗口,(2),=0.4,窗口,(3),=0.4,37,代入公式得,(1),整个售票所空闲的概率,（,2,）平均队长,（,3,）平均等待时间和逗留时间,（,4,）顾客到达后必须等待（即系统中顾客数已有,3,人）的概率,38,M/M/c,型系统和,c,个,M/M/1,系统的比较,上例中，排队方式不变，但顾客到达后在每个窗口前各排一队，且进入队列后坚持不换，这就形成,3,个队列，如下图二每个队列平均到达率为,=0,.9/3=0.3,（,每分钟），这样原来的系统就变成,3,个,M/M/1,型的子系统。,窗口,(1),=0.4,窗口,(2),=0.4,窗口,(3),=0.4,=0.9,=0.3,=0.3,=0.3,39,现按,M/M/1,型解决这个问题，并与上表比较：,从表中各指标的对比可以看出单队比三队有显著的优越性,模型,指标,(1),M/M/3,型,(2),M/M/1,型,服务台空闲的概率,顾客必须等待的概率,平均队列,平均队长,平均逗留时间,平均等待时间,0.0748,P(,n,3,)=0.57,1.70,3.95,4.39(分钟),1.89(分钟),0.25(每个子系统),0.75,2.25(每个子系统),9.00(整个系统),10(分钟),7.5(分钟),40,系统的状态概率和运行指标如下,:,二、,M/M/c/N/,41,三、,M/M/,c/m,(2),平均故障台数：,有效到达率：,42,（,1,）等待修理的机器平均数,（,2,）需要修理的机器平均数,（,3,）有效损坏数,（,4,）等待修理时间,（,5,）停工时间,例,7,设有两个修理工人，负责,5,台机器的正常运行，每台机器平均损坏的概率为每运转一小时,1,次，两个工人能以相同的平均修复率,4,（次,/,小时）修好机器。求,:,43,(1),L,q,=P,3,+2P,4,+3P,5,=0.118,(3),e,=1(5-1.094)=3.906,(4),W,q,=0.118/3.906=0.03,小时,(5),W,s,=1.094/3.906=0.28,小时,44,服务时间是任意分布的情形,：,一、,M/G/1,服务时间,T,的分布是一般的其它的条件和标准的,M/M/1,型相同。为了达到稳态，,1,这一条件是必要的,其中,=,ET.,第五节 一般服务时间,M/G/1,模型,45,例,8,有一售票口,已知顾客按平均为,2,分,30,秒的时间间隔的负指数分布到达,.,顾客在售票口前服务时间平均为,2,分钟,.(1),若服务时间也服从负指数分布,求顾客为购票所需的平均逗留时间和等待时间,;(2),若经过调查,顾客在售票口前至少要占用,1,分钟,且认为服从服务时间服从负指数分布是不恰当的,;,而应服从以下概率密度分布,.,46,(2),令,y,为服务时间，那么,Y=1+X,X,服从均值为,1,的负指数分布。于是,47,二、,M/D/1,服务时间是确定的常数，例如在一条装配线上完成一件工作的时间应是常数。自动的汽车的冲洗台，冲洗一台汽车的时间也是常数，这时,例,9,某实验室有一台自动检验机器性能的仪器，要求检验机器的顾客按,Passion,分布到达，每小时平均,4,个顾客，检验每台机器所需时间为,6,分钟。,求,:,（,1,） 在检验室内机器台数,L,s,(,期望值,),（,2,） 等候检验的机器台数,L,q,（,3,） 每台机器在室内消耗（逗留）时间,W,s,（,4,） 每台机器平均等待检验的时间,W,q,48,注：在一般服务时间分布的,L,q,和,W,q,中以定长服务时间的为最小，这符合我们通常的理解,服务时间越有规律，等候的时间就越短,49,三、,M/E,k,/1,模型,1,2,k,服务机构,k,k,k,50,对于,M/E,k,/1,模型（除服务时间外，其它条件与标准的,M/M/1,型相同）,51,例,10,某单人裁缝店做西服，每套需经过,4,个不同的工序，,4,个工序完成后才开始另一套。每一套工序的时间服从负指数分布，期望值为,2,小时。顾客到来服从,Passion,分布，平均订货率为,5.5,套,/,周,(,设一周,6,天,每天,8,小时,).,以顾客为等到做好一套西服期望时间有多少,?,解 顾客到达,=5,.5,套,/,周,设,为平均服务率,(,单位时间完成的套数,);1/,为平均每套所需的时间,;1/4,为平均每工序,所需的时间,.,由题设,1/4,=2,小时,=1/8,套,/,小时,=6,套,/,周,=5.5/6,T,为每做完一套西服所需时间,52,53,一、问题的提出,排队系统的最优化的目的在于使设备达到最大效益。,费用,服务水平,极小,等待费用,服务费用,合并费用,提高服务水平会降低顾客的等待费用，增加了服务机构的成本，优化的目标使二者费用之和最小。,第六节 经济分析,系统的最优化,54,二、,M/M/1,模型中的,M,的优化,1,、标准,M/M/1:,2,、系统容量为,N,的情况：,55,56,