一、LP 的数学形式

1. LP 的标准形式

• 线性规划（Linear Programming, LP）的标准形式为：

  • 求一组满足如下约束条件的非负变量 $x_1, x_2, \cdots, x_N$，

    $$ \begin{cases}

    a_{11} x_1 + a_{12} x_2 + \cdots + a_{1N} x_N = b_1 \\

    a_{21} x_1 + a_{22} x_2 + \cdots + a_{2N} x_N = b_2 \\

    \ \vdots \\

    a_{M1} x_1 + a_{M2} x_2 + \cdots + a_{MN} x_N = b_M \\

    \forall \, n \in [1, N], \ x_n \ge 0

    \end{cases} $$

    • 前 $N$ 行被称为等式条件，最后一行被称为非负条件。

  • 使得目标函数 (objective function) $S(x_1, x_2, \cdots, x_N)$ 最小：

    $$ \min : S(x_1, x_2, \cdots, x_N) = c_1 x_1 + c_2 x_2 + \cdots + c_N x_N \\ $$

• LP 标准形式的矩阵形式：记 $\boldsymbol A = \{ a_{mn} \}{M \times N}$，$\boldsymbol x = \{ x_n \}{N \times 1}$，$\boldsymbol c = \{ c_n \}{N \times 1}$，$\boldsymbol b = \{ b_m \}{M \times 1}$，等价为：

  $$ \min: S(\boldsymbol x) = \boldsymbol c^{\rm T} \boldsymbol x, \ {\rm s.t. } \begin{cases}

  \boldsymbol A \boldsymbol x = \boldsymbol b \\

  \forall \, n \in [1, N], \ x_n \ge 0

  \end{cases} $$

  • 下面用 $\boldsymbol x \ge \boldsymbol 0$ 简记 $\forall \, n \in [1, N], \ x_n \ge 0$。
  • 可行解：满足 $\boldsymbol A \boldsymbol x = \boldsymbol b$ 和 $\boldsymbol x \ge \boldsymbol 0$ 的 $\boldsymbol x$ 为 LP 的可行解。可行解的全体称为可行域。
  • 最优解：满足 $S(\boldsymbol x)$ 最小的可行解 $\boldsymbol x$ 称为最优解。

2. 将各种 LP 转化为标准形式

• 将极大目标转化为极小目标：

  $$ \max:S=\boldsymbol c^{\rm T} \boldsymbol x \ \ \Rightarrow \ \ \min : -S = (-\boldsymbol c)^{\rm T} \boldsymbol x $$

• 将大于等于形的变量约束 $x_n \ge p_n$ 转为新非负变量 $x_n' = x_n - p_n \ge 0$。

• 将小于等于形的变量约束 $x_n \le p_n$ 转为新非负变量 $x_n' = p_n - x_n \ge 0$。

• 对于某第 $m$ 行的小于等于形不等式 $a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mN} x_N \le b_m$，可以增加松弛变量 (slack variable) $y_i \ge 0$，使得：

  $$ a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mN} x_N + y_i = b_m $$

• 对于某第 $m$ 行的大于等于形不等式 $a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mN} x_N \ge b_m$，可以增加剩余变量 (slack variable) $y_i \ge 0$，使得：

  $$ a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mN} x_N - y_i = b_m $$

• 将自由变量（可正可负）$x_n$ 通过变换 $x_n = \overline x_n - \underline x_n$ 化为一对非负变量 $\overline x_n, \underline x_n$（阳变量 $\overline x_n$、阴变量 $\underline x_n$）。

eg

二、行满秩 LP 的解

1. 重新排列各列（行）顺序

• 假定 $\boldsymbol A$ 为行满秩矩阵，即 ${\rm rank} \, \boldsymbol A = M$（一定有 $M \le N$，否则无法行满秩）。因而能从其 $N$ 列中找到 $M$ 个线性无关的列，构成满秩矩阵 $\boldsymbol B$，称为 LP 的一个基，其可以作为 $\R ^M$ 的一组基。剩下的部分构成矩阵 $\boldsymbol N$。重新排布 $\boldsymbol A$ 的各列让 $\boldsymbol B$ 在前、$\boldsymbol N$ 在后，得到 $\tilde {\boldsymbol A}$：

$$ \tilde {\boldsymbol A} = [ \boldsymbol B, \boldsymbol N ] $$

• 相应重组 $\boldsymbol x$ 的各行得到 $\tilde {\boldsymbol x} = \begin{bmatrix} \boldsymbol x_B \\ \boldsymbol x_N \end{bmatrix}$，使得 $\tilde {\boldsymbol A} \tilde {\boldsymbol x} = \boldsymbol A \boldsymbol x = \boldsymbol b$。等式条件就可以拆成：

  $$ [ \boldsymbol B, \boldsymbol N ] \begin{bmatrix} \boldsymbol x_B \\ \boldsymbol x_N \end{bmatrix} = \boldsymbol B \boldsymbol x_B + \boldsymbol N \boldsymbol x_N = \boldsymbol b $$

  • 称 $\boldsymbol x_B$ 为基变量，$\boldsymbol x_N$ 为非基变量。

• 相应重组 $\boldsymbol c$ 的各行，得到 $\tilde {\boldsymbol c} = \begin{bmatrix} \boldsymbol c_B \\ \boldsymbol c_N \end{bmatrix}$，使得 $S = \tilde {\boldsymbol c}^{\rm T} \tilde {\boldsymbol x} = \boldsymbol c^{\rm T}\boldsymbol x$。化为：

  $$ S = \begin{bmatrix} \boldsymbol c_B^{\rm T} & \boldsymbol c_N^{\rm T} \end{bmatrix}\begin{bmatrix} \boldsymbol x_B \\ \boldsymbol x_N \end{bmatrix} = \boldsymbol c_B^{\rm T} \boldsymbol x_B + \boldsymbol c_N^{\rm T} \boldsymbol x_N $$

2. 假定等式条件成立，将基变量用非基变量表示

• 假定等式条件成立。将基变量 $\boldsymbol x_B$ 用非基变量 $\boldsymbol x_N$ 表示：

  $$ \boldsymbol x_B = \boldsymbol B^{-1}\boldsymbol b - \boldsymbol B^{-1} \boldsymbol N \boldsymbol x_N $$

  • 若令 $\boldsymbol x_N = \boldsymbol 0$，有 $\boldsymbol x_B = \boldsymbol B^{-1} \boldsymbol b$ ，$\tilde {\boldsymbol x} = \begin{bmatrix} \boldsymbol B^{-1} \boldsymbol b \\ \boldsymbol 0 \end{bmatrix}$。此向量满足等式条件，被称为基本解。
    • 如果 $\tilde {\boldsymbol x} = \begin{bmatrix} \boldsymbol B^{-1} \boldsymbol b \\ \boldsymbol 0 \end{bmatrix}$ 还满足非负条件即 $\boldsymbol B^{-1} \boldsymbol b \ge \boldsymbol 0$，称为基本可行解。此时 $\boldsymbol B$ 被称为可行基。
    • 如果基本解中的基变量 $\boldsymbol B^{-1} \boldsymbol b$ 中至少有一维度为零，称其为退化的基本解。