第3章 确定性优化四件武器

第3章 · 确定性优化四件武器

本章要回答的三个问题：当数据与约束都确定已知时，四类主力优化模型——线性、整数、非线性、动态——各在什么局面出手？每件兵器的核心机理（单纯形、分支定界、KKT、贝尔曼方程）是什么？它们的适用边界与常见失效方式是什么？本章是运筹学战线的主攻章。

为什么会有这一章

第 2 章末尾的侦察术把问题分成了四类地形：连续凸、连续非凸、离散、多阶段。现实里这四类地形对应四件武器，而多数教材按数学流派分章，导致学生学完仍不知道"拿到问题先摸哪件兵器"。本章按出鞘顺序讲解：线性规划是基座（绝大多数资源的分配问题最终都化归为它）；整数规划处理不可细分的决策；非线性规划对付带曲线目标或约束的局面；动态规划处理"决策影响后续局面"的多阶段问题——它同时是通往第 8 章强化学习的桥。

四件武器共用第 2 章的四要素翻译法，所以本章每节都直接从一个完整战例进入，不再重复建模规范。

读完能解决什么

• 面对确定性决策问题，能选出正确的模型类别并说明理由；
• 会用 SciPy 求解四类模型，读懂求解器日志里的对偶价格、分支数、KKT 残差；
• 理解对偶理论、分支定界、KKT 条件、贝尔曼方程四个核心机理的直觉版本。

各节怎么分工

本章知识点清单

• 标准形、基可行解与顶点的关系；单纯形法沿顶点移动的机理；
• 对偶问题的经济解读：影子价格与互补松弛；
• 分支定界的搜索树、界剪枝逻辑、间隙（gap）的含义；
• KKT 三条件（平稳性、原始可行、对偶可行）各自查什么；
• 最优性原理与状态、阶段、转移、值函数四要素；
• 模型选型速查：按变量类型与目标形状分流。

四件兵器的地形适配

四件兵器一句话：线性打直、整数打格、非线性打弯、动态打段。

四件兵器的配合与误用

四件兵器并非各自为战，实战中它们经常接力。一个典型的供应链项目里，月度产能分配用线性规划（快、可解释、影子价格直接支撑采购谈判），季度产线开闭决策叠在整数规划上（开关是 0-1 变量），反应装置的操作点用非线性规划精调（收率曲线是真实的物理曲线），跨期的库存联动则交给动态规划（本月的备货改变下月的库存状态）。误用同样常见：用非线性求解器解线性问题（白白承受局部最优的风险与更慢的速度）、用动态规划硬扛高维状态（维数灾难面前查表法寸步难行）、在整数规划里追求零间隙（大规模实例上等到天荒地老也不收敛）。本章四节各配一个"何时收手"的提醒，读的时候请把它们当成与算法同样重要的知识点。

先决条件

• 第 2 章四要素翻译法与凸性、复杂性两门侦察术；
• 矩阵乘法与求导法则；3.3 需要梯度概念，3.4 需要递归的直觉。

往下走到哪

本章假设所有数据确定已知。下一章撕开这个假设：需求随机、排队随机、对手随机时，沙盘本身就是晃动的，需要第 4 章的随机规划、排队论与库存论来稳住局面。