决策理论与方法教学第四章(2).ppt

决策理论与方法 DecisionMakingTheoryandMethods 决策理论与方法 编写组 教育部高等学校管理科学与工程类学科专业教学指导委员会推荐教材 第四章动态决策分析 学习目的 了解多阶段决策 序贯决策的概念及特点 掌握动态规划与决策树方法及其在多阶段决策 序贯决策中的应用 本讲内容 4 3序贯决策4 3 1序贯决策的基本概念4 3 2序贯决策的决策方法 4 3序贯决策 4 3 1序贯决策的基本概念上面的多阶段决策 阶段数是确定的 除这种决策外 还有一些决策的阶段数不是事先确定的 它依赖于执行决策过程中出现的情况 这种决策问题称为序贯决策 sequentialdecisionproblem 序列决策在进行决策后又产生一些新的情况 需要进行新的决策 接着又有一些新的情况 又需要进行新的决策 这样决策 情况 决策 这就构成一个序列 4 3序贯决策 4 3 1序贯决策的基本概念序贯决策是用于随机性或不确态定性动态系统最优化的决策方法 它的特点是 1 所研究的系统是动态的 即系统所处的状态与时间有关 可周期 或连续 地对它观察 2 决策是序贯地进行的 即每个时刻根据所观察到的状态和以前状态的记录 从一组可行方案中选用一个最优方案 即作最优决策 使取决于状态的某个目标函数取最优值 极大或极小值 3 系统下一步 或未来 可能出现的状态是随机的或不确定的 4 3序贯决策 4 3 1序贯决策的基本概念系统在每次作出决策后下一步可能出现的状态是不能确切预知的 存在两种情况 1 系统下一步可能出现的状态的概率分布是已知的 可用客观概率的条件分布来描述 对于这类系统的序贯决策研究得较完满的是状态转移律具有无后效性的系统 相应的序贯决策称为马尔可夫决策过程 它是将马尔可夫过程理论与决定性动态规划相结合的产物 2 系统下一步可能出现的状态的概率分布不知道 只能用主观概率的条件分布来描述 用于这类系统的序贯决策属于决策分析的内容 4 3序贯决策 4 3 2序贯决策的决策方法序贯决策的过程是 从初始状态开始 每个时刻做出最优决策后 接着观察下一步实际出现的状态 即收集新的信息 然后再做出新的最优决策 反复进行直至最后 解决序贯决策问题的有效办法仍然是决策树 解决序贯决策的关键是确定一个决策序列终止的原则 在下例中 这个原则就是 不管到决策的哪个阶段 只要有一个非经抽样的后悔期望值小于进行一次抽样的费用 决策序列便可终止 4 3序贯决策 4 3 2序贯决策的决策方法例4 3 1某工厂的产品每1000件装成一箱出售 每箱中产品的次品率有0 01 0 40 0 90三种可能 其概率分别为0 2 0 6 0 2 现在的问题是 出厂前是否要对产品进行严格检验 将次品挑出 可以选择的行动有两个 整箱检验 a1 检验费为每箱100元 整箱不检验 a 但如果顾客在使用中发现次品 每件次品除条换为合格品外还要赔偿0 25元损失费 4 3序贯决策 为了更好地做出决定可以先从一箱中随机抽取1件作为样本检验它 然后根据这件产品是都次品再决定该箱是否要检验 抽样成本为4 2元 进行第一次抽样后 除选择检验还是不检验外 还可以根据前面抽样的结果 考虑再进行一次抽样检验如此形成一个决策序列 试进行序列决策 1 是否需要抽样 若需要 抽样几次 2 在抽样或不抽样的前提下 采用何种方案进行检验 例8 2 解 1 2 3分别表示产品次品率为0 01 0 4 0 9三种状态 对于抽样检验一件产品 X 1和X 0分别表示样品为次品和合格品两个结果 结果值均用期望损失值表示 序列决策树图不能够一次绘制成功 而是随着决策过程序列的延伸和终止依次进行 为了简化图形 行动方案al和a2可能出现的状态及其对应的损失值均在图中略去 仅在方案枝末端标注上期望损失值 4 5 3 2 8 6 7 抽样 继续抽样 a1 a2 A1 A2 A3 A4 不抽样 X1 0 X1 1 停止抽样 9 X2 0 X2 1 a1 a2 继续抽样 停止抽样 略 相应的损失矩阵为 先进行第一次抽样的后验概率计算 该问题的费用矩阵为 例8 2 第一次抽样的后验概率矩阵为 后验行动方案的期望损失值矩阵为 一次抽样后最满意方案分别为 6 89 4 325 0 4582 19 5 2 69 33 40 4 325 0 4582 53 31 19 5 25 抽样 a1 a2 a1 a2 a1 a2 A1 A2 A3 A4 S1 S2 不抽样 X1 0 X1 1 0 578 0 422 0 3426 0 6228 0 0346 0 3426 0 5687 0 4265 0 0047 0 5687 0 4265 0 2 0 6 0 2 0 0047 0 5687 0 4265 0 2 0 2 0 6 97 5 0 0 0 0 125 97 5 0 0 0 0 125 97 5 0 0 0 0 125 期望损失值 包含抽样费用 4 20 若为正品 则无须检验整箱产品 若为次品 则整箱检验 最满意方案是 应抽取一件产品作样品检验 在A2上X1 1的决策点处 由于行动方案a1的期望损失值0 4582已小于抽样费用4 20 所以第二次抽样分支S2在此处被截断 决策序列在该分支上终止 而在Xl 0的决策点处 由于行动方案al a2 的期望损失值分别为33 40和4 324 均大于抽样费用4 20 因此 在此分支上 可进行第二次抽样 抽样结果用X2表示 X2 0和X2 1分别表示第二次抽样抽取一个样品为正品和次品 第二次抽样的后验概率计算如下 第二次抽样的后验概率矩阵为 后验行动方案的期望损失值矩阵为 二次抽样后最满意方案分别为 由于X2 0在的决策点处 方案a2的期望损失值0 6038已小于抽样费用4 20 则序列决策的这一分支应该终止 同样 对于X2 1决策点处 由于方案a1的期望损失值1 1778也小于抽样费用 则这一分枝也应终止 于是 到此决策序列全部终止 4 20 a1 a2 s1 a1 a2 s2 X1 0 25 33 4 4 325 4 20 19 5 0 578 a1 a2 s3 X2 0 46 17 0 6038 4 20 0 7163 a1 a2 s3 X1 1 13 73 4 20 0 2837 1 1778 a1 a2 s2 X1 1 13 73 4 20 0 422 0 4582 A1 A2 A3 S1 S2 6 89 2 69 4 325 0 4582 0 7666 4 325 1 1778 在A3上X2 0的决策点处 最满意行动方案为a2 截去a1和s3 在X2 1的决策点处 最满意行动方案为a1 截去a2和s3 在s2状态点处 期望损失值为 在A2上X1 0的决策点处 最满意行动方案为a2 截去a1和s2 在X1 1的决策点处 最满意行动方案为a1 截去a2和s2 在s1状态点处 期望损失值为 在A1决策点处 最满意方案的期望损失值为 所以截去a1和a2 综上所述 决策是 应该进行一次抽样检验 若为正品 则采取行动方案a2 即整箱产品不予检验 若为次品 则采取行动方案a1 即整箱产品予以检验 序列决策过程也可以用简化决策树图表示 6 89 2 69 4 20 4 325 0 4582 s1 0 578 0 422 a1 a2 4 325 0 4621 4 4马尔可夫决策 研究这样的一类决策问题 采取的行动已经确定 但将这个行动付诸实践的过程又分为几个时期 在不同的时期 系统可以处在不同的状态 而这些状态发生的概率又可受前面时期实际所处状态的影响 其中一种最简单 最基本的情形 是每一时期状态参数的概率分布只与这一时期的前一时期实际所处的状态有关 而与更早的状态无关 这就是所谓的马尔可夫链 4 4马尔可夫决策 4 4 1马尔可夫决策问题马氏过程马尔科夫 M A Markov 提出一种描述系统状态转移的数学模型 称为马尔科夫过程 简称马氏过程 马氏决策利用马氏过程分析系统当前状态并预测未来状态的决策方法 称为马尔科夫决策 简称马氏决策 4 4马尔可夫决策 4 4 2马尔可夫链与转移概率矩阵若随机过程 X t t T 对于任意的t1 t2 tn ti T都有P x tn y x tn 1 xn 1 x t1 x1 P x tn y x tn 1 xn 1 则称 X t t T 具有马尔可夫性 含义 x tn 的将来只是通过现在与过去发生联系 一旦现在已知 则将来与过去无关 4 4 2马尔可夫链与转移概率矩阵 条件概率P xn j xn 1 i 称为转移概率 表示系统在n 1步状态为i时 第n步状态为j的概率 一步转移概率 若一步转移概率不随时间变化 具有稳定性 记pij P xn j xn 1 i 称矩阵P pij 为转移概率矩阵 其中 4 4 2马尔可夫链与转移概率矩阵 马尔可夫链定义如果随机过程 Xt t 1 2 满足下述性质 则称 Xt 是一个有限状态的马尔可夫 Markov 链 1 具有有限种状态 2 具有马尔可夫性 3 转移概率具有平稳性 4 4马尔可夫决策 例 某企业为使技术人员具有多方面经验 实行技术人员在技术部门 生产部门和销售部门的轮换工作制度 轮换办法采取随机形式 每半年轮换一次 初始状态 即技术人员开始是在某部门工作的概率用Pj 0 表示 j 1 2 3 pij表示处于第i个部门的技术人员在半年后转移到第j个部门的概率 4 4马尔可夫决策 已知 问某人开始在第1部门工作 一年后在第2部门工作的概率是多少 一年后 技术人员在3个部门工作的概率各为多少 4 4马尔可夫决策 解 由状态1经过两次转移到状态2的所有途径为1 1 2 1 2 2 1 3 2记由状态i经两步转移到状态j的概率为 则 若某人开始在第一部门工作 则一年后在第二部门工作的概率是50 4 4马尔可夫决策 解 记一年后技术人员在第j个部门工作的概率为Pj 2 则 一年后 技术人员在3个部门工作的概率 4 4马尔可夫决策 由上例可看出 从而有 一般地 有 4 4马尔可夫决策 4 4 3稳态概率 为稳态概率 由于初始状态对n步转移后所处状态的影响随n增大而减少 故 因此我们可以从n步转移矩阵的极限取得稳态概率分布 称 4 4马尔可夫决策 得 且 此方程组称为稳态方程 记 则 4 4 4马尔可夫应用实例 例1某生产商标为A的产品的厂商为了与另外两个生产同类产品B和C的厂家竞争 有三种可供选择的措施 1 发放有奖债券 2 开展广告宣传 3 优质售后服务 三种方案分别实施以后 经统计调查可知 该类商品的市场占有率的转移矩阵分别是 该类商品的月总销售量为1000万件 每件可获利1元 另外 三种措施的成本费分别为150万 40万 30万 为长远利益考虑 生产商标为A的产品的厂商应该采取何种措施 解 采取第一种措施的稳态概率 解得 且 解 同理可解出采取第二 第三种措施的稳态概率分别为 计算生产A的厂商采取三种方案的期望利润如下 因此生产A的厂商应采取的长期策略为方案 2 例2 我国出口某种设备 在国际市场上的销售状况有两种 畅销和滞销 畅销每年可以获利100万元 滞销时每年仅获利30万元 以一年为一个时期 如果不采用广告推广产品或采取广告措施 状态的转移矩阵分别如下 不采取广告措施 采取广告措施 例2 假定上一年处于畅销状态 每年的广告费为15万元 为了保证今后3年的利润最大化 是否应该采用广告措施 解 1 若不采取广告措施 上一年畅销情况下 三年的期望利润总和为 例2 解 1 若采取广告措施 上一年畅销情况下 三年的期望利润总和为 因