（概率论与数理统计专业论文）随机环境下的几类可修排队系统.pdf

r 、 i 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允 许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容， 可以采用复印、缩印或其它手段保存学位论文同时授权中国科学技 术信息研究所将本学位论文收录到中国学位论文全文数据库，并 通过网络向社会公众提供信息服务 作者签名： 导师签名日期：二业年月旦日 摘要 在本文中，我们主要研究几类随机环境下可修的排队系统 排队系统偶然遭遇了重大的故障，当前所有的顾客( 等待的和正 在被服务的) 全部丢失修理过程马上开始，经过一个负指数分布的修 理时间后系统又重新进入正常工作状态当系统瘫痪处于修理状态时， 新的顾客会变的没有耐心：每一个独立的顾客都遵循一个随机的忍耐 时间，当这个时间在系统修理成功之前来临的话顾客就会放弃等待并 且不再回来当系统从工作状态进入修理状态时，顾客的到达率也随之 调整为五，从修理状态进入工作状态时，根据随机环境的马氏过程来调 整到达率和服务率 本文主要研究了随机环境下的m m i , m m c 和m m o o 排队模型， 通过计算得到每种排队模型中的概率发生函数及相应队长，及完成服 务顾客的平均逗留时间最后将结论应用到单个工作状态和发生故障 后没有顾客到达的两种特殊情形 关键词：排队系统故障，失去耐心，概率发生函数，逗留时间，平均队长 w h e nt h es y s t e m sa r eb r e a k d o w n ，n e wc u s t o m e r sa r eb e c o m ei n p a t i e n t ： e v e r yi n d e p e n d e n tc u s t o m e ri sa c c o r d i n gt oas t o c h a s t i ct o l e r a n tt i m e ，a n d h ew i l lg i v eu pw a i t i n ga n dn e v e rg ob a c k ，i ft h et i m ec o m e se a r l i e rt h a n t h a to f b e i n gr e p a i r e ds u c c e s s f u l l y w h e nt h es y s t e m st u r n si n t ob e i n g r e p a i r e d ，t h ec u s t o m e ra r r i v a lr a t eb e c o m e s 厶w h i l ew h e nt h es y s t e m s t u r n si n t ow o r k ，t h ea r r i v a lr a t ea n ds e r v i c er a t eo u g h tt ob ea d j u s t e dw i t h t h em a r k o vp r o c e s si nt h es t o c h a s t i ce n v i r o n m e n t t h eq u e u es y s t e m so fm m 1 ，m f m f ca n dm m r 。ow i t hs t o c h a s t i c e n v i r o n m e n ta r ei n v e s t i g a t e d b ym o d e l sa n a l y s i sa n dc a l c u l a t i o n s ，w e d e r i v et h e p r o b a b i l i t yg e n e r a t i n gf u n c t i o n ，t h ec o r r e s p o n d i n gq u e u e l e n g t h ，a n dm e a ns o jo u r nt i m eo fs e r v e dc o u s t o m e r s f i n a l l y ，t h e c o n c l u s i o n sa r ea p p l i e dt oc a s e so fs i n g l ew o r ks t a t u sa n dn o nc u s t o m e r a r r i v a la f t e rb r e a k i n gd o w n k e yw o r d s ： s y s t e ms u f f e r sb r e a k d o w n ，i m p a t i e n c e ，p r o b a b i l i t y g e n e r a t i n gf u n c t i o n ，s o jo h mt i m e s ，m e a nq u e u e l e n g t h n 目录 摘要一i a b s t r a c t i i 目勇乏i i 第一章绪论1 1 1 问题提出的背景与研究现状1 1 2 论文的结构3 第二章预备知识5 2 1 排队论简史5 2 2 排队系统的组成部分一5 2 3 排队系统的表示方法一6 2 4 排队系统的主要指标6 2 5 排队论的应用7 2 6 两个重要的概率分布8 2 6 1 几何分布8 2 6 2 负指数分布8 2 7 泊松过程9 2 8 更新过程1 0 2 9 马尔可夫过程12 2 1 0 马尔科夫链。1 2 2 1 1 生灭过程一14 第三章m m 1 可修排队系统分析1 7 3 1l 、压a 压1 模型17 3 2 平衡方程和生成函数1 7 3 3 逗留时间2 0 3 4 顾客数l 1 才能发生故障情形2 l 3 4 1 平衡方程和生成函数2 1 3 4 2 逗留时间2 3 第四章m m c 可修排队系统分析2 4 4 1 平衡方程和生成函数2 4 4 2 逗留时间2 5 4 3 顾客数l 1 才能发生故障情形2 6 第五章m 瓜厦，o o 可修排队系统分析2 9 i i i 5 1 平衡方程和生成函数2 9 5 2 逗留时间3 1 5 3 顾客数l l 才能发生故障情形31 第六章特殊情形。3 4 6 1 单个工作状态情形3 4 6 2 发生故障后没有顾客到达情形3 5 第七章总结3 7 参考文献3 8 致谢4 2 攻读学位期间主要研究成果4 3 i v 硕士学位论文 第章绪论 第一章绪论 1 1 问题提出的背景与研究现状 系统排队论的基本思想是1 9 1 0 年丹麦电话工程师a k 埃尔朗在解决自动电 话设计问题时开始形成的，当时称为话务理论他在热力学统计平衡理论的启发 下，成功地建立了电话统计平衡模型，并由此得到一组递推状态方程，从而导出著 名的埃尔朗电话损失率公式 自2 0 世纪初以来，电话系统的设计一直在应用这个公式3 0 年代苏联数学家 a h 欣钦把处于统计平衡的电话呼叫流称为最简单流瑞典数学家巴尔姆又引 入有限后效流等概念和定义他们用数学方法深入地分析了电话呼叫的本征特性， 促进了排队论的研究5 0 年代初，美国数学家关于生灭过程的研究、英国数学家d g 肯德尔提出嵌入马尔可夫链理论，以及对排队队型的分类方法，为排队论奠定 了理论基础在这以后，l 塔卡奇等人又将组合方法引进排队论，使它更能适应各 种类型的排队问题7 0 年代以来，人们开始研究排队网络和复杂排队问题的渐近 解等，成为研究现代排队论的新趋势 排队是在日常生活中经常遇到的现象，如顾客到商店购买物品、病人到医院 看病常常要排队此时要求服务的数量超过服务机构( 服务台、服务员等) 的容 量也就是说，到达的顾客不能立即得到服务，因而出现了排队现象这种现象不 仅在个人日常生活中出现，电话局的占线问题，车站、码头等交通枢纽的车船堵塞 和疏导，故障机器的停机待修，水库的存贮调节等都是有形或无形的排队现象由 于顾客到达和服务时间的随机性可以说排队现象几乎是不可避免的 排队论( q u e u i n gt h e o r y ) 也称随机服务系统理论，就是为解决上述问题而 发展的一门学科它研究的内容有下列三部分 2 0 ： 1 性态问题，即研究各种排队系统的概率规律性，主要是研究队长分布、等待 时间分布和忙期分布等，包括了瞬态和稳态两种情形 2 最优化问题，又分静态最优和动态最优，前者指最优设计后者指现有排队 的最优运营 3 排队系统的统计推断，即判断一个给定的排队系统符合于哪种模型，以便 根据排队理论进行分析研究 “排队是指在服务机构处要求服务对象的一个等待队列而“排队论则是 研究各种排队现象的理论，它是运筹学的一个重要分支在排队论中我们把要求 服务的对象称为“顾客，而将从事服务的机构或人称为“服务台或“服务员 硕士学位论文 第一章绪论 在顾客到达服务台时，可能立即得到服务，也可能要等待到可以利用服务台的时 候为止 人们在日常工作和生活中，常常遇到各种各样的排队现象，构成顾客一服务 台结构的排队系统例如上、下班的乘客乘坐公共汽车，这里乘客是顾客，公共汽 车是服务员，病人去医院看病，病人是顾客，医生是服务员：一台发生故障的机器 需要修理，机器是顾客，而修理工是服务员，如此等等 6 9 队列除了有形的还有无形的例如，有许多顾客同时打电话给车站订购车票， 当其中一个顾客正在通话中，其它顾客只好在各自的电话机旁等待通话，他们尽 管分散在各处，但却形成一个无形的队列其次，排队的顾客不一定是人，也可以 是物：同样，服务员也不一定是人，可以是物如急需降落的飞机因跑道不空而在 空中盘旋：大海中的船舶等待靠岸等等 下图是排队论的一般模型 项客随机到达顾客服务机构 甩夏客离去 排队( 服务时间随机) 图一 图一中虚线所包含的部分为排队系统各个顾客从顾客源出发，随机地来到服 务机构，按一定的排队规则等待服务，直到按一定的服务规则接受完服务后离开排 队系统 凡要求服务的对象统称为顾客，为顾客服务的人或物称为服务员，由顾客和服 务员组成服务系统对于一个服务系统来说，如果服务机构过小，以致不能满足要 求服务的众多顾客的需要，那么就会产生拥挤现象而使服务质量降低因此，顾客 总希望服务机构越大越好，但是，如果服务机构过大，人力和物力方面的开支也就 相应增加，从而会造成浪费，因此研究排队模型的目的就是要在顾客需要和服务机 构的规模之间进行权衡决策，使其达到合理的平衡 通过查阅排队论的经典文献，发现研究的排队系统几乎都假定服务台是不可 能发生故障的，但在实践中会经常会碰到服务台发生故障( 例如由负顾客的到达所 引起1 而不能为顾客服务的情形此时需要对服务台进行修理，服务台被修理好后 继续为顾客服务对于这类服务台可能发生故障且可修的排队系统，无论从排队论 角度，还是从可靠性理论的角度都是非常值得研究的在6 0 年代前后，国外有学者 在排队系统模型研究开始考虑服务台可能发生故障这一实际情况，但他们仅从排 2 硕士学位论文第一章绪论 队论的角度进行研究的，即只研究了系统的排队指标，而没有考虑由此产生的服务 台的可靠性指标，1 9 8 2 年，c a o 和t h e n 7 8 】研究了服务台可修的m g l 排队系统， 不仅求出了系统的各种排队指标，并且首次从可靠性理论角度讨论了该系统中服 务台的各种可靠性数量指标，即在时刻t 服务台失效的概率( 不可用度) 和在( o ，f 】 内服务台失效的平均次数等，于是排队系统模型与可靠性系统模型的交叉问题引 起了从事运筹学和应用数学工作的专家学者们的广泛注意，而“可修排队系统”一 词也被正式提出并使用起来近来，w a n g 等【7 9 】从可靠性理论的角度分析了服务台 可修的m g 1 重试排队系统，文章既讨论了排队指标，又讨论了服务台的可靠性指 标 可修排队系统是排队模型与可靠性模型的结合，研究的难度会比单独的排队 系统或可靠性系统要高，查阅相关资料发现，此类的研究相对较少，有进一步研究 的空间和意义 本文研究的是随机环境下的几类可修排队系统在系统发生故障后系统中原 有的顾客会选择离开或等待，资料中显示，在早期的研究过程中，系统发生故障崩 溃后，原有的顾客没有全部离开，近期的研究的模型较简单，为系统发生故障崩溃 后，顾客全部离开m m 1 ，m g 1 ，m m c 和m m o o 排队模型都被研究过但是，以前 的作者大都研究的是两个状态，即正常工作状态和修理状态，我们则把他们的结果 推广到了1 1 个状态，考虑了随机环境 1 2 论文的结构 本文主要研究随机环境下的m 肘c ( 萨1 ，l e o o ，c = c o ) 排队模型，随机环 境由( 刀+ 1 ) 个状态的的马氏链控制系统在某个正常状态时作为一个整体遭遇了 一次重大的故障，当故障发生的时候，所有当时系统中的顾客全部丢失，系统进入 修理阶段，修理时间是随机的同时，当系统不能工作的时候，顾客的到来仍然服从 指数分布，每个到来的顾客都有他自己独立的“失去耐心时间”，也就是说在这个时 间到达的时候若系统仍然没有恢复到某个正常的工作状态，顾客便会放弃并且不 再回来 本人余下各章的主要研究如下： 第二章是预备知识介绍本文的排队论理论基础主要介绍排队论简史、排队 系统的组成部分、排队系统的表示方法、排队系统的主要指标、排队论的应用、 两个重要的概率分布、泊松过程、更新过程、马尔可夫过程、马尔可夫链、生灭 过程 第三章研究随机环境下的m m l 排队模型：泊松到达，只有个服务台，服务 时间服从负指数分布通过分析该模型，分别获得系统在发生故障和各个正常工作 硕士学位论文 第一章绪论 状态下的概率发生函数，然后计算出系统的平均队长及被服务顾客的平均逗留时 间同时分别研究系统在任何时候都可以发生故障和只有在工作时才发生故障这 两种情况 第四章研究随机环境下的m j m j c 排队模型：泊松到达，c 个服务台，服务时间 均服从负指数分布分析该模型，获得相关的概率发生函数，计算出平均队长和平 均逗留时间以及各项排队系统参数同时分别研究系统在任何时候都可以发生故 障和只有在工作时才发生故障这两种情况 第五章研究随机环境下的删排队模型：泊松到达，无穷个服务台，服务时 间均服从负指数分布分析模型，获得概率发生函数，计算出各项排队系统参数，分 别研究系统在任何时候都可以发生故障和只有在工作时才发生故障这两种情况 第六章针对随机环境下的m m 1 讨论了两种特殊情形，对m m j c 和m m o o 可类似讨论 最后第七章给出了本文的主要结论我们研究了随机环境下的的m m 1 ，m m c 和m m o o 排队模型，通过计算得到每种排队模型中的概率发生函数及相应队长， 及完成服务顾客的平均逗留时间最后将结论应用到单个工作状态和发生故障后 没有顾客到达的两种特殊情形 4 硕士学位论文第二章预备知识 2 1 排队论简史 第二章预备知识 排队论起源于2 0 世纪初的电话通告1 0 9 0 1 9 2 0 年丹麦数学家、电气工程师 爱尔朗( a k e d a n g ) 用概率论方法研究电话通话问题，从而开创了这门应用数学 学科，并为这门新学科建立许多基本原则3 0 年代中期，当费勒( w f e l l e r ) 引进了 生灭过程时，排队论才被数学晃承认为一门重要的学科在二战期间和二战以后 排队论在运筹学这个新领域中成了一个重要的内容2 0 世纪5 0 年代初肯德尔 ( d g k e n d a l l ) 对排队论做了系统的研究，他用嵌入马尔可夫链方法研究排队论， 使排队论得到了进一步发展他首先用三个字母组成的符号表示排队系统2 0 世纪 6 0 年代起，排队论研究的课题日趋复杂，很多问题不是很难求得其精确解，就是求 得的解非常复杂，不便于应用因而开始了近似方法的研究 排队论的产生于发展来自实际的需要，实际的需要也必将决定他今后的发展 方向排队论应用范围很广，它应用于一切服务系统，尤其在通信系统、交通系统、 计算机、储存系统，生产管理等方面应用的最多 2 2 排队系统的组成部分 一般排队系统由输入过程与到达规则、排队规则、服务机构的结构、服务时 间与服务规则组成 1 输入过程与到达规则输入过程一般是用( 顾客) 到达间隔时间来描述的 根据到达间隔时间所服从的分布，输入过程可分为定长输入、( 负) 指数输入 ( p o i s s o n 输入) 、爱尔朗输入、几何输入( b e r n o u l l i 输入) 、负二项输入与一般 输入，到达规则是指在这些输入的每一种中又可分为单个到达、成批到达、依时 到达、移态到达等 2 排队规则排队规则一般分为等待制、损失制和混合制在等待制与混合制 中通常又可分为先来先服务( f c f s ) 、后来先服务( l c f s ) 、随机服务( r o s ) 、 优先非抢占服务、优先抢占服务等在混合制中又分为队长( 容量) 有限、等待 时间有限此外，还有顾客服务后反馈以及共同占用、占而不用等等 3 服务机构的结构服务机构的结构可分为单服务台、有限个服务台与无限多 个服务台而在( 有限) 多个服务台中又可分为并联、串联两种 4 服务时间与服务规则服务时间是指服务一个顾客所用的时间根据其分布， 一般分为定长分布、指数分布、几何分布与一般分布等服务规则分为有价时间 5 硕士学位论文第二章预备知识 与无价时间两类在有价时间中又可分为穷尽服务、门限服务、有限服务、减量 服务而在穷尽服务和门限服务中又可分为单假时间与多假时间两种在上述各种 情形中又可分为单个服务与成批服务 2 3 排队系统的表示方法 1 9 5 1 年肯德尔用三个字母组成的符号a b c 表示排队论系统其中a 表示到 达间隔时间分布，b 表示服务时间的分布，c 表示服务机构中服务台的个数一般用 d 表示定长分布，用m 表示指数分布，用g e o 表示几何分布，用e 表示r 阶爱尔朗 分布，用日。表示r 超指数分布，用g 表示一般分布例如，m m n 表示到达间隔时间 与服务时间均服从指数分布( 参数一般不相同) 且服务机构有n 个服务台的排队 系统；m g 1 表示到达时间间隔服从指数分布，服务时间服从一般分布，服务机构只 有一个服务台的排队论系统后来人们在三个字母后面又加了两个字母，分别表示 系统的容量和输入源中的顾客数，并且在前两个字母的右上角加字母以表示每次 到达几个顾客与每次服务几个顾客例如，m f g ，1 1 所n 表示该系统的到达间 隔时间服从指数分布，每次到达孝( f 可以是随机变量) ，服务时间服从一般分布， 每次服务7 7 ( 7 7 可以是随机变量) 个顾客，服务机构只有一个服务台且最多只能容 纳m 个顾客，输入源最多只有n 个顾客，如过只有前三个字母，则表示系统的容量 和输入源中的顾客数均为无限 一般还假设到达间隔时间序列 以，f 1 为独立同分布随机变量序列，服务时 间序列 e ，f l l 也为独立同分布随机变量序列且这两个随机变量序列也相互独 立 2 4 排队系统的主要指标 评价一个排队系统的好坏要以顾客和服务机构两方面利益为标准就顾客来 说，总希望等待时间或逗留时间越短越好，从而希望服务台个数尽可能多些但是 就服务机构来说，增加服务台数就意味着增加投资，增加多了就要造成浪费顾客 与服务机构为了照顾自己的利益对排队系统中的几个指标：队长、等待时间、服 务台的忙期都很关心因此，这几个指标就成了排队论的主要研究内容 1 、队长队长是指系统中的顾客数，即正在服务的顾客数与等待服务的顾客数 之和他一般是一个随机变量，通常要求其分布和前两阶矩 2 、等待时间从顾客到达时起一直到他被接受服务时止，这段时间称为该顾客 的等待时间而称从顾客到达系统时起一直到他被服务完离开系统时止这段时间 为该顾客的逗留时间，即顾客的等待时间与服务时间之和我们也要求他们的分布 6 硕士学位论文第二章预备知识 和前两阶矩 3 、忙期忙期是指空闲的服务机构从有顾客到达时起一直到服务机构没有顾 客时止这段时间与忙期相对应的是闲期，他是指服务机构从开始没有顾客起一直 到服务机构有顾客时止这段时间，对于有n 个服务台的系统，一般还要讨论其k 阶 繁忙期从系统中开始有k 个顾客在等待服务时起一直到有一个服务台空闲时止 这段时间称为该系统的k 阶繁忙期零阶繁忙期称繁忙期，忙期、闲、k 阶繁忙期 也是随机变量 2 5 排队论的应用 排队论应用范围很广，它应用于一切服务系统，它的应用领域大致可归纳为以 下七个方面 1 0 】、【1 1 】 1 通讯问题 排队论起源于电话交换机问题的研究一部电话交换机通常只有有限多条通 话线路若在某一时刻所有线路被占用，则这时到达的新呼唤或者消失，或者等待 到有一条线路空出来我们可以把呼唤看作是顾客，通话线路看作是服务员，于是 交换机的工作过程就是一个排队问题，排队规则一般是先来先服务 2 公众服务问题 这是人们在日常生活中最熟悉的一类排队现象银行、邮局的营业员商店，超 级市场的收款员，医院的医生或者病床，交通和娱乐设施的售票口，饭店的座位等 都可以看作是服务员，到这些公众服务设施要求服务的人就是顾客排队规则一般 是先到先服务，但也可能是按优先权服务，例如，医院对于危重病人应给予优先服 务 3 应急单位的服务问题 公安执勤车、消防车、交通事故拯救队、医院救护车等都可以看作是服务员 相应的事故发生表示顾客到达这类排队问题要求系统有足够的服务员，使能随时 应付可能发生的紧急事故排队规则可以是先来先服务或按优先服务权服务 4 交通问题 这是排队论应用的一个重要领域例如，达到某公交车站的乘客是顾客，公共 汽车是服务员，服务时间则是相继两辆车到站时间的间距，这是一个成批服务的排 队问题排队规则一般是先到先服务在水运方面，若把船舶看成是顾客，港口码头 的泊位则是服务员，服务时间是船舶装载时间，服务规则一般是先到先服务或按优 先权服务空运方面的一个排队例子是机场调度问题这是在机场起飞和降落的飞 机是顾客，机场跑道是服务员飞机到达机场时，若没有空闲的跑则要在空中盘旋 等待服务规则多半用先到先服务，但有时也要考虑优先权 7 硕士学位论文第二章预备知识 5 工业生产问题 在工厂生产线上，为了保证生产水平和降低成本，必须合理安排工人、生产工 序、原材料和设备，这类问题往往可以归结为排队问题加以研究解决这时顾客可 以是原材料、半成品或产品，服务员则是工人、设备等等在机器的维修问题中，机 器发生故障后要等待修理工修理，这时故障的发生意味着顾客到达，而修理工就是 服务员上述问题，排队规则一般是先来先服务 6 储存问题 储存系统中许多问题可以作为排队问题处理，例如，商店或仓库中商品的储存 量可以看作是队长，进货表示顾客到达，售出或发出货物则是顾客离去在水库问 题中，流入水库的水是到达的顾客( 这时顾客实际上是连续到达和离去的，但我们 可以做离散化处理) ，水从水库流出则是顾客离去，水库的存水量可以看作是队长 7 计算机系统配置问题 就计算机内部来说，中央处理机、输入输出设备都可以看作是服务员，要求计 算机计算的程序是顾客在计算机网络中则可把计算机本身看作是服务员，计算程 序或指令可以从网络中的一部计算机传送到另一部计算机，这类问题通常都是以 排队网络的形式出现 2 6 两个重要的概率分布 定义2 5 1 ：如果随机变量e ( 孝) = 歹i ，d ( f ) = 专的分布律为 p e - - k ) p q k - ik = 1 ，2 ，3 ，o p 0 ) 为常数，则称随机变量x 服从参数五的负指数分布，其概率分布函 数为 胁i o ， l - e - * 。r 。 七阶原点矩e x = 等( 后= l ，2 ，) ，方差d 【x 】= 万1 8 硕士学位论文第二章预备知识 在现实生活中，大量的随机现象服从负指数分布或近似地服从负指数分布例 如，进港的船舶相近达到的间隔时间就近似地服从负指数分布由于“顾客到达流 是p o s s i o n 流”与“顾客到达间隔时间相互独立、服从相同的负指数分布”二者的等 价性，使得p o s s i o n 流在排队中具有特殊的地位特别是由于负指数分布的“无记忆 性”从而使问题的研究大大简化 2 7 泊松过程 定义2 7 1 考虑单个到达的输入过程，令( f ) 表示在时间( o ，f 】内到达的顾客 数，则 ( f ) ，f o 是连续时间参数的随机过程( 计数过程) 如果满足： 1 ( o ) = o ； 2 ( ，) ，t 0 有独立增量，即对任取的n 个时刻：o t t t 2 0 ) 的p o i s s o n 流的充分必要条件是 毛，玎1 独立、同参数名的负指数分布，其中 乙，万1 为到达的间隔时间序列 定理2 7 2 设 m ( f ) ，t o 与 2 ( f ) ，t o 分别是参数 与五的p o i s s o n 流， 且它们相互独立，则合成流 m ( f ) + 2 ( f ) ，f o 是参数 + 是的p o i s s o n 流 定理2 7 3 ( 九t 0 l 是参数五( 0 ) 的p o i s s o n 流，每一到达顾客以概率 9 硕士学位论文第二章预备知识 p ( o o ( 2 - 2 ) 的积分方程为更新方程，其中a ( t ) 和，( f ) 都是已知的，且，( ，) 是分布函数，而 l o 第二章预备知识 有限区间上，存在唯一 ( 2 3 ) l i i i l 趔：1 t - - + g o t p 定义2 8 3 一个非负随机变量x 称为是格的( 算术的) ，若存在d ( o ) ，使得 p x = n d = l ，此时也成对应的分布函数f ( x ) 是格的，否则称f ( x ) 不是格的 n = o 注：根据上述定义，连续型随机变量的分布函数是非格的，取值0 ，l ，2 的禹散 型随机变量对应的分布函数是格的 定义2 8 4 设g ( t ) 是定义在【o ，佃) 上的函数，对于任意万 0 和任意正整 数n ，令 = i n f g ( t ) ：( n - 1 ) 8 r 玎万 ，玎= 1 ，2 = s u p g ( t ) ：( n - 1 ) 8 f n s ，刀= 1 ，2 a ( 8 ) - - s e n = l ， a = 万鸠 n = l 若极限l i ma ( 8 ) 与l i m ( 艿) 都收敛于同一极限值，则称函数g ( t ) 在o ，+ o o ) o - - o 。0 - - o o 。 一 上是直接黎曼可积的 定理2 8 3 1 在【o ，佃) 上非负可积的单调函数是直接黎曼可积的 2 设g ( f ) 是定义在【o ，佃) 上的非负非降函数，口 1 为常数，若 j c o g ( ，) a - t d t l 为常数，j c o 厂( f ) a d t 为一随机过程t ，f = l ，2 ，n ，且f l ，2 乙 如果对状态空间s 中的任意状态五，屯，毛中x ( 乙) 的条件分布函数满足： p x ( 乙) xlx ( 乙一i ) = 毛- l ，x ( 乙一2 ) = 稚2 ，彳( ，1 ) = 而) = p x 也) x lx ( ，n 1 ) = 毛一1 ) ，x r 则称 z ( ，) ，t t ) ，具有无后效应性或马氏性，并称 x ( f ) ，r t ) 为马尔可夫过 程，简称为马氏过程 一般记尸 x ( 厶) xix ( 乙一1 ) = 毛一1 ) 为f ( 乙1 ，吒一l ；乙，x ) ，即 ，纯_ l ，毛一i ；乙，x ) = 尸 x ( 乙) xix ( 乙一1 ) = 毛一1 ) 称它为马氏过程的转移概率分布它满足c k 方程： 吧 f ( s ，x ；t ，y ) = if ( u ，z ；t ，y ) d , f ( s ，x ；u ，z ) ，s u t t 其中d , f ( s ，x ；u ，z ) 表示对f ( s ，x ；u ，z ) 关于变量z 微分 2 1o 马尔科夫链 定义2 1 0 1 ：设随机过程 x ( f ) ，t t ) 的状态空间s 为r 中的可列集如果对t 中任意n 个，l ，2 为离散参数马氏链如果t 是连续参数集，则称 彳( ，) ，t ) 为连续参 数马氏链 定义2 1 0 2 ：给定齐次马尔柯夫链 x ( 拧) ，刀= 0 ，l ，2 ) ，称概率分布 p ，( 0 ) = p x ( 0 ) = ，) ，j e 为 x ( 刀) ，”= o ，1 ，2 的初始分布，其中o 乃( o ) 1 且p j ( o ) = l ，而称概率 分布 非e p ，( 刀) = p r ( ，) = 歹) ，j e 为 x ) ，= o ，1 ，2 ) 的瞬间分布，它表示过程在任意时刻n 的概率分布 如果极限 p j = l i r a p j ( n ) ，e t i - - , t o o 存在，且o p j l ，乃= l ，则称 乃，e ) 为过程 x ( 刀) ，n = o ，1 ，2 的平稳 分布 严点 一个齐次马尔可夫链，如果它的每一个状态都可以从另外任意一个状态出发 经过若干步到达，即设i j 是任意两个状态，总可以找到一个正整数m ，使得，则称 该齐次马尔可夫链是不可约的，否则称为可约的 记 厶( 刀) = p 从状态j 出发经过n 步首次回到j ) 厶= p 从状态j 出发回到j ) 则 厶= 兀( 刀) n = l 若厶= 1 ，说明从状态j 出发回到j 是必然事件，则称状态j 是常返的；若厶 1 ，则称状态j 是周期的，若d = l ，则称状态j 是非周期的 进一步考虑厶= l 这种常返状态，其平均返回时间为 2 l 如= 帆( 疗) n m l 如果心 o ，则称状态j 是正常返的；若= 0 ，则称状态j 是零常返的 1 3 硕士学位论文 第二章预备知识 定理2 1 0 1 ：不可约的齐次马尔可夫链的状态或全部是正常返的，或全部是零 常返的，或全部是非常返的；如果有周期，则全部状态有相同的周期 定理2 1 0 2 ：不可约的非周期的齐次马尔可夫链的下述极限概率 ! i m 。p j ( n ) = 乃，e 总存在，且与初始状态无关进一步还有 1 ) 如果全部状态是非常返的或全部是零常返的，则 乃= 0 ，j e 此时不存在平稳分布 2 ) 如果全部状态是正常返的，则 易= 古 o 而且 p ，j 日满足等式 乃= l ，p j = p 广功( 1 ) j e e i e e 因此 p ，j e ) 是唯一的平稳分布 定理2 1 0 3 齐次不可约的连续时间参数的马尔柯夫链 x c t ) ，t 0 ) 存在平 稳分布 p j ，毋，则满足方程( p o ，a ，p x ) q = 0 这样，根据上式，结合正规化条件o s p l ，p j = l 可求得其平稳分布 j t e p ，j 毋 2 11 生灭过程 生灭过程是描述考察一个群体成员的数目时，在时间的进程中可增可减，假 定在时刻t 群体有i 个成员，在很短的时间间隔( t ，t + d t ) 中，群体数目增加或减少两个 或两个以上几乎是不可能的，它只可能增加一个或减少( 当i 0 时) 一个或保持不 变 定义2 1 1 1 ：假定有一系统，设系统具有状态集e = o ，l ，2 ，k ) 令n c t ) 表示在 时刻t 系统所处的状态，且有： 只j + i ( d t ) = p n c t + d t ) = f + l l ( ，) = f ) = a d t + o ( d t ) ，f = o ，1 ，k - 1 j - i ( d t ) = 尸 ( ，+ d t ) = i - 1 i ( ，) = f ) = l h , d t + o ( 历) ，f = l ，2 ，k b ( d f ) = p ( n ( t + d r ) = j i ( f ) = 0 = o ( o t ) ，i i - j 巨2 其中丑 0 ，一 0 ，均为常数，则称随机过程 ( f ) ，f o ) 为有限状态 e = o ，1 ，2 ， l 【) 上的生灭过程 当系统状态为可列无限状态e 芦 0 ，1 ，2 ， 时，则称为无限状态的生灭过程 令p ( f ) = 以( f ) = 办，j e ，则由全概率公式，有： 1 4 硕士学位论文第二章预各知识 p j ( t + d t ) = p n ( t + d t ) = j i ( f ) f ) p j ( t ) = 只( ，) 弓( 历) = p j ( t ) 1 一乃历一k t j d t + o ( d t ) + e l o ) 【乃一i d f + o ( d f ) 】+ e + 。( ，) 巩+ l d f + o ( 历) 】+ 只( ，) o ( d t ) = p j ( t ) 1 一a j a t 一# j a t + a j l 弓一l ( o a t + # j + l e + l ( o a t + 。( f ) 于是： p j ( t + f d t ) - p j ( t ) = 荆一( 乃+ 一) 删+ 竹鼎( ，) + 警 令jo + ，得生灭过程的微分差分方程为： 1 当e = o ，1 ，2 ，k ) 时，有 l 巧( f ) = 一九昂( r ) + h 鼻( f ) 弓( r ) = 乃一1 p j - l ( ，) 一( 乃+ t j ) p j ( t ) + , u j + l 弓+ l ( ，) ，= l ，2 ，k 一1 【 最( r ) = 一五一l 最一l ( t ) + l t k p , ( t ) 2 当e = o ，1 ，2 ，) 时，有 l 巧o ) = 一厶昂( f ) + 鸽墨( ，) 【p j ( t ) = 乃一l e l ( ，) 一( 乃+ v j ) p j ( t ) + l j + l 弓+ l ( f ) ，j = l ，2 ， 定理2 1 1 1 ：在弓( f ) 2 ；骢e ( f ) 存在的条件下，j e e ，l ，i m 。p ，：( ，) = o ，je e 在 只，e ) 存在的条件下，令f 专o o ，得平衡方程： 1 对e = o ，1 ，2 ，l 【) 有： l 凡昂= 朋日 ( t + 一) e = t 一- 一，+ 竹+ - 弓+ 。，j = 1 ，2 ，k 一1 【五一。最一，= 以最 结合丢k 。- 1 ，可解得弓= 黯豺= l ，2 ，七 其中 硕士学位论文 特别地，当凡= 五= = 乃一。= a ，一= 鸬= = 以= 时，有 弓葛矗 2 对e = 0 ，1 ，2 ，) ，有： k 鹏：筹麓。w 乩2 ， 再结合罗p = 1 ，可得只： jj j 其中， l o 磊五乃一t 氏 l t 弘j e o = 异， 凡 乃一- 队 l l 弘i 特别地，当凡= 丑= = 乃一l = 旯，“= 心 o oo = 以= 时， 只要兰 0 进入状 态f l ，其中仍= 1 也就是说，状态f l 不能变成状态- ，l ，直到发生故障后，状 态f 1 才能蔓戡状态f = 0 ，也只有在结束修理后，系统才能从状态待0 回到某一个 状态f 1 此外，当系统处于修复状态f = 0 时，到达的顾客会因没有服务会变得不耐烦而 离开系统，一旦离开则永不再回来，设顾客的不耐烦时间是相互独立的，服从参数 为f 的负指数分布 那么上述过程产生了一个二维连续时间马尔可夫过程令，表示系统的状 态，表示系统中的颓客数= f 1 ，表示系统处于某个工作状态f ，j = 0 表示系统 处于修理状态 3 2 平衡方程和生成函数 令最= p ( j = i ，三= 七) ( 扛o ，1 ，刀，k = o ，l ) ，表示系统平稳时处于状态f ，有k 个顾客的概率 令弓2 荟表示系统处于状态f 的概率 得平衡方程为 1 7 硕士学位论文 第三章m m 1 可修排队系统分析 j = o 卜0 ( 气民= i = l 仇懈t l k 1 ，( 凡+ + 蟛) 昂i = &