对偶单纯形法

    

    

    设原问题为：

    

    由对偶单纯形法的条件可知，并非所有线性规划问题都可以用这种方法，该方法最适合于下列线性规划问题。

    综上所述，对偶单纯形法的计算步骤如下：

    

    （4）以为主元素，按原单纯形法在表中进行迭代计算，得到新的计算表，然后转到第（1）步重复运算。

    例2-6利用对偶单纯形法求解线性规划

    解：先将约束不等式化为等式，并给等式两边乘以-1，再将极小化问题转换成极大化问题，以便得到对偶问题的初始可行基，即

    

    建立此问题的初始单纯形表，如表2-7所示。 由表2-7可以看到，检验数行对应的对偶问题的解是可行解。 因为b列数字为负，故需要进行迭代运算。

    换出变量的确定：按对偶单纯形法计算步骤（2），计算

    

表　2-7

    

    换入变量的确定：按对偶单纯形法计算步骤（3），计算

    

    由表2-8得，对偶问题仍是可行解，而b列数字中仍有负分量，故重复上述迭代过程，得到表2-9。

表　2-8

表　2-9

    

续表　2-9

    

    表2-9中，b列数字中全部为非负，检验数全为非正，故问题的最优解为：

    

    用对偶单纯形法求解线性规划问题时，当约束条件为“≥”时，不必引进人工变量，从而使计算简化。但要求在初始单纯形表中其对偶问题是基本可行解这点，对多数线性规划问题很难实现，因此对偶单纯形法很少单独使用，而主要应用于灵敏度分析和求解整数规划的割平面法中。