约定向量 x 大于常数等价于 x 的每个分量大于某个常数

基础知识

多面集的表示定理

定理：设 $S=\lbrace x|Ax\boldsymbol{=}b,x\boldsymbol{\geqslant}0\rbrace$ 为非空多面集，则有

(1) 极点集非空，且存在有限个极点$x^{(1)},\cdots,x^{(k)}.$

(2) 极方向集合为空集的充要条件是S有界；若S无界，则存在有限个极方向$d^{(1)},d^{(2)},\cdots,d^{(l)}.$

$x\in S$的充要条件是

$$ x=\sum_{j=1}^k\lambda_jx^{(j)}+\sum_{j=1}^l\mu_jd^{(j)} $$

其中$\lambda_j\geq0,j=1,2,\cdots,k,\sum_{j=1}^k\lambda_j=1$

$$ \mu_j\geq0,j=1,2,\cdots,l. $$

线性规划

LP 的标准形式

  1. 极小化型
  2. 约束方程为等式
  3. 所有的决策变量为非负值
  4. 约束方程的右端项系数为非负值
$$ \min z = cx, \\ s.t.\ Ax = b,\\ x \ge 0 $$

非标准型 LP 模型可以转化为标准型 LP 模型

  1. 取个负号
  2. 约束方程为不等式：加一个松弛变量变为等式。
  3. 变量无非负约束：令 $x_j = x_j^\prime - x_j^{\prime\prime}$
  4. 决策变量有上下界：平移到0处。

LP 问题的基本性质

可行解

线性规划的可行域是凸集。

最优极点

考虑标准形式：

$$ \begin{cases}\min&cx\\s.t.&Ax=b\\&x\geq0&\end{cases} $$

把多面集表示定理代入其中：

$$ \begin{cases}\min&\sum_{j=1}^k\lambda_jcx^{(j)}+\sum_{j=1}^l\mu_jcd^{(j)}=f\left(x\right)\\s.t.&\sum_{j=1}^k\lambda_j=1\\&\lambda_j\geq0,j=1,\cdots,k\\&\mu_j\geq0,j=1,\cdots,l.&\end{cases} $$

若存在 $j$ 使得 $cd^{(j)} \lt 0$，此时可以取 $\mu_j\to-\infty$，则 $f(x)\to-\infty$。

若所有的 d 都满足 $cd^{(j)} \ge 0$，取 $\mu_j = 0, j = 1, 2, \dots, l$，得到

$$ \begin{cases}\min&\sum_{j=1}^k\lambda_jcx^{(j)}=f\left(x\right)\\s.t.&\sum_{j=1}^k\lambda_j=1\\&\lambda_j\geq0,j=1,\cdots,k\end{cases} $$

此时只需要找到 $p = \arg\min_{j}cx^{(j)}$，取 $\lambda_p = 1$, $\lambda_j = 0 (j\ne p)$ 即可得到最大值。

定理2．设线性规划(L)的可行域非空，则

（1）(L)存在最优解的充要条件是对任意的$j$, $cd^{(j)}≥0$, 其中$d^{(j)}$为可行域的极方向。

（2）若(L)存在最优解，则目标函数的最优值可在某个极点达到。

基和基本解

设标准形式中 $\text{rank}(A_{m\times n}) = m = (P_1\ P_2\ \dots\ P_n)$，$Ax = P_1x_1+\dots+P_nx_n$，则可以从 $A$ 的列中取出 $m$ 个 $P_j$组合成一个可逆矩阵 $B$ 称为基，与取出来的 $P_j$ 对应的 $x_j$ 称为基向量。

设 $A = [B\ N]$，$Ax = Bx_B + Nx_N = b$，解得

$$ x_B = B^{-1}b - B^{-1}Nx_N $$

取 $x_N = 0$，此时 $x = \begin{bmatrix}B^{-1}b\\0\end{bmatrix}$ 为 (LP) 的基本解。

若 $B^{-1}b \ge 0$，则 $x$ 称为基本可行解，$B$ 为可行基矩阵，$x_{B_1}, x_{B_2}, \dots, x_{B_m}$ 为一组可行基。

若 $B^{-1}b \gt 0$，则称基本可行解是非退化的，否则是退化的。

基本可行解与极点之间的关系

引理1：对于可行解 $\bar x$， $\bar x$ 是基本可行解的充要条件是 $\bar x$ 的非零分量对应到 $A$ 中的列向量线性无关。

定理2：设 $S$ 是 $(L)$ 的可行域，$\bar x \in S$，则 $\bar x$ 是 $S$ 极点的充要条件为 $\bar x$ 是 $(L)$ 的基本可行解。

思考：本质上是因为“极点”的唯一性，正好对应了基矩阵可逆，求解出来的基本可行解也是唯一的。
从几何意义思考标准形式：1. $Ax=b$ 本质上代表了一个 k 维的子空间，k 是矩阵的秩，如果 k = 1 就是直线，k = 2 就是平面；2. $x\ge0$ 是一组边界，它会截取子空间的一部分，以 k = 2，n = 3 为例，这意味着我们用一个平面去与三维空间的第一卦限相交的部分作为可行域，不考虑退化的情况，通常它是一个 n 条边界的图形，正好对应 n 个变量分别等于 0 的情况。3. $cx$ 不用解释了，这就是一个 n - 1 维的空间。

定理3：设 $S = \lbrace x| Ax=b, x\ge 0\rbrace $ 的方向 $d$ 有 $k$ 个非零分量，则 $d$ 是 $S$ 的极方向 等价于 $d$ 的非零分量对应到 A 的列向量的秩为 k - 1。

基本可行解的存在问题

定理1．如果(LP)有可行解,则一定存在基本可行解.

定理2．如果(LP)有最优解，则存在一个基本可行解是最优解。

单纯形法

设 $A = (B\ N)$，$x=(x_B\ x_N)^T$，则 $Bx_B + Nx_N = b$，取 $x_N = 0$ 得到 $x_B = B^{-1}b$，$f(x) = c_BB^{-1}b$。则 $x = (B^{-1}b\quad 0)^T$ 为基本可行解。

这里有个问题，$B^{-1}b \ge 0$ 一定成立吗？如果不成立那么这就不是可行解。

但是基本可行解未必是最优解，我们考虑 $x_N\ne0$ 的情况。一般地由 $Bx_B + Nx_N = b$ 得到 $x_B = B^{-1}b - B^{-1}Nx_N$，$f(x) = c_Bx_B + c_Nx_N = c_BB^{-1}b - (c_BB^{-1}N - c_N)x_N$。

如果 $c_BB^{-1}N - c_N \le 0$，则 $f(x) \ge c_BB^{-1}b$，当且仅当 $x_N = 0$ 的时候取等。此时 $x = (B^{-1}b\quad 0)^T$ 就是最优解。$c_BB^{-1}N - c_N = (z_i - c_j)_{m+1\le i \le n}$ 为判别数。

假如判别数里面有正数，假设其中最大的正数为 $z_r-c_r$，这就说明我们可以通过增大 $x_r$ 的方式来减小 $f(x)$ 的值。而 $x\ge 0$ 又约束了我的 $x_r$ 不能无限增加，因为 $x_B = B^{-1}b - B^{-1}Nx_N = B^{-1}b - \sum_{j=m+1}^{n}B^{-1}P_jx_j \ge 0$，因此 $B^{-1}P_rx_r \le B^{-1}(b-\sum_{j\ne r, m+1\le j \le n}B^{-1}P_jx_j) \le B^{-1}b$。设 $y_k = B^{-1}P_k$，$\bar b = B^{-1}b$，则此时有 $y_kx_r \le \bar b, \forall 1\le k \le m$。因此 $\max x_r = \min \lbrace \frac{\bar b_k}{y_k}|y_k \gt 0 \rbrace$。

假如所有的 $y_k \le 0$，则 $x_r$ 无上界，从而 $f(x)$ 也没有最大值。

假如存在 $y_k \gt 0$，则我们假设 $x_r = \frac{\bar b_k}{y_k}$ 时取得最大值。此时 $x_k = \bar b_k - y_kx_r = 0$，也就是说原来的基变量 $x_k$ 变成了 0，原来的非基变量 $x_r$ 变成了大于 0 的数。我们就需要把新的 $x_r$ 加入基变量中，$x_k$ 踢出基变量，从而 $f(x)$ 的值变得更小了。

如果某非基变量的检验数为零，则线性规划问题存在多个最优解。

两阶段法

有时候第一个基本可行解不太好求，特别是表格里没有单位矩阵的时候。我们可以用两阶段法简化计算。

第一阶段：引入人工变量 $x_a$，这时候就有单位矩阵了，用单纯形法解出下列问题的最优解：

$$ \begin{cases}&\min e^Tx_a, e=(1\ 1\ \dots\ 1)^T\\&Ax+x_a=b\\&x,(x_a)_{m\times1}\geq0&\end{cases} $$

最优解 $(\bar x\ \bar x_a)^T$。

如果 $\bar x_a \ne 0$，则原方程没有可行解。因为假如原方程有可行解 $x_0$，则$Ax_0 = b$，从而 $x_a = 0$ 成立，为最优解，矛盾。

如果 $\bar x_a = 0$，有两种情况：

（1）如果 $\bar x_a$ 都是非基变量，则 $\bar x$ 就是原来的基本可行解；

（2）如果 $\bar x_a$ 中存在基变量，那么就需要换基，把 $\bar x_a$ 换走。

此时，$\bar x_a$ 都等于 0，

大 M 法

和两阶段法思想类似，但是把两个函数合成一个了。

$$ \begin{cases}\min&cx+Me^Tx_a,e=\left(11\cdots1\right)_{m\times1}^T,M>0\\s.t.&Ax+x_a=b\\&x,x_a\geq0&\end{cases} $$

用单纯形法求解上述问题最优解 $(\bar x^T\ \bar x_a^T)$：

（1）如果 $\bar x_a = 0$，则 $\bar x$ 为原问题的最优解；

（2）如果 $\bar x_a \ne 0$，则原问题无最优解。

函数无界的充要条件：$Ad=0$ 且 $cd < 0$。

（3）不存在最优解（函数无界） 且 $\bar x_a = 0$，说明原问题没有最优解。

（4）不存在最优解（函数无界） 且 $\bar x_a \ne 0$，说明原问题没有可行解。

这个方法怪就怪在 $M $ 是任意大的正数，并不是一个固定值。

单纯形法容易卡在循环之中，达不到最优解。

主要原因是基变量中有取值为 0 的项，即 $\bar b_k = 0$，按照单纯形法肯定会把 $x_k$ 出基，然后换进来另一个 $x_r$，但是你换进来的 $x_r$ 还是等于 0（这样取值显然为基本可行解），导致极点实际上始终不变，目标函数也一直不变。

解决退化的方法有:“摄动法”、“字典序法”、Bland规则等

对偶

对偶问题的定义

第一类对称形式

(L)

$$ \min cx\\ Ax \ge b\\ x \ge 0 $$

第二类对称形式

(D)

$$ \max wb\\ wA \le c\\ w\ge 0 $$

对偶的对偶是原问题。

对于 (D)，可以写成

$$ \min (-b^T)w^T\\ (-A^T)w^T \ge -c^T\\ w^T\ge 0 $$

这个问题的对偶问题是

$$ \max x^T(-c^T)\\ x^T(-A^T)^T \le -b^T\\ x^T\ge 0 $$

也就是

$$ \min cx\\ Ax \ge b\\ x \ge 0 $$

对称形式的对偶问题规划：

（1）min 变成 max

（2）价值系数和右端向量互换

（3）系数矩阵转置

（4）大于等于变成小于等于

原问题的约束方程的个数等于对偶问题中变量的个数，反过来原问题的变量个数就是对偶问题约束方程的个数。

非对称形式的对偶：

$$ \min cx\\ Ax = b\\ x \ge 0 $$

它的对偶形式为

$$ \max wb\\ wA \le c\\ w 无限制 $$

总结：

原问题 对偶问题
$\min$ $\max$
价值系数 右端向量
右端向量 价值系数
系数矩阵 系数矩阵转置
变量 $\le 0$ 约束 $\ge$
变量 $\ge 0$ 约束 $\le$
变量无限制 约束 $=$
约束 $\ge $ 变量 $\ge 0$
约束 $\le $ 变量 $\le 0$
约束 $=$ 变量无限制

对偶问题的基本性质

弱对偶定理：$x^{(0)}, w^{(0)}$ 分别是 (L), (D) 的可行解，则 $cx^{(0)} \ge w^{(0)}b$。

对于对称形式的情况：

$$ cx^{(0)} \ge w^{(0)}Ax^{(0)} \ge w^{(0)}b $$

推论1：若 LP/DLP 有无界解，则其对偶问题无可行解；若 LP/DLP 无可行解，则其对偶问题或者无可行解，或者目标函数值趋于无穷。

推论2：极大化问题的任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的下界。

推论3：极小化问题的任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的上界。

定理2：最优性准则：若 $x^{(0)}, w^{(0)}$ 分别是 (L), (D) 的可行解，并且 $cx^{(0)} = w^{(0)}b$，则 $x^{(0)}, w^{(0)}$ 是各自问题的最优解。

定理3：强对偶定理：如果 (L), (D) 均有可行解，则 (L), (D) 均有最优解，且 (L), (D) 的最优目标函数值相等。

单纯形乘子