Linear programming

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

你有没有想过，工厂是如何精确决定生产多少产品才能获得最高利润？或是物流公司如何找到配送包裹最省钱的路径？这正是线性规划 (Linear Programming) 的核心所在！它是离散数学 (Discrete Mathematics) 的一个分支，专门用来在资源有限（例如时间、资金或材料）的情况下，找出“最佳”的结果（如最大化利润或最小化成本）。

如果现在觉得这些概念有点抽象，不用担心！我们会将它拆解成简单的步骤，让你成为解题高手！

1. 建立模型：制定问题

在我们解决问题之前，必须先将“现实世界的语言”转化为“数学符号”。这个过程称为制定 (Formulation)。你可以把它想象成把故事翻译成数学语言。

线性规划的三大要素

每个问题都需要这三个部分：

1. 决策变量 (Decision Variables)： 这些代表你想要决定的东西。通常我们将它们设为 \(x\) 和 \(y\)。例子：\(x\) = 要烘焙的杯子蛋糕数量，\(y\) = 要烘焙的布朗尼数量。

2. 目标函数 (Objective Function)： 这是你的目标。你是想最大化利润还是最小化成本？我们通常用 \(P\) 代表利润 (Profit) 或 \(C\) 代表成本 (Cost)。例子：如果每个杯子蛋糕赚 £2，每个布朗尼赚 £3，你的目标就是最大化 \(P = 2x + 3y\)。

3. 约束条件 (Constraints)： 这些是你的限制或“规则”。你的面粉、时间或烤箱空间有限。我们将这些写成不等式（使用 \(\le\) 或 \(\ge\) 等符号）。

逐步教学：如何制定问题

每次解题都请遵循这些步骤：

步骤 A： 清晰定义你的变量（例如：“设 \(x\) 为...”）。
步骤 B： 写下目标函数。
步骤 C： 以不等式列出约束条件。
步骤 D： 别忘了非负约束 (Non-negativity Constraints)！在现实世界中，你不可能烘焙 -5 个杯子蛋糕。因此，我们几乎总是会加上 \(x \ge 0\) 和 \(y \ge 0\)。

快速回顾： 若要制定问题，请找出你想决定的变量 (\(x, y\))、你的目标 (\(P\))，以及限制你的因素（不等式）。

2. 图解法：绘出你的限制范围

有了不等式后，我们需要在图表上把它们画出来。这能帮助我们找到满足所有规则的“甜蜜点”。

画直线

要画出像 \(2x + 3y \le 12\) 这样的不等式，首先要把它视为方程式：\(2x + 3y = 12\)。
小撇步：使用“遮盖法 (Cover-up Method)”找出直线与轴的交点！
- 要找出 \(y\) 轴截距，遮住 \(x\)（令 \(x=0\)）：\(3y = 12\)，所以 \(y = 4\)。
- 要找出 \(x\) 轴截距，遮住 \(y\)（令 \(y=0\)）：\(2x = 12\)，所以 \(x = 6\)。
用直线连接 (0, 4) 和 (6, 0) 即可！

标示可行区域 (Feasible Region)

可行区域（通常标记为 R）是图表上所有不等式同时成立的范围。它就像地图上唯一允许你行走的区域。

重要提示： 请务必仔细阅读题目关于涂色（标示区域）的要求。有些考官希望你标示出你“想要”的区域，而有些则希望你涂掉“不需要”的区域（留下可行区域留白）。AQA 考试通常建议你用 R 清晰标出可行区域。

你知道吗？ 在线性规划中，可行区域总是一个“凸集 (convex)”形状，这意味着它没有凹陷或缺口。

3. 寻找最佳答案

现在你有了区域 R，最佳答案（最佳解 optimal solution）几乎总是位于该区域的其中一个顶点 (vertices)（角位）上。

方法一：顶点测试法 (Vertex Testing Method)

这是对初学者来说最“万无一失”的方法！

1. 找出可行区域每个角落（顶点）的坐标。
2. 将每一组 \((x, y)\) 数值代入你的目标函数。
3. 观察哪一组数值能给你最高（利润）或最低（成本）的结果。

方法二：目标直线法 (Objective Line / Sliding Line Method)

想象你的目标函数是一把可以在图表上滑动的尺。

1. 为目标函数的一个随机值画出一条线（例如，如果 \(P = 2x + 3y\)，画出 \(2x + 3y = 6\)）。
2. 使用尺平行地滑动这条线（最大化时向远离原点的方向滑动）。
3. 直线离开可行区域前触碰到的最后一个点，就是你的最大值！
4. 若是最小化问题，直线进入区域后触碰到的第一个点（从原点开始移动时）就是你的最小值。

常见错误： 学生往往一找到一个顶点就停下来了。请务必检查所有角落，或使用滑动直线法，以确保这确实是绝对最佳解！

4. 处理“整数”问题 (Integer Programming)

有时数学计算可能会告诉你，最佳解是购买 \(3.7\) 辆巴士。很明显，你不能这么做！这就是所谓的离散 (Discrete) 约束。

如果答案必须是整数：
1. 先在图上找出最佳解（即使它是小数）。
2. 查看可行区域内最靠近该点的整数坐标。
3. 将这些附近的整数点代入目标函数，看看哪一个最好。

重点总结： 当你需要取整数时，数学上的“最佳小数解”四舍五入后不一定是“最佳整数解”。请务必测试附近的点！

总结清单

- 我能定义 \(x\) 和 \(y\) 吗？
- 我写下目标函数 (\(P = ...\)) 了吗？
- 我包含所有约束条件了吗，包括 \(x, y \ge 0\)？
- 我的可行区域标记清晰吗？
- 我测试过所有角位（顶点）来找到最大/最小值了吗？

如果一开始觉得画图很混乱，不用担心。只要有削尖的铅笔和稳定的尺，你会发现线性规划是 Further Maths 中最合乎逻辑且极具成就感的部分之一！