单纯形法？什么是单纯形法

一、什么是单纯形法

基本含义：

单纯形法是求解线性规划问题最常用、最有效的算法之一。

单纯形法最早由GeorgeDantzig于1947年提出，近70年来，虽有许多变形体已经开发，但却保持着同样的基本观念。

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

二、管理运筹学单纯形法

单纯形法的基本思想

单纯形法是一种多变量函数的寻优方法。其主要思想是先找一个基本可行解，判断是否为最优解。如果不是则找另外一个解，再进行判定，如此迭代运算，直至找到最优解或者判定其无界。

单纯形法的特点

单纯形法是一种直接、快速的搜索最小值方法，其优点是对目标函数的解析性没有要求，收敛速度快，适用面较广。

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

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

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

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

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

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

三、原始单纯形法的优缺点

一、单纯形法：

1、优点：把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。用于优化多维无约束问题的一种数值方法，属于更普遍的搜索算法的类别。

2、缺点：约束条件中存在大于或等于约束：将约束两边取负。