谈一谈|浅谈单纯形法其中奥妙

1单纯形法简介

单纯形法是求解线性规划问题最常用、最有效的算法之一。其基本思路是：先找出可行域的一个顶点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一顶点，并使目标函数值更优；如此下去，直到找到某最优解为止。

单纯形法的原理可以简单理解成将解通过枚举得出来，但是这个方法很巧妙得减少了枚举的次数，这也是单纯形法中很关键的一个步骤：换基迭代。在换基迭代中，主要需要解决两个问题：

（1）、出基变量的确定

（2）、入基变量的确定

在解决这两个问题时，单纯形法给出了明确的定义，可其中原理是什么呢？我们下面来分析一下。

2原理分析

如下是一张初始单纯形表

表2.1标准型初始单纯形表

对于一个标准型线性规划问题

使用矩阵形式表示上面的标准型：

其中，XB构成了初始基变量，因此，初始可行解可以得出

根据矩阵的运算规律，XB=B-1b，所以，初始可行解还可以表示为：

目标函数

由2式可以得出

将5式带入1式，有

其中m代表基变量的个数，Pj参考标准型，结合矩阵的知识，知道

在6式中，选取一个合适的XK，其他的非基变量全为0，只要它的检验数大于0，就可以让函数值增大。每次选择检验数最大正值对应的XK，达到的效果最好，这就是换入变量的确定。

且此时，目标函数变为：

再根据下面中XB必须大于等于0，可以计算出XK的取值范围，

所以，

只要将对应的Xi替换成Xk，函数值就会增大(Ck-Zk)Xk，这就是换出变量的确定。然后一直迭代，直到找到最优解或者判断出无解，就可以解决线性规划问题。

3阅读背景

上述分析思路建立在矩阵的基础上，所以需要一定的线性代数的知识作为支撑，这里只分析了标准型单纯形法的思路，对于改进的单纯形法没有深入，所以在理解时也要结合标准型线性规划问题，对于其他的单纯形法，还需要结合它的使用方法具体分析。