运筹学 CH5动态规划.ppt

Chapter5 动态规划(Dynamic programming) 教学目的与要求 【教学目的与要求】 了解动态规划的基本思想、基本概念和基本方程，熟悉动态规划的最优性原理和建模的一般步骤； 【教学重难点】 重点是动态规划的基本思想方法，难点是基本方程。 多阶段决策问题 动态规划（简称：DP） 是解决多阶段决策过程最优化问题的一种方法，无特定的数学模型。 多阶段决策问题 多阶段决策过程 ： 是指在一类特殊的活动过程，可将过程分解成若干相互联系的阶段，在每个阶段都要做出决策，从而使整个过程达到最优的效果，全部过程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问题。 动态规划问题 　动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。 基本概念 1、阶段： 把一个问题的过程，恰当地分为若干个相互联系的阶段，以便于按一定的次序去求解。 描述阶段的变量称为阶段变量（k)。k=1,2 ,3, …，n 阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。 基本概念 2、状态：表示每个阶段开始所处的自然状况或客观条件。通常一个阶段有若干个状态，描述过程状态的变量称为状态变量sk (表示第k阶段的状态变量 )，可以是一个数或数组。 状态变量的取值有一定的允许集合或范围，此集合称为可达状态集合S K 。 状态应满足： （1）能描述问题的变化过程。 （2）具有无后效性：当某阶段状态给定后，在这阶段以后过程的发展不受这阶段以前各状态的影响。 （3）能直接或间接地计算出来。 基本概念 在实际问题中决策变量的取值往往在某一范围之内，此范围称为允许决策集合。 常用Dk（sk）表示第k阶段从状态sk出发的允许决策集合，显然uk（sk）∈Dk（sk）。 基本概念 5、状态转移方程：是确定过程由一个状态到另一个状态的演变过程，描述了状态转移规律。 由sk转变为sk+1的状态转移方程： sk+1=T(sk,uk) 基本概念 指标函数的最优值，称为最优值函数。 在不同的问题中，指标函数的含义是不同的，它可能是距离、利润、成本、产量或资源消耗等。 动态规划模型的指标函数，应具有可分离性，并满足递推关系。 基本思想 1、动态规划思想是将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。 从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。 因此，动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件（简称基本方程）。 基本思想 2、动态规划方法是既把当前一段和未来一段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的. 最优化原理 最优化原理：作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略。”也就是说，一个最优策略的子策略也是最优的。 动态规划四大要素一个方程 动态规划的四大要素： 状态变量及其可能集合： sk ∈ S K 决策变量及其允许集合： uk（sk）∈Dk（sk） 状态转移方程：sk+1=T(sk,uk) 指标函数： vk ( sk , uk ) 一个方程：基本方程 建立动态规划模型的步骤 1、划分阶段k 按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念，以便划分阶段。 建立动态规划模型的步骤 3、确定决策变量uk(sk)及允许决策集合Dk(sk) 建立动态规划模型的步骤 5、确定阶段指标函数和最优指标函数，建立动态规划基本方程 动态规划基本方程: f k (sk ) = Opt ｛ Vk (sk ,uk ) + f k+1 (s k+1) ｝ fn+1 (s n+1 ) = 0 Op