动规划 Dynamie Programming(DP 动态规划 Dynamic Programming 建立DP模型与求解 建立动态规划的模型的十步曲: 1、正确、明确地划分阶段k,k=1,2,3, n。依据决策过 程的时间和空间的顺序关系 2、正确选择并确定状态变量sk及状态集合Sk。状态变量的确定有 时并非显而易见,要确定它,通常可对问题作如下分析而帮助确定 状态变量 a.什么关系将各个阶段联系在一起? b.为了决定今后的最优(子)策略,需要事件现状的哪些信息? 16
16 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 建立 DP 模型与求解 建立动态规划的模型的十步曲： 1、正确、明确地划分阶段 k， k =1，2，3，…，n。依据决策过 程的时间和空间的顺序关系。 2、正确选择并确定状态变量 sk 及状态集合 Sk 。状态变量的确定有 时并非显而易见，要确定它，通常可对问题作如下分析而帮助确定 状态变量 a. 什么关系将各个阶段联系在一起？ b. 为了决定今后的最优（子）策略，需要事件现状的哪些信息？
动规划 Dynamie Programming(DP 动态规划 Dynamic Programming 建立DP模型与求解 3、确定决策变量uk及决策集合Dk(sk)。 4、写出状态转移方程sk+1=Tk(sk,uk) 5、定义阶段指标值(函数)vk(sk,uk)。 6、定义第k至n阶段(后部子过程)的最优指标(目标)函数 7、作出动态规划结构图: k阶段 k+1阶段 V(Sw, u) op k ∈Dk(sk) Sk+1 k (sk, uk k (∑,Ⅱ)fk(sk) fK+(Sk+ 17
17 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 建立 DP 模型与求解 3、确定决策变量 uk 及决策集合 Dk（sk）。 4、写出状态转移方程 sk+1 = Tk（sk，uk）。 5、定义阶段指标值（函数） vk（sk，uk）。 6、定义第 k至 n 阶段（后部子过程）的最优指标（目标）函数 fk（sk）。 7、作出动态规划结构图： sk sk+1 = Tk（sk，uk） k阶段 fk（sk） k+1阶段 fk+1（sk+1） opt （ ，） vk（sk，uk） uk Dk（sk）
动规 Dynamic Programming(DP 动态规划 Dynamic Programming 建立DP模型与求解 8、建立动态规划基本方程:(逆序递推方程) fK(Sk)= opt [VK(Sk, uk) +k+1(Sk+)l, k=n-1 2,1 uk∈Dk(sk 或k=n,n-1 opt [Vn(Sn, un)I U,∈Dn(sn) 或fn+1(sm1)=q(sn+1)—边界条件(q为已知函数) 18
18 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 建立 DP 模型与求解 8、建立动态规划基本方程：（逆序递推方程） fk（sk）= opt [ vk（sk，uk）+ fk+1（sk+1）]，k= n-1，…，2，1 uk Dk（sk） fn（sn）= opt [ vn（sn，un）] 或 fn+1（sn+1）=（sn+1） —— 边界条件 （为已知函数） un Dn（sn） 或 k=n，n-1，…，1
动规 Dynamic Programming(DP 动态规划 Dynamic Programming 建立DP模型与求解 9、逆序递推求解动态规划基本方程。 求出最优决策序列u*n,u*n1 10、顺序确定最优策略。p*1n={u*1,u*2,…,u*n} 2 T2(s2,U2) 2 n n 19
19 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 建立 DP 模型与求解 9、逆序递推求解动态规划基本方程。 求出最优决策序列 u*n，u*n-1，…，u*2，u*1 10、顺序确定最优策略。 p*1n = { u*1，u*2，…，u*n } s1 u*1 u*2 u*n s2 = T2（s2，u2） … sn …
动规划 Dynamie Programming(DP 动态规划 Dynamic Programming 建立DP模型与求解 例分配投资问题 某公司有资金10万元,若投资于项目k(k=1,2,3)的投 资额为xk时,其收益分别为g1(X1)=4x1,g2(X2)=9x2, g3(x3)=2x32,问应该如何分配投资数额才能使总收益最大? 该问题表面上看与时间无明显关系,其静态模型: Max z= 4x+ 9x2 2X3 X1 + X 2 + X 3 10 x1≥0(i=1,2,3)
20 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 建立 DP 模型与求解 例 分配投资问题 某公司有资金 10 万元，若投资于项目 k （k = 1，2，3）的投 资额为 xk 时，其收益分别为 g1（x1）= 4x1 ， g2（x2）= 9x2 ， g3（x3）= 2x3 2 ，问应该如何分配投资数额才能使总收益最大？ 该问题表面上看与时间无明显关系，其静态模型： Max z = 4x1 + 9x2 + 2x3 2 x1 + x2 + x3 = 10 xi ≥ 0 （i = 1，2，3）