排队论(脱产).ppt课件

1、排队论 基本概念 排队模型问题分类 排队问题求解 排队系统的优化本章内容重点1例 某火车站售票处有三个窗口，同时售各车次的车票。顾客到达服从泊松分布，平均每小时到达=54人，服务时间服从负指数分布，平均服务率=24（人/h），分两种情况：1. 顾客排成一队，依次购票；2. 顾客每个窗口排一队，不准串队。 考虑: 1、售票处空闲的概率；2、顾客在系统中平均等待时间和逗留时间 3、系统中平均总顾客数和排队的顾客数。2 排队论(Queuing Theory)，又称随机服务系统理论(Random Service System Theory),是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究

2、各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。前 言3例：上、下班搭乘公共汽车； 顾客到商店购买物品； 病员到医院看病； 旅客到售票处购买车票； 食堂、饭店就餐； 打电话；前 言4 通讯卫星与地面传递信息； 生产线上的原料、半成品等待加工； 因故障停止运转的机器等待工人修理； 码头的船只等待装卸货物； 要降落的飞机因跑道不空而在空中盘旋等等； 防空系统向敌机射击。前 言5前 言一般的排队系统，都可由下图加以描述。61.基 本 概 念 一 排队系统的描述 （一）系统特征和基本排队过程 实际的排队系统有以下的共同特征： (1)有请求服务的人或物顾客； (2)有为顾客服务

3、的人或物，即服务员或服务台； (3)顾客到达系统的时刻是随机的，为每一位顾客提供服务的时间是随机的，因而整个排队系统的状态也是随机的。排队系统的这种随机性造成某个阶段顾客排队较长，而另外一些时候服务员(台)又空闲无事。7（二）排队系统的基本组成部分 通常，排队系统都有输入过程、服务规则和服务台等3个组成部分： 1输入过程一般可以从3个方面来描述个输入过程。 (1)顾客总体数，又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。例如，到售票处购票的顾客总数可以认为是无限的，而某个工厂因故障待修的机床则是有限的。1.基 本 概 念8 (2)顾客到达方式。这是描述顾客是怎样来到

4、系统的，他们是单个到达，还是成批到达。病人到医院看病是顾客单个到达的例子。在库存问题中如将生产器材进货或产品入库看作是顾客，那么这种顾客则是成批到达的。9 (3)顾客流的概率分布，或称相继顾客到达的时间间隔的分布。这是求解排队系统有关运行指标问题时，首先需要确定的指标。这也可以理解为在一定的时间间隔内到达K个顾客(K=1、2、 )的概率是多大。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。1.基 本 概 念10 2.服务规则。一般可以分为损失制、等待制和混合制等3大类。 (1)损失制。指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离

5、开系统永不再来。例如,电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为损失制。1.基 本 概 念11 (2)等待制。指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。例如，排队等待售票，故障设备等待维修等。服务台在选择顾客进行服务时，常有如下四种规则： 先到先服务。按顾客到达的先后顺序对顾客进行服务，是最普遍的情形。 后到先服务。仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。1.基 本 概 念12 随机服务。即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。 优先权服务。如老人、儿童

6、先进车站；危重病员先就诊；遇到重要数据需要处理计算机立即中断其他数据的处理等，均属于此种服务规则。1.基 本 概 念13 (3)混合制这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种： 队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。例如最多只能容纳K个顾客在系统中，当新顾客到达时，若系统中的顾客数(又称为队长)小于K，则可进入系统排队或接受服务；否则，便离开系统，并不再回来。如水库的库容是有限的，旅馆的床位是有限的。1.基 本 概 念14 等待时间有限。即顾客在系统中的等待时间

7、不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。如易损坏的电子元器件的库存问题，超过一定存储时间的元器件被自动认为失效。又如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。1.基 本 概 念15 逗留时间(等待时间与服务时间之和)有限。例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t时，若在这个时间内未被击落，也就不可能再被击落了。 不难注意到，损失制和等待制可看成是混合制的特殊情形，如记s为系统中服务台的个数，则当K=s时，混合制即成为损失制；当K=时，混合制即成为等待制。1.基 本 概 念16 3服务台情况。服务台可以从以下3方面来描述：

8、(1) 服务台数量及构成形式。从数量上说，服务台有单服务台和多服务台之分。从构成形式上看，服务台有： 单队单服务台式； 单队多服务台并联式； 多队多服务台并联式； 单队多服务台串联式； 单队多服务台并串联混合式,以及 多队多服务台并串联混合式等等。见图1至图5所示。 1.基 本 概 念17 不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图1至图5。图1 单服务台排队系统服务台数量及构成形式18图2 单队列S个服务台并联的排队系统图3 S个队列S个服务台的并联排队系统服务台数量及构成形式19图

9、4 单队多个服务台的串联排队系统图5 多队多服务台混联、网络系统服务台数量及构成形式20 (2) 服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客就属于成批服务。 (3) 服务时间的分布。一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K级爱尔朗分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。1.基 本 概 念21（三）排队系统的描述符号与分类 为了区别各种排队系统，根据输入过程、排队规则和服务机制的变化对排队模型进行描述或分类，可给出很多排队模型。为了方便对众多模型的描述，肯道尔（D

10、GKendall）提出了一种目前在排队论中被广泛采用的“Kendall记号”，完整的表达方式通常用到6个符号并取如下固定格式：A / B / C / D / E / F 各符号的意义为：1.基 本 概 念22A表示顾客相继到达间隔时间分布，常用下列符号：M表示到达过程为泊松过程或负指数分布；D表示定长输入；Ek表示k阶爱尔朗分布；G表示一般相互独立的随机分布。B表示服务时间分布，所用符号与表示顾客到达间隔时间分布相同。M表示服务过程为泊松过程或负指数分布；D表示定长分布；Ek 表示k阶爱尔朗分布；G表示一般相互独立的随机分布。1.基 本 概 念23C表示服务台(员)个数：“1”则表示单个服务台

11、，“s”。(s1)表示多个服务台。D表示系统中顾客容量限额；如系统包括接受服务和等待共有 k 个位子，则 s k 0为一常数，表示单位时间内到达顾客的平均数，又称为顾客的平均到达率。 2.输入过程和服务时间分布352.输入过程和服务时间分布 对于泊松流，不难证明其相继顾客到达时间间隔i，i=1,2,是相互独立同分布的，其分布函数为负指数分布:36 3.爱尔朗输入. 这是指相继顾客到达时间间隔相互独立，具有相同的分布，其分布密度为 其中k为非负整数。 可以证明，在参数为的泊松输人中，对任意的j与k,设第j与第j+k个顾客之间的到达间隔为 。则随机变量Tk的分布必遵从参数为的爱尔朗分布，其分布密度

12、为：2.输入过程和服务时间分布37 例某排队系统有并联的k个服务台，顾 客流为泊松流，规定第i,K+i,2K+i个顾客排入第i号台(i=1,2,K)，则第K台所获得的顾客流，即为爱尔朗输入流，其他各台，从它的第一个顾客到达以后开始所获得的流也为爱尔朗输入流。 此外，爱尔朗分布中，当K1时将化为负指数分布。2.输入过程和服务时间分布38 4.一般独立输入，即相继顾客到达时间间隔相互独立、同分布，分布函数F(t)是任意分布，因此，上面所述的所有输入都是一般独立分布的特例。 5.成批到达的输入。这时排队系统每次到达的顾客不一定是一个，而可能是一批，每批顾客的数目n是一个随机变量。其分布为： 到达时间

13、间隔可能是上述几类输入中的一种。2.输入过程和服务时间分布39 二、服务时间分布 1定长分布。每一个顾客的服务时间 都是常数，此时服务时间t的分布函数 为： 2负指数分布。即各个顾客的服务时间相互独立，具有相同的负指数分布： 其中0为一常数，服务时间t的数学期望称为平均服务时间。显然，对于负指数分布2.输入过程和服务时间分布40 3.爱尔朗分布. 即每个顾客的服务时间相互独立，具有相同的爱尔朗分布。其密度函数为 其中0为一常数，此种的平均服务时间为： K=1时爱尔朗分布化归为负指数分布当K时，得到长度为1/的定长服务。2.输入过程和服务时间分布414.一般服务分布。所有顾客的服务时间都是相互独

14、立具有相同分布的随机变量，其分布函数记B(X)，前面所述的各种服务分布都是一般服务分布的特例。5.多个服务台的服务分布。可以假定各个服务台的服务分布参数不同或分布类型不同6.服务时间依赖于队长的情况。指服务员排队的人愈多，服务的速度也就愈快。2.输入过程和服务时间分布42 三、排队论研究的基本问题 排队论研究的首要问题是排队系统主要数量指标的概率规律，即研究系统的整体性质，然后进一步研究系统的优化问题。与这两个问题相关的还包括排队系统的统计推断问题。 (1)通过研究主要数量指标在瞬时或平稳状态下的概率分布及其数字特征，了解系统运行的基本特征。 (2)统计推断问题，建立适当的排队模型是排队论研究

15、的第一步，建立模型过程中经常会碰到如下问题：检验系统是否达到平稳状态；检验顾客相继到达时间间隔的相互独立性；确定服务时间的分布及有关参数等。2.输入过程和服务时间分布43 (3)系统优化问题，又称为系统控制问题或系统运营问题，其基本目的是使系统处于最优或最合理的状态。系统优化问题包括最优设计问题和最优运营问题，其内容很多，有最少费用问题、服务率的控制问题、服务台的开关策略、顾客(或服务)根据优先权的最优排序等方面的问题。 对于一般的排队系统运行情况的分析，通常是在给定输入与服务条件下，通过求解系统状态为n(有n个顾客)的概率Pn(t)，再进行计算其主要的运行指标: 2.输入过程和服务时间分布4

16、4 系统中顾客数(队长)的期望值L或Ls； 排队等待的顾客数(排队长)的期望值Lq； 顾客在系统中全部时间(逗留时间)的期望值W或Ws； 顾客排队等待时间的期望值Wq。 排队系统中，由于顾客到达分布和服务时间分布是多种多样的，加之服务台数。顾客源有限无限，排队容量有限无限等的不同组合，就会有不胜枚举的不同排队模型，若对所有排队模型都进行分析与计算，不但十分繁杂而且也没有必要。下面拟分析几种常见排队系统模型。2.输入过程和服务时间分布45 对于泊松输入负指数分布服务的排队系统的一般决策过程： 根据已知条件绘制状态转移速度图。 依据状态转移速度图写出各稳态概率之间的关系。 求出 P0 及 Pn 。

17、3.泊松输入指数服务排队模型46 计算各项数量运行指标。 用系统运行指标构造目标 函数，对系统进行优化。 典型分布 泊松分布及其 性质，负指数分布及其性质泊松 分布 (平稳状态） 0 为单位 时间平均到达的顾客数 P I = n = n e- / n! (n = 0,1,2,)3.泊松输入指数服务排队模型47 负指数分布 为平均服务率，即 单位时间服务的顾客数。 P（服务时间 t ) = 1- e- t t 0 系统状态概率分布及状态转移速 度图 基本的概率分布推导 3.泊松输入指数服务排队模型48状态转移速度图由此图易得：转入率=转出率n=0时，0P0=1P1n一般，n-1Pn-1+n+1P

18、n+1=(n+n)Pn同样可得下列公式: n = 1,2, n-1 nPn=(n -1/n )Pn-1=( i / j )p0 i=0 j=10n123021n-1n1n32n+13、泊松输入指数服务排队模型49系统的运行指标：(稳态时）1.系统中顾客数的期望值： L=KPk k=0 2.排队等待的顾客数的期望值：Lq=(K-C) Pk kc3、泊松输入指数服务排队模型50 3.有效到达率e: 稳态情况下，单位时间内进入系统的顾客数的期望值等于单位时间内离开系统的顾客数的期望值 即： e=e 当系统中有n个顾客时，每单位时间进入系统的顾客平均数为n，每单位时间离开系统的顾客平均数为n e=nP

19、n e=nPn3、泊松输入指数服务排队模型51 4.L ,L q,e ,W ,Wq之间的关系：Little证明了：W=L/e , Wq=Lq/e 几何解释： 稳态时，一个顾客，进入系统后，每单位时间，平均到达e顾客。 eeeee进入时刻离开时刻总时间Ws 队长Ls由时间段内个e组成的Ls=eWs3、泊松输入指数服务排队模型52同理：Lq=eWq又 W=Wq+（1/）-W与Wq只相差一段平均服务时间1/ L=Lq+(e/)以上公式只是对一般问题而成立的。3、泊松输入指数服务排队模型53排队论解题要点判断排队问题：3方面；Kedall符号描述模型；参数 , (单位一致；顾客数/单位时间)；绘状态转

20、移速度图，找出 pn 与 p0 的关系；求 p0 , pn , Ls , Lq , Ws , Wq , e 等 Little 公式54M/M/1 无限源系统稳态概率方程：Pn= (/)Pn-1= (/)nP0 1n N0N-112N-2N1M/M/1/N/ 参数 ，系统状态转移速度：55 N 由Pn=1 n=0 M/M/1 无限源系统 N(/)nP0=1 , = /n=0 Pn=1/(N +1) =(1- ) n/(1- N +1） NP0=1/n= n=01/(N +1) =(1- )/(1- N +1）56 NL=nPn n=0 M/M/1 无限源系统 各计算公式：e =n Pn = (1

21、-PN )+0PN (只有 PN 不再进人，故N =0，其余均为)e =nPn=0P0+(1-P0)（同理）W =L/e , Wq=W -(1/), Lq=Wqe57 其他指标：损=-e=PN P忙=1-P0 , P闲=P0 （只有一个服务台） 平均服务台忙期的长度 T忙， 平均服务台闲期的长度 T闲， T忙/ T闲= P忙/ P闲=(1- P0)/ P0 T闲=1/(是从一个顾客到下一个顾客到达的平均间隔时间)于是 T忙=(1- P0)/ P0M/M/1 无限源系统58 2.M/M/1/: M/M/1 无限源系统 稳态概率方程： Pn=（/）Pn-1=(/)nP0 令=/0n12n-1 当

22、1时, n不收敛，故应1, n=0即59 P0=1/( n)= 1- 或 P0=1-/ n=0 M/M/1 无限源系统Pn=n(1-) 或 Pn=(/)n(1-/)60M/M/1 无限源系统进而： L = n(n - n+1) n=1 = nn - nn+1 n=1 n=1 =+ nn - nn +1 n=2 n=1 = + n +1 n=1 = +2/(1-) = /(1-) = /(-) (=/)取出第一项写成 （n+1）n+1 n=1 与后一项合并61这里: e=(1-P0)=W=L/e=1/（-）Wq=W-1/=/(-)Lq=Wq=2/(-) 3.损失制M/M/1/1: 顾客到达若服务

23、台被占用立即离开。M/M/1 无限源系统62P1=/（+）P损=P忙=P1= /（+）P闲=P0= /（+）M/M/1 无限源系统直接可得： P0= (1-) / (1-)2 = 1 / (1+) = / (+) P0+P1=1 63 1.M/M/C/NM/M/C 无限源系统0N-112N-2c2cNCC-1ccC+13(c-1)cc 稳态概率应满足的关系：当nc时， Pn=/(n) Pn-1当nc时， Pn =/(c) Pn-1 令=/（c） 系统负荷强度系数64 c/nPn-1=cn/nnP0 n的情形=/(c)1时，不收敛，设1, M/M/C 无限源系统 c-1 P0=c n /nn+c

24、 c /c(c /1-)-1 n=067 (cn / n!)nP0 nc (cc/c!)nP0 n c M/M/C 无限源系统Pn= Lq = ccc+1P0 / c! (1-)2e = Wq = Lq/ W = Wq+ 1/ L=W = Lq+/68 3.M/M/C 损失制系统（M/M/C/C/） 此即M/M/C/N中 N=C 的情形 M/M/C 无限源系统 c P0= cn / n!n-1 n=0 Pn= cn / n!nP0e=(1-Pc) Lq=0, Wq=0(不等待) W=1/ L=eW=e/=(/) (1-Pc) 损=-e=Pc69例6.1:某车站售票处有三个窗口，同时售各车次的车

25、票。顾客到达服从泊松分布，平均每分钟到达=0.9（人），服务时间服从负指数分布，平均服务率=24（人/h），分两种情况：1. 顾客排成一队，依次购票；2.顾客每个窗口排一队，不准串队。 求:（1）售票处空闲的概率。 （2）平均等待时间和逗留时间。 （3）队长和队列长。例 题 解 析70例 题 解 析稳态概率：当n3时 Pn=/（n）Pn-1=(n/n!)nP0 =3n/n!nP0 当n3时 Pn=/（c）Pn-1=(33/3!)nP0 =4.5nP0 解：1. M/M/3/031232343单位应相同：=0.4（人/分钟） 记= /（3）=0.9/(0.4*3)=0.7571例 题 解 析 P

26、0+3*0.75 P0+4.5*0.752 P0+4.5n P0 =1 n=3 由Pn=1 n=0 P0= 1/(1+2.25+2.53125+4.53/(1-) =1/13.375 =0.0748P1=0.1683 P2=0.1893 Lq=(n-c)Pn=33/3!4 P0 (n-3)n-3-1 n =c+1 n = 4 72例 题 解 析S= dF/ d=(1-)+/(1-)2于是：Lq=4.54P0/(1-)2=1.704 e=Wq=Lq/e=1.704/0.9=1.893分钟 F= S d=(n-3)n-3-1d= n-3 n=4 n=4 =/(1-) S= (n-3)n-3-1 n

27、=4 73例 题 解 析Ws=Wq+ 1/=1.893+2.5=4.393分钟Ls=Ws=3.954故：售票处的空闲的概率为0.0748有1个窗口空闲 0.18934平均等待时间 Wq=1.893分钟， 平均逗留时间 W=4.393分钟队长 Ls=3.954(人) Lq=1.704(人)74 2.M/M/1/ 三个系统并联：=0.3 =0.4 =/=0.75P0=1-=0.25 三个服务台都有空的时候，P03=0.0156Ls=/(1-)=3 e=0.3Lq=Ls-/=2.25Ws=Ls/=10Wq=Ws-1/=7.5例 题 解 析75故售票处空闲的概率为 0.0156例 题 解 析平均等待时

28、间 Wq=7.5分钟 平均逗留时间 Ws=10分钟队长 Ls=3 三个队 共3+3+3=9队列长 Lq=2.25 共6.75（人）相比之下，排一队共享三个服务台效率好。有1个窗口空闲 0.2576顾客源有限的排队系统 1.M/M/1/m/m系统 顾客源是m个，那么系统容量实质上 最多有m个足够。0m-112m-2m(m-1)2m(m-2)3顾客源中剩余的顾客数乘以每个顾客到达的概率77顾客源有限的排队系统Pn= m-(n-1)/Pn-1 1nm反复推得：Pn=m!/(m-n)!(/)nP0 1nm m 代入Pn=1 n=0 m m!/(m-n)!(/)nP0 =1 n=0 m P0= m!/(

29、m-n)!(/)n-1 n=078顾客源有限的排队系统 mPn=m!/(m-n)!(/)nm!/(m-k)!(/)k-1 k=0由(m-L)=(1-P0)得 L=m-/(1-P0)W=L/eWq=W-1/Lq=Wqee=(m-L) m me=nPn=(m-n)Pn n=0 n=0 m m =(m Pn-n Pn) n=0 n=0e= (1-P0)79 2. M/M/c/m/m系统顾客源有限的排队系统0m-112m-2m(m-1)2c2cmCC-1(m(c-1)c顾客源还有m-(c-1)个顾客每个顾客可到达的概率稳态概率方程Pn=(m-n+1)/nPn-1 nc(m-n+1)/cPn-1 cn

30、m80 m代入 Pn=1 得(整理后) n=0顾客源有限的排队系统反复代入得：Pn=m!/n!(m-n)!(/ )nP0 ncm!/c!(m-n)!cn-c(/)nP0 cnm c m P0= m!/(m-n)!(/)n+ m!/(c!(m-n)! n=0 n=c+1 cn-c)(/)n-181于是可得 ： mLq=(n-c)Pn n=c+1e=(m-L)顾客源有限的排队系统又 L=Lq+e/=Lq+/(m-L) 整理得：L=(L+/m)/(1+/)Wq=Lq/e , W=L/e82应 用 举 例 例6.2:某汽车加油站有两台加油泵为汽车加油，加油站内最多能容纳6辆汽车。已知顾客到达的时间间隔

31、服从负指数分布，平均每小时到达18辆汽车。若加油站中已有K辆车，当K2时，有K/6的顾客将自动离去。加油时间服从负指数分布，平均每辆车需要5分钟。试求：非标准的M/M/2/N模型83应 用 举 例 （1）系统空闲的概率为多少？ P0 （2）求系统满的概率是多少？ P6 （3）求系统服务台不空的概率 P2+P3+P4+P5+P6=1- P0-P1 （4）若服务一个顾客,加油站可以获 得利润10元,问平均每小时可获 得利润为多少元？ 10e （5）求每小时损失掉的顾客数？ 损=-e （6）加油站平均有多少辆车在等待加 油？ Lq 平均有多少个车位被占用？ L （7）进入加油站的顾客需要等多长的 时

32、间才能开始加油？ Wq 进入加油站的顾 客需要多长时间才能离去？ W 84稳态概率关系：P1=/P0=1.5P0 =(3/2)P0P2=/(2)P1=0.75*1.5P0 =(9/8)P0应 用 举 例 解：状态转移速度图 以小时为单位=18 =60/5=1222 2205124632(1-2/6)(1-3/6) (1-4/6) (1-5/6) 85应 用 举 例P3=(4/6)/(2)P2=(1/2)(9/8)P0= (9/16)P0 P4=(3/6)/(2)P3=(3/8)(9/16)P0= (27/128)P0P5=(2/6)/(2)P4=(1/4)(27/128)P0 = (27/51

33、2)P0P6=(1/6)/(2)P5=(1/8)(27/512)P0= (27/4096)P0由 P0+P1+P2+P3+P4+P5+P6=1解得：P0=0.22433 P1 P2 P3 P4 P5 P60.33649 0.25237 0.12618 0.04732 0.01183 0.0014886运行指标：(1) P0=0.22433(2) P6=0.00148(3) P忙=1-P0-P1=0.43918(4)e=0P0+P1+2(P2+P3+P4+P5+P6) = 14.578（辆/h） 10e= 145.78(元/小时）应 用 举 例87(5)损=-e =18-14.5782 =3.4

34、218（辆/h）应 用 举 例(6)Lq=(3-2)P3+(4-2)P4+(5-2)P5+(6-2)P6 = 0.26223 L=Lq+e/ =0.26223+1.21485 =1.4770888应 用 举 例(7)Wq=Lq/e =0.018h =1.08分钟 W=Wq+1/ =0.101h =6.08分钟89 例6.3:某车站候车室在某段时间旅客到达服从泊松流分布，平均速度为50人/h，每位旅客在候车室内停留的时间服从负指数分布，平均停留时间为0.5h，问候车室内平均人数为多少？（L)应 用 举 例解：把旅客停留在候车室看做服务，于是系统为M/M/ =50 =1/0.5=290稳态概率关系

35、：Pn=/(n)Pn-1=.=1/n!(/)nP0 记 =/=50/2 =25 应 用 举 例0n12n-1n2(n+1)n+13(n-1)(n+2)状态转移速度图: 91应 用 举 例 P0=(1/n!n)-1= e- n=0 L=nPn n=1 = e-1/(n-1)!n n=1 =e-1/n!n=25(人) n=0 代入 Pn=1 n=092 4.排队系统的优化目标 与最优化问题 完全消除排队现象是不现实的，那会造成服务人员和设施的严重浪费，但是设施的不足和低水平的服务，又将引起太多的等待，从而导致生产和社会性损失。 从经济角度考虑，排队系统的费用应该包含以下两个方面：一个是服务费用，它

36、是服务水平的递增函数；另一个是顾客等待的机会损失(费用)，它是服务水平的递减函数。两者的总和呈一条U形曲线。93 4.排队系统的优化目标 与最优化问题 系统最优化的目标是寻求U曲线的最小点。这种意义下，排队系统的最优化问题通常分为两类：一类称之系统的静态最优设计，目的在于使设备达到最大效益，或者说，在保证一定服务质量指标的前题下，要求机构最为经济；另一类叫作系统动态最优运营，是指一个给定排队系统，如何运营可使某个目标函数得到最优。归纳起来，排队系统常见的优化问题在于：94 4.排队系统的优化目标 与最优化问题 (1)确定最优服务率*； (2)确定最佳服务台数量s*； (3)选择最为合适的服务规

37、则； (4)确定上述几个量的最优组合。 本节仅就，s这两个决策变量的分别单独优化，介绍两个较简单的模型，以便读者了解排队系统优化设计的基本思想。95 4.排队系统的优化目标 与最优化问题一、MM1 系统的最优平均服务率* : 设C1当 =1时服务系统单位时间的平均费用Cw平均每个顾客在系统逗留单位时间的损失；y整个系统单位时间的平均总费用。其中C1，Cw均为可知。则目标函数为 (6-52)96 4.排队系统的优化目标 与最优化问题将L= ( -)，代入上式，得易见y是关于决策变量的一元非线性函数由一阶条件解得驻点 (6-53)97 4.排队系统的优化目标 与最优化问题 根号前取正号是为了保证

38、。这样，系统才能达到稳态。又由二阶条件 (因 ）可知(6-53)给出的*为(,)上的全局唯一最小点。将*代入 (6-52)中，可得最小总平均费用 （6-54）98 4.排队系统的优化目标 与最优化问题 另外，若设cw为平均每个顾客在队列中等待单位时间的损失，则需用取代式(6-52)中的L，这时类似可得一阶条件： 这是一个关于的四次方程，一般采用数值法(如牛顿法)确定其根*。99 4.排队系统的优化目标 与最优化问题二、M /M /s / 系统的最优服务台数 s*设目标函数为 (6-55)其中： s 并联服务台的个数(待定)； f (s) 整个系统单位时间的平均总费用，它是关于服务台数 s 的函数； c2平均每个服务台的单位时间费用；100cw平均每个顾客在系统中逗留(或等待)单位时间的损失；L(s)平均队长(或平均等待队长)，它是关于服务台数 s 的函数； 要确定最优服务台数 s*1，2，使 由于s取值离散，不能采用微分法或非线性规划的方法，因此我们采用差分法。显然有 （6-56）101 4.排队系统的优化目标 与最优化问题把式（6-55）代人式(6-56) 中，得可得令 (6-57) 依次计算