线性规划

线性规划的一般形式：

$$
\begin{align*}
\max c^Tx \\
s.t. \quad Ax\le b \\
\quad\quad x\ge 0
\end{align*}
$$

$$
c^T = (c_1, c_2, …, c_n), b = (b_1, b_2, …, b_m)^T, A = (A_{ij})_{m\times n}
$$

也就是说，线性规划是指：优化函数是线性函数，约束也是线性函数的优化问题

  • 在这里 $x \ge 0 $ 是一个平常的约束
    事实上，对于没有约束的变量$x$, 可以通过变量代换
    $$x = x_1-x_2\quad x_1>0,x_2>0 $$
    得到等价的结果。而对于约束为 $x\le0$的变量，只需取$x’=-x$

  • 在一些情况下，需要更标准的形式 $Ax=b$
    此时，用过添加松弛变量可以进行转换，即：

$$
\begin{align*}
Ax+x’ = b\\
x’\ge 0
\end{align*}
$$

  • 在题目里遇到需要将等式改成不等式的
    有一点点的神奇：
    $$
    \begin{align*}
    Ax=b \Leftrightarrow Ax\le b \cap Ax\ge b\\
    \Rightarrow A(x, -x)^T\le(b, -b)^T
    \end{align*}
    $$令 $x’ = (x,-x)^T$， 就有 $Ax’\le(b,-b)^T$

单纯形法

聊单纯形法之前，我们先添加松弛变量把线性规划转化为标准形式

$$
\begin{align*}
\max c^Tx \\
s.t. \quad Ax= b \\
\quad\quad x\ge 0
\end{align*}
$$

$$
c^T = (c_1, c_2, …, c_n), b = (b_1, b_2, …, b_m)^T, A = (A_{ij})_{m\times n}
$$

然后再看看下面的东西：

1) 理论背景

线性规划的基本原理：z的极大值所对应的x一定在极点处取得

极点 的定义是：对于凸集中的点$a$, $a$ 不是凸集中任意两个不同点的严格凸组合

这是简单的。不严谨的想法：极点就是凸集的边缘，线性规划的最大值总是会在凸集的边缘处取到。而凸集的边缘，也就是尽可能使更多的约束条件恰好成立的x的值。
这引出了下一点：

线性规划的基本可行解是其极点，反之亦然
首先解释基本可行解： 对于 $Ax=b$ , 其中 $A$ 为 $m\times n$ 的矩阵，假设 $r(A) = m$ :

$$
\begin{align*}
A = (A_B, A_N) \quad ——A_B为基矩阵，A_N 为非基矩阵\\
x = (x_B, x_n)^T \quad ——x_B为基变量，x_N 为非基变量\\
\begin{cases}
x_B = A^{-1}_B b \ge 0\\
x_N = 0\\
\end{cases}\quad —— 为基本可行解
\end{align*}
$$

所以什么才是基本可行解？

事实上这里还有基本解的概念，也就是 $ x_B = A^{-1}_B b ,\quad x_N = 0$ 的解，基本可行解就是可行的基本解

或许可以这么理解，约束条件中我们有m个条件与n个变量，由于变量数多于约束条件，它的解是不唯一的。此时，我们从 n 个变量中选择 m 个， 在约束条件中删去了其他 n-m 的变量，从而得到了含有m个变量和m 个等式的方程组， 由于 $r(A) = m$ ，我们可以求出它唯一的解。

对于被删去的 n-m 个变量， 令它们为0， 从而组成一个完整的解

为什么基本解不一定可行？由于添加了松弛变量，为了满足原始的约束条件，松弛变量需要大于等于0，而基变量中可能存在负数的松弛变量，导致这个解不可行。

考虑可行的基本解，非基变量中的松弛变量取零，表示原始的约束条件等号成立。因此基本可行解可以看成在可行域内尽可能的使更多的约束取得等号的解，对应前面所说的极点，我们发现两者是等价的

证极点是基本可行解：

若可行解 $x$ 不是基本可行解，则 $x = (x_1, …, x_k, 0, …, 0)\quad x_i>0, i = 1,…,k$
记 $x_i$ 对应 $A$ 中的列向量为 $p_i$ ，则 $p_1, …, p_k$ 线性相关（否则，$x$ 为基本可行解）
存在 $\lambda _1, …, \lambda _k $ 不全为零， 使得 $\lambda _i p_i +…+ \lambda_k p_k = 0$ 取
$$
\begin{align*}
x’ = x + \epsilon (\lambda_i,…,\lambda_k,0,…,0)\\
x’’ = x - \epsilon (\lambda_i,…,\lambda_k,0,…,0)\\
x \neq x’ \neq x’’\\
Ax’ = Ax + \epsilon(A (\lambda_i,…,\lambda_k,0,…,0)^T) = b\\
Ax’’ = Ax’ = Ax = b
\end{align*}
$$

故 $x$ 不是极点。 同理可证基本可行解是极点

接下来终于可以开始进入单纯形法 

  单纯形法的直观理解，就是从一个基本可行解出发，在不同的基本可行解之间选择，同时使目标函数逐渐达到最优

2)简单例子

​ 先来看个例子吧 (已经添加了松弛变量 $x_3, x_4$ )，我们先不考虑为什么要这么做：

$$
\begin{align*}
\max z = x_1 +2 x_2\\
s.t.\quad x_1+x_2+x_3 = 3\\
\ \ x_2+x_4 = 1\\
x_1, x_2, x_3, x_4 \ge 0
\end{align*}
$$

方程形式
初始基本可行解 $x^{(0)} = (0,0,3,1)^T, z = 0$
用非基变量表示基变量与目标函数
这些方程与约束条件与目标函数是等价的，而这么写的意义是：基变量用非基变量和目标函数表示，当非基变量取0时，等式中的常数即为基变量（目标函数）的值。
$$
\begin{align*}
\begin{cases}
x_3 = 3-x_1-x_2\\
x_4 = 1-x_2\\
z = x_1 +2x_2
\end{cases}
\end{align*}
$$

下一个基本可行解，让 $x_2$ 入基，$x_4$ 出基：
实际的做法是将入基的变量用现在的非基变量表示 $ x_2 = 1-x_4$，同时修改原来的基变量与目标函数。类似的，由于非基变量取0，新的等式中的常数项表示基本可行解中基变量的值与目标函数的值。

$$
\begin{align*}
x^{(1)} = (0,1,2,0)^T, z = 2\\
\begin{cases}
x_3 = 2-x_1-x_4\\
x_2 = 1-x_4\\
z = x_1 -2x_4+2
\end{cases}
\end{align*}
$$

接着令 $x_1$ 入基，$x_3$ 出基：

$$
\begin{align*}
x^{(2)} = (2,1,0,0)^T, z = 4\\
\begin{cases}x_1 = 2-x_2+x_4\\
x_2 = 1-x_4\\
z = 4-x_3 -x_4\end{cases}
\end{align*}
$$

到这里，我们看到用非基变量表示的目标函数非基变量的系数均小于等于0 ( 这里的系数我们称为检验数)，说明此时达到最优解。

表格形式
表格形式更容易使用，然而更难理解单纯形法的原理：
选取基变量 $x_3, x_4$ ，表格的第一行表示目标函数用非基变量表示，即 $x_1 + 2x_2 = z$ 。
下面各行则表示用非基变量表示基变量，如第一行表示 $x_1+x_2+x_3 = 3$ 。
为了使基变量由非基变量表示而与其他基变量无关，我们应使基变量的列为单位矩阵。
由于基本可行解中非基变量取0，因此表格的最后一列即为当前基本可行解中基变量的值。

1 2 0 0
$x_3$ 1 1 1 0 3
$x_4$ 0 1 0 1 1

让 $x_2$ 入基，$x_4$ 出基：
首先 (把$x_4$ 改为 $x_2$ ) 使当前的基变量相互独立，即$x_2, x_3$ 组成的矩阵为单位矩阵
接着令第一行中基变量所在的列为0，即消去基变量，用非基变量表示目标函数
注意， 这里得到的结果应该是 $ x_1 - 2x_4 = z-2$ ,因此，右上角表示的是目标函数的相反数

1 0 0 -2 -2
$x_3$ 1 0 1 -1 2
$x_2$ 0 1 0 1 1

让 $x_1$ 入基，$x_3$ 出基：

0 0 -1 -1 -4
$x_1$ 1 0 1 -1 2
$x_2$ 0 1 0 1 1

检验数 (第一行除基变量对应的列与最后一列的数字) 均小于等于0，达到最优解，为4 (右上角的相反数)

事实上表格形式与方程形式是对应的

3) 原理解释

这里需要解决两个问题：

  • 怎么使目标函数更优 —— 如何确定入基和出基的变量
  • 怎么判断目标函数达到最优 —— 为什么检验数均为负数即达到最优

我们首先引入符号表示：

$A = (A_B, A_N)$ 可行解 $x=(x_B, x_N)^T$ ，有

$$
\begin{align*}
x_B &= A_B^{-1}b-A_B^{-1}A_Nx_N\\
z &= c^Tx = c_B^Tx_B + c_N^Tx_N = c_B^TA_B^{-1}b + (c_N^T-c_B^TA_B^{-1}A_N)x_N
\end{align*}
$$

记 $\overline A = A_B^{-1}A_N = (\overline a_{ij})_{m\times (n-m)}$ ， $\overline b = A_B^{-1}b $

用表格形式表示规划问题：

$c_B \quad \quad\quad\quad c_N$
$x_B$ $A_B \quad \quad\quad\quad A_N$ b

通过行变换得到基本可行解

$0 \quad \quad\quad\quad c_N-c_B^TA_B^{-1}A_N$ (检验数) $-c_B^TA_B^{-1}b$
$x_B$ $I_{m\times m} \quad \quad\quad A_B^{-1}A_N$ $A_B^{-1}b$

在前面我们已经知道，最优解一定在基本可行解中取得，因此只需要尝试所有基本可行解就可以找到最优解。由于基本可行解得非基变量取 0， 因此目标函数的值为 $z=c_B^TA_B^{-1}b$ ,即表格右上角相反数。

回忆表格形式的计算过程，改变目标函数的是第二步：令第一列中基变量所在的列为0。此时基变量所在的矩阵已经是单位矩阵，因此当检验数为负数时，我们需要向目标函数的相反数加上 检验数的绝对值 *基变量的值，而基变量的值恒大于等于0，因此目标函数只能减小，不会再优化，达到最优解。一样的道理，对于入基的变量，我们选择检验数大于0的变量，从而使目标函数的相反数减小

那么出基呢？ 事实上，出基的变量更重要的是保证新解可行，也就是基变量的值大于等于0。
设出基的变量为$x_k$ ，入基的变量为$x_j$ 。对于入基变量，它的值应该为$\frac{\overline b_k}{\overline a_{kj}}$ ， 对于其他变量$x_i$ ，他们需要减去 $\overline a_{ij} \frac{\overline b_k}{\overline a_{kj}} $ 。由于 $\overline b_k >0$ ，首先需要满足$\overline a_{kj} > 0$ 。为了使其他变量保持大于等于0，需要使 $\overline b_k > \overline a_{ij} \frac{\overline b_k}{\overline a_{kj}} $ 即 $\frac{\overline b_k} {\overline a_{kj} }> \frac{\overline b_k}{\overline a_{kj}} (若\overline a_{kj} > 0)$
因此，我们一般选取 $$\min_{\overline a_{kj}>0} \frac{\overline b_k}{\overline a_{kj}}$$ 对应的变量出基

那么还有一个问题，如果还没有达到最优（存在检验数$\sigma_j$ 大于0）又不存在 k 使 $\overline a_{kj} > 0$ 怎么办？
事实上，此时没有有限最优解：由于检验数$\sigma_j$ 大于0，当变量$x_j$增大时，目标函数会随之增大。而 $x_B = A_B^{-1}b-A_B^{-1}A_Nx_N$ ，变量$x_j$增大，每个基变量也会增大而不会影响其可行性。因此此时目标函数无界

好了，如果你看到了这里，那么上面两个问题应该解决了（

两阶段法

要使用上面的单纯形法，我们首先需要得到一个基本可行解
但得到一个基本可行解并不是简单的

两阶段法就是将线性规划问题转变为找到基本可行解与找到最优解分成两阶段解决

$$
\begin{align*}
\max z = c^T x\\
s.t.\quad Ax = b\\
x \ge 0
\end{align*}
$$

对于上面的线性规划问题，我们引入人工变量 $\overline x$:

$$
\begin{align*}
\min \sum_{i - i}^m \overline x_i\\
s.t. Ax + \overline x = b\\
x, \overline x \ge 0
\end{align*}
$$

得到新的线性规划问题，可以发现，当该问题的最优解为零时，得到的$x$ 为原问题的一个可行解；当问题最优解大于零时，原问题无解。
同时，新的问题的可行解是显然的 $x = 0, \overline x = b$。
(存在 b < 0 怎么办？事实上人为的要求 b > 0 不会改变问题)

由于原问题中人工变量是不存在的，在得到新问题的最优解时，还需要保证人工变量均为非基变量：
若存在在基变量中的人工变量所对应的原变量系数不为零，则将原变量入基，进入第二阶段的优化；
若在基变量中的人工变量所对应的原变量系数全为零，说明存在冗余的约束，将该行删去进入第二阶段的优化。

冗余的约束是什么？？
我们可以看到，每一个人工变量都对应一个约束 $\overline x = b-Ax$ 。
现在人工变量所对应的原变量系数全为零，说明这个人工变量可以只由其他的人工变量表示，也就是这一条约束可以由其他的约束表示， 那么这条约束就是冗余的。

举个例子：

$$
\begin{align*}
2x_1 -x_2 +x_3 = 4\\
x_1 + x_2 +x_3 = 6\\
3x_1 +2x_3 = 10
\end{align*}
$$

可以看出第三条约束等于前两条之和，因此是冗余的。

再看单纯形法-KKT条件

另外一门课也讲了单纯形法，补充一下

KKT 条件详见 凸优化-Lagrange对偶

对于线性规划问题

$$
\begin{align*}
\min c^Tx \\
s.t. \quad Ax= b \\
\quad\quad x\ge 0
\end{align*}
$$

它的KKT条件为：

$$
\begin{align*}
-x&\le0 \\
Ax - b &= 0\\
\lambda &\ge 0\\
(-x)_i\lambda_i &= 0, i = 1,…,n\\
-c - \lambda + A^T\nu &= 0\\
\end{align*}
$$

整理一下为

$$
\begin{align*}
x&\ge0 \\
Ax - b &= 0\\
\lambda &\ge 0\\
x_i\lambda_i &= 0, i = 1,…,n\\
\lambda + A^T\nu &= c\\
\end{align*}
$$

满足 KKT 条件即为最优解，此时

$$
\begin{align*}
A^T\nu + \lambda = c \Rightarrow \left[
\begin{array}{c}
A_B^T\\ A_N^T
\end{array}
\right]\nu + \left[
\begin{array}{c}
\lambda_B\\
\lambda_N
\end{array}
\right] = \left[
\begin{array}{c}
c_B\\ c_N
\end{array}
\right]
\end{align*}
$$

令 $\lambda_B = 0$ （即保持表格第一行中基变量的分量变为0）, 可以得到

$$
\begin{equation}
A_B^T\nu = c_B, \quad A_N^T\nu + \lambda_N = c_N.
\tag{13.19}
\end{equation}
$$

由于 $A_B$ 奇异，可以得到 (即将表格中的基变量的矩阵变换为单位阵)

$$
\begin{equation}
\nu = A_B^{-T}c_B. \tag{13.20}
\end{equation}
$$

$$
\lambda_N = c_N - A_N^T\nu = c_N - A_N^TA_B^{-T}c_B = c_N - (A_B^{-1}A_N)^Tc_B
$$

即检验数。（我好像哪里弄错了一个转置所以看起来不太一样QAQ）

因此，当 $\lambda_N \ge 0$ 时，满足 KKT 条件，达到最优解。

END