随机过程与排队论

《随机过程与排队论》由会员分享，可在线阅读，更多相关《随机过程与排队论（46页珍藏版）》请在金锄头文库上搜索。

1、随机过程与排队论计算机科学与工程学院上一讲内容回顾连续参数马尔可夫链 转移概率函数、转移矩阵 连续参数齐次马氏链 初始分布、绝对分布、遍历 性、平稳分布 转移概率函数的性质 状态转移速度矩阵 生灭过程Date2计算机科学与工程学院 顾小丰本讲主要内容 排队论简介 排队的概念 排队系统的基本组成 经典排队系统的符号表示方法 无限源的简单排队 问题的引入 等待时间与逗留时间 忙期基本的排队系统系统M/M/1/ 队长 Little公式 输出过程Date3计算机科学与工程学院 顾小丰第四章 排队论简介v 排队论，又称为随机服务系统理论，是研究拥 挤现象的一门学科，它通过研究各种服务系统 在排队等待中的

2、概率特性，来解决系统的最优 设计和最优控制。v 排队论起源于20世纪初丹麦电信工程师A.K. Erlang对电信系统的研究，现已发展成为一门应用广泛的学科，在电信、交通运输、生产与 库存管理、计算机系统设计、计算机通信网络 、军事作战、柔性制造系统和系统可靠性等众 多领域，有着非常重要的应用。Date4计算机科学与工程学院 顾小丰排队的概念排队是日常生活和工作中常见的现象，由两个方面构成： 要求得到服务顾客 提供服务服务员或服务台 顾客与服务台(二者缺一不可)就构成一个排队系统，或称为随机服务 系统。Date5计算机科学与工程学院 顾小丰基本的排队系统单服务员(台)的排队系统2. 多服务员(台

3、)的排队系统顾客到达服务完成离去服务员顾客到达 服务完成离去服务员n服务员2服务员1一个队列多个队列顾客到达 服务完成离去服务员n服务员2服务员1服务完成离去服务完成离去串联顾客到达离去服务员1服务员2Date6计算机科学与工程学院 顾小丰排队系统的基本组成 输入过程 排队规则 服务机构描述顾客来源及顾客 按怎样的规律抵达。服务是否允许排队， 顾客是否愿意排队。 在排队等待的情况下 服务的顺序是什么。服务台的数目 服务时间分布Date7计算机科学与工程学院 顾小丰输入过程描述顾客来源及顾客按怎样的规律抵达。顾客总体数顾客的来源可能是有限的，也可能是无限的到达类型顾客是单个到达，还是成批到达顾客

4、相继到达的间隔时间服从什么概率分布， 分布函数是什么，到达的间隔时间之间是否独立在排队论中，一般假定顾客到达的间隔时间序列 n|n1相互独立、同分布。Date8计算机科学与工程学院 顾小丰排队规则服务是否允许排队，顾客是否愿意排队。在排队等待的情 况下服务的顺序是什么。 损失制 顾客到达时，若所有服务台均被占，服务机构 不允许顾客等待，此时该顾客就自动离去 等待制 顾客到达时，若所有服务台均被占，他们就排 队等待服务 先到先服务 后到先服务 随机服务 有优先权服务：强拆型优先权、非强拆型优先权 混合制 损失制与等待制的混合 对长(容量)有限的混合制 等待时间有限的混合制 逗留时间有限的混合制D

5、ate9计算机科学与工程学院 顾小丰服务机构服务台的数目 在多个服务台的情况下，是串联或是并联顾客所需的服务时间服从什么概率分布，每个顾客所需的服务时间是否相互独立，是成批服务或是单个服务Date10计算机科学与工程学院 顾小丰经典排队系统的符号表示方法一个排队系统是由许多条件决定的， 为简明起见，在经典的排队系统中，常 采用35个英文字母表示一个排队系统 ，字母之间用斜线隔开：v第一个字母表示输入的分布类型v第二个字母表示服务时间的分布类型v第三个字母表示服务台的数目v第四个字母表示系统的容量v第五个字母表示顾客源中的顾客数目。Date11计算机科学与工程学院 顾小丰几个经典排队系统的符号表

6、示vM/M/c/：输入过程是泊松流，服务时间服从负指数分布，有c个 服务台平行服务(00)的泊松过程，即相继到达的间隔时间序列n，n1独立、服从参数为(0)的负指数分布F(t)1-e-t，t0；v 顾客所需的服务时间序列n,n1独立、服从参数为(0)的负指数分布G(t)1-e-t，t0；v 系统中只有一个服务台；v 容量为无穷大，而且到达过程与服务过程彼此独立。Date15计算机科学与工程学院 顾小丰2.队长假定N(t)表示在时刻t系统中的顾客数，包括正在被服务 的顾客数，即N(t)表示时刻t系统的队长，t0，且令pij(t)PN(t+t)j|N(t)i，i,j0,1,2,则 1)pi,i+1

7、(t)P在t内到达一个而服务未完成 在t内到达j个而服务完j-1个P1t，1t 1+jtt，1t 1+jt0时，有 Wq(t)PWq=0P00) 的随机变量，即参数为的泊松流。 当系统空闲后，从开始空闲时刻起，到下一个顾客服 务完毕离去时之间的间隔时间不与服务时间同分布。令Tn+表示第n个顾客服务完毕的离去时刻，则 Tn+1+-Tn+表示离去的时间间隔，n1，于是，对t0有PTn+1+Tn+t PNn+=0PTn+1+Tn+t|Nn+=0 PNn+1PTn+1+Tn+t|Nn+1 PNn+=0Pn+1n+1t PNn+1Pn+1t 其中n+1表示剩余到达间隔时间，与n+1独立，而Nn+表示 第

8、n个离去顾客服务完毕离开系统时的队长。Date30计算机科学与工程学院 顾小丰输出过程(续)因此由于此式表示在统计平衡下，相继输出的间隔时间服从参数为 （0）的负指数分布。另外，在统计平衡下，输出的间隔时间相互独立，因 此对M/M/1/系统，其统计平衡下的输出过程与到达过程 相同。Date31计算机科学与工程学院 顾小丰例1某火车站一个售票窗口，若到达该窗口购票的 顾客按泊松流到达，平均每分钟到达1人，假定售 票时间服从负指数分布，平均每分钟可售2人，试 研究该售票窗口前的排队情况。 解 由题设知，1(人/分)，2(人/分)， ，该系统按M/M/1/型处理，于是在统计平衡下，有平均队长为(人)

9、平均等待队长为(人)Date32计算机科学与工程学院 顾小丰例1(续)平均等待时间为(分钟)平均逗留时间为(分钟)顾客到达不需要等待的概率为等待队长超过5人的概率为Date33计算机科学与工程学院 顾小丰例2考虑某种产品的库存问题。如果进货过多，则会带来过多的保管费，如果存货不足，则缺货时影响生产，造成 经济损失。最好的办法是能及时供应，但由于生产和运输 等方面的因素，一般讲这是难以满足的，因此希望找到一 种合理的库存s，使得库存费与缺货损失费的总和达到最小 。假定需求是参数的泊松流，生产是一个一个产品生产 的，每生产一个产品所需时间为参数的负指数分布。库 存一个产品的单位时间费用为c元，缺一

10、个产品造成的损失 费为h元，寻找一个最优库存量s，使得库存费与损失费之和达到最小（不考虑产品的运输时间）。Date34计算机科学与工程学院 顾小丰例2(续1)解 把生产产品的工厂看成是服务机构，需求看作是输入流，于是把问题化成M/M/1/系统，需求量表示队长，pk 表示生产厂有k个订货未交的概率。设库存量为s，则缺货时的平均缺货数为平均库存数为Date35计算机科学与工程学院 顾小丰例2(续2)单位时间的期望总费用为用边际分析法解上式，使上式最小的s应满足 f(s-1)f(s)， f(s+1)f(s)，于是由f(s+1)f(s)得，于是由f(s-1)f(s)得因此取最佳s*为最靠近的正整数即可

11、。Date36计算机科学与工程学院 顾小丰例3设船按泊松流进港口，平均每天到达2条，装卸时间服从负指数分布，平均每天装卸3条船，求：1) 平均等待对长与平均等待时间； 2) 如果船在港口的停留时间超过一个值t0就要罚款，求遭罚款的概率； 3) 若每超过一天罚款c元，提前一天奖励b元。假定服 务费与服务率成正比，每天h元，装卸一条船收入a 元，求使港口每天收入最大的服务率*的值。Date37计算机科学与工程学院 顾小丰例3(续1)解 由题设知， 2(条/天)，3(条/天)， ，该系统按M/M/1/型处理。1) 平均等待对长为(条船)平均等待时间为(天)2) 由于遭到罚款当且仅当船在港口的逗留时间

12、超过t0，所以遭到罚款的概率为3) 从费用方面考虑，每天装卸完条船收入a元，每天服 务费为h元。Date38计算机科学与工程学院 顾小丰例3(续2)平均提前完成时间为平均延后时间为所以，港口一天的总收入为Date39计算机科学与工程学院 顾小丰例3(续3)对f求导得讨论：1) bc时，2) bc时，由于 的符号在时完全由括号内的两项决定。令Date40计算机科学与工程学院 顾小丰例3(续4)由上图看出，y1与y2两曲线有唯一交点，其横坐标为*，b (b-c)*yy2y1且*唯一存在、有限，Date41计算机科学与工程学院 顾小丰例3(续5)b(b-c)*yy2y1bc时，由下图看出，y1与y2

13、两曲线仍有唯一交点，其横坐标为*，且*唯一存在、有限，Date42计算机科学与工程学院 顾小丰例4设顾客到达为泊松流，平均每小时到达个顾客是已知的。一个 顾客在系统内逗留每小时损失c1元，服务机构的费用正比于服务率， 每小时每位顾客的费用为c2元。假定服务时间为参数的负指数分布， 求最佳服务率*，使得整个系统总费用最少。解 由于平均对长 ，所以每小时顾客的平均损失费为元，每小时服务机构的平均费用为c2元，于是单位时间内平均总费用为由得因为，所以最佳服务率为*，此时Date43计算机科学与工程学院 顾小丰本讲主要内容 排队论简介 排队的概念 排队系统的基本组成 经典排队系统的符号表示方法 无限源

14、的简单排队 问题的引入 等待时间与逗留时间 忙期基本的排队系统系统M/M/1/ 队长 Little公式 输出过程Date44计算机科学与工程学院 顾小丰下一讲内容预告 无限源的简单排队系统M/M/1/ 具有可变输入率的M/M/1/ 问题的引入 队长 等待时间与逗留时间 Little公式 具有可变服务率的M/M/1/ 问题的引入 队长 等待时间与逗留时间Date45计算机科学与工程学院 顾小丰病人以每小时3人的泊松流到达医院， 假设该医院只有一个医生服务，他的服务 时间服从负指数分布，并且平均服务一个 顾客时间为15分钟。医生空闲时间的比例？ 有多少病人等待看医生？ 病人的平均等待时间？ 一个病人等待超过一个小时的概率？本节习题Date46计算机科学与工程学院 顾小丰