决策理论与方法教学作者罗党第四章动态决策分析.ppt

决策理论与方法 DecisionMakingTheoryandMethods 决策理论与方法 编写组 教育部高等学校管理科学与工程类学科专业教学指导委员会推荐教材 第四章动态决策分析 学习目的 了解多阶段决策 序贯决策的概念及特点 掌握动态规划与决策树方法及其在多阶段决策 序贯决策中的应用 本讲内容 4 1动态决策的基本原理4 2多属性决策 4 1多阶段决策问题的提出 4 1 1动态规划概述 规划问题的最终目的就是确定各决策变量的取值 以使目标函数达到极大或极小 在线性规划和非线性规划中 决策变量都是以集合的形式被一次性处理的 然而 有时我们也会面对决策变量需分期 分批处理的多阶段决策问题 所谓多阶段决策问题是指这样一类活动过程 它可以分解为若干个互相联系的阶段 在每一阶段分别对应着一组可供选取的决策集合 即构成过程的每个阶段都需要进行一次决策 将各个阶段的决策综合起来构成一个决策序列 称为一个策略 显然 由于各个阶段选取的决策不同 对应整个过程可以有一系列不同的策略 当过程采取某个具体策略时 相应可以得到一个确定的效果 采取不同的策略 就会得到不同的效果 多阶段的决策问题 就是要在所有可能采取的策略中选取一个最优策略 以便得到最佳的效果 动态规划同前面介绍过的各种优化方法不同 它不是一种算法 而是考察问题的一种途径 动态规划是一种求解多阶段决策问题的系统技术 可以说它横跨整个规划领域 线性规划和非线性规划 当然 由于动态规划不是一种特定的算法 因而它不像线性规划那样有一个标准的数学表达式和明确定义的一组规则 动态规划必须对具体问题进行具体的分析处理 在多阶段决策问题中 有些问题对阶段的划分具有明显的时序性 动态规划的 动态 二字也由此而得名 动态规划的主要创始人是美国数学家贝尔曼 20世纪40年代末50年代初 当时在兰德公司从事研究工作的贝尔曼首先提出了动态规划的概念 1951年贝尔曼首先提出了动态规划中解决多阶段决策问题的最优化原理 并给出了许多实际问题的解法 1957年贝尔曼出版了他的第一部著作 动态规划 标志着运筹学这一重要分支的诞生 该著作成为当时唯一的进一步研究和应用动态规划的理论源泉 1961年贝尔曼出版了他的第二部著作 并于1962年同杜瑞佛思合作出版了第三部著作 在贝尔曼及其助手们致力于发展和推广这一技术的同时 其他一些学者也对动态规划的发展作了巨大的贡献 其中最值得一提的是爱尔思和梅特顿 爱尔思先后于1961年和1964年出版了两部关于动态规划的著作 并于1964年同尼母霍思尔 威尔德一道创建了处理分支 循环性多阶段决策系统的一般性理论 梅特顿提出了许多对动态规划后来发展有着重要意义的基础性观点 并且对明晰动态规划路径的数学性质作出了巨大的贡献 动态规划从创立到现在50多年来 无论在工程技术 企业管理还是在工农业生产及军事等部门都有着广泛的应用 并取得了显著的效果 在管理方面 动态规划可用于资源分配问题 最短路径问题 库存问题 背包问题 设备更新问题 最优控制问题等等 所以动态规划是现代管理学中进行科学决策不可缺少的工具 动态规划的优点在于 它把一个多维决策问题转化为若干个一维最优化问题 而对一维最优化问题一个一个地去解 这种方法是许多求极值方法所做不到的 它几乎优于所有现存的优化方法 除此之外 动态规划能求出全局极大或极小 这一点也优于其他优化方法 需要指出的是 动态规划是求解最优化问题的一种方法 是解决问题的一种途径 而不是一种算法 在前面我们学习了用单纯形法解线性规划问题 凡是具有线性规划问题那样统一的数学模型都可以用单纯形法去求解 而 动态规划问题的求解却没有统一的方法 类似于单纯形法 因此在用动态规划求解最优化问题中 必须对具体问题具体分析 针对不同的问题 使用动态规划最优化原理和方法 建立起与其相应的数学模型 然后再用动态规划方法去求解 根据动态规划这些特点 要求我们在学好动态规划的基本原理和方法的同时 还应具有丰富的想象力 只有这样才能建好模型求出问题的最优解 4 1动态决策的基本原理 4 1 1动态规划动态规划 dynamicProgramming DP 是解决多阶段决策过程最优化的一种方法 其基本思路是将多阶段决策过程转化为一系列相互关联的单阶段问题 并依次求解 DP是离散系统最优化的一种有效工具 目前动态规划已广泛用于工业 农业 工程技术 资源 环境 经济 社会等领域 4 1动态决策的基本原理 4 1 1动态规划例4 1 1最优线路问题 由水源地向城市的输水线路需通过3个控制点 每个控制点均有两个可选方案 每段线路的输水费用如下图所示 选出一条输水线路 使得总输水费用最小 4 1动态决策的基本原理 4 1 1动态规划最优性原理 theprincipleofoptimality 也称为Bellman原理 是R Bellman提出的DP的基本原理 其表述为 一个过程的最优策略具有这样的性质 即无论初始状态和初始决策如何 对于由前面的决策所形成的状态来说 其后各阶段的决策序列必定构成相应子过程的最优策略 4 1动态决策的基本原理 4 1 2决策树决策树 decisiontree 就是将决策过程各个阶段之间的结构绘制成一张箭线图 每个决策或事件 即自然状态 都可能引出两个或多个事件 导致不同的结果 决策树的构成有四个要素 1 决策结点 2 方案枝 3 状态结点 4 概率枝 4 1动态决策的基本原理 4 1 2决策树 4 1动态决策的基本原理 4 1 2决策树决策树法的决策程序如下 1 绘制树状图 根据已知条件排列出各个方案和每一方案的各种自然状态 2 将各状态概率及损益值标于概率枝上 3 计算各方案期望值并将其标于该方案对应的状态结点上 4 进行剪枝 比较各个方案的期望值 并标于方案枝上 将期望值小的 即劣等方案剪掉 所剩的最后方案为最佳方案 4 2多阶段决策 多阶段决策有以下三个特点 第一 决策者需要做出时间上有先后之别的多个决策 第二 前一次决策的选择将直接影响到后一次决策 后一次决策的状态取决于前一次决策的结果 第三 决策者关心的是多次决策的总结果 而不是各次决策的即时后果 4 2多阶段决策 4 2 1多阶段决策过程的基本概念 1 阶段 2 状态 3 决策与策略 4 指标函数与目标函数 5 多阶段决策过程 4 2多阶段决策 4 2 2多阶段决策问题的决策方法多阶段决策问题包括确定型与随机型两大类 在确定型多阶段决策中 目标值都是确定值 在风险型多阶段决策中 目标值用期望值作为评价的标准 下面分别以两个例子说明其决策方法 4 2多阶段决策 4 2 2多阶段决策问题的决策方法例4 2 1某公司考虑为某新产品定价 该产品的单价拟从每件5元 6元 7元 8元这四个价格中选取其中之一 每年年初允许变动价格 但幅度不能超过1元 该公司预计该产品畅销只有五年 五年后将被淘汰 另据销售情况的预测 在价格不同的情况下各年的预计利润额见右表 4 2多阶段决策 4 2 2多阶段决策问题的决策方法例4 2 1决策图 4 2多阶段决策 4 2 2多阶段决策问题的决策方法例4 2 2为了更正确地掌握市场情况 正式投产公司打算先生产少量产品试销 试销费需要5000元 试销结果分为产品受欢迎 H1 一般 H2 和不受欢迎 H3 三种 由于试销面不宽 试销结果的准确性有限 其准确度 似然分布矩阵 见下表 4 2多阶段决策 4 2 2多阶段决策问题的决策方法例4 2 2的表格 如不买此项专利 把这笔费用用在其他方面 在同样的时期可获利1 1万元 那么 该公司应该如何决 1 是否买专利 2 如果买专利 是否采取试销办法 3 如果不试销 应大批生产 中批生产还是小批生产 如果试销 又应该如何根据试销结果决定其行动 第一阶段 1 2 7 买专利 不买专利 试销 不试销 3 4 5 6 H1 H2 H3 8 9 10 a1 a2 a3 1 2 3 略 第二阶段 第三阶段 例4 2 2 例4 2 2 解 这是一个三阶段决策问题 采用逆序归纳法进行决策分析 先要计算在一定的试销结果下的各后验概率 由全概率公式 计算得 例4 2 2 再由贝叶斯公式 计算得 例4 2 2 当试销结果为H1时 故当试销结果为H1时 应选择大批生产a1 截去方案a2 a3 结点4的值为3 406万元 结点8 结点9 结点10 例4 2 2 当试销结果为H2时 故当试销结果为H2时 应选择中批生产a2 截去方案a1 a3 结点5的值为2 62万元 例4 2 2 当试销结果为H3时 故当试销结果为H3时 也应选择中批生产a2 截去方案a1 a3 结点6的值为1 53万元 例4 2 2 试销收益期望值 故当不试销时 应选择大批生产a1 截去方案a2 a3 结点7的值为2 7万元 不试销的收益期望值 结点3 例4 2 2 决策 1 购买专利 2 不试销 3 大批生产a2 购买专利总期望收益 2 7 1 1 7万元 大于不买技术的收益1 1万元 截去不买专利方案 结点1的值为1 7万元 试销收益期望值扣除试销费用5000元后小于不试销的收益值 截去试销方案 结点2的值为2 7万元 第一阶段 1 2 7 买专利 不买专利 试销 不试销 3 4 5 6 H10 44 H20 39 H30 17 8 9 10 a1 a2 a3 0 818 0 136 0 046 略 第二阶段 第三阶段 例4 2 2 4万元 2万元 3万元 1 1万元 3 406万 2 77万 1万 3 406万 2 62万 1 53万 2 78054万 0 5万 2 7万 2 7万 1万 1 7万 4 2多阶段决策 4 2 2多阶段决策问题的决策方法例4 2 的决策树 本讲内容 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马尔可夫决策 由上例可看出 从而有 一般地 有