【知识点】对偶问题的对偶理论，原始问题最优解

对偶单纯形法是指从对偶可行性逐步寻找原问题最优解的方法。根据线性规划问题的对偶理论，原问题的测试数对应于对偶问题的一组基本可行解或最优解；原问题的一组基本可行解或最优解对应对偶问题的测试数；原问题约束方程的系数矩阵的转置就是对偶问题的约束方程的系数矩阵。

对偶变量p是pT=cTBB1。然后由原问题的最优性条件cTcTBB1A≥0T得到等价表达式的对偶可行性条件pTA≤cT。

在每个单纯形表中，b列代表当前基本变量的值（同时非基本变量取0），这样就得到了一个可行解。并且非负要求b列的，只是暗示了解的可行性——当b列为负时，表示基变量应该取负值，这与变量的非负性相冲突。也就是说，如果b列有负数，对应基矩阵B作为不可行基。即对偶单纯形法可以从不可行基开始计算。

对偶单纯形法其实是：

(1）选择b列作为负基变量作为换出变量（一般选择最小的）；

(2）对于带负系数的swap-out变量单纯形表入基变量相同，θ值是用测试数除以系数来计算的；

(3）选择θ值最小的变量作为换入变量。

(4）直到所有基变量b都为非负且测试次数达到最优情况，得到最优解。

从对偶单纯形法的求解思想可以看出，在应用对偶单纯形法时单纯形表入基变量相同，对偶问题的解必须是可行解，即必须满足条件：

①校验数行≤0（保持对偶可行）；

②有b<0（通过逐步迭代实现原问题是可行的，实现b≥0的所有目标）。

对偶单纯形法的运算与单纯形法的运算完全相反。它首先确定换出变量，然后确定换入变量。除了矩阵表示和测试数的含义外，与单纯形法相同。区别在于单纯形法要求任何表中b列的数字为负数，而对偶单纯形法则不需要。