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