单纯形法

数学术语

单纯形法是求解线性规划问题最常用、最有效的算法之一。单纯形法最早由 George Dantzig于1947年提出，近70年来，虽有许多变形体已经开发，但却保持着同样的基本观念。如果线性规划问题的最优解存在，则一定可以在其可行区域的顶点中找到。基于此，单纯形法的基本思路是：先找出可行域的一个顶点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一顶点，并使目标函数值更优；如此下去，直到找到某最优解为止。

基本单纯形法

单纯形法的基本想法是从线性规划可行集的某一个顶点出发，沿着使目标函数值下降的方向寻求下一个顶点，面顶点个数是有限的，所以，只要这个线性规划有最优解，那么通过有限步迭代后，必可求出最优解。

为了用迭代法求出线性规划的最优解，需要解决以下三个问题：

(1)最优解判别准则，即迭代终止的判别标准；

(2)换基运算，即从一个基可行解迭代出另一个基可行解的方法；

(3)进基列的选择，即选择合适的列以进行换基运算，可以使目标函数值有较大下降。

改进单纯形法

原单纯形法不是很经济的算法。1953年美国数学家G.B.丹捷格为了改进单纯形法每次迭代中积累起来的进位误差，提出改进单纯形法。其基本步骤和单纯形法大致相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数。这样做可以减少迭代中的累积误差，提高计算精度，同时也减少了在计算机上的存储量。

对偶单纯形法

对偶单纯形法是使用对偶理论求解线性规划问题的一种方法，而不是求解对偶问题的一种方法。与对偶单纯形法相对应，已有的单纯形法称为原始单纯形法。

原问题与对偶问题解之间的对应关系：即原问题单纯形表的检验数行对应其对偶问题的一个基本解。单纯形法求解的基本思想是：在整个迭代过程中，始终保持原问题的解是可行解，而对偶问题的解可以是非可行解，当对偶问题的解由非可行解变为可行解，也就是原问题的检验数行都满足小于等于零时，原问题取得了最优解。而对偶单纯形法的基本思想是：在整个迭代过程中，始终保持对偶问题的解是可行解，原问题的解可以是非可行解，当原问题的解由非可行解变为可行解时，对偶问题取得了最优解。所以，对偶单纯形法的实质就是在保证对偶问题可行的条件下向原问题可行的方向迭代。

下山单纯形法

数学优化中，由George Dantzig发明的单纯形法是线性规划问题的数值求解的流行技术。有一个算法与此无关，但名称类似，它是Nelder-Mead法或称下山单纯形法，由Nelder和Mead发现（1965年），这是用于优化多维无约束问题的一种数值方法，属于更一般的搜索算法的类别。

这二者都使用了单纯形的概念，它是N维中的N+1个顶点的凸包，是一个多胞体：直线上的一个线段，平面上的一个三角形，三维空间中的一个四面体，等等。

求解流程

如果线性规划问题存在最优解，则一定有一个基可行解是最优解。因而线性规划问题的求解，就是要从诸多的基可行解中找到最优解。

利用单纯形法求解线性规划问题的解题思路是：确定初始基可行解，即从可行域的个顶点出发，判断该顶点是否为最优解，若是最优解则问题求解结束；否则寻找新的基可行解，即转换到另一个顶点(转换的目的是优化目标函数值)，再判断该顶点是否为最优解，如此循环往复，直到使目标函数值达到最大为止，而使目标函数值达到最大的基可行解即为问题的最优解。该过程如图1所示。

方法步骤

单纯形法的一般解题步骤可归纳如下：

(1)把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。

(2)若基本可行解不存在，即约束条件有矛盾，则问题无解。

(3)若基本可行解存在，以初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。

(4)按步骤3进行迭代，直到对应检验数满足最优性条件(这时目标函数值不能再改善)，即得到问题的最优解。

(5)若迭代过程中发现问题的目标函数值无界，则终止迭代。

用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解。

全国各地天气预报查询

上海市

市辖区

云南省