第四章动态最优化基础§4.1动态最优化的基本问题例：最短路问题图4.1给出了从城市A到城市B的路线图（省略了距离单位标注）。现求一条从A到B的最短路线。图4.1显然，为了从A到B，必须先逐步经过C1、C2、C3、C4等诸城市。而在C1、C2、C3、C4，又都有多种选择。而关键性的困难是当前的最优选择不一定是全局的最优。这类问题也称为多阶段决策问题。§4.2动态最优化的基本概念阶段：将全过程分为若干个有相互联系的阶段，常用字母t、k表示；状态：系统在不同阶段性态。一般来说，系统在一个阶段有多个状态。系统在某一阶段的所有可能的状态构成的集合成为状态集，记为Sk；状态变量：表示系统状态的变量，记为sk。它与阶段有关；决策：在某一阶段的某一状态下，系统由该状态演变到下一阶段某一状态的选择。在第k阶段，处于状态sk时的所有可能的决策集记为Dk（sk）；决策变量：描述决策的变量，它与阶段与系统在该阶段的状态有关。在第k阶段，处于状态sk时的决策记为dk（sk）；状态转移：从当前阶段的某一状态转移到下一阶段的某一状态。状态转移方程：描述状态转移规律的数学方程。它是当前状态变量与决策变量的函数，即),(1kkkkdsTs；策略：从起点到终点的每一阶段的决策所构成的决策序列，称为（全局）策略。自某一阶段起，至终点的决策称为子策略，记为))(,),(()(11,nnknksdsdsp。指标（目标）函数：性能指标或效用指标，它用来评价决策的效果。它可分为阶段指标与全局指标两类。阶段指标是指衡量某一阶段在某一状态下的决策效果的指标。它仅依赖当前状态和当前决策。记为))(,(kkkksdsv；全局指标是指衡量整个全过程或自某一阶段起至终点的各阶段决策的总体效果的指标。它是所有各阶段的状态和决策的函数，即动态最优化的主要问题是寻找一个策略，使全局指标最优。此策略称为动态系统的最优解。注意，最优解是各阶段状态的函数，其含义是在各个阶段，当处于不同的状态下应选择的（从全局）最优决策。动态最优化的分类离散阶段、离散状态的动态优化问题；离散阶段、连续状态的动态优化问题（如长期投资问题）；连续阶段、离散状态的动态优化问题；连续阶段、连续状态的动态优化问题（如追击问题、长期投资问题）。处理动态最优化的常用方法：1）变分方法；2）极大极小原理（Pontryagin原理）；3）动态规划（Bellmen方法）。§4.3动态规划方法对于动态规划而言，它要求过程的全局指标函数是各阶段指标的和，即动态规划最优化原理（RichardBellman）作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，对前面决策所形成的状态而言，余下的诸决策必须构成最优策略。该原理可以这样理解：如果在某一阶段的某一状态位于全局最优路径上，则以它为起点到终点的最优策略一定与全局最优策略重合。由基本原理，不难得到动态规划的函数基本方程（反向递归方程）：其中，)(kksf表示在第k阶段的某一状态下到终点的最优指标函数。例：求前例的最短路。（反向递归）例：某商店在未来四个月里销售一种商品。它有一个最大容量为1000件的仓库。该商店每月中旬订购商品，下月初到货。经市场调查，今后四个月商品的购买价与销售价如下表所示。假定商店在1月初已有500件库存商品，在不考虑市场需求和库存费用的条件下，问如何安排每月的订购量和销售量，使6个月的总利润最大。月份购买价pk销售价qk110122993111341517解：这是一个四阶段决策问题。决策变量是每月的订购量xk，销售量yk。取状态变量为每月的库存量，记为sk；并记仓库最大容量为H=1000。显然，状态转移方程为基本函数方程为利用后向算法求解。令4k，解约束极值问题：显然，该优化问题的解是4*4sy，0*4x，此时，44417)(ssf。令3k，有优化问题这是一个线性规划问题，解之，有Hx*3，3*3sy，Hssf613)(333。令2k，有优化问题其最优解为Hx*2，2*2sy，Hssf109)(222。令1k，得其最优解为0*1x，1*1sy，Hssf1012)(111。最后，注意到初始条件5001s，1000H，对上述求出的最优解逐步回代，得到该问题的最优解：0*1x，5001*1sy；1000*2Hx，0*1*112*2yxssy；1000*3Hx，1000*2*223*3yxssy；0*4x，1000*3*334*4yxssy。在用动态规划方法解多阶段决...
