文档介绍：多阶段决策过程
最短路问题
特点:若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)最优值函数:是定义在全过程和所有后部子过程的函数,具有可分离性,与原问题目标相关,写出递推方程及初始条件。
例用动态规划方法求如下优化问题的最优解:
计算步骤(程序框图)见P212.
分两步:逆推确定各状态的最优值函数及最优决策规则,顺推确定最优过程及最优策略。
动态规划的主要缺点是所谓的“维数灾”。
课程总结及要求
一、线性规划
:可行解、基解、基可行解和最优解
:若有最优解,则存在最优的基可行解
:列单纯形表,最优性判断,进、出基变量的选择,旋转变换
二、对偶理论
:弱对偶定理,对偶定理,互补松弛定理
、改进的单纯形法
三、非线性规划
:梯度,Hesse阵
:可行解, (严格)局部、全局最优解、值
、可行方向,(不)起作用约束
:必要条件,K—T条件
:凸集、凸函数的概念和性质,凸函数的判定,凸规划及解的性质
:性质,算法
精品课件!