📚 Linear Programming | 线性规划
Linear programming (LP) is a powerful mathematical technique for optimising a linear objective function, subject to a set of linear constraints. It is widely used in operations research and computer science to solve problems such as resource allocation, production scheduling, and network flow analysis. In the Edexcel A‑Level Computer Science specification, the graphical method and problem formulation are essential skills that build the foundation for algorithmic thinking in optimisation.
线性规划（LP）是一种强有力的数学技术，用于在若干线性约束条件下优化线性目标函数。它在运筹学和计算机科学中被广泛用于解决资源分配、生产调度和网络流分析等问题。在 Edexcel A‑Level 计算机科学课程中，图解法和问题建模是培养优化算法思维的重要基础技能。
1. What is Linear Programming? | 什么是线性规划？
Linear programming deals with problems where we need to maximise or minimise a quantity (such as cost, profit, or time) by choosing values for decision variables, while satisfying certain restrictions expressed as linear inequalities or equations.
线性规划处理的是需要通过对决策变量取值使某个量（如成本、利润或时间）达到最大或最小的问题，同时满足用线性不等式或方程表示的若干限制条件。
A standard LP problem requires all relationships to be linear – no variables are multiplied together, no powers other than 1, and no trigonometric or exponential terms appear.
标准的线性规划问题要求所有关系都是线性的——变量不能相乘，次数只能是1，不能出现三角函数或指数项。
2. Key Components of an LP Model | 线性规划模型的关键组成部分
Every linear programming model consists of three essential parts: decision variables (the unknowns we control), an objective function (the linear expression to be maximised or minimised), and constraints (linear inequalities or equalities that restrict the variable values).
每个线性规划模型都由三个基本部分组成：决策变量（我们控制的未知量）、目标函数（需要最大化或最小化的线性表达式）以及约束条件（限制变量取值的线性不等式或等式）。
Common additional requirements include non‑negativity constraints such as x ≥ 0, y ≥ 0, which reflect that real‑world quantities like numbers of items cannot be negative.
常见的附加要求包括非负约束，例如 x ≥ 0、y ≥ 0，这反映了现实世界中物品数量等不能为负。
3. Formulating an LP Problem | 线性规划问题的建模
Then write the objective function, such as Maximise P = 3x + 5y, and list all constraints from the given resources.
要将文字题转化为线性规划模型，首先定义决策变量，例如设 x 为产品 A 的数量，y 为产品 B 的数量。然后写出目标函数，如 最大化 P = 3x + 5y，并列出所有源于给定资源的约束条件。
Each constraint is written as a linear inequality, e.g. 2x + 3y ≤ 120 (minutes available).
约束条件通常来源于原材料、工时、机器时间或存储空间的限制。每条约束都写成线性不等式，例如 2x + 3y ≤ 120（可用分钟数）。
4. Graphical Method for Two Variables | 二变量图解法
When an LP problem involves only two decision variables, the optimal solution can be found by plotting the constraints on a coordinate plane. This method highlights the feasible region – the set of all points satisfying all constraints simultaneously.
当线性规划问题只涉及两个决策变量时，可以通过在坐标平面上绘制约束条件来找到最优解。这种方法突出了可行域——同时满足所有约束条件的所有点的集合。
Rarely does an A‑Level exam require more than two decision variables; for three or more variables the simplex algorithm is used, but the graphical method builds essential intuition.
A‑Level 考试很少要求超过两个决策变量；三个或更多变量时使用单纯形法，但图解法能建立重要的直觉。
5. Drawing Constraints and the Feasible Region | 绘制约束条件与可行域
= 80. Then shade the side of the line that satisfies the inequality. The feasible region is the intersection of all shaded areas, including the axes if non‑negativity applies.
首先画出每条线性不等式对应的直线，将不等号替换为等号。例如，对于 2x + y ≤ 80，画出直线 2x + y = 80。然后给满足不等式的一侧涂上阴影。可行域就是所有阴影区域的交集，如果存在非负约束，还应包括坐标轴。
Using a ruler and clear labelling is critical in exams; always indicate the scale and label the lines with their equations to avoid confusion.
考试中务必使用尺子并清晰标注；一定要标明坐标刻度，并用方程给直线标注，以免混淆。
6. Objective Function and Its Gradient | 目标函数及其梯度
arallel lines. Each line corresponds to a constant profit level; moving the line further from the origin (in the direction of increasing gradient for maximisation) increases the objective value.
目标函数（如最大化 P = 40x + 30y）定义了一族平行直线。每条直线对应一个固定的利润值；将直线朝远离原点的方向（最大化时朝着梯度增加的方向）移动会增大目标值。
Alternatively, you can compute the value of the objective function at each vertex of the feasible region – the vertex method – because the optimum for a linear objective function always occurs at a corner point, provided the region is bounded.
另一种方法是计算可行域每一个顶点的目标函数值——这种方法称为顶点法——因为只要区域是有界的，线性目标函数的最优值总是出现在某个角点处。
7. Finding the Optimal Solution | 寻找最优解
To locate the exact optimal point, either use the ruler method (slide a ruler parallel to the objective line until the last contact with the feasible region) or solve the equations of the two intersecting constraint lines at that vertex simultaneously.
为了确定精确的最优点，可以采用直尺平移法（将直尺与目标函数线保持平行，平移到与可行域最后接触的位置），或者联立求解该顶点处相交的两条约束直线方程。
Then substitute the coordinates back into the objective function to find the maximum or minimum value. Always check that the point satisfies all constraints.
然后将坐标代回目标函数，求出最大值或最小值。务必检查该点是否满足所有约束条件。
8. Worked Example – Maximisation | 示例详解——最大化问题
A company makes two products, X and Y. Profit per unit: £40 for X, £ (machine hours), x + 2y ≤ 70 (labour hours), x ≥ 0, y ≥ 0. Maximise profit P = 40x + 30y.
一家公司生产两种产品 X 和 Y。单位利润：X 为 40 英镑，Y 为 30 英镑。制造约束：2x + y ≤ 80（机器小时），x + 2y ≤ 70（工时），且 x ≥ 0，y ≥ 0。最大化利润 P = 40x + 30y。
0). The vertex (30,20) is found by solving the two equations: 2x + y = 80 and x + 2y = 70.
画出直线 2x + y = 80 和 x + 2y = 70。可行域是一个四边形，顶点为 (0,0)、(0,35)、(30,20) 和 (40,0)。顶点 (30,20) 由联立方程 2x + y = 80 和 x + 2y = 70 解得。
Evaluating P: at (0,35) P=1050; at (30,20) P=1800; at (40,0) P=1600. The maximum profit of £1800 occurs when x=30 and y=20.
计算 P：在 (0,35) 处 P=1050；在 (30,20) 处 P=1800；在 (40,0) 处 P=1600。最大利润为 1800 英镑，此时 x=30，y=20。
9. Minimisation Problems | 最小化问题
Minimisation follows the same principles, except you look for the smallest feasible value of the objective function. The feasible region is still bounded by the constraints, but the optimal point may be much closer to the origin.
最小化问题遵循相同的原理，只是需要寻找目标函数的最小可行值。可行域仍然由约束条件界定，但最优点可能离原点近得多。
s indefinitely upward, but the minimum cost occurs at a vertex, here (10,20) giving C=400.
示例：最小化成本 C = 20x + 10y，约束条件为 x + y ≥ 30，2x + y ≥ 40，x ≥ 0，y ≥ 0。可行域向上无限延伸，但最小成本出现在顶点处，此处为 (10,20)，C=400。
10. Integer Solutions and Discrete Variables | 整数解与离散变量
Many real‑world problems demand whole‑number solutions (e.g. you cannot manufacture 3.5 cars). If the optimal vertex gives a fractional answer, you must test integer points near the boundary of the feasible region. This is called integer linear programming.
许多现实问题要求整数解（例如无法生产 3.5 辆汽车）。若最优顶点给出小数答案，就必须在可行域边界附近测试整数点。这称为整数线性规划。
At A‑Level, you typically identify the closest integer coordinates that remain inside the feasible region and evaluate the objective function for each candidate, selecting the best one that obeys all constraints.
在 A‑Level 阶段，通常需要找出仍在可行域内的最接近的整数坐标，针对每个候选点计算目标函数值，从中选出满足所有约束的最优整数解。
11. Unbounded and Infeasible Problems | 无界问题与不可行问题
Sometimes a maximisation problem has no finite solution because the feasible region extends infinitely in the direction of increasing profit; this is an unbounded problem. It indicates a missing or incorrectly formulated constraint.
有时最大化问题没有有限解，因为可行域在利润增加的方向上无限延伸；这种情况称为无界问题。它表明缺少某条约束或约束描述有误。
Conversely, if no points satisfy all constraints simultaneously, the problem is infeasible irements, such as x ≥ 10 and x ≤ 5. In business contexts, this signals impossible targets.
相反地，如果没有任何点能同时满足所有约束，问题就不可行，通常源于矛盾的要求，例如 x ≥ 10 与 x ≤ 5 同时存在。在商业情景中，这代表着不可能达成的目标。
12. Applications in Computer Science | 计算机科学中的应用
Linear programming is embedded in many computing domains: compilers use integer programming for register allocation, operating systems schedule tasks by solving LP‑similar models, and network routing algorithms optimise flows under capacity constraints.
线性规划被嵌入到许多计算领域：编译器使用整数规划进行寄存器分配，操作系统通过求解类似线性规划的模型来调度任务，而网络路由算法在容量约束下优化流量。
Modern solvers such as CPLEX or open‑source libraries like SciPy allow programmers to build LP models within code, transforming mathematical formulation into automated decision systems – a direct link between A‑Level theory and real‑world software engineering.
像 CPLEX 或开源库 SciPy 这样的现代求解器使程序员能够在代码中构建线性规划模型，将数学表达转化为自动化决策系统——这直接架起了 A‑Level 理论与现实软件工程之间的桥梁。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图