【什么是单纯形法-图】百科知识点

学习生活中有很多内容需要大家了解，为了开阔大家的知识面，下面学大教育网为大家带来【什么是单纯形法-图】百科知识点，希望大家能了解好这些百科知识。

原单纯形法

线性规划问题是研究在线性约束条件下，求线性函数的极值问题。线性规划是运筹学的一个重要分支， 也是最早形成的一个分支。线性规划的最优性条件，又称为Karush-Kuhn-Tucker(KKT)条件。不等式约束问题的必要和充分条件初见于卡罗需(William Karush)的博士论文，之后在一份由W.库恩(Harold W. Kuhn)及塔克(Albert W. Tucker)撰写的研讨生论文出现后受到重视。

线性规划的集大成者是G.B.丹齐克(George Bernard Dantzig)。1947 年，面对美国制定空军军事规划时提出的问题，丹齐克首次提出了单纯形法来解决这类极值问题的求解。单纯形法是年由创建的对所有一般线性规划问题的最早的可行算法。[2] 1953年，他又提出了改进单纯形法。

但原单纯形法不是很经济的算法。许多数学家在随后提出更有效率的算法，如改进单纯形法、对偶单纯形法等。

改进单纯形法

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

对偶单纯形法

1954年美国数学家C.莱姆基提出对偶单纯形法(Dual Simplex Method)。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。设原始问题为min{cx|Ax=b，x≥0}，则其对偶问题(Dual Problem)为 max{yb|yA≤c}。当原始问题的一个基解满足最优性条件时，其检验数cBB-1A-c≤0。即知y=cBB-1(称为单纯形算子)为对偶问题的可行解。所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。

下山单纯形法

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

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

【什么是单纯形法-图】百科知识点大家已经阅读过了，学大教育网将为大家介绍更多的百科知识，希望大家能记忆好这些内容。