biscuitの博客

可行解#

满足约束条件的解称为可行解。可行解的集合称为可行域。

LP的一般形式#

或者矩阵形式：

LP的标准形式#

任何线性规划都可以化成标准形式。满足

• 目标函数是最大化
• 决策变量($x_i$)非负
• 约束条件一律等式（除决策变量非负约束外）
• 约束条件右端（$b_i$）是非负数

如何将一般形式转化为标准形式#

目标函数：如果是最小化问题，可以通过取负号转化为最大化问题

加上松弛变量 $x_i'$ 和减去剩余变量 $x_i''$ ( 均非负 )

• 小于等于加松弛，大于等于减剩余。

自由变量（无约束）：拆成两个非负变量的差。

LP的可行解（域） $\iff$ 方程组 $A\mathbf{x} = b$ 的解集与 $\mathbf{x} \geq 0$ 的交集。这是一个凸多面体（polytope）里的所有点。在可行域里面找特殊结构，就是下文提到的基本可行解。

基变量和非基变量#

一般假设 $rank(A) = m$，可以解出 $m$ 个变量，称作 基变量 ，即 $\mathbf{x_B}={x_{1}, x_{2}, ..., x_{m}}$ 里面的分量，剩下的 $n-m$ 个变量为 自由变量 ($\mathbf{x_N}$ 里面的分量)，或者 非基变量 。

这俩的关系可以用矩阵分块来表示：

从 $A$ 中选出 $rank(A)$ 列线性无关的列向量，他们对应的变量是基变量（系数构成单位矩阵的变量），剩下的列向量对应的变量是非基变量。

TIP

这也解释了为啥基变量的数量等于约束条件的数量 $m$，非基变量的数量等于决策变量的总数减去基变量的数量 $n-m$。

然后令非基变量 $\mathbf{x_N} = 0$，解出基变量 $\mathbf{x_B}$ 的值，这样就得到了一个基本解。基本解可能不满足非负约束 $x_B \geq 0$，如果满足则称为基本可行解。

基本解和基本可行解#

非基变量组成 $\mathbf{x_N}$ ，基变量组成 $\mathbf{x_B}$ ，当 $\mathbf{x_N} = 0$ 时，$\mathbf{x}=\begin{bmatrix} \mathbf{x_B} \\ \mathbf{x_N} \end{bmatrix}$ 称为 基本解 。

• 基本解可能不满足非负约束 $\mathbf{x}_B \geq 0$，即有可能不可行；如果满足则称为 基本可行解 。
• 基本解的数量最多为 $C_n^m$ 个。

当基本解的各个分量都非负时，基本解就是基本可行解。（BFS）

• 基本可行解满足 $\mathbf{x}_B\geq 0$
• 基本可行解的数量最多为 $C_n^m$ 个。
• 基本可行解 = 可行域的顶点（极点）这是单纯形法的核心理论基础。

基本可行解的最优解叫做 最优基本可行解 。

WARNING

存在一个基本可行解是最优解，但不意味着每个最优解都是基本可行解。

线性规划的最优解可能出现在整个边或面上（无穷多最优解），其中非基本可行解（非顶点）也可能取到最优值。

例如：

$$max z = x_1 + x_2 \\ s.t. x_1 + x_2 \leq 1 \\ x_1, x_2 \geq 0$$

在这个例子中，所有满足 $x_1 + x_2 = 1$ 的点都是最优解，其中只有两个基本可行解（顶点）$(1,0)$ 和 $(0,1)$，其他点都是非基本可行解。

依旧用矩阵分块来表示：

所以基本解是 $\mathbf{x} = \begin{bmatrix} B^{-1}b \\ 0 \end{bmatrix}$ ，如果满足 $\mathbf{x_B} = B^{-1}b \geq 0$ 则是基本可行解。