文档介绍：1
最优化原理(贝尔曼最优化原理)
作为一个全过程的最优策略具有这样的性质:对于最优策略过程中的任意状态而言,无论其过去的状态和决策如何,余下的诸决策必构成一个最优子策略。该原理的具体解释是,若某一全过程最优策略为:
动态规划的基本原理
则对上述策略中所隐含的任一状态而言,
第k子过程上对应于该状态的最优策略必然
包含在上述全过程最优策略p1*中,即为
2
(n个阶段)。通常是根据时间或空间而划分的,或者在经由静态的数学规划模型转换为动态规划模型时,常取静态规划中变量的个数n,即k=n。
,使它既能正确地描述过程的状态,,动态规划中的状态变量必须具备以下三个特征:
3
(1)要能够正确地描述受控过程的变化特征。
(2)要满足无后效性。即如果在某个阶段状态已经给定,那么在该阶段以后,过程的发展不受前面各段状态的影响,如果所选的变量不具备无后效性,就不能作为状态变量来构造动态规划的模型。
(3)要满足可知性。即所规定的各段状态变量的值,可以直接或间接地测算得到。一般在动态规划模型中,状态变量大都选取那种可以进行累计的量。此外,在与静态规划模型的对应关系上,通常根据经验,线性与非线性规划中约束条件的个数,,常就是状态变量sk所代表的内容。
4
(sk),根据经验,一般将问题中待求的量,选作动态规划模型中的决策变量。或者在把静态规划模型(如线性与非线性规划)转换为动态规划模型时,常取前者的变量xj为后者的决策变量uk。
4. 能够正确地写出状态转移方程,至少要能正确反映状态转移规律。如果给定第k阶段状态变量sk的值,则该段的决策变量uk一经确定,第k+1段的状态变量sk+1的值也就完全确定,即有sk+1=Tk(sk ,uk)
5
,正确地构造出目标与变量的函数关系——目标函数,目标函数应满足下列性质:
(1)可分性,即对于所有k后部子过程,其目标函数仅取决于状态sk及其以后的决策 uk ,uk+1,┈,un,就是说它是定义在全过程和所有后部子过程上的数量函数。
(2)要满足递推关系,即
(3)函数对其变元Rk+1来说要严格单调。
6
例如常见的指标函数是取各段指标和的形式
其中表示第i阶段的指标,它显然是满足上述三个性质的。所以上式可以写成:
7
学****方法建议:
第一步先看问题,充分理解问题的条件、情况及求解目标。
第二步结合前面讲到的理论和解题过程,考虑如何着手进行求解该问题的工作。分析针对该动态规划问题的“四大要素、一个方程”——这一步在开始时会感到困难,但是一定要下决心去思考,在思考过程中深入理解前文讲到的概念和理论。
8
第三步动手把求解思路整理出来,或者说,把该问题作为****题独立的来做。
第四步把自己的求解放到一边,看书中的求解方法,要充分理解教材中的论述。
第五步对照自己的求解,分析成败。
9
①状态变量及其可能集合 xk Xk
②决策变量及其允许集合 uk Uk
③状态转移方程 xk+1= Tk (xk ,uk )
④阶段效应 rk ( xk , uk )
10
2. 动态规划基本方程
fn+1(xn+1) = 0 (边界条件)
fk(xk) = opt u{rk ( xk , uk ) + fk+1(xk+1) }
k = n,…,1