概述

动态规划在运筹学中是一种用于解决多阶段决策过程最优化问题的方法。它通过将问题分解为一系列相互关联的决策阶段，并在每个阶段做出最优决策，最终达到全局优化的目的。动态规划特别适合处理具有「最优子结构」和「重复子问题」性质的运筹学问题。

动态规划在现代管理中主要用于解决以下类型的问题：

库存管理：确定最佳订货策略以最小化总成本（包括持有成本、订货成本和缺货成本）。
生产计划：优化生产和库存水平以满足需求，并同时最小化生产和存储成本。
项目调度：在多个项目或任务之间进行资源分配，以最小化总工期或总成本。
路径优化：解决最短路径或最低成本路径问题，如交通网络中的路径规划。
资源分配：在有限资源约束下进行最优分配，以最大化利润或效用。
投资组合优化：在给定风险约束下选择投资组合，以最大化回报

基本概念与原理

基本概念

1. 阶段

动态规划将决策问题视为一个多阶段过程，每个阶段都需要做出一个决策。这些决策按照时间顺序或逻辑顺序排列，前一阶段的决策会影响后续阶段的状态和可选决策。

数学表示：设 $k$ 表示阶段变量。

示例：一个企业在未来5年内每年都需要决定生产多少产品，每年的决策构成一个阶段。

2. 状态（State）

状态是对系统在某一阶段所处情况的完整描述。状态变量需要包含足够的信息，使得未来的决策不依赖于到达该状态的历史路径，这被称为无后效性或马尔可夫性质。

数学表示：设 $s_{k}$ 表示第 $k$ 阶段的状态，$S_{k}$为状态集合。

示例：在库存管理中，状态可以是当前时刻的库存水平。

3. 决策（Decision）

在某一状态下可以采取的行动。每个阶段的决策集合可能依赖于当前状态。

数学表示：设 $u_k(s_k)$ 或者 $d_k$表示第 $k$ 阶段的决策，$D_k(s_k)$ 表示状态 $s_k$ 下的可行决策集合。

示例：在库存管理中，决策是订货量。

4. 策略（Policy）

策略是一个决策规则的集合，它规定了在每个阶段、每个状态下应该采取什么决策。

数学表示：$\pi = \{d_1, d_2, \dots, d_n\}$

5. 状态转移（State Transition）

描述系统如何从一个状态转移到下一个状态，转移通常由当前状态和决策共同决定。

数学表示：$s_{k+1} = T_k(s_k, d_k)$
其中 $T_k$ 是状态转移函数。

6. 指标函数

每个阶段的决策会产生相应的收益或成本，这通常是状态和决策的函数。

数学表示：

阶段指标函数：$v_k(s_k, d_k)$表示在状态 $s_k$ 下采取决策 $d_k$ 的即时收益或成本。
过程指标函数：$V_k(s_k, d_k,d_k+1,d_k+2,\cdots,d_n)$从阶段$k$的状态$s_k$开始选择决策直到终点 $n$的累计总收益
最优值函数：$f_k(s_k)$过程指标函数的最优值

基本原理

1. 最优性原理（Bellman's Principle of Optimality）

贝尔曼最优性原理是动态规划的理论基础：

"一个最优策略具有这样的性质：无论初始状态和初始决策如何，对于由初始决策所形成的状态而言，其后续决策必须构成最优策略。"

换句话说，最优策略的任何子策略也必须是最优的。

这一原理使得我们可以从问题的末端开始，逐步向前推导出每个阶段的最优决策。

2. 贝尔曼方程（Bellman Equation）

贝尔曼方程是动态规划的数学核心，它描述了最优值函数的递推关系。

基本形式：

$f_k(s_k)$ 表示从第 $k$ 阶段状态 $s_k$ 出发到终点所能获得的最优值，则

\begin{cases}
f_k(s_k) = \mathop{opt}\limits_{d_k\in D_k(s_k)}\Bigl[v_k(s_k,d_k) + f_{k+1}(s_{k+1})\Bigr], & k=n,n{-}1,\dots,1; \\[6pt]
f_{n+1}(s_{n+1}) = 0.
\end{cases}

其中 $\text{opt}$ 根据题意取 $\min$ 或 $\max$，$v_{k}(s_{k},d_{k})$ 为状态 $s_{k}$、决策 $d_{k}$ 时对应的第 $k$ 阶段指标函数值。

模型建立与求解

模型建立

在运筹学中，建立动态规划模型需要满足一系列基本要求和条件。基本要求如下：

问题可分解为多个阶段
每个阶段都有状态变量
每个阶段都有决策变量

其中最关键的地方在于如何识别问题的多阶段性，准确地将问题按照时间顺序或空间顺序划分为若干个相互关联的决策阶段。然后根据这三个基础条件推导出问题的状态转移方程和指标函数。并且问题成立的前提条件是满足最优性原理并具有无后效性（未来的状态只依赖于当前状态和当前决策，与到达当前状态的历史路径无关）

具体步骤

让我们以经典的最短路径问题为例，详细介绍建立动态规划模型的步骤。（例题选自：《运筹学教程》第 5 版，例 1，第 186 页）

一、划分阶段

根据网络图的层次结构，将问题划分为5个阶段，$k=1,2,3,4,5$

二、确定状态变量

状态变量 $s_k$ 表示在第k阶段所处的节点位置。

各阶段的状态集合：

\begin{aligned}
s_1 &= \{A\} \\[4pt]
s_2 &= \{B_1,\, B_2\} \\[4pt]
s_3 &= \{C_1,\, C_2,\, C_3,\, C_4\} \\[4pt]
s_4 &= \{D_1,\, D_2,\, D_3\} \\[4pt]
s_5 &= \{E_1,\, E_2\} \\[4pt]
s_6 &= \{F\}
\end{aligned}

三、确定决策变量

决策变量 $d_k$ 表示在第k阶段选择前往的下一个节点。

允许决策集合（取决于当前状态）：

从状态 $s_k$ 出发的可行决策集合 $D_k(s_k)$ 是该节点能够直接到达的下一层节点集合。

示例：

\begin{aligned}
s_2=B_1 &\implies D_2(B_1)=\{C_1,\,C_2\},\\[4pt]
s_2=B_2 &\implies D_2(B_2)=\{C_2,\,C_3,\,C_4\},\\[4pt]
s_3=C_2 &\implies D_3(C_2)=\{D_1,\,D_2\}.
\end{aligned}

四、建立状态转移方程

状态转移非常直观：$s_k+1=d_k$

说明：对于最短路径问题，状态转移的核心在于“选择下一个节点”，这种选择是基于边的权重（距离）的计算，而不是状态本身的数值变化。

五、定义阶段指标函数

阶段指标函数表示从状态 $s_k$ 到决策目标 $d_k$ 的距离,其中 $\mathrm{dist}(s_k,d_k)$ 是连接两节点的边的长度。

数学表示：$v_k(s_k, d_k) = \mathrm{dist}(s_k, d_k)$

六、定义最优值函数

最优值函数是从起点A到终点F的最短总距离。

数学表示：$f_k(s_k)$

七、建立递推方程（贝尔曼方程）

设$f_k(s_k)$表示从状态 $s_k$ 出发到达终点F的最短距离。

\begin{cases}
f_k(s_k) = \displaystyle \min_{d_k\in D_k(s_k)}\Bigl[v_k(s_k,d_k) + f_{k+1}(s_{k+1})\Bigr], & k=5,4,3,2,1; \\[6pt]
f_{6}(s_{6}) = 0.
\end{cases}

求解方法

顺推法和逆推法是动态规划求解的两大基本方法，在计算方向、递推方程和适用场景等方面有很大区别。

逆推法

我们接着以最短路径问题讲解逆推法。

$k=5$时，$E→F$:

状态$E_1$：$f_5(E_1) = v_5(E_1,F) + f_6(F) = 4 + 0 = 4$

最优决策：$d_5^*(E_1) = F$

状态$E_2$：$f_5(E_2) = v_5(E_2,F) + f_6(F) = 3 + 0 = 3$

最优决策：$d_5^*(E_2) = F$

$k=4$时，$D→E$:

状态$D_1$：$$f_4(D_1) = \min
\left\{\begin{aligned}
d(D_1, E_1) + f_5(E_1)\\
d(D_1, E_2) + f_5(E_2)
\end{aligned}\right\}
=\min
\left\{\begin{aligned}
3 + 4 \\
5 + 3
\end{aligned}\right\}
= 7 \quad D_1→E_1→F$$

最优决策：$d_4^*(D_1) = E_1$

状态$D_2$：

$$f_4(D_2) = \min
\left\{\begin{aligned}
d(D_2, E_1) + f_5(E_1) \\
d(D_2, E_2) + f_5(E_2)
\end{aligned}\right\}
=\min
\left\{\begin{aligned}
6 + 4 \\
2 + 3
\end{aligned}\right\}
= 5 \quad D_2→E_2→F$$

最优决策：$d_4^*(D_2) = E_2$

状态$D_3$：

$$f_4(D_3) = v_4(D_3,E_2) + f_5(E_2) = 3 + 3 = 6 \quad D_3→E_2→F$$

最优决策：$d_4^*(D_3) = E_2$

$k=3$时，$C→D$:

状态$C_1$：

$$f_3(C_1) = v_4(C_1,D_1) + f_5(D_1) = 8 + 7 = 15 \quad C_1→D_1→E_1→F$$

最优决策：$d_3^*(C_1) = D_1$

状态 $C_2$：

$$f_3(C_2) = \min
\left\{\begin{aligned}
&d(C_2, D_1) + f_4(D_1)\\
&d(C_2, D_2) + f_4(D_2)
\end{aligned}\right\}
= \min
\left\{\begin{aligned}
&4 + 7\\
&5 + 5
\end{aligned}\right\}
= 10 \quad C_2→D_2→E_2→F$$

最优决策：$d_3^*(C_2) = D_2$

状态 $C_3$：

$$f_3(C_3) = \min
\left\{\begin{aligned}
&d(C_3, D_2) + f_4(D_2)\\
&d(C_3, D_3) + f_4(D_3)
\end{aligned}\right\}
= \min
\left\{\begin{aligned}
&3 + 5\\
&4 + 6
\end{aligned}\right\}
= 8 \quad C_3→D_2→E_2→F$$

最优决策：$d_3^*(C_3) = D_2$

状态 $C_4$：

$$f_3(C_4) = d(C_4, D_3) + f_4(D_3) = 4 + 6 = 10 \quad C_4→D_3→E_2→F$$

最优决策：$d_3^*(C_4) = D_3$

$k=2$时，$B→C$:

状态 $B_1$：

$$f_2(B_1) = \min
\left\{\begin{aligned}
&d(B_1, C_1) + f_3(C_1)\\
&d(B_1, C_2) + f_3(C_2)
\end{aligned}\right\}
= \min
\left\{\begin{aligned}
&2 + 15\\
&3 + 10
\end{aligned}\right\}
= 13 \quad B_1→C_2→D_2→E_2→F$$

最优决策：$d_2^*(B_1) = C_2$

状态 $B_2$：

$$f_2(B_2) = \min
\left\{\begin{aligned}
&d(B_2, C_2) + f_3(C_2)\\
&d(B_2, C_3) + f_3(C_3)\\
&d(B_2, C_4) + f_3(C_4)
\end{aligned}\right\}
= \min
\left\{\begin{aligned}
&6 + 10\\
&7 + 8\\
&7 + 10
\end{aligned}\right\}
= 15 \quad B_2→C_3→D_2→E_2→F$$

最优决策：$d_2^*(B_2) = C_3$

$k=1$时，$A→B$:

状态 $A$：

$$f_1(A) = \min
\left\{\begin{aligned}
&d(A, B_1) + f_2(B_1)\\
&d(A, B_2) + f_2(B_2)
\end{aligned}\right\}
= \min
\left\{\begin{aligned}
&4 + 13\\
&5 + 15
\end{aligned}\right\}
= 17 \quad A→B_1→C_2→D_2→E_2→F$$

最优决策：$d_1^*(A) = B_1$

所以从A到F的最短距离为：17，最优路线为$A→B_1→C_2→D_2→E_2→F$

顺推法

我们以投资决策问题为例来讲解顺推法（例题同样选自《运筹学教程》）

阶段划分：按投资决策过程划分为3个阶段$k=1,2,3,$，$k=0$表示初始状态，还未决策任何项目

状态变量$s_k$：表示前k个项目决策后的剩余可用资金，例：

$s_0=10:\quad\text{初始资金}$
$s_1=10-x_1:\quad\text{决策项目1后的剩余资金}$

决策变量$x_k$表示在第k阶段对项目k的投资额。

决策约束：$0≤x_k≤s_k−1$（投资额不能超过当前剩余资金）

状态转移方程：$s_k=s_{k-1}−x_k$（当前剩余资金 = 上一阶段剩余资金 - 当前投资额）

阶段指标函数$v_k(s_k, x_k)$：投资第 k 个项目所获得的直接收益，因为收益函数与 $s_k $无关,令$g_k(x_k)=g_k(s_{k-1}-s_k)=v_k(s_k,x_k)$

$$g_k(s_{k-1}, s_k) =
\begin{cases}
4(s_0 - s_1), & k=1 \\
9(s_1 - s_2), & k=2 \\
2(s_2 - s_3)^2, & k=3
\end{cases}$$

最优值函数 $f_k(s_k)$ 表示：前k个项目决策完毕，剩余资金为 $s_k$ 时，已经获得的最大累积收益

递推方程（正向递推）：

\begin{cases}
f_k(s_k) = \displaystyle \max_{0 \le s_k \le s_{k-1}}\Bigl[f_{k-1}(s_{k-1})+g_k(s_{k-1}-s_k)\Bigr], & k=3,2,1; \\[6pt]
f_{0}(s_{0}) = 0.
\end{cases}

$k=1$时，决策项目1:

$$f_1(s_1) = \displaystyle \max_{0 \le s_1 \le s_{0}}\Bigl[f_{0}(s_{0})+g_k(s_{0}-s_1)\Bigr]=0+4(10−s_1)=40−4s_1$$

最优决策：$s_1^* = 0$

$k=2$时，决策项目2:

\begin{aligned}
f_2(s_2)
&=\max_{0 \le s_2 \le s_{1}}\bigl\{f_1(s_1)+g_2(s_1-s_2)\bigr\}\\[4pt]
&=\max_{0 \le s_2 \le s_{1}}\bigl\{(40-4s_1)+9(s_1-s_2)\bigr\}\\[4pt]
&=\max_{0 \le s_2 \le s_{1}}\{40+5s_1-9s_2\}
\end{aligned}

最优决策：$s_1^* = 10$

$k=3$时，决策项目3:

最终阶段，必须用完所有资金，即 $s_3=0$。

\begin{aligned}
f_3(0)
&=\max_{0 \le s_2 \le 10}\bigl\{f_2(s_2)+g_3(s_2)\bigr\}\\[4pt]
&=\max_{0 \le s_2 \le 10}\bigl\{(90-9s_2)+2s_2^{2}\bigr\}\\[4pt]
&=\max_{0 \le s_2 \le 10}\{2s_2^{2}-9s_2+90\}
\end{aligned}

求最优解：

令$h(s_2)=2s_2^2-9s_2+90$

求导：$\quad h'(s_2)=4s_2-9$

令 $h'(s_2)=0\;\Rightarrow\;s_2=2.25$

二阶导数：$\quad h''(s_2)=4>0$，所以$s_2=2.25$ 为极小值点

由于 $h(s_2)$ 是开口向上的抛物线，在约束 [0,10] 内：

在 $s_2=2.25$ 处取得最小值
在边界处取得最大值

比较边界值：

$h(0)=90$
$h(10)=2(100)−90+90=200$

最优决策：$s_2^* = 10$

由状态方程回溯最优决策：

$s_2^* = 10$

$x_3^* = s_2^* - s_3 = 10 - 0 = 10$
$x_2^* = s_1^* - s_2^* = 10 - 10 = 0$
$x_1^* = s_0 - s_1^* = 10 - 10 = 0$

最优投资策略：

$x_1^*=0,\quad x_2^*=0,\quad x_3^*=10$

最大总收益：

$z_{\max}=4(0)+9(0)+2(10)^2=200$

方法对比

对比维度	顺推法（Forward DP）	逆推法（Backward DP）
1. 计算方向	从「初始阶段」→「终端阶段」 $k = 1 \to N$	从「终端阶段」→「初始阶段」 $k = N \to 1$
2. 状态含义	$f_k(s)=$ 从起点到第 k 阶段状态 s 的最优累计值	$f_k(s)=$ 从第 k 阶段状态 s 到终点的最优累计值
3. 转移方程	「前驱 → 当前」 $f_k(s_k) =$ $\mathrm{opt}\{v_{k}(s_k,d_k)+f_{k-1}(s_{k-1})\}$	「当前 → 后继」 $f_k(s_k) =$ $\mathrm{opt}\{ v_{k}(s_k,d_k)+f_{k+1}(s_{k+1})\}$
4. 边界位置	初始状态已知 $f_0(s_0) = 0$ 或给定	终端状态已知 $f_{n+1}(s_{n+1}) = 0$ 或给定
5. 适用场景	1. 起点唯一、终点多元 2. 累计约束（背包、资源消耗）	1. 终点唯一、起点多元 2. 剩余约束（库存、残值）
6. 经典例题	0-1 背包、数字三角形最大和、最长公共子序列	最短路径、设备更新、库存管理、马尔可夫决策过程