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

第七章 动态规划研究

（一）缺乏统一的标准模型和通用的建模方法
甚至缺少评估某个问题是否适合构建动态规划模型的指导原则。因此，针对

不同问题，通常需要进行个案分析，并建立专门的模型。尤其对于复杂问题，在
定义状态、做出决策以及确立状态转换规则时，往往需要高度的创造性和灵活性，
这在一定程度上限制了其应用范围。
（二）采用数值方法求解时会遇到所谓的“维度灾难”

如果一个状态变量有一百种的取值，那么对于一个 n 维的问题，状态空间的
大小将是这一百种取值的 n 次方。这意味着，随着维度的增加，需要计算和存储
n
的状态 xk 数量为 m 呈指数级增长。对于实际问题中稍大一点的 n 值，这种计算
量和存储需求通常是无法接受的。尚未找到一种广泛适用且有效的方法来彻底解
决这一挑战。

第五节 典型问题模型与求解

一、最短路线问题

在处理如最短路径问题这类案例时，可以将整个过程划分为多个阶段，每

个阶段的状态依据起始位置来定义，而决策则涉及从每个状态出发的选择方向。
具体而言，每个阶段的性能度量有 个可以通过相邻两个状态之间的

距离（或成本） 来表达，而最优值函数 则代表了从
阶段 k 到最终目标点的最短路径长度（或最低成本）。通过对各阶段的逐步优化，
可以实现整体路径的最优化，基本方程为

利用这个模型可以计算出例 l 的最短路线是 AB1C2D1E2F2G ，相应的最短
距离为 18 km。

二、生产计划问题

对于例 2 一类生产计划问题，阶段按计划时间自然划分，状态定义为每阶段
开始时的储存量 xk ，决策为每个阶段的产量 uk ，记每个阶段的需求量（已知量）

185