核心概述
在线性规划标准型下以表格（字典）表示与主元旋转推进基/非基变量替换，依据入/出基与终止判定返回最优解或报告无界/不可行。
原文引述
Description: Standard simplex algorithm for linear programming in standard form (max c·x subject to Ax≤b, x≥0). Uses dictionary (tableau) format with pivot rules (Bland or lex). Handles unbounded/infeasible detection. Time: Exponential worst-case; typically fast in practice Status: tested ——摘自本节点现有英文注释
展开阐述
-
标准型
- 输入：最大化 c·x，满足 A·x ≤ b，x ≥ 0。
- 转化：添加松弛变量 s≥0，使 A·x + I·s = b；基变量为 s，非基变量为 x，目标 max c·x + 0·s。
- 表格（字典）形式：每行表示一个等式，右侧 RHS，目标行单独记录。
-
接口（据实现）
- vector
simplex(const vector<vector >& A, const vector & b, const vector & c) - 返回最优解向量 x（包含原始变量与松弛变量），或空/特殊值表示无界/不可行。
- 结构 Simplex：维护 tableau, basic, nonbasic，提供 pivot, isOptimal, isUnbounded 等方法。
- vector
-
核心步骤（字典序单纯形）
- 初始化：
- 构造增广矩阵 [A | I | b] 与目标行 [−c | 0 | 0]。
- 记录基变量索引（松弛变量）与非基变量索引。
- 主元选择：
- 入基变量：选目标行系数最小的非基变量（负系数，即能增加目标值）。
- 出基变量：对每个约束行，若入基列系数 > 0，计算 RHS / a_{ij}，取最小比值的行（Bland 或字典序规则）。
- 旋转变换（pivot）：
- 以 a_{ij} 为主元，将该行归一化（除以 a_{ij}），
- 用行操作将其他行的该列清零（类似高斯消元）。
- 更新基/非基变量集合。
- 终止条件：
- 若目标行无非正系数，则当前解最优。
- 若存在负系数列但所有对应约束行系数 ≤ 0，则问题无界。
- 可行性：若初始基不可行（某些 RHS < 0），先用对偶单纯形或两阶段法。
- 初始化：
-
数值与实现注意
- 浮点精度：使用 EPS 判断零（如 |x|<1e-9）；避免除以微小数。
- 循环防护：Bland 规则（下标最小）或字典序保证有限步终止。
- 大规模稀疏：可改用内点法或稀疏单纯形（超出模板范围）。
- 对偶问题：可同时获取对偶解（影子价格），用于灵敏度分析。
-
输出语义
- 返回原始决策变量的最优值（x_i），若无可行解则空/NaN；若无界则特殊值（如 INF）。
-
复杂度
- 理论指数最坏（Klee–Minty），实际平均 O(mn^2) 次基本操作，m 为约束数，n 为变量数。
-
使用与注意
- 输入需化为标准型；≥ 约束需乘 −1 并添加人工变量（两阶段法）。
- 若目标为最小化，可乘 −1 转为最大化；或用对偶单纯形。
- 模型规模：适合几百变量/约束；超大规模建议专用求解器。
- 整数规划：本模板不支持整数约束；需分支定界/割平面等。