说说线性规划

如上图，在初中时我们都做过这样的题，给定一些约束条件，求某个目标函数的最大值。相信这个问题对于大家都很容易，把图画一下，很容易就看出来了。但是，如果参数多一点，如下图，参数就多了两个，感觉就没法下手了。所以今天就来说说一种解法--单纯型法(Simplex Method)。

01一个例子

如果线性规划有最优解，那么必然在可行域的顶点上达到最优。例如图1中，黄色部分是其可行域，目标函数的最优解在顶点（3，4）处。单纯型法的思想就是随机从一个顶点（称为基本可行解）开始，去找一个更好（目标函数比上一次更优）的顶点，直到到达最优解。

在用单纯型法求解的时候，需要先将线性规划的一般形式化为标准形。

接下来，就用图1的例子来说说单纯型法的解算过程。

这个基可行解对应着图一中黄色可行域的顶点（0,1），显然不是最优解，所以便要判断何时到达最优解。

只有当目标函数中非基变量对应的系数都小于0，才到达最优解，哪怕存在一个大于0的系数，都能使目标值z增大。

整个过程其实就是一个换基变量迭代求解的过程，所以当变量个数特别大时，这样求解的效率还是挺低的。单纯型法对于求解小规模线性规划还是可以的，对于大规模线性规划，可以采用列生成算法(Column Generation Algorithm)求解。

02算法测试结果

图1例子测试结果。

源码请后台回复“单纯型法”。

▼更多精彩推荐，敬请关注我们▼