随机运筹学-5.

随机运筹学之5马尔科夫过程马尔科夫过程简介马尔科夫过程是由前苏联数学家A.A.Markov在1906年首先提出和研究的一类重要的随机过程，并且因此而得名。目前，已经成为内容十分丰富、理论上相当完整、应用十分广泛的一门数学分支。在自然科学、工程技术、信息理论、自动控制、数值计算、近代物理、交通运输、生物科学及经济管理各领域中都有广泛的应用，使得现代科学家与工程技术人员越来越重视马尔科夫过程的理论及其应用的研究。壹、马尔科夫过程一、随机过程为了表示一个系统的特征，可以用一组随时间进程而变化的变量来加以描述。如果系统在任何时点上的特性或状态是随机性的，则系统的变化过程就对应于由一组随机变量构成的过程，即随机过程。从理论上说，由一簇无穷多个随机变量组成的集合称为随机过程。通常记为{x（t），t∈T}，其中xt——在同一状态空间E中取值的随机变量；T——参数集。若T为可数参数集，则{x（t），t∈T}为离散参数的随机过程。若T为不可数参数集，则{x（t），t∈T}为连续参数的随机过程。过程在各个时点上的状态空间可以是有限或可数多个离散性状态，也可以取任意连续性状态。二、马尔科夫过程的定义定义1具有无后效性的随机过程称为马尔科夫过程，简称马氏过程。定义2无后效性是指：当过程在时刻tm所处的状态为已知时，过程在大于tm的时刻t所处状态的概率特性只与过程在tm时刻所处的状态有关，而与过程在tm时刻以前的状态无关。例某企业实行技术人员在生产部门、技术部门和销售部门轮换工作的制度，以便使技术人员具有多方面的实际工作经验。轮换的办法是采取随机形式，每半年轮换一次。每个技术人员下一轮所去的部门并不是机会均等的，也可能在原部门再工作一轮。三、马尔科夫过程的类型对马尔科夫过程{X（t），t∈T}，按参数集T和状态空间（值域）S的情况一般可分为下列四类：1、时间离散、状态离散的马尔科夫过程通常将这类马尔科夫过程称为马尔科夫链，简称马氏链。2、时间离散、状态连续的马尔科夫过程3、时间连续、状态离散的马尔科夫过程4、时间连续、状态连续的马尔科夫过程四、实例例1（直线上的随机游动）一个质点在零时刻处于实数轴上的原点的位置。每隔单位时间右移或左移一个单位长度，右移的概率为p（0p1），左移的概率为q，其中q=1-p。记质点在第n时刻的位置为X（n），n=0，1，2，…。质点在直线上的移动是随机的，故称之为质点在直线上的随机游动。例2电话交换站在t时刻前来到的呼唤次数X（t）（即时间[0，t]内来到的呼唤数）是一个随机过程。已知现在tm时刻前来到的呼唤次数，未来时刻t（ttm）前来到的呼唤数只依赖于tm时刻前来到的呼唤数，这是因为[0，t]内来到的呼唤数等于[0，tm]时间内来到的呼唤次数加上（tm，t]时间内来到的呼唤数，而（tm，t]时间内来到的呼唤数与tm以前来到的呼唤数相互独立。因此，X（t）具有无后效性，是马尔科夫过程。例3（布朗运动）将一颗小花粉放在水面上，由于水分子的冲击，使它在液面上随机地运动。这种游动物理上称为布朗运动。在水面上作一平面直角坐标系，不妨取花粉的起始位置为坐标原点。考察在t时刻花粉所处位置的x坐标，记为X（t）。由于tm时刻后花粉的位置仅依赖于现在（tm时刻）的位置，而与过去花粉的位置无关，所以花粉随机游动具有无后效性。因而，X（t）也具有无后效性，是马尔科夫过程。同样地，花粉位置的Y（t）也是马尔科夫过程。例4（疾病死亡模型，Fix-Neyman（1951））考虑一个包含两个健康状态S1和S2以及两个死亡状态S3和S4（即由不同原因引起的死亡）的模型。若个体病愈，则认为它处于状态S1；若患病，则认为它处于S2，个体可以从S1和S2进入S3和S4。这是一个马尔科夫过程。例5（赌徒破产或带吸收壁的随机游动）系统的状态是0到n，反映赌博者A在赌博期间拥有的钱数，当他输光或拥有钱数为n时，赌博停止；否则，他将持续赌博，每次以概率p赢得1，以概率q=1-p输掉1。这个系统也是马尔科夫过程。例6例5中当A输光时，将获得赞助1让他继续赌下去，其余条件不变，则这个也是马尔科夫过程。例7（自由随机游动）设一个球在全直线上做无限制的随机游动，它的状态为0，±1，±2，…。这个系统也是马尔科夫过程。贰、马尔科夫链一、马尔科夫链的定义定义1设随机序列{X（n），n=0，1，2，…}的离散状态空间为E。若对于任意m个非负整数n1，n2，…，nm（0≦n1n2…nm）和任意自然数k，以及任意i1，i2，…，im，j∈E，满足P{X（nm+k）=j|X（n1）=i1，X（n2）=i2，…，X（nm）=im}=P{X（nm+k）=j|X（nm）=im}，则称{X（n），n=0，1，2，…}为马尔科夫链。在马尔科夫链中，过程在每一时点（或每一步）上的状态取决于，而且仅仅取决于过程在紧前时点或紧前步上的状态。也就是说，已知系统的当前状态，就足以预计系统在下一步上出现某一状态的可能性，而不必考虑系统在过去曾经到达的状态，以及如何到达目前状态的过程。定义2条件概率P{X（nm+k）=j|X（nm）=im}称为马尔科夫链在n时刻的k步转移概率，记为pij（n，n+k）。转移概率表示已知n时刻处于状态i，经k个单位时间后过程处于状态j的概率。定义3若转移概率pij（n，n+k）是不依赖于n的马尔科夫链，称为齐次（时齐）马尔科夫链。齐次马尔科夫链的状态转移概率仅与转移出发状态i、转移步数k、转移到达状态j有关，而与转移的起始时刻n无关。k步转移概率可记为pij（k）。当k=1时，pij（1）称为一步转移概率，简记为pij。一步转移概率具有下列两个性质：（1）非负性0≦pij≦1，i，j=1，2，…（有限个或无限个）；（2）∑jpij=1，i=1，2，…。一步转移概率可写成矩阵形式：1、对有限状态空间E={1，2，…，N}，矩阵为P=（pij）N×N，为方阵。2、对无限状态空间E={1，2，…}，矩阵为P=（pij…），为无限矩阵。检验随机过程是否为马尔科夫链的定理：定理1设随机过程{Xn，n≧0}满足：（1）Xn=f（Xn-1，ξn）（n≧1），其中f：S×S→S，且ξn取值在S上；（2）{ξn，n≧1}为独立同分布随机变量，且X0与{ξn，n≧1}也相互独立，则{Xn，n≧0}是马尔科夫链，而且其一步转移概率为pij=P（f（i，ξ1）=j）。一般地说，独立同分布的离散随机变量序列{X（n），n=0，1，2，…}也是马尔科夫链。二、实例例1（伯努利试验）设伯努利试验每次试验“成功”的概率为p（0p1），“失败”的概率为q（q=1-p）；且各次试验是相互独立的。“成功”用状态“1”表示，“失败”用状态“2”表示。第n次试验的结果记为X（n），进行无限多次试验得{X（n），n=0，1，2，…}。例2（直线上带吸收壁的随机游动）一质点只能处在实数轴上1，2，3，4，5五个点的位置。当它处在2，3，4位置时，下一时刻右移一格的概率为p（0p1），左移一格的概率为q（q=1-p）。当质点处在1位置时，它永远停留在1上；又当质点处在5位置时，它永远停留在5位置上。把1和5点看作分别放置有吸收壁。质点的随机游动用{X（n），n=0，1，2，…}表示，其中X（n）表示第n时刻质点的位置。判断随机游动，若是马尔科夫链求其一步转移概率矩阵。例3（直线上带反射壁的随机游动）设0p1，q=1-p。一质点只能处在实数轴上1，2，3，4，5五个点的位置。当它处在2，3，4位置时，下一时刻右移一格的概率为p，左移一格的概率为q。当质点处于1位置时，下一时刻留在原位置的概率为q，右移一格的概率为p；当质点处于5位置时，下一时刻左移一格的概率为q，留在原位置的概率为p，可看作在1，5位置分别放置有反射壁。求其一步转移概率矩阵。例4（直线上带完全反射壁的随机游动）设0p1，q=1-p。一质点只能处在实数轴上1，2，3，4，5五个点的位置。当它处在2，3，4位置时，下一时刻右移一格的概率为p，左移一格的概率为q。当质点处于1位置时，下一时刻必定移到2位置；当质点处于5位置时，下一时刻必定移到4位置，可看作1，5位置分别放置具有完全弹性的反射壁。求其一步转移概率矩阵。例5（直线上带完全反射壁的随机游动）设0p，0q，0r，p+q+r=1。一质点只能处在实数轴上1，2，3，4，5五个点的位置。当它处在2，3，4位置时，下一时刻保留在原来位置的概率为r，右移一格的概率为p，左移一格的概率为q。当质点处于1位置时，下一时刻必定移到2位置；当质点处于5位置时，下一时刻必定移到4位置。求它的一步转移概率矩阵。例6（艾伦费斯特（Ehrenfest）模型，著名的粒子通过薄膜进行扩散过程的数学模型）一质点在状态空间E={-a，-a+1，…，-1，0，1，2，…，a}中作随机游动，且带有两个反射壁a和-a，其一步转移概率是：q≥0，原地不动的概率为r≥0（p+q+r=1），且各次移动相互独立，以Xn表示质点经n次移动所处的位置，则{Xn，n≥0}是一马尔科夫链，且pi，i+1=p，pi，i-1=q，pi，i=r，其余pij=0。例7（机械可靠性）某公司生产了一种机器，要么正常，要么坏掉。如果在某一天开始工作时，这种机器是正常的，那么它在第二天开始工作时也是正常的概率为0.98；否则将以0.02的概率坏掉。一旦机器坏掉，公司将派修理工前去修理。如果机器在某一天开始工作时坏掉，它在第二天开始工作时也坏掉的概率为0.03；否则，机器将修理完毕并以0.97的概率正常工作。假定该公司使用两台相同的机器，并且这两台机器彼此独立运行，每台机器都有自己的修理工。若Yn是第n天开始时处于正常工作状态的机器数，则{Yn，n≧0}是离散时间的马尔科夫链，求其转移矩阵。例8（天气模型）Heavenly市的天气被分为晴天、多云和雨天。假定明天的天气仅与今天的天气有关，其关系如下：若今天是晴天，则明天有0.3的概率是多云天气，有0.2的概率是雨天天气；若今天是多云天气，则明天有0.5的概率是晴天天气，有0.3的概率是雨天天气；若今天是雨天天气，则明天有0.4的概率是晴天天气，有0.5的概率是多云天气。则天气模型是马尔科夫链模型。例9（库存系统模型）某计算机公司储存一批PC机供零售。该公司从星期一早上8：00到星期五晚上5：00营业。并且采用以下的经营策略来控制奔腾PC机的库存：在星期五下午5：00，仓库管理员检查有多少奔腾PC机仍在库存。如果库存数目少于2台，仓库管理员就需要订购足够的PC机，以使总库存在下一周营业日开始的星期一达到5台。如果库存数目2台或更多，则不采取任何行动。而一周内市场上对PC机的需求服从参数为3的泊松分布，并且任何需求如果不能立即满足就会丧失这个机会。试建立该公司的奔腾PC机库存的随机模型。例10（生产系统模型）某公司有两台机器组成的生产设备，每台机器每小时生产一个零部件，并且每个零部件可以立即测试以检验有无缺陷。令ai为机器i生产的零部件无缺陷的概率，i=1，2。有缺陷的零部件立即抛弃，而每台机器生产的无缺陷的零部件则被储存在两个分离的箱子里。当每个箱子里储存有零部件时，则这两个箱子立即调集起来运走。每个箱子至多容纳2个零部件。当一个箱子装满，则相应的机器就关掉。只有当箱子有空间容纳至少一个零部件时才重新启动机器。试建立这个系统模型。例11（人力资源计划模型）某公司是一家保险公司，它的100名工人被分成1，2，3，4等4个等级。假定工人只在某一周之初可以从一个等级晋升到另一个等级，或者离开公司。等级1的工人在一周之初晋升到等级2的概率为0.03，或者离开公司的概率为0.02，或者继续呆在原来等级到下一周之初。等级2的工人在一周之初晋升到等级3的概率为0.01，或者离开公司的概率为0.008，或者继续呆在原来等级到下一周之初。等级3的工人在一周之