文档介绍：数学建模方法及其应用
韩中庚 编著
数 学 建 模 教 学 片
第十三章 动态规划方法
设计制作：
主要内容
第十三章 动态规划方法
*
*
动态规划的基本问题；
动态规划的基本概念与条件；
动态规划的基 指标函数（回收函数）
*
*
常见的两种指标函数
*
*
常见的两种指标函数
*
*
(7) 最优值函数
*
*
2 . 动态规划的基本条件
二. 动态规划的基本概念与条件
*无后效性：如果某阶段状态已给定，则以后过程的发展不受以前各阶段状态的影响，也就是说当前状态就是未来过程的初始状态；
**可知性：规定的各阶段状态变量的值，由直接或间接都是可以知道的。
*
*
2 . 动态规划的基本条件
1) 它是过程各阶段状态变量和决策变量的函数；
1) 加法型
逆序法:
三. 动态规划的基本方程
30
其中：fk(sk)表示第k阶段初始状态为sk 时，k后部子过程的最优值函数 。
状态转移方程：
（边界条件）k=1,2,…,n
由此得加法型逆序算法的递归方程如下：
31
2) 乘法型
32
状态转移方程：
（边界条件）k=1,2,…,n
动态规划方法的关键在于利用最优化原理给出最优值函数的递推关系式和边界条件，为此，必须先将问题的过程划分为几个相互联系的阶段，适当选取状态变量、决策变量、状态转移方程及最优值函数。从而把一个大问题化成一系列同类型的子问题，然后逐个求解。
由此得乘法型逆序算法的递归方程如下：
33
动态规划建模有以下过程：
①将问题划分成恰当的阶段；
②正确选择状态变量，使它能描述过程的演变。
③确定决策变量和决策允许集合。
④确定状态转移方程。
⑤明确阶段指标、过程指标和最优值函数。
三、动态规划的建模
34
k=n时，动态规划基本方程是
边界条件：
即 ：
逆序地求出最优目标函数值集合和最优决策集合。
仅就逆序法说明求解步骤：
四、动态规划问题求解的一般步骤
35
k = n－1时，动态规划的基本方程是
因所有的fn(sn)都已经求出，因此可以根据sn=Tn-1 (sn-1,un-1)就n-1阶段每个可能状态sn-1 ，求出最优决策及相应的最优目标函数值fn-1(sn-1) 。
k = n－2时，动态规划的基本方程是
由于fn-1(sn-1)都已经求出，因此可以根据sn-1=Tn-2 (sn-2 ,un-2)就n-2阶段每个可能状态sn-2 ，求出最优决策及相应的最优目标函数值fn-2(sn-2) 。
36
k=1时，动态规划的基本方程是
由于所有的 f2(s2) 都已经求出，因此可以根据 s2=T1(s1,u1)，就第1阶段每个可能状态s1 ,求最优决策及相应的最优目标函数值 f1(s1) .
依次下去 ………….
最后，顺序地求出最优目标值、最优策略和最优路径。
37
*
*
三. 动态规划的基本方程
1 . 动态规划的逆序解法
*
*
1 . 动态规划的逆序解法
*
*
三. 动态规划的基本方程
2 . 动态规划的顺序解法
*
*
2 . 动态规划的顺序解法
*
*
四. 动态规划的求解方法
1 . 动态规划的逆序解法
*
*
1 . 动态规划的逆序解法
*
*
1 . 动态规划的逆序解法
解: 按问题的变量个数划分阶段,把它看作一个三阶段决策问题。令变量x1，x2，x3为决策变量。
例2：用逆推解法求解下面问题:
则有：x3=s3, 0≤x2≤s2, 0≤x1≤s1=c
令状态变量为： s3= x3, s2 = x2+x3, s1=c = x1+x2+x3
即 s3= x3, s2 = s3+ x2, s1=c = s2+ x1。
于是状态转移方程为： s3=s2-x2, s2 =s1-x1
45
各阶段指标按乘积方式结合。即令:
由逆推解法：
即最优解 x3*=s3 。
令最优值函数f k(sk)表示第k阶段从初始状态sk出发，从第k阶段到第3阶段所得到的效益最大值。
46
得 和 x2=0(舍去)
故 为极大值点，也就是最大值点。
整理课件
47
同上对h1(s1, x1)求导并令导数等于0可得：
由于s1=c，
整理课件
48
由s2 =s1－x1＊，
由s3 =s2－x2＊，
因此最优解为：
最大值为：
49
逆推实例
例 1 分配投资问题
某公司有资金 10 万元，若投资于项目 k （k =