对偶单纯形法（Dual Simplex Method）是指从对偶可行性逐步搜索出原始问题最优解的方法。由线性规划问题的对偶理论，原始问题的检验数对应于对偶问题的一组基本可行解或最优解；原始问题的一组基本可行解或最优解对应于对偶问题的检验数；原始问题约束方程的系数矩阵的转置是对偶问题约束条件方程的系数矩阵。所以，在求解常数项小于零的线性规划问题时，可以把原始问题的常数项视为对偶问题的检验数，原始问题的检验数视为对偶问题的常数项。

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

所谓满足对偶可行性，即指其检验数满足最优性条件。只要保持检验数满足最优性条件前提下，一旦基解成为可行解时，对偶问题和原问题均可行，由强对偶性证明，二者均有最优解。

设原始问题的标准形式为max{cx|Ax=b，x≥0}，则其对偶问题(Dual Problem)为 min{yb|yA≤c}。当原问题的一个基解满足最优性条件时，其检验数小于等于0，当σ=cj-zj=cj-CBB-1A≤0时，既有 或 ，即知单纯形算子y=CBB-1为对偶问题的可行解。换而言之，只要保证检验数σ≤0，则对偶问题一定存在可行基B。

在初始单纯形表中，一般此可行基B都为单位矩阵I，这时候只要能够保持检验数持续小于等于0迭代下去，通过变换到一个相邻的目标函数值较小的基可行解（因为对偶问题是求目标函数极小化），并循环进行，一到XB=B-1b≥0时，原问题也为可行解。这时，对偶问题和原问题均为可行解，而且两者的可行解就是最优解，这就是对偶单纯形法求解线性规划的基本思路。

一旦最终基变量XB≥0，原问题也满足最优解条件的原因是：对偶问题的最终单纯形表中的基变量XB=B-1b和原问题的最终单纯形表中的检验数的相反数CBB-1取值相等，不难观察到原问题的检验数σ=cj-zj-CBB-1=-B-1b≤0，其检验数满足最优性条件。（注：这里的B并不是同一个矩阵，它们是各自问题的初始可行基，但CB和b在本质上是同一个向量。）

虽然，本方法借鉴了对偶理论的思路，但是它是求解原问题而非对偶问题的一个方法。而且，一般用对偶单纯形法解决的是原始问题是极小化问题，min{cx|Ax=b，x≥0}，但是只要先标准化为max{cx|Ax=b，x≥0}即于上面一致。

设对某标准形式的线性规划问题

1.做出单纯形表

存在一个对偶问题的可行基B，不妨设B=（P1，P2，···，Pm），列出它的初始单纯形表。

表中必须有的最后一行的检验数σj=cj-zj≤0（j=1,···,n),bi=(i,···,m)的值要求为部分为负数。当对i=1,m,有bi≥0时，即表中原问题和对偶问题均为最优解。否则，通过变化一个基变量，找出原问题的一个目标函数值较小的相邻基解。

2.确定换出基的变量（离基变量）

因为总存在<0的bi，选取数值最小的作为为第r行，令br=min{bi}，其对应变量xr为换出基的变量。

3.确定换入基的变量（入基变量）

（1）为了使下个表中第r行基变量为正值，只有对应的arj<0(j=m+1,···,n)的非基变量才可以考虑作为换入基的变量。为了消除原问题的基解不可行性，变换后的b应该变成正数，故能够成为主元素arj的应该小于零，意味着这第r行的凡是为非负的元素在判别的是否为主元素时不必考虑。

（2）为了使下一个表中的对偶问题的解仍为可行解，选取检验数与对应变量arj中的比值最小的那个变量作为主元素，令。如果有多个值时任选其一。

其中，称为ars为主元素，主元素对应的那一列的变量xs为换入基的变量。如果aij≥0对于所有的非基变量xj成立，则问题没有可行解。

3.用换入变量替换换出变量，得到一个新的基。

对新的基再检查是否所有bi=(i,···,m)≥0。如是，则找到了两者的最优解，如为否，则返回到第一步再循环进行。

分为两者情况讨论满足最小比值法时选取主元素时，可以保证一个表中的检验数为(cj-zj)≤0（对j=1,···,n）

设下一个表中的检验数为(cj-zj)'，有：

(a)对arj≥0，因cj-zj≤0，故(cj-zj)/arj≤0，主元素ars≤0，(cs-zs)/arj≥0，由此可知方括号内的值≤0，故有(cj-zj)'≤0。

(b)对arj<0，因[(cj-zj)/arj-(cs-zs)/arj]>0，故有(cj-zj)≤0。

对偶单纯形法的优点： 不需要人工变量；

当变量多于约束时，用对偶单纯形法可减少迭代次数；

在灵敏度分析中，有时需要用对偶单纯形法处理简化。

对偶单纯形法缺点： 在初始单纯形表中对偶问题是基可行解，这点对多数线性规划问题很难做到。 因此，对偶单纯形法一般不单独使用