优化理论之线性规划

线性规划的标准形式和基本性质

标准形式

$$\begin{aligned} \min \; &\sum_{j=1}^n c_jx_j\\ \mathop{s.t.}\; &\sum_{j=1}^n \alpha_{ij}x_j=b_i,\ &i=1,\dotsb,m\\ &x_j\geq 0,\ &j=1,\dotsb,n\\ \end{aligned}\tag{1.1}$$ 用矩阵表示为： $$\begin{aligned} \min \; &\boldsymbol c^T \boldsymbol x\\ \mathop{s.t.}\; &\boldsymbol A \boldsymbol x = \boldsymbol b\\ &\boldsymbol x \geq \boldsymbol 0\\ \end{aligned}\tag{1.2}$$ 其中$\boldsymbol{A}$是$m\times n$矩阵，$\boldsymbol c^T$是n维行向量，$\boldsymbol b$是m维列向量，且$\boldsymbol b \geq 0$(每个分量都大于等于0)

从非标准形式转化为标准形式

1. 如果存在$\boldsymbol b$的某一分量小于0，可以把方程两端都乘以-1
2. 在标准形式中，$x_j$都是非负的，这在实际生活中有着现实意义，但是处理数据时，难免有负数变量，因此可以令$x_j=x_j'-x_j''$，其中$x_j'\geq 0,x_j''\geq 0$。即用非负变量替换$x_j$
3. 当变量有上下界，不符合标准形式的要求时，也可做变量替换。当$x_j\geq l_j$,可令$x_j'=x_j-l_j$,则取$x_j'\geq 0$。当$x_j\leq u_j$时，可令$x_j'=u_j-x_j$，则取$x_j'\geq 0$
4. 当存在小于等于时，使用正松弛法；当存在大于等于号时用负松弛法。 $$\begin{aligned} \min \; &\sum_{j=1}^n c_jx_j\\ \mathop{s.t.}\; &\sum_{j=1}^n \alpha_{ij}x_j=b_i,\ &i=1,\dotsb,m\\ &x_j\geq 0,\ &j=1,\dotsb,n\\ & 小于等于限制转化为（松弛变量）\Rightarrow\\ &\sum_{j=1}^n \alpha_{ij}x_j + x_{n+i}= b_i,\ &i=1,\dotsb,m\\ & x_{n+1},x_{n+2},\dotsb,x_{n+m}\geq 0 \end{aligned}\tag{1.3}$$

用单纯性方法计算线性规划时，必须要用标准形。

基本性质

可行域

线性规划中，所有约束条件均为线性等式及不等式，满足这些条件的点的集合时凸集。即可行域是凸集。

最优极点

线性规划如果存在最优解，那么最优解一定能够在某个极点上达到。下面简要证明：根据表示定理（见附录），任何可行点$\boldsymbol{x}$可以表示为极点和极方向的组合： $$\begin{aligned} &\boldsymbol x=\sum_{j=1}^k \lambda_j\boldsymbol x^j + \sum_{j=1}^l \mu_j \boldsymbol{d}^j.\\ &\sum_{j=1}^k \lambda_j = 1.\\ &\lambda_j \geq 0,\ j=1,2,\dotsb,k.\\ &\mu_j \geq 0,\ j=1,2,\dotsb,l. \end{aligned}\tag{2.1}$$ 把$\boldsymbol x$的表达式代入$(1.2)$式，得到以$\lambda_j, \mu_j$为变量的等价的线性规划 $$\begin{aligned} \min\ &\boldsymbol x=\sum_{j=1}^k \lambda_j\boldsymbol c^T\boldsymbol x^j + \sum_{j=1}^l \mu_j \boldsymbol c^T\boldsymbol{d}^j.\\ \mathop{s.t.}\ &\sum_{j=1}^k \lambda_j = 1.\\ &\lambda_j \geq 0,\ j=1,2,\dotsb,k.\\ &\mu_j \geq 0,\ j=1,2,\dotsb,l. \end{aligned}\tag{2.2}$$ 注意，我们之前设过$\boldsymbol c^T$是一个行向量。由于$\mu_j$没有上限，因此若对于某个$j$，有$\boldsymbol c^T \boldsymbol d^j<0$，则$\mu_j \boldsymbol c^T\boldsymbol{d}^j$可以随着$\mu_j$的无限增大而无限减小，从而使目标函数趋向$-\infty$。对于这种情形，我们称该问题无界，或不存在有限最优值。

如果$\forall j, 有\boldsymbol c^T\boldsymbol{d}^j\geq 0$，这时为了极小化目标函数，需令 $$\forall j∈\{1,2,\dotsb,l\},\ \mu_j=0, \tag{2.3}$$ 则$(2.2)$可以简写为极点的凸组合： $$\begin{aligned} \min \ & \sum_{j=1}^k \lambda_j\boldsymbol c^T\boldsymbol x^j\\ \mathop{s.t.}\ &\sum_{j=1}^k \lambda_j=1,\\ &\lambda_j\geq 0,\ j=1,2,\dotsb,k \end{aligned}\tag{2.4}$$ 在所有$\boldsymbol c^T\boldsymbol x^j$中，必然有一个最小的值，令其为 $$\boldsymbol c^T\boldsymbol x^p = \min_{1\leq j \leq k} \boldsymbol c^T\boldsymbol x^j \tag{2.5}$$ 显然当 $$\lambda_p=1\ 且 \lambda_j = 0,\ j\neq p\tag{2.6}$$ 时，目标函数取最小值，即$(2.3)$和$(2.6)$式组合到一起时线性规划$(2.2)$的最优解。此时必有 $$\begin{aligned} \boldsymbol c^T\boldsymbol x &= \sum_{j=1}^k \lambda_j\boldsymbol c^T\boldsymbol x^j + \sum_{j=1}^l \mu_j \boldsymbol c^T\boldsymbol{d}^j\\ &\geq \sum_{j=1}^k \lambda_j\boldsymbol c^T\boldsymbol x^j\\ &\geq \sum_{j=1}^k \lambda_j\boldsymbol c^T\boldsymbol x^p=\boldsymbol c^T\boldsymbol x^p \end{aligned}$$ 因此，极点$\boldsymbol x^p$是线性规划的解。

定理1：设线性规划$(1.2)$的可行域非空，则有下列结论：

1. 线性规划$(1.2)$存在有限最优解的充要条件是所有$\boldsymbol c^T\boldsymbol d^j$为非负数。其中，$\boldsymbol d^j$是可行域的极方向。
2. 若线性规划$(1.2)$存在优先最优解，则目标函数的最优值可在某个极点上达到。

一般情况下，把无界问题也归为不存在最优解，只讨论存在有限最优解的情形。

最优基本可行解

基矩阵、基（本）解（基矩阵的解）（基解vs可行解）--》

基解由$\boldsymbol{x_b}$的基变量与非基变量$\boldsymbol{x_n}$组成--》

不是所有基解都是满足非负条件。满足非负条件的基解为基本可行解（=基解 && 可行解）（解的所有分量大于等于0）--》

退化（某个基变量取值为0）与非退化（基变量取值全部大于0）--》

基本可行解与极点有着对应关系--》

线性规化最优解为最优基本可行解

定理2：令$K=\{\boldsymbol x|\boldsymbol A \boldsymbol x=\boldsymbol b,\boldsymbol x\geq 0 \}, \boldsymbol A 为 m\times n$矩阵。$\boldsymbol A$的秩为$m$，则$K$的极点集和$\boldsymbol A \boldsymbol x = \boldsymbol b, \boldsymbol x\geq 0$的基本可行解集等价。

证明：可见最优化理论与算法（第2版）定理2.2.3的证明。

根据定理1和定理2，我们可知线性规划的求解问题归结为求最优基本可行解。

基本可行解的存在问题

在什么条件下存在最优解呢？其实表示定理的第一点已经明示了答案。

若$S=\{\boldsymbol x \vert \boldsymbol A \boldsymbol x= \boldsymbol b, \boldsymbol x \geq 0\}$为非空多面集，则有：

1. 极点集非空，且存在有限个极点$\boldsymbol x^1,\boldsymbol x^2,\dotsb,\boldsymbol x^k$

而有限的极点集必存在一个使目标函数最小的极点。如果从方程求解的角度来看，可以等价为以下定理：

定理3： 如果$\boldsymbol A \boldsymbol x= \boldsymbol b, \boldsymbol x \geq 0$有可行解，则一定存在基本可行解。其中$\boldsymbol A$是$m \times n$维矩阵，且$rank(\boldsymbol A)=m$

附录：表示定理

表示定理：设$S=\{\boldsymbol x \vert \boldsymbol A \boldsymbol x= \boldsymbol b, \boldsymbol x \geq 0\}$为非空多面集，则有：

1. 极点集非空，且存在有限个极点$\boldsymbol x^1,\boldsymbol x^2,\dotsb,\boldsymbol x^k$
2. 极方向集合为空集的充要条件是$S$有界。若$S$无界，则存在有限个极方向$\boldsymbol d^1,\boldsymbol d^2,\dotsb,\boldsymbol d^l$
3. $\boldsymbol x\in S$的充要条件是式$(2.1)$

关于上述定理的证明可见文章

[1] Bazaraa M S, Jarvis J J. Linear programming and Network flows， New York： Wiley 1977