下载文档原格式
排队论例1题目：某火车站的售票处设有一个窗口,若购票者是以最简单流到达,平均每分钟到达1人,假定售票时间服从负指数分布,平均每分钟可服务2人,试研究售票窗口前排队情况解:由题设λ=1(人/分),μ=2(人/分),ρ=λμ=12平均队长L=1ρρ-=1(人)平均等待队长Lq=21ρρ-=12(人)平均等待时间Wq=λμμ（-1）=12(分)平均逗留时间W=1μλ-=1(分)顾客不需要等待的概率为P o=12,等待的顾客人数超过5人的概率为P(N≥6)=1766666111111()(1)()()()()222222n n nnn n n nPρ-∞∞∞∞=====-===∑∑∑∑1例2题目：在某工地卸货台装卸设备的设计方案中,有三个方案可供选择,分别记作甲、乙、丙。
目的是选取使总费用最小的方案，有关费用（损失）如下表所示设货车按最简单流到达，平均每天（按10小时计算）到达15车，每车平均装货500袋，卸货时间服从负指数分布，每辆车停留1小时的损失为10元。
解：平均到达率λ=1.5车/小时,服务率μ依赖于方案μ甲=1000/500/袋小时袋车=2车/小时μ乙=2000/500/袋小时袋车=4车/小时μ丙=6000/500/袋小时袋车=12车/小时由(7.2.6),1辆车在系统内平均停留时间为W甲=12-1.5=2(小时/车)W乙=14-1.5=0.4(小时/车)W丙=112-1.5=0.095(小时/车)每天货车在系统停留的平均损失费为W⨯10⨯15,每天的实际可变费用(如燃料费等)为(可变操作费/天)⨯设备忙的概率=c p(元/天)而ρ甲=0.75 , ρ乙=0.375 , ρ丙=0.125,所以每个方案的费用综合如下表所示:23例3 题目：要购置计算机,有两种方案.甲方案是购进一大型计算机,乙方案是购置n 台小型计算机.每台小型计算机是大型计算机处理能力的1n设要求上机的题目是参数为λ的最简单流,大型计算机与小型计算机计算题目的时间是负指数分布,大型计算机的参数是μ.试从平均逗留时间、等待时间看，应该选择哪一个方案 解：设ρ=λμ，按甲方案，购大型计算机 平均等待时间 q W 甲=ρμρ（1-）=λμμλ（-）平均逗留时间 W 甲=1μλ- 按乙方案，购n 台小型计算机，每台小计算机的题目到达率为n λ，服务率为nμ, ρ=//n n λμ=λμ平均等待时间 W q 乙=nρμρ（1-）=n ρμρ（1-）=nW q 甲平均逗留时间 W 乙=1n nμλ-=n μλ-=nW 甲所以只是从平均等待时间，平均逗留时间考虑，应该购置大型计算机4例4题目：设船到码头，在港口停留单位时间损失c 1 元，进港船只是最简单流，参数为λ，装卸时间服从参数为μ的负指数分布，服务费用为c μ2，c 2是一个正常数.求使整个系统总费用损失最小的服务率μ 解:因为平均队长L λμλ=-,所以船在港口停留的损失费为1c λμλ-,服务费为c μ1,因此总费用为 1c F c λμμλ=+-2 求μ使F 达到最小,先求F 的导数12()c dF c d λμμλ=-+-2 让dF d μ=0,解出2μλ=因为 22F u μμ*=∂∂=22()c λμλ*-1>0 (μ>λ) 最优服务率是μ*,当μμ*=时, 12()[c F c c λμλ*=+5例5题目：一个理发店只有一个理发师,有3个空椅供等待理发的人使用,设顾客以最简单流来到,平均每小时5人,理发师的理发时间服从负指数分布,平均每小时6人.试求L ,q L ,W ,q W解:λ=5(人/小时) , μ=5(人/小时) , k =4 , 56ρ= 用公式(7.2.10),(7.2.11),(7.2.12),(7.2.13)得到565555[16()5()]666 1.9715[1()]66L -+==- 5555(1)[16()]66 1.97 1.2251()6q L -=+=- 55555()[1()]660.101()6P -==- 5(1)z LLW P λλ==-=1.9750.9=0.438(小时)0.271qq zL W λ==(小时)6例6题目：给定一个//1/M M k 系统,具有λ=10(人/小时), μ=30（人/小时），k =2.管理者想改进服务机构.方案甲是增加等待空间,使k =3.方案乙是将平均服务率提高到μ=40(人/小时),设服务每个顾客的平均收益不变,问哪个方案获得更大收益,当λ增加到每小时30人,又将有什么结果?解:由于服务每个顾客的平均收益不变,因此服务机构单位时间的收益与单位时间内实际进入系统的平均人数k n 成正比(注意,不考虑成本)!(1)(1)1k k k k n p λρλρ+-=-=- 方案甲:k=3, λ=10, μ=3033411()310[]11()3n -=-=9.75 方案乙: k=2, λ=10, μ=40223110(1())311()4n -=-=9.5 因此扩大等待空间收益更大 当λ增加到30人/小时时,λρμ==1.这时方案甲有3330()31n =+=22.5(人/小时) 而方案乙是把μ提高到μ=40人/小时. λρμ==3040<1, k=2 2233(1())430[]31()4n -=-=22.7(人/小时) 所以当λ=30人/小时时,提高服务效益的收益比扩大等待空间的收益大7例7题目：一个大型露天矿山,考虑建设矿山卸矿场,是建一个好呢?还是建两个好.估计矿车按最简单流到达,平均每小时到达15辆,卸车时间也服从负指数分布,平均卸车时间是3分钟,每辆卡车售价8万元,建设第二个卸矿场需要投资14万元解:平均到达率 λ=15(辆/小时) 平均服务率 μ=20(辆/小时) 只建一个卸矿场的情况:1ρρ==1520=0.75 在卸矿场停留的平均矿车数0,,,,,,q q q q p p L L W W λμL λμλ=-=152015-=3(辆)建两个卸矿场的情况:ρ=0.75,2μ=2λμ=0.375 2101220[10.75(0.75)]0.452!22015P -=++=- 220.451520(0.75)0.750.120.750.871!(22015)L +=+=+=-因此建两个卸矿场可减少在卸矿场停留的矿车数为:3-0.87=2.13辆.就是相当于平均增加2.13辆矿车运矿石.而每辆卡车的价格为8万元,所以相当于增加2.13⨯8=17.04万元的设备,建第二个卸矿场的投资为14万元,所以建两个卸矿场是合适的.8例8题目：有一个///M M c ∞系统,假定每个顾客在系统停留单位时间的损失费用为c 1元,每个服务设备单位时间的单位服务率成本为c 2元.要求建立几个服务台才能使系统单位时间平均总损失费用最小解:单位时间平均损失费为F c L c c μ=+12要求使F 达到最小的正整数解c *,通常用边际分析法:找正整数c *,使其满足{()(1)()(1)F c F c F c F c ****≤+≤-由()(1)F c F c **≤+,得到122()(1)(1)c L c c c c L c c c μμ****+≤+++所以 21()(1)c L c L c c μ**-+≤ 同样,由()(1)F c F c **≤-得到21(1)()c L c L c c μ**--≥因此c *必须满足不等式21()(1)c L c L c c μ**-+≤≤(1)()L c L c **-- 取c =1,2,…,计算()L c 与(1)L c +之差,若21c c μ落在()(1)L c L c **-+,(1)()L c L c **--之间,c *就是最优解9例9题目：某公司中心实验室为各工厂服务,设做实验的人数按最简单流到来.平均每天48(人次/天),1c =6(元).作实验时间服从负指数分布,平均服务率为μ=25(人次/天),2c =4(元),求最优实验设备c *,使系统总费用为最小. 解:λ= 48(人次/天)，μ=25(人次/天)，λμ＝1.92 按///M M c ∞计算0P ,()L c 等(注意以下公式只对0 1.92cρ=<1成立). 201100(1.92)(1.92)[]!(1)!( 1.92)n P n c c ρ--==+--∑12(1.92)() 1.92(1)!( 1.92)c L c P c c +=+-- 将计算结果列成下表21c c μ=1006=16.67 所以取c *=3,总费用最小10例10题目：设有2个工人看管5台自动机,组成//2/5/5M M 系统,λ=1(次/运转小时),μ=4(次/小时),求平均停止运转机器数L 、平均等待修理数q L 以及每次出故障的平均停止运转时间W 、平均等待修理时间q W解：14λμ=，18c λμ=由（7.3.1）,(7.3.2)有 0P =0.3149 1P =0.391 2P =0.197 由（7.3.3）,(7.3.4)有 q L =0.118,L =1.094,c λ=3.906 由（7.3.5）,(7.3.6)有W =0.28(小时),q W =0.03(小时)实际上,这些数量指标有表可查例11题目：设某厂有自动车床若干台,各台的质量是相同的,连续运转时间服从负指数分布,参数为λ,工人的技术也差不多,排除故障的时间服从负指数分布,参数为μ.设λμ=0.1,有两个方案.方案一:3个工人独立地各自看管6台机器.方案二,3个工人共同看管20台机器,试比较两个方案的优劣解:方案一.因为是分别看管,可以各自独立分析,是3个//1/6M M 系统.由上面的公式可求出01P -=0.5155,c =0.5155, a =5.155Lq =0.3295, L =0.845,(1)q =0.4845,(1)r =0.0549方案二.m =20,c =3,λμ=0.1,可求得c =1.787,a =17.87,q L =0.339 L =2.126,(3)q =0.4042,(3)r =0.01695机器损失系数,修理工人损失系数都小于方案一,所以方案二较好11例12题目：某露天铁矿山,按设计配备12辆卡车参加运输作业(每辆载重160吨,售价72万元),备用车8辆,要求保证同时有12辆车参加运输的概率不低于0.995.设每辆平均连续运输时间为3个月,服从负指数分布.有两个修理队负责修理工作,修理时间服从负指数分布.平均修复时间为5天.问这个设计是否合理.解:由假设知,这是////M M c m N m +系统,m =12,1λ=3,1μ=6(月)c =2我们有m c λμ=0.3333,c μλ=36用c N ≤的公式,求N ,要求00.995Nn n p =≥∑设N =2,有Nnn p=∑=0.9474,当N =3时,有Nnn p=∑=0.9968.所以3辆备用车就能达到要求,原设计用的备用车太多当N =3时,卡车的利用律(2)q =0.793712例13题目：假定例2.1中工人的到达服从泊松分布，λ=8人/小时，试分别计算1h 内到达4，5，6，…，12个工人的概率。
第八章排队论排队（queue）是社会活动中经常遇到的现象，如顾客到商店购物，学生去图书馆借书，病人上医院看病，仪器等待维修等等，当售货员、图书管理员、医生和修理员的数量满足不了顾客或病人及时服务的需要时，就出现了排队等待的现象．由于接受服务的顾客数和服务时间的随机性，排队现象是不可避免的．当然增加服务能力可以减少排队现象，但这样势必增加投资，有时因供大于求造成资源浪费．因此，在这样一个排队系统中，作为管理人员不但需要了解排队等待服务的顾客数，等待服务时间长度，系统内服务设施的空闲率等数量指标的变化规律，而且需要在满足顾客服务基本要求的条件下，研究如何提高服务质量、降低排队系统运行成本等问题．排队论就是解决这类问题的一门科学．在排队系统中要求得到某种服务的对象统称为顾客（customer），为顾客服务者统称为服务台（service facility）．根据顾客和服务台的不同情况，组成不同的排队系统．本章研究的主要内容是排队系统的状态概率、队长、等待时间、服务时间、服务台利用效率等运行指标，以及排队系统的优化问题．第一节排队系统的基本概念一、排队系统的组成一个排队系统或称服务系统（service system），有三个基本组成部分：即输入过程（arrival process）、排队规则（queue discipline）和服务规则（service discipline）．图8-1给出了排队系统的一般结构．1．输入过程：指顾客到达排队系统的规律，可用到达时间间隔或单位时间内顾客到达数的概率分布来描述；按到达的时间间隔分有确定的时间间隔和随机的时间间隔；按顾客到达的方式有单个到达和成批到达；从顾客源总体看，分有限源总体和无限源总体．2．排队规则：排队系统一般分为等待制、损失制和混合制．(1) 等待制 顾客到达系统时，如果服务台没有空闲，则顾客排队等候服务．等待制服务的方式有：① 先到先服务（first come first service ，FCFS ）：按顾客到达先后给予服务，这是最常见的服务规则．② 后到先服务（last come first service ，LCFS ）：如情报收集中最后到达的信息最有价值，往往最先采用．③ 优先权服务（priority ，PR ）：如医院对危重病人给予优先治疗．④ 随机服务（service in random order ，SIRO ）：排队系统随机抽取等待服务的顾客．(2) 损失制 顾客到达系统时，如果服务台没有空闲，则顾客离去，另求服务．如没有足够医生或医疗器械救治急诊患者，医院药物、卫生材料暂缺等．(3) 混合制 它是介于等待制和损失制之间的形式．方式有：① 队伍长度有限，当队伍的长度小于N 时，新到顾客就排队等待；当队伍长度为N 时，新来顾客离去．如患者住院所需要的病床数有限就属此类．② 等待时间有限，新到顾客排队等候服务，一段时间后仍未得到服务，顾客离去．例如医院血库的血浆、生物制剂等．③ 逗留时间（等待时间与服务时间之和）有限，顾客在系统中的逗留时间不得超过确定的时间．例如药品的有效期．3．服务机构：指排队系统中服务台的个数、排列及服务方式．排队系统中服务台的个数可以是一个或多个．多个服务台可以是串联或并联．排列结构大体有：(1) 单服务台、单列图8-2输出(2) 多服务台、单队列（多队列）(3) 多服务台串列(4) 多服务台混合医院里的CT室就是(1)的例子，口腔科、理疗室就是(2)的例子，先挂号候诊再住院手术就是(3)或(4)的例子．服务方式上有单个服务，也有成批服务的，如医院里的上下电梯．二、排队系统的评价指标排队论研究的问题，可以分成两大类，第一类问题是在服务设施设置之前，根据顾客输入过程与服务过程的要求，结合对系统的一定数量指标与服务过程要求（如规定服务质量的必需水平），确定服务设施（如诊断室、检验科、供应中心等等）的图8-3图8-4图8-5…图8-6规模；第二类问题是对已有的服务系统施以最优控制，改进和提高排队系统工作效率．排队系统的数量指标主要有：1．单位时间内到达的顾客数的期望值，即单位时间内的平均到达率，记作λ．而λ1表示相邻两个顾客到达的平均间隔时间．2．单位时间内服务的顾客数的期望值，即单位时间内顾客的平均离去率，记作μ．同样，μ1表示每个顾客的平均服务时间．3．在时刻t时排队系统中恰有n个顾客的概率()tPn ，显然()tP为系统空闲率．4．系统内的平均顾客数称为队长（queue length），记作L．5．系统内排队等待服务的平均顾客数称为等待队长，记作qL．6．顾客从进入系统到接受完服务后离开系统的平均时间称为平均逗留时间，记作W．7．顾客在系统内排队等待服务的平均时间称为平均等待时间(waiting time)，记作qW．三、排队模型的符号表示由于排队系统的特征可以有许许多多的组合，从而形成不同的排队模型．本章采用A/B/C/m/N形式表示不同排队模型．其中：A——顾客到达间隔时间概率分布B——服务时间的概率分布C——服务台数m——顾客源总数N——系统内顾客的容量例如：M/M/ 1 / ∞/ 12排队模型的特点是：顾客到达间隔时间和服务时间均服从负指数分布（M指负指数分布，具有无记忆性，即Markov性），单服务台，顾客来源总体数无限，系统的顾客容量为12．四、排队系统的常见分布顾客到达和离开分别构成排队系统的输入与输出过程流．到达分布和离开分布确定了到达系统和离开系统的顾客数这两个随机变量的分布．求解排队系统有关数量指标问题，首先要确定顾客到达流的概率分布，即在一定的时间间隔内来n 个顾客的概率是多大．其次是要确定顾客离开流的概率分布，即在一定的时间内服务完m 个顾客的概率是多大．实际问题研究中，可根据原始资料测算顾客在单位时间平均到达流的经验分布，然后按照统计学的方法（例如，2χ检验法）确定资料适合于哪种理论分布，并估计理论分布的参数值，这是确定排队模型的前提．1．泊松分布（Poisson distribution ）在排队论中，最基本的排队模型是在给定时间内到达系统的顾客数服从泊松分布，即顾客到达流是泊松流（也称最简单流）．它具有如下性质：(1) 平稳性：在时间+t △t 内，到达n 个顾客的概率只与△t 和n 的大小有关，而与时刻起点t 无关．(2) 无后效性：在时间+t △t 内到达n 个顾客的概率与起始时刻之前到达多少个顾客无关．(3) 普通性：对于充分小的时间间隔△t ，在时间+t △t 内最多有一个顾客到达系统．即在时间+t △t 内有2个或2个以上顾客到达的概率极小，有()0lim2=∆+∑∞=→∆t t P n nt可以证明，在长为t 的时间内到达n 个顾客的概率为：()(),2,1,00!)(=>=-n t e n t t P tn n λλ （8-1）当1=t 时，即单位时间内到达n 个顾客的概率为：()λλ-==e n P P nn n !1其中λ为单位时间内到达系统的顾客的期望值． 2．负指数分布(negative exponential distribution )理论上可以证明若顾客在单位时间内到达系统的个数X 是服从参数为λ的泊松分布，则顾客到达系统的间隔时间T 服从参数为λ的负指数分布，反之亦然．即同一随机过程可从两种不同的角度用两种分布来描述．负指数分布的概率密度为：)0()(>=-t e t f tT λλ间隔时间T 的期望值。
