运筹学 — rin.contact

数据科学的大部分都在预测将会发生什么。运筹学（OR）回答一个不同、更可付诸行动的问题：在资源有限、约束刚性的前提下，我们该做什么？你如何分配预算、安排人员、规划配送路线、或调配产品组合，以取得尽可能好的结果？运筹学正是把这些决策化为数学并最优地求解的学科。

它是微积分与优化那个面向应用、面向决策的表亲：同样以找到一个最优点为目标，但如今行动空间被现实世界的限制所约束，而答案是一个你能执行的计划。本页从表述到求解，构建其核心引擎——线性规划。

更好决策的科学

运筹学脱胎于第二次世界大战，那时数学家被要求把稀缺资源用到最好——船队航线、雷达布点、补给后勤——它由此成为现代物流、排程与规划的骨干。其统一的想法陈述起来很简单：在约束之下最大化（或最小化）一个目标。在预算之下最大化利润；在满足需求之下最小化成本；在车辆容量之下最小化配送时间。

让它强大的，是数量惊人的现实问题都套得进那一个模子。学会认出这种形状——一个你想尽量推远的目标，被你不能违反的规则所围困——你就能把问题交给一个求解器，它会返回可证明为最优的答案。

表述一个问题

运筹学里真正的本事不是求解——求解器会做那个——而是表述：把一个杂乱的现实情境翻译成三个精确的部件。

决策变量——你所控制、正在求解的那些量（产品 A 造多少个，是否开设仓库 B）。
目标函数——你想最大化或最小化的那个单一数字，用变量写出（总利润、总成本）。
约束——解必须遵守的规则，同样用变量表示（可用工时、预算、要满足的需求、非负性）。

把这三个弄对，问题就完全确定了。一位运筹分析师所增添的价值大多在此——选对变量、诚实地捕捉真实的约束，因为一个被漂亮地求解了的错误表述，比毫无用处还糟。

线性规划

当目标与所有约束在决策变量上都是线性的，你便有了一个线性规划（LP）——运筹学中最重要、也最可解的一类。它的标准形式很紧凑：

\begin{aligned} \text{maximise} \quad & \mathbf{c}^{\top}\mathbf{x} \\ \text{subject to} \quad & A\mathbf{x} \le \mathbf{b} \\ & \mathbf{x} \ge \mathbf{0} \end{aligned}

x：决策变量。c：目标的权重。A 与 b：约束。最后一行禁止出现负的量。

直白地读：选择那些量 $\mathbf{x}$ ，让加权总和 $\mathbf{c}^{\top}\mathbf{x}$ 尽可能大，同时每个约束 $A\mathbf{x} \le \mathbf{b}$ 都成立、没有任何量变负。一家工厂在决定两种产品各造多少——每种赚取已知的利润、每种消耗有限的人力与材料——正是这个，也是你脑中要为接下来的几何留着的例子。

线性规划的几何

线性规划有一层优美的视觉含义。每个约束是一条直线，把平面切成允许与不允许的两半。把它们叠起来，满足所有约束的点便构成一个可行域——一个凸多边形（在更高维里是一个多胞形）。里面的每个点都是一个合法的计划；目标是一个你正朝其推进的方向。

关键定理让求解变得可行：最优解总是位于可行域的一个角（顶点）上。直观地说，你沿改善的方向把目标线尽量滑远，它在离开可行域之前触到的最后一个点，就是一个角。所以你不必搜索无穷多的内部点，只需检查那些顶点。

一个二维线性规划。约束界定出一个可行多边形；虚线的目标线沿改善的方向滑动，直到刚好触到可行域——在一个顶点上。那个角就是最优计划。

单纯形的想法

如果最优总在一个角上，算法便自然成形。单纯形法——Dantzig 1947 年的突破，至今仍是主力——从可行域的一个顶点出发，沿着棱走向相邻的顶点，总是移向一个能改善目标的，直到没有相邻的角更好。那最后一个顶点就是全局最优。

它之所以有效，是因为可行域是凸的——所以一个没有更好邻居的角，保证是整体最优的，不会有那些缠扰机器学习一侧非凸问题的局部最小值陷阱。最坏情况下单纯形可能很慢，但实践中它快得惊人，常规地求解带数千个变量的线性规划。

对偶与影子价格

每个线性规划都有一个隐藏的孪生。对偶说，对任何线性规划（「原问题」），都存在一个伙伴问题（「对偶问题」），其最优值恰好相同——而对偶的解携带着无价的管理信息：每个约束的影子价格。

影子价格回答「如果我把这个约束放松一个单位，目标会改善多少？」——多一个工时、或多一块钱预算，实际能买来多少额外利润。这把线性规划从一次性的答案变成一件决策工具：它告诉你哪个约束才是真正的瓶颈、放松它值多少。实践中，影子价格往往比解本身更有价值。

当变量必须是整数

线性规划悄悄地假定你能造出 3.7 个某物。常常你不能——你建 3 座或 4 座工厂，你把一名工人排进某个班次、要么不排，一条路线被用、要么不用。强迫变量取整数，就得到一个整数规划（IP），而它难得多：你不能只是把线性规划的答案四舍五入（舍入可能违反约束、或错过真正的最优），而且问题一般会变成 NP 难。

求解器用巧妙的搜索来对付它——分支定界系统地把问题拆成一个个情形，并用（容易的）线性规划松弛作为界，剪掉那些不可能胜过迄今最优解的分支。那种是/否的版本，变量取 0 或 1，囊括了一大类现实决策（指派、排程、设施选址），这正是为什么尽管代价高昂，整数规划在物流中无处不在。

线性规划之外

线性规划是地基，但运筹学是一整套工具箱。几个出众的成员，全都框定为「在约束之下优化」：

网络流——把问题建模成一张图，让流量穿过它：最短路径、最大流、最小成本运输。其中许多都有特别快的专用算法。
指派与匹配——以最小成本把工人配给任务、或把学生配给项目。（与 AI 页上的约束满足问题同形。）
排程——把作业在时间与机器上排序，以最小化延迟或成本——经典，也经典地难。

它在我工作中的体现

从「是什么」到「该做什么」

运筹学是工具箱中从描述世界走向改变它的那部分。每当真正的问题是约束之下的分配——如何部署一支有限的团队、一笔固定的预算、或稀缺的产能以发挥最大效用——那就是一个优化问题，而非预测问题，去拿一个模型而不是线性规划，是一种范畴错误。它培养的最有用的习惯是影子价格式的思考：在政府工作中，知道哪个约束才是绑住手脚的瓶颈、放松它值多少，正是决策者能据以行动的那种洞见。

它也补全了贯穿这些页面的优化故事：微积分在一个开放曲面上找到最优点，梯度下降走到那里，而运筹学在刚性约束之下做到这点——对同一个根本问题「什么最好？」的三个角度。