求解线性规划的单纯形法（这玩意不是都能网络流写的吗（谁跟你这样说的

首先是线性规划的定义

利用松弛变量将约束中的不等式换成等式，则得到

在约束等式左边的 $x[n+1]…x[n+m]$ 叫做基变量，等式右边的 $x[1]…x[n]$ 叫做非基变量

线性规划有三种情况：有解、无解（不存在一个满足限制条件的解）、无界（目标函数可以无穷大）

显然当 $b_i$ 非负时令所有基变量为 $b_i$，非基变量为0，即可得到一个满足条件的初始解

有个重要的操作叫转轴（Pivot）

我们可以把一个基变量 $x[b]$ 和非基变量 $x[n]$ 互换，用 $x[b]$ 和其他非基变量代换这个 $x[n]$，这样 $x[b]$ 就成了非基变量，而 $x[n]$ 成了基变量

为了最大化目标函数，我们考虑不停地找一个系数为正的非基变量，然后增大这个量

最优化的具体过程：

举个栗子：

找到 $x1$，然后限制一为 $x1 \le 30$，限制二为 $x1 \le 12$，限制三为 $x1 \le 9$，所以我们用 $x1$ 代换下界最紧的 $x6$

得到下面的新线性规划：

然后找到 $x3$，得到：

增大 $x2$ 得到

最后得到最大值为28，此时 $x1=8,~x2=4,~x3=0$

但是，在 $bi$ 为负的时候，把所有基变量设为0不是一组合法的初始解

我们选择一个 $bi$ 为负的基变量 $x[i+n]$，然后我们在该约束右边找一个系数为正的非基变量，然后进行转轴操作，如果没有系数为正显然就无解了

时间复杂度的话 Pivot 操作的复杂度为 $O(nm)$，但是最优化操作中 Pivot 操作的调用次数可能会成为指数级

其他多项式时间算法：

椭球算法 $O(n^6 m^2)$

内点算法 $O(n^{3.5}m^2)$

改进的内点算法 $O(n^{3.5}m)$

例题：UOJ #179. 线性规划

其余科学阅读资料：

http://www.cnblogs.com/zzqsblog/p/5457091.html