文档介绍：动态规划法简介
多阶段决策过程
最短路问题
特点:若O-H-P-D是最短路,则H-P-D是从H到D的最短路。
最短路求解过程
动态规划法减少了计算量,丰富了计算结果
动态规划的基本概念
:反映问题时间或空间的自然特性k;
:表示在某阶段开始所处的自然状态或客观条件sk;
:可作出的选择dk,允许决策集合;
:决策序列(子策略);
过程:状态序列(子过程);
对状态要求具有无后效性,允许决策集合只与当时的状态有关;
:决策对下一阶段状态的影响sk+1 =Tk(sk ,dk);
收益或支出函数r=rk(sk ,dk);
fk(sk );
递推方程 fk(sk )=opt{rk(sk ,dk)+fk+1(sk+1)};
k
sk
dk
sk+1
rk
动态规划最优性原理
Bellman最优性原理:作为整个过程的最优策略具有这样的性质:无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的决策必定构成一个最优策略。
换言之,最优策略的子策略总是最优的。
同样,最优轨线的子轨线也是最优的。
用动态规划方法解优化问题
1)将问题恰当的划分阶段;
2)状态变量的选择:能描述过程的演变,满足无后效性;
3)确定决策变量及允许决策集合;
4)写出状态转移方程和阶段效益式;
5)最优值函数:是定义在全过程和所有后部子过程的函数,具有可分离性,与原问题目标相关,写出递推方程及初始条件。
例用动态规划方法求如下优化问题的最优解:
例用动态规划方法求如下优化问题的最优解:
分两步:逆推确定各状态的最优值函数及最优决策规则,顺推确定最优过程及最优策略。
动态规划的主要缺点是所谓的“维数灾”。
资源分配问题
例: 某公司拟将50万元资金投放下属A、B、C三个部门,各部门在获得资金后的收益如表所示,用动态规划方法求总收益最大的投资分配方案(投资数以10万元为单位)。
投放资金(万元)
0
10
20
30
40
50
收
益
(万元)
A
0
15
20
25
28
30
B
0
0
10
25
45
70
C
0
10
20
30
40
50