用对偶单纯形法求解线性规划问题

1、例4-7用对偶单纯形法求解线性规划问题Min z =5x 1+3x2s.t.-2 Xi + 3x 2 A 6X1 - 6 x 2 A 4A 0 (j=1,2 )解：将问题转化为XjMax z = -5X1 -3 x 2s.t. 2xi - 3xX 3 = -6-3 xi + 6 X2 + x 4A -4Xj其中，X3 , X4,3,4 )A 0 (j=1,2为松弛变量，可以作为初始基变量，单纯形表见表表4-17例4-7单纯形表4-17.e-6-3-40Cb迭代0次XbbX1X2焉X0X4-62-3100X-4-3601zcZj0-5-300CB迭代1次XbbXXaX3X4-3X42-2/31-

2、1/300X3-161021ZCjZj6-70-10在表4-17中,b=-16<0,而yA 0,故该问题无可行解.注意：对偶单纯形法仍是求解原问题，它是适用于当原问题无可行基，且所有检验数均为负的情况.若原问题既无可行基，而检验数中又有小于0的情况.只能用人工变量法求解.在计算机求解时，只有人工变量法，没有对偶单纯形法.3.对偶问题的最优解,可以根据这些关系，由对偶理论可知，在原问题和对偶问题的最优解之间存在着密切的关系 从求解原问题的最优单纯形表中，得到对偶问题的最优解.(1)设原问题(P)为Min z= ex则标准型 (LP) 为AX bs.t.X0Max z=CXAX bs.t.X

3、0其对偶线性规划(D)为Max z=bTYAX bs.t.X0用对偶单纯形法求解时，有 Pj=-ei， cj=0(LP),得最优基B和最优单纯形表 T ( B)。对于(LP)来说，当j=n+iT (B )中，对于检验数，有(b n+1,b n+2b n+m) = (Cn+i, cn+2，cn+m) -CbB-1 (Pn+1,Pn+2 ,Pn+m) =- CbB-1 (-I)于是，Y*= (b n+1,b n+2b n+m T 。可见，在(LP)的最优单纯形表中，剩余变 量对应的检验数就是对偶问题的最优解。同时，在最优单纯形表T ( B)中，由于剩余变量对应的系数所以从而，在最优单纯形表b n+

4、2 bB 1 = ( -y n+1 , -y n+2 -y n+m)例 4-8 求下列线性规划问题的对偶问题的最优解。Min z =6x 1+8x2s.t.Xi + 2x2 >20X1 + 2x 2 A 50Xj > 0 (j=1,2 )解： 将问题转化为Max z =-6x 1-8x 2s.t.-x1 2x 2 + x 3=20-3X1 - 2X 2 + X 4 =50Xj > 0 (j=1,2 , 3,4 )用对偶单纯形法求解如表表4-18例4-8单纯形表C-6-800CBXbbX1X2XiX迭代0 次-8X45/201-3/41/4-6X515101/2-1/2ZCjZ

5、j-1100031在引入松弛变量化为标准型之后，约束等式两侧同乘-1,能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。对于有些线性规划模型， 如果在开始求解时不能很快使所有检验数非正，最好还是采用单纯形法求解。因为，这样可以免去为使检验数全部非正而作的许多工作。从这个意义上看，可以说，对偶单纯形法是单纯形法的一个补充。除此之外，在对线性规划进行灵敏度分 析中有时也要用到对偶单纯形方法，可以简化计算。标准化：s.t.Min f = 2x1 + 3x2 + 4x3S.t.x1 + 2x2 + x332x1 - x2 + x34x1 , x2 , x3 >0Max z = - 2x1 - 3x2-4x3例4-9：求解线性规划问题:-x1-2x2-x3+x4= -3-2x1+x2-3x3+x5= -4x1,x2,x3,x4,