对偶单纯形法的基本思路是：

（1）求出满足最优检验的基本解X(0)，利用这个解X(0)及线性规划模型提供的信息，编制初始单纯形表。

（2）判断基本解X(0)是否满足非负约束，即X(0)是否为基本可行解。

（3）若X(0)是基本可行解，计算停止；若X(0)不是基本可行解，就将一个小于零的基变量换出，再将一个非基变量换入，进而产生使目标函数次优的另外一个可行解，同时生成另一张单纯形表，再返回第（2）步。如此逐步迭代，若线性规划模型有最优解，那么经过有限次迭代后就会求出最优解。

基于对偶单纯形法基本思路的三个过程，需要解决以下几个问题：

（1）如何保证求出的可行解使线性规划模型的目标函数保持最优？

（2）如何判断求出的可行解是否满足非负约束？

（3）若求出的可行解不满足非负约束，如何将一个基变量换出？如何将一个非基变量换入？

为了解决以上问题，同时为了理解和掌握对偶单纯形法的基本思路，下面通过一个例题进行详细的说明和解释。

例3.4　用对偶单纯形法对以下线性规划模型求解。

下面对该模型用对偶单纯形法求解：

1.寻找使目标函数达到最优的可行解X(0)

引入多余变量x5、x6，将模型中约束条件方程转换为等式，模型如下：

在上述模型的约束条件方程组中没有单位矩阵，而多余变量x5、x6的系数都为-1，构不成单位矩阵，又因为对偶单纯形法先不考虑满足非负约束，所以可将两个约束条件方程的两端同乘以-1，从而使多余变量x5、x6的系数构成单位矩阵。需要注意的是，这样处理也使约束条件方程右端的常数变成了负数，在单纯形法里是不允许这样处理的。两个约束条件方程的两端同乘以-1后，模型变为

可以选择多余变量x5、x6作为基变量，将模型按照单纯形表的形式列出。因为此单纯形表是用于对偶单纯形法的，所以也称为对偶单纯形表。对偶单纯形表如表3.7所示：

表3.7

这样得出一个基本解(x1,x2,x3,x4,x5,x6)=(0,0,0,0,-2,-3）。表3.7的全部检验数zj－cj≤0，因为模型是min型，满足最优检验，即这个基本解使目标函数达到最优。

2.判断基本解是否满足非负约束

前面得出的基本解中至少存在一个基变量的取值为负数，原因是对偶单纯形表的b列存在负数。显然，这个可行解违反了xj≥0的约束，故不是基本可行解，需要进行迭代计算，以使不满足非负约束的基变量个数减少。(www.daowen.com)

3.基本解的迭代计算

（1）确定换出变量。

为了使可行解中不满足非负约束的基变量个数减少，首先需要确定换出变量。确定换出变量的方法是：原则上选择b列中负值最小的一行所对应的基变量作为换出变量，若出现多个最小负值，任意取一个，把这一行标记为i*。

在上面的对偶单纯形表中，取b列最小值，即min{-2,-3}=-3，b列最小值3-所对应的行为第2行，所以i*=2。

（2）确定换入变量。

按照如下公式确定换入变量：

利用上式确定出最小值所在的列对应的变量作为换入变量。

如果目标函数是max型，就将上式括号中的分子zj－cj改写为cj－zj。

其实上式就是检验数除以上一步记住的那一行所在的负元素（ai*j<0），最后取最小比值所在的列对应的变量作为换入变量。

上面的对偶单纯形表3.7中，min{-2/-2,-5/-1}=1，最小值1来自第1列，所以将x1作为换入变量。

（3）进行行运算。

换入变量和换出变量确定后，将对偶单纯形表的换入变量和换出变量进行置换，仍然按照前面单纯形法的思路进行初等变换，变换的原则仍然是保证新的基变量对应的矩阵调整为单位矩阵。

先把表3.7迭代为表3.8所示的对偶单纯形表。

表3.8

由表3.8可以看到，检验数仍然全部保持小于等于0，但b列中还有负的基变量，仍然不可行，重复前面的步骤，继续迭代，得到表3.9所示的对偶单纯形表。

表3.9

由表3.9可知，检验数仍然保持全部小于等于0，基变量也没有负值存在，至此，已经找到了此线性规划模型的最优解：(x1,x2,x3,x4,x5,x6)=(8/5,1/5,0,0,0,0)。

上面这个例题如果用单纯形法求解，在加入多余变量以后，因为没有单位矩阵，还需要引入人工变量，这样变量的个数就变得很多，而且求解的过程较为麻烦。从以上的求解过程可以看到，用对偶单纯形法求解线性规划问题时，可以不必引入人工变量就可以进行求解，从而使计算简化。