单纯形方法原理

最优化

---

单纯型法是解决线性规划问题的一个方法，其设立的问题：

$$\min\quad{cx} \\ \mbox{s.t}\quad Ax=b \\ \quad x\geq0$$
其中$A \in R^{m\times n}$,$rank(A) = m$,$b\geq 0$
单纯形法的目的其实就是找到使得$f(x) = \sum_{i=0}^nc_ix_i$这个值最小（大）

接下来是推导过程：

- 由于$x$必须要满足条件：

$$Ax=b$$ 所以$x$必须是该方程的一个解。

- 由于$rank(A)=m$，所以一定能将A拆解成两个矩阵的形式，一个矩阵是满秩的，另一个则非满秩。
So:

$$A = [B\quad N]$$
$\Rightarrow\quad$ $Ax=b \quad \Rightarrow \quad [B\quad N] \begin{bmatrix} X_B\\X_N\end{bmatrix} = b \quad \Rightarrow \quad BX_B+NX_N = b$

因为$B$是可逆矩阵，所以方程左右两边同时乘$B^{-1}$
所以：

$$X_B = B^{-1}b-B^{-1}NX_N$$
-现在，对于$Ax = b$的这个条件基本上已经使用结束，现在我们要处理目标函数：
我们设 $$f = \sum_i^nc_ix_i$$ 同样我们将其拆成两个部分： $$f = C_BX_B+C_NX_N$$
带入$X_B$得： $$f = C_B(B^{-1}b-B^{-1}NX_N)+C_NX_N$$ 整理得 $$f=C_BB^{-1}b-(C_BB^{-1}N-C_N)X_N$$ 化简整理得 $$f=f_0-\sum_{j\in R}(C_BB^{-1}p_j-C_j)X_j$$ 其中$p_j$是矩阵$N$的第$j$列，现在我们令 $$z_j = C_BB^{-1}p_j$$ 所以最后的结果为 $$f = f_0-\sum_{j\in R}(z_j-c_j)x_j$$ 因为$x_j$是自由解，只要其保证大于0就行了，所以我们先令$x_j=0$，再取寻找$x_k$当其系数$(z_k-c_k)\geq 0$
$x_k$则去正数时$f$就会变小，此时我十分的希望$x_k$能够足够的大。可是这是做不到的。因为$x_k$会影响$X_B$的取值，而且$X_B\geq 0$，因此，在变换$x_k$的时候，我们需要考虑$X_B$的取值，为了推理方便，我们将$X_B$展开： $$X_B = \begin{bmatrix}\over b_1\\ \over b_2 \\ \vdots \end{bmatrix}+\begin{bmatrix}y_{k1} \\ \\y_{k2} \\ \vdots \end{bmatrix} x_k$$
其中，$\overline b = B^{-1}b$，$y_{k} = B^{-1}p_k$
因此，我们需要保证$X>0$的这个条件，就要求$x_k = min{\frac{\overline b}{y_k}}$，此时该$X_b$
出基，$x_k$进基。反复几次。

原理大致如此接下来的博客介绍算法：
https://www.zybuluo.com/Sherlockyang/note/966696