运筹学教案(动态规划）.pptVIP

概述 状态与状态变量 状态： 表示每个阶段开始时所处的自然状况或客观条件，又称为不可控因素，是阶段的特征，通常一个阶段有若干个状态。 如：前例，第一阶段状态为点A，第二阶段的状态有B1，B2，B3三个状态。 状态变量：描述过程状态的变量称为，一般用xk表示第k个阶段的状态变量。 状态集： k阶段所有可能状态构成的集合。记为Sk，如S2={B1,B2,B3} 状态的无后效性： 即当某阶段的状态一旦确定,则此后过程的演变不再受此前各状态和决策的影响, 或者说“未来与过去无关”。 即由状态xk出发的后部子过程可以看成一个以xk为初始状态的独立过程。 注：阶段的划分与状态的选择要具有此性质，是动态规划问题的特点。 决策与决策变量 决策：使在k阶段，使状态从xk 到xk+1 发生转移的选择。 决策变量：描述决策的变量称为决策变量，一般用uk表示第k个阶段的决策变量。 决策空间：即决策变量可能取值的集合，用Dk(xk)表示第k个阶段xk状态下的所有允许决策的集合。 状态转移方程 状态转移：系统由某一阶段的一个状态因相关决策而转变到下一个阶段的另一个状态。与阶段、状态和决策有关，用下图示意： 全过程与后部k子过程 从k阶段开始到终止状态为止的过程称为动态规划问题的后部 k 子过程。如下图所示： 全过程：k=1时的子过程。 策略与k子策略 策略：设 为k阶段作出的决策，则称其组成的决策序列 为整个过程的一个全过程策略，简称为策略，记为p1,n(x1)。可供选择的所有全过程策略的集合构成允许策略集合，记为P1,n(x1)。 最优策略：使总体效果达到最优的策略。记为 k子策略: k部子过程对应决策形成的决策序列。记为pk,n(xk)= 指标函数与最优指标数 阶段指标函数：指对某一个阶段的决策效果进行衡量其优劣的一种数量指标。 一般记为： vk(xk; uk) K指过程的指标函数：描述　k子过程策略效果优劣的数量函数，记为： Vk,n(xk; pk,n ) 或Vk,n 。 由阶段划分与状态选择的无后效性知，k阶段指标函数具有可分性，即可写为： K=1时称为全过程的指标函数。 一般地，其可分性写为 最优指标函数：指标函数的最优值称为最优指标函数，记为 即有： 最优化原理 “作为全过程的最优策略具有这样的性质：无论过去的状态和决策如何，对于前面决策所形成的状态（即该最优策略上某一状态）而言，余下的诸决策必须构成以此状态为初始状态的最优策略。 即：最优策略的任一后部子策略都是最优的。 注：最优化原理只是最优性定理的一个推论，即最优策略的必要条件。即最优性原理不是对任何决策过程普遍成立，它与基本方程不是无条件等价。 故逆序递推法的基本方程为： 此两个基本方程描述多阶段决策问题的求解方法，可以处理广泛的实际优化问题，而且可以得到各阶段的一系列最优解。 但是要受到维数限制。 求解动态规划问题的过程： （1）将问题过程划分恰当阶段，选择阶段变量k.。 （2）正确选择状态变量xk. 应注意：既能够正确描过程的演变，又要满足无后效性。 （3）正确选择决策变量uk，确定允许集合 。 （4）正确写出状态转移方程 xk+1= Tk(xk, uk)。 （5） 列出按阶段可分的准则函数V1,n ，要满足几个性质。 （6）根据求解方向，给出边界条件。 （7）利用基本方程逆推求解。 动态规划的最优性定理 最优性原理仅为策略最优的必要条件，是最优性定理的推论，为此下面介绍最优性定理。 例一：前述最短距离问题逆向标注法 动态规划应用——资源分配问题 将把资料分配给一个或多个使用者的过程作为一个阶段，此静态规划问题的决策变量为多阶段决策变量，将累计的量或递推过程中变化的量选择为状态变量。 决变量策变量 uk 表示分配给第k种产品的原料数，状态 xk 表示分配用于生产第k种产品至第n种产品的原料数，则有状态转移方程： 而且 阶段指标函数为 边界条件为 例：某公司现有4台设备准备分配给该公司所属的3家工厂. 当分配台uk设备给工厂k时，工厂k利用这些设备为公司创造的利润（假设非负）为gk(uk). 应当如何分配设备资源，使得公司总利润最大？其利润见下表： 将此问题划分为三个阶段，1，2，3个工厂，其模型为前述模型中n=3,a=4 基本方程为： 从最后一个阶段，即3阶段计算，并逐次逆推，直到求出最优解。 用动态规划原理求解静态规划问题 某些静态规划问题，在适当引入阶段变量及状态变量之后，可转化为动态规划问题求解。 并且可以用逆推算法或顺推算法求解。以具体例子加以说明。 P206~211 动态规划的计算框图 详