运筹学课件——第4讲马尔可夫决策(精)_第1页
运筹学课件——第4讲马尔可夫决策(精)_第2页
运筹学课件——第4讲马尔可夫决策(精)_第3页
运筹学课件——第4讲马尔可夫决策(精)_第4页
运筹学课件——第4讲马尔可夫决策(精)_第5页
已阅读5页,还剩15页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、引例:牛奶厂决策最佳经营策略选择: 北京地区鲜牛奶由三个厂家提供,该地区客户总数为 100 万户,假定厂家每年从每个客户那里平均获利 50 元,客户资源每月都在三个厂家之间相互流动,厂家 2 考虑从以下两套候选方案之中选择一个实施: 方案一:吸引老客户,须花费 450 万元; 方案二:吸引厂家 1 和厂家 3 的客户,须花费 400 万元。您有什么好的建议来帮助厂家 2 决策?市场调查数据 今年一月份厂家 2 对 2000 名消费者进行了调查,购买厂家 1 , 2 , 3 产品的消费者人数分别为 800 , 600 和 600 ,得到市场占有率向量(概率向量)为( 0.4 , 0.3 , 0.

2、3 ); 同时通过询问这 2000 名消费者下月的购买倾向,得到如下转移频数矩阵: 123123状态转移概率矩阵 P从转移频数矩阵到状态转移概率矩阵 P : 用各行总数分别去除转移频数矩阵 N 的每行各元素,得到状态转移概率矩阵 P 如下:/800/600/600均衡状态的市场占有率在目前状态转移概率矩阵 P 下,达到均衡状态时的市场占有率记为 u ;估计如果实施方案一或二以后状态转移概率矩阵分别为 P1 和 P2 ,他们各自对应的均衡状态时市场占有率分别为 u1 和 u2 ;具体数据如下: u= ( 0.5 ,0.25 , 0.25 ) u 1= ( 0.39 , 0.44 ,0.17 )

3、u2= ( 0.44 , 0.42 ,0.14 )厂家 2 的方案选择有了均衡状态时的市场占有率 u , u1 和 u2 ,厂家 2 就能够方便地进行分别方案选择,根据前面的数据,我们知道: u=0.25 , u1=0.44 , u2=0.42 , 因此,如果采用方案一可获利: 100 (0.44- 0.25) 50 450=500 (万元) 如果采用方案二可获利: 100 (0.42- 0.25) 50 400=450 (万元)结论:选择方案一,即吸引老客户的方案为佳。 例:人力资源预测某高校1990年为编制师资发展规划,需要预测为了教师队伍的结构。现在对教师状况进行如下四个分类:青年,中年

4、,老年和流退(流失或退休)。根据历史资料以及调查分析,各类教师按照一年一期的状态转移概率矩阵如下,目前青年教师400人,中年教师360人,老年教师300人。试分析3年后教师的结构以及为保持编制不变,3年内应当多少硕士和博士毕业生充实教师队伍?马尔可夫( Markov )链随机过程:不确定变化的随机变量序列时间序列:X1 , X2 , Xt, ,指与时间相关的离散随机变量序列状态集合: S=S1 , S2 , Sn ,一般表示为 Xt= Si无后效性(马尔可夫性):时间序列在 t+1 时刻(将来)的状态只与 t 时刻(现在)的状态有关而与 t 时刻之前(过去)的状态无关,即 P Xk+1= Si

5、k+1/ X1=Sik1 , X2=Sik2 , ,Xk=Sik =P Xk+1= Sik+1/Xk=Sik马尔可夫( Markov )链:具备无后效性的时间序列。状态转移概率矩阵 P状态转移概率: pij 表示从状态 Si 转移到状态 Sj 的概率,记: pij= P ( Sj/ Si ) =P ( Xk+1=Sj/Xk= Si ), 简称为从状态 i 到状态 j 的转移概率。状态转移概率矩阵:由状态转移概率 pij ( i , j=1,2 ,,n )构成的 n 阶方阵 P多步状态转移概率 pij一步状态转移概率:用 pij(1) 表示, pij(1) 即 pij ,表示从状态 Si 经过一

6、个时刻转移到状态 Sj 的概率,记为: pij=pij(1)=P ( Xt+1= Sj/Xt= Si ),相应的一步状态转移概率矩阵记为 P ( 1 )= P 。k 步状态转移概率:用 pij(k) 表示,表示从状态 Si 经过 k 个时刻转移到状态 Sj 的概率,记为: pij(k)=P ( Xt+ k=Sj/Xt= Si ),相应的 k 步状态转移概率矩阵记为 P ( k )。 P(k) 与 P ( 1 )之间的关系如何?例:三品牌洗衣粉下月购买意愿调查求( 1 )一步状态转移概率矩阵 P ( 1 )=? ( 2 )购买 C 品牌的顾客在未来第 2 个月购买各品牌的概率? ( 3 )二步状

7、态转移概率矩阵 P ( 2 )=?您发现P(K)的一般规律了吗? A B C 调查总数 A B C 40 30 30 60 30 60 60 30 30 100 150 120规律:P(K)=Pk定理: k 步状态转移概率矩阵 P ( k )等于一步状态转移概率矩阵 P ( 1 )= P 的k 次幂, 即P(k)=P P P= Pk例:通过 P ( 1 )计算 P ( 3 )已知一步状态转移概率矩阵 P ( 1 )= P ,计算三步状态转移概率矩阵P ( 3 )=?固定概率向量 u设 P 为马尔可夫( Markov )链的一步状态转移概率矩阵,如果存在概率向量 u=( u1 , u2 ,, u

8、n) 满足于 uP =u 则称 u 为 P 的固定概率向量或者均衡点示例: u 为 P 的固定概率向量引例中均衡状态时的市场占有率就是 P 的固定概率向量(均衡点) u 。均衡点是否一定存在,是否唯一?牛奶厂例:市场占有率变动表及均衡状态月份 k三个厂家的市场占有率u1u2u3012345670.40.520.4960.50080.499840.5000320.50.50.30.240.2520.24960.250080.2499840.250.250.30.240.2520.24960.250080.2499840.250.25正规概率矩阵设 P 为马尔可夫链的一步状态转移概率矩阵,如果存在

9、自然数 k 使 Pk 的所有元素都是正数,则称 P 为正规概率矩阵。正规概率矩阵的例子正规概率矩阵的判断方法:看任意两状态之间是否可以相互连通(彼此到达),若是,则为正规概率矩阵,若否,则不是正规概率矩阵。马尔可夫链基本定理定理:设 P 为马尔可夫链的一步状态转移概率矩阵,如果 P 为正规概率矩阵,则存在唯一的由正数组成的固定概率向量(均衡点) u ,并且对于任意的初始概率向量 u0 ,向量序列: u0 P , u0 P2 , u0 Pk 以 u 为极限, 即当 k 时,有 lim u0 Pk =u均衡点举例均衡点 u 的求法设概率向量 u 为状态转移矩阵 P 的均衡点,有: uP =u 即 u ( P- I) =0 ,其中I为单位矩阵 等式两边取转置,得到: ( PT - I) uT =0方法:联立求解以下线性方程组 ( PT - I) uT =0 u1+u2+ + un =1例:项目选址问题某汽车维修公司有甲、乙、丙3个维修厂。由于公司注重对员工的技术培训,树立顾客至上,信誉第一的理念,管理模

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论