第9章动态规划

1、第9章 动态规划§9.1 动态规划基本概念和基本定理9.1.1 动态规划举例和基本术语动态规划是运筹学的一个分支,是解决多阶段决策过程最优化的一种数学方法，主要用于以时间或地域划分阶段的动态过程的最优化1951年美国数学家R. Bellman等人根据一类多阶段决策问题的特性，提出了解决这类问题的“最优化原理”，并研究和解决了许多实际问题，从而创立了“动态规划”. 动态规划在工程技术、管理、经济、工业生产、军事以及现代控制工程等领域中都有广泛的应用，并获得显著的效果状态状态状态12n决策决策决策多阶段决策过程:由于其特性可将过程按时间、空间等标志分为若干个状态互相联系而又相互区别的阶段

2、在每一阶段都需要作出决策，从而使整个过程达到最优各个阶段决策的选取依赖于当前面临的状态，又给以后的发展以影响当各个阶段决策确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动路线这样一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，也称序贯决策过程动态规划举例：例1：最短路线问题: 确定一条由A到E路程最短的路线这种多阶段决策过程最优化是典型动态规划问题将整个过程分成4个阶段，要求在每个阶段做出选择，使从A到E的全过程达到最优化，即使总路程最短（或费用最小）48583256543235AB1B2C1AC2AC3AD1AD2AEA例2:生产-存贮问题: 某工厂根据市场调查情况，

3、需制定今后四个月的生产计划。市场对该产品需求量如下：月份1234需求2324假定生产每批产品的固定成本费为3千元，每单位产品的生产成本费为1千元，库存费为每月0.5千元，并且假定1月初和4月末均无产品库存试求该厂如何安排各个月的生产与库存，使总成本费最小？基本术语：（1）阶段和阶段变量阶段是整个过程的自然划分，通常按时间顺序或空间特性划分阶段。表示阶段序号的变量称为阶段变量，用字母k表示（2）状态和状态变量每个阶段开始所处的自然状况或客观条件称为状态，是不可控因素例1中，每个阶段的状态为该阶段初始点的集合描述每个阶段状态的变量称为状态变量，用表示第k阶段的状态变量的全体可取值组成的集合，称为第

4、k阶段允许状态集合，用表示对例1： 注1：动态规划中定义的状态应具有无后效性。无后效性又称马尔科夫性，指系统从某个阶段后的发展，完全由本阶段所处的状态及其往后的决策决定，与系统以前的状态和决策无关具有无后效性的多阶段决策过程，意味着系统过程的历史只能通过系统现阶段的状态去影响系统的未来，即当前状态就是过程往后发展的初始条件（3）决策、决策变量和决策序列一个阶段的状态确定后，可以作出不同的选择，从而演变到下阶段的某个状态，这种选择称为决策描述决策的变量称为决策变量，用表示第k阶段状态变量取值时的决策变量给定状态变量的取值后，决策变量全体可取值组成的集合称为第阶段从出发的允许决策集合，用表示对例1

5、， 由决策组成的序列称为决策序列从初始状态开始，由各阶段决策()组成的序列称为全过程策略，简称为策略，记作。从第k阶段开始到终止状态的过程称为后部子过程（或称k子过程）由k子过程各阶段的决策组成的序列称为k子过程策略，简称为子策略，记作实际问题中，可供选择的策略有一定范围，称此范围为允许策略集合，记作.允许策略集合中达到最优效果的策略称最优策略（4）状态转移方程若第k阶段的状态和决策给定，则第阶段的状态随之而定：称此关系为状态转移方程例1中，状态转移方程为.（5）指标函数指标函数是衡量过程优劣的数量指标，它是定义在全过程和所有后部子过程上的数量函数：表示初始状态为采取策略时全过程的指标函数值：

6、表示在第k阶段状态为采用策略时，后部子过程的指标函数值采用不同的策略可以得出不同的指标函数值指标函数取得最优值（最大值或最小值）时，相应的策略称为最优策略最优指标函数记作它与指标函数之间的关系：注2：指标函数应具有可分离性，并满足递推关系，即可表示成，和的函数。常见的指标函数形式：表示第j阶段的阶段指标（6）最优策略和最优轨线使指标函数达到最优值的策略称为第k后部子过程中的最优策略；使指标函数达到最优值的策略称为全过程中的最优策略，简称为最优策略按最优策略和状态转移方程得出的状态序列， ，称为最优轨线9.1.2动态规划基本定理和基本方程最优性原理：多阶段决策过程的特点：每个阶段都要进行决策，n

7、段决策过程的策略是由n个相继进行的阶段决策构成的决策序列由于前一阶段的终止状态又是后一阶段的初始状态，因此，阶段k的最优决策不应该只是本阶段效应的最优，而必须是本阶段及其所有后续阶段的总体最优，即关于整个k后部子过程的最优决策Bellman在深入研究的基础上，针对具有无后效性的多段决策过程的特点，提出了著名的解决多段决策问题的最优性原理：“作为整个过程的最优策略具有这样的性质：无论初始状态和初始决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略”.最优性原理的含义：最优策略的任何一部分子策略，也是相应初始状态的最优策略每个最优策略只能由最优子策略构成对于具有无后效性的多段决策

8、过程而言，如果按照k后部子过程最优的原则来求各阶段状态的最优决策，那么这样构成的最优决策序列一定具有最优性原理所揭示的性质利用这个原理，可以把多段决策问题的求解看成是一个连续的递推过程，由后向前或由前向后逐步推算求解时在各阶段以前的状态和决策，对其后面的子问题来说，只不过相当于其初始条件而已，并不影响后面过程的最优策略因此，可以把一个问题按阶段分解成许多相互联系的子问题，其中每个子问题均是一个比原问题简单得多的优化问题，并且每一个子问题的求解仅利用它的下一阶段子问题的优化结果，依次求解即可求得原问题的最优解 基本定理：定理1：（动态规划的最优性定理）对于给定的初始状态，策略是最优策略的充分必要

9、条件是，对于任意的，有, 其中，是由初始状态和子策略确定的第k阶段状态定理2：若允许策略是最优策略，则对任意的,子策略对以为起点的k到n子过程来说，必是最优策略注3：定理2 是定理1的必要性命题这个定理实际上就是R . Bellman等人提出的最优性原理，即一个最优策略的子策略总是最优的基本方程:根据最优指标函数的定义及定理1，必有根据上述分析，得到动态规划基本方程（也称为Bellman方程）：，终端条件为. 动态规划基本方程是最优性原理的体现，也显示了构成最优策略的最优决策的性质：不论作为前面阶段结果的当前阶段的状态是什么，当前阶段的决策必须选择为该阶段效应及其后部子过程的条件指标函数值之和

10、为最优的决策注4：动态规划的基本原理，是针对具有无后效性的多段决策过程的特点，对于任意给定的阶段状态，研究其下一阶段可能到达的所有状态，并求出最优后续过程从出发的所有后部子过程中找最优决策，等效于对出发的所有决策的阶段效应及其相应的到达状态的最优后部子过程的条件最优指标函数值之和求最优决策。一般来说，的所有最优后部子过程要比所有后部子过程少得多，因此，按后者求最优决策和策略的方法要优越得多，动态规划的真谛就在这里§9.2 动态规划的求解方法9.2.1 逆推解法逆推解法的计算步骤：（1）利用已知条件，从开始由后向前推算，求得各阶段最优决策和最优指标函数，最后算出得到最优指标函数值。（2

11、）再从开始，利用状态转移方程确定最优轨线和最优策略。例3：最短路线问题: 用逆推法确定一条由A到E路程最短的路线初始状态，状态转移方程。最优指标函数是各地到E地的最小路程。当时，有，当时，有当时，有当时，有由A到E的最短路程。利用最优决策序列得出最优轨线：例4：（资源分配问题）某单位将6套设备分配给A，B，C三个用户，每个单位分配设备数量与可获利润如下：设备数ABC00001435298103121112414151451617166191817如何分配才能使总利润最大？该问题可归结为多阶段决策过程最优化，按用户划分为3个阶段。A，B，C三个用户编号为1，2，3。状态变量表示分配给第k个用户到

12、第n（n=3）个用户的设备数。决策变量表示分配给第k个用户的设备数。动态规划基本方程：状态转移方程为：当时，有，最优决策由下表给出01234560123456051012141617当时，有状态转移方程为： 0123456000010+53+05020+103+58+010030+123+108+511+0131,240+143+128+1011+515+018250+163+148+1211+1015+517+021360+173+168+1411+1215+1017+518+0254当时，有状态转移方程为： 012345660+254+219+1812+1314+1016+519+0272

13、再由前向后顺推，确定分配方案。，因此有 当时，当时，即6套设备分配给每个用户各2套，总利润最大为27万元。9.2.2 顺推解法顺推解法与逆推解法的递推顺序正好相反。从第1阶段开始，利用状态转移方程，由前向后推算。递推方程为：始端条件：最优指标函数表示第k阶段末的结束状态为，从第1阶段到第k阶段的最优值。是由确定的允许决策集合，即在第k阶段中可将状态转移到状态的允许决策集合。例5：最短路线问题: 用顺推法确定一条由A到E路程最短的路线（数据见例3）初始条件。当时，有，当时，有当时，有当时，有最优决策序列：，最优路线为：9.2.3 动态规划求静态规划问题动态规划和静态规划本质上是条件极值问题，在很多情形下可以相互转化：（1）动态规划可以看作求决策变量，使指标函数达到最优的极值问题，从而可以用静态规划方法求解。约束条件为状态转移方程、端点条件，允许状态集合，允许决策集合等。（2）一些静态规划，只要适当引入阶段变量、状态变量、决策变量等，就可以用动态规划方法求解。动态规划能够求出全局最优解，有时可以得到一族最优解，而且能够利用经验提高求解效率。例6：用动态规划的逆推法求解非线性规划按变量个数划分阶段，把该规划问题看作3阶段决策过程最优化问题。设状态变量为。把约束条件看作资源限