线性规划

形式陈述 ​

线性规划是一类优化问题公理库优化问题Optimization problem在可行解集合上最小化或最大化目标函数的计算问题。，也是凸优化问题公理库凸优化问题Convex optimization problem在凸可行域上最小化凸目标且不等式约束为凸函数的优化模型。的多面体特例：目标函数线性，可行域由仿射等式与线性不等式相交而成，因而是凸集。

一般形式与线性边界 ​

线性规划（LP）是在实向量 $x\in {\mathbb{R}}^n$ 上优化线性目标，并用有限个线性等式和不等式规定可行域。一般最小化形式可写成

$$\underset{x}{min}{c}^{\mathsf{T}}x\text{s.t.}{A}_{\mathrm{ineq}}x\le b_{\mathrm{ineq}},A_{\mathrm{eq}}x=b_{\mathrm{eq}}.$$

变量还可带非负或自由符号约束。目标与所有约束都必须对决策变量线性；若目标仍是 $c^{\mathsf{T}}x$，却加入 $x_1{x}_2\le 1$、$\Vert x{\Vert }_2\le 1$ 或整数取值要求，就不再是这里定义的连续 LP。

不同教材对“标准形式”和“规范形式”的命名略有差异，使用时应直接写出约定。常见三种表示是：

表示	目标与约束
一般形式	线性等式、不等式与变量符号约束并存
等式标准形式	$min{c}^{\mathsf{T}}x$，$Ax=b$，$x\ge 0$
不等式规范形式	$max{c}^{\mathsf{T}}x$，$Ax\le b$，$x\ge 0$

这些形式可以互相转换。不等式 $a^{\mathsf{T}}x\le \beta$ 加入松弛变量 $s\ge 0$ 后变成 $a^{\mathsf{T}}x+s=\beta$；自由变量可写成 $x_j=x_j^{+}-x_j^{-}$，其中 $x_j^{+},x_j^{-}\ge 0$；一个等式也可拆成方向相反的两个不等式。转换会增加变量或冗余约束，可能引入退化，但不会改变原问题的可行解与最优值对应关系。

可行多面体与三种状态 ​

有限个线性半空间与仿射子空间的交是闭凸多面体。LP 首先可能不可行；若可行，目标还可能沿某条可行射线无限改善；只有可行且目标有有限最优值时，才进入通常的最优情形。对非空多面体，线性目标若有有限下确界或上确界，该值能够取到。

无界可行域不等于目标无界。例如最大化 $-x$ 且 $x\ge 0$ 时，可行域向右无限延伸，最优值仍为 $0$，在 $x=0$ 处取得。真正的无界需要存在一个保持可行并持续改善目标的方向。

若可行多面体含有极点，并且有限最优存在，则至少有一个最优极点；最优解也可能铺满一条边或更高维的面。含整条直线的多面体可能根本没有极点，因此“LP 的最优解总在顶点”需要这项存在条件，不能把非退化性当作替代。

直觉

线性约束把空间切成一个凸多面体，线性目标的等值超平面沿固定方向平移，最后接触可行域的位置给出有限最优。这个几何图像同时区分不可行、目标无界与最优可取三种状态，也解释了为何极点常重要，却不是无条件存在。

例子与边界

二维资源例与几何图像 ​

考虑

$$maxx+y\text{s.t.}x+2y\le 4,x\ge 0,y\ge 0.$$

可行多边形的顶点为 $(0,0),(4,0),(0,2)$，目标值分别为 $0,4,2$，故最优点为 $(4,0)$。几何上，直线 $x+y=t$ 沿法向平移，最后接触可行多边形的位置给出最大 $t$。若再加入 $x\le 1$，旧最优点被切掉，必须检查新边界交点；模型变化体现在可行多面体，而不是求解器“偏好”发生改变。

若把 $x,y$ 限制为整数，问题成为整数规划。连续多面体中的凸组合、极点和 LP 对偶仍可用于构造松弛，但不能直接保证整数可行或整数最优；LP 松弛与舍入公理库线性规划松弛与舍入LP relaxation and rounding放宽整数可行域获得可计算界，再把分数解舍入为可行组合解。与整数性间隙公理库整数性间隙Integrality gap衡量整数最优值与其松弛最优值在最坏实例上的比值。专门研究这道落差。

推论与应用

算法与对偶出口 ​

单纯形法公理库单纯形法Simplex method沿可行多面体顶点与边枢轴移动求解线性规划的方法。沿基可行解移动，内点法从可行域内部逼近边界，二者求解同一 LP，却依赖不同不变量和数值机制。线性规划对偶公理库线性规划对偶Linear programming duality · LP duality从线性约束生成对偶界，并以弱对偶、强对偶和互补松弛连接两侧最优解。为每个有限维 LP 构造界与最优性证书，弱对偶、强对偶和互补松弛属于模型建立后的理论，而不是理解线性目标与约束的前置条件。

网络流、匹配和近似算法会把具体结构编码成 LP。模型是否忠实、连续松弛是否过于乐观、数值求解是否达到容差是三个不同问题；不能把舍入造成的组合误差归因于 LP 求解器，也不能用一个很小的代数残差替代可行性与对偶间隙证书。

参考资料

• Bernhard Korte and Jens Vygen, Combinatorial Optimization, 6th ed., Springer, 2018，Chs. 4–11。
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。