运筹学 operations research 第二章动态规划 问题:动态规划的最优解和最优值各是什么? 最优解:最优策略Bn 最优值:最优指标f1
http://www.tju.edu.cn 第二章 动态规划 问题：动态规划的最优解和最优值各是什么？ ——最优解：最优策略 P1 n ， 最优值：最优指标 f1
运筹学 operations research 第二章动态规划 2、基本方程 1)基本原理 定理:P=(x1…xn)是最优策略对任何k(1<k<n) 和允许状态,有f1=qpt1k+f1 pik 推论( bellman最优性原理):若P是最优策略, 则对任何k(1<k<n),子策略P对于以S;为起 点的k至n子过程来说必为最优策略
http://www.tju.edu.cn 第二章 动态规划 （1）基本原理 和允许状态 有 { }。 定理： 是最优策略 对任何 （ 11 1 1 1 1 1 , ),,( )1 + ∗∗ ∗ += = ⇔ << kk p n n fvoptfs xxP nkk k " 点的 至 子过程来说必为最优策 略。 则对任何 （ ），子策略 对于以 为起 推论（ 最优性原理）：若 是最优策略， nk nkk P s Bellman P kn k n ∗ ∗ ∗ 1 << 1 2、基本方程
运筹学 operations research 第二章动态规划 以最短路为例说明 (2)基本方程 根据最优性原理,可建立从后向前逆推求 解的递推公式—基本方程 f, =opt f +fi fn1=0,k=n2…l
http://www.tju.edu.cn 第二章 动态规划 （2）基本方程 根据最优性原理，可建立从后向前逆推求 解的递推公式——基本方程： { } ⎪⎩ ⎪⎨⎧ == = + + + ,1, 0, 1 1 nkf " fvoptf n k k x k k 以最短路为例说明
运筹学 operations research 第二章动态规划 ◆动态规划求解的一般步骤: ◆确定过程的分段,构造状态变量; ◆设置决策变量,写出状态转移; ◆列出阶段指标和指标函数: ◆写出基本方程,由此逐段递推求解
http://www.tju.edu.cn 第二章 动态规划 动态规划求解的一般步骤： 确定过程的分段，构造状态变量； 设置决策变量，写出状态转移； 列出阶段指标和指标函数； 写出基本方程，由此逐段递推求解
运筹学 operations research 第二章动态规划 中三、求解方法 1.离散型(用表格方式求解) 例1用动态规划方法求解前面的最短路问题 B 14 D A 0 E 12 B
http://www.tju.edu.cn 第二章 动态规划 三、求解方法 1.离散型（用表格方式求解） 例1 用动态规划方法求解前面的最短路问题 A E B1 B2 B3 C1 C2 C3 D1 D2 2 9 5 3 12 5 2 1 5 6 4 6 8 10 13 12 11 14 10