文档介绍：2017-4-14 1第七章第七章动态规划动态规划第一节多阶段决策过程的最优化第二节动态规划的基本概念和基本原理第三节动态规划模型的建立与求解第四节动态规划在经济管理中的应用第五节马氏决策规划简介主要内容: 2017-4-14 2 引引言言动态规划是解决多阶段决策过程最优化问题的一种方法,该方法是美国数学家贝尔曼等人在 20 世纪 50 年代初提出来的。它是现代企业管理中的一种重要决策方法,可以用于解决最优路径问题、资源分配问题、生产计划与库存、投资、装载、排序等问题及生产过程的最优控制等。动态规划模型的分类: 1 、离散确定型; 2 、离散随机型; 3 、连续确定型; 4 、连续随机型。其中离散确定型是动态规划最基本的模型,本章主要针对这种类型的问题,介绍动态规划的基本思想、原理和方法。 2017-4-14 3 § § 7-1 7-1 多阶段决策过程的最优化多阶段决策过程,是指一类特殊的活动过程,它们可以按时间顺序分解成若干相互联系的阶段,称为“时段”,在每个时段都要做出决策,全部过程的决策是一个决策序列,所以多阶段决策问题属序贯决策问题。多阶段决策过程最优化的目标是多阶段决策过程最优化的目标是要达到整个活动的总体效果最优要达到整个活动的总体效果最优。动态规划方法与“时间”关系很密切,随着时间过程的发展而决定各时段的决策,产生一个决策序列,这就是“动态”的含义。例1生产与存储问题例2投资决策问题某公司现有资金 Q 万元,在今后 5 年内考虑给 A,B,C,D四个项目投资,这些项目投资的回收期限、回报率均不同,问该公司应如何确定这些项目的投资额,使到第五年末拥有资金的本利总额最大。显然,这是一个 5阶段决策问题例3设备更新问题第七章动态规划 2017-4-14 4 § §7-2 7-2 动态规划的基本概念和基本原理动态规划的基本概念和基本原理一、动态规划的基本概念一、动态规划的基本概念使用动态规划方法解决多阶段决策问题, 使用动态规划方法解决多阶段决策问题, 首先要将实际问题写成动态规划模型,要用到首先要将实际问题写成动态规划模型,要用到以下概念: 以下概念: ( (1 1) )阶段阶段; ;( (2 2) )状态状态; ; ( (3 3) )决策决策; ;( (4 4) )策略策略; ; ( (5 5) )状态转移状态转移; ; ( (6 6) )指标函数指标函数 2017-4-14 5 ( (1 1)阶段)阶段为了便于求解和表示决策及过程的发展顺序,而把所给问题按时间或空间特征恰当地划分为若干个相互联系又有区别的子问题,称之为多段决策问题的阶段阶段。一个阶段,就是需要作出一个决策的子问题。用以描述阶段的变量叫作阶段变量阶段变量,一般以。 2017-4-14 6 ( (2 2)状态)状态用以描述事物( 或系统) 在某特定的时间与空间域中所处位置及运动特征的量,称为状态状态。反映状态变化的量叫做状态变量状态变量。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。按照过程进行的先后,每个阶段的状态可分为初始状态和终止状态,或称输入状态和输出状态, 阶段 k 的初始状态记作 s k ,终止状态记为 s k+1。但为了清楚起见,通常定义阶段的状态即指其初始状态。各阶段开始时的客观条件叫各阶段开始时的客观条件叫状态状态。一般状态变量的取值有一定的范围或允许集合,称为可能状态集,或可达状态集。可能状态集实际上是关于状态的约束条件。通常可能状态集用相应阶段状态 s k 的大写字母 S k表示, s k?S k ,可能状态集可以是一离散取值的集合,也可以为一连续的取值区间,视具体问题而定。 2017-4-14 7 ( (3 3)决策)决策决策决策的实质是关于状态的选择,是决策者从给定阶段状态出发对下一阶段状态作出的选择。用以描述决策变化的量称之决策变量决策变量。决策变量的值可以用数,向量、其它量,也可以是状态变量的函数,记为 u k=u k(s k) ,表示在阶段 k 状态 s k 时的决策变量。决策变量的取值往往也有一定的允许范围,称之允许决策集合允许决策集合。决策变量 u k(s k) 的允许决策集用 D k(s k) 表示, u k(s k)∈D k(s k) ,允许决策集合实际是决策的约束条件。 2017-4-14 8( (4 4)策略)策略策略(Policy) 部子策略之分,全过程策略是指由依次进行的 n 个阶段决策构成的决策序列,简称策略策略,表示为 p 1,n{u 1,u 2,…,u n} 。从 k 阶段到第 n 阶段,依次进行的阶段决策构成的决策序列称为 k 部子策略, 表示为 p k,