📚 Linear Programming Problems | 线性规划问题
Linear programming (LP) is a powerful mathematical technique used to find the best outcome in a model with linear relationships. In A-Level Computer Science, it sits at the intersection of algorithm design, optimisation, and computational thinking. An LP problem typically involves maximising or minimising a linear objective function subject to a set of linear constraints. Understanding how to formulate and solve these problems equips students with practical skills for tackling real-world resource allocation, scheduling, and decision-making challenges.
线性规划是一种强大的数学技术，用于在线性关系模型中找到最佳结果。在A-Level计算机科学中，它处于算法设计、优化和计算思维的交叉点。线性规划问题通常是在一组线性约束条件下，最大化或最小化一个线性目标函数。理解如何建立和求解这类问题，能让学生掌握处理现实世界中的资源分配、调度和决策挑战的实用技能。
1. Introduction to Linear Programming | 线性规划简介
A linear programming problem is defined by three main components: decision variables, an objective function, and constraints. The decision variables represent the quantities we can control. The objective function is a linear expression of these variables that we wish to maximise or minimise. Constraints are linear inequalities or equalities that restrict the values the decision variables can take.
线性规划问题由三个主要部分定义：决策变量、目标函数和约束条件。决策变量代表我们可以控制的数量。目标函数是这些变量的线性表达式，我们希望将其最大化或最小化。约束条件则是限制决策变量取值的线性不等式或等式。
In computer science, LP problems are often encountered in algorithm analysis, resource scheduling in operating systems, and network flow optimisation. The goal is not only to solve a single instance but to understand how to implement efficient solvers that can handle large numbers of variables and constraints.
在计算机科学中，线性规划问题常出现在算法分析、操作系统中的资源调度以及网络流优化中。目标不仅仅是解决单个实例，更要理解如何实现能够处理大量变量和约束的高效求解器。
2. The Standard Form of an LP Problem | 线性规划问题的标准形式
+ a₂ₙxₙ ≤ b₂, ..., and xᵢ ≥ 0 for all i. All constraints are inequalities with a ≤ sign and all variables are non-negative.
最大化线性规划的标准形式是：最大化 Z = c₁x₁ + c₂x₂ + ... + cₙxₙ，满足 a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁，a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂，...，且对所有 i 有 xᵢ ≥ 0。所有约束均为带 ≤ 号的不等式，且所有变量非负。
For minimisation problems, we can convert them to maximisation by negating the objective function. Equality constraints can be replaced by two opposite inequalities, and variables unrestricted in sign can be split into the difference of two non-negative variables. This standardisation is essential because well-known algorithms such as the simplex method are designed to work on this form.
对于最小化问题，我们可以通过将目标函数取负转化为最大化问题。等式约束可以用两个反向的不等式替代，符号不受限制的变量可以拆分为两个非负变量之差。这种标准化至关重要，因为诸如单纯形法等著名的算法都是针对这种形式设计的。
3. Objective Function and Constraints | 目标函数与约束条件
ariables. For example, if a bakery produces two types of cakes, x₁ and x₂, with profits of '3 and '5 respectively, the objective function to maximise profit is Z = 3x₁ + 5x₂.
目标函数量化了我们想要实现的目标——利润、成本、时间或距离——它始终是决策变量的线性组合。例如，一家面包店生产两种蛋糕 x₁ 和 x₂，利润分别为 3 英镑和 5 英镑，则最大化利润的目标函数为 Z = 3x₁ + 5x₂。
ties. For the bakery, constraints could be: 2x₁ + x₂ ≤ 100 (flour), x₁ + 3x₂ ≤ 80 (sugar), and x₁, x₂ ≥ 0. Each constraint forms a half-plane in the solution space, and the intersection of all half-planes gives the feasible region.
约束条件代表诸如原料供应、烤炉时间或存储空间等限制。它们必须是线性不等式或等式。对面包店而言，约束条件可能是：2x₁ + x₂ ≤ 100（面粉），x₁ + 3x₂ ≤ 80（糖），且 x₁, x₂ ≥ 0。每个约束在解空间中形成一个半平面，所有半平面的交集构成了可行域。
4. Feasible Region and Graphical Method | 可行域与图解法
e the feasible region where all constraints are satisfied. The non-negativity constraints x₁ ≥ 0 and x₂ ≥ 0 confine the region to the first quadrant.
当线性规划问题只包含两个决策变量时，我们可以用图解法求解。我们在二维平面上将每个约束绘制为一条直线，然后给所有约束同时成立的可行域打上阴影。非负约束 x₁ ≥ 0 和 x₂ ≥ 0 将区域限制在第一象限。
The graphical method provides a visual intuition: the optimal solution always lies at a vertex (corner point) of the feasible region, provided the region is bounded and the objective function is linear. This is known as the corner-point principle, which forms the foundation of more advanced algorithms.
图解法提供了一种直观感受：只要可行域有界且目标函数是线性的，最优解总是位于可行域的一个顶点（角点）上。这就是顶点原理，它为更高级的算法奠定了基础。
5. Corner Point Principle | 顶点原理
The corner-point principle states that for any linear programming problem with a bounded feasible region and a non-empty set of feasible solutions, the optimal value of the objective function is attained at one of the corner points of the feasible region. This means we can find the optimum by evaluating the objective function at each vertex and picking the best one.
顶点原理指出，对于任何可行域有界且可行解集非空的线性规划问题，目标函数的最优值总会在可行域的某个角点上达到。这意味着我们可以通过计算每个顶点处的目标函数值并选出最佳值来找到最优解。
Even when the feasible region is unbounded, if an optimal solution exists, it will still lie at a corner point. This principle drastically reduces the search space from an infinite number of points to a finite set of vertices, and it is the reason why the simplex method can work by moving from vertex to vertex.
即使可行域无界，只要存在最优解，它仍然会位于一个角点上。这个原理将搜索空间从无穷多点大幅缩减为有限个顶点，这也是单纯形法能够通过从一个顶点移动到另一个顶点来工作的原因。
6. The Simplex Method: An Overview | 单纯形法概述
The simplex method, developed by George Dantzig in 1947, is an algebraic procedure that systematically examines corner points of the feasible region to find the optimal solution. It starts at a known feasible corner point (often the origin) and moves to an adjacent corner point that improves the objective function value. The process repeats until no further improvement is possible.
单纯形法由乔治·丹齐格于1947年提出，它是一种系统地检查可行域角点以寻找最优解的代数方法。它从一个已知的可行角点（通常是原点）开始，然后移动到一个能改善目标函数值的相邻角点。此过程反复进行，直到无法进一步改进为止。
For a standard maximisation problem, the simplex method converts inequalities into equalities by adding slack variables. It then uses pivot operations on a tableau to perform the vertex-hopping while maintaining feasibility. The algorithm remains one of the most widely used optimisation tools in computer science.
对于标准最大化问题，单纯形法通过添加松弛变量将不等式转换为等式。然后它在单纯形表上进行转轴操作，在保持可行性的同时实现顶点跳跃。该算法至今仍是计算机科学中使用最广泛的优化工具之一。
7. Simplex Tableau and Iteration | 单纯形表与迭代
The simplex tableau is a compact matrix representation of the LP problem. For a problem with m constraints and n original variables, we add m slack variables s₁, s₂, ..., sₘ to turn inequalities into equations. The initial tableau includes rows for each constraint and an objective row. Each iteration selects a pivot column (entering variable) with the most negative coefficient in the objective row, and a pivot row (leaving variable) determined by the minimum ratio test.
单纯形表是线性规划问题的一种紧凑矩阵表示。对于一个有 m 个约束和 n 个原始变量的问题，我们添加 m 个松弛变量 s₁, s₂, ..., sₘ 将不等式转化为等式。初始表格包含每个约束对应的行以及一个目标行。每次迭代都会在目标行中选择系数最负的列作为主元列（进基变量），并通过最小比值检验确定主元行（出基变量）。
The pivot operation normalises the pivot row and clears the pivot column in all other rows. This transforms the tableau into a new basic feasible solution. The process stops when there are no negative coefficients in the objective row, indicating optimality. The solution can then be read directly from the tableau.
转轴操作会将主元行归一化，并清除其他行中的主元列。这会将表格转换为一个新的基本可行解。当目标行不再包含负系数时，过程停止，表示已达到最优。此时可以直接从表格中读出解。
8. Handling Inequalities: Slack and Surplus Variables | 处理不等式：松弛变量与剩余变量
ents unused resource. For ≥ constraints, we subtract a surplus variable and often add an artificial variable to initialise the simplex method.
松弛变量被添加至 ≤ 型约束中，以将其转化为等式。例如，2x₁ + x₂ ≤ 100 变为 2x₁ + x₂ + s₁ = 100，其中 s₁ ≥ 0。松弛量表示未使用的资源。对于 ≥ 型约束，我们会减去一个剩余变量，并常常添加一个人工变量来初始化单纯形法。
artificial variables to find an initial basic feasible solution when one is not readily available, which is common in problems with ≥ or = constraints.
在计算机实现中，正确处理这些变量对于构建一个稳健的线性规划求解器至关重要。两阶段单纯形法利用人工变量来寻找初始基本可行解，这在包含 ≥ 或 = 约束的问题中非常常见，因为这类问题不易直接获得初始解。
9. Unbounded and Infeasible Solutions | 无界解与不可行解
Not every LP problem has an optimal solution. A problem is said to be unbounded if the objective function can be made arbitrarily large (in maximisation) while satisfying all constraints. In the simplex tableau, this is detected when the pivot column contains no positive entries, so the leaving variable cannot be determined.
并非每个线性规划问题都有最优解。如果目标函数在满足所有约束的情况下可以变得任意大（对最大化而言），则称该问题无界。在单纯形表中，当主元列不存在正元素，从而无法确定出基变量时，便可检测到这种情况。
Infeasibility occurs when no solution satisfies all constraints simultaneously. Graphically, the feasible region is empty. In the simplex method, this is identified during the two-phase procedure when the artificial variables cannot be reduced to zero, indicating the original problem has no feasible solution.
不可行性发生在没有任何解能同时满足所有约束的情况下。从图形上看，可行域为空。在单纯形法中，这可在两阶段过程中被识别出——当人工变量无法被减小至零时，表明原问题没有可行解。
10. Implementing LP Solvers in Code | 在代码中实现线性规划求解器
A simple implementation of the simplex method can be coded in languages like Python. The core data structure is a 2D array representing the tableau. The algorithm loops through iterations: finding the pivot column (most negative in the objective row), performing the ratio test, and executing the row operations. Efficient implementations use matrix libraries to handle pivot steps with minimal floating-point error.
单纯形法的一种简单实现可以用 Python 等语言编码。核心数据结构是一个表示单纯形表的二维数组。算法循环执行以下迭代：找到主元列（目标行中最负的系数）、执行比值检验、并进行行运算。高效的实现会使用矩阵库来处理转轴步骤，以尽量减少浮点误差。
Modern LP solvers, such as those found in SciPy or commercial libraries like CPLEX, use advanced techniques like sparse matrix handling, presolving, and interior-point methods. Understanding the simplex method provides a solid foundation for appreciating these industrial-strength tools that solve problems with thousands of variables and constraints.
现代线性规划求解器，例如 SciPy 中的求解器或像 CPLEX 这样的商业库，使用了稀疏矩阵处理、预求解以及内点法等先进技术。理解单纯形法能够为欣赏这些能处理成千上万个变量和约束的工业级工具打下坚实基础。
11. Computational Complexity and Efficiency | 计算复杂度与效率
The theoretical worst-case complexity of the simplex method is exponential, meaning there exist contrived examples where the number of iterations grows dramatically with problem size. Yet in practice, the method performs remarkably well, typically solving problems in a number of iterations proportional to the number of constraints, not the number of variables.
单纯形法在理论上的最坏情况复杂度是指数级的，这意味着存在一些人为构造的例子，其中迭代次数会随问题规模急剧增长。然而在实践中，该方法表现非常出色，通常能以与约束数量（而非变量数量）成正比的迭代次数求解问题。
Polynomial-time algorithms for LP, such as the ellipsoid method and interior-point methods, have been known since the 1970s. Interior-point methods are particularly efficient for very large-scale problems and have become the default in many software packages, though the simplex method remains competitive for many practical applications.
自20世纪70年代起，人们就知道了求解线性规划的多项式时间算法，如椭球法和内点法。内点法对于超大规模问题特别高效，并已成为许多软件包的默认选择，不过单纯形法在许多实际应用中仍然很有竞争力。
12. Real-World Applications in Computer Science | 计算机科学中的实际应用
Linear programming is embedded in numerous computer science domains. In networking, it is used to model maximum flow and minimum cost flow problems. In machine learning, support vector machines rely on quadratic programming, a generalisation of LP. Compiler optimisation uses integer linear programming for instruction scheduling and register allocation, though these often require integer solutions.
线性规划已嵌入众多计算机科学领域。在网络中，它被用于建立最大流和最小费用流问题模型。在机器学习中，支持向量机依赖于二次规划（线性规划的推广）。编译器优化利用整数线性规划进行指令调度和寄存器分配，尽管这些通常要求整数解。
Other examples include CPU process scheduling, robotic path planning, and even game AI for minimising resource usage. The ability to formulate a problem as an LP and integrate a solver into a larger system is a valuable skill for software engineers and data scientists, reinforcing the importance of mastering LP concepts at A-Level.
其他例子包括CPU进程调度、机器人路径规划，甚至游戏AI中用于最小化资源消耗。能够将问题建立为线性规划模型并将求解器集成到更大系统中，是软件工程师和数据科学家的一项宝贵技能，这进一步巩固了在A-Level阶段掌握线性规划概念的重要性。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图