前段时间参加了华为的2017软件精英挑战赛，用到了单纯形算法求解线性规划问题，学习了正单纯形，对偶单纯形以及割平面法并用C语言实现了完整的simplex算法。

单纯形算法是用来求解线性规划问题的，其被用在了众多SMT Solver中，如Yices, Z3等，都是基于的单纯形算法，其算法效率在最坏情况下为指数级别，不过实现证明其效率在大多数情况下都是令人满意的。

max{b+∑1≤k≤nckxk}

∑1≤k≤nA1xk≤b1 … ∑1≤k≤nAmxk≤bm x1,...,xn≥0

对于 b1,...,bm≥0 的情况，可使用正单纯形算法求解,对于存在 bi0 ,若不存在(目标式已经无法再继续增大)，跳转到第4步 2.找到 minbiAi ,即限制条件最强的一组式子 3.交换 xk 和 yi , xk 变为新的基变量， yi 变为新的非基变量，将其他式子中的 xk 替换为新的值，然后回到第1步 4.将所有的非基变量取0值，即可算出所有的基变量的值以及目标式的最大值，算法结束

如上图所示，为7个限制不等式所构成的凸多面体，每个限制条件可看成正凸多面体的一个面，凸多面体的内部(包括表面)即为可行解区域。可以证明，最优解如果存在，则一定在凸多面体的顶点上。对于三维空间来说(更高维空间可类似推广)，某个顶点比为三个或以上的平面的交点，这个交点满足对应相交平面的限制不等式。如点A，同时满足式子②③⑦。 算法中第3步中的交换因子(pivot)，可以看成是从凸多面体的一个顶点走向另一个顶点。

在标准形式(Slack Form)中，如果 bm