对偶单纯形法.doc

对偶单纯形法：对偶单纯形法：设线性规划问题为：max Z=cx(P) AX=bX≥0 原始的单纯形法的思想：1 要求纯型迭代要求每一步都是基础可行解 b=B¯1b≥02 达到最优解时，检验数 Cj-Zj≤0（max)或者 Cj-Zj≥0（min)3 但对于（max,≥）型所加的剩余变量无法构成初始基础可行解，因此通过加人工变量来解决4 大 M 法和二阶段法比较繁琐5 能否从剩余变量构成的初始基础非可行解出发迭代，但保证检验数满足最优条件，Cj-Zj≤0（max)或者 Cj-Zj≥0（min)X bXb B¯1A B¯1bδδ C-CbB¯1A -CbB¯1b若上表最优单纯形表，则下面两个式子同时成立1 B¯1≥0 （可行性条件，又叫对偶最优性条件）2 C-CbB¯1A ≤0（最优性条件，又叫做对偶可行性条件）从满足 2 的基出发去找元问题的最优解对偶单纯形法的思想：从满足条件 2 的基（一般称为正则基）B 出发，经过换基运算得到另一个正则基，即一直保证 2 成立，知道找到一个满足条件（1）的正则基对偶单纯形法的步骤：P118 页看例题 4.41注意几个问题：（1）对偶单纯形法求解线性规划的一种求解方法，而不是去求对有问题的最优解（2）初始表中一定要满足对问题可行，也就是说检验数满足最优判别准则（3）最小比值中|δj∕aij | 的绝对值是使得比值非负，在极小化问题时 δj≥0 ，分母 aij＜0 这时必须取绝对值。

在极大化问题中，δ≤0 ， 分母 aij＜0， δj∕aij 总满足非负，这时绝对值不起作用，可以去掉如果本例中将目标函数写成 maxz’=-2X1-3X2-4X3这里 aij＜0 在求 θk 时就可以不带绝对值符号4）对偶单纯形法与普通单纯形法的换基顺序不一样，普通的单纯形法是先确定进基变量后确定出基变量，对偶单纯形法是先确定出基变量后确定进基变量5）普通单纯形法的最小比值是 min i{b i／aij |aik＞0} 其目的是保证下一个元问题的基本解可行，对偶单纯形法得最小比值是 min j{|δj∕aij| aij＜0} 其目的是保证下一个对偶问题的基本解可行（6）对偶单纯形法在确定出基变量时，若不遵循 bt=min{bi | bi＜0}规则，任何一个小于 bi对应的基变量出基，不影响计算结果，只是迭代次数可能不一样。