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

1、引例：牛奶厂决策引例：牛奶厂决策 最佳经营策略选择：最佳经营策略选择： 北京地区鲜牛奶由三个厂家提供，该地北京地区鲜牛奶由三个厂家提供，该地区客户总数为区客户总数为 100 万户，假定厂家每年从每个万户，假定厂家每年从每个客户那里平均获利客户那里平均获利 50 元，客户资源每月都在三元，客户资源每月都在三个厂家之间相互流动，厂家个厂家之间相互流动，厂家 2 考虑从以下两套考虑从以下两套候选方案之中选择一个实施：候选方案之中选择一个实施： 方案一：吸引老客户，须花费方案一：吸引老客户，须花费 450 万元；万元； 方案二：吸引厂家方案二：吸引厂家 1 和厂家和厂家 3 的客户，须花的客户，须花费

2、费 400 万元。万元。 您有什么好的建议来帮助厂家您有什么好的建议来帮助厂家 2 决策？决策？市场调查数据市场调查数据 今年一月份厂家今年一月份厂家 2 对对 2000 名消费者进行了调名消费者进行了调查，购买厂家查，购买厂家 1 ， 2 ， 3 产品的消费者人数分别为产品的消费者人数分别为 800 ， 600 和和 600 ，得到市场占有率向量（概率向，得到市场占有率向量（概率向量）为（量）为（ 0.4 ， 0.3 ， 0.3 ）；）； 同时通过询问这同时通过询问这 2000 名消费者下月的购买名消费者下月的购买倾向，得到如下转移频数矩阵：倾向，得到如下转移频数矩阵： 1806036060

3、180360240240320n1 12 23 31 12 23 3状态转移概率矩阵状态转移概率矩阵 p 从转移频数矩阵到从转移频数矩阵到状态转移概率矩阵状态转移概率矩阵 p ： 用各行总数分别去除转移频数矩阵用各行总数分别去除转移频数矩阵 n 的每行的每行各元素，得到状态转移概率矩阵各元素，得到状态转移概率矩阵 p 如下：如下：1806036060180360240240320n3 . 01 . 06 . 01 . 03 . 06 . 03 . 03 . 04 . 0p/800/600/600均衡状态的市场占有率均衡状态的市场占有率 在目前状态转移概率矩阵在目前状态转移概率矩阵 p 下，达到

4、均衡状态时的市下，达到均衡状态时的市场占有率记为场占有率记为 u ；估计如果实施方案一或二以后状态；估计如果实施方案一或二以后状态转移概率矩阵分别为转移概率矩阵分别为 p1 和和 p2 ，他们各自对应的均衡，他们各自对应的均衡状态时市场占有率分别为状态时市场占有率分别为 u1 和和 u2 ；具体数据如下：；具体数据如下：3 . 01 . 06 . 01 . 03 . 06 . 03 . 03 . 04 . 0p3 . 01 . 06 . 007 . 03 . 03 . 03 . 04 . 01p1 . 05 . 04 . 01 . 03 . 06 . 02 . 05 . 03 . 02p u=

5、 （ 0.5 ，0.25 ， 0.25 ） u 1= （ 0.39 ， 0.44 ，0.17 ） u2= （ 0.44 ， 0.42 ，0.14 ）厂家厂家 2 2 的方案选择的方案选择 有了均衡状态时的市场占有率有了均衡状态时的市场占有率 u ， u1 和和 u2 ，厂家，厂家 2 就能够方便地进行分别方案选择，根据前面的数据，就能够方便地进行分别方案选择，根据前面的数据，我们知道：我们知道： u=0.25 ， u1=0.44 ， u2=0.42 ， 因此，如果采用方案一可获利：因此，如果采用方案一可获利： 100 (0.44- 0.25) 50 450=500 （万元）（万元） 如果采用方

6、案二可获利：如果采用方案二可获利： 100 (0.42- 0.25) 50 400=450 （万元）（万元）结论：选择方案一，即吸引老客户的方案为佳。结论：选择方案一，即吸引老客户的方案为佳。 例：人力资源预测例：人力资源预测 某某高校高校1990年为编制师资发展规划，需要预测年为编制师资发展规划，需要预测为了教师队伍的结构。现在对教师状况进行如为了教师队伍的结构。现在对教师状况进行如下四个分类：青年，中年，老年和流退（流失下四个分类：青年，中年，老年和流退（流失或退休）。根据历史资料以及调查分析，各类或退休）。根据历史资料以及调查分析，各类教师按照一年一期的状态转移概率矩阵如下，教师按照一年

7、一期的状态转移概率矩阵如下，目前青年教师目前青年教师400人，中年教师人，中年教师360人，老年教人，老年教师师300人。试分析人。试分析3年后教师的结构以及为保持年后教师的结构以及为保持编制不变，编制不变，3年内应当多少硕士和博士毕业生年内应当多少硕士和博士毕业生充实教师队伍？充实教师队伍？马尔可夫（马尔可夫（ markov markov ）链）链 随机过程：不确定变化的随机变量序列随机过程：不确定变化的随机变量序列 时间序列：时间序列：x1 ， x2 ， xt, ，指与时间相关，指与时间相关的离散随机变量序列的离散随机变量序列 状态集合：状态集合： s=s1 ， s2 ， sn ，一般表示

8、为，一般表示为 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 表示从状态表示从状态

9、 si 转移到状态转移到状态 sj 的概的概率，记：率，记： pij= p （ sj/ si ） =p （ xk+1=sj/xk= si ）, 简称为从状态简称为从状态 i 到状态到状态 j 的转移概率。的转移概率。 状态转移概率矩阵：由状态转移概率状态转移概率矩阵：由状态转移概率 pij （ i ， j=1,2 ，,n ）构成的）构成的 n 阶方阵阶方阵 pnnnnnnnxnpppppppppppij.)(212222111211多步状态转移概率多步状态转移概率 pij 一步状态转移概率：用一步状态转移概率：用 pij(1) 表示，表示， pij(1) 即即 pij ，表，表示从状态示从状态

10、 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 ）之

11、间的关系如何）之间的关系如何?例：三品牌洗衣粉下月例：三品牌洗衣粉下月购买意愿调查购买意愿调查求（求（ 1 ）一步状态转移概率矩阵）一步状态转移概率矩阵 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规律:p(k)=pk 定理定理: k 步状态转移概率矩阵步状态转移概率矩阵

12、p （ k ）等于一步状态转移概率矩阵等于一步状态转移概率矩阵 p （ 1 ）= p 的的k 次幂次幂, 即即 p(k)=p p p= pk例：通过例：通过 p p （ 1 1 ）计算）计算 p p （ 3 3 ） 已知一步状态转移概率矩阵已知一步状态转移概率矩阵 p （ 1 ）= p ，计算三步状态转移概率矩阵计算三步状态转移概率矩阵p （ 3 ）=?固定概率向量固定概率向量 u u 设设 p 为马尔可夫（为马尔可夫（ markov ）链的一步状态转移概率）链的一步状态转移概率矩阵，如果存在概率向量矩阵，如果存在概率向量 u=( u1 ， u2 ，, un) 满足满足于于 up =u 则称则

13、称 u 为为 p 的固定概率向量或者均衡点的固定概率向量或者均衡点 示例：示例： u 为为 p 的固定概率向量的固定概率向量 引例中均衡状态时的市场占有率就是引例中均衡状态时的市场占有率就是 p 的固定的固定概率向量（均衡点）概率向量（均衡点） u 。 均衡点是否一定存在，是否唯一？均衡点是否一定存在，是否唯一？牛奶厂例：市场占有率变动牛奶厂例：市场占有率变动表及均衡状态表及均衡状态月份月份 k三个三个厂家的市场占有率厂家的市场占有率u1u2u3012345670.40.520.4960.50080.499840.5000320.50.50.30.240.2520.24960.250080.2

14、499840.250.250.30.240.2520.24960.250080.2499840.250.253 . 01 . 06 . 01 . 03 . 06 . 03 . 03 . 04 . 0p正规概率矩阵正规概率矩阵 设设 p 为马尔可夫链的一步状态转移概率矩阵，如果为马尔可夫链的一步状态转移概率矩阵，如果存在自然数存在自然数 k 使使 pk 的所有元素都是正数，则称的所有元素都是正数，则称 p 为正规概率矩阵。为正规概率矩阵。 正规概率矩阵的例子正规概率矩阵的例子 正规概率矩阵的判断方法：看任意两状态之间是否正规概率矩阵的判断方法：看任意两状态之间是否可以相互连通（彼此到达），若是，

15、则为正规概率可以相互连通（彼此到达），若是，则为正规概率矩阵，若否，则不是正规概率矩阵。矩阵，若否，则不是正规概率矩阵。马尔可夫链基本定理马尔可夫链基本定理 定理：设定理：设 p 为马尔可夫链的一步状态转移概率矩为马尔可夫链的一步状态转移概率矩阵，如果阵，如果 p 为正规概率矩阵，则存在唯一的由正为正规概率矩阵，则存在唯一的由正数组成的固定概率向量（均衡点）数组成的固定概率向量（均衡点） u ，并且对于，并且对于任意的初始概率向量任意的初始概率向量 u0 ，向量序列，向量序列: u0 p ， u0 p2 ， u0 pk 以以 u 为极限为极限, 即当即当 k 时时,有有 lim u0 pk =

16、u 均衡点举例均衡点举例均衡点 u 的求法 设概率向量设概率向量 u 为状态转移矩阵为状态转移矩阵 p 的均衡点，有：的均衡点，有： up =u 即即 u （ p- i） =0 ，其中，其中i为单位矩阵为单位矩阵 等式两边取转置，得到：等式两边取转置，得到： （ pt - i） ut =0 方法：联立求解以下线性方程组方法：联立求解以下线性方程组 （ pt - i） ut =0 u1+u2+ + un =1例：项目选址问题例：项目选址问题 某某汽车维修公司有甲、乙、丙汽车维修公司有甲、乙、丙3个维修厂。由于公个维修厂。由于公司注重对员工的技术培训，树立顾客至上，信誉第司注重对员工的技术培训，树立顾客至上，信誉第一的理念，管理模式先进，所以公司在本行业具有一的理念，管理模式先进，所以公司在本行业具有良好的形象，形成了一定规模的客户群。对客户的良好的形象，形成了一定规模的客户群。对客户的