一罐可乐

1. 多阶段决策过程#

在许多实际问题中，整个决策过程可以被恰当地划分为若干个相互联系、前后衔接的阶段。在每个阶段都需要作出决策，当前的决策不仅依赖于当前所处的状况，还会直接影响下一个阶段的发展，进而决定了整个过程的活动路线。这种把问题看作一个前后关联、具有链状结构的多阶段决策过程，称为序贯决策过程。

2. 最短路径问题示例#

• 问题描述：求从起点 $A$ 经由中间各节点（如 $B_i, C_i, D_i$ 等）到终点 $E$（或 $G$）的最短路径。
• 求解思想：直接穷举所有路径的计算量非常大。动态规划将此问题转化为多个性质相同但规模较小的子问题：即从各阶段节点到终点的最短路径。
• 逆序递推（Backward Induction）：从终点 $E$ 开始，倒退计算第四阶段（$D_i \rightarrow E$）、第三阶段（$C_i \rightarrow D \rightarrow E$）、第二阶段（$B_i \rightarrow C \rightarrow E$）和第一阶段（$A \rightarrow B \rightarrow E$），利用已算出的子路程最优值，仅进行少量加法和比较，即可得出全局最短路径。

1. 阶段（Stage）#

描述过程所处的步骤或阶段。常用阶段变量 $k$ ($k=1,2,\dots,n$) 表示。阶段的划分通常根据时间、空间或逻辑演变特征确定。

2. 状态与状态变量（State）#

表示每个阶段开始时所处的自然状况或客观条件。用 $s_k$ 表示第 $k$ 阶段的可达状态变量，$S_k$ 表示第 $k$ 阶段的所有可达状态的集合。

• 无后效性（马尔可夫性, Markov Property）：状态必须具备该特征，即“未来的状态只取决于当前的状态和当前的决策，而与过去是如何到达这一状态的历史无关”。当前状态是过去历史的完整总结。

3. 决策与决策变量（Decision）#

表示在第 $k$ 阶段当过程处于状态 $s_k$ 时，决策者可以作出的不同选择（决定）。决策变量用 $u_k(s_k)$ 或 $x_k$ 表示。允许决策的集合用 $D_k(s_k)$ 表示，有 $u_k(s_k) \in D_k(s_k)$。

4. 状态转移方程（State Transition Equation）#

描述过程由第 $k$ 阶段的状态 $s_k$ 经过决策 $u_k$ 后，向第 $k+1$ 阶段的状态 $s_{k+1}$ 演变的物理或逻辑规律： $s_{k+1} = T_k(s_k, u_k)$ 其中 $T_k$ 称为状态转移函数。

5. 指标函数与最优值函数（Value Function）#

• 指标函数：用来衡量全过程或某后部子过程效果好坏的数值指标（如总路程、总利润）。用 $V_{k,n}$ 表示从第 $k$ 阶段到第 $n$ 阶段子过程的指标。指标函数必须具有可分离性并满足递推关系： $V_{k,n}(s_k, u_k, \dots, u_n) = v_k(s_k, u_k) * V_{k+1,n}(s_{k+1}, u_{k+1}, \dots, u_n)$ （其中 $*$ 通常为加法或乘法）。
• 最优值函数：从第 $k$ 阶段的状态 $s_k$ 开始，到过程终结所能获得的最佳（极大或极小）指标值，记为 $f_k(s_k)$： $f_k(s_k) = \text{opt}_{u_k, \dots, u_n} \{ V_{k,n} \}$

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

由理查德·贝尔曼（Richard Bellman）于 1953 年提出：

“作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，对前面决策所形成的状态而言，余下的诸决策必须构成最优策略。” 简言之，最优策略的任何子策略也必须是对应子问题的最优策略。（可用反证法予以证明）。

2. 动态规划基本方程（递推方程）#

设指标函数为各阶段指标之和（如累积距离/成本）：

案例 1：乘积极大化问题#

• 问题描述：将正数 $c$ 分割为三个非负数 $x_1, x_2, x_3$之和，使它们的乘积最大： $\max \prod_{i=1}^3 x_i \quad \text{s.t. } \sum_{i=1}^3 x_i = c, \ x_i \ge 0$
• 逆推建模：
  • 阶段：设为 3 个阶段 ($k=1, 2, 3$)。
  • 状态变量：$s_k$ 表示分配给第 $k$ 阶段到第 3 阶段的可用资金余额。
    • 初始状态 $s_1 = c$。
    • 状态转移方程：$s_{k+1} = s_k - x_k$。
  • 决策变量：$x_k \in [0, s_k]$。
  • 基本方程： $f_k(s_k) = \max_{0 \le x_k \le s_k} \{ x_k \cdot f_{k+1}(s_k - x_k) \}$ 边界条件：$f_4(s_4) = 1$。
• 递推求解：
  1. 第 3 阶段： $f_3(s_3) = \max_{0 \le x_3 \le s_3} \{ x_3 \} = s_3 \quad (\text{此时最优决策 } x_3^* = s_3)$
  2. 第 2 阶段： $f_2(s_2) = \max_{0 \le x_2 \le s_2} \{ x_2 \cdot f_3(s_2 - x_2) \} = \max_{0 \le x_2 \le s_2} \{ x_2 (s_2 - x_2) \}$ 对 $x_2$ 求导并令导数为 0：$s_2 - 2x_2 = 0 \implies x_2^* = \frac{s_2}{2}$。 代回得：$f_2(s_2) = \left(\frac{s_2}{2}\right)^2$。
  3. 第 1 阶段： $f_1(s_1) = \max_{0 \le x_1 \le s_1} \{ x_1 \cdot f_2(s_1 - x_1) \} = \max_{0 \le x_1 \le s_1} \left\{ x_1 \left(\frac{s_1 - x_1}{2}\right)^2 \right\}$ 令目标函数对 $x_1$ 的一阶导数为 0，求极值点： $\frac{1}{4} (s_1 - x_1)(s_1 - 3x_1) = 0 \implies x_1^* = \frac{s_1}{3} \quad (\text{因 } x_1 < s_1)$ 由于初始状态 $s_1 = c$，得： $x_1^* = \frac{c}{3} \implies s_2 = \frac{2c}{3} \implies x_2^* = \frac{c}{3} \implies s_3 = \frac{c}{3} \implies x_3^* = \frac{c}{3}$
  • 结论：当 $x_1 = x_2 = x_3 = \frac{c}{3}$ 时取得极大值，最大乘积为 $\left(\frac{c}{3}\right)^3$。