运筹学思想方法及应用 ch8 马尔可夫预测方法

2023/2/51第八章马尔可夫预测方法运筹学OperationalResearch2023/2/52马尔可夫预测（MarkovForecast）也称为马尔可夫分析，作为一种企业管理的工具,已经成功地应用到许多场合.它的优点在于依靠现在资料推知未来,计算比较精确,适用于中、长期预测.因此，较多地应用于市场需求等诸多领域的预测.2023/2/538.1马尔可夫过程定义及其性质8.2遍历性定理与平衡态预测8.3马尔可夫预测的应用8.4WinQSB软件应用2023/2/548.1马尔可夫过程定义及其性质2023/2/558.1马尔可夫过程定义及其性质

1.马尔可夫及其马尔可夫过程马尔可夫（A.Markov，1856—1922）俄国数学家.1878年大学毕业于彼得堡大学数学系，1884年获物理数学博士学位，1886年成为教授，1896年当选为彼得堡院士.对概率论、数理统计、数论、函数逼近论、微分方程、数的几何等都有建树.他开创了一种无后效性随机过程的研究，即在已知当前状态的情况下，过程的未来状态与其过去状态无关，这就是现在大家熟悉的马尔可夫过程.马尔可夫的工作极大的丰富了概率论的内容，促使它成为自然科学和技术直接有关的最重要的数学领域之一.2023/2/568.1马尔可夫过程定义及其性质我们先介绍几个与马尔科夫过程相关的概念.

随机变量与随机过程把随机现象的每个结果对应一个数，这种对应关系称为随机变量.例如某一时间内公共汽车站等车乘客的人数，电话交换台在一定时间内收到的呼叫次数等等，都是随机变量的实例.

随机过程随机过程是一连串随机事件动态关系的定量描述.

马尔科夫过程与马尔科夫链设x(t)是一随机过程，当过程在时刻t0所处的状态为已知时，时刻t（t>t0）所处的状态与过程在时刻t0之前的状态无关，这个特性成为无后效性.无后效的随机过程称为马尔科夫过程(MarkovProcess).马尔科夫过程中的时间和状态既可以是连续的，又可以是离散的.我们称时间离散、状态离散的马尔科夫过程为马尔科夫链.2023/2/578.1马尔可夫过程定义及其性质为了形象说明“状态”和“状态的转移”的概念，假设在一个水池中有三片荷叶，一只青蛙在三片荷叶之间跳跃玩耍，见图.观察青蛙的活动会发现青蛙的动作是随意的.为讨论方便，我们给荷叶编号，我们关心的是在一定时间内，它从一片荷叶跳到其他两片荷叶的转移结构.当青蛙在第1片荷叶上时，它下一步动作跳跃到第2、3片荷叶上或原地不动，只与现在的位置1有关，而与它以前跳过的路径无关.我们给出这只青蛙从各片荷叶上向另一片荷叶移动的转移图，见图.2023/2/588.1马尔可夫过程定义及其性质箭头表示跳跃的方向，数字表示跳跃的概率，白环表示青蛙保持不动.此图表明：在一定时间内，当青蛙开始时刻在第1片荷叶上时，它保持不动的概率为0.3，它跳跃到第2片荷叶上的概率为0.6，跳跃到第3片荷叶上的概率为0.1；当青蛙开始时刻在第2片荷叶上时，它保持不动的概率为0.4，它跳跃到第1片荷叶上的概率为0.2，跳跃到第3片荷叶上的概率为0.4；当青蛙开始时刻在第3片荷叶上时，它保持不动的概率为0.5，它跳跃到第1片荷叶上的概率为0.2，跳跃到第2片荷叶上的概率为0.3.2023/2/598.1马尔可夫过程定义及其性质我们以x(t)表示青蛙跳跃t次后所处的位置,x(t)的取值叫做状态，S={1,2,3}叫状态空间.我们称{x(t)}(t>0)为一个随机过程.当从x(0)到x(t)已知时，青蛙在t+1时处在x(t+1)状态上的概率仅与t时刻状态有关，即满足以下关系式

（8.1）

我们称满足（8.1）式的随机过程{x(t)}(t>0)为马尔可夫过程或马尔可夫链，而把（8.1）式的随机过程{x(t)}称为马尔可夫性，它反映了前一状态x(t-1)

、现状态x(t)和后一状态x(t+1)之间的链接.因此，用马尔可夫链描述随机性状态变量的变化时，只需求在某一点上两个相邻随机变量的条件分布就可以了.2023/2/510我们称为转移概率.由于这种转移概率不依赖于时间，因此具有稳定性，我们用常数来表示.将各个状态之间的转移概率用一个矩阵表示出来，就得到一个马尔科夫问题（有限状态稳定的马尔可夫过程问题）的数学模型：2023/2/5118.1马尔可夫过程定义及其性质称矩阵为一步概率转移矩阵，简称转移矩阵.由于转移矩阵的每行都是独立的分布，所有每行的元素满足下列性质：（8.2）

（8.3）2023/2/5128.1马尔可夫过程定义及其性质

2.马尔可夫链的基本方程

马尔可夫性质的数学描述是：对任意的时间及任意的状态i,j,i1，…，it,都有由图8.2，青蛙跳跃的一步转移矩阵为

2023/2/5138.1马尔可夫过程定义及其性质其中为一步转移概率.如果用矩阵表示步转移概率组成的矩阵,（8.5）式的矩阵表达式为如果x(t)是齐次的（即对一切状态i,j,条件概率（8.4）（8.5）（8.6）与m的取值无关）,则2023/2/514称（8.5）或（8.6）式为柯尔莫哥洛夫—卡普曼方程,简记为K-C方程.

特别地,8.1马尔可夫过程定义及其性质（8.7）其中为系统经过步转移后处于状态的概率.（8.8）

或者,同理有.设从（8.4）式,易见有2023/2/5158.1马尔可夫过程定义及其性质记为系统的初始状态向量,则（8.8）式的前一等式可表示为

由于,故有（8.9）由上述内容可以看到,应用马尔可夫预测法的关键是要找出所考察系统的一步转移矩阵及初始状态向量..2023/2/516下面通过实例理解上述的预测模型.【例8.1】设任意相继的两天中，雨天转晴天的概率为1/3，晴天转雨天的概率为1/2，任一天晴或雨是互为逆事件.以0表示晴天状态，以1表示雨天状态，表示第8.1马尔可夫过程定义及其性质

天状态（0或1）.试写出马尔可夫链的一步转移概率矩阵；又已知10月1日为晴天，问10月3日为晴天、10月5日为雨天的概率各等于多少？解由于任一天晴或雨是互为逆事件，而且雨天转晴天的概率为1/3，晴天转雨天的概率为1/2，故一步转移概率矩阵分别为

2023/2/5178.1马尔可夫过程定义及其性质由于故一步转移概率矩阵为2023/2/5188.1马尔可夫过程定义及其性质故10月1日为晴天，10月3日为晴天的概率为10月1日为晴天，10月5日为雨天的概率为2023/2/5198.1马尔可夫过程定义及其性质【例8.2】已知,上月共销售100万包洗衣粉,其中、、三种牌号各为30万包、40万包、30万包.又知本月与下月市场客量不变.试预测本月和下月三种牌号洗衣粉的市场占有率,并给出从本月起第六个月的市场占有率.

解将上月市场占有率写成向量形式，也即初始状态向量转移矩阵为2023/2/5208.1马尔可夫过程定义及其性质则本月市场占有率应为下月市场占有率应为2023/2/5218.1马尔可夫过程定义及其性质由此可知：本月A、B、C三种牌号的洗衣粉预测销售量依次为25万,37万,38万包；下月则依次为22.5万,34.7万,42.8万包.

从本月算起第六个月的市场占有率为2023/2/5228.1马尔可夫过程定义及其性质可见A、B、C三种牌号洗衣粉的市场占有率,随着月数的增长,,两种牌号洗衣粉的市场占有率逐期下降,而牌号洗衣粉的市场占有率却逐月上升.如果三个厂家都不采取竞争手段,如此发展下去,最终市场占有率将会是什么样呢？利用马尔可夫链的遍历性定理可以回答这个问题.2023/2/5238.2遍历性定理与平衡态预测2023/2/5248.2遍历性定理与平衡态预测

遍历性定理如果存在一个整数s,使对一切的状态i或j均有pij(s)>0

，则极限

1.遍历性与遍历性定理设齐次马尔可夫链的状态空间为

，若对所有的

转移概率

都存在极限

（不依赖于

），则称该马尔可夫链具有遍历性.

对任意状态或存在（注意：极限与起始状态无关）,同时,这些极限是（8.10）2023/2/5258.2遍历性定理与平衡态预测

（8.11）

及条件的唯一解（证明略）.方程组（8.10）式用矩阵表示,即2023/2/5268.2遍历性定理与平衡态预测记（8.12）我们称为转移矩阵的固有概率向量,应满足条件（8.11）2.平衡预测态遍历性定理告诉我们,如无新的外界影响改变转移概率,则系统早晚会进入平衡状态.这对管理决策十分有用.2023/2/5278.2遍历性定理与平衡态预测.设【例8.3】

（例8.2续）求稳定状态时A、B、C三种洗衣粉的市场占有率,也就是求出最终市场占有率.解由遍历性定理,我们只需求出方程组（8.12）满足条件（8.11）的唯一解.这等价于求出转移矩阵的满足条件（8.11）的固有概率向量则由（8.12）式2023/2/5288.2遍历性定理与平衡态预测即由解出2023/2/5298.2遍历性定理与平衡态预测这表明A、B、C三种洗衣粉的最终市场占有率分别为20%,30%,50%.如果生产A牌洗衣粉的A厂对此严峻的市场局面,决定采取竞争手段.经过分析认为,采取加强广告宣传的手段,可以改变转移概率,使得买B和C牌的顾客有一部分转而购买A牌.假设改变后的转移概率为即得新的转移矩阵2023/2/5308.2遍历性定理与平衡态预测利用上述同样方法,可求出最终市场占有率为A牌占33.3%,B牌占26.7%,C牌占40%.这正是A厂利用马尔可夫预测进行决策的优势.2023/2/5318.2遍历性定理与平衡态预测【例8.4】某市场销售A、B、C三厂家生产的汽车备件,经过市场调查分析得知：市场容量为10万户；转移矩阵P为

问题：A厂通过加强广告宣传的手段,使最终市场占有率提高了13.3%,所带来的经济效益是否大于广告费用？因为只有此种手段带来的经济效益大于广告费用时,采用此种手段竞争才是可行的.这类问题又如何分析呢？请看下例.本月

上月

ABC

ABC2023/2/5328.2遍历性定理与平衡态预测矩阵中第1行元素0.4，0.3，0.2分别表示：上月为A厂的客户，本月仍为A厂的客户占40%，本月转为B厂的客户占30%，本月转为C厂的客户占30%.第2，3行元素的意义类同.求：（1）在三厂家都不采取竞争措施时的最终市场占有率；（2）若B厂采取竞争措施,如提高产品质量、适当降低价格、加强广告宣传及售后服务等,以提高市场占有率.具体方案有方案一：采取上述措施,投资50万元,使转移矩阵为2023/2/5338.2遍历性定理与平衡态预测可以使老用户保留到50%,使厂从厂争取用户从60%下降为40%.方案二：投资60万元,使转移矩阵为2023/2/5348.2遍历性定理与平衡态预测可以从C厂争取20%客户,从厂争取10%客户.若每个用户使用B厂汽车备件能为B厂提供100元盈利,试问B厂应采用哪一个方案？解(1)记转移矩阵P的固有概率向量为则由方程组解出2023/2/5358.2遍历性定理与平衡态预测换言之,在三厂家都不采取竞争措施时,最终市场占有率为：A厂占50%,B厂占25%,C厂占25%.（2）B厂若采用方案一,此时转矩阵为

由.解得

在此方案下,B厂可增加新用户盈利（万元）2023/2/5368.2遍历性定理与平衡态预测（3）厂若采用方案二,此时转移矩阵为,由解得.在此方案下,厂可增加新用户(万户)增加盈利(万元).(户),显然,从经济效益看,厂应采取第二个方案.2023/2/5378.2遍历性定理与平衡态预测从以上例子可以看到,马尔可夫分析不仅可以用于预测,也可以用于对策分析.如上例中企业为争取顾客、提高市场占有率,可根据预测结果采取不同竞争方案（也称策略）例如：第一种方案是设法保留住老顾客；第二种方案是尽量争取其他新顾客；第三种方案是既设法保留住顾客,又尽量争取新顾客.

第三种方案的效果比前两种收效好,但所需费用也高.此外,当各方竞争力量旗鼓相当时,竞争结果,顾客往往没有多大变动.所以,当市场占有率接近平衡状态时,各种方案的效果都不会太好,只有等打破平衡时再做工作.2023/2/5388.2遍历性定理与平衡态预测

由此可见,运用马尔可夫分析,可以预测得两项重要信息：其一,可以预测出事物各状态经过一段时间后,转入其他状态时所占的比例；其二,可根据某些转移矩阵确定出在远期（即平衡状态时）各状态所占的比例,即最终市场占有率.若能早期求得最终市场占有率,就可据此选择经营策略,制定分阶段的最优对策，避免“青蛙效应”。马尔可夫预测法的工作流程如图8.3所示：2023/2/539图8.3马尔可夫预测法的工作流程8.2遍历性定理与平衡态预测2023/2/5408.3马尔可夫预测的应用

2023/2/5418.3马尔可夫预测的应用

1.设备状态预测【例8.5】

设有A,B而一周后仍无故障的概率为0.7,即对设备A,若已知现在无故障（状态1）,.两种设备,其功能、价格、使用成本均相同.对设备B,相应的概率假设是因此,从无故障而一周后有故障（状态2）的概率,对设备A而言,应为；对设备B而言,应为

2023/2/5428.3马尔可夫预测的应用再假设我们的问题是：从长远看,选择哪一种设备更合适？

由遍历性定理,可假设设备A和B的固有概率向量分别为及由于设备A与B的一周转移概率分别是

2023/2/5438.3马尔可夫预测的应用对设备A,由,解出.即当系统处于稳定状态时,设备A无故障的概率为,有故障的概率为.对设备B,由解出,即当系统处于稳定状态时,设备B无故障的概率为,有故障的概率为

.由于设备B无故障的概率大于设备A无故障的概率,应选购设备B.

2023/2/5448.3马尔可夫预测的应用2.企业设备更新决策【例8.6】对某种设备每周检查一次,并将它们的状态分为新,优,良,坏,分别用状态1,2,3,4表示.若发现已坏需要一周时间更新.经统计,转移矩阵为

新优良坏新优良坏= 2023/2/5458.3马尔可夫预测的应用假设更新一台设备需要25元；若发现已坏,生产损失为20元.试问,每周更新设备的费用和设备损坏造成的生产损失是多少？这个问题可用平衡分析解决.由遍历性定理,只需求出矩阵的固有概率向量.由方程组解出(新,优,良,坏)=(0.19,0.30,0.32,0.19),于是对每台设备而言,每周的更新费用和生产损失费分别为更新费=0.1925=4.75(元)，损失费=0.1920=3.80(元)，共计8.55元.2023/2/5468.3马尔可夫预测的应用现在若采取另一种更新策略：一经检查发现设备处于“良”的状态,就马上更新掉,以减少因设备损坏给生产造成的损失.此时,转移矩阵为

新优良=

新优良由方程组解得(新,优,良)=(0.28,0.44,0.28).2023/2/5478.3马尔可夫预测的应用此时,每周更新费增加到0.2825=7(元),但损失费减少到零,总费用小于原更新策略.若一个工厂有一千台这种设备,采用新更新策略,每周可节约

1000(8.55-7)元=1550元.一年按50周计算,全年可节约501550元=77500元.这是一笔可观的经济效益.2023/2/5488.4WinQSB软件应用

2023/2/5498.4WinQSB软件应用

马尔可夫过程分析程序需要调用子程序MarkovProcess(MKP).

当给定一步转移概率矩阵P、初始状态概率向量