线性规划 · aiwiki.page

线性规划是数学优化的一个分支，研究如何在有限个线性等式和不等式约束下，使线性目标函数最大化或最小化。其决策变量通常取连续的实数值，而非仅限于整数。线性规划是凸优化的一种特殊情形，为资源分配、生产组织和经济决策分析提供了一个框架。这里的“规划”最初指制订计划，而不是编写计算机代码。(courses.csail.mit.edu)

数学表述

一种常见的表述为

\begin{aligned} \text{最大化}\quad &c^{T}x\\ \text{约束条件}\quad &Ax\leq b,\\ &x\geq 0. \end{aligned}

向量 $x$ 包含决策变量； $c$ 包含这些变量在目标函数中的系数；矩阵 $A$ 指定各变量在约束中的系数； $b$ 则给出约束的限值。向量不等式按分量逐一解释。目标函数是各变量的线性组合，因此不允许出现决策变量之间的乘积、 $x_j^2$ 这样的幂，或依赖于变量的系数。(courses.csail.mit.edu)

等价的表述可以采用最小化目标、等式约束或无符号限制的变量。将目标函数取负，即可把最大化转为最小化。无符号限制的变量可以写成两个非负变量之差。引入非负的松弛变量，便可将约束 $a^{T}x\leq b$ 转为 $a^{T}x+s=b$ 。通过这些变换，可以得到常用的标准形式 $Ax=b,\ x\geq0$ ；不同教材对“标准形式”和“规范形式”的命名有所不同。(courses.csail.mit.edu)

几何解释与可能的结果

可行集由所有满足约束的变量取值组成。每个线性不等式定义一个半空间，而当系数向量非零时，线性等式定义一个超平面。它们的交集既是多面体，也是凸集：任意两个可行点之间的整条线段都仍然可行。有界多面体通常称为多胞体。(courses.csail.mit.edu)

线性规划问题主要有三种结果：不可行、取得有限的最优值，或目标函数沿改善方向无界。可行集无界并不一定意味着目标函数无界。多个点可能具有相同的最优值，此时它们的凸组合也都是最优解。(courses.csail.mit.edu)

对于具有有限最优值的标准形式问题，至少有一个最优解是基本可行解，对应于可行多面体的一个极点。这一顶点性质是单纯形法的基础。对于一般形式，这一结论需要附加条件：包含一条直线的多面体可能没有极点，即便目标函数能够取得最优值。(courses.csail.mit.edu)

一个生产示例

假设某作坊生产两种产品，产量分别为 $x$ 和 $y$ ，且产量可以取非整数值。两种产品的单位利润分别为 3 和 2，资源限制给出如下问题：

\text{最大化 }3x+2y,\qquad x+y\leq4,\quad x\leq2,\quad y\leq3,\quad x,y\geq0.

取 $x=2,\ y=2$ 是可行的，所得利润为 10。这一方案也是最优的，因为任何可行取值都满足

3x+2y=2(x+y)+x\leq2(4)+2=10.

这个构造的例子既展示了一个可行的生产计划，也给出了一个证明，说明任何可行计划都无法取得更好的目标函数值。

对偶性与敏感性

与上述最大化形式相对应的对偶问题为

\begin{aligned} \text{最小化}\quad &b^{T}u\\ \text{约束条件}\quad &A^{T}u\geq c,\\ &u\geq0. \end{aligned}

这里， $A^{T}$ 是对 $A$ 进行矩阵转置得到的矩阵。这种关系是拉格朗日对偶的一个实例。弱对偶性表明，任意对偶可行解的目标函数值都是任意原问题可行解的目标函数值的上界。强对偶性表明，当原问题具有有限最优值时，对偶问题也能取得最优值，且两者的最优值相同。(math.mit.edu)

互补松弛条件刻画了原问题与对偶问题的最优解对：

u_i\bigl(b_i-(Ax)_i\bigr)=0,\qquad x_j\bigl((A^{T}u)_j-c_j\bigr)=0.

因此，若某种资源仍有剩余，则其对应的对偶乘子为零；若某个决策变量为正，则其对应的对偶约束取等号。(math.mit.edu)

在资源分配模型中，对偶乘子通常被解释为影子价格。敏感性分析研究系数或资源限额发生变化时，解和目标函数值如何变化。乘子只有在适当的变化范围内才能衡量资源的边际价值；较大的变化可能改变最优基，从而改变适用的边际价值。(web.mit.edu)

求解方法

单纯形法在约束系统的基上进行运算，通过换基操作在基本可行解之间移动。从几何上看，非退化步骤沿多面体的边移动。退化情形可能导致换基后目标函数值没有改善；若不采用适当的换基规则，还可能出现循环。尽管单纯形法在实践中普遍有效，但对于专门构造的实例，常见的单纯形法变体可能需要指数级数量的步骤。(courses.csail.mit.edu)

椭球法和内点法提供了多项式时间算法。内点法通常利用障碍函数，通过求解一系列问题逐步趋近最优解，而不是遍历顶点。对于有理数输入，这些方法的计算复杂性保证取决于输入的编码长度，其中包括表示系数所需的位数。(courses.csail.mit.edu)

发展与应用

列昂尼德·康托罗维奇于 1939 年提出了早期的资源分配方法。乔治·丹齐格于 1947 年创立了单纯形法。康托罗维奇和特亚林·库普曼斯因在最优资源分配方面的贡献，共同获得了 1975 年诺贝尔经济学奖。(nobelprize.org)

线性规划的应用包括运输、配料、生产计划和博弈论，尤其是有限零和博弈。当变量必须取整数时，模型就成为整数规划。去掉整数约束后，可得到线性松弛问题，其最优值为整数规划的最优值提供界限；但将线性松弛问题的解取整，并不一定能保持可行性或最优性。(web.mit.edu)