动态规划的基本概念
基本概念
设我们研究某一个过程,这个过程可以分解为若干个互相联系的阶段。
每一阶段都有其初始状态和结束状态,其结束状态即为下一阶段的初始.状态。
第一阶段的初始状态就是整个过程的初始状态,最后一阶段的结束状态就是整个过程的结束状态。
在过程的每一个阶段都需要作出决策,而每一阶段的结束状态依赖于其初始状态和该阶段的决策。
动态规划问题就是要找出某种决策方法, 使过程达到某种最优效果。
这种把问题看作前后关联的多阶段过程称为多阶段决策过程, 可用图9.1表示。
下面介绍动态规划的术语和基本概念。
(l)阶段 把所研究的过程恰当地分为若干个互相联系的相对独立过程。
(2)状态变量 用来描述系统所处状态的变量称为状态变量。
通常用s k 表示第k 阶段的初始状态，则s k +1表示第k 阶段结束时(也就是第k+l 阶段开始时)过程的状态。
通常要求状态变量具有无后效性, 即过程在第k 阶段以后的变化只与该阶段结束时的状态有关, 而与系统如何到达此状态的过程无关。
(3)决策变量的状态转移方程。
系统在第k 阶段中的变化过程, 通常我们并不关心，但我们希望知道该阶段的初始状态与结束状态之间的关系。
我们用以影响该系统的手段，也用一个变量x k 表示，称为决策变量， 则第k 阶段结束时的状态s k +1是决策变量x k 和初始状态s k 的函数, 即
s k +1=T (s k ,x k ) (9-1)
(9-1)称为状态转移方程。
(4)权函数 反映第k 阶段决策变量x k 的效益函数W k (s k ,x k ) 称为权函数。
(5)指标函数 判断整个过程优劣的数量指标称为指标函数。
当第k 阶段初始状态为s k 时,设我们在此阶段及以后各阶段均采取最优策略时,所获得的效益为f k (s k ), 那么有 ))}(),,(({)(11++∈=k k k k k k D x k k s f x s W F opt s f k
k (9-2) 其中opt 表示最优,按具体问题可取为max 或min , D k 是决策变量x k 的定义域;F k 是某一个函数; s k +1=T (s k ,x k ).
图9.1
例如,描述一质点在已知力场中的运动,若我们选取该质点的坐标(x,y,z)作为状态变量, 则不能满足无后效性要求, 因质点的运动不仅与它当前的坐标有关,还与它如何来到此点的过程有关。
若我们选取该质点的位置向量r 与速度向量v 作为状态变量,那么就可以满足无后效性的要求, 因为质点在已知力场中的运动由它的初始位置和初始速度完全决定, 而与质点以前的历史无关。
动态规划的最优化原理
(9-2)反映动态规划的最优化原理：
最优策略的每一部分子策略,都是相应阶段的最优策略。
要运用动态规划解决某个问题,关键在于把该过程分解为若干阶段、这些阶段的状态变量和决策变量以及指标函数应该满足最优化原理。
利用状态转移方程(9-1)和递推方程(9-2)来解动态规划的方法称为逆序解法。
对某些问题,也可采用顺序解法,请参阅有关书籍。
在许多问题中,有
)(),())(),,((1111+++++=k k k k k k k k k k k s f x s W s f x s W F
这时递推方程(9-2)可以写成
)}(),({)(11++∈+=k k k k k D x k k s f x s W opt s f k
k (9-3)
简单例子
求解如下问题：
⎩⎨⎧=≥≤+++-=3
,2,1 ,0923..24max 321232221i x x x x t s x x x f i
解 我们把该问题分为三个阶段:
阶段1:初始状态s 1=9, 决策变量x 1;
阶段2:初始状态s 2=s 1-3x 1, 决策变量x 2;
阶段3:初始状态s 3=s 2-2x 3, 决策变量x 3.
则有330s x ≤≤，第三阶段的目标函数为232x ，有
)( ,2}2max{)(33232333s x s x s f === 现在有2
022s x ≤≤，目标函数为23222x x +-，有 )0( ,2})2(2max{ }
2max{)}(max{)(222222222322332222==-+-=+-=+-=x s x s x s x s f x s f 最后有3011s x ≤
≤，目标函数为23222124x x x +-，故有
)0( ,2}9
4,2max{ }
)3(24max{ }
24max{)}(4max{)(1212121211212221222111===-+=+=+=x s s s x s x s x s f x s f
因为s 1=9, x 1=x 2=0, 故得s 3=9, 从而x 3=9, 此时max f =f 1(9)=162. 即此题的最优解为x =(0,0,9), 最优值为162.
请你探索
如何用动态规划的方法证明以下不等式：
n n n x x x x x x n 1)()(12121 ≥+++ 其中各x i >0.。