单纯形方法

单纯形方法是用线性代数解联立方程所用的迭代法求最优解的方法，是线性规划问题的基本算法。它和代数学中解线性联立方程组的高斯消去法极为相似。

简介由George Dantzig发明的单纯形法（simplex algorithm）在数学优化领域中常用于线性规划问题的数值求解。

Nelder-Mead 法或称下山单纯形法，与单纯形法名称相似，但二者关联不大。该方法由Nelder和Mead于1965年发明，是用于优化多维无约束问题的一种数值方法，属于更普遍的搜索算法的类别。这两种方法都使用了单纯形的概念。单纯形是N维中的N+1个顶点的凸包，是一个多胞体：直线上的一个线段，平面上的一个三角形，三维空间中的一个四面体等等，都是单纯形。

基本思想它的基本思想是：采取逐步接近最优解的办法，先求出一个可行解，但它未必是最优者，然后逐步改善可行解，使目标函数值逐步增大(或减小)，直到目标函数达到极值(最大值或最小值)时，该问题就得到了最优解，或判断无最优解。1

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

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

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

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

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

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

最优化过程如果b向量所有元素非负，则显然我们只需要令所有的变量等于0，就可以得到一个可行解。在这种情况下，通过下述最优化过程，我们可以得到该线性规划的最优解，或者指出该线性规划的最优解为无穷大（不存在）3。

任取一个非基变量xe，使得ce>0。

选取一个基变量xd，使得Ad,e>0，且最小化bd/Ad。

执行转轴操作pivot(d, e)，并转到第一步继续算法。

根据bd/Ad的最小性不难证明pivot(d, e)不会破坏b的非负性。因此将所有变量取0值仍然是可行解。同时，根据Δv=ce(bd/Ad),e≥0，我们发现v一定是不降的。这就达到了更新解的目的。

不难发现，算法终止有两种情况：

对于所有的非基变量，c均非正。

对于某一个e，所有的Ad均非正。

可以证明，对于第一种情况，我们已经得到了该线性规划的最优解。当前的v即为答案。严格证明比较复杂，但是直观上是很容易理解的。因为所有的非基变量都是非负的，而所有的c都是非正的，因此只要某个非基变量不为0，就会使得目标函数更小。

对于第二种情况来说，很容易证明此时线性规划的最优解是无穷大。只要让其他所有变量均为0，变量xe为正无穷。由于所有的Ad都非正，因此非基变量的非负性得到保证。同时由于ce>0，目标函数值为正无穷。

本词条内容贡献者为:

任毅如 - 副教授 - 湖南大学