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

决策理论与方法（DecisionMakingTheoryandMethods）《决策理论与方法》编写组教育部高等学校管理科学与工程类学科专业教学指导委员会推荐教材《决策理论与方法》第2页第2页第四章动态决策分析《决策理论与方法》第3页第3页学习目的了解多阶段决策、序贯决策的概念及特点；掌握动态规划与决策树方法及其在多阶段决策、序贯决策中的应用。《决策理论与方法》第4页第4页本讲内容4.1动态决策的基本原理4.2多属性决策《决策理论与方法》第5页第5页4.1多阶段决策问题的提出4.1.1动态规划概述规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶段，在每一阶段分别对应着一组可供选取的决策集合，即构成过程的每个阶段都需要进行一次决策。将各个阶段的决策综合起来构成一个决策序列，称为一个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同的策略。当过程采取某个具体策略时，相应可以得到一个确定的效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略中选取一个最优策略，以便得到最佳的效果。动态规划同前面介绍过的各种优化方法不同，它不是一种算法，而是考察问题的一种途径。动态规划是一种求解多阶段决策问题的系统技术，可以说它横跨整个规划领域（线性规划和非线性规划）。当然，由于动态规划不是一种特定的算法，因而它不像线性规划那样有一个标准的数学表达式和明确定义的一组规则，动态规划必须对具体问题进行具体的分析处理。在多阶段决策问题中，有些问题对阶段的划分具有明显的时序性，动态规划的“动态”二字也由此而得名。《决策理论与方法》第6页第6页动态规划的主要创始人是美国数学家贝尔曼。20世纪40年代末50年代初，当时在兰德公司从事研究工作的贝尔曼首先提出了动态规划的概念。1951年贝尔曼首先提出了动态规划中解决多阶段决策问题的最优化原理，并给出了许多实际问题的解法。1957年贝尔曼出版了他的第一部著作《动态规划》，标志着运筹学这一重要分支的诞生。该著作成为当时唯一的进一步研究和应用动态规划的理论源泉。1961年贝尔曼出版了他的第二部著作，并于1962年同杜瑞佛思合作出版了第三部著作。在贝尔曼及其助手们致力于发展和推广这一技术的同时，其他一些学者也对动态规划的发展作了巨大的贡献，其中最值得一提的是爱尔思和梅特顿。爱尔思先后于1961年和1964年出版了两部关于动态规划的著作，并于1964年同尼母霍思尔、威尔德一道创建了处理分支、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义的基础性观点，并且对明晰动态规划路径的数学性质作出了巨大的贡献。动态规划从创立到现在50多年来，无论在工程技术、企业管理还是在工农业生产及军事等部门都有着广泛的应用，并取得了显著的效果。在管理方面，动态规划可用于资源分配问题、最短路径问题、库存问题、背包问题、设备更新问题、最优控制问题等等，所以动态规划是现代管理学中进行科学决策不可缺少的工具。动态规划的优点在于，它把一个多维决策问题转化为若干个一维最优化问题，而对一维最优化问题一个一个地去解，这种方法是许多求极值方法所做不到的，它几乎优于所有现存的优化方法。除此之外，动态规划能求出全局极大或极小，这一点也优于其他优化方法。需要指出的是，动态规划是求解最优化问题的一种方法，是解决问题的一种途径，而不是一种算法。在前面我们学习了用单纯形法解线性规划问题，凡是具有线性规划问题那样统一的数学模型都可以用单纯形法去求解，而《决策理论与方法》第7页第7页动态规划问题的求解却没有统一的方法（类似于单纯形法）。因此在用动态规划求解最优化问题中，必须对具体问题具体分析，针对不同的问题，使用动态规划最优化原理和方法，建立起与其相应的数学模型，然后再用动态规划方法去求解。根据动态规划这些特点，要求我们在学好动态规划的基本原理和方法的同时，还应具有丰富的想象力，只有这样才能建好模型求出问题的最优解。《决策理论与方法》第8页第8页4.1动态决策的基本原理4.1.1动态规划动态规划（dynamicProgramming，DP）是解决多阶段决策过程最优化的一种方法，其基本思路是将多阶段决策过程转化为一系列相互关联的单阶段问题，并依次求解。DP是离散系统最优化的一种有效工具，目前动态规划已广泛用于工业、农业、工程技术、资源、环境、经济、社会等领域。《决策理论与方法》第9页第9页4.1动态决策的基本原理4.1.1动态规划例4-1-1最优线路问题。由水源地向城市的输水线路需通过3个控制点，每个控制点均有两个可选方案，每段线路的输水费用如下图所示。选出一条输水线路，使得总输水费用最小。616344542354AE1E2F1F2G1G2BS1k=1S2k=2S3k=3S4k=4S5《决策理论与方法》第10页第10页4.1动态决策的基本原理4.1.1动态规划最优性原理（theprincipleofoptimality）也称为Bellman原理，是R.Bellman提出的DP的基本原理，其表述为：“一个过程的最优策略具有这样的性质，即无论初始状态和初始决策如何，对于由前面的决策所形成的状态来说，其后各阶段的决策序列必定构成相应子过程的最优策略”。22,raEfE22,raEfE22,raEfE《决策理论与方法》第11页第11页4.1动态决策的基本原理4.1.2决策树决策树(decisiontree)就是将决策过程各个阶段之间的结构绘制成一张箭线图，每个决策或事件（即自然状态）都可能引出两个或多个事件，导致不同的结果。决策树的构成有四个要素：1)决策结点；2)方案枝；3)状态结点；4)概率枝。22,raEfE22,raEfE22,raEfE《决策理论与方法》第12页第12页4.1动态决策的基本原理4.1.2决策树22,raEfE22,raEfE22,raEfE方案枝方案枝决策结点概率枝概率枝状态结点概率枝概率枝概率枝状态结点概率枝《决策理论与方法》第13页第13页4.1动态决策的基本原理4.1.2决策树决策树法的决策程序如下：1)绘制树状图，根据已知条件排列出各个方案和每一方案的各种自然状态。2)将各状态概率及损益值标于概率枝上。3)计算各方案期望值并将其标于该方案对应的状态结点上。4)进行剪枝，比较各个方案的期望值，并标于方案枝上，将期望值小的(即劣等方案剪掉)所剩的最后方案为最佳方案。《决策理论与方法》第14页第14页4.2多阶段决策多阶段决策有以下三个特点，第一，决策者需要做出时间上有先后之别的多个决策；第二，前一次决策的选择将直接影响到后一次决策，后一次决策的状态取决于前一次决策的结果；第三，决策者关心的是多次决策的总结果，而不是各次决策的即时后果。《决策理论与方法》第15页第15页4.2多阶段决策4.2.1多阶段决策过程的基本概念（1）阶段（2）状态（3）决策与策略（4）指标函数与目标函数（5）多阶段决策过程《决策理论与方法》第16页第16页4.2多阶段决策4.2.2多阶段决策问题的决策方法多阶段决策问题包括确定型与随机型两大类，在确定型多阶段决策中，目标值都是确定值，在风险型多阶段决策中，目标值用期望值作为评价的标准。下面分别以两个例子说明其决策方法。《决策理论与方法》第17页第17页4.2多阶段决策4.2.2多阶段决策问题的决策方法例4-2-1某公司考虑为某新产品定价，该产品的单价拟从每件5元、6元、7元、8元这四个价格中选取其中之一，每年年初允许变动价格，但幅度不能超过1元。该公司预计该产品畅销只有五年，五年后将被淘汰，另据销售情况的预测，在价格不同的情况下各年的预计利润额见右表。单价第1年第2年第3年第4年第5年5元10121520256元12131620247元14141618188元1615151414《决策理论与方法》第18页第18页4.2多阶段决策4.2.2多阶段决策问题的决策方法例4-2-1决策图736045845元1012152025736045846元1213162024736045847元1414161818736045848元1615151414《决策理论与方法》第19页第19页4.2多阶段决策4.2.2多阶段决策问题的决策方法例4-2-2为了更正确地掌握市场情况，正式投产公司打算先生产少量产品试销，试销费需要5000元。试销结果分为产品受欢迎(H1)，一般(H2)和不受欢迎(H3)三种。由于试销面不宽，试销结果的准确性有限。其准确度（似然分布矩阵）见下表：θP(θ)P(H1︱θ)P(H2︱θ)P(H3︱θ)θ10.60.60.30.1θ20.30.20.60.2θ30.10.20.30.5《决策理论与方法》第20页第20页4.2多阶段决策4.2.2多阶段决策问题的决策方法例4-2-2的表格a12（0.6）（0.3）（0.1）4000020000-300003000030000-20000100001000010000123（0.6）（0.3）（0.1）0.60.20.20.30.60.30.10.20.51a2a3a1H2H3H《决策理论与方法》第21页第21页如不买此项专利，把这笔费用用在其他方面，在同样的时期可获利1.1万元。那么，该公司应该如何决（1）是否买专利？（2）如果买专利，是否采取试销办法？（3）如果不试销，应大批生产，中批生产还是小批生产？如果试销，又应该如何根据试销结果决定其行动？《决策理论与方法》第22页第22页第一阶段127试销不试销3456H1H2H38910a1a2a3θ1θ2θ3（略）第二阶段第三阶段例4-2-2《决策理论与方法》第23页第23页例4-2-23,2,1)()/(31ipHpHpjjjii　　解：这是一个三阶段决策问题，采用逆序归纳法进行决策分析，先要计算在一定的试销结果下的各后验概率。由全概率公式：计算得：17.039.044.0321HpHpHp《决策理论与方法》第24页第24页例4-2-2再由贝叶斯公式：计算得：)()()/(/ijjiijHppHpHp321321294.0076.0046.0353.0462.0136.0353.0462.0818.0/HHHHpij　　　　　　　　　　　　　《决策理论与方法》第25页第25页例4-2-2当试销结果为H1时：（万元）　　　　　　406.3046.0)3(136.02818.04/11HaE（万元）　　　　　　77.2046.0)2(136.03818.03/12HaE万元）　　　　　　(1046.01136.01818.01/13HaE故当试销结果为H1时，应选择大批生产a1，截去方案a2、a3，结点4的值为3.406万元。----结点8----结点9----结点10《决策理论与方法》第26页第26页例4-2-2当试销结果为H2时：（万元）　　　　　　544.2076.0)3(462.02462.04/21HaE（万元）　　　　　　62.2076.0)2(462.03462.03/22HaE（万元）　　　　　　1462.01462.01462.010/23HaE故当试销结果为H2时，应选择中批生产a2，截去方案a1、a3，结点5的值为2.62万元。《决策理论与方法》第27页第27页例4-2-2当试销结果为H3时：（万元）　　　　　　236.1294.0)3(353.02353.04/31HaE（万元）