马尔可夫预测.doc

第6章 马尔可夫预测第6章 马尔可夫预测马尔可夫预测方法不需要大量历史资料，而只需对近期状况作详细分析。它可用于产品的市场占有率预测、期望报酬预测、人力资源预测等等，还可用来分析系统的长期平衡条件，为决策提供有意义的参考。6.1 马尔可夫预测的基本原理马尔可夫（A.A.Markov）是俄国数学家。二十世纪初，他在研究中发现自然界中有一类事物的变化过程仅与事物的近期状态有关，而与事物的过去状态无关。具有这种特性的随机过程称为马尔可夫过程。设备维修和更新、人才结构变化、资金流向、市场需求变化等许多经济和社会行为都可用这一类过程来描述或近似，故其应用范围非常广泛。6.1.1 马尔可夫链为了表征一个系统在变化过程中的特性（状态），可以用一组随时间进程而变化的变量来描述。如果系统在任何时刻上的状态是随机的，则变化过程就是一个随机过程。设有参数集，如果对任意的，总有一随机变量与之对应，则称为一随机过程。如若为离散集（不妨设），同时的取值也是离散的，则称为离散型随机过程。设有一离散型随机过程，它所有可能处于的状态的集合为，称其为状态空间。系统只能在时刻改变它的状态。为简便计，以下将等简记为。一般地说，描述系统状态的随机变量序列不一定满足相互独立的条件，也就是说，系统将来的状态与过去时刻以及现在时刻的状态是有关系的。在实际情况中，也有具有这样性质的随机系统：系统在每一时刻（或每一步）上的状态，仅仅取决于前一时刻（或前一步）的状态。这个性质称为无后效性，即所谓马尔可夫假设。具备这个性质的离散型随机过程，称为马尔可夫链。用数学语言来描述就是：马尔可夫链 如果对任一，任意的恒有 (6.1.1)则称离散型随机过程为马尔可夫链。例如，在荷花池中有N张荷叶，编号为。假设有一只青蛙随机地从这张荷叶上跳到另一张荷叶上。青蛙的运动可看作一随机过程。在时刻，青蛙所在的那张荷叶，称为青蛙所处的状态。那么，青蛙在未来处于什么状态，只与它现在所处的状态有关，与它以前在哪张荷叶上无关。此过程就是一个马尔可夫链。由于系统状态的变化是随机的，因此，必须用概率描述状态转移的各种可能性的大小。6.1.2 状态转移矩阵马尔可夫链是一种描述动态随机现象的数学模型，它建立在系统“状态”和“状态转移”的概念之上。所谓系统，就是我们所研究的事物对象；所谓状态，是表示系统的一组记号。当确定了这组记号的值时，也就确定了系统的行为，并说系统处于某一状态。系统状态常表示为向量，故称之为状态向量。例如，已知某月A、B、C三种牌号洗衣粉的市场占有率分别是0.3、0.4、0.3，则可用向量来描述该月市场洗衣粉销售的状况。当系统由一种状态变为另一种状态时，我们称之为状态转移。例如，洗衣粉销售市场状态的转移就是各种牌号洗衣粉市场占有率的变化。显然，这类系统由一种状态转移到另一种状态完全是随机的，因此必须用概率描述状态转移的各种可能性的大小。如果在时刻系统的状态为的条件下，在下一个时刻系统状态为的概率与无关，则称此马尔可夫链是齐次马尔可夫链，并记称为状态转移概率。显然，我们有转移矩阵 设系统的状态转移过程是一齐次马尔可夫链，状态空间 有限，状态转移概率为，则称矩阵 (6.1.2)为该系统的状态转移概率矩阵，简称转移矩阵。为了论述和计算的需要，引入下述有关概念。概率向量 对于任意的行向量（或列向量），如果其每个元素均非负且总和等于1，则称该向量为概率向量。概率矩阵 由概率向量作为行向量所构成的方阵称为概率矩阵。对于一个概率矩阵，若存在正整数，使得的所有元素均为正数，则称矩阵为正规概率矩阵。例如，矩阵中每个元素均非负，每行元素之和皆为1，行数和列数相同，为方阵，故矩阵A为概率矩阵。概率矩阵有如下性质：如果A、B皆是概率矩阵，则AB也是概率矩阵；如果A是概率矩阵，则A的任意次幂也是概率矩阵。对，记 (6.1.3)称为k步状态转移概率，为k步状态转移概率矩阵，它们均与n无关（从下面的式(6.1.4)也可看出）。特别，当时，为1步状态转移概率。马尔可夫链中任何k步状态转移概率都可由1步状态转移概率求出。由全概率公式可知对有（其中表示单位矩阵）：其中用到马尔可夫链的“无记忆性”和齐次性。用矩阵表示，即为，从而可得 (6.1.4)记为过程的开始时刻，则称为初始状态概率向量。如已知齐次马尔可夫链的转移矩阵以及初始状态概率向量，则任一时刻的状态概率分布也就确定了：对，记，则由全概率公式有 (6.1.5)若记向量，则上式可写为 (6.1.6)由此可得， (6.1.7)例6.1 考察一台机床的运行状态。机床的运行存在正常和故障两种状态。由于出现故障带有随机性，故可将机床的运行看作一个状态随时间变化的随机系统。可以认为，机床以后的状态只与以前的状态有关，而与过去的状态无关，即具有无后效性。因此，机床的运行可看作马尔可夫链。设正常状态为1，故障状态为2，即机床的状态空间由两个元素组成。机床在运行过程中出现故障，这时从状态1转移到状态2；处于故障状态的机床经维修，恢复到正常状态，即从状态2转移到状态1。120.90.20.10.8图6.1 机床的状态转移现以一个月为时间单位。经观察统计，知从某月份到下月份机床出现故障的概率为0.2，即。其对立事件，保持正常状态的概率为。在这一时间，故障机床经维修返回到正常状态的概率为0.9，即；不能修好的概率为。机床的状态转移情形见图6.1。由机床的一步转移概率得状态转移概率矩阵若已知本月机床的状态向量，现要预测机床两个月后的状态。先求出两步转移概率矩阵矩阵的第一行表明，本月处于正常状态的机床，两个月后仍处于正常状态的有0.82，转移到故障状态的有0.18。第二行说明，本月处于故障状态的机床，两个月后转移到正常状态的有0.81，仍处于故障状态的有0.19。于是，两个月后机床的状态向量6.1.3 稳态概率矩阵在马尔可夫链中，已知系统的初始状态和状态转移概率矩阵，就可推断出系统在任意时刻可能所处的状态。现在需要研究当不断增大时，的变化趋势。1 平稳分布若存在非零概率向量，使得，其中为一概率矩阵，则称为的固定概率向量。特别，设为一状态概率向量，为状态转移概率矩阵。若 (6.1.8)即则称为马尔可夫链的一个平稳分布。若随机过程某时刻的状态概率向量为平稳分布，则称过程处于平衡状态。一旦过程处于平衡状态，则过程经过一步或多步状态转移之后，其状态概率分布保持不变，也就是说，过程一旦处于平衡状态后将永远处于平衡状态。对于我们所讨论的状态有限（即N个状态）的马尔可夫链，平稳分布必定存在1。特别地，当状态转移矩阵为正规概率矩阵时，平稳分布唯一。此时，求解方程(6.1.8)，即可得到系统的平稳分布。2 稳态分布对概率向量，如对任意的均有 (6.1.9)则称为稳态分布。此时，不管初始状态概率向量如何，均有或这也是称为稳态分布的理由。设存在稳态分布，则由于下式恒成立，就得 (6.1.10)即，有限状态马尔可夫链的稳态分布如存在，那么它也是平稳分布。对任一状态i，如果的公约数为1，则称i是非周期状态。如果一个马尔可夫链的所有状态均是非周期的，则称此马尔可夫链是非周期的。对非周期的马尔可夫链，稳态分布必存在，对不可约非周期的马尔可夫链，稳态分布和平稳分布相同且均唯一1。例6.2 设一马尔可夫链的转移矩阵为求其平稳分布及稳态分布。解：（1）P不可约，仅当且时。又，由定义可知，P是不可约的。（2）P非周期由可知1，2的公约为1，故状态1为非周期状态。同理可得2，3均为非周期状态。故P是非周期的。（3）由于P不可约且是非周期的，求解如下方程组得 这就是该马尔可夫链的稳态分布，而且也是平稳分布。6.2 马尔可夫预测的应用马尔可夫预测乃是利用某一系统的现在状况及其发展动向去预测系统未来状况的一种预测方法。它在技术与经济发展以及现代企业的经营管理中，均可为决策者制定决策提供较科学的未来信息。马尔可夫预测范围广泛，如在预测企业的发展规模和产品销售份额，分析顾客（消费者）流向，选择销售及服务地点，选择销售维修策略，制定设备更新方案，以及决定最优工作分配等方面均有显著成效。应用马尔可夫分析，对环境保护、生态平衡等复杂大系统未来状况进行预测，对各种环境污染治理策略的选择等，均可取得良好的效果。6.2.1 市场占有率的预测我们结合例题来说明如何预测市场占有率。例6.3 伍迪公司、布卢杰.里维公司、雷恩公司(分别用符号 A、B、C代表)是美国中西部地区三家主要灭虫剂产商。根据历史资料得知，公司A、B、C产品销售额的市场占有率分别为50%，30%，20%。由于C公司实行了改善销售与服务方针的经营管理决策，使其产品销售额逐期稳定上升，而A公司却下降。通过市场调查发现三个公司间的顾客流动情况如表6.1所示。其中产品销售周期是季度。现在的问题是按照目前的趋势发展下去，A公司的产品销售额或客户转移的影响将严重到何种程度？更全面的，三个公司的产品销售额的占有率将如何变化？表6.1 A、B、C三公司的顾客流动情况公司周期0的顾客数周期1的供应公司ABCA500035005001000B30003002400300C20001001001800周期2的顾客数390030003100将表6.1中的数据化为转移概率将对研究分析未来若干周期的顾客流向更为有利。表6.2列出了各公司顾客流动的转移概率。表6.2中的数据是每家厂商在一个周期中的顾客数与前一周期的顾客数相除所得。表中每一行表示某公司从一个周期到下一个周期将能保住的顾客数的百分比，以及将要丧失给竞争对手的顾客数的百分比。表中每一列表示各公司在下一周期将能保住的顾客数的百分比，以及该公司将要从竞争对手那里获得顾客数的百分比。表6.2 顾客流动的转移概率公司ABCA3500/5000=0.7500/5000=0.11000/5000=0.2B300/3000=0.12400/3000=0.8300/3000=0.1C100/2000=0.05100/2000=0.051800/2000=0.95如用矩阵来表示表6.2中的数据，那么就得到了如下的转移矩阵 (6.2.1)P中数据表示一个随机挑选的顾客，从一个周期到下一个周期仍购买某一公司产品的可能性或概率。如，随机挑选一名A公司的顾客，他在下一周期仍购买A公司产品的概率为0.7，购买B公司产品的概率为0.1，购买C公司产品的概率为0.2。1. 未来各周期市场占有率的计算以A、B、C公司作为我们要分析的系统的状态，那么状态概率向量就分别为三家公司的产品销售额的市场占有率。初始状态概率向量为转移矩阵由（6.2.1）式给出。于是可用式（6.1.6）来计算未来各期的市场占有率。如状态转移一次后第一周期的市场占有率向量为：由式（6.1.6）可以递推地求得未来各期的市场占有率。2. 稳态市场占有率从转移矩阵P中可以看出，A公司的市场占有率将逐期下降，而C公司的市场占有率则将逐期上升（用式(6.1.6)计算出即可验证）。从经营决策和管理的角度来看，自然希望了解公司的市场占有率最终将达到什么样的水平，亦即需要知道稳态市场占有率。由于式(6.2.1)中的P是不可约非周期的，所以稳态市场占有率即为平衡状态下的市场占有率，亦即马氏链的平稳分布。由前面的讨论知道，我们求解如下方程组解得亦即，A、B、C三家公司的市场占有率最终将分别达到17.65%，23.53%，58.82%。对本例来说，当销售份额达到平衡时，所有公司都各占总销售额中的一部分保持不变。但在某些情况下，参与竞争的公司或厂商中能有一个或多个被完全逐出市场。例如对于转移矩阵厂商A从B与C双方得到顾客，而从不失去顾客，容易推知照此趋势发展下去厂商A 将独占100%的市场。这一点从式(6.1.8)的求解中亦可看出。最后我们指出平衡状态存在的条件与初始状态概率向量无关。3. 销售策略对市场占有率的影响从本例的上述分析可以看出，A公司的市场占有率将从50%降至最终的17.65%, 当然这是假定以状态转移概率保持不变作为分析的前提的。如果公司的经营决策者看到了这种不利趋势，并制订某种策略(如销售策略)来扭转这种不利趋势，使公司在市场上保持较有利的地位。以后我们就两种不同的销售策略，讨论如何利用马尔可夫分析帮助公司管理人员评价销售策略对销售份额的影响。可类似分析其它的经营策略。1) 保留策略，指尽力保留公司原有顾客较大百分比的各种经营方针与对策。如采用提供优质服务或对连续两期购货的顾客实行折价优待等方法。设公司采用这样的保留策略后，减少了其原有顾客向公司的流失，使保留率从原来的70提高到85，则转移矩阵成为新的平衡状态下、三公司的市场占有率分别为31.6，26.3，42.1，公司的市场占有率从17.65提高到31.6。2) 争取策略。指从竞争者拥有的顾客中争取顾客的各种经营方针与对策。如通过广告等方法。设公司通过争取策略，能从上一周期内向另外两家公司购货的顾客中各争取15，则转移矩阵成为在新的平衡状态下，、三家公司的市场占有率分别为33.3，22.2，44.5。在实际工作中，市场占有率仅仅是经营者制订决策的一个考虑因素。为制订出正确的决策，还可能要考虑其它的因素，如考虑采取策略的费用等。6.2.2 期望报酬预测一个与经济有关的马氏型随机系统中，系统获得的报酬(或称收益)也会随状态的不同而不同。设有一台机器，它在第n周期的状态用表示：进一步假定，机器正常时，每一个周期可带来v元的收益，并且在下一周期失效的概率为p，当机器失效时，需对其进行更换，更换的费用为d，修理时间为一个周期，下一个周期初修好开始工作，于是是一个齐次马氏链，其状态空间为S=0,1，转移矩阵为但这是一个带报酬(或称收益、费用)的马氏链。一般地,设是状态空间为的齐次马氏链，其转移矩阵为。设r(i)表示某周期系统处于状态i时获得的报酬。我们称如此的马尔可夫链是具有报酬的。显然，r(i)0时称为盈利，报酬，收益等；r(i)0时称为亏损，费用等。对于这样一个带报酬的马尔可夫链，n 时的报酬是一个随机变量。我们分三种目标函数来讨论。1 有限时段期望总报酬记表示初始状态为i的条件下，到第k步状态转移前所获得的期望总报酬(k1，iS)：若记列向量,则上式可写为 (6.2.2)进而，可证明有如下递推式： (6.2.3)于是可用上式递推求得。2 无限时段单位时间平均报酬对iS，定义初始状态为i的无限时段单位时间平均报酬为：记西沙洛极限矩阵，则由(6.2.2)可证得 (6.2.4)于是为求，只须求得P*即可，但一般地要求出P*并不是件容易的事情。这里我们只讨论如下的特殊情况。我们考虑稳态分布存在的这种特殊情况。由上节可知，转移矩阵P非周期即可保证存在。当存在时，它也是平稳分布，于是我们有如下结论。结论 设所考虑的马氏链存在稳态分布，则的西沙洛极限与其极限相同,而,进而若(6.1.10)有唯一解，则有 (6.2.5)实际上，如果存在，当(6.1.10)有唯一解X时，由于稳态分布必为平稳分布,故特别，对于不可约非周期的马氏链，(6.2.5)恒成立。于是可先求解(6.1.10)得X，然而由(6.2.5)求得。3无限时段期望折扣总报酬在现实生活中，今年的一元钱将大于明年的一元钱，其实将钱存于银行即可。也就是说明年的一元钱折算到现在计算，就不值一元钱了，如为(0,1)，这个就称为折扣因子。实际上，在工程问题中，在企业管理中当考虑贷款、折旧等时都必须考虑到钱的增值问题。如将钱存于银行，年息为，则与有如下关系：=1/(1+)如果一个周期为一个月，那么只须将理解为月息即可。这里折扣因子一般地在区间(0,1)中。对有报酬的马氏链，定义从状态出发的无限时段期望折扣总报酬为 (6.2.6)于是 (6.2.7)若记向量，则上式的向量/矩阵形式为: (6.2.8)与有限时段中的(6.2.3)类似，由(6.2.7)可得： (6.2.9)显然，线性方程组(6.2.9)的解即为(6.2.8)所表示的。我们称为具有报酬的马氏链的三种目标函数。利用其中的任一个目标函数，我们可以讨论不同策略的优劣。例6.4 最佳维修策略的选择。我们研究一化工企业对循环泵进行季度维修的过程。该化工企业对泵进行定期检查，每次检查中，把泵按其外壳及叶轮的腐蚀程度定为五种状态中的一种。这五种状态是：状态1：优秀状态，无任何故障或缺陷；状态2：良好状态，稍有腐蚀；状态3：及格状态，轻度腐蚀；状态4：可用状态，大面积腐蚀；状态5：不可运行状态，腐蚀严重。该公司可采用的维修策略有以下几种。单状态策略：泵处于状态5时才进行修理，每次修理费用为500元。两状态策略：泵处于状态4和5时进行修理，处于状态4时的修理费用每次为250元, 处于状态5时的每次修理费用为500元。三状态策略：泵处于状态3,4,5时进行修理，处于状态3时的每次修理费用为200元,处于状态4和5时的修理费用同前。目前，该公司采用的维修策略为“单状态”策略。假定不管处于何种状态，只要进行修理，泵的状态都将在本周期内恢复为状态1。已知在不进行任何修理时的状态转移概率，如表6.3中所示。表6.3 不修理时的状态转移概率泵在周期n的状态泵在周期n+1的状态1234510.000.600.200.100.1020.000.300.400.200.1030.000.000.400.400.2040.000.000.000.500.5050.000.000.000.001.00现在我们要确定哪个策略的费用最低。目标为长期运行单位时间平均报酬。容易看出，在单状态、两状态、三状态下的转移概率矩阵分别为 下面我们分别来求三种策略下的。1)单状态策略。此时r(1)r(2)r(3)r(4)0，r(5)500，将代入(6.1.8)可解得唯一的平稳分布为 而显然是不可约非周期的，从而 X亦为稳态分布，由此及(6.2.4)，(6.2.5)可得=5000.19999.50(元)，与无关。2)两状态策略。r(1)r(2)r(3)0，r(4)250，r(5)500，与1)中类似，可知(0.266,0.228,0.241,0.168,0.097)从而由(6.2.4)，(6.2.5)有0.168250+0.097500=90.50(元).3)三状态策略。r(1)r(2)0，r(3)200，r(4)250，r(5)500，于是因此，两状态策略为最优策略，平均每周期的费用为90.50元。从上面的计算发现，均与无关。其实