(精品)排队论课件.ppt

运筹学课程软件第六章排队论基本概念基本概念 单服务台负指数单服务台负指数多服务台负指数多服务台负指数损失制系统模型损失制系统模型表达间隔表达间隔 本章要点本章要点 4/4/20234/4/20231 1太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页本章要点掌握排队系统的特征；掌握排队系统的一些基本概念；会解决负指数分布的排队系统；能够应用排队论知识解决一些实际问题4/4/20234/4/20232 2太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页.基本概念排队论：研究排队系统的概率特性，从而确定排队系统的最优设计及现有排队系统的最优控制的一门学科排队系统的特征排队系统的特征 研究内容研究内容 基本组成部分基本组成部分 排队系统的模型排队系统的模型 4/4/20234/4/20233 3太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页.排队系统的特征.“顾客”：指请求服务的人或物；.“服务台”：指为顾客服务的人或物；.在排队系统中，顾客相继到来的时间间隔，以及为每位顾客服务所需要的时间，一般情况下，往往都是无法确切知道的，因此随机性是排队系统的一个重要特征正因如此，排队系统也称做随机服务系统，排队论也可称为随机服务系统理论4/4/20234/4/20234 4太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页.研究内容.排队系统的数量指标：即研究与排队现象有关的几个数量指标的概率规律性他们是：(1).队长：在排队系统中，顾客排队等待服务的队列长短由于队长的随机性，因此要确定队长属于何种分布(2).等待与逗留时间分布：等待时间也是一随机变量(3).忙期与闲期分布：忙期从顾客来到空闲的服务台接受服务起，到服务台再次变成空闲为止的这段时间即服务台连续服务的时间闲期服务台连续保持空闲的时间长度下一页4/4/20234/4/20235 5太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页.排队系统的优化问题：在研究了排队系统的一些数量指标的概率规律后，可以在此基础上进一步研究排队系统的最优化问题最优化问题一般设计两种类型：一类是研究排队系统的最优设计问题，它属于静态最优化问题例如，工厂仓库的大小，医院床位数量的多少，机场跑道的数量等等另一类是研究排队系统的最优控制问题，它属于动态最优化问题例如：工具室是否增加分发工人等4/4/20234/4/20236 6太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页.排队系统的基本组成部分一般说来，排队系统都有三个组成部分，即：输入过程，服务规则和服务台.输入过程：指要求服务的顾客是按怎样的规律来到排队系统的一个输入过程可以用顾客总体数，顾客来到方式和顾客流的概率分布这三个方面来描述.服务规则：指顾客来到排队系统后，怎样接受服务的规则一般分为损失制，等待制（包括先到先服务，后到先服务，随机服务，优先权服务等）和混合制（即等待与损失制相结合的一种服务规则，例如，队长有限制，排队等待时间有限制等）下一页4/4/20234/4/20237 7太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页.服务台情况：服务台数量及布置形式（既指单服务台还是多服务台，是串列还是并列等），某一时刻接受服务的顾客数（即单个顾客服务还是成批顾客服务）和服务时间分布4/4/20234/4/20238 8太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页.排队系统的模型到达过程服务过程服务台个数系统客量顾客源个数服务规律服务结构（注：排队系统的数学模型若写成的形式，则表示系统客量无限，顾客源无限，先来先服务）4/4/20234/4/20239 9太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页.到达间隔的分布与服务时间的分布泊松（泊松（oissonoisson）分布分布负指数分布负指数分布rlangrlang分布分布4/4/20234/4/20231010太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页下一页.泊松分布泊松分布具有如下一些性质：.平稳性：指在时间区段之内，来到系统的任何数量 时间的概率，只于t的长度有关，而与t在时间轴上的位置无关即任意给定一个时间t，在tt时间内，到达k个顾客的概率与起始时刻t无关，而只与t和k的大小有关.无后效性：在两个互不相交的时间段t1和t2内，来到系统的顾客数是相互独立的，即每个顾客来到系统的时刻互不相关 4/4/20234/4/20231111太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页下一页.普通性：即在充分小的间隔时间内，或者说在同一瞬间内，同时有两个或两个以上顾客来到系统的概率比来到一个顾客的概率小到可以忽略不计.有限性：在任意有限的时间区间内，到达有限个顾客概率为注：当顾客的到达满足上述四条性质时，我们说顾客的到达形成Poisson流4/4/20234/4/20231212太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页下一页由以上性质，我们来求在，t时间内到达n个顾客的概率为此：设(t)(0,t)内到达的顾客数(t0)Pn(t1,t2)(t1,t2)时间内有n个顾客到达的概率n(t1,t2)（t）（t）n）（t2t1，n）单位时间内到达的顾客数的平均值则由性质可知，对充分小的t有：P1（t，tt）*to（t）注：o（t）表示t是，比t高阶的无穷小4/4/20234/4/20231313太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页下一页下面求N(t)的概率分布（即Pn(t)=P(N(t)=n):证，考虑：将分成当t很小时有：4/4/20234/4/20231414太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页下一页整理得到：4/4/20234/4/20231515太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页下一页令t，则由上式可得：（n=1）当令t，则有：4/4/20234/4/20231616太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页下一页即：得：又4/4/20234/4/20231717太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页（，n=0,1,）由此可得：4/4/20234/4/20231818太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页下一页.负指数分布随机变量T服从负指数分布是指T的密度函数为：或分布函数为：且，4/4/20234/4/20231919太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页负指数分布的性质：（）无后效性（无证忆性或马尔可夫性）（）当输入过程是Poisson流时，顾客相继到达的间隔时间服从负指数分布4/4/20234/4/20232020太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页Erlang分布设是相互独立的随机变量，且服从相同参数的负指数分布，则随机变量的概率密度为：则称T服从k阶Erlang分布，且4/4/20234/4/20232121太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页单服务台负指数分布排队系统的分析M|M|1M|M|1模型模型M|M|1|M|M|1|m|m模型模型M|M|1|N|M|M|1|N|模型模型4/4/20234/4/20232222太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页下一页.1 M|M|1模型该模型可解释为：（）一定时间内到达的顾客数服从Poisson分布或顾客相继到达的时间间隔服从负指数分布；（）服务时间服从负指数分布；（）只有一个服务台4/4/20234/4/20232323太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页下一页下面求t时刻系统有n个顾客的概率，即求设系统的平均到达率为,平均服务率为,则：=4/4/20234/4/20232424太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页下一页将含有合并为一项，则由上式得：令，则：n=0时,有：(n=1,2,)（）4/4/20234/4/20232525太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页下一页令，则由上式得：（）4/4/20234/4/20232626太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页下一页 由于上述微分方程（）（）中的瞬态解（即 在t时刻的解）很难求得，因此下面求其瞬态解（即与t无关的解）若 与t无关，即 证则由(1),(2)得：（）（）由（）得：由（）得：4/4/20234/4/20232727太原理工大学太原理工大学运 筹 学 课 程 软 件回目录页下一页同理：(n=1，)即故由此可得：（，n=1,2,)系统的平均队长：系统的平均等待队长：4/4/20234/4/20232828太原理工大学太原理工大学回目录页下一页系统空闲的概率：系统忙期的概率：每一顾客在系统中的平均逗留时间（指顾客来到系统的平均间隔时间和顾客平均逗留数的乘积）：每一顾客在系统中的平均等待时间（指顾客来系统的平均间隔时间和顾客平均等待数的乘积）：运 筹 学 课 程 软 件4/4/20234/4/20232929太原理工大学太原理工大学回目录页下一页，系统有关运行指标计算如下：（）系统空闲的概率：（）系统忙期的概率：（）平均队长：（）平均等待队长：（）平均逗留时间：（）平均等待时间：例：某超市，顾客按Poisson流来到唯一的受银已知平均每小时来到人，收款时间服从负指数分布，平均每个顾客需.分钟，试求该超市收银台的有关运行指标解：此系统为等待制系统，且，运 筹 学 课 程 软 件4/4/20234/4/20233030太原理工大学太原理工大学回目录页下一页例：某机关接待室只有一位接待人员，每天工作小时，来访人员和接待时间都是随机的若来访人员按Poisson流输入，且人小时，接待时间服从负指数分布，且现要求知道：（）来访者需要在接待室逗留多久等待多久（）排队数与接待的平均人数（）若希望来访者逗留时间减少一半，则接待人数应提高多少？解：（）（）运 筹 学 课 程 软 件4/4/20234/4/20233131太原理工大学太原理工大学回目录页即每小时若平均接待人，可使来访者平均逗留时间比原来减少一半运 筹 学 课 程 软 件4/4/20234/4/20233232太原理工大学太原理工大学回目录页下一页.2模型该模型指：到达过程为Poisson流，服务时间服从负指数分布，一个服务台，系统容量为，服务源无限，其状态图如下：n+1N-1Nn-1n运 筹 学 课 程 软 件4/4/20234/4/20233333太原理工大学太原理工大学回目录页下一页由此可得微分方程：(n=1,2,N-1)由此及可得：由此可得各种指标如下：系统的平均队长：(n=1,2,N)运 筹 学 课 程 软 件4/4/20234/4/20233434太原理工大学太原理工大学回目录页系统的平均等待队长：平均逗留时间：平均等待时间：顾客拒绝排队的概率：被拒绝排队的顾客平均数：系统有空时的到达率为（平均到达率），当n=N时，有效到达率为：，且运 筹 学 课 程 软 件4/4/20234/4/20233535太原理工大学太原理工大学回目录页下一页.m(即m/m）模型该系统的顾客源为m，系统的有效到达率为：其中指顾客的到达率（在机器维修问题中，表示每台机器单位运转时间内发生故障的平均次数）状态转移图如下：n-1nn+1n+1n+1运 筹 学 课 程 软 件4/4/20234/4/20233636太原理工大学太原理工大学回目录页下一页由上述转移图可得下列差分方程：(n=1,2,m-1)（）（）（）（）运 筹 学 课 程 软 件4/4/20234/4/20233737太原理工大学太原理工大学回目录页下一页例单人理发馆有六个椅子接待人们排队等待理发当个椅子都坐满时，后到的顾客不进店就离开顾客平均到达率为人小时，理发需时平均分钟则N为系统中最大的顾客数，人小时，人小时（）求某顾客一到达就能理发的概率这种情形相当于理发馆内没有顾客，所求概率（）求需要等待的顾客数的期望值运 筹 学 课 程 软 件4/4/20234/4/20233838太原理工大学太原理工大学回目录页下一页（）求有效到达率（）求一顾客在理发馆内逗留的期望时间（）在可能到来的顾客中有白分之几不等待就离开这就是求系统中有个顾客的概率，这也是理发馆的损失率，先比较队长为有限和无限的两种结果=3=3人人/小小时时=4=4人人/小小时时可能到来的可能到来的顾顾客中客中有百分之几离开有百分之几离开有限有限队长队长N=7N=72.112.111.391.390.730.730.480.480.270.278 83.7%3.7%无限无限队长队长3 32.252.251.01.00.750.750.250.250 0运 筹 学 课 程 软 件4/4/20234/4/20233939太原理工大学太原理工大学回目录页下一页例某车间有台机器，每台机器的连续运转时间服从负指数分布，平均连续运转时间分钟，有一个修理工，每次修理时间服从负指数分布，平均每次分钟求：（）修理工空闲的概率；（）五台机器都出故障的概率；（）出故障的平均台数；（）等待修理的平均台数；（）平均停工时间；（）平均等待修理时间；（）评价这些结果解：（）运 筹 学 课 程 软 件4/4/20234/4/20234040太原理工大学太原理工大学回目录页（）（）机器停工时间过长，修理工几乎没有空闲时间，应当提高服务率减少修理时间或增加修理工人（）（）（）（）运 筹 学 课 程 软 件4/4/20234/4/20234141太原理工大学太原理工大学回目录页.多服务台负指数分布排队系统的分析M|M|C|M|M|C|模型模型M|M|C|N|M|M|C|N|模型模型M|M|C|M|M|C|m|m 模型模型运 筹 学 课 程 软 件4/4/20234/4/20234242太原理工大学太原理工大学回目录页下一页.M|M|C模型该模型为：到达过程为Poisson流，服务时间服从负指数分布，有个服务台，系统容量无限，顾客源无限，先来先服务等设平均到达率为，各服务台的平均服务率相同，且为，则整个系统的平均服务率为c （当nc）或n（当nc）该系统的状态转移图如下：n-1n-1nn+1n+1n运 筹 学 课 程 软 件4/4/20234/4/20234343太原理工大学太原理工大学回目录页下一页由此可得下列差分方程：解之得：运 筹 学 课 程 软 件4/4/20234/4/20234444太原理工大学太原理工大学回目录页下一页系统的运行指标如下：平均队长：平均等待队长：平均逗留时间：平均等待时间：运 筹 学 课 程 软 件4/4/20234/4/20234545太原理工大学太原理工大学回目录页下一页例某兽票所有三个窗口，顾客的到达服从普阿松过程，平均到达率每分钟（人），服务（售票）时间服从负指数分布，平均服务率每分钟（人）现设顾客到达后排成一队，依次向空闲的窗口购票如下图所示，这就是一个M|M|c型的系统，其中符合要求的条件，代入公式得：窗口(1)窗口(1)窗口(2)窗口(3)窗口(2)窗口(3)=4=4=4=4=4=40.9=0.9=0.3=0.3=0.3运 筹 学 课 程 软 件4/4/20234/4/20234646太原理工大学太原理工大学回目录页下一页整个售票所空闲概率：平均队长：平均等待时间和逗留时间：顾客到达后必须等待（即系统中顾客数已有人即各服务台都没有空闲）的概率：运 筹 学 课 程 软 件4/4/20234/4/20234747太原理工大学太原理工大学回目录页下一页例：某汽油加油站共有两个加油泵已知待加油的汽车按Poisson流来到加油站，平均每小时来到辆，加油时间服从负指数分布，平均每辆加油时间为分钟试求（）加油站空闲的概率？（）在加油站逗留及等待加油的汽车数各为多少？（）平均每辆汽车在加油站逗留时间为多少？解：此加油站为M/M/2等待制系统，且，（）加油站空闲的概率：运 筹 学 课 程 软 件4/4/20234/4/20234848太原理工大学太原理工大学回目录页（）（）运 筹 学 课 程 软 件4/4/20234/4/20234949太原理工大学太原理工大学回目录页下一页.M|M|C|N|模型系统容量为，且当时系统为损失制系统其状态转移图如下：c-1n-1nn+12cNN-1n+1nn-1运 筹 学 课 程 软 件4/4/20234/4/20235050太原理工大学太原理工大学回目录页下一页(n c)由此可得下列微分方程：由此可求解 和 如下：(n c)(n c)(n c)运 筹 学 课 程 软 件4/4/20234/4/20235151太原理工大学太原理工大学回目录页下一页系统的运行指标如下：运 筹 学 课 程 软 件4/4/20234/4/20235252太原理工大学太原理工大学(1)(1)(2)(2)(3)(3)(4)(4)(5)(5)(6)(6)(7)(7)(8)(8)1.2 1.2 10101.44 1.44 1.73 1.73 2.07 2.07 2.49 2.49 2.99 2.99 3.58 3.58 4.30 4.30 1 12 26 624241201207207205.04 5.04 4.03 4.03 121272722882888648642.07 2.07 4.15 4.15 7.11 7.11 1.07 1.07 131385853733731.24 1.24 3.31 3.31 7.46 7.46 1.45 1.45 2.52 2.52 0.920.920.850.850.770.770.700.700.630.630.560.560.490.490.420.420.080.080.150.150.230.230.300.300.370.370.440.440.510.510.580.580.920.921.831.832.742.743.623.624.484.485.335.336.146.146.936.93回目录页下一页例：在某风景区准备建造旅馆，顾客到达为普阿松流，每天平均到（）人，顾客平均逗留时间为（）天，试就该旅馆在具有（c)，个房间的条件下，分别计算每天客房平均占用数 及满员概率 .这是即时式，因为在客房满员条件下，顾客显然不能排队等待计算过程如下表格进行：运 筹 学 课 程 软 件4/4/20234/4/20235353太原理工大学太原理工大学回目录页第（）栏：（）（）第（）栏：第（）栏各数累加第（）栏：（）（）得满员概率，注意第（）（）两栏的c就是同行的n,具体意义是：当c=1旅馆只有一个房间，满员（旅客被拒绝）概率0.92 当c=5旅馆备有个房间，满员（旅客被拒绝）概率0.63 当c=8旅馆备有个房间，埋怨（旅客被拒绝）概率0.42第（）栏：为求 做准备，用第（）栏同行去除上一行结果第（）栏：（），得 ，每天客房平均占用数，它的具体意义是：当n=1旅馆只有一个房间，每天客房平均占有数=0.93(间)n=5旅馆备有个房间，=4.48(间)n=8旅馆备有个房间，=6.92(间)，也就是说每天平均都有一间以上是空闲的 运 筹 学 课 程 软 件4/4/20234/4/20235454太原理工大学太原理工大学回目录页下一页M|M|C|m模型顾客源为有限数m，且mc，系统状态转移图如下：m-2m-1mc-1c运 筹 学 课 程 软 件4/4/20234/4/20235555太原理工大学太原理工大学回目录页下一页由此得平稳状态概率满足的差分方程为：由上述差分方程的 及 如下：(n c)(n c)(n c)运 筹 学 课 程 软 件4/4/20234/4/20237575太原理工大学太原理工大学回目录页下一页故顾客必须等待的概率为：运 筹 学 课 程 软 件4/4/20234/4/20237676太原理工大学太原理工大学回目录页例：对于（c1）模型，分别就（）系统容量有限制（），（）顾客源有限（m）这两种情况，写出有效到达率的表达式解：（）（）运 筹 学 课 程 软 件4/4/20234/4/20237777太原理工大学太原理工大学