欢迎来到线性规划 (Linear Programming)!
在决策数学 1 (Decision Mathematics 1) 的这一章中，我们将探索现代数学中最有力的工具之一。线性规划 (Linear Programming, LP) 的核心在于“最优化”——即在各种限制条件下，找出解决问题的最佳方案。无论是工厂如何在有限资源下实现利润最大化，还是物流公司如何将燃料成本降至最低，线性规划都是背后的关键技术。
如果刚开始觉得有些抽象，别担心。我们基本上是在做这件事：将现实世界的问题转化为代数表达式，然后使用固定的步骤（算法）来找出完美答案。让我们开始吧！
1. 问题建模 (Formulation)
在解决问题之前，我们必须先将其从文字“翻译”成数学语言。这个过程称为建模 (Formulation)。
线性规划问题的要素
1. 决策变量 (Decision Variables)：这是你可以控制的部分，通常用 \(x, y, z\) 等表示。例如，\(x = \) 生产蛋糕的数量。
2. 目标函数 (Objective Function)：这是你的目标。通常以“最大化 (Maximise)”（针对利润/产量）或“最小化 (Minimise)”（针对成本/时间）开头。例如：\(P = 5x + 3y\)。
3. 限制条件 (Constraints)：这是你的限制因素（如原材料、时间、资金）。通常以不等式表示，例如 \(2x + y \le 10\)。
4. 非负限制 (Non-negativity Constraint)：这是一个微小但至关重要的点！在现实中，你不可能生产 -5 个蛋糕。因此，我们必须加上 \(x, y \ge 0\)。
松弛变量、剩余变量与人工变量
为了在后续使用高级算法，我们需要将不等式（如 \(\le\)）转化为等式（如 \(=\)）。我们通过加入特殊的变量来达成：
松弛变量 (Slack Variables, \(s\))：用于 \(\le\) 的限制条件。可以将 "Slack" 想象成“剩余”的资源。如果你有 10kg 面粉但只用了 8kg，那么松弛变量就是 2kg。
例子： \(3x + 2y \le 20\) 变为 \(3x + 2y + s_1 = 20\)。
剩余变量 (Surplus Variables, \(s\))：用于 \(\ge\) 的限制条件。这是指超过最低要求的那部分“额外”数量。
例子： \(x + y \ge 5\) 变为 \(x + y - s_2 = 5\)。但等等！如果 \(x\) 和 \(y\) 为 0，那么 \(-s_2 = 5\)，这意味着 \(s_2 = -5\)。在我们的算法中变量不能为负！这就引出了……
人工变量 (Artificial Variables, \(a\) 或 \(t\))：这些是“数学占位符”，添加到 \(\ge\) 或 \(=$ 的限制条件中，为算法提供一个有效的起点。它们没有现实意义，且必须在计算结束前被消除。
\n例子： \(x + y \ge 5\) 变为 \(x + y - s_2 + t_1 = 5\)。
快速回顾：
- 松弛 (Slack)：为 \(\le\) 加入“未使用的”资源（使用 \(+\) 号）。
- 剩余 (Surplus)：为 \(\ge\) 减去“多余的”资源（使用 \(-\) 号）。
- 人工 (Artificial)：为 \(\ge\) 或 \(=\) 引入一个“虚假”变量（使用 \(+\) 号）以帮助算法启动。
2. 图解法 (Graphical Method)
如果我们只有两个变量（\(x\) 和 \(y\)），我们可以在图表上绘制问题。这是可视化问题的好方法。
步骤详解
1. 绘制限制条件：将不等式视为等式（直线）并画出。
2. 找到可行域 (Feasible Region, FR)：这是图上满足所有限制条件的区域。为了保持清晰，建议涂掉那些不允许的区域（被排除的区域），剩下的就是可行域。
3. 确定最优点：最佳答案一定会出现在可行域的角点（顶点）上。
如何找到“最佳”角点？
有两种方法：
- 顶点法 (Vertex Method)：计算可行域每个角点的坐标，并将其代入你的目标函数。数值最大（或最小）的那个点就是赢家！
- 目标直线法 (Objective Line Method / Ruler Method)：画出一条代表目标函数的直线（例如假设 \(5x + 3y = 15\)）。将尺子放在这条线上，保持斜率不变并平移，直到它碰到可行域中最后一个接触点。该点即为最优解。
常见错误：忘记有些问题要求整数解 (Integer Solutions)。如果最优点是 \(x = 2.7, y = 3.2\)，但你无法卖出 0.7 辆车，你必须检查该点附近的整数坐标，找出可行域内最优的整数结果。
重点总结：最优解总是位于可行域的边界上，通常是在角点！
3. 单纯形法 (Simplex Algorithm)
图解法对于 2D 问题很棒，但如果有 4 个变量呢？你总不能画一个 4D 图表！既然无法绘制，我们就使用单纯形法 (Simplex Algorithm)——这是一种基于表格的逐步迭代方法 (tableau)。
初始表格 (Initial Tableau)
对于只有 \(\le\) 限制条件的最大化问题，我们建立一个表格。所有变量（\(x, y, s_1, s_2\)）放在顶部。最底行是目标行 (Objective Row)。
技巧：当把目标函数 \(P = 14x + 12y\) 写入表格时，要将其改写为 \(P - 14x - 12y = 0\)。这就是为什么底部一行的数值通常以负数开始的原因！
迭代过程
1. 选择主元列 (Pivot Column)：观察目标行，选择最负的数值。这代表该变量能最快增加你的利润。
2. 比值检验 (Ratio Test，确定主元行)：对于每一行，将“数值 (Value)”列除以你所在主元列的数字。忽略零或负数结果。得到最小正比值的那一行就是你的主元行。
3. 主元运算 (Pivot)：使用行运算将主元（行列交点处的数字）变为 1，并该列中其他所有数字变为 0。
4. 重复：持续此过程，直到目标行中没有负数为止。如果没有负数，你就找到了最大值！
你知道吗？ 单纯形算法是在二战期间开发的，至今仍被航空公司用于安排航班和机组人员排班！
4. 高级方法：两阶段法与 Big-M 法
标准的单纯形法只有在原点 (\(x=0, y=0\)) 是有效起点时才适用。如果我们有 \(\ge\) 限制条件，原点会位于可行域之外。我们需要一个“推动力”进入区域。这就是两阶段法 (Two-Stage) 和 Big-M 法 (Big-M Method) 的用武之地。
Big-M 法
我们在目标函数中为任何人工变量 (\(t\)) 添加一个极大的惩罚项 \(M\)。因为 \(M\) 极大，算法会为了避免这些惩罚而极力将 \(t\) 变为 0。一旦所有人工变量都为零，你就进入了可行域，剩下的部分按正常的单纯形法运算即可。
两阶段法 (Two-Stage Method)
顾名思义，分两个阶段进行：
- 阶段 1：建立一个临时的目标函数：最小化所有人工变量的总和。我们的目标是让这个总和变为 0。
- 阶段 2：一旦总和为 0（意味着所有人工变量已消除），抛弃阶段 1 的目标函数和人工变量列。然后使用得到的结果表格来求解原始的目标函数。
记忆法：
- Big-M：使用“惩罚项”(\(M\)) 来把人工变量“吓跑”。
- 两阶段：使用“小游戏”（阶段 1）在玩“主游戏”（阶段 2）之前先把人工变量删除。
总结检核清单
- 建模：我有没有加入非负限制 (\(x, y \ge 0\))？
- 松弛/剩余：\(\le\) 是否用了 \(+s\)，\(\ge\) 是否用了 \(-s + t\)？
- 图解法：我有没有涂掉不想要的区域？是否检查了是否需要整数解？
- 单纯形法：主元列是否为目标行中最负的数？主元行是否为最小的正比值？
- 停止条件：对于最大化问题，当目标行中没有负数时，我就停止。
如果单纯形法的行运算让你觉得乏味，别担心！这只是 bookkeeping（簿记工作）。慢慢来，仔细检查减法，你一定能找到最优路径！