单纯形法

线性目标若有有限最优值，总能在某个顶点取得，因此单纯形法不扫描整个连续区域，而是在可行多面体的顶点（基可行解）之间沿边选择改进方向：每次选择能改善目标的入基变量，并用比值检验确定哪个基变量先降到零。这种边界行走有完整的几何依据；实践中它常很快，但存在精心构造的指数长枢轴路径。

松弛变量把 $Ax\le b$ 化为等式并给出初始基；没有显然基可行解时需两阶段法。单纯形法实践中常很快，但存在指数步坏例；它不是已知的多项式时间保证算法。浮点实现需分别设置可行性、约化成本与比值检验容差，并通过变量和约束缩放避免同一阈值跨越悬殊量级；几何退化与数值病态也不能混为一个失败状态。

标准形 $Ax=b,x\ge 0$ 中选取一组基列 $B$，令非基变量为零并解 $B^{-1}b$ 得基解。若某非基变量的约化成本表明增加它可改善目标，就沿对应方向移动，直到某个基变量触及零并离基。

初始可行基不一定显然存在，需两阶段法或人工变量；无界方向、不可行和退化要分别诊断。退化枢轴可能目标不变并造成循环，Bland 规则等可保证终止。修正单纯形实现会反复求解以基矩阵 $B$ 为系数的系统：$B$ 的条件性公理库问题条件性与条件数Conditioning of a problem · Condition number度量问题真解对输入微扰的局部敏感性，并把这种固有敏感性与算法误差分开。决定残差对基解的放大，数值分解还要使用枢轴与增长因子公理库主元选取与增长因子Pivoting · Growth factor · Partial pivoting通过行列置换限制消元乘子和中间元素增长，并把主元策略与 LU 的有限精度后向误差联系起来。诊断，而不是显式形成 $B^{-1}$。

线性规划公理库线性规划Linear programming · LP在线性等式和不等式约束下优化线性目标函数的问题。给出多面体与目标，基公理库向量空间的基Basis of a vector space同时线性无关并张成整个向量空间的向量组。给出顶点代数表示。最优终止时，最终基不仅给出原始变量，还通过对偶乘子和约化成本暴露约束的影子价格；在基保持最优且可行的范围内，还能读取目标系数或右端项变化的灵敏度区间。越出这些范围就可能换基，不能继续用同一局部价格作全局预测。单纯形法也适合暖启动，但经典枢轴规则没有多项式最坏步数保证；对偶单纯形、修正单纯形和内点法是不同求解器，不能把经验速度写成复杂度定理。

网络单纯形法公理库网络单纯形法network simplex method · network simplex algorithm把最小费用流的基表示为生成树，以约化费用选入基弧并沿基本环完成枢轴。利用流网络基的生成树结构专门求最小费用流，枢轴和可行性维护不同于通用稠密表。LP 松弛与舍入公理库线性规划松弛与舍入LP relaxation and rounding放宽整数可行域获得可计算界，再把分数解舍入为可行组合解。则先用 LP 值作上下界，再把分数解转成离散解并分析 integrality gap；它可以调用任意 LP 求解器，近似比不是单纯形沿边移动自动提供的。