单纯形法的理解
2016-08-02 17:57阅读：
每个线性规划问题（通过添加剩余、松弛、人工变量）都可以转化成如下标准形式：
由矩阵A和b构成的可行域是凸的，有着多个顶点。简单起见，如在二维情况下，可表示如下：
当把矩阵A划分为基矩阵B和非基矩阵N时，相应的基变量取值为：
非基变量的取值为0.可知知道，不同的B对应着不同的基变量取值。当基变量和非基变量都满足非负的约束时，基变量和非基变量构成的解即成为基本可行解。
由上图可知，线性规划的可行域存在着顶点，而这里有两个定理：
定理1：线性规划问题的每一个基本可行解都对应着可行域的一个顶点；（当B不同时，基本解的取值也就不同，
也就对应着不同的顶点）
定理2：若线性规划问题有最优解，则一定存在一个基本可行解是最优解；
定理3：若线性规划问题有最优解，则目标函数的最优值一定可以在可行域的某个顶点上达到。
（如上图所示，
图中的虚线为目标函数值取值相同的等值线，按箭头方向递增，可见在图示的情况下，最优解在左下角
的箭头处取得，即其中一个顶点；当然，若虚线，即等值线与最优解所在直线平行，则不难得出，该直
线的两端同样为可行域的两个顶点，此时，最优解同样可以在这两个顶点上取得）
通过以上的分析，我们知道，一个线性规划问题的最优值可以通过沿着可行域的顶点去寻找，这正是单纯形法的思想。当当前所在的顶点不是最优解时，即非基变量的检验数：
不满足非负时，进行进基和出基变量的选择，即进入到下一个更优的可行解。
（1）进基变量的选择原则：
即选择检验数最小的对应的非基变量作为进基变量。
（2）出基变量的选择原则：
经过一轮进出基变换后，基矩阵B和非基矩阵N对换一列元素，其余不变，新形成的B仍然是可逆的。
单纯形法的迭代过程就是不断地重复上述的进出基变换而已，达成的效果就是不断的从当前的顶点进入到下一个更接近最优解的顶点，从而最终达到最优解（即所有的检验数都非负）。
最后，推荐两本书：蒋金山
《最优化计算方法》 -华南理工大学出版社
Jorge Nocedal 《Numerical
Optimization》
蒋金山的介绍的比较通俗易懂，上手快；第二本英文书，但也很易读，与第一本角度不同，讲得很透彻，而且非常容易就把算法转化为程序，此外这本书是优化领域的经典书籍。
