对偶单纯形法是直接解?对偶单纯形法是直接解对偶问题 _生活百科

对偶单纯形法是指从对偶可行性逐步搜索出原始问题最优解的方法。
由线性规划问题的对偶理论，原始问题的检验数对应于对偶问题的一组基本可行解或最优解；原始问题的一组基本可行解或最优解对应于对偶问题的检验数；原始问题约束方程的系数矩阵的转置是对偶问题约束条件方程的系数矩阵。

文章插图
对偶单纯形法的操作与单纯形法恰相反，它先确定换出变量、在确定换入变量，除此外的矩阵表示、检验数含义等都与单纯形法相同。不同的是，单纯形法要求任一表中b列的数都为负值，对偶单纯形法却不一定。
对偶单纯形方法（dualsimplexmethod）纯形方法的一种对称变形．对于原单纯形方法而言，在迭代过程中始终保持相应的解对原问题是可行的，并不断改善对偶问题解（即判别系数）的可行性，直至可行．而对偶单纯形方法则是始终保持对偶问题的解的可行性，并不断改善原问题解的可行性，直至满足原问题。

文章插图
【对偶单纯形法是直接解?对偶单纯形法是直接解对偶问题】对偶单纯形法是指从对偶可行性逐步搜索出原始问题最优解的方法。由线性规划问题的对偶理论，原始问题的检验数对应于对偶问题的一组基本可行解或最优解；原始问题的一组基本可行解或最优解对应于对偶问题的检验数；原始问题约束方程的系数矩阵的转置是对偶问题约束条件方程的系数矩阵。
（1）选择b列为负基变量作为换出变量（一般选最小的）；
（2）对于系数为负的换出变量，用检验数除以系数计算θ值；

文章插图
（3）选择θ值最小的变量作为换入变量。
（4）直到所有的基变量b列为非负，且检验数达到最优情形时结束，得到最优解。
当然，并不是什么时候都能顺利地进入（4），可能会遇到以下情形。
首先，可能遇到b列数全非负，但检验数没有最优的情况。b列一旦变为非负，就已经可以用一般的单纯形法求解了，实际上这是非可行基到可行基的过渡。一般对偶单纯形法和单纯形法可以综合使用，更快求解。