《马尔科夫决策ppt课件》由会员分享,可在线阅读,更多相关《马尔科夫决策ppt课件(43页珍藏版)》请在金锄头文库上搜索。
1、第一节 根本原理 一、根本概念1.随机变量、随机函数与随机过程一变量x,能随机地取数据但不能准确地预言它取何值,而对于每一个数值或某一个范围内的值有一定的概率,那么称x为随机变量。假定随机变量的能够值xi发生概率为Pi即P(x=xi)=Pi对于xi的一切n个能够值,有离散型随机变量分布列:Pi=1对于延续型随机变量,有P(x)dx=1在实验过程中,随机变量能够随某一参数不一定是时间的变化而变化.如丈量大气中空气温度变化x=x(h),随高度变化。这种随参变量而变化的随机变量称为随机函数。而以时间t作参变量的随机函数称为随机过程。也就是说:随机过程是这样一个函数,在每次实验结果中,它以一定的概率取
2、某一个确定的,但预先未知的时间函数。2、马尔科夫过程随机过程中,有一类具有“无后效性性质,即当随机过程在某一时辰to所处的形状知的条件下,过程在时辰tto时所处的形状只和to时辰有关,而与to以前的形状无关,那么这种随机过程称为马尔科夫过程。即是:ito为确知,it(tto)只与ito有关,这种性质为无后效性,又叫马尔科夫假设。3、马尔科夫链时间和形状都是离散的马尔科夫过程称为马尔科夫链。例:蛙跳问题假定池中有N张荷叶,编号为1,2,3,N,即蛙跳能够有N个形状形状确知且离散。青蛙所属荷叶,为它目前所处的形状;因此它未来的形状,只与如今所处形状有关,而与以前的形状无关无后效性成立写成数学表达式
3、为:P(xt+1=j|xt=it,xt-1=it1,x1=i1)=P(xt+1=j|xt=it)定义:Pij=P(xt+1=j|xt=i)即在xt=i的条件下,使xt+1=j的条件概率,是从i形状一步转移到j形状的概率,因此它又称一步形状转移概率。由形状转移图,由于共有N个形状,所以有1234P33P22P44P41P42P31P32二形状转移矩阵1.一步形状转移矩阵系统有N个形状,描画各种形状下向其他形状转移的概率矩阵P11P12P1N定义为P21P22P2N:PN1PN2PNN这是一个N阶方阵,满足概率矩阵性质1Pij0,i,j=1,2,N非负性性质2Pij=1行元素和为1,i=1,2,N
4、NNP=如:W1=1/4,1/4,1/2,0W2=1/3,0,2/3W3=1/4,1/4,1/4,1/2W4=1/3,1/3,-1/3,0,2/33假设A和B分别为概率矩阵时,那么AB为概率矩阵。概率向量非概率向量2.稳定性假设假设系统的一步形状转移概率不随时间变化,即转移矩阵在各个时辰都一样,称该系统是稳定的。这个假设称为稳定性假设。蛙跳问题属于此类,后面的讨论均假定满足稳定性条件。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
5、)PNN(k)当系统满足稳定性假设时P=P=PPP其中P为一步形状转移矩阵。即当系统满足稳定性假设时,k步形状转移矩阵为一步形状转移矩阵的k次方.kkk例:设系统形状为N=3,求从形状1转移到形状2的二步形状转移概率.解:作形状转移图解法一:由形状转移图:112:P11P12122:P12P22132:P13P32P12=P11P12+P12P22+P13P32=P1iPi2132P13P32P11P12P12P22解法二:k=2,N=3P11(2)P12(2)P13(2)P=P21(2)P22(2)P23(2)P31(2)P32(2)P33(2)P11P12P13P11P12P13=PP=P
6、21P22P23P21P22P23P31P32P33P31P32P33得:P12(2)=P11P12+P12P22+P13P32=P1iPi2例:味精销售问题已延续统计六年共24个季度,确定畅销,滞销界限,即只允许出现两种形状,且具备无后效性。设形状1为畅销,形状2为滞销,作出形状转移图:图中:P11为当前畅销,延续畅销概率;P12为当前畅销,转滞销概率;P22为当前滞销,延续滞销概率;P21为当前滞销,转畅销概率。12P22P11P12P21数据在确定盈亏量化界限后的统计表如下:t12345678910111213形状t1415161718192021222324形状进展概率计算时,第二十四
7、个季度为畅销,但后续是什么形状不知,故计算时不能采用,只用于第二十三季度统计。有:P11=7/(7+7)=0.5;P12=7/(7+7)=0.5;P21=7/(7+2)=0.78;P22=2/(7+2)=0.22那么0.50.50.780.22此式阐明了:假设本季度畅销,那么下季度畅销和滞销的能够性各占一半假设本季度滞销,那么下季度滞销有78%的把握,滞销风险22%P=二步形状转移矩阵为:0.50.50.50.50.780.220.780.220.640.360.56160.4384P11(2)P11(2)P11(2)P11(2)=P=P=22三.稳态概率:用于处理长期趋势预测问题。即:当转移
8、步数的不断添加时,转移概率矩阵P的变化趋势。1.正规概率矩阵。定义:假设一个概率矩阵P,存在着某一个正整数m,使P的一切元素均为正数Pijo,那么该矩阵称为正规概率矩阵k例:1/21/41/4P=1/31/31/3为正规概率矩阵2/51/52/501P11=01/21/2但当m=2,有有Pij0它也是正规概率矩阵。P每个元素均为正数但1001就找不到一个正数m,使P的每一个元素均大于0,所以它不是正规概率矩阵。P=22P=mP=22.固定概率向量特征概率向量设P为NN概率矩阵,假设U=U1,U2,UN为概率向量,且满足UP=U,称U为P的固定概率向量例011/21/2为概率矩阵P的固定概率向量
9、U=1/3,2/3检验UP=1/32/3011/21/2=1/32/3P=3.正规概率矩阵的性质定理一设P为NXN正规概率矩阵,那么A.P有且只需一个固定概率向量U=U1,U2,UN且U的一切元素均为正数Ui0B.NXN方阵P的各次方组成序列P,P,P,P趋于方阵T,且T的每一个行向量都是固定概率向量U。即U1U2UNUlimPk=T=:=:U1U2UNU这个方阵T称稳态概率矩阵。23k这个定理阐明:无论系统如今处于何种形状,在经过足够多的形状转移之后,均到达一个稳态。因此,欲求长期转移概率矩阵,即进展长期形状预测,只需求出稳态概率矩阵T;而T的每个行向量都是固定概率向量,所以只须求出固定概率
10、向量U就行了!定理二:设X为恣意概率向量,那么XT=U即恣意概率向量与稳态概率矩阵之点积为固定概率向量。现实上:U1U2UNXT=X:=U1XiU1XiU1XiU1U2UN=U1U2UN=U例:假设0.40.30.3P=0.60.30.1求T0.60.10.3解:设U=U1U2U3=U1U21U1U2由UP=U有0.40.30.3U1U21U1U20.60.30.1=U1U2U30.60.10.3即-0.2U1+0.6=U1U1=0.50.2U1+0.2U2+0.1=U2U2=0.25-0.2U2+0.3=U3U3=0.25U=0.50.250.25那么0.50.250.25T=0.50.25
11、0.250.50.250.25阐明:不论系统的初始形状如何,当系统运转时间较长时,转移到各个形状的概率都相等。列向量各元素相等即各形状转移到1形状都为0.5;2形状都为0.25;3形状都为0.25第二节 市场占有率预测 商品在市场上参与竞争,都拥有顾客,并由此而产生销售,现实上,同一商品在某一地域一切的N个商家或不同品牌的N个同类产品都拥有各自的顾客,产生各自销售额,于是产生了市场占有率定义:设某一确定市场某商品有N个不同品牌或N个商家投入销售,第i个商家在第j期的市场占有率Si(j)=xi(j)/xi=1,2,N其中xi(j)为第i个商家在第j期的销售额或拥有顾客数x为同类产品在市场上总销售
12、额或顾客数市场占有率所需数据可经过顾客抽样调查得到。普通地,首先思索初始条件,设当前形状即j=0为S(0)=S1(0)S2(0)SN(0)第i个商家Si(0)=xi(0)/xxi(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)+xS2(0)P2i(k)+xSN(0)PNi(k)P1i(k)=xS1(0)S2(0)SN(0)P2i(k):PNi(k)有:Si(k)=xi(k)
13、/xP1i(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步预测模型.kkk例:东南亚各国味精市场占有率预测,初期任务:a)行销上海,日本,香港味精,确定形状1,2,3.b)市场调查,求得目前情况,即初始分布c)调查流动情况;上月转本月情况,求出一步形状转移概率.1)初始向量:设上海味精情况为1;日本味精情况为2;香港味精情况为3;有S(0)=S1(0)S2(0)S3(0)=0
14、.40.30.32)确定一步形状转移矩阵P11P12P130.40.30.3P=P21P22P23=0.60.30.1P31P32P330.60.10.33),3步形状转移矩阵(假定要预测3个月后)P11(3)P12(3)P13(3)0.4960.2520.252P3=P21(3)P22(3)P23(3)=P=0.5040.2520.244P31(3)P32(3)P33(3)0.5040.2440.25234)预测三个月后市场0.4960.2520.252S(3)=S(0)P3=0.40.30.30.5040.2520.2440.5040.2440.252S1(3)=0.40.496+0.30
15、.504+0.30.504=0.5008S2(3)=0.2496S3(3)=0.2496二.长期市场占有率预测这是求当k时S(k)?我们知道:S(k)=S(0)PlimS(k)=S(0)limP=S(0)T=U因此,在知初始条件下求长期市场占有率就是求稳态概率矩阵,也是求固定概率向量.求固定概率向量的方法,我们在前一节已有例子,只不过阐明了长期市场占有率也是只与稳态矩阵有关,与初始条件无关.kk上面味精例子,0.40.30.3知P=0.60.30.10.60.10.40.50.250.25求出T=0.50.250.25=limPk0.50.250.25limS(k)=0.50.250.25即中
16、国味精可拥有50%的长期市场.第三节 期望利润预测 是思索:一个与经济有关随机系统在进展形状转移时,利润要发生相应变化,例如商品延续畅销到滞销,显然在这些过程变化时,利润变化的差距是很大的.所以有如下的定义:假设马尔科夫链在发生形状转移时,伴随利润变化,称这个马尔科夫链为带利润的马尔科夫链.设系统有N个形状形状i经过一步转移到形状j时(即当事件发生时,Pij=1)所获得的利润为riji,j=1,2,N于是有利润矩阵r11r12r1NR=r21r22r2n:rN1rN2rNN显然,rij0盈利;rij0亏损;rij=0平衡由于系统形状转移为随机的,得到的利润也该当是随机的,这个利润只能是期望利润
17、.11、即时期望利润(一步形状转移期望利润)思索形状i形状转移i1i2iiiN一步转移概率Pi1Pi2PiiPiN利润变化ri1ri2riiriN所以:从i转到1的期望利润值P11r11从i转到2的期望利润值P12r12:从i转到i的期望利润值Piirii:从i转到N的期望利润值P1Nr1N而从形状i开场经过一步转移后所得到的期望利润值为Pijrij=Pi1ri1+Pi2ri2PiNriN这个值称为即时期望利润,又是一步形状转移期望利润,是概率定义下的利润均值.记为Vi=Vi=Pijrij特别地Vi=0,即当k=0,未转移,没有利润变化.102.k步转移期望利润递推公式k步转移期望利润可以分解
18、为两步,即一步和k1步,一步转移期望利润为Vi=Pijrij现思索k1步首先,从0时辰到1时辰发生了一步形状转移,假定形状已转移1形状(令Pij=1)后,从1形状开场k1步转移后到达期望利润为V1k-1.而i形状转移到1形状的发生概率为Pi1,因此i形状先转移到1形状后的k1步实践期望利润为 Pi1V1k-1k1同理i形状先转到2形状后的k1步实践期望利润为Pi2V2即:各实践期望利润之和,构成了初始形状为i的k1步转移后的转移期望利润:PijVjk步转移期望利润Vi=Vi+PijVj=Pijrij+PijVj=Pij(rij+Vj)以上公式为k步转移期望利润递推公式此公式可改写为矩阵递推式:
19、由Vi=Vi+PijVjk1k1k1k1k1k1kk1 V1定义 V = V2 为j步转移期望利润列向量 : VN V1 V = V2 为即时期望利润列向量 :. VN P11 P12 P1N : : : 为一步形状转移概率矩阵 PN1 PN2 PNN 有V = V +PVjjjjP=Kk1例:设某商品销售形状分别为畅销(形状1)及滞销(形状2),销售形状转移概率矩阵为P11P120.50.5P21P220.40.6利润矩阵r11r1251r21r221-1试预测三个月后的期望利润.=P=R=解:利用递推公式顺序推出,即时期望利润Vi=PijrijV1=P1jr1j=P11r11+P12r12
20、=0.55+0.51=3(百万元)V2=P2jr2j=P21r21+P22r22=0.41+0.6(-1)=-0.2(百万元)V1:本月畅销,一月后可期望获利300万V2:本月滞销,一个月后预测亏损20万由V1=P1j(r1j+Vj)kk-1V1=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万元.22由此,可推出此题结果: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万元.32223222