图解线性规划简介
欢迎来到离散数学中最实用的章节之一！线性规划 (Linear Programming, LP) 的名称听起来很高级，但其实目标很简单：在给定一系列限制条件下，找出最佳的结果（例如利润最大化或成本最小化）。
想象你在经营一家小烘焙坊。你希望赚取最多的利润，但你只有有限的面粉、有限的烤箱使用时数，而且你不可能烤出负数个蛋糕！线性规划能帮助我们平衡这些规则，找出成功的“甜蜜点”。
1. 建立问题模型：基本要素
在绘图之前，我们需要将现实世界的情况转化为数学模型。这称为建立模型 (Formulation)。任何线性规划问题都包含四个主要部分：
A. 决策变量 (Decision Variables)
这是你可以控制的项目。我们通常称之为 \(x\) 和 \(y\)。务必定义它们所代表的含义并列出单位。
例子：设 \(x\) 为生产的标准杯子蛋糕数量，\(y\) 为生产的豪华杯子蛋糕数量。
B. 目标函数 (Objective Function)
这是你想要达成的目标。你是想最大化 (maximise) 利润，还是最小化 (minimise) 浪费？它通常以方程式形式呈现，开头通常是 \(P\)（利润，Profit）或 \(C\)（成本，Cost）。
例子：如果一个标准杯子蛋糕能带来 £2 利润，而一个豪华款能带来 £3 利润，你的目标就是最大化 \(P = 2x + 3y\)。
C. 约束条件 (Constraints)
约束条件就是“规则”或限制。我们将这些写成不等式（使用 \(\le\) 或 \(\ge\) 等符号）。
- 资源限制：“你只有 500g 糖。”如果每个 \(x\) 用 10g，每个 \(y\) 用 20g，那么 \(10x + 20y \le 500\)。
- 比例约束：“你生产的标准蛋糕数量必须至少是豪华蛋糕的两倍。”这代表 \(x \ge 2y\)。
D. 平凡约束 (Trivial Constraints)
在现实世界中，你不可能制作负数量的产品。我们必须总是包含 \(x \ge 0\) 和 \(y \ge 0\)。别忘了这些，它们能确保我们的图形位于第一象限！
快速回顾：建立模型时，先找出变量，写下你的“目标”（目标函数），并列出你的“规则”（约束条件）。
2. 可行区域：绘图规则
现在进入绘图阶段。我们需要找到可行区域 (Feasible Region)，即图表上同时满足所有规则的区域。
如何画线
对于每个约束条件（例如 \(2x + 3y \le 12\)），首先将其视为方程式（\(2x + 3y = 12\)）来画出一条直线。一个好用的技巧是截距法 (Cover-Up Method)：
- 令 \(x = 0\)，求出 \(y\)。(在我们的例子中：\(3y = 12\)，所以 \(y = 4\))。标记点 \((0, 4)\)。
- 令 \(y = 0\)，求出 \(x\)。(在我们的例子中：\(2x = 12\)，所以 \(x = 6\))。标记点 \((6, 0)\)。
- 将两点用直线连接起来。
阴影规则（OCR 考试重点！）
在本课程中，我们遵循一个特定的惯例：涂黑不满足条件的区域。
如果你的规则是 \(x + y \le 10\)，直线上方的任何点都是“错误的”（不符合规则）。请涂黑直线上方的区域。当你为所有约束条件都做完这个步骤后，你会剩下清晰、没有阴影的区域。这个空白区域就是可行区域。
你知道吗？ 使用这种“涂黑排除法”能让可行区域脱颖而出，让你更容易观察解的位置！
3. 找出最佳解
一旦你有了清晰的可行区域，如何找到能带来最大利润的精确点呢？有两种主要方法：
方法一：顶点测试法 (Vertex Testing)
“最佳”解永远会出现在可行区域的其中一个顶点 (vertices)（角落）。
- 找出所有顶点的坐标。
- 将这些 \((x, y)\) 值代入你的目标函数。
- 得到最大值（求最大化时）或最小值（求最小化时）的那一个就是优胜者！
方法二：目标线法 (The Objective Line / "Sliding Line")
如果顶点很多，这个方法比较快：
- 为你的目标函数选择一个随机值（例如，如果 \(P = 2x + 3y\)，试着设 \(2x + 3y = 6\)）。
- 在图上画出这条线（通常画成虚线）。
- 使用直尺，将该线平行移动穿过可行区域。
- 最大化时： 直线离开可行区域前触碰到的最后一个点就是最大值。
- 最小化时： 直线进入可行区域内触碰到的第一个点就是最小值。
重点摘要：“最佳”答案几乎总是落在角落！利用直尺找出在目标方向上最远的那个角落。
4. 处理整数解
如果刚开始觉得这部分很麻烦别担心，因为有时候算出来的答案可能是“生产 4.7 辆车”。你不可能生产 0.7 辆车！如果题目要求整数解 (integer solutions)，你必须找出最合适的整数坐标。
常见错误：不要直接四舍五入！四舍五入后的点可能已经超出了你的可行区域（违反了规则）。
修正方法：观察最接近你最佳顶点的整数点 \((x, y)\)，并确保它们仍然在未涂黑的可行区域内。将这些点代入目标函数中进行测试，看看哪一个最好。
总结清单
- 建模： 确定变量 (\(x, y\))，写下目标函数 (\(P = ...\))，并列出约束条件。
- 作图： 使用截距法画线。
- 涂阴影： 将直线“错误”的一侧涂黑。保持可行区域清晰。
- 求解： 测试顶点或使用滑动目标线法。
- 检查： 答案是否需要为整数？在现实语境下是否合理？
秘诀： 请务必使用削尖的铅笔和长直尺。精确的绘图会让你在使用滑动目标线法寻找“最后触碰点”时轻松许多！