Linear programming

欢迎来到线性规划：做出最优决策！

你好！线性规划（Linear Programming, LP）是决策数学中最实用且最令人兴奋的领域之一。它的核心在于：在给定一系列限制条件（约束）的情况下，找到最佳可能结果——通常是利润最大化或成本最小化。

在本章中，我们将学习如何将现实世界的问题转化为数学模型，并利用图形法进行求解。别担心“规划”这个词听起来很深奥，在这里它仅仅意味着计划或调度。本质上，我们是在用几何方法解决优化问题！

本节背景：该主题是 D1：决策数学 1 (Decision Mathematics 1) 单元的核心部分。

---

1. 线性规划的基础

什么是优化？

在 D1 中，优化是指找到某项指标的最大值或最小值。当所有涉及的关系均为线性（直线关系）时，线性规划提供了一种系统化的求解方法。

线性规划问题的三个基本要素

每个线性规划问题必须具备以下三个要素：

1. 决策变量 (Decision Variables)： 这是我们要试图确定的量，通常用 \(x\) 和 \(y\) 表示。
   示例：工厂应该生产的 A 型椅子数量 (\(x\)) 和 B 型桌子数量 (\(y\))。
2. 目标函数 (Objective Function)： 这是我们希望最大化（例如利润、收入）或最小化（例如成本、时间）的公式。它必须是关于决策变量的线性方程。
3. 约束条件 (Constraints)： 这是对可用资源的限制。它们表达为线性不等式。
   示例：总装配时间不能超过 100 小时：\(2x + 5y \le 100\)。

---

2. 建立线性规划模型

解决线性规划问题的第一步是将文字转化为数学语言。这通常是最棘手的部分，所以请仔细遵循以下步骤。

逐步建模指南

1. 定义决策变量

清楚地说明 \(x\) 和 \(y\) 代表什么。要具体，必要时包括单位。

示例：设 \(x\) 为生产的大号袋子数量，\(y\) 为生产的小号袋子数量。

2. 写出目标函数

确定目标是最大化（Max）还是最小化（Min）。写出被优化量的公式，通常记为 \(P\)（代表利润）或 \(C\)（代表成本）。

示例：如果大号袋子 (\(x\)) 的利润为 5 美元，小号袋子 (\(y\)) 的利润为 3 美元，则目标函数为：

$$\text{Maximize } P = 5x + 3y$$

3. 建立约束条件（不等式）

识别问题中施加的每一项限制（时间、材料、产能等）。

• 不等号方向检查：
  • “不能超过”、“最多”、“最大”、“限制在”意味着 \(\le\)（小于或等于）。
  • “至少”、“必须大于”、“最小”意味着 \(\ge\)（大于或等于）。
  • 如果某项必须等于特定值，请使用 \(=\)（但在 D1 图解法中很少见）。
• 非负约束： 由于你不能生产负数量的产品，请务必包含： $$\mathbf{x \ge 0 \quad \text{and} \quad y \ge 0}$$

  （这些约束至关重要，它们确定了图形的第一象限。）

建模要点总结

冷静分析： 仔细阅读题目，分配变量，写出目标（目标函数），并列出限制（约束条件）。如果你建模正确，后面的画图部分就会简单得多！

---

3. 图解法：寻找可行域

模型建立后，必须使用图解法进行求解。由于我们处理的是两个变量 (\(x\) 和 \(y\))，我们可以使用二维坐标系。

第一步：绘制约束直线

要绘制一个不等式（例如 \(2x + y \le 10\)），我们首先将其视为等式来画出边界线：

$$\mathbf{2x + y = 10}$$

• 找到截距：
  • 令 \(x=0\) 求 y 轴截距。（此处：\(y=10\)。点 \((0, 10)\)）
  • 令 \(y=0\) 求 x 轴截距。（此处：\(2x=10\)，得 \(x=5\)。点 \((5, 0)\)）
• 连接这些截距画出直线。

第二步：识别可行域 (R)

可行域 (R) 是图中同时满足所有约束条件的区域。我们需要确定直线的哪一侧代表该不等式。

测试点法：

1. 选择一个测试点，通常是原点 \((0, 0)\)（除非直线经过原点）。
2. 将 \((0, 0)\) 代入原始不等式。
3. 如果不等式成立（例如 \(0 \le 10\)），则可行域位于包含 \((0, 0)\) 的那一侧。
4. 如果不等式不成立（例如 \(0 \ge 10\) 不成立），则可行域位于直线的另一侧。

阴影约定： 在决策数学中，标准做法是涂掉你不想要的区域（即不可行区域）。这样留下的空白区域就是可行域 (R)，通常是由相交直线构成的多边形。

记得包含约束 \(x \ge 0\)（涂掉 y 轴左侧）和 \(y \ge 0\)（涂掉 x 轴下方）。

可行域要点总结

可行域 (R) 是图中唯一存在有效解的区域。R 的边界就是约束直线。

---

4. 寻找最优解

线性规划的基本定理指出：最优解（最大值或最小值）总是出现在可行域 R 的某个顶点（角点）处。

我们有两种主要方法来找到这个最优值：

方法 A：目标函数线法（搜索线法）

这种方法涉及画出目标函数线，并在可行域内平移它。

第一步：确定目标函数的斜率

设目标函数为 \(P = ax + by\)。为了将其画成直线，我们将 \(P\) 设为一个方便的常数 \(k\)：

$$ax + by = k$$

将其变形为 \(y = mx + c\) 的形式以找到斜率 (\(m\))。

$$by = -ax + k \quad \implies \quad y = -\frac{a}{b}x + \frac{k}{b}$$

目标线的斜率为 \(m = -\frac{a}{b}\)。

第二步：画出目标线

为一个方便画图的 \(k\) 值赋值（例如，如果 \(P = 3x + 2y\)，选 \(k=6\)，得到 \(3x + 2y = 6\)）。画出这条线，这就是你的搜索线。

第三步：平移直线

• 使用直尺平行于搜索线移动。
• 如果是最大化，将直尺向远离原点的方向平移，直到它刚刚触碰到可行域 R 的边缘。
• 如果是最小化，将直尺向靠近原点的方向平移，直到它刚刚触碰到可行域 R 的边缘。

第四步：确定最优顶点

直尺最后触碰到的点（可能是一个角点或整条边）就是最优解。

💭 记忆锦囊： 当最大化时，你想要 \(P\) 的最大值，所以你要让距离原点（\(P=0\) 的位置）越远越好。

方法 B：顶点测试法（角点法）

这种方法非常直接，但需要准确计算出每个顶点的坐标。

第一步：找出所有顶点（角点）

列出可行域 R 每个角点的坐标。利用联立方程组求出由两条约束直线相交形成的顶点的精确坐标。

示例：如果顶点 V 由 \(x + 2y = 10\) 和 \(x + y = 7\) 形成，联立求解得到 \((4, 3)\)。

第二步：代入目标函数

将每个顶点的坐标代入目标函数（\(P\) 或 \(C\)）中进行测试。

示例：如果 \(P = 5x + 3y\):

• 顶点 A \((0, 0)\): \(P = 5(0) + 3(0) = 0\)
• 顶点 B \((5, 0)\): \(P = 5(5) + 3(0) = 25\)
• 顶点 C \((4, 3)\): \(P = 5(4) + 3(3) = 29\)

第三步：陈述最优解

确定产生所需最大值或最小值的顶点。

示例：如果是最大化问题，最优解为 29，出现在点 \((4, 3)\) 处。

---

5. 高级解释与特殊情况

情况 1：非整数解与整数解

通常，变量 \(x\) 和 \(y\) 代表离散的物品（如汽车、人或包装），因此必须是整数。

如果你的数学最优解（通过方法 A 或 B 得到）不是整数——例如最大利润点在 \((4.2, 3.8)\)——你必须检查可行域 R 内或边界上的邻近整数点。

如何寻找整数最优解：

1. 识别最优非整数顶点 \(V\)。
2. 观察距离 \(V\) 最近且位于 R 内或边界上的整数坐标。
3. 将这些邻近的整数点代入目标函数进行测试。
4. 产生最好结果的点即为整数最优解。

重要提示： 从非整数最优解移动到整数点时，确保移动的方向是使目标函数值减小最少（如果求最大）或增加最少（如果求最小）的方向。

情况 2：多重最优解

如果目标函数的斜率与某条约束边界的斜率完全相同，那么最优解不会出现在单一顶点，而是出现在整条边上。

在这种情况下，连接顶点 A 和顶点 B 的边界线段上的任意一点都会产生相同的最优值。

考试中如何回答： 明确指出最大/最小值，并说明它出现在连接顶点 A 到顶点 B 线段上的所有点（含端点）。

结果解释与最终答案

最后一步始终是将数学答案放回到问题的原始语境中。

如果你的解是 \(x=10, y=5\)，最大利润为 120 美元：

最终答案： 公司应生产 10 单位的 X 和 5 单位的 Y，以实现 120 美元的最大利润。