欢迎来到单纯形法（Simplex Algorithm）的世界！
在之前的学习中，你可能已经习惯用图解线性规划（Graphical Linear Programming）来解决优化问题。当只有两个变量（\(x\) 和 \(y\)）时，这种方法非常好用，但如果工厂需要决定 10 种不同产品的产量呢？你总不能画出一个 10 维的图表吧！
这就是单纯形法（Simplex Algorithm）大显身手的时候了。它是一套循序渐进的数学“食谱”，专门用来在多变量系统中找出最佳结果（例如最大利润）。如果刚开始看到一堆数字觉得头昏脑胀，别担心——这其实只是一个逻辑过程：从形状的一个顶点移动到更好的顶点，直到抵达顶端为止！
1. 事前准备：专有名词
在建立第一张表格之前，我们需要先理解单纯形法的语言。这里通常是学生最容易搞混的地方，所以让我们简单拆解一下。
基本变量（Basic Variables）与非基本变量（Non-Basic Variables）
在算法的任何特定步骤中，我们会将变量分为两类：
- 非基本变量（Non-Basic Variables）：这些是我们通过将其设为零而“关闭”的变量。
- 基本变量（Basic Variables）：这些是目前有数值的变量。在单纯形表（Simplex Tableau）（我们那张大表格）中，基本变量很容易辨认，因为该栏位除了唯一的 1 以外，其余皆为 0。
- 基本可行解（Basic Feasible Solution, BFS）：这只是一个高大上的名称，指的就是在 3D（或多维）形状上，满足所有限制条件的一个“顶点”坐标。
松弛变量（Slack Variables）
单纯形法不喜欢不等式（例如 \(\le\)），它更喜欢等式（\(=\)）。为了修正这一点，我们会在每个限制条件中加入一个松弛变量（\(s\)）。 类比：想象你有 10 英镑可以花。你花了 \(x\)。所谓的“松弛”就是你口袋里剩下的零钱。花费 \(x \le 10\) 等同于说 \(x + s = 10\)，其中 \(s\) 就是你剩下的零钱。
快速回顾：关键术语
松弛变量：为了将 \(\le\) 转换为 \(=\) 而加入的变量。
基本变量：处于“解”中的变量（该栏位有一个 '1'，其余为 '0'）。
非基本变量：被设为零的变量。
2. 建立初始单纯形表
首先，我们将所有数据放入一个单纯形表（Tableau）中。课程大纲要求使用标准格式：
- 目标行（Objective Row）：通常是第一行。它显示你想要最大化的利润或数值。如果你的目标函数是 \(P = 3x + 2y\)，你必须先将其重写为 \(P - 3x - 2y = 0\)，才能填入表格。
- 约束行（Constraint Rows）：紧接在目标行之后。每一行代表加入松弛变量后的其中一个限制条件。
- RHS 栏位：“右侧（Right Hand Side）”栏位，显示方程式右边的数值。
你知道吗？我们总是从原点 \((0, 0)\) 开始执行单纯形法。这意味着我们初始的非基本变量是决策变量（\(x, y\)），而基本变量则是松弛变量（\(s_1, s_2\)）。这代表我们目前什么都没生产，所有资源都还剩着呢！
3. 迭代：改善你的解
一个迭代（Iteration）就是算法的一个完整周期。每一次迭代都会让我们沿着多维形状的边缘，移动到一个新的顶点（BFS），该点对目标函数来说数值更好。
逐步操作：如何进行迭代
1. 选择主元列（Pivot Column）：观察目标行，找出最负的数值。这一列告诉我们哪个变量能为利润带来最大的提升。这就是我们的入基变量（entering variable）。
2. 选择主元行（Pivot Row）（比值测试）：对于每一行（目标行除外），用 RHS 的数值除以主元列对应的数值。
规则：忽略主元列中的零或负值！
得到最小正比值的那一行就是你的主元行。该变量就是我们的离基变量（leaving variable）。
3. 主元运算（Pivot!）：这是代数运算的部分。你必须利用行运算来达成：
- 让主元元素（Pivot element）（主元行与主元列的交点）等于 1。
- 让该列中的其他所有数字都等于 0。
如果起初觉得棘手，别担心！这就像你以前学过的联立方程式解法。你只是在转换表格，让一个新的变量变成“基本变量”（即该列拥有唯一的 1）。
4. 何时停止？
你必须持续执行迭代，直到观察目标行时，发现变量栏位中再也没有负数为止。这代表没有办法再提高目标函数的数值了。你已经到达了最优解（optimum）！
解读最终表格
要读取最终答案：
- 找出那些只有一个 '1' 其余皆为 '0' 的栏位（这些就是基本变量）。
- 该变量的值即为该行对应的 RHS 栏位数值。
- 任何非基本变量（即栏位内容杂乱的变量）的值皆为 0。
常见错误避坑指南
符号陷阱：将目标函数移入表格时（例如 \(P = 5x + 4y\)），学生经常忘记将符号变号为 \(-5\) 和 \(-4\)。如果你的目标行中没有负数，你就无法启动算法！
5. 图解与代数解释
将发生的事情可视化非常重要。线性规划问题的可行区域是一个凸多边形（Convex Polygon）（在 2D 中）或多面体（Polyhedron）（在 3D 中）。
单纯形法的每一次迭代，其实就是沿着形状的边缘，从一个顶点（角落）跳跃到另一个相邻的顶点。我们正在“爬”这个形状，直到抵达最高点为止。
重点总结：单纯形法只是你用图解法做的事情的代数化版本，但它处理 100 个变量和处理 2 个变量一样轻松！
摘要检查表
• 松弛变量：用于将 \(\le\) 转为 \(=\)。
• 表格布局：目标行（需变号）、约束行、RHS。
• 主元列：目标行中最负的数值。
• 主元行：RHS/主元比值中最小的正数。
• 停止条件：目标行中不再有负数。
• 解读：基本变量 = RHS 的值；非基本变量 = 0。