动规划 Dynamie Programming(DP 动态规划 Dynamic Programming 动态规划的基本概念和基本原理 7、指标函数( objective function) 衡量在选定某策略时,其优劣的数量指标。定义在整个过程(1 到n阶段)上的指标函数记为:V1,n(S1,U1,s2,…,sn,Un), 定义在后部子过程(k到n阶段)上的指标函数记为:Vk,n(sk ,…,sn,Un),或简记为:V Sk, pK 常见指标函数的形式: VK. n(Sk, pK, n)=>Vi(si, ui) (sk,pk,n)=∏v;(s,u1)
11 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 动态规划的基本概念和基本原理 7、指标函数（objective function） 衡量在选定某策略时，其优劣的数量指标。定义在整个过程（1 到n阶段）上的指标函数记为：V1，n（s1，u1，s2，…，sn，un）， 定义在后部子过程（k到n阶段）上的指标函数记为： Vk，n（sk， uk，…，sn，un），或简记为：Vk，n（sk， pk，n ）。 常见指标函数的形式： Vk，n（sk， pk，n ）= ∑ vi（si ，ui） Vk，n（sk， pk，n ）= ∏ vi（si ，ui）
动规划 Dynamie Programming(DP 动态规划 Dynamic Programming 动态规划的基本概念和基本原理 8、最优指标函数( optimal value function) 从第k阶段状态sk出发,采用最优策略p*k,n到终止时的 后部子过程指标函数值。 fK( sk Opt I VK, n(Sk, pk. n)I psn∈P,n(sk) 12
12 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 动态规划的基本概念和基本原理 8、最优指标函数（optimal value function） 从第k阶段状态 sk 出发，采用最优策略 p*k，n 到终止时的 后部子过程指标函数值。 fk（ sk ）= Opt [ Vk，n（sk， pk，n ）] pk，n Pk，n（ sk ）
动规划 Dynamie Programming(DP 动态规划 Dynamic Programming 动态规划的基本思想 基本思想总结:例—最短路线问题 划分阶段 2、求解从边界条件开始,逆向逐段递推。 3、每段的最优是从全局考虑的,并非仅考虑本阶段。 Bellman最优化原理: 个过程的最优策略具有这样的性质,即无论开始的状态及 初始的决策如何,对先前决策所形成的状态而言,其以后所有的决 策必构成最优决策——后部子过程最优 13
13 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 动态规划的基本思想 基本思想总结：例——最短路线问题 1、划分阶段。 2、求解从边界条件开始，逆向逐段递推。 3、每段的最优是从全局考虑的，并非仅考虑本阶段。 Bellman 最优化原理： “一个过程的最优策略具有这样的性质，即无论开始的状态及 初始的决策如何，对先前决策所形成的状态而言，其以后所有的决 策必构成最优决策——后部子过程最优
动规划 Dynamie Programming(DP 动态规划 Dynamic Programming 动态规划的基本思想 动态规划发展的早期,从简单逻辑分析出发给出了所谓“最优 性原理”,然后在最优策略存在的前提下导出了基本动态方程,再 由此方程求解最优策略。后来,在其应用过程中发现,最优性原理 并非对任何多阶段决策过程普遍成立,它与基本动态方程并不是无 条件等价的,二者之间也不存在任何确定的蕴含关系,基本方程在 动态规划中起着更为本质的作用。 fK(sk)= opt [vk(Sk, uk)+k+1(Sk+) 1,ke=n,n 2,1 u k D (s k fn+1(sn+1)=q(sn+1) 边界条件(g为已知函数) 14
14 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 动态规划的基本思想 动态规划发展的早期，从简单逻辑分析出发给出了所谓“最优 性原理”，然后在最优策略存在的前提下导出了基本动态方程，再 由此方程求解最优策略。后来，在其应用过程中发现，最优性原理 并非对任何多阶段决策过程普遍成立，它与基本动态方程并不是无 条件等价的，二者之间也不存在任何确定的蕴含关系，基本方程在 动态规划中起着更为本质的作用。 fk（sk）= opt [ vk（sk，uk）+ fk+1（sk+1）]，k=n，n-1，…，2，1 uk Dk（sk） fn+1（sn+1）= （sn+1） —— 边界条件 （为已知函数）
动规划 Dynamie Programming(DP 动态规划 Dynamic Programming 建立DP模型与求解 建立动态规划的模型,就是分析问题并建立问题的动态规划基 本方程,成功地应用动态规划方法的关键,在于识别问题本身的多 阶段特征,将问题分解成为可用递推关系式联系起来的若干子问题, 或者说正确地建立具体问题的基本方程,这不仅需要经验和技巧, 也需要对实际问题敏锐的动察力。而正确建立基本递推关系方程的 关键又在于正确选择状态变量sk+1=Tk(sk,uk),这是建立动态 规划的模型的两个要点。 15
15 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 建立 DP 模型与求解 建立动态规划的模型，就是分析问题并建立问题的动态规划基 本方程，成功地应用动态规划方法的关键，在于识别问题本身的多 阶段特征，将问题分解成为可用递推关系式联系起来的若干子问题， 或者说正确地建立具体问题的基本方程，这不仅需要经验和技巧， 也需要对实际问题敏锐的动察力。而正确建立基本递推关系方程的 关键又在于正确选择状态变量 sk+1 = Tk（sk，uk），这是建立动态 规划的模型的两个要点