动态规划

多阶段的决策问题

所谓多阶段决策是指这样一个决策过程：它可以分为若干个互相联系的阶段，在每一阶段分别对应着一组可以选取的决策，当每个阶段的决策选定以后，过程也就随之确定。把各个阶段的决策综合起来，构成一个决策序列，成为一个策略。显然由于各个阶段选取的决策不同对应整个过程就可以有一系列不同的策略。当对过程采取某一策略时，可以得到一个确定的（或期望的）效果，采取不同的策略，就会得到不同的效果。多阶段决策问题，就是要在所有可能采取的策略中间选取一个最优的策略，使在预定的标准下得到最好的效果。

最优原理与动态规划的数学模型

动态规划问题的解题思路

用动态规划方法解题的基本思路，是将一个 $n$ 阶段的决策问题转化依次求解 $n$ 个具有递推关系的单阶段决策问题，从而简化计算过程。其中逆序算法使用的较多。

多阶段转化为依次求解多个单阶段的决策问题时，一个重要特征就是将前面的解传递并纳入下一个阶段一并考虑，即做到求解的各阶段间具有 传递性。

动态规划基本概念

阶段（ $stage$ ） 指一个问题需要做出决策的步数，通常用 $k$ 来表示问题包含的阶段数，称为 阶段变量。 $k$ 的编号方法有两种： $(1)$ 顺序编号法，即初始阶段编号为 $1$ ，以后随进程逐渐增大； $(2)$ 逆序编号法，令最后一个阶段编号为 $1$ ，往前推时编号逐渐增大。一般采用顺序编号法。
状态（ $state$ ） 是动态规划中一个最关键的参数，既反映前面各阶段状态和决策的结局，又是本阶段做出决策的出发点和依据。状态时动态规划问题各阶段的传递点和结合点，第 $k$ 阶段的状态变量 $s_k$ 应包含该阶段之前决策过程的全部信息，做到从该阶段后做出的决策同这之前的状态和决策相互独立。各阶段的状态通常用状态变量 $s$ 来描述，向量中所含变量个数称为动态规划问题的维数。
决策（decision） 指某阶段初从给定的状态出发，决策者在面临的若干种不同方案中做出的选择。决策变量 $x_k(s_k)$ 表示第 $k$ 阶段初状态为 $s_k$ 时对方案的选择。决策变量的取值要受到一定范围的限制，用 $D_k(s_k)$ 表示 $k$ 阶段状态为 $s_k$ 时决策允许的取值范围，称允许决策集合，因而有
$x_k(s_k) \in D_k(s_k)$
策略（policy）和子策略（subpolicy），动态规划问题各阶段决策组成的序列总体称作一个策略。含 $n$ 个阶段的动态规划问题的策略可写为
$\{ x_1(1s_1),x_2(s_2),\cdots ,x_n(s_n) \}$
把从某一阶段开始到过程最终的决策序列称为问题的子过程策略或子策略。从 $k$ 阶段起的子策略可写为
$\{ x_k(s_k),x_{k+1}(s_{k+1}),\cdots ,x_n(s_n) \}$
状态转移律。从 $s_k$ 的某一状态值出发，当决策变量 $x_k(s_k)$ 的取值决定后来，下一阶段状态变量 $s_{k+1}$ 的取值也就随之确定。这种从上阶段的某一状态值到下阶段某一状态值的转移的规律称为状态转移律。显然下一阶段状态 $s_{k+1}$ 的取值时上阶段状态变量 $s_k$ 和上阶段决策变量 $x_k(s_k)$ 的函数，记为
$s_{k+1} = T(s_k,x_k(s_k))$
或简写为
$s_{k+1} = T(s_k,x_k)$
状态转移律也称状态转移方程。
指标函数。有阶段指标函数和过程指标函数之分。阶段指标函数是对应某一阶段状态和从该状态出发的一个阶段的决策的某种效益度量，用 $v_k(s_k,x_k)$ 表示。过程指标函数是指从状态 $s_k(k=1,\cdots ,n)$ 出发至过程最终，当采取某种子策略时，按预定标准得到的效益值。这个值既与 $s_k$ 的状态值有关，又与 $s_k$ 之后所选取的策略有关，它是两者的函数值，记作
$V_{k,n}(s_k,x_k,s_{k+1},x_{k+1},\cdots ,s_n,x_n)$
过程指标函数又是它所包含的各阶段指标函数的函数，按问题性质，它可以是各阶段指标函数的和、积或其他函数形式。当 $s_k$ 的值确定后，指标函数的值就只同 $k$ 阶段起的子策略有关。所谓最优指标函数，是指对某一确定状态选取最优策略吼得到的指标函数值，实际上也就是对应某一最优子策略的某种效益度量（这个度量值可以是产量、成本、距离等）。对应从状态 $s_k$ 出发的最优子策略的效益值记作 $f_k(s_k)$ ，于是有
$f_k(s_k) = opt\ V_{k,n}$
式中 $opt$ 表示最优化，根据效益值的具体含义可以是求最大 $(max)$ 或最小 $(min)$ 。