📚 Linear Programming Problems | 线性规划问题
Linear programming (LP) is a mathematical technique used to find the best outcome, such as maximum profit or minimum cost, in a model whose requirements are represented by linear relationships. In A-Level Computer Science, LP appears as an optimisation problem that can be solved algorithmically, often using graphical methods for two variables or more general iterative methods such as the simplex algorithm.
线性规划是一种数学技术，用于在由线性关系表示需求的模型中寻找最佳结果，例如最大利润或最小成本。在 A-Level 计算机科学中，线性规划作为一种优化问题出现，可以通过算法求解，通常对两个变量使用图解法，或对更一般的问题使用单纯形法等迭代方法。
1. What is linear programming? | 什么是线性规划？
Linear programming deals with optimising a linear objective function subject to a set of linear constraints. The key components are decision variables, an objective function, constraints, and non-negativity restrictions.
线性规划处理的是在一组线性约束条件下优化一个线性目标函数的问题。关键组成部分包括决策变量、目标函数、约束条件和非负限制。
Decision variables are the quantities we control, such as the number of units to produce or the amount of a resource to use.
决策变量是我们控制的量，例如要生产的单位数量或要使用的资源数量。
The objective function is the expression to maximise or minimise, such as total profit or total cost.
目标函数是要最大化或最小化的表达式，例如总利润或总成本。
Constraints are linear inequalities or equalities that limit the values of the variables. Non-negativity means that variables cannot be negative in most real-world problems.
约束条件是限制变量取值的线性不等式或等式。非负性表示在大多数实际问题中变量不能为负。
2. Formulating an LP problem | 建立线性规划问题模型
To formulate an LP problem, first identify the decision variables, then write the objective function, and finally express each constraint as a linear inequality or equation.
要建立线性规划模型，首先确定决策变量，然后写出目标函数，最后将每个约束表示为线性不等式或方程。
For example, a company makes two products X and Y. Product X earns £3 profit per unit and product Y earns £2 per unit. Machine time limits production: each X needs 2 hours, each Y needs 1 hour, and only 16 hours are available. Packaging requires 1 hour for X and 2 hours for Y, with only 16 hours available.
例如，一家公司生产两种产品 X 和 Y。产品 X 每单位赚取 3 英镑利润，产品 Y 每单位赚取 2 英镑。机器时间限制生产：每个 X 需要 2 小时，每个 Y 需要 1 小时，只有 16 小时可用。包装需要 X 1 小时，Y 2 小时，只有 16 小时可用。
Let x be the number of units of X and y be the number of units of Y. The model is written as:
设 x 为 X 的单位数量，y 为 Y 的单位数量。模型写为：
Maximise P = 3x + 2y
Subject to:
2x + y ≤ 16
x + 2y ≤ 16
x ≥ 0, y ≥ 0
Here P is the total profit, and the inequalities represent the machine and packaging time limits.
这里 P 是总利润，不等式表示机器和包装时间限制。
3. Graphical method for two variables | 两变量图解法
For two decision variables, the constraints can be drawn as straight lines on a coordinate plane. The region that satisfies all constraints is called the feasible region.
对于两个决策变量，约束可以在坐标平面上画成直线。满足所有约束的区域称为可行域。
To draw the feasible region, first draw each constraint line. Then determine which side of each line satisfies the inequality by testing a point such as (0, 0). Shade the region that satisfies all inequalities simultaneously.
要绘制可行域，首先绘制每条约束直线。然后通过测试点（如 (0, 0)）确定每条直线的哪一侧满足不等式。对同时满足所有不等式的区域进行着色。
The corner points of the feasible region are critical because the optimal solution will occur at one of these vertices. Label the axes and the constraint lines clearly.
可行域的角点非常关键，因为最优解将出现在其中一个顶点处。需要清楚地标记坐标轴和约束直线。
4. Feasible region and optimal solution | 可行域与最优解
The optimal solution, if it exists, lies at a vertex of the feasible region. To find it, evaluate the objective function at each vertex and select the maximum or minimum value.
如果存在最优解，它位于可行域的顶点。为了找到它，在每个顶点处计算目标函数值，并选择最大值或最小值。
For the model above, the feasible region has vertices at (0, 0), (8, 0), (0, 8), and (16/3, 16/3). The objective values are shown in the table:
对于上述模型，可行域的顶点为 (0, 0)、(8, 0)、(0, 8) 和 (16/3, 16/3)。目标函数值如下表所示：
| Vertex (x, y) | P = 3x + 2y |
|---|---|
| (0, 0) | 0 |
| (8, 0) | 24 |
| (0, 8) | 16 |
| (16/3, 16/3) | 80/3 ≈ 26.67 |
equires integer answers, rounding is not enough because the solution must remain feasible.
最大利润为 80/3，在 x = 16/3 和 y = 16/3 处取得。如果问题要求整数答案，仅四舍五入是不够的，因为解必须保持可行。
5. Standard form and slack variables | 标准形式与松弛变量
To solve larger LP problems computationally, inequalities are converted into equations by adding slack variables. A slack variable represents unused resources.
为了用计算机求解更大的线性规划问题，通过添加松弛变量将不等式转换为方程。松弛变量表示未使用的资源。
+ y + s₁ = 16, where s₁ ≥ 0. Likewise, x + 2y ≤ 16 becomes x + 2y + s₂ = 16, where s₂ ≥ 0.
例如，约束 2x + y ≤ 16 变成 2x + y + s₁ = 16，其中 s₁ ≥ 0。同样，x + 2y ≤ 16 变成 x + 2y + s₂ = 16，其中 s₂ ≥ 0。
2x + y + s₁ = 16
x + 2y + s₂ = 16
P - 3x - 2y = 0
Introducing slack variables transforms the problem into a set of linear equations, which is easier for algorithms such as the simplex method to process.
引入松弛变量将问题转化为一组线性方程，这更容易被单纯形法等算法处理。
6. Introduction to the simplex method | 单纯形法简介
The simplex method is an iterative algorithm that moves from one vertex of the feasible region to an adjacent vertex, improving the objective value until the optimum is reached.
单纯形法是一种迭代算法，从可行域的一个顶点移动到相邻顶点，不断改进目标值，直到达到最优。
The method starts by creating an initial simplex tableau. It then identifies a pivot column from the most negative indicator in the bottom row for a maximisation problem. The pivot row is chosen using the minimum ratio test, and row operations are performed to update the tableau.
该方法首先创建初始单纯形表。然后从最大化问题底部行中最负的指示数中识别主元列。使用最小比值检验选择主元行，并执行行变换以更新单纯形表。
These steps repeat until all entries in the bottom row are non-negative. At that point, the basic variables give the optimal solution.
重复这些步骤，直到底部行中所有条目均为非负。此时，基变量给出最优解。
7. Computational thinking and algorithms | 计算思维与算法实现
In computer science, LP problems are solved by encoding the model into a program. Key computational thinking skills include abstraction, decomposition, pattern recognition, and algorithm design.
在计算机科学中，线性规划问题通过将模型编码到程序中来解决。关键的计算思维技能包括抽象、分解、模式识别和算法设计。
Abstraction removes unnecessary detail and keeps only the objective function, constraints, and variables. Decomposition breaks the problem into smaller parts such as entering variable selection, leaving variable selection, and pivoting.
抽象去除不必要的细节，只保留目标函数、约束和变量。分解将问题分解为更小的部分，例如选择进入变量、选择离开变量和主元变换。
The core loop of a simplex-based solver can be described as:
基于单纯形法的求解器的核心循环可以描述为：
WHILE optimal not reached
SELECT entering variable
SELECT leaving variable by minimum ratio test
PIVOT
END WHILE
This algorithmic view shows that linear programming is not only a mathematical tool but also a computational problem that can be implemented efficiently.
这种算法视角表明，线性规划不仅是一种数学工具，而且是一个可以有效实现的计算问题。
8. Using Python to solve LP | 使用 Python 求解线性规划
Libraries such as SciPy provide linprog for solving linear programming problems. A typical implementation defines the coefficients of the objective function, the constraint matrix, and the bounds of the variables.
SciPy 等库提供了 linprog 用于求解线性规划问题。典型实现定义目标函数的系数、约束矩阵和变量的边界。
The linprog function minimises c·x subject to Aub x ≤ bub problem, we must convert it by negating the objective function, because linprog minimises
Published by TutorHao | A-Level Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图