单纯形法

单纯形法、标准技术线性规划为解决一个优化的问题,通常涉及一个函数和几个约束表示为不平等。不平等定义多边形地区的解决方案通常是在一个顶点。单纯形法是一个系统化的程序测试的顶点可能的解决方案。

一些简单的优化问题可以通过画画来解决约束图。然而,这种方法只适用于系统涉及两个变量的不平等。在实践中,问题往往涉及方程与成千上万的变量,这会导致一个极端点的天文数字。1947年乔治Dantzig为美国空军数学顾问,设计了单纯形法限制极端点的数量必须检查。单纯形法是最有用的和有效的算法发明的,它仍然是在电脑上使用的标准方法来解决优化问题。

首先,该方法假定一个极端点。(如果没有极端点,单纯形法的一种变体,称为第一阶段,用于查找一个或确定没有可行的解决方案。)接下来,使用一个代数问题的规范,测试确定极端点是最优的。如果最优的测试不通过,一个相邻极端的观点是寻求一个边缘的方向,目标函数的值增加最快的速度。有时你可以沿着一条边没有绑定,使目标函数值增加。如果发生这种情况,程序终止与处方的边缘沿着目标趋于积极