改进单纯形法（Revised Simplex）
改进单纯形法亦称修正单纯形法（Revised Simplex），与「原始单纯形」在整张表上做 Gauss–Jordan 枢轴不同：不显式存储完整的修正方程组表，只保留与当前基 相关的紧缩数据（如 或对 的 LU 分解），按需算出比值检验与进基列所需的信息。大规模稀疏 LP、分支定界节点的重复求解、列生成 中的受限主问题等场景几乎都采用这一路线或其变种。
若尚未熟悉检验数与原始 / 对偶单纯形的进退基逻辑，请先阅读 单纯形法（含对偶单纯形骨架）。
与原始单纯形的对比
对标准形
原始单纯形在一张「表」上同时更新右端、目标行与各约束行的系数块；基变换时每轮对工作矩阵做一次大范围填充更新。
改进单纯形每轮只保证能拿到下列量：
含义： 常与对偶变量（影子价格）同一向量相差符号约定；检验数（简化费用）为 。
当前基变量取值 ；候选进基列 在基坐标下的表示 。
据此可做原始单纯形比值检验；若配合对偶可行基，也可在同一套数据上套用 单纯形法 文中对偶单纯形一节的比值 (4)。换言之，改变的主要是数据的存取与更新方式，进退基准则可与原始或对偶单纯形一致。
一轮迭代需要算什么
记当前可行基 （， 非奇异）。
1. 解三角系统得到 与
由 求 （若维护 则各一次三角回代）；由 求 。
2. 定价（pricing）
按某种顺序扫描非基列 ，计算 （稀疏时常只对一部分列做部分定价）。原始单纯形进基要求 （极小化）；若已是对偶可行起点则可转入对偶比值步骤。
3. 生成进基方向
对选定的进基列 ，解 得 。
4. 比值检验与换基
用 与 做最小比值（或对偶情形用 与 ），确定出基变量；得到新基 。
5. 更新基阵表示
将 换为 ，或用 eta 矩阵、Schur 补、稀疏 LU 刷新等方式等价更新，使得下一轮仍能快速解 与 。
基逆的数值更新（概要）
Eta 因子：早期实现对每次枢轴积累初等矩阵 ，使 ；迭代多时链变长，需周期性 reinversion（重新分解当前 ）。
LU 分解：对当前 做稀疏 LU（带行列置换与阈值选主元），每轮枢轴后在因子上做秩一修正或定期全量重分解；现代开源 / 商业求解器多采用此类稀疏内核。
稠密小块： 很小时显式维护稠密 亦可接受。
▶ 改进单纯形法（原始单纯形准则，骨架）
1. 初始化
取得可行基 及 的可逆表示（如 LU），使得 。
2. 计算 与检验数
解 ；对候选非基列计算 ，直至找到某个 （或用别套定价规则）；若全部 ，最优，停止。
3. 进基方向与无界判定
解 。若 ，无界，停止。
4. 比值检验
，确定出基行与出基变量。
5. 换基与更新
更新 及 的 LU / eta 链；令 在新基下修正（实现细节依因子格式而定）。返回步骤 2。
复杂度与实务提示
每轮主要代价常在定价步骤（扫描多少列）与解稀疏三角系统的次数上；部分定价、Devex / steepest-edge 等可减少迭代次数但增加单次工作量。内存上通常远优于存整张 修正表。
与其它笔记的关系
用途：与 单纯形法 同一数学骨架；工程层实现几乎是「大规模 LP + MIP 线性松弛」的默认选项。
衔接：列生成主问题仅含当前列子集， 即其对偶向量，供定价子问题使用；理解本节 与 与 列生成 记号的对应很有帮助。
常见线性规划教材在「修正单纯形」「乘积形式」「稀疏 LU」等处有更细的数值讨论。