运筹学第七章：动态规划.pdf

动态规划是一种在运筹学中广泛使用的优化技术，尤其适用于解决涉及多个阶段决策的问题。这一章主要讨论了离散确定型的动态规划模型，这是最基础的形式，但其核心思想和原则同样适用于其他类型的动态规划问题。 理解动态规划的关键在于掌握多阶段决策过程的最优化。在这样的过程中，每一阶段都需要作出决策，并且这些决策之间相互关联，影响着最终的整体效果。动态规划的核心在于，每个阶段的决策不仅要考虑本阶段的最优，还要考虑到对全局目标的影响。这种随时间发展而决定各时段决策的方法，即为“动态”的含义。 动态规划包含五个基本概念： 1. 阶段：问题被划分为一系列互相联系的时间或空间阶段。 2. 状态：每个阶段开始时的条件，由状态变量（如sk）表示，状态集合（Sk）定义了所有可能的状态。 3. 决策和策略：在给定状态下作出的决定（uk），决策变量受到允许决策集合（Dk(sk)）的约束。 4. 状态转移方程：描述如何从一个阶段的状态（sk）通过决策（uk）转移到下一个阶段的状态（sk+1）。 5. 指标函数：衡量策略优劣的量，包括阶段指标函数（d(sk, uk)）和过程指标函数（Vk,n(sk, pk,n)），最优指标函数（fk(sk)）表示从特定状态采用最优策略至过程结束的最佳效益。 动态规划的基本思想是将问题分解为子问题，从边界条件开始，逆向或顺向递推求解。每个子问题的最优解依赖于前一个子问题的最优解，最后得到的整体最优解就是原问题的最优解。动态规划的基本方程是一个递推公式，用于找到从当前阶段到后续阶段的最优决策。 例如，假设有一个背包问题，我们需要在有限的背包容量下，从一组物品中选择最有价值的组合。动态规划可以创建一个表格，每一行代表一个阶段（物品的选择），每一列代表背包的容量，表格中的每个单元格存储的是在当前容量下能获得的最大价值。通过比较放入和不放入当前物品两种情况下的最大价值，我们可以填满这个表格，最后得到的就是背包问题的最优解。 动态规划提供了一种系统性的方法来解决多阶段决策问题，通过将问题分解为阶段，定义状态、决策和目标函数，然后利用递推公式寻找最优解。这种方法在诸如资源分配、路径规划、库存管理、生产计划等领域都有广泛应用。