《运筹学》 课件 第10、11章 排队论、存储论

7/16/2024第10章排队论1WheretheTimeGoes美国人一生中平均要花费---7/16/202426年吃5年排队等待4年做家务2年回电话不成功1年寻找放置不当的物品8个月打开邮寄广告6个月停在红灯前AC尼尔森公司的调查在消费者经常遭遇排队问题的各类场所银行的排队率是73%；医院以44%居第二；零售商店的排队率以43%居第三。在调查受访的消费者中，超过60%的受访者称通常一周用于排队的时间高于30分钟。在所有受访的消费者中，有28%的人因排长队而转选其它服务提供商，66%的人因不想耽误时间而选择离开，而46%的人会有抱怨。7/16/20243行为研究结论行为科学家发现：无序排队是影响客户流失的一条主要原因。研究结果表明等候时间：超过十分钟，情绪开始急躁；超过二十分钟，情绪表现厌烦；超过四十分钟，常因恼火而离去。7/16/20244如何减少排队？减少等候时间的解决方案：开设更多的服务点；提供自助服务解决方案；雇用更多员工。7/16/20245排队管理系统的应用近年来，许多公共服务场所出现了排队机(ticketdispenserunit)，窗口秩序为之一变，一种令人耳目一新的排队方式：进得大门，在排队机的触摸屏上点一下所要办理的项目，排队机就会“吐”出一张像名片大小的号票，拿着这张号票安安静静地坐在休息区舒适的椅子上等候，轮到自己时，大屏幕和语音系统会提醒你到相应的窗口办理，井然有序。7/16/20246DisneyParis’sEuroDisney,Tokyo’sDisneyJapan,andtheU.S.’sDisneyWorldandDisneylandallhaveonefeatureincommon—longlinesandseeminglyendlesswaits。在游乐园中的频频排队会极为扫兴……7/16/20247Disney在佛罗里达州Orlando的DisneyLand里,游客们依着绳子排成许多队，指示牌可以估计出等待的时间，而许多大的电视屏幕为游客们提供消遣。DisneyLand中的FastPass系统就是想解决排队问题。7/16/20248WhatisFastPass?工作原理：到达的顾客将自己的票插入FastPass的slot中FastPass计算出建议顾客返回的时间间隔（timeinterval）或时间点或时间窗（timewindow）顾客无需排队，在指定的时间返回就可持票进入7/16/20249Disney’sFastpass7/16/202410

如何计算顾客等待时间？7/16/202411

排队论！服务系统的构成排队现象抽象成服务系统，它由顾客、服务机构、队列和服务规则等组成7/16/202412ThreePartsofaQueuingSystem

atDave’sCar-Wash7/16/202413排队系统的基本特征离开排队规则到达过程排队结构服务过程退出需求群体7/16/202414什么是排队论排队论是研究服务系统中排队现象随机规律的理论与方法。因为排队现象是一个随机现象，因此在研究排队现象的时候，主要采用的是研究随机现象的概率论作为主要工具，还有微分方程。7/16/202415排队论研究目的和内容减少顾客等待时间计算顾客平均等待时间计算顾客的平均队长提高服务系统的效率计算服务强度计算忙期\闲期对服务系统进行成本效益平衡分析增加服务台的成本与效益分析7/16/202416排队论发展简述1909年丹麦数学家A.K.Erlang(爱尔朗)服务于一家电话公司，他在解决自动电话设计问题时开始形成的，当时称为话务理论。他在热力学统计平衡理论的启发下，成功地建立了电话统计平衡模型，并由此得到一组递推状态方程，从而导出著名的爱尔朗电话损失率公式。7/16/202417排队论发展简述上世纪50年代，英国人D.G.Kendall提出嵌入马尔可夫链理论，以及对排队队型的分类方法，为排队论奠定了理论基础；上世纪60年代更多的应用于生产线，交通信号灯绿信比的设置等问题；上世纪70年代应用于计算机网络、通信等领域；如今通信系统仍然是排队论应用的主要领域,同时在运输、港口泊位设计、机器维修、库存控制等领域得到广泛应用，特别是服务行业。7/16/202418CONTENTS019目录7/16/202410.1

排队服务系统的基本概念10.2

到达间隔与服务时间的分布10.3

生灭过程与系统状态方程10.4

单服务台负指数分布排队模型10.5

多服务台排队模型10.6

其他类型排队模型10.7

排队系统的优化10.1排队服务系统的基本概念10.1排队服务系统的基本概念一个排队系统可以抽象描述为：为了获得服务的顾客到达服务设施前排队，等候接受服务，服务完毕后就自行离开。要求得到服务的对象称为顾客服务者称为服务设施或服务台顾客的到达和离开称为排队系统的输入和输出。顾客的总体称为顾客源或输入源。因此，任何一个排队系统是一种输入-输出系统。7/16/202421服务系统系统类型 顾客 服务台理发店 人 理发师银行出纳服务 人 出纳ATM机服务 人 ATM机超市收银台 人 收银员电影院售票窗口 人 售票员机场检票处 人 航空公司代理人7/16/202422服务系统系统类型 顾客 服务台公路收费站 汽车 收费员港口卸货区 轮船 卸货工人等待起飞的飞机 飞机 跑道航班服务 人 飞机出租车服务 人 出租车电梯服务 人 电梯停车场 汽车 停车空间急救车服务 人 急救车7/16/20242310.1.1排队服务系统的构成事实上，任何一个排队服务系统都是一种输入-输出系统。顾客的到达和离开称为排队系统的输入和输出。顾客的总体称为顾客源或输入源。顾客源等候队列服务设施到达输入输出离开排队系统7/16/202424排队系统的三个基本组成部分：输入过程(顾客按照怎样的规律到达)；排队规则(顾客按照一定规则排队等待服务)；服务机构(服务机构的设置,服务台的数量,服务的方式,服务时间分布等)10.1.1排队服务系统的构成7/16/202425一、输入ArrivalCharacteristics顾客源是有限集还是无限集（Sizeofthearrivalpopulation）工厂内待修的机器数是有限集，售票处购票顾客源可认为是无限集。顾客到达系统的方式是单个的，还是成批的（Behaviorofarrivals）如到达宾馆服务台住宿有散客，也有团体相继到达系统的时间间隔是确定性的还是随机性的（Patternofarrivalatthesystem）如自动装配线上待装配部件到达各工序的时间间隔是确定的。而多数顾客到达都是随机的，随机的服从某种概率分布：二项、负指数、爱尔朗分布等。7/16/202426到达过程(输入过程)的内容顾客总体数或顾客源数有限或无限顾客的到达类型单个或成批顾客的到达间隔时间间隔时间分布7/16/202427二、排队规则QueueDiscipline顾客来到排队系统后如何排队等候服务的规则1、即时制（损失制）：当顾客到达时，如果所有服务台都已被占用，顾客可以随即离开系统；如电话拨号后出现忙音，顾客可马上挂上电话。2、等候制：当顾客到达时，所有服务台都已被占用，顾客就加入排队队列等候服务。排队规则：FIFO/FCFS先到先服务，最常见LIFO：乘电梯的顾客是后进先出SIRO随机服务：从等待的顾客中随机取一个进行服务，人工电话交换优先权服务：重病优先、老年人优先等7/16/202428二、排队规则QueueDiscipline3、混合制：即时制和等候制相结合的一种排队服务规则。队列长度有限制时：排队等候的人数超过预定数量，后来的顾客就自动离开。排队时间有限制时：顾客排队等候超过一定的时间就会自动离开，不能再等；电子元器件库存超过一定时期，就失效了7/16/202429三、服务机构服务设施的结构、服务方式、服务时间：按服务设施个数分，有一个或多个之分，有并联和串联之分单台服务系统和多台服务系统服务方式有单个服务和成批服务服务时间是确定和随机的7/16/202430服务台结构等候队列服务台单服务台等候队列服务台2服务台1并列多台等候队列服务台1串列多台服务台2等候队列服务台3服务台1混列多台服务台4服务台27/16/202431服务方式

服务的方式是对单个顾客进行的，还是对成批顾客进行的。公共汽车站台等待的顾客是成批进行服务的。7/16/202432服务时间对顾客的服务时间是确定的还是随机的。自动冲洗汽车的装置对每辆汽车冲洗服务的时间是确定性的。但大多数情况下服务时间是随机性的。对于随机要知道它的概率分布，是定长、负指数还是爱尔朗分布。Servicetimedistribution7/16/202433排队结构多队多服务台领号34826101211579单队多服务台入口7/16/202434通常，按排队系统的主要特征来进行排队系统的分类。一般是以相继顾客到达系统的间隔时间分布类型、服务时间的分布类型和服务台数目为分类标志。Kendall提出一个排队系统的分类方法，特征可以用六个参数表示，形式为：

X／Y／Z其中X––顾客到达的概率分布，可取M、D、Ek、G等；Y––服务时间的概率分布，可取M、D、Ek、G等；Z––服务台个数，取正整数；10.1.2排队服务系统的分类7/16/202435X、Y可有四种分布符号M、D、Ek、GM—负指数分布所描述的随机现象对于过去的事件具有无记忆性或称马尔可夫性MarkovD—定长分布，事件以不变的方式发生DeterministicEk—k阶爱尔朗分布ErlangG—一般随机分布General如M/M/1表示到达的间隔时间服从负指数分布，服务时间也服从负指数分布的单服务台排队系统模型M/D/2表示到达的间隔时间服从负指数分布，服务时间为定长分布的双服务台排队系统模型10.1.2排队服务系统的分类7/16/2024361971年又将Kendall符号扩展为：

X／Y／Z/A／B／C其中：A––排队系统的最大容量，可取正整数N或

；B––顾客源的最大容量，可取正整数m或

；C––排队规则，可取FCFS、LCFS等。特别约定，如略去后三项，则是指

X／Y／Z/

／

／FCFS因为本课程只介绍FCFS,所以略去最后一项10.1.2排队服务系统的分类7/16/20243710.1.2排队服务系统的分类例

M/M/1/

/

/FCFS表示：顾客到达的时间间隔是负指数分布服务时间是负指数分布一个服务台排队系统和顾客源的容量都是无限实行先到先服务的一个服务系统

7/16/202438一个排队系统开始运行时,系统的运行状态在很大程度上取决于系统的初始状态和运转的时间。经过一段时间以后，系统的状态将独立于初始状态和经历时间，这时系统处于稳定状态。排队系统主要研究稳定状态。系统处于稳定状态时，工作状况与时刻t无关。10.1.3排队系统的相关术语7/16/202439主要名词术语平均到达率

n

：当系统中有n个顾客时，新来顾客的平均到达率（单位时间内顾客的到达数）。当对所有n值

n为常数时，可用代替n1/

为相邻两顾客到达系统的平均间隔时间。平均服务率

n

：当系统中有n个顾客时，单位时间内被服务完毕后离开系统的平均顾客数。当对所有n值，

n为常数时，可用代替n1/

为每个顾客的平均服务时间。c—系统中并列服务台数目。7/16/202440主要名词术语N(t)

在时刻t排队服务系统的顾客数，即系统在时刻t的瞬时状态。Pn(t)

在t时刻系统中恰好有n个顾客的概率主要分析系统平稳分布,即当系统达到统计平衡状态时处于状态n的概率,记为Pn7/16/202441主要系统性能指标平均逗留时间Ws

：进入系统的顾客逗留时间的平均值，包括接受服务的时间。平均等待时间Wq

：进入系统的顾客等待时间的平均值。服务机构工作强度

：服务机构累计的工作时间占全部时间的比例，即服务强度

平均顾客数Ls

：一个排队系统的顾客平均数，包括正在接受服务的顾客。平均队长Lq

：系统中等待服务的顾客平均数。7/16/202442常用的记号c—服务台的个数n––系统中的顾客数,即系统状态

––平均到达率，即单位时间内平均到达的顾客数

––平均服务率，即单位时间内服务完毕的顾客数Pn(t)––时刻t系统状态n的概率Pn––系统中的顾客数n（系统状态n)的稳态概率M––顾客相继到达的时间间隔服从负指数分布D––顾客相继到达的时间间隔服从定长分布Ek––顾客相继到达的时间间隔服从k阶Erlang分布G—顾客相继到达的时间间隔服从一般分布7/16/20244310.2到达间隔与服务时间的分布组成一个排队系统的四要素输入\输出\排队服务规则\服务机构顾客的输入和输出过程一般是随机的研究较多且结果较好的排队系统是：顾客的输入过程服从泊松分布，而服务时间服从负指数分布的排队系统若顾客输入过程服从泊松分布，则顾客相继到达的间隔时间服从负指数分布。10.2到达间隔与服务时间的分布7/16/202445定义：满足以下条件的输入流称为Poisson流（最简单流、Poisson过程）1）无后效性：不相交的时间区间内到达的顾客数互相独立。2）平稳性：对充分小的

t，在时间区间[t,t+

t)内到达1个顾客的概率与t无关，只与

t有关，即：其中：l是一个大于零的常数，表示单位时间内到达一个顾客的概率3）守序性：设在[t,t+

t）内到达多于一个顾客的概率为极小o(

t)。即 10.2.1Poisson流7/16/202446实际情况是否符合三条性质到达工厂机修车间的要维修的机器情况分析：因为每台机器在各个时刻处的状态大致一样，所以在相等时间区间内各台机器损坏的概率大致相同，即要求维修的机器的流具有平稳性由于一台机器的故障不会引起另一台机器的故障，而对同一台机器，这段时间内损坏的次数不影响到以后损坏次数多少，这表明具有无后效性由于每台机器损坏概率很小，在足够小的时间区间内发生两台及以上机器损坏的概率几乎为0，这就符合普通性。因此对到达机修车间的要维修的机器数可以认为是最简单流,即poisson流。7/16/202447Poisson流与Poisson分布定理1对于一个参数为

的Poisson流，在[0，t]内到达n个顾客的概率为

即服从以

为参数的Poisson分布。

7/16/202448PoissonDistributionsforArrivalTimesProbabilityProbability=2=4

：单位时间顾客的平均到达率7/16/202449Poisson流与负指数分布间的关系定理2

在排队系统中，如果单位时间内顾客到达数服从以

为参数的Poisson分布，则顾客相继到达的时间间隔T服从以

为参数的负指数分布。

l=0.41/

为平均到达间隔时间（expectedinterarrivaltime)7/16/202450负指数分布

NegativeExponentialDistribution分布函数7/16/202451负指数分布——无后效性无后效性表示T顾客到达的时间间隔已经过了s后，再等t的时间与s无关。7/16/20245210.2.2服务时间的分布1）负指数分布在排队系统中，一般假设服务时间（servicetime)服从参数为m的负指数分布：1/m为平均服务时间（expectedservicetime)7/16/202453平均服务时间Meanservicetime=1/

分布函数10.2.2服务时间的分布7/16/202454服务时间负指数分布的性质假如服务设施对每个顾客的服务时间服从负指数分布，则对每个顾客的平均服务时间为1/m当服务设施对顾客的服务时间t为参数m

的负指数分布时，则有在[t,t+

t]时间内，没有顾客离去的概率为1-m

t在[t,t+

t]时间内，恰有一个顾客离去的概率为m

t如果

t足够小，在[t,t+

t]时间内有多于两个以上顾客离去的概率趋于07/16/202455服务时间负指数分布的性质若按依次到达的间隔时间统计，顾客流服从负指数分布，则对同一顾客流若按单位时间到达的数量统计，它服从泊松分布。泊松分布和负指数分布是对同一顾客流按不同方式进行统计时得到的两种不同分布。7/16/2024562）k阶Erlang分布爱尔朗分布比负指数分布具有更广泛的适应性，k阶爱尔朗分布（Ek)的概率密度函数为：

10.2.2服务时间的分布7/16/202457爱尔朗分布的均值和方差是由此可得爱尔朗分布的阶数：10.2.2服务时间的分布7/16/20245810.2.2服务时间的分布m=1k=1k=2k=4k=87/16/202459K个相互独立的且具有相同参数的负指数分布的随机变量的和，其分布服从k阶Erlang分布。例如一台自动机床上依次利用三把刀具对一个工件进行加工，若每把刀具对该工件的加工时间均为参数相同的负指数分布，则该工件在自动机床上总的加工时间服从3阶Erlang分布10.2.2服务时间的分布7/16/202460定理3设v1，v2，…，vk是k个互相独立的，具有相同参数m的负指数分布的随机变量，则随机变量

Ek=v1+v2+…+vk服从k阶Erlang分布，Ek的密度函数为10.2.2服务时间的分布7/16/202461均值、方差和阶数总服务时间服从爱尔朗分布，其均值和方差是由此可得爱尔朗分布的阶数：每个服务台的平均服务时间是：7/16/20246210.3生灭过程10.3生灭过程排队系统—随机聚散服务系统顾客到达是“生”，顾客离开是“灭”7/16/202464生灭过程

Birth-deathprocessN(t)是系统t时刻的状态（顾客数），则{N(t),t>=0}就构成一个随机过程，若用“生”表示一个顾客的到达，“灭”代表一个顾客过程的离去，则对许多排队过程来说，{N(t),t>=0}也是一类特殊的随机过程——生灭过程7/16/202465定义：设{N(t),t>=0}是一个随机过程，如果其概率分布满足有如下性质：（1）给定N(t)=n,到下一个“生”（顾客到达）的间隔时间服从参数为ln的负指数分布;（2）给定N(t)=n,到下一个“灭”（顾客离去）的间隔时间服从参数为mn的负指数分布;（3）同一时刻只能到达一个或离去一个顾客；则称{N(t),t>=0}是生灭过程生灭过程

Birth-deathprocess7/16/202466当顾客到达时间服从参数为λn

的负指数分布时，则有:在[t,t+

t]时间内，没有顾客到达的概率为在[t,t+

t]时间内，恰有一个顾客到达的概率为如果

t足够小，在[t,t+

t]时间内有多于两个以上顾客到达的概率趋于07/16/202467生灭过程

Birth-deathprocess当服务设施对顾客的服务时间服从参数的负指数分布时，则有:在[t,t+

t]时间内，没有顾客离去的概率为在[t,t+

t]时间内，恰有一个顾客离去的概率为如果

t足够小，在[t,t+

t]时间内有多于两个以上顾客离去的概率趋于07/16/202468生灭过程

Birth-deathprocessnnn+1n-1nPn(t)Pn-1(t)Pn+1(t)Pn(t)t时刻t+

t时刻无到达，无离开无到达，离开一个到达一个，无离开到达一个，离开一个假设在t+

t时刻系统中顾客数为n的概率Pn(t+

t)7/16/202469生灭过程

Birth-deathprocess7/16/202470生灭过程

Birth-deathprocess系统的过渡状态与稳定状态过渡稳定7/16/202471生灭过程的稳定状态方程生灭过程的瞬时状态一般很难求得，但可求得稳定状态分布7/16/202472生灭过程的稳定状态转移图对于稳定的生灭状态，从平均意义上说有：“流入速率=流出速率”稳定的生灭过程可以用状态转移图表示7/16/202473生灭过程的稳态方程基本原理系统任意状态n达到稳态平衡的条件是：产生该状态的平均速率等于该状态转变成其他状态的平均速率例如，对于系统状态n=0的情况，产生和破坏该状态的可能性有两种情况。如后图所示。7/16/202474n=0状态的产生和破坏7/16/202475n=1状态的产生和破坏7/16/202476n=2状态的产生和破坏7/16/202477n-1状态的产生和破坏7/16/202478任意状态n的产生和破坏7/16/202479λ012n-1nn+17/16/202480生灭过程Birth-deathprocess生灭过程的基本公式7/16/202481生灭过程的状态概率因为所以即得7/16/202482标准的排队过程是参数不随状态而变的特殊的生灭过程7/16/202483生灭过程

Birth-deathprocess10.4单服务台负指数分布排队模型输入过程为泊松流，服务时间基本服从负指数分布的排队系统10.4.1标准M/M/1/∞/∞10.4.2有限队列模型M/M/1/N/

/10.4.3顾客为有限源系统M/M/1/∞/m10.4单服务台负指数分布排队模型7/16/20248510.4.1标准排队模型[M/M/1/

/

/FCFS][M/M/1/

/

/FCFS]顾客到达的时间间隔是负指数分布服务时间是负指数分布一个服务台排队系统和顾客源的容量都是无限实行先到先服务的一个服务系统7/16/202486M/M/1的状态转移分析012n-1nn+17/16/202487M/M/1排队模型标准的排队过程是参数不随状态而变的特殊的生灭过程7/16/202488得到

令

称

为服务强度，则得由M/M/1排队模型7/16/202489例10.1高速公路入口收费处设有一个收费通道，汽车到达服从Poisson分布，平均到达速率为100辆／小时，收费时间服从负指数分布，平均收费时间为15秒／辆。求1、收费处空闲的概率；2、收费处忙的概率；3、系统中分别有1，2，3辆车的概率。7/16/202490M/M/1排队模型根据题意,

=100辆/小时,1/

=15秒=1/240（小时/辆）,即

＝240（辆/小时）。因此，

=

/

=100/240=5/12。系统空闲的概率为：

P0=1-

=1-(5/12)=7/12=0.583系统忙的概率为：

1-P0=1-(1-

)=

=5/12=0.417系统中有1辆车的概率为：

P1=

(1-

)=0.417×0.583=0.243系统中有2辆车的概率为：

P2=

2(1-

)=0.4172×0.583=0.101系统中有3辆车的概率为：

P3=

3(1-

)=0.4173×0.583=0.04217/16/202491M/M/1排队模型解：系统绩效度量

系统中的平均顾客数LsExpectednumberofcustomersinsystem

平均等待顾客个数Lq（排队长）

Expectedqueuelength(excludecustomersbeingserved)

顾客平均逗留时间Ws

Waitingtimeinsystem

顾客平均（排队）等待时间WqWaitingtimeinqueue(excludeservicetime)7/16/202492M/M/1/

/

/FCFS的系统指标系统中的平均顾客数Ls

队列中的平均顾客数Lq7/16/202493顾客在系统中的平均逗留时间顾客在系统中的逗留时间Ts服从参数为m-l的负指数分布7/16/202494顾客在系统中的平均逗留时间Ws

顾客在队列中的平均逗留时间Wq

顾客在系统中的平均逗留时间7/16/202495JohnD.C.Little公式7/16/202496理发店空闲的概率店内有3个顾客的概率店内至少有一个顾客的概率店内顾客的平均数，等待服务顾客的平均数顾客在店内的平均逗留时间和平均等待时间必须在店内消耗15分钟以上的概率例10.2某理发店只有一名理发师，来理发的顾客按泊松分布到达，平均每小时4人，理发时间服从负指数分布，平均需要6分钟，求7/16/202497M/M/1排队模型(3)P(n≥1)=1−P(n<1)=1−P0=0.4(4)Ls=r/(1−r)=0.4/(1−0.4)=0.667人

Lq=Ls−r=0.667-0.4=0.227解：此为M/M/1系统，已知l=4/60=1/15人/分

m=1/6人/分，r=l/m=(1/15)/(1/6)=0.4(1)P0=1−r=1=0.4=0.6(2)P3=(1−r)r3=0.6×0.43=0.03847/16/202498M/M/1排队模型

例10.3高速公路入口收费处设有一个收费通道，汽车到达服从Poisson分布，平均到达速率为200辆/小时，收费时间服从负指数分布，平均收费时间为15秒/辆。求Ls、Lq、Ws和Wq。7/16/202499M/M/1排队模型解：根据题意，

=200辆/小时，

=240辆/小时，

=

/

=5/6。7/16/2024100M/M/1排队模型当队列的容量从无限值变为有限值N时，[M/M/1/

/

/FCFS]就转化成为[M/M/1/N/

/FCFS]

10.4.2有限队列模型M/M/1/N/

/FCFS7/16/2024101系统的状态转移图012N-1N7/16/2024102系统的状态概率平衡方程对于状态0：

0P0=

1P1

… …对于状态n：

n-1Pn-1+

n+1Pn+1=(

n+

n)Pn0<n<N… …对于状态N：

N-1PN-1=

NPN7/16/2024103系统参数7/16/2024104系统状态概率PN称为顾客损失率7/16/2024105系统的状态概率由得到

7/16/2024106系统的运行指标当r=1时的情形，此时由得：7/16/2024107系统的运行指标对于

1有7/16/2024108有效到达率7/16/2024109Little公式7/16/2024110例10.4

一个单人理发店，除理发椅外，还有4把椅子可供顾客等候。顾客到达发现没有座位空闲，就不再等待而离去。顾客到达的平均速率为4人/小时，理发的平均时间为10分钟/人。顾客到达服从Poisson流，理发时间服从负指数分布。求：1、顾客到达不用等待就可理发的概率；2、理发店里的平均顾客数以及等待理发的平均顾客数；3、顾客来店理发一次平均花费的时间及平均等待的时间；4、顾客到达后因客满而离去的概率顾客损失率；5、增加一张椅子可以减少的顾客损失率。7/16/202411110.4.2有限队列模型M/M/1/N/

/FCFS解：这是一个[M/M/1/N/

/FCFS]系统，其中N=4+1=5，

=4人/小时，

=6人/小时，

=2/3。

7/16/202411210.4.2有限队列模型M/M/1/N/

/FCFS因客满而离去的概率为0.00487/16/202411310.4.2有限队列模型M/M/1/N/

/FCFS当N=6时

P5-P6=0.0480-0.0311=0.0169=1.69%即增加一张椅子可以减少顾客损失率1.69%7/16/202411410.4.2有限队列模型M/M/1/N/

/FCFS设顾客总数为m,当顾客需要服务时，就进入队列等待；服务完毕后，重新回到顾客源中,如此循环往复。。。服务台...顾客源需要服务服务完毕队列10.4.3M/M/1/∞/m/FCFS模型7/16/2024115关于顾客的平均到达率，在无限源的情形下是按全体顾客来考虑的，而在有限源的情形下，必须按照每个顾客来考虑，l即为每一顾客单位时间内请求服务的平均次数。10.4.3M/M/1/∞/m/FCFS模型7/16/2024116分析假定每一个顾客在单位时间内需要接受服务的平均次数是相同的，设为λ

。当正在等待及正在接受服务的顾客数为n时，则在单位时间内要求接受服务的平均顾客数为：

λn=λ(m-n)01nm7/16/2024117状态转移方程λ0P0=μP1 ……[λn+μ]Pn=μPn+1+λn-1Pn-1

(n=1，2，…，m-1) ……μPm=λm-1Pm-1

(n=1，2，…，m) 7/16/20241187/16/2024119状态转移方程有效到达率λn=λ(m-n)n=1,2,…,m7/16/2024120系统绩效指标7/16/2024121例10.5某车间有5台机器，每台机器的连续运转时间服从负指数分布，平均连续运行时间15分钟。有一个修理工，每次修理时间服从负指数分布，平均每次12分钟。求:(1)修理工空闲的概率；(2)五台机器都出故障的概率；(3)出故障的平均台数；(4)平均停工时间；(5)平均等待修理时间；(6)评价这个系统的运行情况。7/16/202412210.4.3M/M/1/∞/m/FCFS模型解：根据题意，m=5，λ=1/15，μ=1/12，ρ=λ/μ=0.8

7/16/202412310.4.3M/M/1/∞/m/FCFS模型（7）系统绝对通过能力（工人的维修能力）A=le=l(m-Ls)=m(1-P0)=0.083

每小时维修0.083*60=4.96（台）总体看来，该维修系统较繁忙，机器等待时间过长。7/16/202412410.4.3M/M/1/∞/m/FCFS模型10.5多服务台排队模型标准的[M/M/c/∞/∞/FCFS]模型系统容量有限的[M/M/c/N/∞/FCFS]模型有限顾客源的[M/M/c/∞/m/FCFS]模型

10.5多服务台排队模型7/16/2024126服务台服务台服务台顾客到达顾客离去顾客离去顾客离去队列顾客到达后，进入队列尾端；当某一个服务台空闲时，队列中的第一个顾客即到该服务台接收服务；服务完毕后随即离去。各服务台互相独立且服务速率相同，即μ1=μ2=…=μc

10.5.1M/M/c/∞/∞/FCFS模型7/16/2024127分析系统的服务速率与系统中的顾客数有关。当系统中的顾客数k不大于服务台个数，即1≤k≤c时，系统中的顾客全部在服务台中，这时系统的服务速率为kμ；当系统中的顾客数k＞c时，服务台中正在接受服务的顾客数仍为c个，其余顾客在队列中等待服务，这时系统的服务速率为cμ。

则当ρ＜1时系统才不会排成无限的队列

7/16/2024128状态转移图与状态转移方程对状态0: λP0=μP1

对状态1: λP0+2μP2=(λ+μ)P1 …………对状态c： λPc-1+cμPc+1=(λ+cμ)Pc …………对状态n λPn-1+cμPn+1=(λ+cμ)Pn ………01cn7/16/2024129状态概率7/16/2024130运行指标7/16/2024131例10.6某售票处有三个窗口，顾客到达服从Poisson流，到达速率为0.9人／分，售票时间服从负指数分布，每个窗口的平均售票速率为0.4人／分。顾客到达后排成一队，依次到空闲窗口购票。求：(1)所有窗口都空闲的概率；(2)平均队长；(3)平均等待时间及逗留时间；(4)顾客到达后必须等待的概率。7/16/202413210.5.1M/M/c/∞/∞/FCFS模型解：λ/μ=2.25，ρ=λ/cμ=0.75(1)所有窗口都空闲的概率，即求P0的值

(2)平均队长，即求Ls的值，必须先求Lq

7/16/202413310.5.1M/M/c/∞/∞/FCFS模型(3)平均等待时间和平均逗留时间，即求Wq和Ws和的值

(4)顾客到达后必须等待，即n≥37/16/202413410.5.1M/M/c/∞/∞/FCFS模型M/M/C型VSC个M/M/1型如果顾客到达后在每个窗口各排一队，且进入队列后不可更换，形成3个队列，在上例中，每个队列的平均到达率为：7/16/2024135M/M/1系统的指标λ=0.3，μ=0.4，ρ=λ/μ=0.75P0=1-ρ=0.25P(n>=1)=1-P0=0.75Ls=λ/(μ-λ)=3Lq=Ls-ρ=3-0.75=2.25Ws=Ls/λ=10分Wq=Ws-1/μ=7.5分7/16/2024136指标模型M/M/3M/M/1服务台空闲的概率P00.07480.25(每个子系统）顾客必须等待的概率0.570.75平均队列长（等待顾客数）Lq1.702.25(每个子系统）平均队长（顾客数）Ls3.959.00（整个系统）平均逗留时间Ws4.39分钟10分钟平均等待时间Wq1.89分钟7.5分钟由此可见，单队比三队有显著的优越性。系统指标对比结果7/16/2024137离开服务台服务台服务台顾客到达顾客离去顾客离去顾客离去队列10.5.2M/M/c/N/∞/FCFS模型7/16/2024138分析设系统容量为N(N≥c)，当系统中的顾数n＜N时，到达的顾客就进入系统；当n=N时，到达的顾客就被拒绝。设顾客到达的速率为λ，每个服务台服务的速率为μ，ρ=λ/cμ。由于系统不会无限止地接纳顾客，对ρ不必加以限制。

7/16/2024139状态转移图与状态转移方程对状态0: λP0=μP1

对状态1: λP0+2μP2=(λ+μ)P1 …………对状态c： λPc-1+cμPc+1=(λ+cμ)Pc …………对状态N λPN-1=cμPN ………01cN7/16/2024140状态概率7/16/2024141系统指标7/16/2024142例10.7某旅馆有8个单人房间，旅客到达服从Poisson流，平均速率为6人／天，旅客平均逗留时间为2天，求：(1)每天客房平均占用数；(2)旅馆客满的概率。7/16/202414310.5.2M/M/c/N/∞/FCFS模型旅馆8个房间全满的概率为0.423平均占用客房数为6.9间。客房占用率为86.6%7/16/202414410.5.2M/M/c/N/∞/FCFS模型解：顾客到达修理速率μ发生故障等待修理的机器修理速率μ修理速率μ正在修理的机器到达速率(m-n)λ修理速率cμ运行的机器数m-n10.5.3M/M/c/∞/m/FCFS模型7/16/2024145状态概率其中

7/16/2024146系统指标有效到达速率λe为单位时间内出现故障的机器数，有

λe=λ(m-Ls)7/16/2024147例10.8车间有5台机器，每台机器的故障率为1次／小时，有2个修理工负责修理这5台机器，工作效率相同，为4台／小时。求：(1)等待修理的平均机器数；(2)等待修理及正在修理的平均机器数；(3)每小时发生故障的平均机器数；(4)平均等待修理的时间；(5)平均停工时间。7/16/202414810.5.2M/M/c/N/∞/FCFS模型可以计算得到（算式略）：P1=0.394，P2=0.197，P3=0.074，P4=0.018，P5=0.0027/16/202414910.5.2M/M/c/N/∞/FCFS模型解：由此，计算系统的各项运行指标如下：7/16/202415010.5.2M/M/c/N/∞/FCFS模型10.7排队系统的优化一般排队系统的总费用构成：总费用=服务能力费+顾客损失费最佳服务能力服务能力顾客损失费服务能力费总费用费用10.7排队系统的优化7/16/2024152单位时间总费用单位时间服务成本单位顾客停留单位时间损失成本1）

M/M/1/

模型优化10.7.1M/M/1模型的最优服务率μ*7/16/202415310.7.1M/M/1模型的最优服务率μ*7/16/20241542）M/M/1/K模型优化顾客被拒概率为PK,接受概率1-PK,有效到达率le.设每服务一个顾客服务机构获G元,则单位时间收入期望值为利润：10.7.1M/M/1模型的最优服务率μ*7/16/2024155令：得：由此确定出r,进而确定出使服务系统最优的m*

10.7.1M/M/1模型的最优服务率μ*7/16/2024156每个服务台单位时间成本每位顾客停留单位时间损失成本10.7.2M/M/c/

∞/

∞/FCFS模型的最优服务台数c*7/16/202415710.7.2M/M/c/

∞/

∞/FCFS模型的最优服务台数c*7/16/20241587/16/2024第11章存储论159CONTENTS7/16/20240160目录11.1存储论概述11.2确定性存储基本模型11.3随机需求的基本存储模型11.1存储论概述库存一词在英语里面有两种表达方式：Inventory和Stock，它表示用于将来目的的资源暂时处于闲置状态。库存的目的：是防止短缺，就象水库里储存的水一样；它还具有保持生产过程连续性、分摊订货费用、快速满足用户订货需求的作用。11.1存储论概述7/16/2024162库存是缓解供给与需求之间不协调的重要环节供应需求库存11.1存储论概述7/16/2024163库存的双重影响积极影响缓冲作用制造与购买中的经济性生产连续运行的媒介服务水平(ServiceLevel)消极影响占用流动资金库存系统运行费用机会成本(OpportunityCost)掩盖管理问题7/16/2024164顾客的参与产出产品服务投入人力物料设备技术信息能源土地实施信息反馈变换过程12345生产与运作活动过程7/16/2024165TypesofInventoryMaintenance/Repair/Operatingsupply(MRO)FinishedgoodsRawmaterialWork-in-process(WIP)1.原材料2.在制品3.维修备件4.产成品7/16/2024166TypesofInventoriesHeldinaSupplyChain7/16/2024167CycleStockandSafetyStockCycleStockCycleStockCycleStockSafetyStockOnHandWhatshouldmyinventorypolicybe?(howmuchtoorderwhen)Whatshouldmysafetystockbe?Whataremyrelevantcosts?Time7/16/2024168库存论发展的里程1915年F．哈里斯就稳定需求，即对供应的情况得出关于存储费用的“简单批量公式”。1929年，L．梅厄（奥地利人）出版的《仓库业的经营经济学》是与库存论有关的早期著作之一。二战后，由于成批生产的日益普遍，同时由于运筹学的其他分支和管理科学的建立，库存论得到深入的发展，例如随机性模型得到进一步的研究，20世纪50年代，库存论成为一门应用广泛的运筹学的分支学科。库存论被应用到更广泛的领域：停车场大小，铁路车场侧线数量、电力系统发电设备容量、计算机容量等的决策问题都可应用库存论来解决。自上世纪70年代，汽车工业的发展和生产管理，为库存论的研究注入新的要素，如JIT.7/16/2024169供应链管理环境下的库存库存问题信息类问题（牛鞭效应）供应链的运作问题供应链的战略与规划问题库存策略：VMI管理系统联合库存管理多级库存优化7/16/2024170供应需求库存库存的基本问题:什么时候补货(When)?补多少(Howmany)?11.1.2存储问题的分类7/16/2024171库存分类在库存理论中，人们一般根据物品需求的重复程度分为单周期库存和多周期库存。单周期需求也叫一次性订货，这种需求的特征是偶发性和物品生命周期短，因而很少重复订货，如报纸，没有人会订过期的报纸来看，人们也不会在农历八月十六预订中秋月饼，这些都是单周期需求。多周期需求是在长时间内需求反复发生，库存需要不断补充，在实际生活中，这种需求现象较为多见。7/16/2024172库存问题的基本术语需求（demand)确定随机补充(订货)（replenishment)Leadtime(从订货到进货的时间，备货时间）订货周期（OrderCycleTime)订货量（OrderQuantity）费用（cost)存储费HoldingCost缺货费ShortageCost订货费OrderingCost+PurchaseCost生产费(set-upcost设备安装费+productcost生产费用）7/16/2024173库存策略库存策略（inventorystrategy)t0

循环策略，每隔t0时间补充库存量Q0(t,S)策略,每隔固定时间t补充一次,补充数量以补足一个固定的存储量S为准.(s,S)策略，当存储量x>s时，不补充；当存储量x<s时，补充量Q=S-x；(t,s,S)策略，经过时间t检查库存量x,当x>s时，不补充；当x<s时，补充库存量到S7/16/2024174库存策略定量(定点)订货策略(EOQ)(fixed-orderquantitymodel,Qmodel)事件驱动的，当到达规定的再订货水平的事件发生时，就进行订货，这种事件可能随时发生；平均库存量较小，有利于贵重物品的库存；定期订货策略（Fixed-timeperiodmodel,Pmodel)时间驱动的，只限定在时间期末进行订货；平均库存量较大。在确定性需求下,这两个定货模型是一样的时间定了，定货量也定了.7/16/2024175CycleStockandSafetyStockCycleStockCycleStockCycleStockSafetyStockOnHandTime7/16/2024176随机需求下的订货策略定点订货策略

如何确定每次订货量Q？

7/16/2024177最高库存M如何确定？

定期订货策略

随机需求下的订货策略7/16/2024178库存模型的分类确定性需求模型不允许缺货、瞬时生产时间不允许缺货、生产需要时间允许缺货、瞬时生产时间允许缺货、生产需要时间价格有折扣随机性需求模型离散需求连续需求7/16/2024179报童问题（Newsboyproblems）

一名报童以每份0.20元的价格从发行人那里订购报纸然后再以0.50元的零售价格出售，但是他在订购第二天的报纸时不能确定实际的需求量而只是根据以前的经验知道需求量具有均值为50份标准偏差为12份的正态分布那么他应当订购多少份报纸呢？经典的随机库存模型7/16/2024180报童模型的扩展

ExpansionofInventoryManagement

约会问题(DateProblem)

您要与您的女朋友晚上六点钟在她家附近的一个地方约会，您估计从您的办公室乘车过去所用的平均时间是30分钟，但由于高峰期会出现交通阻塞因此还会有一些偏差，路程所用时间的标准偏差估计为10分钟，虽然很难量化您每迟到一分钟所造成的损失，但是您觉得每晚到一分钟要比早到一分钟付出十倍的代价，那么您应当什么时候从办公室出发呢？7/16/2024181报童模型的扩展超额预售机票问题（ExcessiveAirTicketSalesProblem）一家航空公司发现一趟航班的持有机票而未登机（no-show）的人数具有为20人，标准偏差为10人的正态分布，根据这家航空公司的测算每一个空座位的机会成本为100美元，乘客确认票后但因满座不能登机有关的罚款费用估计为400美元，该航空公司想限制该航班的“超额预订”，飞机上共有150个座位，确认预订的截止上限应当是多少？7/16/202418211.2确定性存储基本模型11.2.1不允许缺货的存储模型例：某医院药房每年需某种药品1600瓶，每次订购费为5元，每瓶药品每年保管费0.1元，试问一年应订购多少次？每次应订多少瓶？例：某轧钢厂每月按计划需生产角钢3000吨，每吨每月存储费5.3元，每次生产需调整机器设备，共需装配费2500元.试排一个全年的排产计划。7/16/2024184t进货周期……时间库存水平最高库存Q平均库存Q/2一年7/16/202418511.2.1不允许缺货的存储模型费用分析

单位货物存储费率C1单位货物缺货损失C2每次采购费用C3货物单价为K最佳采购量Q*每次采购量缺货成本+采购费库存费用总成本费用7/16/2024186要达到的目标达到最小成本成本的构成与存储有关的费用由缺货所引起的费用采购费用可控变量订货时间每次进货量库存模型的要素7/16/2024187模型一：不允许缺货且瞬时补货的存储模型模型假设：需求是连续的、均匀的，需求速度为R（单位时间的需求量）;缺货费用无穷大（单位时间缺少单位货物的费用）；当库存降至零时，可立即得到补货，忽略生产时间；每次订货量不变，订购费不变；单位时间单位货物存储费不变。7/16/2024188经济批量(EOQ)t进货周期……时间库存水平最高库存Q平均库存Q/2一年7/16/2024189平均费用C(t)＝存储费＋订货费第一项是存储费用，时间越长，该项费用越大，因此从存储费用看每次应当尽量少购一点；第二项是订购费，它与订货量无关，因此订货量越大（可用时间越长），单位货物费用越少，从这一点上说应当每次尽量多采购一些。7/16/2024190经济批量(EOQ)经济批量模型的解(EOQ)订货周期批次经济批量最少平均费用（不包括KR）7/16/2024191EOQ模型的应用例11.1某医院药房每年需某种药品1600瓶，每次订购费为5元，每瓶药品每年保管费0.1元，试求经济订货量？解：已知R=1600，C1=0.1，C3=5。经济批量7/16/2024192比较分析批量年存储费年订购费年总费用费用最小批量QC10020030040050060051015202530804026.7201613.3855041.7404143.3Q*7/16/2024193EOQ模型的应用例11.2某企业经销某类电子配件，该电子配件的单位进货价为500元，年存储费为成本的20%，年需求量365件，需求速度为常数，该电子配件的订购费为20元，假设该商品的补货可以随时实现。求最佳订货批量和最低订货周期。7/16/2024194解：依题意，由EOQ公式（11.5）得，最优订货批量为：最优订货间隔时间为：生产速度(或补货速度)P>RT时间库存水平最高库存S平均库存S/2一年t-T边生产边销售期销售期t模型二:不允许缺货且补货需要时间的存储模型7/16/2024195变量：最大存储量S最大订购量：Q订货周期：t边生产边销售期：T存储期：t-T关系：S=(P-R)T=R(t-T)T与t的关系：指在T时间内生产的要足够满足在t时间内所消耗掉的模型二:不允许缺货且补货需要时间的存储模型7/16/2024196平均费用C(t)＝存储费＋调整费最佳生产周期：每次最佳生产批量：模型二：不允许缺货且补货需要时间的存储模型7/16/2024197例11.5某汽车公司每月汽车底盘的需求为100件，每月的生产率为500个，每批装配费为5元，每月每个汽车底盘存储费为0.4元，问应如何安排生产使总费用最少？7/16/2024198模型二:不允许缺货且补货需要时间的存储模型解：依题意可知，C3=5,C1=0.4,P=500,R=100则最优生产量为

最佳周期为11.2.2允许缺货的存储模型上节中模型研究的是不允许缺货情形下的存储问题，即假设产品的缺货费用无穷大。而现实中有些情况是允许产品暂时出现缺货的。顾客在购买彩电、冰箱或空调等商品时，供应商暂时缺货，但顾客愿意等待直到之后的某个日期收到供货。因此，有必要进一步研究允许缺货的经济批量模型。7/16/2024199缺货期t2t1库存期……时间库存水平最高库存S平均库存S/2一

年缺货量QtQ模型三：允许缺货且瞬时补货的存储模型7/16/2024200变量：S：最大存储量；Q：最大订购量;Q-S：最大缺货量订货周期：t=t1+t2；

存储期：t1；缺货期：t2

关系：S=Rt1t1=S/R缺货期t2t1库存期……时间库存水平最高库存S平均库存S/2一

年缺货量QtQ模型三：允许缺货且瞬时补货的存储模型7/16/2024201t时间内平均费用C(t1,t2)＝存储费＋订货费＋缺货费最佳订货周期：模型三：允许缺货且瞬时补货的存储模型7/16/2024202最佳订货批量最大库存量最佳缺货量模型三：允许缺货且瞬时补货的存储模型7/16/2024203例11.7某大型超市对某款彩电的年需求量为4900台，设每次定购费为50元，每台每年存储费为100元。如果允许缺货，每台每年的缺货损失费为200元，试求最佳存贮方案。7/16/2024204模型三：允许缺货且瞬时补货的存储模型解：根据题意知最佳订货周期为最大存储量为7/16/2024205最低费用为最佳订货量为最大缺货量为模型三：允许缺货且瞬时补货的存储模型生产速度Pt1时间库存水平最高库存S一年t2边生产边销售期销售期t缺货期t3模型四：允许缺货但需补货时间的存储模型7/16/2024206变量：最大存储量：S最大订购量：Q最大缺货量：B=Q-S缺货期：[0,t2]，t1;存储期：[t2,t],t3;模型四：允许缺货但需补货时间的存储模型7/16/2024207关系：缺货量：B=Rt1=(P-R)(t2-t1)t1=(P-R)t2/P存储量：S=(P-R)(t3-t2)=R(t-t3)(t3-t2)=R(t-t2)/P模型四：允许缺货但需补货时间的存储模型7/16/2024208在[0,t]时间内的费用：存储费=存储量*C1缺货费=缺货量*C2定购费（装配费）=C3模型四：允许缺货但需补货时间的存储模型7/16/20242097/16/2024210

模型四：允许缺货但需补货时间的存储模型模型四的最优解11.2.3四种模型的比较分析7/16/202421111.2.3四种模型的比较分析从最佳订货量看不允许缺货且瞬时补货情况下的最优订货量最小，即模型一的订货量最少；允许缺货，且补货需要时间情况下的最优订货量最多，即模型四的最佳订货量最多。从最佳订货周期看不允许缺货且瞬时补货情况下的订货周期最短，即模型一的订货周期最短；允许缺货且补货需要时间情况下的订货周期最长，即模型四的订货周期最长。显然，当补货速度充分大时，模型二的解接近模型一的解；当缺货成本

充分大时，模型三的解接近模型一的解。7/16/2024212价格-订购量关系如下图所示11.2.4经济批量折扣模型7/16/2024213根据价格-订购量关系图，给出价格区间11.2.4经济批量折扣模型7/16/2024214费用分析一个周期内，所需平均费用为平均费用C(Q)是关于Q的分段函数，分别为7/16/2024215平均费用图示7/16/2024216费用分析单位时间所需平均费用为不考虑购买费用时的最低费用7/16/2024217求经济批量的方法求经济批量的步骤计算Q0若Q0<Q1，计算求得经济批量Q*若Q1≤Q0<Q2，计算并由

确定经济批量Q*若Q2<Q0，则经济批量Q*=Q0。7/16/2024218例11.9在例11.1中，假如药房经理计划向药品生产商成批量订购。药品生产商提出若一次订购800瓶以上，价格为9.8元/瓶，否则为10元/瓶。药房经理应如何订购最为经济？例11.1某医院药房每年需某种药品1600瓶，每次订购费为5元，每瓶药品每年保管费0.1元，试求每次应订多少瓶？7/16/202421911.2.4经济批量折扣模型价格有折扣问题举例解：首先计算在例1中，假如制药厂提出若一次订购800瓶以上，价格为9.8元/瓶，否则为10元/瓶，应如何订购？7/16/2024220由于400<800，计算

可以看出

CII(800)<CI(400)

所以最佳采购批量是Q=800瓶/次。7/16/2024221价格有折扣问题举例再举一例在上例中，如果R=900瓶/年，C1=2元/瓶年，C3=100元/次，折扣政策Q<900瓶/次，每瓶10元，Q≥900瓶/次，每瓶9.9元。医院应采取什么存储策略？解：计算经济批量计算C(300)和C(900)7/16/2024222计算结果因为C(300)<C(900)，因此应当一年采购三次，每次300瓶，而不是一年采购一次，每次900瓶。7/16/202422311.3随机需求的基本存储模型需求是随机的，分布概率已知。因为需求随机，因此进货太少，将失去销售机会；进货太多，则因滞销造成损失。随机存储策略的优劣一般用用期望利润值或期望损失值的大小来衡量，而不是只考虑成本。11.3随机需求的基本存储模型7/16/2024225随机需求下的库存问题—例某商店拟在新年期间出售一批日历画片，每售出一千张可赢利7元，如果在新年期间不能售罄，必须降价处理，一定可以售完，此时每千张赔损4元。已知市场需求概率见下表，每年只能订货一次，问应订购多少张日历才能使获利最大。需求(千张)012345概率0.050.10.250.350.150.17/16/2024226分析我们可以计算出商家不同定购量和不同需求量时的损益值，和风险决策相似，给出损益表rQ012345期望值0.050.100.250.350.150.100123450-4-8-12-16-20073-1