线性规划 - OptLab

线性规划是优化领域中最为基础且应用广泛的分支，它研究在一组线性约束条件下，如何使线性目标函数取得极值。无论是生产计划、资源分配，还是交通运输、通信系统设计，都能看到线性规划的身影。本页将带你走进线性规划的世界，聚焦一个核心概念——基本解，并揭示它为何是求解线性规划问题的钥匙。

什么是线性规划？

线性规划问题的标准形式可写为：

\begin{array}{ll} \text{minimize} & c^T x \\ \text{subject to} & Ax = b \\ & x \geq 0 \end{array}

其中 \(x \in \mathbb{R}^n\) 是决策变量，\(c \in \mathbb{R}^n\) 是成本系数，\(A \in \mathbb{R}^{m\times n}\) 是约束矩阵，\(b \in \mathbb{R}^m\) 是右端项。我们通常假设 \(m < n\) 且 \(\text{rank} A=m\)，\(b \geq 0\)。

任何其他形式（如最大化、不等式约束）均可通过引入松弛变量或剩余变量转化为上述标准型。因此，掌握标准型的求解方法是理解线性规划的关键。

基本解：从无穷多解中抓住有限个候选

对于方程组 \(Ax = b\)，由于变量个数多于方程个数，通常有无穷多组解。但若我们从 \(A\) 的 \(n\) 个列向量中选出 \(m\) 个线性无关的列构成基矩阵 \(B\)，则令其余 \(n-m\) 个变量（称为非基变量）为零，可唯一解出基变量 \(x_B = B^{-1}b\)，从而得到一个基本解：

x = \begin{bmatrix} x_B \\ 0 \end{bmatrix}

如果这个基本解还满足 \(x \geq 0\)，则称之为基本可行解。基本可行解中若某些基变量为零，则称为退化的基本可行解。

            关键事实：基本解的个数最多为 \(\binom{n}{m}\)，虽然可能很大，但它是有限多个。这为后续的搜索算法奠定了基础。
        

线性规划基本定理

            如果线性规划存在可行解，则一定存在基本可行解；
如果线性规划存在最优可行解，则一定存在最优基本可行解。

这意味着，我们无需在无穷多的可行点中盲目搜索，而只需将注意力集中在有限个基本可行解上。最优解（如果存在）必定出现在某个基本可行解处。这一定理极大地简化了求解过程，也为单纯形法的诞生提供了理论依据。

几何视角：基本可行解就是可行域的极点

将约束条件 \(Ax = b, x \geq 0\) 看作 \(\mathbb{R}^n\) 中的一个凸集 \(\Omega\)（称为可行域）。几何上，\(\Omega\) 是一个凸多面体。它的极点（即不能表示为集合中其他两点凸组合的点）恰好与基本可行解一一对应。

换言之，基本可行解就是可行域的“角落”。线性规划的目标函数是线性的，因此其最优值必然在某个角落（极点）达到。

在二维空间中（如右图所示）：可行域是一个多边形，目标函数的等值线平行移动，最后离开可行域的点必是多边形的一个顶点。

二维可行域与目标函数等值线示意图

一个简单例子：从基本可行解到最优解

生产计划问题：

\begin{array}{ll} \text{maximize} & 3x_1 + 5x_2 \\ \text{subject to} & x_1 + 5x_2 \leq 40 \\ & 2x_1 + x_2 \leq 20 \\ & x_1 + x_2 \leq 12 \\ & x_1, x_2 \geq 0 \end{array}

当前解状态

坐标: \((0, 0)\)

目标函数: \(f = 0\)

变量	\(x_1\)	\(x_2\)	\(x_3\)	\(x_4\)	\(x_5\)

控制面板

选择入基变量：

代数操作步骤

等待操作...

可见，最优解正是在某个基本可行解处取得。单纯形法的思想就是从一个基本可行解出发，沿着可行域的棱边转移到相邻的、使目标值更优的基本可行解，直至找到最优。

松弛变量法

单纯形法要求从一个基本可行解开始迭代。对于形如下述不等式约束的线性规划问题（所有约束为“\(\le\)”且右端项非负）：

\begin{array}{ll} \text{maximize} & 3x_1 + 5x_2 \\ \text{subject to} & x_1 + 5x_2 \le 40 \\ & 2x_1 + x_2 \le 20 \\ & x_1 + x_2 \le 12 \\ & x_1, x_2 \ge 0 \end{array}

在每个不等式左侧添加一个非负的松弛变量，将不等式化为等式标准型：

\begin{array}{ll} \text{maximize} & 3x_1 + 5x_2 \\ \text{subject to} & x_1 + 5x_2 + x_3 = 40 \\ & 2x_1 + x_2 + x_4 = 20 \\ & x_1 + x_2 + x_5 = 12 \\ & x_1, x_2, x_3, x_4, x_5 \ge 0 \end{array}

此时，若取原变量 \(x_1 = 0, x_2 = 0\)，则松弛变量的取值恰好等于右端项：\(x_3 = 40, x_4 = 20, x_5 = 12\)，这组解显然满足所有约束且非负，因此是一个基本可行解（基变量为 \(x_3, x_4, x_5\)，基矩阵为单位阵）。

            要点：只要线性规划的所有约束均为“\(\le\)”形式且右端项非负，添加松弛变量后即自动获得一个初始基本可行解，从而可以直接启动单纯形法。对于包含等式或“\(\ge\)”约束的一般问题，则需要通过人工变量法（如大M法或两阶段法）构造初始可行基。
        

本例中，从初始基本可行解 \((x_1, x_2, x_3, x_4, x_5) = (0,0,40,20,12)\) 出发，通过单纯形法的换基迭代，最终移动到最优顶点 \((x_1, x_2) = (5,7)\)（对应松弛变量值可通过约束求得）。这正是上述交互演示所展示的过程。

大M法

当线性规划的标准型中不包含单位矩阵（即无法直接获得初始基可行解）时，引入人工变量构造一个单位矩阵。为使人工变量最终为零，需在目标函数中给予极大惩罚。

对于最大化问题，人工变量在目标函数中的系数设为 \(-M\)（\(M\) 为一个任意大的正数）；对于最小化问题，系数设为 \(+M\)。这样，在寻优过程中，算法会强制将人工变量从基变量中换出。

\begin{array}{ll} \text{maximize} & c^T x - M \sum_{i} a_i \\ \text{subject to} & Ax + a = b \\ & x \ge 0,\ a \ge 0 \end{array}

            求解步骤与最优性判断
            构造辅助问题，用单纯形法迭代；
若所有检验数 \(\le 0\)（最大化问题）且基变量中不含人工变量，得到最优解：
                    非基变量检验数全为负 → 唯一最优解；
存在非基变量检验数为零 → 多重最优解。

                
若所有检验数 \(\le 0\) 但基变量中仍含非零人工变量 → 原问题无可行解；
若存在检验数 \(>0\) 且其对应变量系数列向量全为非正 → 原问题无界解。

        

基变换时，通常选择检验数最大的非基变量入基，按 \(\theta\) 准则确定出基变量，以主元作初等行变换，重复直至满足最优条件。

两阶段法

两阶段法将求解过程分为两个阶段，避免了直接使用大 \(M\) 可能带来的数值稳定性问题，尤其适用于计算机求解。

第一阶段：判断可行性

引入人工变量，构造辅助目标函数 \(w = \sum (\text{人工变量})\)，并求解其最小值。约束条件与原问题添加人工变量后的等式组相同。

若最优值 \(w_{\min} = 0\)，则原问题存在基可行解，转入第二阶段；
若 \(w_{\min} > 0\)，说明原问题无可行解，停止计算。

第二阶段：求解原问题

以第一阶段最终单纯形表为基础，去除人工变量列，恢复原问题的目标函数（系数需重新计算检验数）。使用单纯形法继续迭代，直到得到最优解或判定无界。

两阶段法不仅逻辑清晰，而且能有效识别无可行解的情形，是实际求解线性规划问题的重要方法。