动态规划实例讲解-1.ppt

第九章 动态规划（续） 动态规划的基本原理 动态规划方法的基本步骤 动态规划方法应用举例 动态规划的基本原理 最优化原理 （贝尔曼最优化原理） 作为一个全过程的最优策略具有这样的性质：对于最优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个最优子策略。该原理的具体解释是，若某一全过程最优策略为： 3.动态规划方法的基本步骤 1．应将实际问题恰当地分割成n个子问题(n个阶段)。通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数n，即k=n。 2．正确地定义状态变量sk，使它既能正确地描述过程的状态，又能满足无后效性．动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的，动态规划中的状态变量必须具备以下三个特征： 3.动态规划方法的基本步骤 (1)要能够正确地描述受控过程的变化特征。 (2)要满足无后效性。即如果在某个阶段状态已经给定，那么在该阶段以后，过程的发展不受前面各段状态的影响，如果所选的变量不具备无后效性，就不能作为状态变量来构造动态规划的模型。 (3)要满足可知性。即所规定的各段状态变量的值，可以直接或间接地测算得到。一般在动态规划模型中，状态变量大都选取那种可以进行累计的量。此外，在与静态规划模型的对应关系上，通常根据经验，线性与非线性规划中约束条件的个数，相当于动态规划中状态变量sk的维数．而前者约束条件所表示的内容，常就是状态变量sk所代表的内容。 3.动态规划方法的基本步骤 3．正确地定义决策变量及各阶段的允许决策集合Uk(sk)，根据经验，一般将问题中待求的量，选作动态规划模型中的决策变量。或者在把静态规划模型(如线性与非线性规划)转换为动态规划模型时，常取前者的变量xj为后者的决策变量uk。 4. 能够正确地写出状态转移方程，至少要能正确反映状态转移规律。如果给定第k阶段状态变量sk的值，则该段的决策变量uk一经确定，第k+1段的状态变量sk+1的值也就完全确定，即有sk+1=Tk(sk ,uk) 3.动态规划方法的基本步骤 5．根据题意,正确地构造出目标与变量的函数关系——目标函数，目标函数应满足下列性质： (1)可分性，即对于所有k后部子过程，其目标函数仅取决于状态sk及其以后的决策 uk ,uk+1,┈,un,就是说它是定义在全过程和所有后部子过程上的数量函数。 (2)要满足递推关系，即 (3)函数 对其变元Rk+1来说要严格单调。 3.动态规划方法的基本步骤 6．写出动态规划函数基本方程 例如常见的指标函数是取各段指标和的形式 其中 表示第i阶段的指标，它显然是满足上述三个性质的。所以上式可以写成 ： 1.动态规划的四大要素 ① 状态变量及其可能集合 xk ? Xk ② 决策变量及其允许集合 uk ? Uk ③ 状态转移方程 xk+1= Tk (xk ,uk ) ④ 阶段效应 rk ( xk , uk ) 求 最 短 路 径  将问题分成五个阶段，第k阶段到达的具体地点用状态变量xk表示，例如：x2=B3表示第二阶段到达位置B3，等等。这里状态变量取字符值而不是数值。 将决策定义为到达下一站所选择的路径，例如目前的状态是x2=B3，这时决策允许集合包含三个决策，它们是D2(x2)=D2(B3)={B3?C1,B3?C2,B3?C3} 最优指标函数fk(xk)表示从目前状态到E的最短路径。终端条件为 f5(x5)=f5(E)=0其含义是从E到E的最短路径为0。 第四阶段的递推方程为 : 其中*表示最优值，在上表中，由于决策允许集合D4(x4)中的决策是唯一的，因此这个值就是最优值。 由此得到f4(x4)的表达式。由于这是一个离散的函数，取值用列表表示： 第三阶段的递推方程为： 由此得到f3(x3)的表达式： 由此得到f2(x2)的表达式： 第一阶段的递推方程为： 由此得到f1(x1)的表达式 资 源 分 配 问 题 例5.6: 有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（万吨）和投入资金（万元）关系见下表： 阶段k：每投资一个项目作为一个阶段； 状态变量xk：投资第k个项目前的资金数； 决策变量dk：第k个项目的投资； 决策允许集合：0≤dk≤xk 状态转移方程：