动态规划实例讲解.ppt

《动态规划实例讲解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九章动态规划（续）动态规划的基本原理动态规划方法的基本步骤动态规划方法应用举例本章以下内容1最优化原理（贝尔曼最优化原理）作为一个全过程的最优策略具有这样的性质：对于最优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个最优子策略。该原理的具体解释是，若某一全过程最优策略为：动态规划的基本原理则对上述策略中所隐含的任一状态而言，第k子过程上对应于该状态的最优策略必然包含在上述全过程最优策略p1*中，即为23.动态规划方法的基本步骤1．应将实际问题恰当地分割成n个子问题(n个

2、阶段)。通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数n，即k=n。2．正确地定义状态变量sk，使它既能正确地描述过程的状态，又能满足无后效性．动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的，动态规划中的状态变量必须具备以下三个特征：33.动态规划方法的基本步骤(1)要能够正确地描述受控过程的变化特征。(2)要满足无后效性。即如果在某个阶段状态已经给定，那么在该阶段以后，过程的发展不受前面各段状态的影响，如果所选的变量不具备

3、无后效性，就不能作为状态变量来构造动态规划的模型。(3)要满足可知性。即所规定的各段状态变量的值，可以直接或间接地测算得到。一般在动态规划模型中，状态变量大都选取那种可以进行累计的量。此外，在与静态规划模型的对应关系上，通常根据经验，线性与非线性规划中约束条件的个数，相当于动态规划中状态变量sk的维数．而前者约束条件所表示的内容，常就是状态变量sk所代表的内容。43.动态规划方法的基本步骤3．正确地定义决策变量及各阶段的允许决策集合Uk(sk)，根据经验，一般将问题中待求的量，选作动态规划模型中的决策

4、变量。或者在把静态规划模型(如线性与非线性规划)转换为动态规划模型时，常取前者的变量xj为后者的决策变量uk。4.能够正确地写出状态转移方程，至少要能正确反映状态转移规律。如果给定第k阶段状态变量sk的值，则该段的决策变量uk一经确定，第k+1段的状态变量sk+1的值也就完全确定，即有sk+1=Tk(sk,uk)53.动态规划方法的基本步骤5．根据题意,正确地构造出目标与变量的函数关系——目标函数，目标函数应满足下列性质：(1)可分性，即对于所有k后部子过程，其目标函数仅取决于状态sk及其以后的决策u

5、k,uk+1,┈,un,就是说它是定义在全过程和所有后部子过程上的数量函数。(2)要满足递推关系，即(3)函数对其变元Rk+1来说要严格单调。66．写出动态规划函数基本方程例如常见的指标函数是取各段指标和的形式其中表示第i阶段的指标，它显然是满足上述三个性质的。所以上式可以写成：3.动态规划方法的基本步骤7学习方法建议：第一步先看问题，充分理解问题的条件、情况及求解目标。第二步结合前面讲到的理论和解题过程，考虑如何着手进行求解该问题的工作。分析针对该动态规划问题的“四大要素、一个方程”——这一步在开始

6、时会感到困难，但是一定要下决心去思考，在思考过程中深入理解前文讲到的概念和理论。4.动态规划方法应用举例8第三步动手把求解思路整理出来，或者说，把该问题作为习题独立的来做。第四步把自己的求解放到一边，看书中的求解方法，要充分理解教材中的论述。第五步对照自己的求解，分析成败。4.动态规划方法应用举例91.动态规划的四大要素①状态变量及其可能集合xkXk②决策变量及其允许集合ukUk③状态转移方程xk+1=Tk(xk,uk)④阶段效应rk(xk,uk)4.动态规划方法应用举例102.动态规划基本方程f

7、n+1(xn+1)=0(边界条件)fk(xk)=optu{rk(xk,uk)+fk+1(xk+1)}k=n,…,14.动态规划方法应用举例11求最短路径12求最短路径例5.513将问题分成五个阶段，第k阶段到达的具体地点用状态变量xk表示，例如：x2=B3表示第二阶段到达位置B3，等等。这里状态变量取字符值而不是数值。将决策定义为到达下一站所选择的路径，例如目前的状态是x2=B3，这时决策允许集合包含三个决策，它们是D2(x2)=D2(B3)={B3C1,B3C2,B3C3}求最短路径14最优指

8、标函数fk(xk)表示从目前状态到E的最短路径。终端条件为f5(x5)=f5(E)=0其含义是从E到E的最短路径为0。第四阶段的递推方程为:求最短路径15其中*表示最优值，在上表中，由于决策允许集合D4(x4)中的决策是唯一的，因此这个值就是最优值。由此得到f4(x4)的表达式。由于这是一个离散的函数，取值用列表表示：求最短路径16第三阶段的递推方程为：求最短路径17由此得到f3(x3)的表达式：求最短路径18求最短路径19由此得到f2(x2)的表达式