Question

对偶单纯形法求解过程

Answer 1

方法/步骤

• 1

  建立初始单纯形表，计算检验数行；

• 2

  基变化，先确定换出变量——解答列中的负元素（一般选最小的负元素）对应的基变量出基。然后确定换入变量，原则是: 在保持对偶可行的前提下，减少原始问题的不可行性；

• 3

按主元素进行换基迭代 (旋转运算、枢运算)，将主元素变成1，主元列变成单位向量，得到       新的单纯形表。循环以上步骤，直至求出最优解。

总结

1.单纯形法的求解过程就是:在保持原始可行的前提下(b列保持≥0)，通过逐步迭代实现对偶可行(检验数行≤0)。 

2.对偶单纯形法思想就是:换个角度考虑LP求解过程:保持对偶可行的前提下(检验数行保持≤0) ，通过逐步迭代实现原始可行(b列≥0，从非可行解变成可行解)。



请点击输入图片描述

资料：

对偶单纯形法是指从对偶可行性逐步搜索出原始问题最优解的方法。

对偶单纯形方法纯形方法的一种对称变形．对于原单纯形方法而言，在迭代过程中始终保持相应的解对原问题是可行的，并不断改善对偶问题解（即判别系数）的可行性，直至可行。而对偶单纯形方法则是始终保持对偶问题的解的可行性，并不断改善原问题解的可行性，直至满足原问题。

在求解常数项小于零的线性规划问题时，可以把原始问题的常数项视为对偶问题的检验数，原始问题的检验数视为对偶问题的常数项。

优缺点

1、对偶单纯形法的优点： 不需要人工变量；当变量多于约束时，用对偶单纯形法可减少迭代次数。

2、对偶单纯形法缺点： 在初始单纯形表中对偶问题是基可行解，这点对多数线性规划问题很难做到。