1、例 4-7 用对偶单纯形法求解线性规划问题.Min z =5x1+3x2s.t. -2 x1 + 3x 63 x1 - 6 x 42Xj0（j=1,2）解： 将问题转化为 Max z = -5 x1 - 3 x 2s.t. 2 x1 - 3x + x3 = -62-3 x1 + 6 x + x4-4Xj0（j=1,2，3,4）其中，x 3 ，x 4 为松弛变量，可以作为初始基变量，单纯形表见表 4-17.表 4-17 例 4-7 单纯形表Cj -6 -3 -4 0CB迭代 0次XB b X1 X2 X3 X40 X4 -6 2 -3 1 00 X5 -4 -3 6 0 1jjzc0 -5 -3
2、 0 0CB迭代 1次XB b X1 X2 X3 X4-3 X4 2 -2/3 1 -1/3 00 X3 -16 1 0 2 1jjzc6 -7 0 -1 0在表 4-17 中,b=-160, 而 y0,故该问题无可行解.注意: 对偶单纯形法仍是求解原问题,它是适用于当原问题无可行基,且所有检验数均为负的情况.若原问题既无可行基,而检验数中又有小于 0 的情况.只能用人工变量法求解.在计算机求解时,只有人工变量法,没有对偶单纯形法.3.对偶问题的最优解由对偶理论可知,在原问题和对偶问题的最优解之间存在着密切的关系,可以根据这些关系,从求解原问题的最优单纯形表中,得到对偶问题的最优解.(1)设原
3、问题(p)为Min z=CXs.t. 0XbA则标准型(LP)为Max z=CXs.t. 0b其对偶线性规划（D）为Max z=bTYs.t. 0XA用对偶单纯形法求解（LP） ，得最优基 B 和最优单纯形表 T（B） 。对于（LP）来说，当j=n+i 时，有 Pj=-ei，c j=0从而，在最优单纯形表 T（B）中，对于检验数，有（n+1，n+2n+m）=（c n+1，c n+2，c n+m）-C BB-1（Pn+1,Pn+2,Pn+m）=- C BB-1 (-I)于是，Y*= （n+1，n+2n+m） T 。可见，在（LP）的最优单纯形表中，剩余变量对应的检验数就是对偶问题的最优解。同时，
4、在最优单纯形表 T（B）中，由于剩余变量对应的系数所以B-1 =（-y n+1，-y n+2-yn+m） 例 4-8 求下列线性规划问题的对偶问题的最优解。Min z =6x1+8x2s.t. x1 + 2x 203 x1 + 2x 50 2Xj0（j=1,2）解： 将问题转化为 Max z =-6x1-8x2s.t. -x1 2x + x3=20-3 x1 - 2x + x4 =50 2Xj0（j=1,2，3,4）用对偶单纯形法求解如表表 4-18 例 4-8 单纯形表Cj -6 -8 0 0CB迭代 0次XB b X1 X2 X3 X4-8 X4 5/2 0 1 -3/4 1/4-6 X5
5、 15 1 0 1/2 -1/2jjzc-110 0 0 3 1在引入松弛变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，最好还是采用单纯形法求解。因为，这样可以免去为使检验数全部非正而作的许多工作。从这个意义上看，可以说，对偶单纯形法是单纯形法的一个补充。除此之外，在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法，可以简化计算。例 4-9： 求解线性规划问题：Min f = 2x1 + 3x2 + 4x3 S.t. x1 + 2x2 + x3 32x1 - x2 + x3 4 x1 , x2 , x3 0标准化：Max z = - 2x1 - 3x2 - 4x3s.t. -x1-2x2-x3+x4= -3-2x1+x2-3x3+x5= -4 x1,x2,x3,x4,x5 0表格对偶单纯形法 Cj -6 -8 0 0CB迭代 0次XB b X1 X2 X3 X4-8 X4 5/2 0 1 -3/4 1/4-6 X5 15 1 0 1/2 -1/2jjzc-110 0 0 3 1
