第2章随机过程与排队轮基础PPT讲稿.ppt

第2章随机过程与排队轮基础第1页，共99页，编辑于2022年，星期一准备知识:随机过程第2页，共99页，编辑于2022年，星期一准备知识:随机过程第3页，共99页，编辑于2022年，星期一准备知识:计数过程随机过程N(t),t0称为一个计数过程。N(t)表示到时刻t为止已发生的“事件”的总数。N(t)0；N(t)是整数；N(t)N(s)，当t s；N(t)-N(s)代表时间区间t,s)中发生的“事件”数第4页，共99页，编辑于2022年，星期一随机事件的两种描述法第5页，共99页，编辑于2022年，星期一随机事件的概率特征描述第6页，共99页，编辑于2022年，星期一随机事件的概率特征描述第7页，共99页，编辑于2022年，星期一随机事件特征量的物理意义第8页，共99页，编辑于2022年，星期一随机事件特征量的物理意义第9页，共99页，编辑于2022年，星期一Poisson过程 定义：计数过程N(t)服从泊松分布的随机过程，即长度为t的时间内到达k个事件的概率为 其中0是泊松流的强度，表示平均到达率；且N(0)=0；不相交区间上增量相互独立，即对一切 0t1t2tn，N(t1),N(t2)-N(t1),N(t3)-N(t2),N(tn)-N(tn-1)相互独立。应用：广泛用于各种随机事件的描述或近似，可用来描述完全不可预测的随机事件和大量随机事件的叠加。第10页，共99页，编辑于2022年，星期一o（1）平稳性:在区间 内有k个事件到来的概率与起点a无关，只与时间区间的长度有关，这个概率记为 o（2）无记忆性：不相交区间内到达的事件数是相互独立的；o（3）稀疏性:令 表示长度为t的区间内至少到达两个事件的概率，则 o（4）有限性：在任意有限区间内到达有限个事件的概率为1，即Poisson过程第11页，共99页，编辑于2022年，星期一都可以近似看作泊松流都可以近似看作泊松流.某电话交换台收到的电话呼叫数；某电话交换台收到的电话呼叫数；到某机场降落的飞机数到某机场降落的飞机数;一个售货员接待的顾客数一个售货员接待的顾客数;一台纺纱机的断头数一台纺纱机的断头数;一放射性源放射出的一放射性源放射出的 粒子数；粒子数；Poisson过程第12页，共99页，编辑于2022年，星期一Poisson过程第13页，共99页，编辑于2022年，星期一例题分析设电话呼叫按设电话呼叫按30次次/小时的泊松过程进行，求小时的泊松过程进行，求5分钟间隔分钟间隔内，内，(1)没有呼叫的概率；没有呼叫的概率；(2)呼叫呼叫3次的概率。次的概率。解：按题意=30次/h=0.5次/min t=5min，分别计算k=0或k=3 第14页，共99页，编辑于2022年，星期一Simon Denis Poisson oBorn:6/21/1781-Pithiviers,FranceoDied:4/25/1840-Sceaux,Franceo“Life is good for only two things:discovering mathematics and teaching mathematics.”第15页，共99页，编辑于2022年，星期一Simon Denis PoissonoPoissons father originally wanted him to become a doctor.After a brief apprenticeship with an uncle,Poisson realized he did not want to be a doctor.oAfter the French Revolution,more opportunities became available for Poisson,whose family was not part of the nobility.oPoisson went to the cole Centrale and later the cole Polytechnique in Paris,where he excelled in mathematics,despite having much less formal education than his peers.第16页，共99页，编辑于2022年，星期一Poissons education and workoPoisson impressed his teachers Laplace and Lagrange with his abilities.oUnfortunately,the cole Polytechnique specialized in geometry,and Poisson could not draw diagrams well.oHowever,his final paper on the theory of equations was so good he was allowed to graduate without taking the final examination.oAfter graduating,Poisson received his first teaching position at the cole Polytechnique in Paris,which rarely happened.oPoisson did most of his work on ordinary and partial differential equations.He also worked on problems involving physical topics,such as pendulums and sound.第17页，共99页，编辑于2022年，星期一Poissons accomplishmentsoHe has many mathematical and scientific tools named for him,including Poissons integral,Poissons equation in potential theory,Poisson brackets in differential equations,Poissons ratio in elasticity,and Poissons constant in electricity.He first published his Poisson distribution in 1837 in Recherches sur la probabilit des jugements en matire criminelle et matire civile.Although this was important to probability and random processes,other French mathematicians did not see his work as significant.His accomplishments were more accepted outside France,such as in Russia,where Chebychev used Poissons results to develop his own.第18页，共99页，编辑于2022年，星期一泊松过程的期望与方差第19页，共99页，编辑于2022年，星期一泊松过程的期望与方差第20页，共99页，编辑于2022年，星期一Poisson过程的叠加和分解第21页，共99页，编辑于2022年，星期一Poisson过程的叠加o性质2-1：m个Poisson流的参数分别为 ，并且它们是相互独立的，合并流仍然为Poisson流，且参数为 。o这个性质也就是说独立的Poisson过程是可加的。=1+212第22页，共99页，编辑于2022年，星期一o性质2-2：参数为 的Poisson流到达交换局A后，每个呼叫将独立去两个不同方向，且去两个方向的概率分别为o o则Poisson流被分解为两个独立的Poisson流，参数分别为 Poisson过程的分解第23页，共99页，编辑于2022年，星期一o设N(t)表示一个Poisson 过程，o假设t,i=0,1,2,i 为相应的呼叫到达时刻，考虑呼叫的间隔：o根据Poisson 的特性o随机变量X 满足PX t=et，o分布函数为：PX t=Pmin(T1,T2)t=PT1t,T2t=PT1t PT2t 又因为 ，所以(2)先证明第28页，共99页，编辑于2022年，星期一(3)需要证明的就是随机变量T与随机事件T1t,T1tPT1T2。性质2.4的证明 第29页，共99页，编辑于2022年，星期一例题分析(1/6)第30页，共99页，编辑于2022年，星期一例题分析(2/6)第31页，共99页，编辑于2022年，星期一例题分析(3/6)第32页，共99页，编辑于2022年，星期一例题分析(4/6)第33页，共99页，编辑于2022年，星期一例题分析(5/6)第34页，共99页，编辑于2022年，星期一例题分析(6/6)第35页，共99页，编辑于2022年，星期一名言中的数学哲理第36页，共99页，编辑于2022年，星期一 由泊松定理，由泊松定理，n重贝努里试验中重贝努里试验中稀有事件稀有事件出现出现的次数近似地服从的次数近似地服从泊松分布泊松分布.我们把在每次试验中出现概率很小的事我们把在每次试验中出现概率很小的事件称作件称作稀有事件稀有事件.如地震、火山爆发、特大洪水、意外事故等等如地震、火山爆发、特大洪水、意外事故等等名言中的数学哲理第37页，共99页，编辑于2022年，星期一生灭过程的应用与举例生灭过程的应用与举例 o应用：用于处理输入过程为最简单流，服务时间为指数分布的一类最简单的排队模型。o举例：(1)某地区人口数量的自然增减 (2)细菌的繁殖与死亡 (3)服务窗口前顾客数的变化第38页，共99页，编辑于2022年，星期一生灭过程的定义生灭过程的定义 o用N(t)表示系统在时刻t 的状态，N(t)取非负整数值。如果N(t)=k，称在时刻t 系统处于状态k。系统是生灭过程的条件：n（a）在时间(t,t+t)内系统从状态k(k0)转移到k+1的概率为kt+o(t)，这里k 为在状态k 的出生率；n（b）在时间(t,t+t)内系统从状态k(k1)转移到k1的概率为k t+o(t)，这里k 为在状态k 的死亡率；n（c）在时间(t,t+t)内系统发生跳转的概率为o(t)；n（d）在时间(t,t+t)内系统停留在状态k 的概率为1(k+k)t+o(t)。第39页，共99页，编辑于2022年，星期一生灭过程的定义生灭过程的定义 第40页，共99页，编辑于2022年，星期一生灭过程的状态转移生灭过程的状态转移o生灭过程的状态转移图o状态转移图包含系统的所有状态和所有可能的变化。o状态变化仅仅发生在相邻的状态之间，整个状态图是一个有限或无限的链。生灭过程是一个马尔可夫链第41页，共99页，编辑于2022年，星期一 “将来”“过去”“现在”=“将来”“现在”-马氏性(无记忆性，无后效性)马尔可夫链的概念马尔可夫链的概念第42页，共99页，编辑于2022年，星期一生灭过程的特性生灭过程的特性 o生灭过程是一种特殊的离散状态的连续时间马尔可夫过程，或被称为连续时间马尔可夫链。o生灭过程的特殊性在于状态为有限个或可数个，并且系统的状态变化一定是在相邻状态之间进行。o生灭过程的极限解或稳态解有很简单的形式。o应用：考虑一个电话机中的呼叫数，既可以增加也可以减少，所以需要引入的生灭过程可以用来描述电话交换机中呼叫数的变化。Poisson 过程是一种特殊的纯生过程。第43页，共99页，编辑于2022年，星期一生灭过程的稳态分布生灭过程的稳态分布o考虑系统的稳态分布。生灭过程满足的柯尔莫哥洛夫（Kolmogorov）方程。n pk(t)=P N(t)=k；n pik(t)为系统从状态i 经过时间t 后转移到k 的条件概率：n根据生灭过程性质有第44页，共99页，编辑于2022年，星期一生灭过程的稳态分布生灭过程的稳态分布o推导后当 t 0 时，有o称为柯尔莫哥洛夫方程组o如果加上初始条件pk(0)，可确定各个时刻t 的分布。o考虑的重点为极限分布或稳态分布，就不需要处理复杂的微分方程组，而是线性方程组。第45页，共99页，编辑于2022年，星期一稳态分布满足的必要条件o假设稳态分布存在，对方程求解 o在t 时，o方程变为：(k+k)pk +k1pk1+k+1pk+1=0n其中 1=0=p1=0；n另外第46页，共99页，编辑于2022年，星期一稳态分布稳态分布 o解容易得到o其中第47页，共99页，编辑于2022年，星期一极限定理 o定理2-3：对有限状态的生灭过程或对满足条件 的可数状态的生灭过程，稳态分布存在，且与初始条件无关。o有限状态时，稳态分布为：第48页，共99页，编辑于2022年，星期一o关于生灭过程中微分方程和稳态方程的建立可以依照下面图2-3简单完成 微分方程和稳态方程第49页，共99页，编辑于2022年，星期一生灭过程小结n方程组：和初始值决定系统的变化，它们是瞬态分析的基础。n生灭过程的稳态分布，虽然一般是无限多变量的线性方程组，但是由于生灭过程只有相邻状态有关系，故可以简单化解。n如果系统的状态变化不局限在相邻状态之间，分布就不容易得到。如果到达的呼叫流不平稳，有时可以用特殊的生灭过程表示信源。第50页，共99页，编辑于2022年，星期一名人名言 生活中最重要的问题，其中绝大多数在实质生活中最重要的问题，其中绝大多数在实质上只是概率的问题上只是概率的问题.-拉普拉斯拉普拉斯 我又转念，见日光之下，快跑的人未必能赢，力我又转念，见日光之下，快跑的人未必能赢，力战的未必得胜，智慧的未必得粮食，明哲的未必得资战的未必得胜，智慧的未必得粮食，明哲的未必得资财，灵巧的未必得喜悦，所临到众人的，是在乎当时财，灵巧的未必得喜悦，所临到众人的，是在乎当时的机会的机会.-传道书传道书第51页，共99页，编辑于2022年，星期一排队系统的基本概念o排队论是专门研究带有随机因素，产生拥挤现象的优化理论。也称为随机服务系统。第52页，共99页，编辑于2022年，星期一排队系统的基本概念第53页，共99页，编辑于2022年，星期一排队系统的基本概念第54页，共99页，编辑于2022年，星期一排队系统的基本概念第55页，共99页，编辑于2022年，星期一排队系统的基本概念第56页，共99页，编辑于2022年，星期一排队系统的基本概念第57页，共99页，编辑于2022年，星期一排队系统的描述第58页，共99页，编辑于2022年，星期一排队系统的描述第59页，共99页，编辑于2022年，星期一排队系统的描述第60页，共99页，编辑于2022年，星期一排队系统的描述第61页，共99页，编辑于2022年，星期一排队系统的描述第62页，共99页，编辑于2022年，星期一排队系统的描述第63页，共99页，编辑于2022年，星期一排队系统的描述第64页，共99页，编辑于2022年，星期一排队系统的描述第65页，共99页，编辑于2022年，星期一排队模型表示排队模型表示肯德尔肯德尔记号记号第66页，共99页，编辑于2022年，星期一排队系统的参数和指标第67页，共99页，编辑于2022年，星期一排队系统的参数和指标第68页，共99页，编辑于2022年，星期一排队系统的参数和指标第69页，共99页，编辑于2022年，星期一排队系统的参数和指标第70页，共99页，编辑于2022年，星期一排队系统的参数和指标第71页，共99页，编辑于2022年，星期一Little定理第72页，共99页，编辑于2022年，星期一Little定理第73页，共99页，编辑于2022年，星期一Little定理第74页，共99页，编辑于2022年，星期一Little定理第75页，共99页，编辑于2022年，星期一Little定理第76页，共99页，编辑于2022年，星期一Little定理第77页，共99页，编辑于2022年，星期一Little公式的应用1.考虑一个传输线，每隔K秒到达一个数据包，假设第一个包在0时刻到达。所有的包长度相等，需要相同的传输和处理时间，分别为K秒和X秒，问传输线上停留的数据分组的平均数目为多少？解：1/K；N T(K+X)/K+X/K 第78页，共99页，编辑于2022年，星期一Little公式的应用2.假设一个服务大厅有K个窗口，该服务大厅最多容纳N个顾客(NK)，且服务大厅始终是客满的，即一个顾客离开将会有另一个顾客进入。设每个顾客的服务时间是X，问顾客在大厅内停留的时间T为多少？3.改变上题目中的顾客到达方式，假设顾客到达时发现服务窗口被占就立即离开大厅(即顾客被阻塞)。设顾客到达率是，问顾客的阻塞率为多少？解：NT T N/；K X K/X；TNX/K解：平均处于忙的窗口数为j(j K)，系统中平均用户数：j(1)X；1j/X 1K/X 第79页，共99页，编辑于2022年，星期一Little公式的应用第80页，共99页，编辑于2022年，星期一M/M/1oM/M/1的到达过程为一个参数为 的Poisson过程；系统允许排队的队长可以是无穷大(系统的缓存容量无限大)；服务时间是参数为 的负指数分布；服务员的数目为1，到达过程与服务过程相互独立。如果用系统中的顾客数来表征系统的状态，容易验证这是一个生灭过程，并且第81页，共99页，编辑于2022年，星期一o 令 ，根据生灭过程的性质o在 时 oM/M/1的队长分布 M/M/1第82页，共99页，编辑于2022年，星期一M/M/1第83页，共99页，编辑于2022年，星期一M/M/1第84页，共99页，编辑于2022年，星期一M/M/1第85页，共99页，编辑于2022年，星期一M/M/1第86页，共99页，编辑于2022年，星期一M/M/1由Little定理，顾客停留在系统中的平均时间：顾客的平均排队时间：顾客的平均排队(等待)队长：假设k为顾客到达时看到的队长分布，这个分布在许多情形下不同于稳态分布p k，不过在到达过程为泊松过程时k和p k是一样的。第87页，共99页，编辑于2022年，星期一M/M/1第88页，共99页，编辑于2022年，星期一o定理2-5：M/M/1排队系统在稳态时，系统时间s服从参数为-的负指数分布。M/M/1第89页，共99页，编辑于2022年，星期一M/M/1第90页，共99页，编辑于2022年，星期一忙期与闲期第91页，共99页，编辑于2022年，星期一忙期与闲期第92页，共99页，编辑于2022年，星期一 设某学校有一部传真机为全校2万名师生提供传真服务。假定每份传真的传输时间服从负指数分布，其平均传输时间为3分钟，并假定每个人发送传真的可能性相同，服从泊松到达。如果希望平均排队的队长不大于5人，试问平均每人间隔多少天才可以发送一份传真？例题分析(1/2)第93页，共99页，编辑于2022年，星期一n该传真服务系统可用M/M/1队列来描述。已知1/=3分钟,人，要求解(份/天)。n系统总的可以发送的传真速率为：例题分析(2/2)o平均每个用户要隔 天才可以发送一份传真。第94页，共99页，编辑于2022年，星期一课堂练习1在某数据传输系统中，有一个数据交换节点。顾客的信息包按泊松流到达此节点。已知平均每小时到达20个数据包，此节点的处理事件服从负指数分布，平均处理每个信息包需要2.5min，问：节点闲的概率：节点忙的概率：平均队长：平均等待队长：平均逗留时间：平均排队时间：节点闲的概率：1/6节点忙的概率：5/6平均队长：5个平均等待队长：4.166个平均逗留时间：15min平均排队时间：12.5min第95页，共99页，编辑于2022年，星期一课堂练习2某机关接待室有一位对外接待人员，每天工作10h。若来访人员按泊松流输入，其输入强度=7人/h，服务时间服从负指数分布，服务强度为=7.5人/h。现在要求：来访者的逗留时间和等待时间？平均排队的队长？若来访者希望逗留时间减少一半，则接待人数应提高多少？来访者的逗留时间和等待时间？120min/112min平均排队的队长？13人若来访者希望逗留时间减少一半，则接待人数应提高多少？8人/h第96页，共99页，编辑于2022年，星期一课堂练习3第97页，共99页，编辑于2022年，星期一课堂练习3第98页，共99页，编辑于2022年，星期一习题作业 o2-2o2-4 o2-8o2-11 第99页，共99页，编辑于2022年，星期一