马尔科夫预测与决策ppt课件.ppt

《马尔科夫预测与决策ppt课件.ppt》由会员分享，可在线阅读，更多相关《马尔科夫预测与决策ppt课件.ppt（47页珍藏版）》请在三一文库上搜索。

1、马尔科夫预测与决策法 小组成员：于文豪 张薇 刘思伯 梅成波 杜照玺,马尔科夫预测与决策,1.基本原理概述 2.马尔科夫预测与决策 3.案例分析,第一节 基本原理,一、基本概念 1.随机变量 、 随机函数与随机过程 一变量x，能随机地取数据（但不能准确地预言它取何值），而对于每一个数值或某一个范围内的值有一定的概率，那么称x为随机变量。 假定随机变量的可能值xi发生概率为Pi 即P(x = xi) = Pi 对于xi的所有n个可能值，有离散型随机变量分布列： Pi = 1 对于连续型随机变量，有 P(x)dx = 1,在试验过程中，随机变量可能随某一参数（不一定是时间）的变化而变化. 如测量大

2、气中空气温度变化x = x(h),随高度变化。这种随参变量而变化的随机变量称为随机函数。而以时间t作参变量的随机函数称为随机过程。 也就是说：随机过程是这样一个函数，在每次试验结果中，它以一定的概率取某一个确定的，但预先未知的时间函数。,2、马尔科夫过程 随机过程中，有一类具有“无后效性性质”，即当随机过程在某一时刻to所处的状态已知的条件下，过程在时刻tto时所处的状态只和to时刻有关，而与to以前的状态无关，则这种随机过程称为马尔科夫过程。 即是：ito为确知,it(tto)只与ito有关，这种性质为无后效性，又叫马尔科夫假设。,简例：设x(t)为大米在粮仓中t月末的库存量，则 x(t)

3、= x(t1)y(t) +G(t) t月的转出量 第t1月末库存量 ,G(t)为当月转入量 x(t)可看作一个马尔科夫过程。,3、马尔科夫链 时间和状态都是离散的马尔科夫过程称为马尔科夫链。例：蛙跳问题 假定池中有N张荷叶，编号为1，2，3,N，即蛙跳可能有N个状态（状态确知且离散）。青蛙所属荷叶，为它目前所处的状态；因此它未来的状态，只与现在所处状态有关，而与以前的状态无关（无后效性成立）,1,2,3,4,P33,P22,P44,P41,P42,P31,P32,写成数学表达式为： P( xt+1 = j | xt = it , xt-1 = it1,x1 = i1) =P( xt+1 = j

4、 | xt = it ) 定义：Pij = P( xt+1 = j | xt = i) 即在xt = i的条件下，使 xt+1 = j的条件概率，是从 i状态一步转移到j状态的概率，因此它又称一步状态转移概率。 由状态转移图，由于共有N个状态，所以有,二状态转移矩阵 1.一步状态转移矩阵 系统有N个状态，描述各种状态下向其他状态转移的概率矩阵 P11 P12 P1N 定义为 P21 P22 P2N : : : PN1 PN2 PNN 这是一个N阶方阵，满足概率矩阵性质 1） Pij 0,i,j = 1,2, , N 非负性性质 2） Pij = 1 行元素和为1 ,i=1,2,N,NN,P =

5、,如： W1 = 1/4, 1/4, 1/2, 0 W2 = 1/3, 0, 2/3 W3 = 1/4, 1/4, 1/4, 1/2 W4 = 1/3, 1/3, -1/3,0, 2/3 3）若A和B分别为概率矩阵时，则AB为概率矩阵。,概率向量,非概率向量,2.稳定性假设 若系统的一步状态转移概率不随时间变化，即转移矩阵在各个时刻都相同，称该系统是稳定的。 这个假设称为稳定性假设。蛙跳问题属于此类，后面的讨论均假定满足稳定性条件。,3.k步状态转移矩阵 经过k步转移由状态i转移到状态j的概率记为 P(xt+k =j | xt = i) = Pij(k) i,j = 1,2, , N 定义：k

6、步状态转移矩阵为： P11(k) P12(k) P1N(k) P = : : : PN1(k) PN2(k) PNN (k) 当系统满足稳定性假设时 P = P = P P P 其中P为一步状态转移矩阵。 即当系统满足稳定性假设时，k步状态转移矩阵为一步状态转移矩阵的k次方.,k,k,k,例：设系统状态为N = 3，求从状态1转移到状态2的 二步状态转移概率. 解：作状态转移图 解法一：由状态转移图： 1 1 2: P11 P12 1 2 2: P12 P22 1 3 2: P13 P32 P12 = P11 P12 + P12 P22 +P13 P32 = P1i Pi2,1,3,2,P13

7、,P32,P11,P12,P12,P22,解法二： k = 2, N = 3 P11(2) P12 (2) P13(2) P = P21(2) P22 (2) P23(2) P31(2) P32(2) P33(2) P11 P12 P13 P11 P12 P13 = PP = P21 P22 P23 P21 P22 P23 P31 P32 P33 P31 P32 P33 得： P12(2) = P11 P12 + P12 P22 +P13 P32 = P1i Pi2,三.稳态概率： 用于解决长期趋势预测问题。 即：当转移步数的不断增加时，转移概率矩阵 P 的变化趋势。 1.正规概率矩阵。 定义

8、：若一个概率矩阵P，存在着某一个正整数m,使P 的所有元素均为正数（Pij o），则该矩阵称为正规概率矩阵,k,例： 1/2 1/4 1/4 P = 1/3 1/3 1/3 为正规概率矩阵 2/5 1/5 2/5 0 1 P11 = 0 1/2 1/2 但当 m = 2， 有 有Pij 0 它也是正规概率矩阵。 （P 每个元素均为正数） 但 1 0 0 1 就找不到一个正数m,使P 的每一个元素均大于0，所以它不是正规概率矩阵。, ,P =,2,2,P =,m,P =,2,2.固定概率向量（特征概率向量） 设 P为NN概率矩阵,若U = U1, U2, UN为概率向量,且满足UP = U,称U

9、为P的固定概率向量 例 0 1 1/2 1/2 为概率矩阵 P的固定概率向量 U = 1/3 , 2/3 检验 UP = 1/3 2/3 0 1 1/2 1/2 =1/3 2/3,P =,3.正规概率矩阵的性质 定理一 设P为NXN正规概率矩阵，则 A .P有且只有一个固定概率向量 U = U1,U2, UN 且U的所有元素均为正数 Ui 0 B.NXN方阵P的各次方组成序列 P, P, P, ,P 趋于方阵T，且T的每一个行向量都是固定概率向量U。 即 U1 U2 UN U lim Pk = T = : : : = : U1 U2 UN U 这个方阵T称稳态概率矩阵。,2,3,k,这个定理说

10、明：无论系统现在处于何种状态，在经过足够多的状态转移之后，均达到一个稳态。 因此，欲求长期转移概率矩阵，即进行长期状态预测，只要求出稳态概率矩阵T； 而T的每个行向量都是固定概率向量，所以只须求出固定概率向量U就行了 !,定理二：设X为任意概率向量，则XT = U 即任意概率向量与稳态概率矩阵之点积为固定概率向量。 事实上： U1 U2 UN XT = X : : : = U1Xi U1Xi U1Xi U1 U2 UN = U1 U2 UN = U,例：若 0.4 0.3 0.3 P = 0.6 0.3 0.1 求T 0.6 0.1 0.3 解：设 U = U1 U2 U3 = U1 U2 1

11、U1U2 由 UP = U 有 0.4 0.3 0.3 U1 U2 1U1U2 0.6 0.3 0.1 = U1 U2 U3 0.6 0.1 0.3,即 -0.2U1 + 0.6 = U1 U1 = 0.5 0.2U1 + 0.2U2 + 0.1 =U2 U2 = 0.25 -0.2U2 + 0.3 = U3 U3 = 0.25 U = 0.5 0.25 0.25 则 0.5 0.25 0.25 T = 0.5 0.25 0.25 0.5 0.25 0.25 说明： 不管系统的初始状态如何，当系统运行时间较长时，转移到各个状态的概率都相等。（列向量各元素相等） 即 各状态转移到1状态都为0.5

12、; 2状态都为0.25 ; 3状态都为0.25,第二节 马尔科夫预测和决策,马尔科夫决策方法就是根据某些变量的现在状态及其变化趋向，来预测它在未来某一特定期间可能出现的状态，从而提供某种决策的依据。 马尔科夫决策基本方法是用转移概率矩阵进行预测和决策。,一、转移概率矩阵及其决策特点,转移概率矩阵模型为：,其中Pij 表示概率，,表示转移概率矩阵。,用马尔科夫决策方法进行决策的特点：,（1）转移概率矩阵中的元素是根据近期市场 或顾客的保留与得失流向资料确定的。 （2）下一期的概率只与上一期的预测结果有 关，不取决于更早期的概率。 （3）利用转移概率矩阵进行决策，其最后结 果取决于转移矩阵的组成，

13、不取决于原 始条件，即最初占有率。,二、转移概率矩阵决策的应用步骤,转移概率矩阵决策的步骤如下： 1、建立转移概率矩阵。 2、利用转移概率矩阵进行模拟预测。 3、求出转移概率矩阵的平衡状态，即稳 定状态。 4、应用转移概率矩阵进行决策,案例1 市场占有率预测,商品在市场上参与竞争，都拥有顾客，并由此而产生销售，事实上，同一商品在某一地区所有的N个商家（或不同品牌的N个同类产品）都拥有各自的顾客，产生各自销售额，于是产生了市场占有率定义： 设某一确定市场某商品有N个不同品牌（或N个商家）投入销售，第i个商家在第j期的市场占有率 Si(j) = xi(j)/x i =1,2, N 其中 xi(j)

14、为第i个商家在第j期的销售额（或拥有顾客数） x为同类产品在市场上总销售额（或顾客数） 市场占有率所需数据可通过顾客抽样调查得到。,一般地,首先考虑初始条件,设当前状态（即j = 0 ） 为 S(0) = S1(0) S2(0) SN(0) 第i个商家 Si(0) = xi(0)/x xi(0) = Si(0) x 即当前第i个商家市场占有率与初始市场占有率及市场总量有关. 同时假定满足无后效性及稳定性假设. 由于销售商品的流通性质,有第i个商家第j期销售状况为,xi(k) = x1(0)P1i(k) + x2(0)P2i(k)+ + xN(0)PNi(k) = xS1(0)P1i(k) +x

15、S2(0)P2i(k) + + xSN(0)PNi(k) P1i(k) = xS1(0) S2(0) SN(0) P2i(k) : PNi(k) 有：Si(k) = xi(k)/x P1i(k) = S1(0) S2(0) SN(0) P2i(k) : PNi(k),故可用矩阵式表达所有状态: S1(k),S2(k), ,SN(k)= S1(0),S2(0), ,SN(0) P 即 S(k) = S(0) P 当满足稳定性假设时,有 S(k) = S(0) P 这个公式称为已知初始状态条件下的市场占有率k步预测模型.,k,k,k,例:东南亚各国味精市场占有率预测, 初期工作: a)行销上海,日

16、本,香港味精,确定状态1,2,3. b)市场调查,求得目前状况,即初始分布 c)调查流动状况;上月转本月情况,求出一步状态转移概率. 1)初始向量: 设 上海味精状况为1; 日本味精状况为2; 香港味精状况为3; 有 S(0) = S1(0) S2(0) S3(0) = 0.4 0.3 0.3,2)确定一步状态转移矩阵 P11 P12 P13 0.4 0.3 0.3 P = P21 P22 P23 = 0.6 0.3 0.1 P31 P32 P33 0.6 0.1 0.3 3),3 步状态转移矩阵(假定要预测3个月后) P11(3) P12(3) P13(3) 0.496 0.252 0.25

17、2 P 3= P21(3) P22(3) P23(3) = P = 0.504 0.252 0.244 P31(3) P32(3) P33(3) 0.504 0.244 0.252,3,4)预测三个月后市场 0.496 0.252 0.252 S(3) = S(0)P3 =0.4 0.3 0.3 0.504 0.252 0.244 0.504 0.244 0.252 S1(3) = 0.40.496 +0.30.504 + 0.30.504 = 0.5008 S2(3) = 0.2496 S3(3) = 0.2496,二.长期市场占有率预测 这是求当 k 时 S(k) ? 我们知道: S(k)

18、 = S(0) P lim S(k) = S(0) lim P = S(0)T = U 因此,在已知初始条件下求长期市场占有率就是求稳态概率矩阵,也是求固定概率向量. 求固定概率向量的方法,我们在前一节已有例子,只不过说明了长期市场占有率也是只与稳态矩阵有关,与初始条件无关.,k,k,上面味精例子, 0.4 0.3 0.3 已知 P = 0.6 0.3 0.1 0.6 0.1 0.4 0.5 0.25 0.25 求出 T = 0.5 0.25 0.25 = lim Pk 0.5 0.25 0.25 lim S(k) = 0.5 0.25 0.25 即中国味精可拥有50%的长期市场.,案例2 期

19、望利润预测,是考虑:一个与经济有关随机系统在进行状态转移时,利润要发生相应变化,例如商品连续畅销到滞销,显然在这些过程变化时,利润变化的差距是很大的. 所以有如下的定义: 若马尔科夫链在发生状态转移时,伴随利润变化,称这个马尔科夫链为带利润的马尔科夫链.,设系统有N个状态 状态i经过一步转移到状态j时(即当事件发生时,Pij = 1)所获得的利润为rij i,j = 1,2, N 于是有利润矩阵 r11 r12 r1N R = r21 r22 r2n : : : rN1 rN2 rNN 显然 ,rij 0 盈利 ;rij 0 亏损 ; rij = 0 平衡 由于系统状态转移为随机的,得到的利润

20、也应当是随机的,这个利润只能是期望利润.,11、即时期望利润(一步状态转移期望利润) 考虑状态 i 状态转移 i 1 i 2 i i i N 一步转移概率 Pi1 Pi2 Pii PiN 利润变化 ri1 ri2 rii riN 所以:从i转到1的期望利润值 P11r11 从i转到2的期望利润值 P12r12 : : 从i转到i的期望利润值 Piirii : : 从i转到N的期望利润值 P1Nr1N,而从状态i开始经过一步转移后所得到的期望利润值为 Pijrij = Pi1ri1 + Pi2ri2 PiNriN 这个值称为即时期望利润,又是一步状态转移期望利润,是概率定义下的利润均值. 记为

21、Vi = Vi = Pijrij 特别地Vi = 0 ,即当 k = 0, 未转移,没有利润变化.,1,0,2. k步转移期望利润递推公式 k步转移期望利润可以分解为两步,即一步和k1步, 一步转移期望利润为Vi = Pijrij 现考虑k1步 首先,从0时刻到1时刻发生了一步状态转移,假定 状态已转移1状态(令Pij = 1)后,从1状态开始 k1 步转移后达到期望利润为V1k-1 . 而i状态转移到1状态的发生概率为Pi1 , 因此i状态先转移到1状态后的k1步实际期望利润为 Pi1 V1k-1,k1,同理 i状态先转到2状态后的k1步实际期望利润为 Pi2 V2 即:各实际期望利润之和,

22、构成了初始状态为i的 k1步转移后的转移期望利润 : PijVj k步转移期望利润 Vi = Vi +PijVj = Pijrij + PijVj = Pij (rij + Vj ) 以上公式为k步转移期望利润递推公式 此公式可改写为矩阵递推式: 由 Vi = Vi + PijVj,k1,k1,k,1,k1,k1,k1,k,k1,V1 定义 V = V2 为j步转移期望利润列向量 : VN V1 V = V2 为即时期望利润列向量 :. VN P11 P12 P1N : : : 为一步状态转移概率矩阵 PN1 PN2 PNN 有V = V +PV,j,j,j,j,P =,K,k1,例:设某商品

23、销售状态分别为畅销(状态1)及滞销(状态2),销售状态转移概率矩阵为 P11 P12 0.5 0.5 P21 P22 0.4 0.6 利润矩阵 r11 r12 5 1 r21 r22 1 -1 试预测三个月后的期望利润.,=,P =,=,R =,解:利用递推公式顺序推出, 即时期望利润 Vi = Pijrij V1 = P1jr1j = P11r11 + P12r12 = 0.55 + 0.51 = 3(百万元) V2 = P2jr2j = P21r21 + P22r22 = 0.41 + 0.6(-1)= -0.2(百万元) V1: 本月畅销,一月后可期望获利300万 V2: 本月滞销,一个

24、月后预测亏损20万 由 V1 = P1j (r1j+ Vj ),k,k-1,V1 = P1j (r1j+ Vj) = P11( r11 + V1) + P12 ( r12 + V2) = 0.5(5 + 3) + 0.5(10.2) = 4.4 (百万) 即本月畅销,预计两个月后可期望获利440万元 V2 = P2j (r2j+ Vj) = P21(r21 + V1) + P22(r22 + V2) = 0.4(1 +3) + 0.6(-10.2) = 0.88(百万) 即本月滞销,两月后可期望获利88万元.,2,2,由此,可推出本题结果: V1 = P1j (r1j + Vj) = P11(r11 + V1) + P12(r12 + V2) = 0.5(5 + 4.4) + 0.5(1+0.8) = 5.64 (百万) V2 = P2j (r2j+ Vj) = P21(r21 + V1) + P22(r22 + V2) = 0.4(1 + 4.4) + 0.6(-1+0.88) = 2.088(百万) 答案:若本月畅销,三月后将期望盈利564万元 若本月滞销,三月后将期望盈利208.8万元.,3,2,2,2,3,2,2,2,