《运筹学——马尔可夫决策.pptx》由会员分享，可在线阅读，更多相关《运筹学——马尔可夫决策.pptx（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、市场调查数据市场调查数据 今年一月份厂家 2 对 2000 名消费者进行了调查，购买厂家 1，2，3 产品的消费者人数分别为 800，600 和 600，得到市场占有率向量（概率向量）为（0.4，0.3，0.3）；同时通过询问这 2000 名消费者下月的购买倾向，得到如下转移频数矩阵：1 12 23 31 12 23 3第1页/共20页状态转移概率矩阵状态转移概率矩阵 P从转移频数矩阵到状态转移概率矩阵 P：用各行总数分别去除转移频数矩阵 N 的每行各元素，得到状态转移概率矩阵 P 如下：/800/600/600第2页/共20页均衡状态的市场占有率均衡状态的市场占有率在目前状态转移概率矩阵 P
2、 下，达到均衡状态时的市场占有率记为 u；估计如果实施方案一或二以后状态转移概率矩阵分别为 P1 和 P2，他们各自对应的均衡状态时市场占有率分别为 u1 和 u2；具体数据如下：u=（0.5，0.25，0.25）u 1=（0.39，0.44，0.17）u2=（0.44，0.42，0.14）第3页/共20页厂家厂家 2 2 的方案选择的方案选择有了均衡状态时的市场占有率有了均衡状态时的市场占有率 u，u1 和和 u2，厂家，厂家 2 就能够方便地进就能够方便地进行分别方案选择，根据前面的数据，我们知道：行分别方案选择，根据前面的数据，我们知道：u=0.25，u1=0.44，u2=0.42，因此
3、，如果采用方案一可获利：100 (0.44-0.25)50 450=500（万元）如果采用方案二可获利：100 (0.42-0.25)50 400=450（万元）结论：选择方案一，即吸引老客户的方案为佳。第4页/共20页例：人力资源预测例：人力资源预测某高校1990年为编制师资发展规划，需要预测为了教师队伍的结构。现在对教师状况进行如下四个分类：青年，中年，老年和流退（流失或退休）。根据历史资料以及调查分析，各类教师按照一年一期的状态转移概率矩阵如下，目前青年教师400人，中年教师360人，老年教师300人。试分析3年后教师的结构以及为保持编制不变，3年内应当多少硕士和博士毕业生充实教师队伍？
4、第5页/共20页马尔可夫（马尔可夫（Markov Markov）链）链随机过程：不确定变化的随机变量序列时间序列：X1，X2，Xt,，指与时间相关的离散随机变量序列状态集合：S=S1，S2，Sn，一般表示为 Xt=Si无后效性（马尔可夫性）：时间序列在 t+1 时刻（将来）的状态只与 t 时刻（现在）的状态有关而与 t 时刻之前（过去）的状态无关，即 P Xk+1=Sik+1/X1=Sik1，X2=Sik2，,Xk=Sik =P Xk+1=Sik+1/Xk=Sik马尔可夫（Markov）链：具备无后效性的时间序列。第6页/共20页状态转移概率矩阵状态转移概率矩阵 P状态转移概率：状态转移概率：
5、pij 表示从状态表示从状态 Si 转移到状态转移到状态 Sj 的概率，记：的概率，记：pij=P（Sj/Si）=P（Xk+1=Sj/Xk=Si）,简称为从状态简称为从状态 i 到状态到状态 j 的的转移概率。转移概率。状态转移概率矩阵：由状态转移概率状态转移概率矩阵：由状态转移概率 pij（i，j=1,2，,n）构成的）构成的 n 阶方阵阶方阵 P第7页/共20页多步状态转移概率多步状态转移概率 pij一步状态转移概率：用一步状态转移概率：用 pij(1)表示，表示，pij(1)即即 pij，表示从状态，表示从状态 Si 经过一个时刻转移到状态经过一个时刻转移到状态 Sj 的概的概率，记为：
6、率，记为：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）之间的关系如何）之间的关系如何?第8页/共20页例：三品牌洗衣粉下月例：三品牌洗衣粉下月购买意愿调查购买意愿调查求（1）一步状态转移概
7、率矩阵 P（1）=?（2）购买 C 品牌的顾客在未来第 2 个月购买各品牌的概率?（3）二步状态转移概率矩阵 P（2）=?您发现P（K）的一般规律了吗？A B C 调查总数 A B C 40 30 30 60 30 60 60 30 30 100 150 120第9页/共20页规律:P(K)=Pk定理:k 步状态转移概率矩阵 P（k）等于一步状态转移概率矩阵 P（1）=P 的k 次幂,即P(k)=P P P=Pk第10页/共20页例：通过例：通过 P P（1 1）计算）计算 P P（3 3）已知一步状态转移概率矩阵 P（1）=P，计算三步状态转移概率矩阵P（3）=?第11页/共20页固定概率向
8、量固定概率向量 u u设 P 为马尔可夫（Markov）链的一步状态转移概率矩阵，如果存在概率向量 u=(u1，u2，,un)满足于 uP=u 则称则称 u 为为 P 的固定概率向量或者均衡点的固定概率向量或者均衡点示例：示例：u 为为 P 的固定概率向量的固定概率向量引例中均衡状态时的市场占有率就是引例中均衡状态时的市场占有率就是 P 的固定概率向量（均衡的固定概率向量（均衡点）点）u。均衡点是否一定存在，是否唯一？均衡点是否一定存在，是否唯一？第12页/共20页牛奶厂例：市场占有率变动牛奶厂例：市场占有率变动表及均衡状态表及均衡状态月份月份 k三个厂家的市场占有率三个厂家的市场占有率u1u
9、2u3012345670.40.520.4960.50080.499840.5000320.50.50.30.240.2520.24960.250080.2499840.250.250.30.240.2520.24960.250080.2499840.250.25第13页/共20页正规概率矩阵正规概率矩阵设 P 为马尔可夫链的一步状态转移概率矩阵，如果存在自然数 k 使 Pk 的所有元素都是正数，则称 P 为正规概率矩阵。正规概率矩阵的例子正规概率矩阵的例子正规概率矩阵的判断方法：看任意两状态之间是正规概率矩阵的判断方法：看任意两状态之间是否可以相互连通（彼此到达），若是，则为正规否可以相互连
10、通（彼此到达），若是，则为正规概率矩阵，若否，则不是正规概率矩阵。概率矩阵，若否，则不是正规概率矩阵。第14页/共20页马尔可夫链基本定理马尔可夫链基本定理定理：设 P 为马尔可夫链的一步状态转移概率矩阵，如果 P 为正规概率矩阵，则存在唯一的由正数组成的固定概率向量（均衡点）u，并且对于任意的初始概率向量 u0，向量序列:u0 P，u0 P2，u0 Pk 以以 u 为极限为极限,即当即当 k 时时,有有 lim u0 Pk=u均衡点举例均衡点举例第15页/共20页均衡点 u 的求法设概率向量 u 为状态转移矩阵 P 的均衡点，有：uP=u 即即 u（P-I）=0，其中，其中I为单位矩阵为单位
11、矩阵 等式两边取转置，得到：等式两边取转置，得到：（PT-I）uT=0方法：联立求解以下线性方程组方法：联立求解以下线性方程组 （PT-I）uT=0 u1+u2+un=1第16页/共20页例：项目选址问题例：项目选址问题某汽车维修公司有甲、乙、丙3个维修厂。由于公司注重对员工的技术培训，树立顾客至上，信誉第一的理念，管理模式先进，所以公司在本行业具有良好的形象，形成了一定规模的客户群。对客户的调查显示，客户在甲、乙、丙3个维修厂之间的转移概率如下，由于资金的原因，公司目前打算只对其中的一个 维修厂 进行改造，并且扩大 规 模。试决定应该 选择哪个维修厂？第17页/共20页作业作业作业本：习题作业本：习题1.61.6预习：层次分析方法决策预习：层次分析方法决策第18页/共20页 谢谢！谢谢！再再 见！见！第19页/共20页感谢您的观看！第20页/共20页