单纯性算法的正确性证明

一个引理

设$I$是一个下标集合。对于每一个$j\in I$，设$\alpha_j$和$\beta_j$是实数，并且令$x_j$是一个实数变量。设$\gamma$是一个实数。

如果对于变量$x_j$的任意设置，我们都有$\sum_{j\in I} \alpha_j x_j = \gamma + \sum_{j\in I} \beta_jx_j$。那么可以推出对于任意的$j\in I$有$\alpha_j = \beta_j$并且$\gamma =0$。

证明：

我们可以令所有的$x_j$都等于$0$，这样就可以推出$\gamma =0$。

对于某一个$j\in I$，我们令$x_j=1$且对于所有的$k\not =j$令$x_k = 0$，就可以得到$\alpha_j = \beta_j $。

---

线性规划弱对偶性

设$\overline x$为原始线性规划问题的一个任意一个可行解，$\overline y$为对偶问题的任意一个可行解，那么有$\sum_{j=1}^n c_j\overline{x}_j\le \sum_{i=1}^m b_i\overline y_i$。

证明：

$$\sum_{j=1}^n c_j\overline x_j \le \sum_{j=1}^n (\sum_{i=1}^m a_{i,j}\overline y_i)\overline x_j\\ =\sum_{i=1}^m (\sum_{j=1}^n a_{i,j}\overline x_j ) \overline y_i\\ \le \sum_{i=1}^m b_i\overline y_i$$

因此，原问题的一组解$\overline x $和对偶问题的一组解$\overline y$如果满足$\sum_{j=1}^n c_j x_j = \sum_{i=1}^m b_i x_i$，那么这个两组解分别是原问题和对偶问题的最优解。

---

线性规划对偶性 && 单纯性算法的正确性证明

首先给出，如何通过单纯性算法最终返回的$z= v’+\sum_{j\in N}c_j’x_j$和$x_i = b_i’-\sum_{j\in N} a’_{i,j}x_j$构造出对应的$y$（其中我们用$N$表示非基变量的集合，$B$表示基变量的集合，$z$是我们要最大化的目标函数）：

$$\overline y _i = \begin{cases} -c'_{n+i} & \text {if } (n+i)\in N\\ 0 & otherwise \end{cases}$$

我们定义对于所有的$j\in B$有$c’_j = 0$。

那么

$$z = v+\sum_{j=1}^n c_j x_j\\ =v'+\sum_{j\in N}c'_j\overline x_j\\ =v'+\sum_{j\in N} c'_j \overline x_j + \sum_{j\in B} c'_j\overline x_j \\ =v'+\sum_{j\in N} c'_j \overline x_j + \sum_{j\in B} (-\overline y_j)\overline x_{n+i}\\ =v'+\sum_{j\in N} c'_j \overline x_j + \sum_{j\in B} (-\overline y_j )(b_j - \sum_{i=1}^n a_{j,i} \overline x_i )\\ =(v'-\sum_{j\in B }b_j\overline y_j) +(\sum_{j\in N} (c'_j + \sum_{i=1}^n a_{j,i}\overline y_j)\overline x_j$$

上式对于任意一组可行解都成立。因此，我们可以得到：

$$v'-\sum_{j\in B} b_j\overline y_j =0\\ \forall j\in B,c'_j +\sum_{i=1}^n a_{j,i}\overline y_j = c_j\\ \because c'_j \le 0\\ \therefore a_{j,i}\overline y_j \ge c_j$$

因此我们的对偶解是一组可行解。因此我们通过单纯性算法得到的就是最优解。