运筹学课件-对偶单纯形法

对偶单纯形法并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。以标准型线性规划为例，对于线性规划：

若B是A中的一个基，当B对应的基本解也是可行解时，称B是可行基，当B对应的基本可行解是最优解时，称B为最优基。若是对偶问题的可行解，则称B是对偶可行基。2.2对偶单纯形法可见对偶可行基还是原问题的一个基，且使单纯形乘子成为对偶问题的可行解，即满足。由第一章的知识可知最优基既应该是可行基，也应该使检验数，而这就意味着B也是对偶可行基。反之当B是可行基，且也是对偶可行基时，对应于B的基本可行解的检验数，因此B也是最优基。定理

B是线性规划的最优基的充要条件是：B是可行基，而且也是对偶可行基。单纯形法的基本过程可以归纳为保持基的可行性，逐步迭代最终达到基的对偶可行性。

先找到一个对偶可行基，然后保持基的对偶可行性，逐步迭代直至最终达到基的可行性。这种算法就称为对偶单纯形法。

对偶单纯形法的基本思想对偶单纯形法的基本思想是：从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。

如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。

对偶单纯形法在什么情况下使用：

应用前提：有一个基，其对应的基满足:

①单纯形表的检验数行全部非正（对偶可行）；

②变量取值可有负数（非可行解）。

注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。设原问题是（记为LP）：对偶问题是（记为DP）：

根据对偶性质6，可以构造一个求线性规划的另一种方法，即对偶单纯形法。

对偶单纯形法的计算步骤：对偶单纯形法的条件是：初始表中对偶问题可行，即极大化问题时，极小化问题时。

（1）建立初始对偶单纯形表,将线性规划的约束化为等式，求出一组基本解，因为对偶问题可行，即全部检验数（max）或

（min）,当基本解可行时，则达到最优解；若基本解不可行，即有某个基变量的解bi<0，则进行换基计算；（2）先确定出基变量。行对应的变量xl出基；

（3）再选进基变量。求最小比值（4）求新的基本解，用初等变换将主元素alk化为l,k列其它元素化为零，得到新的基本解，转到第一步重复运算。【例2.10】用对偶单纯形法求解【解】先将约束不等式化为等式，再两边同乘以（－1），得到用对偶单纯形法，迭代过程如下页。表2－4

应当注意：（1）用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶问题的最优解；（2）初始表中一定要满足对偶问题可行，也就是说检验数满足最优判别准则；（3）最小比值中的绝对值是使得比值非负，在极小化问题时

，分母aij<0这时必须取绝对值。在极大化问题中，

分母aij<0，总满足非负，这时绝对值符号不起作用，可以去掉。如在本例中将目标函数写成这里

在求θk时就可以不带绝对值符号。（4）对偶单纯形法与普通单纯形法的换基顺序不一样，普通单纯形法是先确定进基变量后确定出基变量，对偶单纯形法是先确定出基变量后确定进基变量；（5）普通单纯形法的最小比值是其目的是保证下一个原问题的基本解可行，对偶单纯形法的最小比值是其目的是保证下一个对偶问题的基本解可行；（6）对偶单纯形法在确定出基变量时，若不遵循规则，任选一个小于零的bi对应的基变量出基，不影响计算结果，只是迭代次数可能不一样。例2.11：求解线性规划问题：

单纯形法和对偶单纯形法步骤是是是是否否否否所有所有得到最优解计算计算典式对应原规划的基本解是可行的典式对应原规划的基本解的检验数所有所有计算计算以为中心元素进行迭代以为中心元素进行迭代停没有最优解没有最优解单纯形法对偶单纯形法

对偶单纯形法的适用范围对偶单纯形法适合于解如下形式的线性规划问题

在引入松弛变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。对于有些线性规划模型，如果在开始求解时不