文档介绍：动态规划
A
F1
F2
F3
G1
G2
G3
H1
H2
B
A
F1
F2
F3
G1
G2
G3
H1
H2
B
380
280
400
290
380
350
230
210
320
350
350
400
280
410
300
250
200
300
200
350
380
280
510
670
830
860
1060
810
660
不仅求出了从A到B的最优路线,而且求出了任一点到A
的最优路线!
最优路线的特性
在一个多阶段的网络图中,最优路线有如下特性: 若从A到B最优路线TAB经过某个结点X,则从X出发到B的最优路线TXB必是TAB的一部分!
求解的方法: 先求出从X到B的最优路线,逐步递推(X变化),求得从A到B的最优路线!
最优策略的特性
在一个多阶段的决策问题中,最优策略有如下特性: 一个最优策略PAB经过某个状态X,则从X出发到B的最优策略PXB必是PAB的一部分。
求最优策略的方法: 先求出从X出发到B的最优路线,逐步递推(X变化),求得从A到B的最优策略。
动态规划的特点
动态规划用来求解多阶段决策问题;
求解过程中使用递推的方法;
每一阶段的决策对下一阶段产生影响;
每一阶段中的最优决策未必是整个过程中的最优决策。
必须搞清各阶段决策之间的关系;
需建立数学模型,以求出最优决策。
多阶段决策问题的例子
某种装卸机械可在高低两种负荷下运行,每台装卸机
械在高负荷下年装卸量为8万,,在低
负荷下年装卸量为5万,。在第一年初
公司共有机械1000台。
试作一决策,使公司5年的装卸量达到最大?
这是一个多阶段问题,今年的决策将影响到明年投入运行
的机械数,从而影响明年的决策。
需建立数学模型,建立决策变量关系之间的表达式
动态规划模型的建立
将问题按时间或按空间划分成若干个阶段;每个阶段可进行决策。
在机器负荷分配问题中,以时间(年度)为阶段;在最优路线问题中,以网络结点为阶段。
在动态规划中,一般以下标k来标识阶段。
动态规划模型的建立
决策、决策变量和策略 决策:在过程的每一阶段,根据当前状态,以决定过程到下一阶段的状态。
决策变量:用uk表示,描述决策的变量;
策略:一系列的决策称为策略。策略用PK表示
动态规划模型的建立
状态、状态变量和状态集合: 状态:指过程过去、现在和将来的状况; 状态是对环境的客观描述。状态是对决策有影响的客观环境。
状态变量:描述状态的变量。 用SK表示状态变量。
状态集合:状态变量取值的全体。
注意:状态变量有时可能不止一个。
动态规划模型的建立
状态变量的选择必须具有无后效性:
过程的发展只依赖于当前的状态,它与过去的历史无关。
当前的状态就是未来过程的初始状态。
第k+1阶段的状态Sk+1只与第k阶段的决策uk第k阶段的状态Sk有关,与其它阶段的变量无关。
动态规划模型的建立
状态转移方程: 需要给出状态变量Sk+1与Sk和uk的关系。
允许决策集合Dk: 需要给出决策变量uk的约束条件。它可用集合形式表示。 Dk(Sk)={uk|uk的约束条件}