形式陈述
线性规划是一类优化问题 理路 优化问题 Optimization problem 在可行解集合上最小化或最大化目标函数的计算问题。 凸优化问题 理路 凸优化问题 Convex optimization problem 在凸可行域上最小化凸目标且不等式约束为凸函数的优化模型。
一般形式与线性边界
线性规划（LP）是在实向量 x ∈ R n
min x c T x s.t. A ineq x ≤ b ineq , A eq x = b eq . 变量还可带非负或自由符号约束。目标与所有约束都必须对决策变量线性；若目标仍是 c T x x 1 x 2 ≤ 1 ‖ x ‖ 2 ≤ 1
不同教材对“标准形式”和“规范形式”的命名略有差异，使用时应直接写出约定。常见三种表示是：
表示
目标与约束
一般形式
线性等式、不等式与变量符号约束并存
等式标准形式
min c T x A x = b x ≥ 0
不等式规范形式
max c T x A x ≤ b x ≥ 0
这些形式可以互相转换。不等式 a T x ≤ β s ≥ 0 a T x + s = β x j = x j + − x j − x j + , x j − ≥ 0
可行多面体与三种状态
有限个线性半空间与仿射子空间的交是闭凸多面体。LP 首先可能不可行；若可行，目标还可能沿某条可行射线无限改善；只有可行且目标有有限最优值时，才进入通常的最优情形。对非空多面体，线性目标若有有限下确界或上确界，该值能够取到。
无界可行域不等于目标无界。例如最大化 − x x ≥ 0 0 x = 0
若可行多面体含有极点，并且有限最优存在，则至少有一个最优极点；最优解也可能铺满一条边或更高维的面。含整条直线的多面体可能根本没有极点，因此“LP 的最优解总在顶点”需要这项存在条件，不能把非退化性当作替代。
直觉 线性约束把空间切成一个凸多面体，线性目标的等值超平面沿固定方向平移，最后接触可行域的位置给出有限最优。如果目标方向恰好平行于一个边界面，接触点可以是一整条边；若可行域沿改善方向无限延伸，便没有最后一条接触超平面。这个图像区分不可行、目标无界与最优可取三种状态，也解释了为何极点常重要，却不是无条件存在。
约束系数在建模时已经固定，变量才是算法要选择的量。例如 a x ≤ b a , b a a x
图片加载失败 例子与边界 二维资源例与几何图像
考虑
max x + y s.t. x + 2 y ≤ 4 , x ≥ 0 , y ≥ 0. 可行多边形的顶点为 ( 0 , 0 ) , ( 4 , 0 ) , ( 0 , 2 ) 0 , 4 , 2 ( 4 , 0 ) y ≥ 0 x + y ≤ x + 2 y ≤ 4 4
若再加入 x ≤ 1 x + y ≤ 2 + 1 / 2 = 5 / 2 ( 1 , 3 / 2 )
若把 x , y LP 松弛与舍入 理路 线性规划松弛与舍入 LP relaxation and rounding 放宽整数可行域获得可计算界，再把分数解舍入为可行组合解。 整数性间隙 理路 整数性间隙 Integrality gap 衡量整数最优值与其松弛最优值在最坏实例上的比值。
推论与应用 算法与对偶出口
单纯形法 理路 单纯形法 Simplex method 沿可行多面体顶点与边枢轴移动求解线性规划的方法。 对数障碍与中心路径 理路 对数障碍函数与中心路径 Logarithmic barrier · Central path 在严格可行域中加入对数障碍，构造扰动互补条件，并由中心点的对偶证书得到可计算的目标误差界。 原始—对偶内点法 理路 原始—对偶内点法 Primal-dual interior-point method · Primal-dual path following 对原始可行性、对偶可行性与扰动互补条件联合取 Newton 步，以保正步长推进，并区分互补量与真正的可行对偶间隙。 线性规划对偶 理路 线性规划对偶 Linear programming duality · LP duality 从线性约束生成对偶界，并以弱对偶、强对偶和互补松弛连接两侧最优解。
Seidel 二维算法 理路 Seidel 二维线性规划 Seidel linear programming · Seidel randomized LP · Seidel 低维线性规划 随机加入半平面，在当前最优点被排除时降为边界上的一维区间问题，并用符号框区分不可行、有限最优和目标无界。 Clarkson 加权抽样 理路 Clarkson 加权抽样 Clarkson weighted sampling · Clarkson iterative reweighting · Clarkson 迭代倍增算法 反复按整数权重抽取小样本，核验全部约束，并只在违反总权较小时倍增违反者，以基权增长证明期望终止。
网络流、匹配和近似算法会把具体结构编码成 LP。模型是否忠实、连续松弛是否过于乐观、数值求解是否达到容差是三个不同问题；不能把舍入造成的组合误差归因于 LP 求解器，也不能用一个很小的代数残差替代可行性与对偶间隙证书。
双矩阵博弈的支持枚举 理路 双矩阵博弈的支持枚举 Bimatrix support enumeration · Support enumeration for Nash equilibria 枚举双方的非空支持集，用最大化正概率裕量的线性规划识别精确支持，并覆盖退化博弈中的不等大支持与连续均衡族。
有限分布的Kantorovich 输运问题 理路 Kantorovich 输运问题 Kantorovich transport problem 在指定边缘的联合分布上最小化搬运成本，允许拆分质量并利用弱紧性保证最优计划存在。
参考资料
Bernhard Korte and Jens Vygen, Combinatorial Optimization, 6th ed., Springer, 2018，Chs. 4–11。
Stephen Boyd、Lieven Vandenberghe，Convex Optimization
