运筹学课件——第4讲 马尔可夫决策.ppt

引例 牛奶厂决策 最佳经营策略选择 北京地区鲜牛奶由三个厂家提供 该地区客户总数为100万户 假定厂家每年从每个客户那里平均获利50元 客户资源每月都在三个厂家之间相互流动 厂家2考虑从以下两套候选方案之中选择一个实施 方案一 吸引老客户 须花费450万元 方案二 吸引厂家1和厂家3的客户 须花费400万元 您有什么好的建议来帮助厂家2决策 市场调查数据 今年一月份厂家2对2000名消费者进行了调查 购买厂家1 2 3产品的消费者人数分别为800 600和600 得到市场占有率向量 概率向量 为 0 4 0 3 0 3 同时通过询问这2000名消费者下月的购买倾向 得到如下转移频数矩阵 1 2 3 1 2 3 状态转移概率矩阵P 从转移频数矩阵到状态转移概率矩阵P 用各行总数分别去除转移频数矩阵N的每行各元素 得到状态转移概率矩阵P如下 800 600 600 均衡状态的市场占有率 在目前状态转移概率矩阵P下 达到均衡状态时的市场占有率记为u 估计如果实施方案一或二以后状态转移概率矩阵分别为P1和P2 他们各自对应的均衡状态时市场占有率分别为u1和u2 具体数据如下 u 0 5 0 25 0 25 u1 0 39 0 44 0 17 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年为编制师资发展规划 需要预测为了教师队伍的结构 现在对教师状况进行如下四个分类 青年 中年 老年和流退 流失或退休 根据历史资料以及调查分析 各类教师按照一年一期的状态转移概率矩阵如下 目前青年教师400人 中年教师360人 老年教师300人 试分析3年后教师的结构以及为保持编制不变 3年内应当多少硕士和博士毕业生充实教师队伍 马尔可夫 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 链 具备无后效性的时间序列 状态转移概率矩阵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经过一个时刻转移到状态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 二步状态转移概率矩阵P 2 您发现P K 的一般规律了吗 规律 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 un 满足于uP u则称u为P的固定概率向量或者均衡点示例 u为P的固定概率向量引例中均衡状态时的市场占有率就是P的固定概率向量 均衡点 u 均衡点是否一定存在 是否唯一 牛奶厂例 市场占有率变动表及均衡状态 正规概率矩阵 设P为马尔可夫链的一步状态转移概率矩阵 如果存在自然数k使Pk的所有元素都是正数 则称P为正规概率矩阵 正规概率矩阵的例子正规概率矩阵的判断方法 看任意两状态之间是否可以相互连通 彼此到达 若是 则为正规概率矩阵 若否 则不是正规概率矩阵 马尔可夫链基本定理 定理 设P为马尔可夫链的一步状态转移概率矩阵 如果P为正规概率矩阵 则存在唯一的由正数组成的固定概率向量 均衡点 u 并且对于任意的初始概率向量u0 向量序列 u0P u0P2 u0Pk以u为极限 即当k 时 有limu0Pk u均衡点举例 均衡点u的求法 设概率向量u为状态转移矩阵P的均衡点 有 uP u即u P I 0 其中I为单位矩阵等式两边取转置 得到 PT I uT 0方法 联立求解以下线性方程组 PT I uT 0u1 u2 un 1 例 项目选址问题 某汽车维修公司有甲 乙 丙3个维修厂 由于公司注重对员工的技术培训 树立顾客至上 信誉第一的理念 管理模式先进 所以公司在本行业具有良好的形象 形成