文档介绍：第七章动态规划
第1页，共61页，2022年，5月20日，20点16分，星期六
Chapter 7 动态规划 (Dynamic Programming)
多阶段决策问题
动态规划的基本概念
动态规划的求解步骤
动态规划模型的建立与决策变量
当一个阶段的状态确定后，可以作出不同的决定或选择，从而演变到下一阶段的某个状态，这种决定或选择称为决策。描述决策的变量称为决策变量，通常用uk表示，前面已经说过，决策要依据该阶段的状态，因此通常用uk(sk)表示第k阶段处于状态sk时的决策。决策变量的取值范围称为决策集合 ，表示为Dk(sk)。
第9页，共61页，2022年，5月20日，20点16分，星期六
动态规划的基本概念和基本方法
4、策略与子策略
一组有序的决策序列构成一个策略，从第k阶段至第n阶段的一个策略称为后部子策略记为 pk，n →（uk，uk+1，…，un）。
5、状态转移方程
在确定型多阶段决策过程中，一旦某阶段的状态和决策为已知，下一阶段的状态便完全确定，用状态转移方程反映这种状态间的演变规律，写作：
（）
第10页，共61页，2022年，5月20日，20点16分，星期六
动态规划的基本概念和基本方法
6、指标函数
衡量决策效果优劣的数量指标称为指标函数，具体可以是收益、成本、距离等指标，可以分为k阶段指标函数，子过程指标函数和最优指标函数。
从k阶段状态sk出发，做出决策uk所产生的第k阶段指标称为k阶段指标函数，记为vk(sk, uk)。从k阶段状态sk出发，选择决策uk，uk+1，…，un所产生的过程指标，称为k子过程指标函数或简记为过程指标函数，记为Vk(sk, uk,uk+1,…,un)或Vk,n。从k阶段状态sk出发，对所有的子策略，最优的过程指标函数称为最优指标函数，记为fk(sk)，通常取Vk的最大值或最小值。
第11页，共61页，2022年，5月20日，20点16分，星期六
动态规划的基本概念和基本方法
通常要求动态规划的子过程指标满足递推关系
常用的有连加和连乘的形式，分别为
（）
（）
第12页，共61页，2022年，5月20日，20点16分，星期六
动态规划的基本概念和基本方法
最有指标函数fk(sk)取式（）和（）的最优值，分别为：
式（）和（）称为动态规划的基本方程。为了使递推方程有递推起点，需要确定最后一个状态sn的最优指标函数fn(sn)的值，称为终端条件。一般情况下，连和形式fn(sn)=0，连乘形式fn(sn)=1。
动态规划的数学模型由式()或()，边界条件及状态转移方程构成，如连加形式的数学模型为：
（）
（）
第13页，共61页，2022年，5月20日，20点16分，星期六
动态规划的基本概念和基本方法
由式（）和使（）的形式知，计算顺序是从最后一个阶段开始到第一个阶段结束，这种方法称为逆序算法。也可以将基本方程改为前向递推：
这时计算顺序是从第一阶段开始到最后一个阶段结束，这种算法称为顺序算法。
第14页，共61页，2022年，5月20日，20点16分，星期六
动态规划的基本概念和基本方法
总结
在明确了动态规划的基本概念和基本思想之后，在解决一个实际问题建立动态规划模型时，步骤如下：
（1）将问题的过程划分为恰当的阶段；
（2）正确选择状态变量sk，使它既能描述过程的演变，又能满足无后效性；
（3）正确写出决策变量uk及每阶段的允许决策集合Dk(sk)；
（4）正确写出状态转移方程；
（5）正确写出指标函数Vk,n的关系，它满足下面三个性质：
第15页，共61页，2022年，5月20日，20点16分，星期六
动态规划的基本概念和基本方法
①是定义在全过程和所有后部子过程上的数量函数；
②具有可分离性，并满足递推关系。即：
③函数 对于变量Vk+1,n要严格单调。
以上五点是构造动态规划模型的基础，是正确写出动态规划基本方程的基本要素。而一个问题的动态规划模型是否正确给出，它集中反映在恰当地定义最优值函数和正确写出递推关系式及边界条件。简而言之，要正确写出动态规划的基本方程。
第16页，共61页，2022年，5月20日，20点16分，星期六
动态规划举例
下面我们举一个动态规划的实际例子。
（基建投资问题）一家公