《第6章动态规划》由会员分享，可在线阅读，更多相关《第6章动态规划（48页珍藏版）》请在金锄头文库上搜索。
1、第 6 章 动态规划动态规划(Dynamic Programming)是解决多阶段决策过程最优化的一种有用的数学方法。它是由美国 学者Richard .Bellman在1951年提出的，1957年他的专著动态规划一书问世，标志着运筹学的一个 重要分支动态规划的诞生.动态规划也是一种将多变量问题转化为单变量问题的一种方法。在动态规划中， 把困难的多阶段决策问题变换成一系列相互联系的比较容易的单阶段问题一个个地求解。动态规划是考察解 决问题的一种途径 ,而不是一种特殊的算法，不像线性规划那样有统一的数学模型和算法(如单纯形法). 事实上，在运用其解决问题的过程中还需要运用其它的优化算法。因此，动态
2、规划不像其它方法局限于解决 某一类问题,它可以解决各类多阶段决策问题。动态规划在工程技术、经济管理等社会各个领域都有着广泛的应用，并且获得了显著的效果。在经济管 理方面,动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、 设备更新问题以及生产过程最优控制问题等，是经济管理中一种重要的决策技术。许多规划问题用动态规划 的方法来处理,常比线性规划或非线性规划更有效。特别是对于离散的问题，由于解析数学无法发挥作用， 动态规划便成为了一种非常有用的工具。动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态规划；也可以按照决策变 量的取值是否连续分为连
3、续性动态规划和离散性动态规划。本教材主要介绍动态规划的基本概念、理论和方 法,并通过典型的案例说明这些理论和方法的应用。6.1动态规划的基本理论6.1.1多阶段决策过程的数学描述 有这样一类活动过程,其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应的决策,以使整个过程达到最佳的活动效果。任何一个阶段(stage,即决策点)都是由输入(input)、决策(decision)、状态 转移律(transformation functio)i和输出(output)构成的，如图6-1 (a)所示.其中输入和输出也称为状 态(state)，输入称为输入状态，输出称为输出状态。由于每一阶段都有一个决
4、策，所以每一阶段都应存在一个衡量决策效益大小的指标函数，这一指标函数称为阶段指标函数，用v表示.显然v二v(S ,u )，如图6一1 (b)所示.显然，输出是输入和决策的函数,即：kkkkS 二 r(S , u )(6-1)k +1k k式(61)为状态转移方程。在由n个阶段构成的过程里，前一个阶段的输出即为后一个阶段的输入。6。1.2动态规划的基本概念动态规划的数学描述离不开它的一些基本概念与符号，因此有必要在介绍多阶段决策过程的数学描述的基础上，系统地介绍动态规划的一些基本概念。1)阶段、阶段变量阶段是过程中需要做出决策的决策点。描述阶段的变量称为阶段变量，常用k来表示。阶段的划分一般 是
5、根据时间和空间的自然特征来进行的，但要便于将问题的过程转化为多阶段决策的过程。对于具有n个阶 段的决策过程，其阶段变量k=1, 2,，n。(2) 状态、状态变量 状态表示每个阶段开始所处的自然状况或客观条件,它描述了研究问题过程的状况。状态既反映前面各阶段系列决策的结局,又是本阶段决策的一个出发点和依据；它是各阶段信息的传递点和结合点。各阶段的 状态通常用状态变量Sk来加以描述。作为状态应具有这样的性质：如果某阶段状态给定后，则该阶段以后 过程的发展不受此阶段以前各阶段状态的影响。换句话说，过程的历史只能通过当前的状态来影响未来,当 前的状态是以往历史的一个总结.这个性质称为无后效性(the
6、fu ture is in depe ndent of the pas t)。状态变量的取值有一定的允许集合或范围，此集合称为状态允许集合。(3) 决策、决策变量 过程的某一阶段、某个状态,可以做出不同的决定(选择)，决定下一阶段的状态，这种决定称为决策.描述决策的变量，称为决策变量.决策变量是状态变量的函数，常用u(sk)表示第k阶段当状态为sk时的 决策变量。在实际问题中决策变量的取值往往在某一范围之内，此范围称为允许决策集合.常用Dk(sQ表示 第k阶段从状态sk出发的允许决策集合，显然有uk(sk)GDk (sk)(4)状态转移方程多阶段决策过程可以在各个阶段进行决策，去控制过程发展的
7、多段过程；其发展是通过一系列的状态转 移来实现的；系统在某一阶段的状态转移不但与系统的当前的状态和决策有关，而且还与系统过去的历史状态和决策有关。其状态转移方程如下(一般形式)s2 = T1( S,竹)s3能用动态规划方法求解的多阶k+1,u2，,sk,uk段决策过程是一类特殊的多阶段决策过程，即具有无后效性的多阶段决策过程。(5) 策略策略是一个按顺序排列的决策组成的集合。由过程的第k阶段开始到终止状态为止的过程，称为问题的 后部子过程(或称为k子过程)。由每段的决策按顺序排列组成的决策函数序列称为k子过程策略，简称子 策略，记为pkn(sk)，即pkn (sk) = S (sk ),uk+
8、1(sk+),un (sn)当k-1时，此决策函数序列成为全过程的一个策略，简称策略，记为5叩即P(S) = 5冲,u2(s2),un(sn)在实际问题中，可供选择的策略有一定范围，此范围称为允许 策略集合，用p表示.从允许策略集合中找出达到最优效果的策略称为最优策略。(6)函数和最优值函数 用来衡量所实现过程优劣的一种数量指标，称为指标函数，它是定义在全过程或所有后部子过程上确定的数量函数.Vk, n表示之.即V = V (s ,u ,s ,u ，,s ), k = 1,2,n动态规划模型的指标函数，应具有可分离性，并满足 k,nk ,n k k k +1 k+1n+1递推关系。即V 可以表
9、示为S u V的函数.即有如下式子Vk,n (k ,k ,Sk +, Uk +, Sn+1)k,nk k Z=kSk ,Uk ,Vk +1,n(Sk+1,Uk+1,Sn+1)常见的指标函数的形式有以下两种情况：情形 1 过程和它的任一子过程的指标是它所包含的各阶段的指标和。即 V (s ,u，,s )=v C,u )k, n k kn + 1j j jj 二 k其中v (S ,u )表示第j阶段的阶段指标。j j j情形 2 过程和它的任意子过程的指标是它所包含的各阶段的指标的乘积。即 V (S ,u,.,S ) = nv (S ,u )k ,n k kn+1j=k j j j最优值函数：表示
10、从第k阶段的状态Sk开始到第n阶段的终止状态的过程，采取最优策略所得到的指标函数值。即f (S ) = opt V (S ,u , S )k k |k ,n k k n+1! k ,n，,u丿kn(7)多阶段决策过程的数学模型具有无后效性的多阶段决策过程opt V (S , u，,S ) = v (S , u )k kn +1j j jk , n ui ,u2，*,un S.t.j=1s = T (s , u )k +1k k kS G Ss kku G Ukkk = n, n 一 1,1所谓求解多阶段决策过程问题，就是要求出 最优策略，即最优决策序列最优目标函数值V1,n = V1,n (S
11、1,竹，,SnU)f (S )= opt v (S ,u , S )k kk , n k k n + 1k u , ukn62)6.1.3 动态规划的数学模型 动态规划的数学模型除包括式(62)外，还包括阶段的划分、各阶段的状态变量和决策变量的选取、 允许决策集合和状态转移律的确定等。如何获得最优指标函数呢？一个n阶段的决策过程,具有如下一些特性：(1)刚好有 n 个决策点；(2) 对阶段k而言，除了其所处的状态S和所选择的决策u外，再没有任何其它因素影响决策的最优kk性了；(3) 阶段k仅影响阶段k +1的决策，这一影响是通过S 来实现的；k+1(4) 贝尔曼(Bellmar)最优化原理：在
12、最优策略的任意一阶段上，无论过去的状态和决策如何，对过去 决策所形成的当前状态而言，余下的诸决策必须构成最优子策略。根据贝尔曼(Bellman)最优化原理，可以将式(6-2)表示为递推最优指标函数关系式(63)或式(6(63)(64)即k=n)的最优指标函数:(65)(6-6)4)：f (S )二 optv v v 二 optv + f (S )k kkk 十 1Nkk 十 1 k 十 1ukNukf (S )二 optv v v 二 optv x f (S )k kkk+1Nkk+1 k+1利用式(63和式(6-4)可表示出最后一个阶段(第n个阶段,f (S )二 optv + f (S )
13、n n nn +1 n +1unf (S )二 optv x f (S )n n nn +1 n +1un其中f (S )称为边界条件。一般情况下，第n阶段的输出状态S 已经不再影响本过程的策略，即式(6-5)n+1 n+1n +1中的边界条件f (S ) = 0，式(6-6)中的边界条件f (S ) = 1 ;但当问题第n阶段的输出状态S 对本 n+1 n+1n+1 n+1n +1过程的策略产生某种影响时，边界条件f (S )就要根据问题的具体情况取适当的值，这一情况将在后续例 n +1 n+1题中加以反映。已知边界条件f (S )，利用式(6-3)或式(6-4)即可求得最后一个阶段的最优指
14、标函数f (S )；有 n +1 n +1n n了 f (S )，继续利用式(63)或式(64)即可求得最后两个阶段的最优指标函数f (S );有了 f (S )，n nn-1 n-1n-1 n-1进一步又可以求得最后三个阶段的最优指标函数f (S );反复递推下去，最终即可求得全过程n个阶段的n-2 n-2最优指标函数f (S )，从而使问题得到解决。由于上述最优指标函数的构建是按阶段的逆序从后向前进行的, 11所以也称为动态规划的逆序算法.通过上述分析可以看出，任何一个多阶段决策过程的最优化问题，都可以用非线性规划(特殊的可以用线性规划)模型来描述;因此，从原则上讲，一般也可以用非线性规划(或线性规划)的方法来求解。那么 利用动态规划求解多阶段决策过程有什么优越性、又有什么局限性呢？动态规划的优点:(1)求解更容易、效率更高。动态规划方法是一种逐步改善法，它把原问题化成一系列结构相似的最 优化子问题,而每个子问题的变量个数比原问题少得多，约束集合也简单得多，故较易于确定最优解。(2)解的信息更丰富。非线性规划(或线性规划)的方法是对问题的整体进行一次性求解的,因此只能得到 全过程的解;而动态规划方法是将过程分解成多个阶段进行求解的,因此不仅可以得到全过程的解，同时还可 以得到所有子过程的解。动态规划的缺点：(1) 没有一个统一的
