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

1、.例4-7 用对偶单纯形法求解线性规划问题. min z =5x1+3x s.t. -2 x1 + 3x6 3 x1 - 6 x4 xj0（j=1,2）解： 将问题转化为 max z = -5 x1 - 3 x s.t. 2 x1 - 3x+ x3 = -6 -3 x1 + 6 x+ x4-4 xj0（j=1,2，3,4）其中，x3 ，x4 为松弛变量，可以作为初始基变量，单纯形表见表4-17. 表4-17 例4-7单纯形表cj-6-3-40cbxbbx1x2x3x4迭代0次0x4-62-3100x5-4-36010-5-300cbxbbx1x2x3x4迭代1次-3x42-2/31-1/300

2、x3-1610216-70-10在表4-17中,b=-160,而y0,故该问题无可行解.注意: 对偶单纯形法仍是求解原问题,它是适用于当原问题无可行基,且所有检验数均为负的情况.若原问题既无可行基,而检验数中又有小于0的情况.只能用人工变量法求解.在计算机求解时,只有人工变量法,没有对偶单纯形法.3.对偶问题的最优解由对偶理论可知,在原问题和对偶问题的最优解之间存在着密切的关系,可以根据这些关系,从求解原问题的最优单纯形表中,得到对偶问题的最优解.(1) 设原问题(p)为精品. min z=cx s.t. 则标准型(lp)为 max z=cx s.t. 其对偶线性规划（d）为 max z=bt

3、y s.t. 用对偶单纯形法求解（lp），得最优基b和最优单纯形表t（b）。对于（lp）来说，当j=n+i时，有pj=-ei，cj=0从而，在最优单纯形表t（b）中，对于检验数，有（n+1，n+2n+m）=（cn+1，cn+2，cn+m）-cbb-1（pn+1,pn+2,pn+m）=- cbb-1 (-i)于是，y*=（n+1，n+2n+m）t 。可见，在（lp）的最优单纯形表中，剩余变量对应的检验数就是对偶问题的最优解。同时，在最优单纯形表t（b）中，由于剩余变量对应的系数所以 b-1 =（-y n+1，-y n+2-yn+m） 例4-8 求下列线性规划问题的对偶问题的最优解。 min z

4、=6x1+8x s.t. x1 + 2x20 3 x1 + 2x50 xj0（j=1,2）解： 将问题转化为 max z =-6x1-8x s.t. -x1 2x + x3=20 -3 x1 - 2x+ x4 =50 精品.xj0（j=1,2，3,4）用对偶单纯形法求解如表 表4-18 例4-8单纯形表cj-6-800cbxbbx1x2x3x4迭代0次-8x45/201-3/41/4-6x515101/2-1/2-1100031在引入松弛变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。 对于有些线性规划模型，如

5、果在开始求解时不能很快使所有检验数非正，最好还是采用单纯形法求解。因为，这样可以免去为使检验数全部非正而作的许多工作。从这个意义上看，可以说，对偶单纯形法是单纯形法的一个补充。除此之外，在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法，可以简化计算。例4-9：求解线性规划问题： min f = 2x1 + 3x2 + 4x3 s.t. x1 + 2x2 + x3 3 2x1 - x2 + x3 4 x1 , x2 , x3 0 标准化：max z = - 2x1 - 3x2 - 4x3 s.t. -x1-2x2-x3+x4= -3 -2x1+x2-3x3+x5= -4 x1,x2,x3,x4,x5 0表格对偶单纯形法 cj-6-800c