线性规划（Edexcel IAL 数学 D1）

Edexcel 国际 A-Level 数学· 2018 Specification Issue 3· 25 分钟阅读

1. 建立线性规划问题★★☆☆☆⏱ 6 min

✓ 计算器

📘 定义

线性规划（LP）

一种在一组线性不等式或等式约束下，求解线性目标函数最优值（最大值或最小值）的数学方法。

要建立任意双变量线性规划问题，你需要三个核心组成部分：决策变量、目标函数和约束条件。在解题开始时务必明确定义决策变量，Edexcel 考官会为清晰的变量定义单独给分。

决策变量：代表你可以控制的数量，例如生产的椅子数量、分配给项目的小时数。务必结合完整背景明确定义。
目标函数：代表你想要最大化（例如利润、收入）或最小化（例如成本、时间）的线性函数，用 x 和 y 表示，通常记为 Z。
约束条件：代表资源上限（例如可用总劳动小时数）或要求的线性不等式，加上非负约束（ $x \geq 0$ , $y \geq 0$ ），除非题目另有说明。

📐 例题

一名木匠制作小桌和大桌。每张小桌耗时2小时，消耗3米木材，产生25英镑利润。每张大桌耗时4小时，消耗5米木材，产生40英镑利润。木匠每周最多有40小时劳动时间和60米木材可用。将该问题建立为线性规划模型，最大化周利润。

1
步骤1：定义决策变量
2
令 $x$ = 每周生产的小桌数量， $y$ = 每周生产的大桌数量
3
步骤2：写出目标函数（最大化利润）：
4
$Z = 25x + 40y$
5
步骤3：写出资源约束条件，化简以便后续绘图：
6
劳动约束：每张小桌2小时，每张大桌4小时，总时长最多40小时：
7
$2x + 4y \leq 40 \implies x + 2y \leq 20$
8
木材约束：每张小桌3米，每张大桌5米，总木材最多60米：
9
$3x + 5y \leq 60$
10
步骤4：添加非负约束：
11
$x \geq 0, y \geq 0$

Exam tip:

尽可能化简约束条件（例如上例中将劳动约束除以2），可以让后续绘图更简单。只要化简后的约束与原始约束等价，考官都会认可。

2. 图解法：目标直线（直尺）法★★★☆☆⏱ 7 min

✓ 计算器

📘 定义

可行域

线性规划问题中满足所有约束条件的所有(x, y)点的集合。对于双变量问题，这是x-y平面上的一个凸多边形（包含其边界）。

目标直线法使用滑动直尺找到可行域中目标函数取得最大值或最小值的点。如果你需要在不计算精确坐标的情况下识别最优点，或者解释目标函数的变化如何改变最优解，该方法尤其有用。

1. 在x-y平面上绘制所有约束直线，对满足所有约束（包括非负性）的可行域进行阴影标记。
1. 为任意选定的Z值绘制目标直线，选择的Z值要便于绘图（例如对于 $Z = 25 x + 40 y$ ，取 $Z = 200$ 得到 $5 x + 8 y = 40$ ）。
1. 对于最大化问题，将目标直线沿平行方向向上/右尽可能滑动，直到它仍然接触可行域。对于最小化问题，将其向下/左滑动。
1. 目标直线与可行域的最后接触点即为最优点。

📐 例题

使用上一小节木匠示例的线性规划模型，用目标直线法找出最大化利润的最优点。

1
步骤1：绘制约束 $x + 2 y \leq 20$ 、 $3 x + 5 y \leq 60$ 、 $x \geq 0$ 、 $y \geq 0$ 。可行域是一个三角形，顶点位于(0,0)、(20, 0)、(0, 10)。
2
步骤2：绘制目标直线 $25 x + 40 y = 200$ ，该直线经过点(8, 0)和(0, 5)。
3
步骤3：将目标直线平行向上滑动以最大化Z。它在可行域内所能到达的最远点是(20, 0)。
4
步骤4：最优点为(20, 0)，最大利润为 $Z = 25 (20) + 40 (0) = 500$ 英镑。

Exam tip:

考试中务必在图上清晰标注目标直线，并用箭头指示滑动方向，这是使用目标直线法获得满分的必要要求。

3. 图解法：顶点检验法★★★☆☆⏱ 7 min

✓ 计算器

顶点检验法基于线性规划的基本性质：目标函数的最优值始终出现在可行域的某个顶点（角点）上。该方法在计算精确最优值时更可靠，如果你需要计算Z的精确最大值或最小值，这是首选方法。

1. 通过求解在每个顶点相交的约束直线的线性方程组，找出可行域的所有顶点。
1. 计算每个顶点处的目标函数Z值。
1. 对于最大化问题，选择Z值最高的顶点；对于最小化问题，选择Z值最低的顶点。

📐 例题

使用顶点检验法验证前几节中木匠示例的最优利润。

1
步骤1：找出可行域的所有顶点：
2
顶点1： $x = 0$ 和 $y = 0$ 的交点：(0, 0)
3
顶点2： $y = 0$ 和 $x + 2 y = 20$ 的交点：(20, 0)
4
顶点3： $x = 0$ 和 $x + 2 y = 20$ 的交点：(0, 10)
5
步骤2：计算每个顶点处的Z值：
6
在(0,0)点： $Z = 25 (0) + 40 (0) = 0$ 英镑
7
在(20,0)点： $Z = 25 (20) + 40 (0) = 500$ 英镑
8
在(0,10)点： $Z = 25 (0) + 40 (10) = 400$ 英镑
9
步骤3：Z的最大值为500英镑，位于点(20, 0)，与目标直线法的结果一致。

Exam tip:

务必列出可行域的所有顶点，即使有些点看起来显然会得到较低的Z值。即使你的最终最优值是正确的，Edexcel 考官也会为正确识别所有顶点给分。

4. 整数线性规划解★★★★☆⏱ 6 min

✓ 计算器

许多线性规划问题的决策变量代表不可分割的物品（例如桌子的数量、员工的数量），因此解必须是整数。对于 Edexcel IAL D1，你只需要检验连续最优解附近的可行整数点来找到整数最优解，不需要掌握更高级的整数规划算法。

📘 定义

整数可行点

x和y均为整数值，且满足线性规划问题所有约束条件的点(x, y)。

1. 首先使用目标直线法或顶点检验法找到连续最优解。
1. 找出位于可行域内部或边界上、靠近连续最优点的所有整数点。
1. 计算每个整数点的Z值，选择具有最优（最大/最小）Z值的点。

📐 例题

对于木匠示例，假设木匠每周必须至少生产3张大桌，求最大化利润的整数解。

1
步骤1：添加新约束 $y \geq 3$ 。更新后的可行域顶点位于(0,3)、(14, 3)、(0, 10)。
2
步骤2：通过检验顶点找到连续最优解：
3
在(0,3)点： $Z = 25 (0) + 40 (3) = 120$ 英镑
4
在(14,3)点： $Z = 25 (14) + 40 (3) = 470$ 英镑
5
在(0,10)点： $Z = 25 (0) + 40 (10) = 400$ 英镑
6
步骤3：连续最优点(14, 3)已经是整数，因此整数最优利润为470英镑，对应生产14张小桌和3张大桌。
7
如果连续最优点是例如(3.2, 5.7)，你需要检验整数点(3,5)、(3,6)、(4,5)、(4,6)，检查哪些点可行并给出最高Z值。

Exam tip:

切勿直接对连续最优解取整，因为取整后的值通常会落在可行域之外。务必明确检验你测试的每个整数点是否满足所有约束条件。

5. 常见陷阱

错误做法:

建立线性规划问题时没有明确定义决策变量

原因:

Edexcel 考官会为清晰的变量定义单独给分，跳过这一步会白白丢失容易拿到的分数

正确做法:

建模时始终以“令x = ...，令y = ...”开头，带上完整背景，例如“令x = 每周生产的小桌数量”

错误做法:

直接对连续最优值取整得到整数解，不检验可行性

原因:

取整后的值通常会违反一个或多个约束条件，得到无效解

正确做法:

检验连续最优点附近的所有整数点，在计算Z之前确认每个点都满足所有约束条件

错误做法:

建模时忘记包含非负约束（ $x \geq 0, y \geq 0$ ）

原因:

几乎所有线性规划问题都需要非负约束，省略它们会完全改变可行域

正确做法:

除非题目明确允许决策变量取负值，否则务必添加 $x \geq 0$ 和 $y \geq 0$

错误做法:

绘制可行域时，在约束直线的错误一侧进行阴影标记

原因:

这会导致可行域错误，后续所有最优点的计算结果都会出错

正确做法:

测试一个点（通常是(0,0)，如果它不在直线上），判断直线的哪一侧满足不等式，然后对该侧进行阴影标记

错误做法:

使用顶点检验法时，仅检验可行域的一个顶点

原因:

最优点可能是另一个顶点，你会因为没有展示全部计算过程而丢分

正确做法:

计算可行域每个顶点处的Z值，即使有些点看起来会得到较低的Z值

6. 速查表

任务	步骤	关键考试提示
建立线性规划问题	定义决策变量 2. 写出目标函数 3. 写出约束条件 + 非负约束	化简约束条件，让后续绘图更简单
目标直线法	绘制可行域 2. 绘制任意目标直线 3. 平行滑动直线找到最优点	标注目标直线，并用箭头标记滑动方向
顶点检验法	找到可行域所有顶点 2. 计算每个顶点的Z值 3. 选择最优Z值	列出所有顶点，拿到全部方法步骤分
整数解求解	找到连续最优解 2. 检验附近的整数可行点 3. 选择最优整数Z值	切勿直接取整：务必检验每个整数点的可行性

7. 常见问题

Edexcel IAL D1 考试中我需要同时掌握两种图解求解方法吗？

是的，目标直线法和顶点检验法都明确属于考试范围，题目可能会要求你使用指定的方法。顶点法在求解整数解问题时更可靠，而目标直线法在处理目标函数变化的定性问题时速度更快。

线性规划题目可以使用计算器吗？

可以，所有 Edexcel IAL D1 试卷都允许使用标准计算器，但禁止使用带符号代数功能的 CAS 计算器。你可以用计算器快速计算顶点处的目标函数值。

线性规划问题是否总是需要整数解？

不是，只有当题目说明决策变量代表不可分割的物品（例如桌子的数量），或者明确要求整数解时才需要。请务必先仔细审题确认问题背景。

深入阅读

下一步

现在你已经掌握了 Edexcel IAL D1 的线性规划内容，可以开始练习完整的历年真题，在限时条件下应用所学技能。线性规划经常与算法、图论等其他 D1 主题结合，出现在分值为6-8分的长考题中，因此请确保你完全掌握所有 D1 内容，最大化考试得分。记住两种图解法都属于考试范围，练习两种方法以应对任何题型。整数解题目通常占3-4分，练习快速检验可行点，避免在此处丢分。

→算法（Edexcel IAL D1）