在算法导论随笔(十五)：线性规划与单纯形算法（上篇：基本概念）中，我介绍了解决线性规划问题的单纯性算法所用到的一些概念。在这篇文章中我们来看看算法的一些实现的细节。单纯形算法的Python实现已经上传到我的GitHub仓库https://github.com/tjfy1992/Simplex中。下载后在PyCharm中打开工程即可。
上篇文章中提到过，单纯形算法的目的是将一个标准型的线性规划问题转化为松弛型，并且对松弛型进行一系列转化，使得该松弛型的目标函数中，所有变量的系数都为负数。此时该松弛型的基本解即是该问题的最优解，也就是算法的输出。这个对松弛型的转化的过程，称为转动。
转动的本质上其实就是把松弛型的等式约束中左侧的变量（基本变量）替换为右侧的变量（非基本变量）。比如有一个等式约束
x 0 = 1 − x 1 x_0 = 1 - x_1 x0=1−x1
那么我们就可以把x0移到等式右侧，把x1移到等式左侧，也就是
x 1 = 1 − x 0 x_1 = 1 - x_0 x1=1−x0
接着我们把目标函数和等式约束中所有的x1都替换为1 - x0。这个过程就是一个转动。
下面给出一个具体的例子：
上图中，我们把约束
x 5 = 1 − x 1 + x 2 x_5 = 1 - x_1 + x_2 x5=1−x
