西南科技大学网络教育系列课程 数学建模与数学实验 第7讲 动态规划 主讲教师: 彭煜 杨学南 西南科技大学理学院数学系.

Presentation on theme: "西南科技大学网络教育系列课程 数学建模与数学实验 第7讲 动态规划 主讲教师: 彭煜 杨学南 西南科技大学理学院数学系."— Presentation transcript:

1 西南科技大学网络教育系列课程 数学建模与数学实验 第7讲 动态规划 主讲教师: 彭煜 杨学南 西南科技大学理学院数学系

2 第7章 动态规划 动态规划是解决多阶段决策过程最优化问题的一种数学方法．动态规划在工程技术、管理、经济、工业生产、军事及现代控制工程等方面都有广泛的应用，而且由于动态规划方法有其独特之处，在解决某些实际问题时，显得更加方便有效。 由于决策过程的时间参数有离散的和连续的情况，故决策过程分为离散决策过程和连续决策过程．本部分内容主要介绍离散决策过程，通过几个类型的问题来说明用动态规划处理问题的方法，但所建立的概念、理论和方法，具有相当的重要性．

3 7.1 动态规划的基本方法 7.1.1 多阶段决策过程及实例 在生产和科学实验中一类活动的过程，由于它的特殊性，可将其分为若干个互相联系的阶段，在它的每一个阶段都需要作出决策，从而使整个过程达到最好的活动效果．因此，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又给以后的发展施以影响．当各个阶段决策确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动路线，这样一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，也称序贯决策过程。

4 在多阶段决策问题中，各个阶段采取的决策一般来说是与时间有关的，决策依赖于当前的状态，而又随即引起状态的转移，一个决策序列就是在状态的运动变化中产生的，故有“动态”的含义。因此，把处理它的方法称为动态规划方法。但有一些与时间没有关系的静态规划问题，只要人为地引进“时间”因素，也可把它视为多阶段决策问题，从而用动态规划方法去处理。

5 例（生产-存贮问题）某工厂根据市场调研情况，需制定今后四个月的生产计划，据估计，在这四个月内，市场对该产品需求量如下表所示．

6 此外，各种资源（人力、物力）分配问题、背包问题、购货问题、水库调度问题等等，也都具有多阶段决策问题的特性．
假定生产每批产品的固定成本费用为3千元，每单位产品生产成本费用为1千元，库存费用每月为0.5千元．并且规定四月初和4月末均无产品库存，试求该厂如何安排各个月的生产与库存，使总成本费用最小． 此外，各种资源（人力、物力）分配问题、背包问题、购货问题、水库调度问题等等，也都具有多阶段决策问题的特性．

7 教材上例1的最短路线问题是动态规划中一个较为直观的典型例子．我们通过讨论它的解法来说明动态规划方法的基本思想，并阐述它的基本概念．
7.1.2 动态规划的基本概念和基本方程 教材上例1的最短路线问题是动态规划中一个较为直观的典型例子．我们通过讨论它的解法来说明动态规划方法的基本思想，并阐述它的基本概念． 如教材图7—1所示的线路网络，明显地，从A点到G点可分为6个阶段．从A到B为第一阶段，从B到C为第M阶段，…，从F到G为第六阶段．在第一阶段中A为起点，终点有B1、B2二个，因而这时走的路线有两个选择，若我们选择走到B2的决策，则B2就是我们选择的决策结果．

8 在第二阶段，从B2出发，对应于B2就有一个可供选择的终点集合{C2，C3，C4}，若选择B2到C2为第二阶段的决策，则C2就是第二阶段的终点，同时又是第三阶段的始点．类似地递推下去，我们看到各个阶段的决策不同所走的路线就不同，因而整个路线的长短也不同．问题的要求是在各个阶段选取一个恰当的决策，使由这些决策所决定的一条路线，其总路程最短．

9 若我们采取穷举法．即把由 A到G共有条不同的路线都算出来，比较48条不同路线的最短距离，最短距离为18，找出相应的最短路线为
l．动态规划的基本概念 （1）阶段 把所给问题的过程，恰当地划分为若干个相互联系的阶段，以便于求解．通常用k表示阶段变量．如例1可分为6个阶段来求解．

10 （2）状态 状态表示在任一阶段所处的位置．通常一个阶段有若干个状态．描述状态的变量称为状态变量．参数表示第k阶段的状态变量．如在例1中第三阶段有四个状态，则状态变量 可取四个值，即C1，C2，C3，C4，点集合{C1，C2，C3，C4}就称为第三阶段的可能状态集合，记为S3＝ {C1，C2，C3，C4}。 （3）决策 在某一阶段，当状态给定后，往往可以作出不同的决定，从而确定下一阶段的状态，这种决定称为决策．描述决策的变量称为决策变量，用 表示第阶段当状态为Sk时的决策变量，它是状态Sk的函数．决策变量的变化范围称为允许决策集合．通常以 表示第k阶段状态为Sk时的允许决策集合．显然有

11 （4）状态转移方程 状态转移方程描述由一个状态到另一个状态的演变过程．用 表示，它表示 k阶段与k＋1阶段状态的变换规律．如在例1第二阶段中，若从状态B1出发，就可作出三种不同的决策，其允许决策集合 若选取的点为C2，则C2是状态B1在决策 作用下的一个新的状态，记作

12 （5）策略 由过程的第k阶段开始到终点为止的过程，称为问题的后部子过程，由每段的决策组成的决策函数序列 就称为子过程的策略，简称子策略，记为 当k=1时，则此决策函数序列称为全过程的一个策略，简称策略，记为

13 在实际问题中，由于每个阶段都有若干个状态，针对每一个状态又有多种不同的决策，从而组成了不同的决策函数序列，即存在许多策略可供选择这种可供选择的策略范围，称为允许策略集合，用P表示．从允许策略集合中找出使问题达到最优效果的策略称为最优策略． （6）指标函数和最优指标函数值 指标函数（又称目标函数）是用来衡量所实现过程优劣的一种数量指标，它是定义在过程上的数量函数，用 表示：

14 当初始状态给定时，过程的策略就确定了，因而指标函数也就确定，故指标函数是初始状态和策略的函数，即
阶段指标（又称阶段效益）是衡量该段决策效果的数量指标，用 表示在第k阶段 由状态 和决策所得的效益 ，它表示从第k阶段由状态 的最优值，称为最优指标函 数值，记为 指标函数 它表示从第k阶段由状态 出发到过程结束时所获得的最优指标函数值．

15 在不同的问题中，指标的含义是不同的，可能是距离、利润、资源消耗等．如在最短路线问题中，
表示从第 k阶段的点 Sk至终点 G的距离； 表示由点 Sk到 G的最短距离，用 表示在第k阶段由点sk到点 的距离． 如在第5段中由点E1 到F1的距离为3就记为

16 2．动态规划的基本思想和基本方程 现在，我们结合解决最短路线问题来介绍动态规划方法的基本思想．最短路线有一个重要特性，即如果从起点到终点的最短路线在第k站通过点 ，则由点 出发到达终点的所有可能选择的不同路线来说，必定也是最短的． 最短路线的这一特性，启发我们找最短路线的方法，那就是从最后一段开始，由后向前逐步递推，求出各点到G点的最短路线，最后就求得由A点到G点的最短路线．所以动态规划的方法是从终点逐段向始点寻找最短路线的一种方法． 下面我们按照动态规划的方法，将例1从最后一段开始计算，由后向前逐步推移至A点．

17 当k=5时，出发点有El，E2，E3三个．若从E1出发，则有两个选择，一是至Fl，一是至F2，所以
当k＝6时，由F1到终点G只有一条路线，故 ，同理， 当k=5时，出发点有El，E2，E3三个．若从E1出发，则有两个选择，一是至Fl，一是至F2，所以 ． ． 这说明，其最短路线是 而相应的决策为

18 同理，从E2和E3出发，则有 其最短路线是 其最短路线是

19 完全类似地，可算得如下结果: 当k＝4时，有 当k=3时，有 当k=2时，有

20 再按计算顺序反推之，可得最优决策函数序列
当k＝l时，出发点只有一个A点，则 至此，求得图7一1的最短路线为 相应的最短路为18． ，即由 再按计算顺序反推之，可得最优决策函数序列 ,即由 组成一个最优策略．

21 从最短路线问题例子的计算过程中，我们可以看到，用动态规划方法求解问题的关键，在于正确地写出k阶段与k＋l阶段之间的速推关系式：
（或写成 ) 和边界条件 一般地，k阶段与k＋l阶段的递推关系式可写为 : 边界条件为 其中“opt”是Optimzation（最优化）的缩写．可根据题意选取min或max．这种递推关系式称为动态规划的函数基本方程．

22 7．2 最优化原理与最优性定理 20世纪50年代，R.Bellman等人根据研究一类多阶段决策问题，提出了“最优化原理”作为动态规划的理论基础．长期以来，人们一直沿用这一提法．动态规划原理的内容是，“作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略．” 后来，随着人们深入地研究动态规划，认为动态规划基本方程在动态规划理论中具有更为基础的作用．反映动态规划基本方程的最优性定理是策略最优性的充要条件，而最优化原理是策略最优性的必要条件，它仅是最优性定理的推论而已．

23 最优性定理: 设阶段数为n的多阶段决策过程，其阶段编号为k＝0，1，2，…，n-1允许策略
是最优策略的充要条件是对任意一个k（0＜k＜n-1) 和初始状态 有 其中，

24 它是由初始状态s0和子策略 所确定的k阶段状态， 是状态转移方程.． 是最优策略， 推论: 若允许策略 则对任意的k（0＜k＜n-l)，它的子策略 对于以 为起点的k到n-1子过程来说，必是最优策略 （注意:k段状态 所确定的） 是由S0和 此推论就是最优化原理所谈的内容．关于定理和推论的证明从略．

25 把一个实际问题化为能用动态规划的方法来求解，首先要做的是根据题意把它构造成动态规划的数学模型．构造动态规划模型的步骤为：
7.3 构成动态规划模型的条件 把一个实际问题化为能用动态规划的方法来求解，首先要做的是根据题意把它构造成动态规划的数学模型．构造动态规划模型的步骤为： 一、将实际问题恰当地划分为若干个阶段，一般是根据时间和空间的自然特征而划分，但要便于能把问题的过程转化成多阶段决策的过程．

26 二、正确地选择状态变量 ，使它既能描述过程的演变特征，又要满足无后效性（马尔可夫性）．所谓“无后效性”是指：如果某段状态结定，则在这段以后过程的发展只与当前的状态有关，而与过去的历史无关．若选择状态变量不满足无后效性的要求，则就不能唯一确定下段的状态及其最优指标函数． 三、确定决策变量 及每段的允许决策集合 三、确定决策变量

27 四、正确写出状态转移方程 五、正确列出指标函数关系 ，并要求满足 递推性。 正确的指标函数关系要满足三点： 1．它是定义在过程上的数量函数；
2．要有可分离性并满足推关系，即 的函数，记为 可以表示为

28 3． 对其变元 来说严格单调。 常见的指标函数是取各段指标和的形式，即:

29 其中， 表示初始状态为 时的后部子过程所有子策略中的最优子策略。

30 7.4动态规划的递推方法 在上节已看到，动态规划方法的关键在于正确写出动态规划的递推关系式，而动态规划的递推方式有逆推和顺推两种形式，一般地，当初始状态给定时，用逆推比较方便，当终止状态给定时，用顺推比较方便。 逆推解法 ，并假定最优值函数 设已知初始状态 是以s为初始状态，从k阶段到n阶段所 得到的最大效益。

31 首先从第n 阶段开始，对任意输入参数 ，则此阶段最大效益为 这里 是由状态 所确定的第n阶段的允许决策集合。解此一维极值问题，得到最优值 及最优解 它就是当第n阶段的初始状态为 时的最优决策。

32 然后，进入第n-1阶段，则最大效益为 其中 。解此一维极值问题， 得到最优解 ,就是当第n-1阶段的输入为 时的最优决策。 如此类推，直到第一阶段，得到最大效益为

33 其中 ，解之，得到最优解 在上述逆推过程中，我们逐步求出了极值函数 及相应决策函数 由于初始状态 是已知的，按照上述递推过程相反的顺序推算，就可逐步确定出每一阶段的决策及效益。 综上所述，整个过程包括两个步骤，前一步骤称为“迭代”或“递推”，后一步骤称为“回代”。

34 例: 求 在满足约束条件 之下，使函数 达到最大值。 这个例子可有用初等方法或微分学方法求出它的最优解，现在用动态规划方法来求解。按变量划分阶段，可把它看作一个三阶段决策问题，决策变量分别为 设初始状态 ，状态转移函数为 ，各阶段的效益 按乘法结合起来，

35 。因此从最后一阶段开始，依次列出极值函数不清的递推关系为
设 然后，可逐步求出各阶段的最优值及最优解， 显然有 及最优解 接着可求出（如用微分法） 及最优解

36 及最优解 ，进行回代运算， 由于已知初始状态 得 ， 由此得到最优策略 最大值

37 上述递推过程为求极值问题提供了一条新的途径，把n 维极值问题化为n 个前后关联的一维极值问题，这正是动态规划方法的基本特征。
顺推解法

38 由于终止状态 是已知的，所以回代过程从 开始，按上述过程相反的顺序，就可以逐步确定出每阶段的决策及效益，从而得到整个问题的最优策略。

39 通过上面的讨论，对如何恰当地运用动态规划中的逆推和顺推方法有了比较明确的了解。至于当初始状态和终止状态都已知时，顺推和逆推都可以进行，应视具体情况而定。
注意理解教材中例2的计算方法，它对我们用动态规划的方法去解某些非线性规划问题的思路是有启发的。

40 7.5 动态规划模型举例 畜牧领域的资源分配问题 :

41

42