一、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

• 不失一般性地，我们还可以要求 $\boldsymbol b \ge \boldsymbol 0$。这是因为对于对应的 $b_i < 0$ 的行，我们能将原方程 $\boldsymbol a_i^{\rm T} \boldsymbol x = b_i$（这里 $\boldsymbol a_i^{\rm T}$ 是 $\boldsymbol A$ 的第 $i$ 行行向量）两侧乘以负一来转换为 $(-\boldsymbol a_i)^{\rm T} \boldsymbol x = -b_i$。

3. 图解法

• 当 $n \le 2$ 的时候，可以通过画图进行可行域的描述与最优解的寻找。

二、LP 的几何结构性质

1. 极点与方向相关的性质

• 称 LP 的可行域 $T = \{ \boldsymbol x \in \R^n \, | \, \boldsymbol A \boldsymbol x= \boldsymbol b, \boldsymbol x \ge \boldsymbol 0 \}$，它显然是一个凸集，而且它还是一个多面体，它的对应矩阵是列满秩的。

  说 $T$ 是多面体，是因为 $T$ 可以像下面这样化为 $\{\boldsymbol x \in \R^n \, | \, \boldsymbol M \boldsymbol x \, (\le, =) \, \boldsymbol b \}$ 的形式：

  $$ T = \left\{ \boldsymbol x \in \R^n \, \left| \,

  \begin{bmatrix}

  -\boldsymbol I \\ \boldsymbol A \\ -\boldsymbol A

  \end{bmatrix} \boldsymbol x \le \begin{bmatrix}

  \boldsymbol 0 \\ \boldsymbol b \\ -\boldsymbol b

  \end{bmatrix}

  \right.\right\} $$

  我们可以看到 $-\boldsymbol I$ 是一个列满秩矩阵，而下面接上再多的行也都还是列满秩的。

  • 根据凸集时的分析，我们知道（假设 $T$ 非空）：
    • $T$ 的方向的集合是 $D = \{ \boldsymbol d \neq \boldsymbol 0 \, | \, \boldsymbol A \boldsymbol d = \boldsymbol 0, \boldsymbol d \ge \boldsymbol0 \}$。
    • 对于 $T$ 的方向 $\boldsymbol d \in D$，有：$\boldsymbol d$ 是 $S$ 的极方向 $\Leftrightarrow$ 向量组 $\boldsymbol a_i$（$i \in I_+(\boldsymbol d)$）是最小正依赖集。

• **【LP 表示定理】**假设 $T$ 非空。根据列满秩多面体时的表示定理，知道 $T$ 的极点数目非零且有限；$T$ 的极方向数目有限；$T$ 的最大空间是平凡的 $\{0\}$。因而设 $T$ 的极点为 $\boldsymbol p^{(1)}, \boldsymbol p^{(2)}, \cdots, \boldsymbol p^{(|P|)}$，极方向为 $\boldsymbol d^{(1)}, \boldsymbol d^{(2)}, \cdots, \boldsymbol d^{(|D|)}$。

  • 任意可行点 $\boldsymbol x$ 可以表示为：

    $$ \boldsymbol x = \sum_{i=1}^{|P|} \lambda_i \boldsymbol p^{(i)} + \sum_{i=1}^{|D|} \mu_i \boldsymbol d^{(i)} $$

    • 其中：
      • $\forall i=1, 2, \cdots, |P|$ 有 $\lambda_i \ge 0$，且 $\sum_{i=1}^{|P|} \lambda_i = 1$。
      • $\forall i=1, 2, \cdots, |D|$ 有 $\mu_i \ge 0$。

  • 因而最小化问题就是：

    $$ \begin{align*}

    S &= \boldsymbol c^{\rm T} \left ( \sum_{i=1}^{|P|} \lambda_i \boldsymbol p^{(i)} + \sum_{i=1}^{|D|} \mu_i \boldsymbol d^{(i)} \right) \\

    &= \sum_{i=1}^{|P|} \lambda_i \boldsymbol c^{\rm T}\boldsymbol p^{(i)} + \sum_{i=1}^{|D|} \mu_i \boldsymbol c^{\rm T}\boldsymbol d^{(i)}

    \end{align*} $$