Question

单纯形法求解过程

Answer 1

单纯形法求解过程如下：

单纯形法是求解线性规划问题最常用、最有效的算法之一。单纯形法最早由George Dantzig于1947年提出，近70年来，虽有许多变形体已经开发，但却保持着同样的基本观念。如果线性规划问题的最优解存在，则一定可以在其可行区域的顶点中找到。

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

原单纯形法不是很经济的算法。1953年美国数学家G.B.丹捷格为了改进单纯形法每次迭代中积累起来的进位误差，提出改进单纯形法。

其基本步骤和单纯形法大致相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数。这样做可以减少迭代中的累积误差，提高计算精度，同时也减少了在计算机上的存储量。

方法步骤：

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

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

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

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

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