Linear Programming Key Points | 线性规划考点精讲

📚 Linear Programming Key Points | 线性规划考点精讲

Linear programming (LP) is a powerful optimisation technique used to find the best outcome—such as maximum profit or minimum cost—under a set of linear constraints. In IB and Edexcel mathematics, LP appears in the Applications and Interpretation course (AI HL includes simplex) as well as Edexcel’s Decision Mathematics modules. Mastering the graphical method and understanding the underlying theory will help you score high marks on exam questions. This article covers essential concepts, common pitfalls, and worked examples to consolidate your revision.

线性规划是一种强大的优化技术，用于在一组线性约束条件下找到最佳结果——如最大利润或最小成本。在 IB 和 Edexcel 数学中，线性规划出现在应用与解释课程（AI HL 包含单纯形法）以及 Edexcel 决策数学模块中。掌握图解法并理解其背后的理论，将帮助你轻松应对考试。本文将涵盖核心概念、常见误区，并提供示例巩固复习。

1. What is Linear Programming? | 什么是线性规划？

Linear programming deals with optimising a linear objective function subject to linear equality and inequality constraints. The decision variables are typically non‑negative, and the relationships among variables are expressed as straight lines or planes. In two dimensions, LP problems can be solved graphically, making them highly visual and intuitive.

线性规划研究的是在线性等式和不等式约束下优化一个线性目标函数。决策变量通常非负，变量之间的关系用直线或平面表示。在二维情形下，线性规划问题可通过图解法求解，因此非常直观。

2. Formulating the Problem | 建立模型

Every LP problem begins with a clear statement of the decision variables. For example, let x = number of product A produced, y = number of product B produced. Then formulate the objective function, e.g., maximise profit P = 5x + 7y, and list the constraints as linear inequalities, such as 2x + y ≤ 100 (machine hours), x + 3y ≤ 90 (labour), x ≥ 0, y ≥ 0. All constraints must be linear—no powers, products, or trigonometric terms.

每个线性规划问题首先明确决策变量。例如设 x = 产品A的产量，y = 产品B的产量。然后构建目标函数，如最大化利润 P = 5x + 7y，并列出线性不等式约束，如 2x + y ≤ 100（机器工时），x + 3y ≤ 90（人工），x ≥ 0, y ≥ 0。所有约束必须线性——不能包含幂次、乘积或三角函数项。

3. Graphing the Constraints | 绘制约束条件

Each inequality defines a half‑plane. To graph a constraint like 2x + y ≤ 20, first draw the boundary line 2x + y = 20 as a solid line (for ≤ or ≥) or a dashed line (for strict < or >). Then test a point not on the line, usually (0,0), to determine which side satisfies the inequality. Shade the forbidden region or, more commonly, leave the feasible side unshaded and clearly mark the feasible area.

每个不等式定义一个半平面。绘制约束 2x + y ≤ 20 时，先画出边界直线 2x + y = 20，≤ 或 ≥ 用实线，严格不等式用虚线。然后取直线外一点（通常为 (0,0)）检验哪一侧满足不等式。可将不可行侧涂黑，或更常见的是保留可行侧不涂色，并清晰标注可行区域。

4. The Feasible Region | 可行域

The intersection of all half‑planes defined by the constraints forms the feasible region. In a well‑posed LP, this region is a convex polygon (bounded or unbounded). If the region is empty—i.e., no point satisfies all constraints—the problem is infeasible. Always check that your drawn region matches every constraint, especially the non‑negativity conditions x ≥ 0, y ≥ 0.

所有约束半平面的交集构成可行域。在适定问题中，该区域是一个凸多边形（有界或无界）。若区域为空——即没有点满足所有约束——则问题无可行解。务必检查绘制区域是否满足每一个约束，特别是非负条件 x ≥ 0, y ≥ 0。

5. Corner Points (Vertices) | 角点（顶点）

The fundamental theorem of linear programming states that if an optimal solution exists, it will occur at one of the vertices (corner points) of the feasible region. Hence, after drawing the feasible region, identify all corner points. These are the intersections of the boundary lines. Solve the relevant pairs of simultaneous linear equations to find their exact coordinates, as graphical approximations may be imprecise.

线性规划基本定理指出：若存在最优解，它必然出现在可行域的某个顶点（角点）上。因此绘制可行域后，需找出所有角点。它们是各边界线的交点。通过联立求解线性方程组得到精确坐标，因为图形估计可能不够精确。

6. Finding the Optimal Solution | 求最优解

Once the vertices are known, evaluate the objective function at each vertex. For a maximisation problem, choose the vertex giving the highest value; for minimisation, select the lowest. Alternatively, use the objective line (or iso‑profit line) method: draw a line Z = c and slide it parallel until it just leaves the feasible region. The last vertex touched gives the optimal solution.

一旦求出所有顶点，计算每个顶点处的目标函数值。最大化问题取最大值所在顶点；最小化问题取最小值所在顶点。也可用目标函数等值线方法：画出 Z = c 的直线，平行移动该直线直至刚好离开可行域，最后接触的顶点即为最优解。

7. Multiple Optimal Solutions | 多重最优解

If the objective function is parallel to one of the binding constraints, all points along that edge of the feasible region yield the same optimum value. In this case, there are infinitely many optimal solutions. Examiners often test this by asking for the set of optimal solutions; you should describe the edge segment, e.g., “all points on the line segment from (2,4) to (5,2)”.

若目标函数与某个紧约束平行，则可行域该边上的所有点均对应同一最优值。此时存在无穷多最优解。考试常要求写出最优解集；应描述该边线段，例如“从 (2,4) 到 (5,2) 线段上的所有点”。

8. Unbounded and Empty Feasible Regions | 无界解与无可行解

When the feasible region is unbounded in the direction of optimisation, a maximisation (or minimisation) problem may have no finite optimal solution—called an unbounded solution. However, an unbounded region does not automatically mean the solution is unbounded; it depends on the objective function’s gradient. An empty feasible region means the constraints are contradictory, leading to no solution at all. Always state clearly “no feasible region” or “unbounded solution” when appropriate.

当可行域在优化方向上无界时，最大化（或最小化）问题可能没有有限最优解——称为无界解。但无界区域并不意味解无界，还需看目标函数的梯度方向。空可行域表示约束相互矛盾，问题无解。遇到这些情况，务必明确写出“无可行域”或“无界解”。

9. Integer Linear Programming | 整数规划

In many real‑life problems, decision variables must be whole numbers (e.g., number of buses to hire). The integer programming requirement adds complexity: the optimal vertex might not have integer coordinates. The solution is to examine all integer points near the continuous optimum, ensuring they lie within the feasible region. For two‑variable problems, you can list a few integer candidates and check. Note that the integer optimum is not simply the rounded continuous solution.

许多实际问题中，决策变量必须为整数（如租用巴士数量）。整数规划的要求增加了难度：连续最优解对应顶点可能并非整数坐标。此时需检验该顶点附近所有整数点，确保它们在可行域内。对二变量问题可列出邻近整数点并检验函数值。注意整数最优解并非简单地将连续解四舍五入。

10. Introduction to the Simplex Method | 单纯形法简介

For problems with more than two variables, the graphical method fails, and the simplex algorithm is used. This iterative procedure moves from one vertex of the feasible region to an adjacent vertex, improving the objective value each time, until optimality is reached. IB AI HL and Edexcel Decision Mathematics cover simplex tableaux, pivot operations, and interpretation of the final tableau. Although the algorithm is systematic, careful arithmetic and the ability to recognise an optimal tableau (no negative entries in the objective row for maximisation) are essential exam skills.

对于多于两个变量的问题，图解法失效，必须使用单纯形法。该方法从可行域的一个顶点迭代移动到相邻顶点，每次改进目标值，直至达到最优。IB AI HL 和 Edexcel 决策数学涉及单纯形表、转轴运算和最终表解读。尽管算法是系统的，但细心计算和识别最优表（最大化问题中目标行无非负项）是核心考试技能。

11. Tips and Common Mistakes | 技巧与常见错误

Common mistakes include: forgetting to include non‑negativity constraints x ≥ 0, y ≥ 0; confusing maximisation with minimisation when reading the question; shading the wrong half‑plane; incorrectly calculating vertex coordinates from simultaneous equations; and assuming the integer solution is simply the rounded LP optimum. Always double‑check the gradient of the objective function when sliding the objective line. For simplex, a frequent error is misidentifying the pivot column or row. Practice both graphical and simplex methods under timed conditions to build speed and accuracy.

常见错误包括：忘记添加非负约束 x ≥ 0, y ≥ 0；读题时混淆最大化与最小化；涂错了半平面；联立方程计算顶点坐标错误；直接四舍五入连续解当作整数解。使用目标函数等值线法时，务必复核梯度方向。在单纯形法中，经常误选转轴列或转轴行。建议计时练习图解法和单纯形法，提高速度与准确度。

12. Practice Example | 例题演练

Problem: A factory produces two types of items, A and B. Profit per unit A is £3, per unit B is £4. Each A requires 2 hours on machine M1 and 1 hour on M2; each B requires 1 hour on M1 and 3 hours on M2. The factory can use M1 for at most 10 hours and M2 for at most 12 hours per day. Find the daily production plan that maximises profit.

问题：一家工厂生产 A、B 两种产品，单位利润分别为 £3 和 £4。每件 A 需机器 M1 加工 2 小时、M2 加工 1 小时；每件 B 需 M1 加工 1 小时、M2 加工 3 小时。每天 M1 可用时长不超过 10 小时，M2 不超过 12 小时。求使日利润最大的生产方案。

Formulation: Let x = number of A items, y = number of B items.
Maximise P = 3x + 4y
Subject to:
2x + y ≤ 10 (M1)
x + 3y ≤ 12 (M2)
x ≥ 0, y ≥ 0

建立模型：设 x = A 产量，y = B 产量。
最大化 P = 3x + 4y
约束：
2x + y ≤ 10 (M1)
x + 3y ≤ 12 (M2)
x ≥ 0, y ≥ 0

Graphing: Plot the lines 2x + y = 10 and x + 3y = 12 on the x‑y plane. The feasible region is a quadrilateral with vertices at (0,0), (5,0), (0,4) and the intersection of the two lines. Solve simultaneously:
From 2x + y = 10 → y = 10 − 2x
Substitute into x + 3(10 − 2x) = 12 → x + 30 − 6x = 12 → −5x = −18 → x = 3.6
Then y = 10 − 2×3.6 = 2.8
Hence intersection is (3.6, 2.8)

绘图：在 x‑y 平面绘制直线 2x + y = 10 和 x + 3y = 12。可行域为四边形，顶点为 (0,0)、(5,0)、(0,4) 和两直线交点。联立求解：
由 2x + y = 10 得 y = 10 − 2x
代入 x + 3(10 − 2x) = 12 → x + 30 − 6x = 12 → −5x = −18 → x = 3.6
于是 y = 10 − 2×3.6 = 2.8
交点坐标为 (3.6, 2.8)

Evaluate P at vertices:
At (0,0): P = 0
At (5,0): P = 15
At (0,4): P = 16
At (3.6, 2.8): P = 3×3.6 + 4×2.8 = 10.8 + 11.2 = 22
The maximum profit is £22 at x=3.6, y=2.8. Since these are non‑integer, the production plan should be 3 or 4 units of A and 2 or 3 units of B if integer solutions are required, with further checking.

计算顶点处 P 值：
(0,0)：P = 0
(5,0)：P = 15
(0,4)：P = 16
(3.6, 2.8)：P = 3×3.6 + 4×2.8 = 10.8 + 11.2 = 22
最大利润为 £22，对应 x=3.6, y=2.8。如果产品必须为整数，则需要进一步检验附近整数点，连续解为非整数。

Interpretation: The continuous optimal solution suggests producing 3.6 units of A and 2.8 of B per day maximises profit under the given resource limits. This is the standard LP solution; if integer quantities are required, the integer optimum would need to be found by inspection of feasible integer points near (3.6, 2.8), such as (3,2) giving P=17, (3,3)=21, (4,2)=20 – note that (4,3) violates M2 constraint, so the integer maximum is 21 at (3,3). Thus, integer programming gives a slightly lower profit, as expected.

解读：连续最优解表明每天生产 3.6 件 A 和 2.8 件 B 可在资源限制下最大化利润。这是标准 LP 解；若要求整数产量，则需在 (3.6, 2.8) 附近寻找可行整数点，如 (3,2) 得 P=17，(3,3)=21，(4,2)=20——注意 (4,3) 违反 M2 约束，故整数最大利润为 21，对应 (3,3)。整数规划结果略低于连续最优值，符合预期。

Published by TutorHao | Mathematics Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Linear Programming Key Points | 线性规划考点精讲