Linear programming

欢迎来到线性规划的世界！

在离散数学的这一章中，你将学习如何在资源有限的情况下做出最佳决策。想象你在经营一门生意：你希望最大化利润，但你却只有有限的员工、时间和原材料。这些限制就是所谓的约束条件 (constraints)。

线性规划 (Linear Programming, LP) 是一套强大的数学工具，从航空公司排程到工厂管理，人们都利用它来找到效率最高的“甜蜜点”。别担心，刚开始可能会觉得步骤繁多，我们会将其拆解成简单且合乎逻辑的小单元。

1. 建立模型 (Formulating the Problem) (DD1)

在解题之前，我们必须将问题从文字“翻译”成数学。这个过程称为建模 (formulation)。

每个线性规划问题都有三个主要元素：

1. 决策变量 (Decision Variables)： 这些是你能够控制的事物。我们通常称它们为 \(x\)、\(y\) 或 \(x_1\)、\(x_2\)。（例如：我应该烘焙多少个巧克力蛋糕？多少个香草蛋糕？）

2. 目标函数 (Objective Function)： 这是你的目标。你通常希望最大化某个数值（例如利润）或最小化某个数值（例如成本或浪费）。它的形式如下：\( \text{Maximise } P = 5x + 3y \)。

3. 约束条件 (Constraints)： 这是你必须遵守的规则或限制，通常写成不等式。（例如：你只有 10kg 的面粉，而每个蛋糕都需要一定分量的面粉。）

非负限制 (Non-negativity)： 在现实世界中，你不可能烘焙出 -5 个蛋糕！因此，我们几乎总是会包含约束条件 \(x \ge 0, y \ge 0\)。

快速复习：建模的黄金法则

• 确认需要决策的项目 (变量)。
• 写下你的目标 (目标函数)。
• 列出限制条件 (约束条件)。
• 别忘了 \(x, y \ge 0\)！

2. 图解法 (Graphical Solutions) (DD2)

如果你只有两个变量（\(x\) 和 \(y\)），你可以通过绘图来解题！这是理解问题最直观的方式。

图解法的步骤：

1. 绘制约束条件： 将不等式视为方程（直线）并绘制在图表上。
2. 找出可行区域 (Feasible Region)： 这是图表上满足所有约束条件的区域。通常我们会将“不需要”的区域涂黑，以便留下清晰的“允许”区域。
3. 找出最佳点 (Optimal Point)： 最佳解总是位于可行区域的其中一个顶点 (vertices)（角点）。

如何找出最佳角点？

你可以使用目标线法 (Objective Line Method)（也称为等利润线）：
• 为你的目标函数随意选一个数值，例如 \(5x + 3y = 15\)。
• 在图表上画出这条线。
• 使用直尺平移这条线，使其在可行区域内平行移动。
• 当这条线最后离开可行区域时所触碰的最后一点，就是你的最大值点。

常见错误： 对于 \( \le \) 和 \( \ge \) 要非常小心。如果约束条件是 \(x + y \le 10\)，你需要的范围是直线的下方。如果你涂错了边，你的可行区域就会出错！

3. 单纯形法：基础概念 (The Simplex Algorithm) (DD3)

如果你有 10 个变量怎么办？你没办法画出 10 维的图表！这时候就需要单纯形法 (Simplex Algorithm) 出场了。它是一套逐步执行的“食谱”，从可行区域的一个角点移向更好的角点，直到找到最佳解为止。

松弛变量 (Slack Variables)

单纯形法不喜欢不等式 (\( \le \))，它更偏好方程 (\( = \))。为了修正这点，我们在每个 \( \le \) 约束条件中加入一个松弛变量 (Slack Variable) (\(s\))。
类比： 如果你的预算有 10 英镑，而你花了 7 英镑，那么你的“松弛额”就是 3 英镑。
因此，\(x + y \le 10\) 会变为 \(x + y + s = 10\)，其中 \(s \ge 0\)。

初始单纯形表 (Initial Tableau)

我们将所有方程放入一个表格中，称为单纯形表 (tableau)。表格中的每一行代表一个约束条件。最底下一行通常是目标函数行（或称为 \(P\) 行）。

重要： 当你将目标函数放入表格时，必须将其重新排列使其等于零。
例如：\(P = 5x + 3y\) 变为 \(P - 5x - 3y = 0\)。这就是为什么最底行中的 \(x\) 和 \(y\) 值通常一开始是负数的原因。

4. 如何进行“枢轴运算” (How to Pivot) (DD3 & DD4)

枢轴运算 (Pivoting) 是我们从尚可的解转向更好解的方法。刚开始如果觉得复杂别担心，这只是一组规则而已。

步骤 1：选择枢轴栏 (Pivot Column)
观察目标函数行（最底行），挑选负值最大（数值最小）的数字。这一栏告诉我们哪一个变量最能帮助我们增加利润。

步骤 2：选择枢轴列 (Pivot Row) (比例测试)
对于每一行（最底行除外），将“数值 (Value)”（等号右侧的数）除以该枢轴栏中的数字。
• 规则： 选择最小正比例的那一行。
• 为什么？ 这能确保我们不会意外“打破”约束条件并离开可行区域。

步骤 3：行运算 (Row Operations)
现在，使用你在矩阵章节学过的“行消去法”技巧：
1. 将枢轴元素 (pivot element)（该栏与该列的交点）通过除法变为 1。
2. 通过加减枢轴行的倍数，将该栏中所有其他的数字变为 0。

你知道吗？ 电脑每天使用单纯形算法数百万次，解决庞大的问题，为企业节省了数十亿英镑！

5. 解读最终单纯形表 (Interpreting the Final Tableau) (DD4)

怎么知道什么时候结束？当目标函数行中没有负数时，你就完成了。

如何解读结果：

• 基本变量 (Basic Variables)： 这些是看起来像单位矩阵栏位（有很多 0 和一个 "1"）的栏。它们的值可以在“数值 (Value)”栏中找到。
• 非基本变量 (Non-basic Variables)： 这些是数值杂乱的栏位。我们将这些设为 0。
• 目标值 (Objective Value)： 右下角的数字就是你的最大利润（或最小成本）。

重点小结： 如果在最终单纯形表中，某个松弛变量 (\(s\)) 有数值，这代表你在该约束条件下有“剩余”的资源。如果 \(s = 0\)，代表你刚好用完了所有资源！

总结清单

• 建模： 定义变量、目标和限制。
• 图解法： 用于 2 个变量的情况；找出可行区域的顶点。
• 松弛变量： 加入它们以将 \( \le \) 转变为 \( = \)。
• 枢轴栏： 最底行中负值最大的数。
• 枢轴列： 最小正比例 (数值 / 栏位值)。
• 结束： 最底行没有负数，代表你已经找到最佳解！