单纯形法（Simplex Method）
单纯形法是求解线性规划（Linear Programming, LP）的经典算法：在满足线性等式与变量非负的前提下，沿可行域多面体的顶点逐次移动目标值，直至满足最优性判别。本文给出原始单纯形与对偶单纯形的算法骨架；不显式维护整张表的实现见 改进单纯形法。它是分支定界、分支切割等方法中 LP 松弛子问题的事实标准求解内核之一，也与 列生成 中的受限主问题求解密切相关。
问题形式与标准形
考虑极小化 LP（极大化时可将目标乘以 ，再在输出层换回符号）：
其中 ，，，且可通过预处理（如对约束乘 ）使得 。
一般模型中的 、 约束可先引入松弛、剩余或人工变量化为等式；细节依赖建模，此处只假定已得到 (1)–(2) 的标准形。
基本可行解与基
将列指标划分为两部分：基 （，对应矩阵 可逆）与非基 。变量分为基变量 与非基变量 （常取 ）。若
则称 为基本可行解（Basic Feasible Solution, BFS）。在一般非退化情形下，BFS 与可行域多面体的顶点一一对应；单纯形迭代即在相邻顶点间移动。
检验数与最优性
记 、 为基与非基部分的目标系数。非基列 的检验数（简化费用）常写作
在对 (1) 的极小化约定下：若所有 ，则当前 BFS 最优；若存在 ，则选取这样的 作为进基候选（常见规则：最负检验数，或 Bland 规则以避免循环）。
进基后需在基变量中选出基变量：沿射线增大进基变量分量时，保证仍满足 ，由最小比值检验（minimum ratio test）确定离开基的索引。
几何直觉（简述）
可行域 为一凸多面体；在非退化条件下，单纯形路径沿其棱从一顶点走到相邻顶点，每一步使目标值不降（极小化下不升）。有限步内在最优顶点终止；退化时可能出现若干迭代目标不变，需额外枢轴规则保证有限终止。
▶ 原始单纯形法（教科书骨架）
1. 前提
已得到形如 (1)–(2) 的可行 BFS 及对应基 （构造初始可行解常用两阶段法或大 法，此处略去细节）。
2. 最优性检验
按 (3) 计算（或等价地从单纯形表读出）全体非基变量的检验数 。若对所有 有 ，则当前解最优，停止。
3. 选取进基列
选取某个满足 的下标 作为进基列（若并列，按预定打破平局规则）。
4. 无界性判定
若进基方向上有 ，则沿该方向目标可无限下降，问题无界，停止。
5. 比值检验与枢轴
否则对满足 的基变量行做比值
达到最小的行为出基行；以 为枢轴做一次 Gauss–Jordan 消元（单纯形表上的换基），更新 、 与当前解。
6. 迭代
返回步骤 2。
对偶单纯形法（Dual Simplex）
原始单纯形从原始可行的基本可行解出发（），沿途保持原始可行性，直至达到对偶可行（极小化下全体检验数非负：）。
对偶单纯形则反过来：从一组基 出发，先要求对偶可行（仍以极小化 (1) 为准：所有非基变量的 已由 (3) 算出且 ），但允许原始不可行，即 中可能出现负分量；再通过枢轴逐步消除负的基变量取值，同时保持 。一旦原始可行性恢复，当前基既原始可行又对偶可行，即为最优。
动机：不必重新求一阶段可行基即可在「加割、加行、灵敏度分析」等情景下热启动：分支切割中新割常破坏当前原始可行性，若仍保持对偶可行性，用对偶单纯形往往比从头跑原始单纯形更顺。
记当前表（或等价地经 左乘后的方程组）中，第 行对应某个基变量，右端为 ，该行上非基列 的系数为 （即 ）。在对偶单纯形枢轴中，先选出基行 满足 ；再在满足 的非基列 上选取进基列，使比值规则维持枢轴后对偶可行性（极小化标准叙述如下）。
▶ 对偶单纯形法（极小化，骨架）
1. 前提
已知基 ，使得对偶可行：由 (3) 得全体非基 。允许 存在负分量。
2. 原始可行性检验
若 ，则当前解原始可行且已最优，停止。
3. 选出基行
选取一行 满足 （若有多个，按预定规则打破平局）。
4. 原始不可行判定
若对所有非基列 有 ，则原始问题无可行解（在对偶有界前提下），停止。
5. 比值检验（进基列）
在 中选取进基列 ，使
（极小化且当前已对偶可行时 ，且仅考虑 ，故比值非负；并列时用预定规则。）
6. 枢轴与迭代
以 为枢轴换基，更新 、 及表格系数（或等价地在修正形式下更新 / 因子分解）。返回步骤 2。
与原始单纯形对称：原始单纯形是「先进基、再比值选出基」，对偶单纯形是「先出基行、再比值选进基」。二者可在同一实现框架内仅交换比值检验与进退基判定顺序。
实现要点（工程视角）
修正单纯形：不显式维护整张表时的流程与数值工程要点见专页 改进单纯形法（Revised Simplex）。
内点法：当代商业与开源 MIP/LP 求解器常默认或可选内点法；单纯形仍广泛用于分支定界节点上的热启动与获取基状态。
退化与循环：多个比值并列时出现退化枢轴；实践中可选用 Bland 规则或在数值阈值下扰动以保证稳健性。
与其它笔记的关系
用途：分支定界各节点的 LP 松弛、割平面生成的分离子问题外层界计算等，底层常调用单纯形或其稀疏实现。
衔接：列生成主问题在固定列集上也是 LP，每轮常解其对偶以驱动定价；理解检验数与对偶变量有助于阅读 列生成 与 分支定价。
参考文献线索
单纯形法由 Dantzig 系统化；任何一本线性规划教材（如 Luenberger & Ye、Bertsimas & Tsitsiklis、Chvátal 等）均有完整推导与两阶段法。