随机运筹学-排 队 论

运筹帷幄之中决胜千里之外运筹学课件排队论QueueingTheory第1页基本模型M/M/1模型M/M/c模型其他模型结束语排队论2基本的排队模型基本组成概念与记号指数分布和生灭过程3基本组成顾客源排队结构服务机构排队系统顾客到来服务完离开排队系统的三个基本组成部分.输入过程(顾客按照怎样的规律到达);排队规则(顾客按照一定规则排队等待服务);服务机构(服务机构的设置,服务台的数量,服务的方式,服务时间分布等)排队规则服务规则4基本排队模型－输入过程顾客源

有限/无限达到方式单个成批相继到达时间间隔确定型随机型相继到达顾客的关系相互独立相互关联输入过程平稳的（齐次的：相继到达的间隔时间分布和所含参数与时间无关）非平稳的输入过程：顾客按怎样规律到达、顾客源情况如何5基本排队模型－排队规则/队列排队规则/队列损失制/即时制（服务台都正被占用，顾客随即离开）等待制先到先服务（FCFS）；后到先服务；随机服务；有优先权的服务系统容量有限/无限队列数目单列/多列6基本排队模型－服务机构服务设施，服务渠道与服务台服务台数量:一个/多个（串联/并联）单队——单台单队——多台（并列）单队——多台（串列）多队——多台（串列）多队——多台（并列）多队——多台（混合）7………服务排队到达离开离开………………离开…………………………离开离开单—单：单—多(并)：单—多(串)：多—多(并)：多—多(串)：多—多(混)：8基本排队模型－服务机构服务方式:单个/成批服务时间:确定型/随机型输入过程、服务时间二者至少一个是随机型的服务时间分布:平稳的，方差与期望不受时间影响9基本排队模型—分类

1953年D.G.Kendall提出：X/Y/Z

其中X:相继到达间隔时间的分布（输入过程）

Y:服务时间的分布

Z:服务台数目

1971年，排队论符号标准化会议：X/Y/Z/A/B/C

A：系统容量限制

B：顾客源数目

C：服务规则（FCFS,LCFS等等）

X、Y表示为：

M:负指数分布(Markov)D:确定型(Deterministic)

Ek:k级Erlang

分布

G:一般(General)服务时间分布

M/M/1/

/

/FCFS

M/M/1/

若略去后三项，指X/Y/Z/

/

/FCFS

10基本排队模型—求解常用数量指标四项主要性能指标（都是指期望值）队长：系统中的顾客数，Ls

排队长：系统中排队等待的顾客数，Lq

逗留时间：一个顾客在系统中的停留时间，Ws

等待时间：一个顾客在系统中排队等待的时间，Wq

Ls=Lq+[正在接受服务的顾客数]

Ws=Wq+[服务时间]

11常用数量指标其他常用指标（都是指期望值）

：平均到达率(单位时间平均达到顾客数): 平均服务率(单位时间平均服务顾客数)1/: 平均到达时间间隔1/: 平均服务时间间隔

： 服务强度，或称使用因子,/(s)忙期：服务机构连续繁忙的时间长度损失率：单位时间顾客被拒绝而使企业受到的损失基本排队模型—求解12系统：排队机构系统状态：系统中的顾客数状态转移：由于顾客到达或离去系统的状态发生改变系统状态为n

：系统中有n个顾客

Pn(t)

：在时刻t,系统状态为n的概率

N(t)

：在时刻t排队系统中顾客的数量，则

Pi(t)=P{N(t)=i}稳态：limt→∞Pn(t)=Pn（若存在的话）基本排队模型－系统状态统计平衡状态的解13N（t）

:时间区间[0,t)内到达的顾客数（t>0）Pn(t1,t2)：[t1,t2)内有n个顾客到达的概率，即3o普通性—

对充分小的⊿t,在[t,t+⊿t)内有2个或以上顾客到达的概率极小，可以忽略，即普阿松流：当Pn(t1,t2)满足下列条件时，顾客到达形成的流1o无后效性—不重叠的时间区间内顾客到达数相互独立2o平稳性（均匀性）—对充分小的⊿t,在[t,t+⊿t)内有一个顾客到达的概率与t无关，约与⊿t成正比，即概率强度：单位时间有1个顾客到达的概率到达间隔时间的分布—普阿松流14到达间隔时间的分布—普阿松流在上述条件下，研究顾客到达数n的概率分布由2o，总可以取时间由0时刻算起，简记为：由2o、3o可得在[t,t+⊿t)内没有顾客到达的概率建立微分方程。将[0,t)[t,t+△t)[0,t+△t)个数概率个数概率个数概率nn-1n-2n-3…0Pn(t)Pn-1(t)Pn-2(t)Pn-3(t)…P0(t)0123…n1-

△t+o(△t)

△t

o(△t)nnnn…nPn(t)(1-

△t+o(△t))Pn-1(t)△t

o(△t)15由上表可知即，又数学期望方差到达间隔时间的分布—普阿松流16负指数分布密度函数数学期望方差随机变量

T分布函数

fT(t)t标准差17负指数分布性质1

fT(t)tttfT(t)是一个严格下降函数18负指数分布性质2无记忆性不管多长时间(s)已经过去，逗留时间的概率分布与下一个事件的相同.19负指数分布性质3当输入过程是普阿松流时，顾客相继到达的间隔时间服从负指数分布。相继到达的间隔时间是独立且为负指数分布，与输入过程为普阿松流是等价的，所以都用M表示。20负指数分布性质4指数分布Poisson分布服务时间的概率在t时间内已经服务n个顾客的概率1/:平均服务时间平均服务率=21服务时间

的分布密度函数有时，忙期相继离开系统的两顾客的间隔时间也服从负指数分布分布函数

: 平均服务率(单位时间平均服务顾客数)1/: 平均服务时间间隔22M/M/1//或

M/M/1模型一个服务台,到达率和服务率

都服从指数分布。状态转移关系图平衡方程设

=/,当<1时，系统存在稳态。由∑Pi=1得23M/M/1//或

M/M/1模型

<1(否则队列将排至无限远)24M/M/1//或

M/M/1模型系统中队长大于k的概率：Little公式：25M/M/1举例例1某诊室只有一名医生，每名病人诊治时间服从指数分布。平均时间15分钟。病人到达按普阿松流，平均3人/小时。求（1）

=？=？=？（2）Ls,Lq,Ws,Wq？（3）若要求逗留时间不超过半小时，诊治时间应减少多少？（4）若使候诊病人90%有座位，应有多少座位？解（1）

=3（人/小时）=4（人/小时）=3/4

（2）Ls=/(-)=3;Lq=Ls=2.25;Ws=1/(-)=1;Wq=/Ws=3/4

（3）若要求Ws≤0.5,则1/(-)≤0.5,

不变，所以≥5

（4）设有x座位，加上诊室1个座位，共x+1个，求x，使得P{N≤x+1}≥90%，即P{N>x+1}≤0.1，∴

x+2≤0.1,解得x≥626M/M/1举例例2某音乐厅售票处营业时间为8:00-16:00，顾客到达为普阿松流，平均到达间隔时间为2.5分钟。窗口为每位顾客服务，平均需1.5分钟。求（1）

=？=？=？（2）Ls,Lq,Ws,Wq？（3）顾客不需等待的概率；（4）系统内顾客超过4个的概率；（5）系统内没有顾客的时间（小时）；（6）若顾客逗留时间超过半小时，则增加一个窗口，此时顾客到达率是原来的几倍？解（1）

=60/2.5=24（人/小时）=60/1.5=40（人/小时）=0.6

（2）Ls=/(-)=1.5;Lq=Ls=0.9;Ws=1/(-)=1/16;Wq=/Ws=0.0375

（3）P0=1-=0.4

（4）1-∑4n=0Pn=1-P0∑4n=0

n=

5=0.078

（5）8×P0=3.2（小时）（6）Ws≥0.5,则1/(-)≥0.5,

不变，变。所以1/(-1)≥0.5

，≤38（人/小时），

1/=1.58(倍)27M/M/1举例例3某街口有一电话亭，在步行距离为4分钟的对方有另一电话亭。已知每次平均通话时间为3分钟，顾客到达为每小时10人的普阿松流。若另一人去其中一个电话亭打电话，达到时正有一人通话，且有一人等待，问该人是原地等待还是去另一电话亭？解

=10，=60/3=20，=0.5

Wq=/(-)=1/20=3(分钟)

去另一电话亭需3+4=7(分钟)

原地等待：3+3=6(分钟)

故原地等待问题：若每次通话为4分钟呢？

=10，=60/4=15，=2/3

Wq=/(-)=2/15=8(分钟)

去另一电话亭需8+4=12(分钟)

原地等待：4+4=8(分钟)

故原地等待28M/M/1/N/

若到了最大系统容量，新顾客将不能进入系统.N=1为即时制，N=∞为容量无限制单服务台，最大容量N状态转移关系图平衡方程设

=/,由∑Pi=1得29M/M/1/N/

30M/M/1/N/

损失率：当系统中有N个顾客时，新来的顾客损失掉.有效到达率：PN称为损失率31M/M/1/N/

举例例4自行车修理部只有一名工人，修理部最大容量为7辆车，平均每小时有3辆车来修理，平均修理一辆车需15分钟。求

Ls,Lq,Ws,Wq？

解N=7，

=3,=60/15=4,=3/4P0=(1-)/(1-

N+1)=0.2778

e=

(1-P0)=2.8887

Ls=

/(1-)-(N+1)N+1/(1-N+1)=2.11

Lq=Ls-(1-P0)=1.39

Ws=Ls/

e=0.37(小时);Wq=Ws-1/=0.48(小时);

32M/M/1/N/

举例例5单人理发店有六个椅子接待人们排队等待理发。当6个椅子都坐满时，后来到的顾客不进店就离开。顾客平均到达率为3人/小时，理发需时平均15分钟。则（1）N=？

=？=？（2）某顾客一到达就理发的概率？（3）求有效到达率；（4）求需要等待的顾客数的期望值；（5）求一顾客在理发馆内逗留的期望时间（6）在可能到来的顾客中有百分之几不等待就离开？解（1）N=7，

=3（人/小时）,=60/15=4（人/小时）,=3/4

（2）P0=(1-)/(1-

N+1)=0.2778

（3）

e=

(1-P0)=2.89(人/小时)

（4）Ls=

/(1-)-(N+1)N+1/(1-N+1)=2.11;Lq=Ls-(1-P0)=1.39;

（5）Ws=Ls/

e=0.73(小时)=43.8(分钟);

（6）P7=

N(1-)

/(1-N+1)=3.7%33M/M/1/N/

举例例6某理发店只有一位理发师，连同理发椅共5个椅子。若顾客到达时无空闲椅子则离去。设顾客到达服从普阿松流，平均每小时5人，理发时间服从负指数分布，平均10分钟/人，求（1）Ls,Lq,Ws,Wq？（2）流去顾客占全部顾客的比例。

解（1）N=5，

=5,=60/10=6,=5/6P0=(1-)/(1-

N+1)=0.25

e=

(1-P0)=4.5(人/小时)

Ls=

/(1-)-(N+1)N+1/(1-N+1)=1.98;

Lq=Ls-(1-P0)=1.23;

Ws=Ls/

e=0.44(小时);Wq=Ws-1/=0.27(小时);

（2）PN=

N(1-)

/(1-N+1)=10%34M/M/1/N/

举例例7开洗车场需先确定提供等待汽车使用的场地的大小。设汽车到达服从普阿松分布，平均每4分钟1辆，洗车时间服从负指数分布，平均每3分钟1辆。若场地可容纳(a)1辆；(b)3辆；(c)5辆，求由于场地不足而离去汽车占到达汽车的比例。

解

=15,=20,=3/4P0=(1-)/(1-

N+1)(a)N=1,P1=42.8%(b)N=3,P3=15.5%(c)N=5,P5=7.2%

35M/M/1/

/m顾客源有限（m）情况.例一个工人照管m台机器，有机器出故障则负责修理。设每台机器出故障的强度（概率）为

若只有一台机器，则工人修理机器的概率为

若有m台机器，则工人修理机器的概率为m

设某时刻m台机器中有k台出现故障，m-k台正常工作，此时工人需修理机器的概率为(m-k)

设工人修复机器的强度为

，则36状态转移关系图平衡方程由∑Pi=1M/M/1/

/m37

M/M/1/

/m正常运转的平均台数38例8某车间有5台机器，每台机器的连续运转时间服从负指数分布，平均连续运转时间15分钟，有1个修理工，每次修理时间服从负指数分布，平均每次12分钟。求（1）修理工空闲的概率；（2）5台机器都出故障的概率；（3）出故障的平均台数；（4）等待修理的平均台数；（5）平均停工时间；（6）平均等待修理时间；（7）评价这些结果解（1）P0=0.0073

（2）P5=0.287

（3）Ls=3.76;

（4）Lq=2.77;

（5）Ws=46(分钟);

（6）Pq

=34(分钟);

（7）机器停工时间过长，修理工几乎没有空闲时间，应当提高服务率，减少修理时间或增加修理工人。

M/M/1/

/m举例39标准的

M/M/c从状态n到n+1的转移概率仍为.从状态n到n-1的转移概率需分情况讨论.系统中有n个顾客正在接受服务，有n个服务台在工作，总效率是一个服务台的n倍，整个服务机构的平均服务率为c（n≥c);n

(n≤c).设

=/(c),只有<1才不会排成无限的队列称为服务强度，或服务机构的平均利用率单队并列多服务台。除了服务台为c个外，M/M/c的假设与M/M/1均相同同时假设各服务台工作相互独立，平均服务率相同，为

系统的可能状态为{0,1,2,…}40标准的

M/M/c(1≤n<c)(n≥c)

P1=P0(n+1)Pn+1+Pn-1=(+n)Pn

(1≤n<c)cPn+1+Pn-1=(+c)Pn

(n≥c)Pi=1<1状态转移关系图平衡方程41标准的M/M/c42M/M/c举例例9单售票所有三个窗口，顾客的到达率服从普阿松过程，平均到达率每分钟0.9人，服务时间服从负指数分布，平均服务率每分钟0.4人。现设顾客到达后排成一队，依次向空闲的窗口购票，如图。解c=3，

=0.9,=0.4,/=2.25，

=/(c)=2.25/3<1

（1）P0=0.0748

（2）

Lq=1.70；Ls=3.95;

（3）Wq=1.70/0.9=1.89(分钟);Ws=4.39(分钟);

（4）(系统中已有3人);P(n≥3)=∑n=c∞Pn=0.57求（1）整个售票所空闲概率；（2）平均队长；（3）平均等待时间和逗留时间；（4）顾客到达后必须等待的概率.43M/M/c与M/M/1比较上例中，若顾客到达后在每个窗口前各站一排，且坚决不换，其他条件不变，这就形成了三个队列，如图。M/M/3与M/M/1各项指标比较结果如下表M/M/3M/M/1P00.07480.25(每个子系统)等待P(n≥3)0.570.75Lq1.702.25(每个子系统)Ls3.959.00(整个系统)Ws4.3910(分钟)Wq1.897.5(分钟)44例题例10汽车按普阿松分布到达高速公路收费口，平均每小时90辆，每辆车通过收费口时间平均需35秒（服从负指数分布），司机抱怨等待时间太长，管理部门拟采用新装置，使通过时间缩短为30秒，但条件是原来平均等待车辆超过6辆，且新装置利用率不低于75%才采用。问上述条件能否采用？解c=1

旧装置：

=90,=3600/35,=/=7/8，

Lq=/(-)=6.12>6,

新装置：

=3600/30,=/=3/4，

P0=1-=1-3/4=0.75;

故可采用。

45考研真题例1（15分）某机关接待室接待人员每天工作10小时。来往人员的到来服从普阿松分布，每天平均有90人到来，接待时间服从负指数分布，平均速度10人/小时（平均每人6分钟）。试求排队等待接待的平均人数；等待接待的多余2人的概率；如果使等待接待的人平均为2人，接待速度应提高多少？解M/M/1模型

=90/10(人/小时),=10,=/=0.9，

P0=1-=0.1;

Lq=/(-)=8.1,

P(n>2)=1-(P0+P1+P2)=0.729;2=Lq=/(-)-/=9/(-9)-9/

解得

=12.3，

接待速度应提高：12.3-10=2.3

46考研真题例2（15分）为开办一个小型理发店，目前只招聘了一个服务员，需要决定等待理发的顾客的位子应设立多少。假设需要理发的顾客到达的规律服从普阿松流，平均每4分钟来一个，而理发的时间服从负指数分布，平均3分钟一个人。如果要求理发的顾客因没有等待的位子而转向其他理发店的人数占理发的人数的7%，应该安放几个供顾客等待的位子？解M/M/1模型

=1/4,=1/3,=/=3/4，

Ls=

/(1-)-(N+1)N+1/(1-N+1)

Lq=Ls-(1-P0)=Ls-[1-(1-)/(1-

N+1),

由

Lq/Ls=7%