第七章 西北农林科技大学运筹学课件动态规划PPT.ppt

动态规划标号法较之穷举法的优点: 第一，容易算出; 其次，动态规划的计算结果不仅得到了从起始点到最终点的最短路线，而且得到了中间段任一点到最终点的最短路线 。 二、基本概念和基本原理 动态规划方法的基本思想： (1)将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数．从而把问题化成一族同类型的子问题，然后逐个求解。 (2)求解时从边界条件开始，逆(或顺)过程行进方向，逐段递推寻优。在每一个子问题求解时，都要使用它前面已求出的子问题的最优结果，最后一个子问题的最优解，就是整个问题的最优解。 (3)动态规划方法是既把当前一段与未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法，因此每段的最优决策选取是从全局考虑的，与该段的最优选择一般是不同的。 二、基本概念和基本原理 三、动态规划模型的建立与求解 （一）动态规划模型的建立 （二）逆序解法与顺序解法 （三）基本方程分段求解时的几种常用算法 （一）动态规划模型的建立 建立动态规划的模型关键，在于识别问题的多阶段持征，将问题分解成为可用递推关系式联系起来的若干子问题，或者说正确地建立具体问题的基本方程。而正确建立基本递推关系方程的关键又在于正确选择状态变量，保证各阶段的状您变量具有递推的状态转移关系 sk+1=Tk(sk,uk) 下面以资源分配问题为例介绍动态规划的建模条件及解法。 三、动态规划模型的建立与求解 例5 某公司有资金10万元．若投资于项目i(i＝1，2，3）的投资额为xi时，其收益分别为g1(x1)＝4x1，g2(x2)＝9x2，g3(x3)＝2x32，问应如何分配投资数额才能使总收益最大? 可以人为地赋予时段，把问题转化为一个3段决策过程。 关键问题是如何正确选择状态变量，使各后部子过程之间具有递进关系。 三、动态规划模型的建立与求解 K=1 K=2 第k段时 所以，建立动态规划模型： 阶段k：本例中取1，2，3 状态变量sk：第k段可以投资于第k项到第3个项目的资金数 决策变量xk：决定给第k个项目投资的资金数。 状态转移方程：sk+1＝sk-xk 最优指标函数fk(sk)：当可投资金数为sk时，投资第k-3项所得的最大收益数。 基本方程为： 三、动态规划模型的建立与求解 建立动态规划模型的要点 1、分析题意，识别问题的多阶段特性，按时间或空间的先后顺序适当地划分为满足递推关系的若干阶段。 2、正确地选择状态变量，使其具备两个必要待征： (1)可知性； (2)能够确切地描述过程的演变且满足无后效性。 3、根据状态变量与决策变量的含义，正确写出状态转移方程sk+1=Tk(sk,uk)或转移规则。 4、根据题意明确指标函数vk,n最优指标函数fk(sk)以及k阶段指标vk(sk,uk)的含义，并正确列出最优指标函数的递推关系及边界条件(即基本方程)。 三、动态规划模型的建立与求解 （二）逆序解法与顺序解法 如果寻优的方向与多阶段决策过程的实际行进方向相反，从最后一段开始计算逐段前推，求得全过程的最优策略，称为逆序解法。 顺序解法的寻优方向同于过程的行进方向，计算时从第一段开始逐段向后递推，计算后一阶段要用到前一阶段的求优结果，最后一段计算的结果就是全过程的最优结果。 三、动态规划模型的建立与求解 第一步：k=0 状态：s1＝A f0(A)＝0 求解步骤 三、动态规划模型的建立与求解 第二步：k=1 状态：B1 B2 u1*(B1)=A u1*(B2)=A f1(B1)＝4 f2(B2)＝5 (4) (5) 三、动态规划模型的建立与求解 第三步：k=2 状态：C1 C2 C3 C4 u2*(C1)=B1 u2*(C2)=B1 u2*(C3)=B1 f2(C1)＝6 f2(C2)＝7 f2(C3)＝10 u2*(C4)=B2 f2(C4)＝12 (4) (5) (6) (7) (10) (12) 三、动态规划模型的建立与求解 (4) (5) (6) (7) (10) (12) 第四步：k=3 状态：D1 D2 D3 u3*(D1)=C1或C2 u3*(D2)=C2 u3*(D3)=C3 f3(D1)＝11 f3(D2)＝12 f3(D3)＝14 (11) (12) (14) 三、动态规划模型的建立与求解 第五步：k=4 状态：E1 E2 u4*(E1)=D1 u4*(E2)=