Page 188 - 数学建模算法与应用

Mathematical Modeling Algorithms and Applications
数学建模算法与应用

第二节 动态规划的基本概念与方程

一、动态规划的基本概念和基本方程

一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。
（一）阶段

阶段是对整体流程的一种合理分割方式，通常基于时间或空间的特点来进行
划分，旨在依照各阶段的序列解决优化问题。阶段变量常用 k = 1，2，…，n 来
标识。例如，在第 1 个例子中，从 A 点开始的阶段被标记为 k = 1，而从 B i (i = 1，
2) 出发的阶段则为 k = 2，以此类推，直至从 Fi(i =1，2) 出发的阶段被定为 k = 6，

总共包含 n = 6 个阶段。在第 2 个例子中，根据一年中的第一、二、三、四季度，
分别设定了 k = 1, 2, 3, 4，共计 4 个阶段。
（二）状态

状态指的是在每个阶段开始之际，流程所处的实际情形。这种状态需要能够
准确地反映流程的特点，并且具有无后效性的特点，一旦确定了某个阶段的状态
变量，那么自此阶段之后的流程发展就不会受到之前阶段状态的影响。此外，状
态通常是可观察的，无论是直接还是间接的方式。用来描述这些状态的变量被称

为状态变量。状态变量所能取的所有可能值的集合，则被定义为允许状态集合。
如果使用xk来代表第k阶段的状态变量，那么这个变量既可以是一个单一的数值，
也可以是一个向量形式的数据。用 Xk 表示第 k 阶段的允许状态集合。在例 1 中

x 2 可取 B1，B2 ，或将 Bi 定义为 i(i = 1，2) ，则 x 2 = 1 或 2 ，而 X 2 = {1，2}。
n 个阶段的决策过程有 n +1 个状态变量，xn 表示 xn 演变的结果。在例 1
+1
中 x 7 取 G ，或定义为 1，即 x 7 = 1。根据过程演变的具体情况，状态变量是离散
的或者是连续的。为了计算的方便有时将连续变量进行离散化；为了方便分析有

时又将离散变量视为连续的，状态变量简称为状态。
（三） 决策
当一个阶段的状态得到确定后，作出各种选择从而演变到下一阶段，再进入

某个状态，这种选择手段称为决策，决策在最优控制问题中也称为控制。其中，
描述决策的变量称决策变量，变量允许取值的范围为允许决策集合。用 u k (xk )
表示第 k 阶段处于状态 xk 时的决策变量，其属于 xk 的函数，用 Uk (xk ) 表示 xk

178