马尔科夫预测与决策

null马尔科夫预测与决策法 小组成员：于文豪 张薇 刘思伯 梅成波 杜照玺 马尔科夫预测与决策法 小组成员：于文豪 张薇 刘思伯 梅成波 杜照玺 马尔科夫预测与决策马尔科夫预测与决策1.基本原理概述 2.马尔科夫预测与决策 3.案例 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 第一节 基本原理 第一节 基本原理 一、基本概念 1.随机变量 、 随机 函数 excel方差函数excelsd函数已知函数     2 f x m x mx m      2 1 4 2拉格朗日函数pdf函数公式下载 与随机过程 一变量x，能随机地取数据（但不能准确地预言它取何值），而对于每一个数值或某一个范围内的值有一定的概率，那么称x为随机变量。 假定随机变量的可能值xi发生概率为Pi 即P(x = xi) = Pi 对于xi的所有n个可能值，有离散型随机变量分布列： ∑Pi = 1 对于连续型随机变量，有 ∫P(x)dx = 1 null 在试验过程中，随机变量可能随某一参数（不一定是时间）的变化而变化. 如测量大气中空气温度变化x = x(h),随高度变化。这种随参变量而变化的随机变量称为随机函数。而以时间t作参变量的随机函数称为随机过程。 也就是说：随机过程是这样一个函数，在每次试验结果中，它以一定的概率取某一个确定的，但预先未知的时间函数。 null 2、马尔科夫过程 随机过程中，有一类具有“无后效性性质”，即当随机过程在某一时刻to所处的状态已知的条件下，过程在时刻t>to时所处的状态只和to时刻有关，而与to以前的状态无关，则这种随机过程称为马尔科夫过程。 即是：ito为确知,it(t>to)只与ito有关，这种性质为无后效性，又叫马尔科夫假设。 null 简例：设x(t)为大米在粮仓中t月末的库存量，则 x(t) = x(t―1)—y(t) +G(t) t月的转出量 第t―1月末库存量 ,G(t)为当月转入量 x(t)可看作一个马尔科夫过程。 null 3、马尔科夫链 时间和状态都是离散的马尔科夫过程称为马尔科夫链。例：蛙跳问题 假定池中有N张荷叶，编号为1，2，3,……,N，即蛙跳可能有N个状态（状态确知且离散）。青蛙所属荷叶，为它目前所处的状态；因此它未来的状态，只与现在所处状态有关，而与以前的状态无关（无后效性成立） null 1234P33P22P44P41P42P31P32null 写成数学 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 达式为： P( xt+1 = j | xt = it , xt-1 = it―1,……x1 = i1)   =P( xt+1 = j | xt = it ) 定义：Pij = P( xt+1 = j | xt = i) 即在xt = i的条件下，使 xt+1 = j的条件概率，是从 i状态一步转移到j状态的概率，因此它又称一步状态转移概率。 由状态转移图，由于共有N个状态，所以有 null 二．状态转移矩阵 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,…NN×N P =null 如： 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为概率矩阵。 概率向量非概率向量null 2.稳定性假设 若系统的一步状态转移概率不随时间变化，即转移矩阵在各个时刻都相同，称该系统是稳定的。 这个假设称为稳定性假设。蛙跳问题属于此类，后面的讨论均假定满足稳定性条件。 null 3.k步状态转移矩阵 经过k步转移由状态i转移到状态j的概率记为   P(xt+k =j | xt = i) = Pij(k) i,j = 1,2, ……, N 定义：k步状态转移矩阵为：   P11(k) P12(k) …… P1N(k) P = : : :   PN1(k) PN2(k) …… PNN (k) 当系统满足稳定性假设时   P = P = P• P• …… P 其中P为一步状态转移矩阵。 即当系统满足稳定性假设时，k步状态转移矩阵为一步状态转移矩阵的k次方.[k][k] k null 例：设系统状态为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 132P13P32 P11P12P12P22null 解法二： 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 = P•P = P21 P22 P23 P21 P22 P23 P31 P32 P33 P31 P32 P33 得： P12(2) = P11 • P12 + P12 • P22 +P13 • P32 =∑ P1i • Pi2 null 三.稳态概率： 用于解决长期趋势预测问题。 即：当转移步数的不断增加时，转移概率矩阵 P 的变化趋势。 1.正规概率矩阵。 定义：若一个概率矩阵P，存在着某一个正整数m,使P 的所有元素均为正数（Pij >o），则该矩阵称为正规概率矩阵 [k]null例： 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 =22 P =m P =2null 2.固定概率向量（特征概率向量） 设 P为NN概率矩阵,若U = [U1, U2,…, UN]为概率向量,且满足UP = U,称U为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 = null 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称稳态概率矩阵。23knull 这个定理说明：无论系统现在处于何种状态，在经过足够多的状态转移之后，均达到一个稳态。 因此，欲求长期转移概率矩阵，即进行长期状态预测，只要求出稳态概率矩阵T； 而T的每个行向量都是固定概率向量，所以只须求出固定概率向量U就行了 ! null 定理二：设X为任意概率向量，则XT = U 即任意概率向量与稳态概率矩阵之点积为固定概率向量。 事实上： U1 U2 …… UN XT = X• : : : = [U1∑Xi U1∑Xi …… U1∑Xi ]   U1 U2 …… UN = [U1 U2 …… UN ] = Unull例：若 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－U1－U2] 由 UP = U 有   0.4 0.3 0.3 [U1 U2 1－U1－U2]  0.6 0.3 0.1 = [U1 U2 U3]   0.6 0.1 0.3 null即 -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; 2状态都为0.25 ; 3状态都为0.25 第二节 马尔科夫预测和决策第二节 马尔科夫预测和决策 马尔科夫决策方法就是根据某些变量的现在状态及其变化趋向，来预测它在未来某一特定期间可能出现的状态，从而提供某种决策的依据。 马尔科夫决策基本方法是用转移概率矩阵进行预测和决策。 一、转移概率矩阵及其决策特点一、转移概率矩阵及其决策特点转移概率矩阵模型为： 其中Pij 表示概率， 表示转移概率矩阵。用马尔科夫决策方法进行决策的特点： 用马尔科夫决策方法进行决策的特点： （1）转移概率矩阵中的元素是根据近期市场 或顾客的保留与得失流向资料确定的。 （2）下一期的概率只与上一期的预测结果有 关，不取决于更早期的概率。 （3）利用转移概率矩阵进行决策，其最后结 果取决于转移矩阵的组成，不取决于原 始条件，即最初占有率。 二、转移概率矩阵决策的应用步骤 二、转移概率矩阵决策的应用步骤 转移概率矩阵决策的步骤如下： 1、建立转移概率矩阵。 2、利用转移概率矩阵进行模拟预测。 3、求出转移概率矩阵的平衡状态，即稳 定状态。 4、应用转移概率矩阵进行决策 案例1 市场占有率预测 案例1 市场占有率预测 商品在市场上参与竞争，都拥有顾客，并由此而产生销售，事实上，同一商品在某一地区所有的N个商家（或不同品牌的N个同类产品）都拥有各自的顾客，产生各自销售额，于是产生了市场占有率定义： 设某一确定市场某商品有N个不同品牌（或N个商家）投入销售，第i个商家在第j期的市场占有率   Si(j) = xi(j)/x i =1,2, …… N 其中 xi(j)为第i个商家在第j期的销售额（或拥有顾客数） x为同类产品在市场上总销售额（或顾客数） 市场占有率所需数据可通过顾客抽样调查得到。 null 一般地,首先考虑初始条件,设当前状态（即j = 0 ） 为 S(0) = [S1(0) S2(0) …… SN(0)] 第i个商家 Si(0) = xi(0)/x → xi(0) = Si(0) x 即当前第i个商家市场占有率与初始市场占有率及市场总量有关. 同时假定满足无后效性及稳定性假设. 由于销售商品的流通性质,有第i个商家第j期销售状况为 null xi(k) = x1(0)P1i(k) + x2(0)P2i(k)+ ……+ xN(0)PNi(k) = xS1(0)P1i(k) +xS2(0)P2i(k) + ……+ xSN(0)PNi(k) P1i(k) = x[S1(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) null故可用矩阵式表达所有状态: [S1(k),S2(k), …… ,SN(k)]= [S1(0),S2(0), …… ,SN(0)] P 即 S(k) = S(0) P 当满足稳定性假设时,有   S(k) = S(0) P 这个 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 称为已知初始状态条件下的市场占有率k步预测模型. [k]k[k]null 例:东南亚各国味精市场占有率预测, 初期工作: a)行销上海,日本,香港味精,确定状态1,2,3. b)市场调查,求得目前状况,即初始分布 c)调查流动状况;上月转本月情况,求出一步状态转移概率. 1)初始向量: 设 上海味精状况为1; 日本味精状况为2; 香港味精状况为3; 有 S(0) = [S1(0) S2(0) S3(0)] = [0.4 0.3 0.3]null2)确定一步状态转移矩阵   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.252 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 3null4)预测三个月后市场   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.4×0.496 +0.3×0.504 + 0.3×0.504 = 0.5008  S2(3) = 0.2496  S3(3) = 0.2496 null 二.长期市场占有率预测 这是求当 k →∞ 时 S(k) → ? 我们知道:   S(k) = S(0) P   lim S(k) = S(0) lim P = S(0)•T = U 因此,在已知初始条件下求长期市场占有率就是求稳态概率矩阵,也是求固定概率向量. 求固定概率向量的方法,我们在前一节已有例子,只不过说明了长期市场占有率也是只与稳态矩阵有关,与初始条件无关. [k][k]null  上面味精例子, 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 期望利润预测 案例2 期望利润预测 是考虑:一个与经济有关随机系统在进行状态转移时,利润要发生相应变化,例如商品连续畅销到滞销,显然在这些过程变化时,利润变化的差距是很大的. 所以有如下的定义: 若马尔科夫链在发生状态转移时,伴随利润变化,称这个马尔科夫链为带利润的马尔科夫链. null 设系统有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 平衡 由于系统状态转移为随机的,得到的利润也应当是随机的,这个利润只能是期望利润. null 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的期望利润值 P1Nr1Nnull 而从状态i开始经过一步转移后所得到的期望利润值为   ∑Pijrij = Pi1ri1 + Pi2ri2…… PiNriN 这个值称为即时期望利润,又是一步状态转移期望利润,是概率定义下的利润均值. 记为 Vi = Vi = ∑Pijrij 特别地Vi = 0 ,即当 k = 0, 未转移,没有利润变化. [1][0]null 2. k步转移期望利润递推公式 k步转移期望利润可以分解为两步,即一步和k―1步, 一步转移期望利润为Vi = ∑Pijrij 现考虑k―1步 首先,从0时刻到1时刻发生了一步状态转移,假定 状态已转移1状态(令Pij = 1)后,从1状态开始 k―1 步转移后达到期望利润为V1[k-1] . 而i状态转移到1状态的发生概率为Pi1 , 因此i状态先转移到1状态后的k―1步实际期望利润为 Pi1• V1[k-1] [k―1]null 同理 i状态先转到2状态后的k―1步实际期望利润为 Pi2• V2 即:各实际期望利润之和,构成了初始状态为i的 k―1步转移后的转移期望利润 : ∑PijVj k步转移期望利润 Vi = Vi +∑PijVj = ∑Pijrij + ∑PijVj   = ∑Pij (rij + Vj ) 以上公式为k步转移期望利润递推公式 此公式可改写为矩阵递推式: 由 Vi = Vi + ∑PijVj[k―1][k―1][k][1] [k―1][k―1][k―1][k][k―1]null V1 定义 V = V2 为j步转移期望利润列向量 : VN   V1 V = V2 为即时期望利润列向量 :.   VN P11 P12 P1N : : : 为一步状态转移概率矩阵 PN1 PN2 PNN 有V = V +PV[j][j][j][j]P =[K] [k―1]null例:设某商品销售状态分别为畅销(状态1)及滞销(状态2),销售状态转移概率矩阵为   P11 P12 0.5 0.5 P21 P22 0.4 0.6 利润矩阵 r11 r12 5 1  r21 r22 1 -1 试预测三个月后的期望利润. =P = =R = null解:利用递推公式顺序推出, 即时期望利润 Vi = ∑Pijrij   V1 = ∑P1jr1j = P11r11 + P12r12 = 0.5×5 + 0.5×1 = 3(百万元) V2 = ∑P2jr2j = P21r21 + P22r22 = 0.4×1 + 0.6×(-1)= -0.2(百万元) V1: 本月畅销,一月后可期望获利300万 V2: 本月滞销,一个月后预测亏损20万 由 V1 = ∑ P1j (r1j+ Vj ) [k][k-1]null    V1 = ∑ P1j (r1j+ Vj)   = P11( r11 + V1) + P12 ( r12 + V2)    = 0.5(5 + 3) + 0.5(1―0.2) = 4.4 (百万) 即本月畅销,预计两个月后可期望获利440万元   V2 = ∑ P2j (r2j+ Vj)   = P21(r21 + V1) + P22(r22 + V2)   = 0.4(1 +3) + 0.6(-1―0.2)   = 0.88(百万)  即本月滞销,两月后可期望获利88万元. [2][2]null由此,可推出本题结果: 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]