📚 Linear Programming for A-Level Computer Science: Modelling, Simplex and Complexity | 面向 A-Level 计算机科学的线性规划：建模、单纯形算法与复杂性
Linear programming (LP) is a mathematical technique for finding the best outcome in a model whose requirements are represented by linear relationships. In computer science, LP appears in resource scheduling, network flow, compiler optimisation and decision support systems. This article explains the core ideas, the graphical method, the simplex algorithm, duality, complexity consequences and exam-style guidance for Edexcel A-Level Computer Science.
线性规划（LP）是一种数学技术，用于在需求由线性关系表示的模型中寻找最佳结果。在计算机科学中，线性规划出现在资源调度、网络流、编译器优化和决策支持系统中。本文讲解核心概念、图解法、单纯形算法、对偶理论、复杂性影响以及面向 Edexcel A-Level 计算机科学的考试风格指导。
Everything in this article is written for students who are comfortable with algebra, Big O notation and basic algorithm analysis but who have never built an LP model before. Each idea is introduced in English and then restated in Chinese, so you can revise in either language.
本文面向已经掌握代数运算、Big O 记号和基本算法分析、但从未构建过线性规划模型的学生。每个概念先以英文讲解，再用中文复述，方便你用任意一种语言复习。
1. What Is Linear Programming? | 什么是线性规划？
Linear programming deals with optimising a linear objective function subject to a set of linear equality or inequality constraints. The word 'programming' here means planning rather than computer programming, although computers are now the main tool used to solve LP problems. The technique was developed in the 1930s and 1940s by Leonid Kantorovich and George Dantzig to plan military logistics, transport and industrial production.
线性规划处理的是在一组线性等式或不等式约束下优化一个线性目标函数的问题。这里的 'programming' 表示规划而非计算机编程，尽管计算机现在是求解线性规划问题的主要工具。该技术由列昂尼德·康托罗维奇和乔治·丹齐格在 20 世纪 30 至 40 年代提出，最初用于军用后勤、运输和工业生产计划。
A model is a linear programme when three properties hold: the decision variables are continuous (they may take fractional values), the objective and every constraint are linear expressions in those variables, and all constraints can be written as equalities or inequalities. If any of these fails, the model is a non-linear programme and different methods are needed.
当满足三个性质时，一个模型才属于线性规划：决策变量是连续变量（可以取分数值）；目标函数与每一条约束都是这些变量的线性表达式；所有约束都能写成等式或不等式。任一条件不满足，模型就是非线性规划，需要使用其他方法。
In general form, an LP is written as follows:
一般而言，线性规划的标准写法如下：
maximise Z = c₁x₁ + c₂x₂ + … + cₙxₙ
subject to a₁₁x₁ + a₁₂x₂ + … + a₁ₙxₙ ≤ b₁
… aₘ₁x₁ + aₘ₂x₂ + … + aₘₙxₙ ≤ bₘ , xⱼ ≥ 0
Here Z is the value to be optimised, x₁ … xₙ are the decision variables, c₁ … cₙ are objective coefficients, and the a-values and b-values describe the available resources. 'Maximise' problems can always be rewritten as 'minimise' problems by negating the objective, so the two forms are mathematically equivalent.
其中 Z 是待优化的值，x₁ … xₙ 是决策变量，c₁ … cₙ 是目标系数，a 值与 b 值描述可用资源。最大化问题总可以通过对目标取负改写为最小化问题，因此两种形式在数学上等价。
2. Anatomy of an LP Model | 线性规划模型的基本构成
An LP problem consists of decision variables, an objective such as maximising profit or minimising cost, and constraints such as CPU core limits, memory capacity or bandwidth availability. Examiners expect you to name these components precisely and to explain what each one represents in the real system being modelled.
线性规划问题由决策变量、目标（例如利润最大化或成本最小化）以及约束（例如 CPU 核心数限制、内存容量或带宽可用量）组成。考官期望你能准确说出这些组成部分，并解释每一个在真实被建模系统中代表什么。
- Decision variables | 决策变量: the unknown quantities the solver can control, for example the number of hours each server runs or the bandwidth allocated to each route.
求解器可以控制的未知量，例如每台服务器的运行小时数，或分配给每条路由的带宽。 - Objective function | 目标函数: the linear expression to be maximised or minimised, such as total profit, total cost, total latency or total energy used.
需要最大化或最小化的线性表达式，例如总利润、总成本、总延迟或总能耗。 - Constraints | 约束条件: linear restrictions that represent physical or business limits, such as 400 available CPU cores or 600 GB of RAM.
代表物理或业务限制的线性约束，例如可用 400 个 CPU 核心或 600 GB 内存。 - Non-negativity restriction | 非负限制: the requirement xⱼ 0, because you cannot allocate a negative number of cores or transmit negative bandwidth.
要求 xⱼ ≥ 0，因为你不能分配负数个核心，也不能传输负的带宽。 - Feasible region | 可行域: the set of all points satisfying every constraint at once.
同时满足所有约束的点的集合。 - Feasible solution | 可行解: any single point inside or on the boundary of the feasible region.
位于可行域内部或边界上的任意一个点。 - Optimal solution | 最优解: the feasible solution giving the best value of the objective function.
使目标函数取值最优的可行解。 - Parameters or coefficients | 参数与系数: the fixed numbers in the model, for example 3 seconds of CPU time per request.
模型中固定的数值，例如每个请求消耗 3 秒 CPU 时间。
A compact example makes the vocabulary concrete:
一个紧凑的例子可以让这些术语变得具体：
maximise Z = 3x₁ + 5x₂
x₁ ≤ 4 , 2x₂ ≤ 12 , 3x₁ + 2x₂ ≤ 18 , x₁, x₂ ≥ 0
This is the standard textbook LP: two decision variables, three resource constraints and one objective. Every technique in the rest of this article is applied to this same model, which lets you compare the graphical, simplex and duality views of one problem.
这就是经典的教科书线性规划：两个决策变量、三条资源约束和一个目标函数。本文后续所有方法都会应用于这同一个模型，从而让你在同一个问题上比较图解法、单纯形法与对偶视角。
3. Formulating Computer Science Problems as LPs | 把计算机科学问题形式化为线性规划
Modelling is the hardest and most examinable step. A real computing problem must be translated into variables, an objective and constraints before any algorithm can run. Below are four recurring computing contexts where this translation is natural and defensible.
建模是最困难、也最常被考查的一步。真实计算问题必须先被翻译成变量、目标和约束，算法才能运行。下面是四类常见计算场景，这种翻译既自然又站得住脚。
- Resource scheduling | 资源调度: assign limited CPU cores, memory or technician hours to competing jobs so that throughput or profit is maximised.
在互相竞争的任务之间分配有限的 CPU 核心、内存或工程师工时，使吞吐量或利润最大化。 - Network flow | 网络流: send as much data as possible from source to sink while respecting the capacity of every link.
在遵守每条链路容量的前提下，尽可能多地把数据从源点送到汇点。 - Compiler optimisation | 编译器优化: choose how to schedule instructions or allocate registers so that the generated code is fast or short.
选择指令调度顺序或寄存器分配方案，使生成的代码更快或更短。 - Decision support systems | 决策支持系统: provide managers with an optimised recommendation under explicit business constraints rather than a guess.
在明确的业务约束下向管理者提供最优建议，而不是凭经验猜测。
A worked formulation for a bandwidth problem shows the process step by step. A streaming service must deliver at least 900 Mbps of traffic every second. Link A costs £2 per Mbps, link B costs £3 per Mbps, and the contracts allow at most 600 Mbps on A and at most 500 Mbps on B. The objective is to minimise cost.
下面用带宽问题演示完整建模过程。某流媒体服务每秒至少要交付 900 Mbps 流量。链路 A 每 Mbps 成本 £2，链路 B 每 Mbps 成本 £3；合同规定 A 最多 600 Mbps，B 最多 500 Mbps。目标是最小化成本。
minimise C = 2x₁ + 3x₂
x₁ + x₂ ≥ 900 , x₁ ≤ 600 , x₂ ≤ 500 , x₁, x₂ ≥ 0
cheaper, the optimum loads it to its limit: x₁ = 600, x₂ = 300, so C = 2 × 600 + 3 × 300 = £ traffic, and any change in price or capacity is absorbed simply by changing coefficients.
由于链路 A 更便宜，最优解把它用到上限：x₁ = 600，x₂ = 300，因此 C = 2 × 600 + 3 × 300 = 每秒 £2,100。注意模型如何把权衡显式化：由求解器而非程序员决定流量如何分配，任何价格或容量变化只需修改系数即可吸收。
4. The Graphical Method | 图解法
The graphical method solves LPs with exactly two decision variables. Each constraint is drawn as a straight line, the feasible region is the polygon where all half-planes overlap, and the objective function is swept across the region as a family of parallel lines until it leaves the polygon. The last point it touches is the optimum.
图解法只能求解恰好含两个决策变量的线性规划。每条约束画成一条直线，可行域是所有半平面重叠形成的多边形，目标函数则以一族平行线扫过该区域，直到离开多边形。最后接触到的那个点就是最优解。
The corner point theorem | 顶点定理: if an LP has an optimal solution, at least one optimal solution occurs at a vertex (corner) of the feasible region. This is why the graphical method only needs to test corners instead of infinitely many interior points, and it is the theoretical justification for the simplex algorithm.
顶点定理：如果一个线性规划存在最优解，那么至少有一个最优解出现在可行域的顶点（角点）上。这正是图解法只需检验角点、而无须检验无穷多个内点的原因，也是单纯形算法的理论依据。
Applying this to the standard model, the vertices and their objective values are:
把顶点定理应用于标准模型，各顶点及其目标值如下：
| Vertex (x₁, x₂) | 顶点 | Z = 3x₁ + 5x₂ |
| (0, 0) | 0 |
| (4, 0) | 12 |
| (4, 3) | 27 |
| (2, 6) | 36 ← optimal | 最优 |
| (0, 6) | 30 |
f the objective line is parallel to one of the edges of the feasible region, the optimum is not unique: every point along that edge gives the same best value. Examiners sometimes award a mark for recognising this special case.
最大值是 Z = 36，出现在 x₁ = 2、x₂ = 6 处。如果目标函数直线与可行域的某条边平行，最优解就不唯一：该边上的每一点都给出相同的最优值。考官有时会为识别出这一特殊情况给分。
The limitation is obvious: with three or more variables you cannot draw the diagram, so a numerical algorithm is required.
其局限也很明显：当变量达到三个或更多时无法作图，因此需要数值算法。
5. The Simplex Algorithm | 单纯形算法
The simplex algorithm, published by George Dantzig in 1947, walks from vertex to vertex along the edges of the feasible region, improving the objective at every step, until no improving move exists. It is an iterative improvement algorithm, and it is the classic example of how a geometric insight becomes a finite step-by-step procedure.
单纯形算法由乔治·丹齐格于 1947 年发表，它沿着可行域的边从一个顶点移动到另一个顶点，每一步都改进目标值，
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图