运筹学 动态规划1.ppt

* opt=optimization(最优化)，取min 或者max * （1）将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数。关键在于正确地写出基本的递推关系式和恰当的边界条件（基本方程）。 （2）动态规划方法既把当前一段和未来各段分开，又把当前效益和未来效益结合起来考虑。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案不同。 （3）由于初始状态已知，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态可依次变换得到，从而确定最优路线。 * 该例题要求板书，给出分析过程。求解过程在手写教案上。 解释为什么是最优值函数？各阶段的决策函数可以有不同的形式，函数的函数。 * opt=optimization(最优化)，取min 或者max * 1、用逆序法和顺序法求解 2、用顺序法引出例2 * 逆序法课堂讲授，顺序法可留给学员自己做，也可课堂讲授，据情况而定。 * * * * 解释为什么是最优值函数？各阶段的决策函数可以有不同的形式，函数的函数。 * 解释为什么是最优值函数？各阶段的决策函数可以有不同的形式，函数的函数。 * opt=optimization(最优化)，取min 或者max u1(A)=B1 u2(B1)=C2 u3(C2)=D1 u4(D1)=E2 u5(E1)=F1 E1 F1 G u5(E2)=F2 E2 F2 G u5(E3)=F2 E3 F2 G 7 5 9 u5(E2)=F2 u6(F2)=G 最优策略 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 3 6 8 5 3 3 8 4 2 2 2 1 3 3 3 5 2 5 6 6 4 3 最优路线为：A → B1 → C2 → D1 → E2 → F2 → G 路长＝18 P247 9.2 第四节 动态规划与静态规划的关系 1、线性规划与动态规划的共同点？ 2、线性规划与动态规划的不同点？ 3、线性规划这样的静态问题可以转化为多阶段过程的动态问题。 例1 用动态规划方法求解下面问题： 例2 用动态规划方法求解下面问题： 练习2 用动态规划方法求解下面问题： 练习1 用动态规划方法求解下面问题： 一般地说，顺序解法与逆序解法在本质上没有什么不同。 通常情况下，当初始状态给定时用逆序解法较方便，当终止状态给定时用顺序解法较方便，初始和当终止状态都给定时，两种方法都可以。 但若初始状态虽已给定，然而终点状态较多，需比较到达不同终点状态的各个路径及指标函数值，以选取总效益最佳的终点状态时，以使用顺序解法比较方便。 逆序解法与顺序解法的比较： 状态转移的方式不同： 逆序法中第k段的输入状态sk,决策为uk,输出状态sk+1 状态转移方程为：sk+1=Tk(sk,uk) 1 决策u1 s2 状态s1 效益v1(s1,u1) k 决策uk Sk+1 状态sk 效益vk(sk,uk) n 决策un Sn+1 状态sn 效益vn(sn,un) … … 顺序法中第k段的输入状态sk+1,决策为uk,输出状态sk 状态转移方程为：sk=Tk(sk+1,uk) 1 决策u1 s2 状态s1 效益v1(s2,u1) k 决策uk sk+1 状态sk 效益vk(sk+1,uk) n 决策un sn+1 状态sn 效益vn(sn+1,un) … … 状态变量的含义不同： 在逆序解法中，状态变量sk是k段的出发点；而在顺序解法中，sk+1是k段的终点。 决策过程和结果不同: 在逆序解法中，决策过程是顺序的；在顺序解法中，决策过程逆序的。 逆序法得到的结果，是每一点到终点的最短路线和距离；顺序法得到的结果是起点到每一点的最短路线和距离。 指标函数的定义不同 在逆序解法中，最优指标函数fk(sk)定义为从k段的开始状态sk出发，到过程终点的后部子过程的最优效益。f1(s1)是整体最优函数。 在顺序解法中，最优指标函数fk(sk＋1)定义为从k段终止状态sk＋1回到过程起点的前部子过程的最优效益。fn(sn＋1)是整体最优函数。 逆序解法的基本方程 动态规划的基本方程不同： 顺序解法的基本方程 其中“*” 取”+”或者“×” P212 8.5 （1） 逆序法求解 （2） 顺序法求解 动态规划的不足： 动态规划仅是求解问题的方法论，到目标为止，尚不存在统一的标准模型可用，由此，建立合适的模型往往需要丰富的想象力和灵活的技巧。 动态规划的状态变量必须满足“无后效性”，这严重制约了动态规划的普遍应用。 利用计算机求解时，存在”维数