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

1、（Decision Making Theory and Methods）决策理论与方法决策理论与方法第 2 页第 2 页决策理论与方法决策理论与方法第 3 页第 3 页学习目的学习目的了解多阶段决策、序贯决策的概念及特点；了解多阶段决策、序贯决策的概念及特点；掌握动态规划与决策树方法及其在多阶段决策、掌握动态规划与决策树方法及其在多阶段决策、序贯决策中的应用。序贯决策中的应用。决策理论与方法决策理论与方法第 4 页第 4 页本讲内容本讲内容4.1动态决策的基本原理动态决策的基本原理4.2多属性决策多属性决策决策理论与方法决策理论与方法第 5 页第 5 页4.1 4.1 多阶段决策问题的提出多阶

2、段决策问题的提出动态规划概述动态规划概述 规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。 所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶段，在每一阶

3、段分别对应着一组可供选取的决策集合，即构成过程的每个阶段都需要段，在每一阶段分别对应着一组可供选取的决策集合，即构成过程的每个阶段都需要进行一次决策。将各个阶段的决策综合起来构成一个决策序列，称为一个策略。显然进行一次决策。将各个阶段的决策综合起来构成一个决策序列，称为一个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同的策略。当过程采，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同的策略。当过程采取某个具体策略时，相应可以得到一个确定的效果，采取不同的策略，就会得到不同取某个具体策略时，相应可以得到一个确定的效果，采取不同的策略，就会得到不同的效果。多阶段的决策

4、问题，就是要在所有可能采取的策略中选取一个最优策略，以的效果。多阶段的决策问题，就是要在所有可能采取的策略中选取一个最优策略，以便得到最佳的效果。动态规划同前面介绍过的各种优化方法不同，它不是一种算法，便得到最佳的效果。动态规划同前面介绍过的各种优化方法不同，它不是一种算法，而是考察问题的一种途径。动态规划是一种求解多阶段决策问题的系统技术，可以说而是考察问题的一种途径。动态规划是一种求解多阶段决策问题的系统技术，可以说它横跨整个规划领域（线性规划和非线性规划）。当然，由于动态规划不是一种特定它横跨整个规划领域（线性规划和非线性规划）。当然，由于动态规划不是一种特定的算法，因而它不像线性规划那

5、样有一个标准的数学表达式和明确定义的一组规则，的算法，因而它不像线性规划那样有一个标准的数学表达式和明确定义的一组规则，动态规划必须对具体问题进行具体的分析处理。在多阶段决策问题中，有些问题对阶动态规划必须对具体问题进行具体的分析处理。在多阶段决策问题中，有些问题对阶段的划分具有明显的时序性，动态规划的段的划分具有明显的时序性，动态规划的“动态动态”二字也由此而得名。二字也由此而得名。决策理论与方法决策理论与方法第 6 页第 6 页 动态规划的主要创始人是美国数学家贝尔曼。动态规划的主要创始人是美国数学家贝尔曼。2020世纪世纪4040年代末年代末5050年代初，当时在兰德公司年代初，当时在兰

6、德公司从事研究工作的贝尔曼首先提出了动态规划的概念。从事研究工作的贝尔曼首先提出了动态规划的概念。19511951年贝尔曼首先提出了动态规划中解决年贝尔曼首先提出了动态规划中解决多阶段决策问题的最优化原理，并给出了许多实际问题的解法。多阶段决策问题的最优化原理，并给出了许多实际问题的解法。19571957年贝尔曼出版了他的第一年贝尔曼出版了他的第一部著作部著作动态规划动态规划，标志着运筹学这一重要分支的诞生。该著作成为当时唯一的进一步研究，标志着运筹学这一重要分支的诞生。该著作成为当时唯一的进一步研究和应用动态规划的理论源泉。和应用动态规划的理论源泉。19611961年贝尔曼出版了他的第二部著

7、作，并于年贝尔曼出版了他的第二部著作，并于19621962年同杜瑞佛思合年同杜瑞佛思合作出版了第三部著作。在贝尔曼及其助手们致力于发展和推广这一技术的同时，其他一些学者作出版了第三部著作。在贝尔曼及其助手们致力于发展和推广这一技术的同时，其他一些学者也对动态规划的发展作了巨大的贡献，其中最值得一提的是爱尔思和梅特顿。爱尔思先后于也对动态规划的发展作了巨大的贡献，其中最值得一提的是爱尔思和梅特顿。爱尔思先后于19611961年和年和19641964年出版了两部关于动态规划的著作，并于年出版了两部关于动态规划的著作，并于19641964年同尼母霍思尔、威尔德一道创建年同尼母霍思尔、威尔德一道创建了

8、处理分支、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划后来发展有了处理分支、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义的基础性观点，并且对明晰动态规划路径的数学性质作出了巨大的贡献。着重要意义的基础性观点，并且对明晰动态规划路径的数学性质作出了巨大的贡献。 动态规划从创立到现在动态规划从创立到现在5050多年来，无论在工程技术、企业管理还是在工农业生产及军事等多年来，无论在工程技术、企业管理还是在工农业生产及军事等部门都有着广泛的应用，并取得了显著的效果。在管理方面，动态规划可用于资源分配问题、部门都有着广泛的应用，并取得了显著的效果。在管

9、理方面，动态规划可用于资源分配问题、最短路径问题、库存问题、背包问题、设备更新问题、最优控制问题等等，所以动态规划是现最短路径问题、库存问题、背包问题、设备更新问题、最优控制问题等等，所以动态规划是现代管理学中进行科学决策不可缺少的工具。代管理学中进行科学决策不可缺少的工具。 动态规划的优点在于，它把一个多维决策问题转化为若干个一维最优化问题，而对一维最动态规划的优点在于，它把一个多维决策问题转化为若干个一维最优化问题，而对一维最优化问题一个一个地去解，这种方法是许多求极值方法所做不到的，它几乎优于所有现存的优优化问题一个一个地去解，这种方法是许多求极值方法所做不到的，它几乎优于所有现存的优化

10、方法。除此之外，动态规划能求出全局极大或极小，这一点也优于其他优化方法。需要指出化方法。除此之外，动态规划能求出全局极大或极小，这一点也优于其他优化方法。需要指出的是，动态规划是求解最优化问题的一种方法，是解决问题的一种途径，而不是一种算法。在的是，动态规划是求解最优化问题的一种方法，是解决问题的一种途径，而不是一种算法。在前面我们学习了用单纯形法解线性规划问题，凡是具有线性规划问题那样统一的数学模型都可前面我们学习了用单纯形法解线性规划问题，凡是具有线性规划问题那样统一的数学模型都可以用单纯形法去求解，而以用单纯形法去求解，而决策理论与方法决策理论与方法第 7 页第 7 页动态规划问题的求解

11、却没有统一的方法（类似于单纯形法）。因此在用动态规划求解最优化问动态规划问题的求解却没有统一的方法（类似于单纯形法）。因此在用动态规划求解最优化问题中，必须对具体问题具体分析，针对不同的问题，使用动态规划最优化原理和方法，建立起题中，必须对具体问题具体分析，针对不同的问题，使用动态规划最优化原理和方法，建立起与其相应的数学模型，然后再用动态规划方法去求解。根据动态规划这些特点，要求我们在学与其相应的数学模型，然后再用动态规划方法去求解。根据动态规划这些特点，要求我们在学好动态规划的基本原理和方法的同时，还应具有丰富的想象力，只有这样才能建好模型求出问好动态规划的基本原理和方法的同时，还应具有丰

12、富的想象力，只有这样才能建好模型求出问题的最优解。题的最优解。决策理论与方法决策理论与方法第 8 页第 8 页4.1 动态决策的基本原理动态决策的基本原理动态规划动态规划 动态规划（动态规划（dynamic Programming，DP）是解）是解决多阶段决策过程最优化的一种方法，其基本思路是决多阶段决策过程最优化的一种方法，其基本思路是将多阶段决策过程转化为一系列相互关联的单阶段问将多阶段决策过程转化为一系列相互关联的单阶段问题，并依次求解。题，并依次求解。 DP是离散系统最优化的一种有效工具，目前动是离散系统最优化的一种有效工具，目前动态规划已广泛用于工业、农业、工程技术、资源、环态规划已

13、广泛用于工业、农业、工程技术、资源、环境、经济、社会等领域。境、经济、社会等领域。 决策理论与方法决策理论与方法第 9 页第 9 页4.1 动态决策的基本原理动态决策的基本原理动态规划动态规划 例例4-1-1 最优线路问题。由水源地向城市的输水最优线路问题。由水源地向城市的输水线路需通过线路需通过3个控制点，每个控制点均有两个可选方个控制点，每个控制点均有两个可选方案，每段线路的输水费用如下图所示。选出一条输水案，每段线路的输水费用如下图所示。选出一条输水线路，使得总输水费用最小。线路，使得总输水费用最小。6 1 6 3 4 4 5 4 2 3 5 4 A E1 E2 F1 F2 G1 G2

14、B S1 k=1 S2 k=2 S3 k=3 S4 k=4 S5 决策理论与方法决策理论与方法第 10 页第 10 页4.1 动态决策的基本原理动态决策的基本原理动态规划动态规划 最优性原理（最优性原理（the principle of optimality）也称为）也称为Bellman原理，是原理，是R. Bellman提出的提出的DP的基本原理，的基本原理，其表述为：其表述为：“一个过程的最优策略具有这样的性质，一个过程的最优策略具有这样的性质，即无论初始状态和初始决策如何，对于由前面的决策即无论初始状态和初始决策如何，对于由前面的决策所形成的状态来说，其后各阶段的决策序列必定构成所形成的

15、状态来说，其后各阶段的决策序列必定构成相应子过程的最优策略相应子过程的最优策略”。22,r a Ef E22,r a Ef E22,r a Ef E决策理论与方法决策理论与方法第 11 页第 11 页9、 人的价值，在招收诱惑的一瞬间被决定。人的价值，在招收诱惑的一瞬间被决定。21.11.421.11.4Thursday, November 04, 202110、低头要有勇气，抬头要有低气。、低头要有勇气，抬头要有低气。16:20:1416:20:1416:2011/4/2021 4:20:14 PM11、人总是珍惜为得到。、人总是珍惜为得到。21.11.416:20:1416:20Nov-2

16、14-Nov-2112、人乱于心，不宽余请。、人乱于心，不宽余请。16:20:1416:20:1416:20Thursday, November 04, 202113、生气是拿别人做错的事来惩罚自己。、生气是拿别人做错的事来惩罚自己。21.11.421.11.416:20:1416:20:14November 4, 202114、抱最大的希望，作最大的努力。、抱最大的希望，作最大的努力。2021年年11月月4日星期四日星期四下午下午4时时20分分14秒秒16:20:1421.11.415、一个人炫耀什么，说明他内心缺少什么。、一个人炫耀什么，说明他内心缺少什么。2021年年11月月下午下午4时

17、时20分分21.11.416:20November 4, 202116、业余生活要有意义，不要越轨。、业余生活要有意义，不要越轨。2021年年11月月4日星期四日星期四16时时20分分14秒秒16:20:144 November 202117、一个人即使已登上顶峰，也仍要自强不息。、一个人即使已登上顶峰，也仍要自强不息。下午下午4时时20分分14秒秒下午下午4时时20分分16:20:1421.11.4决策理论与方法决策理论与方法第 12 页第 12 页9、 人的价值，在招收诱惑的一瞬间被决定。人的价值，在招收诱惑的一瞬间被决定。21.11.421.11.4Thursday, November

18、04, 202110、低头要有勇气，抬头要有低气。、低头要有勇气，抬头要有低气。16:20:1416:20:1416:2011/4/2021 4:20:14 PM11、人总是珍惜为得到。、人总是珍惜为得到。21.11.416:20:1416:20Nov-214-Nov-2112、人乱于心，不宽余请。、人乱于心，不宽余请。16:20:1416:20:1416:20Thursday, November 04, 202113、生气是拿别人做错的事来惩罚自己。、生气是拿别人做错的事来惩罚自己。21.11.421.11.416:20:1416:20:14November 4, 202114、抱最大的希望

19、，作最大的努力。、抱最大的希望，作最大的努力。2021年年11月月4日星期四日星期四下午下午4时时20分分14秒秒16:20:1421.11.415、一个人炫耀什么，说明他内心缺少什么。、一个人炫耀什么，说明他内心缺少什么。2021年年11月月下午下午4时时20分分21.11.416:20November 4, 202116、业余生活要有意义，不要越轨。、业余生活要有意义，不要越轨。2021年年11月月4日星期四日星期四16时时20分分14秒秒16:20:144 November 202117、一个人即使已登上顶峰，也仍要自强不息。、一个人即使已登上顶峰，也仍要自强不息。下午下午4时时20分分

20、14秒秒下午下午4时时20分分16:20:1421.11.4决策理论与方法决策理论与方法第 13 页第 13 页4.1 动态决策的基本原理动态决策的基本原理决策树决策树 决策树决策树(decision tree)就是将决策过程各个阶段就是将决策过程各个阶段之间的结构绘制成一张箭线图，每个决策或事件（即之间的结构绘制成一张箭线图，每个决策或事件（即自然状态）都可能引出两个或多个事件，导致不同的自然状态）都可能引出两个或多个事件，导致不同的结果。结果。 决策树的构成有四个要素：决策树的构成有四个要素：1)决策结点；决策结点；2)方案方案枝；枝；3)状态结点；状态结点；4)概率枝。概率枝。 22,r

21、 a Ef E22,r a Ef E22,r a Ef E决策理论与方法决策理论与方法第 14 页第 14 页4.1 动态决策的基本原理动态决策的基本原理决策树决策树 22,r a Ef E22,r a Ef E22,r a Ef E方案枝方案枝决策结 点概率枝概率枝状态结点概率枝概率枝概率枝状态结点概率枝决策理论与方法决策理论与方法第 15 页第 15 页4.1 动态决策的基本原理动态决策的基本原理决策树决策树 决策树法的决策程序如下：决策树法的决策程序如下： 1)绘制树状图，根据已知条件排列出各个方案和绘制树状图，根据已知条件排列出各个方案和每一方案的各种自然状态。每一方案的各种自然状态。

22、 2)将各状态概率及损益值标于概率枝上。将各状态概率及损益值标于概率枝上。 3)计算各方案期望值并将其标于该方案对应的状计算各方案期望值并将其标于该方案对应的状态结点上。态结点上。 4)进行剪枝，比较各个方案的期望值，并标于方进行剪枝，比较各个方案的期望值，并标于方案枝上，将期望值小的案枝上，将期望值小的(即劣等方案剪掉即劣等方案剪掉)所剩的最后所剩的最后方案为最佳方案。方案为最佳方案。 决策理论与方法决策理论与方法第 16 页第 16 页4.2 多阶段决策多阶段决策 多阶段决策有以下三个特点，多阶段决策有以下三个特点， 第一，决策者需要做出时间上有先后之别的多个第一，决策者需要做出时间上有先

23、后之别的多个决策；决策； 第二，前一次决策的选择将直接影响到后一次决第二，前一次决策的选择将直接影响到后一次决策，后一次决策的状态取决于前一次决策的结果；策，后一次决策的状态取决于前一次决策的结果； 第三，决策者关心的是多次决策的总结果，而不第三，决策者关心的是多次决策的总结果，而不是各次决策的即时后果。是各次决策的即时后果。 决策理论与方法决策理论与方法第 17 页第 17 页4.2 多阶段决策多阶段决策多阶段决策过程的基本概念多阶段决策过程的基本概念 （1）阶段）阶段 （2）状态）状态 （3）决策与策略）决策与策略 （4）指标函数与目标函数）指标函数与目标函数 （5） 多阶段决策过程多阶段

24、决策过程决策理论与方法决策理论与方法第 18 页第 18 页4.2 多阶段决策多阶段决策多阶段决策问题的决策方法多阶段决策问题的决策方法 多阶段决策问题包括确定型与随机型两大类，在多阶段决策问题包括确定型与随机型两大类，在确定型多阶段决策中，目标值都是确定值，在风险型确定型多阶段决策中，目标值都是确定值，在风险型多阶段决策中，目标值用期望值作为评价的标准。多阶段决策中，目标值用期望值作为评价的标准。 下面分别以两个例子说明其决策方法。下面分别以两个例子说明其决策方法。决策理论与方法决策理论与方法第 19 页第 19 页4.2 多阶段决策多阶段决策多阶段决策问题的决策方法多阶段决策问题的决策方法

25、例例4-2-1 某公司考虑为某新产品定某公司考虑为某新产品定价，该产品的单价拟从每件价，该产品的单价拟从每件5元元、6元、元、7元、元、8元这四个价格中元这四个价格中选取其中之一，每年年初允许变选取其中之一，每年年初允许变动价格，但幅度不能超过动价格，但幅度不能超过1元。元。该公司预计该产品畅销只有五年该公司预计该产品畅销只有五年，五年后将被淘汰，另据销售情，五年后将被淘汰，另据销售情况的预测，在价格不同的情况下况的预测，在价格不同的情况下各年的预计利润额见右表。各年的预计利润额见右表。单价第1年第2年第3年第4年第5年5元10121520256元12131620247/p>

26、元1615151414决策理论与方法决策理论与方法第 20 页第 20 页4.2 多阶段决策多阶段决策多阶段决策问题的决策方法多阶段决策问题的决策方法 例例4-2-1决策图决策图 736045845元1012152025736045846元1213162024736045847元1414161818736045848元1615151414决策理论与方法决策理论与方法第 21 页第 21 页4.2 多阶段决策多阶段决策多阶段决策问题的决策方法多阶段决策问题的决策方法 例例4-2-2 为了更正确地掌握市场情况，正式投产公司为了更正确地掌握市场情况，正式投产公司打算先生产少量产品试销，试销费需要打算

27、先生产少量产品试销，试销费需要5000元。试元。试销结果分为产品受欢迎销结果分为产品受欢迎( (H1) )，一般，一般( (H2) )和不受欢迎和不受欢迎( (H3) )三种。由于试销面不宽，试销结果的准确性有三种。由于试销面不宽，试销结果的准确性有限。其准确度（似然分布矩阵）见下表：限。其准确度（似然分布矩阵）见下表：决策理论与方法决策理论与方法第 22 页第 22 页4.2 多阶段决策多阶段决策多阶段决策问题的决策方法多阶段决策问题的决策方法 例例4-2-2的表格的表格a12（0.6）（0. 3）（0.1）4000020000-300003000030000-200001000010000

28、10000 123（0.6）（0. 3）（0.1）0.60.20.20.30.60.30.10.20.51a2a3a1H2H3H决策理论与方法决策理论与方法第 23 页第 23 页如不买此项专利，把这笔费用用在其他方面，在同样如不买此项专利，把这笔费用用在其他方面，在同样的时期可获利的时期可获利1.1万元。那么，该公司应该如何决万元。那么，该公司应该如何决（1）是否买专利？）是否买专利？（2）如果买专利，是否采取试销办法？）如果买专利，是否采取试销办法？（3）如果不试销，应大批生产，中批生产还是小批）如果不试销，应大批生产，中批生产还是小批生产？如果试销，又应该如何根据试销结果决定其行生产？如

29、果试销，又应该如何根据试销结果决定其行动？动？ 决策理论与方法决策理论与方法第 24 页第 24 页第一阶段第一阶段127买专利买专利不买专利不买专利试销试销不试销不试销3456H1H2H38910a1a2a3123（略）（略）第二阶段第二阶段第三阶段第三阶段例例4-2-2决策理论与方法决策理论与方法第 25 页第 25 页例例4-2-2 3 , 2 , 1)()/(31 ipHpHpjjjii 解：这是一个三阶段决策问题，采用解：这是一个三阶段决策问题，采用逆序归逆序归纳法进行决策分析，先要计算在一定的试销纳法进行决策分析，先要计算在一定的试销结果下的各后验概率。由全概率公式：结果下的各后验

30、概率。由全概率公式：计算得计算得： 17. 039. 044. 0321 HpHpHp决策理论与方法决策理论与方法第 26 页第 26 页例例4-2-2再再由贝叶斯公式：由贝叶斯公式：计算得计算得： )()()/(/ijjiijHppHpHp 321321294. 0076. 0046. 0353. 0462. 0136. 0353. 0462. 0818. 0/HHHHpij 决策理论与方法决策理论与方法第 27 页第 27 页例例4-2-2v当试销结果为当试销结果为 H1时：时： （万元）（万元）406. 3046. 0)3(136. 02818. 04/11 HaE （万元）（万元）77

31、. 2046. 0)2(136. 03818. 03/12 HaE 万元）万元）( 1046. 01136. 01818. 01/13 HaE故当试销结果为故当试销结果为 H1时，应选择大批生产时，应选择大批生产a1，截，截去方案去方案a2、a3，结点结点4的值为的值为3.406万元万元。-结点结点8-结点结点9-结点结点10决策理论与方法决策理论与方法第 28 页第 28 页例例4-2-2v当试销结果当试销结果为为 H2时：时： （万元）（万元）544. 2076. 0)3(462. 02462. 04/21 HaE （万元）（万元）62. 2076. 0)2(462. 03462. 03/

32、22 HaE （万元）（万元）1462. 01462. 01462. 010/23 HaE故当试销结果为故当试销结果为 H2时，应选择中批生产时，应选择中批生产a2，截，截去方案去方案a1、a3 ，结点结点5的值为的值为2.62万元万元 。决策理论与方法决策理论与方法第 29 页第 29 页例例4-2-2v当试销结果为当试销结果为 H3时：时： （万元）（万元）236. 1294. 0)3(353. 02353. 04/31 HaE （万元）（万元） 53. 1294. 0)2(353. 03353. 03/32 HaE （万元）（万元）1294. 01353. 01353. 01/33 Ha

33、E故当试销结果为故当试销结果为 H3时，也应选择中批生产时，也应选择中批生产a2，截去方案截去方案a1、a3 ，结点结点6的值为的值为1.53万元万元 。决策理论与方法决策理论与方法第 30 页第 30 页例例4-2-2v试销收益期望值：试销收益期望值： （万元）（万元）78054. 217. 053. 139. 062. 244. 0406. 3/322212321 HpHaEHpHaEHpHaEE 万元）万元）(7 . 21 . 0)3(3 . 026 . 041 aE 万元）万元）(11 . 013 . 016 . 013 aE故当不试销时，应选择大批生产故当不试销时，应选择大批生产a1

34、，截去方案，截去方案a2、a3 ，结点结点7的值为的值为2.7万元万元。不试销的收益期望值：不试销的收益期望值： 万元）万元）(5 . 21 . 0)2(3 . 036 . 032 aE-结点结点3决策理论与方法决策理论与方法第 31 页第 31 页例例4-2-2决策：（决策：（1）购买专利；）购买专利；（2）不试销；）不试销； （3）大批生产）大批生产a2。v购买专利总期望收益购买专利总期望收益2.711.7万元，大于万元，大于不买技术的收益不买技术的收益1.1万元万元截去不买专利方案，截去不买专利方案，结点结点1的值为的值为1.7万元万元 。试销收益期望值扣除试销费用试销收益期望值扣除试销

35、费用5000元后小于元后小于不试销的收益值，截去试销方案，不试销的收益值，截去试销方案，结点结点2的值的值为为2.7万元万元。决策理论与方法决策理论与方法第 32 页第 32 页第一阶段第一阶段127买专利买专利不买专利不买专利试销试销不试销不试销3456H10.44H2 0.39H3 0.178910a1a2a30.8180.1360.046（略）（略）第二阶段第二阶段第三阶段第三阶段例例4-2-24万元万元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万万决策理论与方法

36、决策理论与方法第 33 页第 33 页4.2 多阶段决策多阶段决策多阶段决策问题的决策方法多阶段决策问题的决策方法 例例4-2-的决策树的决策树1H买不试试不买10.620.3830.110.620000300003406041a2a20.136910.81830.046300003000020000340603a1000031(0.44)H520.46210.46230.076400002000030000340601a2a20.46210.46230.076300003000020000340603a1000010112(0.39)H620.35310.35330.294400002000

37、030000340601a2a20.35310.35330.294300003000020000340603a1000012133(0.17)H720.310.630.1400002000030000340601a2a20.310.630.1300003000020000340603a10000141521150002780527305500100017305决策理论与方法决策理论与方法第 34 页第 34 页本讲内容本讲内容4.3序贯决策序贯决策 序贯决策的基本概念序贯决策的基本概念 序贯决策的决策方法序贯决策的决策方法决策理论与方法决策理论与方法第 35 页第 35 页4.3 序贯决策序贯

38、决策序贯决策的基本概念序贯决策的基本概念 上面的多阶段决策，阶段数是确定的。除这种决上面的多阶段决策，阶段数是确定的。除这种决策外，还有一些决策的阶段数不是事先确定的，它依策外，还有一些决策的阶段数不是事先确定的，它依赖于执行决策过程中出现的情况。这种决策问题称为赖于执行决策过程中出现的情况。这种决策问题称为序贯决策（序贯决策（sequential decision problem）。）。 序列决策在进行决策后又产生一些新的情况，需序列决策在进行决策后又产生一些新的情况，需要进行新的决策，接着又有一些新的情况，又需要进要进行新的决策，接着又有一些新的情况，又需要进行新的决策。这样决策、情况、决

39、策行新的决策。这样决策、情况、决策，这就构成，这就构成一个序列。一个序列。 决策理论与方法决策理论与方法第 36 页第 36 页4.3 序贯决策序贯决策序贯决策的基本概念序贯决策的基本概念 序贯决策是用于随机性或不确态定性动态系统最序贯决策是用于随机性或不确态定性动态系统最优化的决策方法。它的特点是：优化的决策方法。它的特点是： 1）所研究的系统是动态的，即系统所处的状态）所研究的系统是动态的，即系统所处的状态与时间有关，可周期（或连续）地对它观察；与时间有关，可周期（或连续）地对它观察； 2）决策是序贯地进行的，即每个时刻根据所观）决策是序贯地进行的，即每个时刻根据所观察到的状态和以前状态的

40、记录，从一组可行方案中选察到的状态和以前状态的记录，从一组可行方案中选用一个最优方案（即作最优决策），使取决于状态的用一个最优方案（即作最优决策），使取决于状态的某个目标函数取最优值（极大或极小值）；某个目标函数取最优值（极大或极小值）； 3）系统下一步）系统下一步(或未来或未来)可能出现的状态是随机的可能出现的状态是随机的或不确定的。或不确定的。决策理论与方法决策理论与方法第 37 页第 37 页4.3 序贯决策序贯决策序贯决策的基本概念序贯决策的基本概念 系统在每次作出决策后下一步可能出现的状态系统在每次作出决策后下一步可能出现的状态是不能确切预知的，存在两种情况：是不能确切预知的，存在两

41、种情况： 1）系统下一步可能出现的状态的概率分布是已）系统下一步可能出现的状态的概率分布是已知的，可用客观概率的条件分布来描述。对于这类系知的，可用客观概率的条件分布来描述。对于这类系统的序贯决策研究得较完满的是状态转移律具有无后统的序贯决策研究得较完满的是状态转移律具有无后效性的系统，相应的序贯决策称为马尔可夫决策过程效性的系统，相应的序贯决策称为马尔可夫决策过程，它是将马尔可夫过程理论与决定性动态规划相结合，它是将马尔可夫过程理论与决定性动态规划相结合的产物。的产物。 2）系统下一步可能出现的状态的概率分布不知）系统下一步可能出现的状态的概率分布不知道，只能用主观概率的条件分布来描述。用于

42、这类系道，只能用主观概率的条件分布来描述。用于这类系统的序贯决策属于决策分析的内容。统的序贯决策属于决策分析的内容。22,r a Ef E22,r a Ef E22,r a Ef E决策理论与方法决策理论与方法第 38 页第 38 页4.3 序贯决策序贯决策序贯决策的决策方法序贯决策的决策方法 序贯决策的过程是：从初始状态开始，每个时序贯决策的过程是：从初始状态开始，每个时刻做出最优决策后，接着观察下一步实际出现的状态刻做出最优决策后，接着观察下一步实际出现的状态，即收集新的信息，然后再做出新的最优决策，反复，即收集新的信息，然后再做出新的最优决策，反复进行直至最后。进行直至最后。 解决序贯决

43、策问题的有效办法仍然是决策树，解解决序贯决策问题的有效办法仍然是决策树，解决序贯决策的关键是确定一个决策序列终止的原则。决序贯决策的关键是确定一个决策序列终止的原则。在下例中，这个原则就是：不管到决策的哪个阶段，在下例中，这个原则就是：不管到决策的哪个阶段，只要有一个非经抽样的后悔期望值小于进行一次抽样只要有一个非经抽样的后悔期望值小于进行一次抽样的费用，决策序列便可终止。的费用，决策序列便可终止。22,r a Ef E22,r a Ef E22,r a Ef E决策理论与方法决策理论与方法第 39 页第 39 页4.3 序贯决策序贯决策序贯决策的决策方法序贯决策的决策方法 例例4-3-1 某

44、工厂的产品每某工厂的产品每1000件装成一箱出售。件装成一箱出售。每箱中产品的次品率有每箱中产品的次品率有0.01，0.40，0.90三种可能，三种可能，其概率分别为其概率分别为0.2，0.6，0.2。现在的问题是：出厂前。现在的问题是：出厂前是否要对产品进行严格检验，将次品挑出。可以选择是否要对产品进行严格检验，将次品挑出。可以选择的行动有两个：的行动有两个： 整箱检验整箱检验(a1) ，检验费，检验费 为每箱为每箱100元；整箱不检验元；整箱不检验(a) ，但如果顾客在使用中发现次，但如果顾客在使用中发现次品，每件次品除条换为合格品外还要赔偿品，每件次品除条换为合格品外还要赔偿0.25元损

45、失元损失费。费。决策理论与方法决策理论与方法第 40 页第 40 页4.3 序贯决策序贯决策为了更好地做出决定可以先从一箱中随机抽取为了更好地做出决定可以先从一箱中随机抽取1件作件作为样本检验它，然后根据这件产品是都次品再决定为样本检验它，然后根据这件产品是都次品再决定该箱是否要检验，抽样成本为该箱是否要检验，抽样成本为4.2元。进行第一次抽元。进行第一次抽样后，除选择检验还是不检验外，还可以根据前面样后，除选择检验还是不检验外，还可以根据前面抽样的结果，考虑再进行一次抽样检验如此形成一抽样的结果，考虑再进行一次抽样检验如此形成一个决策序列。个决策序列。试进行序列决策：试进行序列决策：（1）是

46、否需要抽样？（若需要，抽样几次？）是否需要抽样？（若需要，抽样几次？）（2）在抽样或不抽样的前提下，采用何种方案进行）在抽样或不抽样的前提下，采用何种方案进行检验？检验？决策理论与方法决策理论与方法第 41 页第 41 页【例例8.2】 解：解： 1，2，3分别表示产品次品率为分别表示产品次品率为 0.01 ，0.4，0.9三种状态。对于抽样检验一件产品，三种状态。对于抽样检验一件产品，X=1和和X=0分分别表示样品为次品和合格品两个结果。结果值均用期别表示样品为次品和合格品两个结果。结果值均用期望损失值表示。望损失值表示。序列决策树图不能够一次绘制成功，而是随着决策过序列决策树图不能够一次绘

47、制成功，而是随着决策过程序列的延伸和终止依次进行。为了简化图形，行动程序列的延伸和终止依次进行。为了简化图形，行动方案方案al和和a2可能出现的状态及其对应的损失值均在图可能出现的状态及其对应的损失值均在图中略去，仅在方案枝末端标注上期望损失值。中略去，仅在方案枝末端标注上期望损失值。决策理论与方法决策理论与方法第 42 页第 42 页4532867抽样抽样继续抽样继续抽样a1a2A1A2A3A4不抽样不抽样X1=0X1=1停止抽样停止抽样9X2=0X2=1a1a2继续抽样继续抽样停止抽样停止抽样（略）（略）决策理论与方法决策理论与方法第 43 页第 43 页相应的损失矩阵为相应的损失矩阵为

48、12500005 .97)(32ijrR先进行第一次抽样的后验概率计算先进行第一次抽样的后验概率计算 3111)()|0()0(jjjpxpXP 2 . 010. 06 . 060. 02 . 099. 0 578. 0 2251001001005 . 2100)(32ijqQ该问题的费该问题的费用矩阵为：用矩阵为：决策理论与方法决策理论与方法第 44 页第 44 页3426. 0578. 02 . 099. 0)0()()|0()0|(111111 XPPXpXP 6228. 0578. 06 . 060. 0)0()()|0()0|(122112 XPPXPXP 0346. 0578. 0

49、2 . 010. 0)0()()|0()0|(133113 XPPXPXP 3111)()|1()1(jjjPXPXP 2 .090.06 .040.02 .001.0 422.0 决策理论与方法决策理论与方法第 45 页第 45 页【例例8.2】0047. 0422. 02 . 001. 0)1()()|1()1|(111111 XPPXPXP 5687. 0422. 06 . 040. 0)1()()|1()1|(122112 XPPXPXP 4265. 0422. 02 . 090. 0)1()()|1()1|(133113 XPPXPXP 第一次抽样的后验概率矩阵为第一次抽样的后验概率

50、矩阵为 4265.05687.00047.00346.06228.03426.0)|(3211 XP01 X11 X决策理论与方法决策理论与方法第 46 页第 46 页后验行动方案的期望损失值矩阵为后验行动方案的期望损失值矩阵为)|()|(11XPRXaR 4265. 05687. 00047. 00346. 06228. 03426. 012500005 .97 31.53325. 44582. 040.3321aa01 X11 X一次抽样后最满一次抽样后最满意方案分别为：意方案分别为：11)1(aXa 21)0(aXa 决策理论与方法决策理论与方法第 47 页第 47 页6.894.325

51、0.458219.52.6933.404.3250.458253.3119.525抽样抽样a1a2a1a2a1a2A1A2A3A4S1S2不抽样不抽样X1=0X1=10.5780.4220.34260.62280.03460.34260.56870.42650.00470.56870.42650.20.60.20.00470.56870.42650.20.20.697.5000012597.5000012597.50000125期望损失值(包含抽样费用)4.20 若为正品，则无须检若为正品，则无须检验整箱产品；验整箱产品； 若为次品，则整箱检若为次品，则整箱检验。验。最满意方案是，应抽取一件产

52、品作样品检验。最满意方案是，应抽取一件产品作样品检验。决策理论与方法决策理论与方法第 48 页第 48 页在在A2上上X1=1的决策点处，由于行动方案的决策点处，由于行动方案a1的期望损失的期望损失值值0.4582已小于抽样费用已小于抽样费用4.20，所以第二次抽样分支，所以第二次抽样分支S2在此处被截断，决策序列在该分支上终止。在此处被截断，决策序列在该分支上终止。而在而在Xl0的决策点处，由于行动方案的决策点处，由于行动方案al，a2。的期望。的期望损失值分别为损失值分别为33.40和和4.324，均大于抽样费用，均大于抽样费用4.20，因此，在此分支上，可进行第二次抽样，抽样结果用因此，

53、在此分支上，可进行第二次抽样，抽样结果用X2表示。表示。X20和和X2=1分别表示第二次抽样抽取一个样品为正分别表示第二次抽样抽取一个样品为正品和次品。品和次品。 决策理论与方法决策理论与方法第 49 页第 49 页第二次抽样的后验概率计算如下第二次抽样的后验概率计算如下： 311212)0|()|0()0|0(jjjXPXPXXP 0346. 010. 06228. 06 . 03426. 099. 0 7163. 0 4735. 07163. 03426. 099. 0)0|(21 XP 5217. 07163. 06228. 060. 0)0|(22 XP 0048. 07163. 00

54、346. 010. 0)0|(23 XP 决策理论与方法决策理论与方法第 50 页第 50 页 311212)0|()|1()0|1(jjjXPXPXXP 0346. 090. 06228. 040. 03426. 001. 0 2837.0 0121. 02837. 03426. 001. 0)1|(21 XP 8781. 02837. 06228. 040. 0) 1|(22 XP 1098. 02837. 00346. 090. 0) 1|(23 XP 决策理论与方法决策理论与方法第 51 页第 51 页第二次抽样的第二次抽样的后验概率矩阵为后验概率矩阵为 1098. 08781. 00

55、121. 00048. 05217. 04735. 0)|(3212 XP02 X12 X后验行动方案的期望损失值矩阵为后验行动方案的期望损失值矩阵为 )|()|(22XPRXaR 1098. 00048. 08781. 05217. 00121. 04735. 012500005 .97 73.136038. 01778. 117.4621aa02 X12 X二次抽样后最满二次抽样后最满意方案分别为：意方案分别为：12)1(aXa 22)0(aXa 决策理论与方法决策理论与方法第 52 页第 52 页由于由于X2=0在的决策点处，方案在的决策点处，方案a2的期望损失值的期望损失值0.6038

56、已小于抽样费用已小于抽样费用4.20，则序列决策的这，则序列决策的这一分支应该终止。同样，对于一分支应该终止。同样，对于X2=1决策点处，决策点处，由于方案由于方案a1的期望损失值的期望损失值1.1778也小于抽样费也小于抽样费用，则这一分枝也应终止。于是，到此决策用，则这一分枝也应终止。于是，到此决策序列全部终止。序列全部终止。 决策理论与方法决策理论与方法第 53 页第 53 页4.20a1a2s1a1a2s2X1=02533.44.3254.2019.50.578a1a2s3X2=046.170.60384.200.7163a1a2s3X1=113.734.200.28371.1778a

57、1a2s2X1=113.734.200.4220.4582A1A2A3S1S26.892.694.3250.45820.76664.3251.1778决策理论与方法决策理论与方法第 54 页第 54 页在在A3上上 X2=0的决策点处，最满意行动方案的决策点处，最满意行动方案为为a2 ，截去，截去a1和和 s3；在在 X2=1的决策点处，最满意行动方案为的决策点处，最满意行动方案为 a1，截去截去 a2和和 s3。在在 s2状态点处，期望损失值为：状态点处，期望损失值为： )(7666. 02837. 01778. 17163. 06038. 0元元 决策理论与方法决策理论与方法第 55 页第

58、 55 页在在A2上上 X1=0的决策点处，最满意行动方案为的决策点处，最满意行动方案为a2 ，截去，截去a1和和 s2；在在 X1=1的决策点处，最满意行动方案为的决策点处，最满意行动方案为 a1，截去，截去 a2和和 s2。在在 s1状态点处，期望损失值为：状态点处，期望损失值为： （元元）69. 2422. 04582. 0578. 0325. 4 在在A1决策点处，最满意方案的期望损失值为：决策点处，最满意方案的期望损失值为： )(89. 62 . 469. 2元元 所以截去所以截去a1和和a2。 决策理论与方法决策理论与方法第 56 页第 56 页综上所述，决策是：应该进行一次抽样检

59、验。综上所述，决策是：应该进行一次抽样检验。若为正品，则采取行动方案若为正品，则采取行动方案a2，即整箱产品不予检，即整箱产品不予检验；验；若为次品，则采取行动方案若为次品，则采取行动方案a1，即整箱产品予以检，即整箱产品予以检验，序列决策过程也可以用简化决策树图表示。验，序列决策过程也可以用简化决策树图表示。6.892.694.204.3250.4582s10.5780.422a1a24.3250.4621决策理论与方法决策理论与方法第 57 页第 57 页4.4马尔可夫决策马尔可夫决策研究这样的一类决策问题：研究这样的一类决策问题：采取的行动已经确定，但将这个行动付诸实践的采取的行动已经确

60、定，但将这个行动付诸实践的过程又分为几个时期。在不同的时期，系统可以过程又分为几个时期。在不同的时期，系统可以处在不同的状态，而这些状态发生的概率又可受处在不同的状态，而这些状态发生的概率又可受前面时期实际所处状态的影响。前面时期实际所处状态的影响。其中一种最简单、最基本的情形，是每一时期状其中一种最简单、最基本的情形，是每一时期状态参数的概率分布只与这一时期的前一时期实际态参数的概率分布只与这一时期的前一时期实际所处的状态有关，而与更早的状态无关，这就是所处的状态有关，而与更早的状态无关，这就是所谓的马尔可夫链。所谓的马尔可夫链。决策理论与方法决策理论与方法第 58 页第 58 页4.4马尔