优化理论之线性规划

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

标准形式

\[ \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