文档介绍：例 4-7 inz =5x 1 +3 x2 . -2x 1+ 3x2 ≥63x 1-6x2 ≥4Xj≥0( j=1,2 ) 解: 将问题转化为 M axz= -5x 1-3x2 . 2x 1- 3x2 +x 3= -6 -3x 1+6x2 +x 4≥-4 Xj≥0( j=1,2 , 3,4 ) 其中, x 3,x 4 为松弛变量,可以作为初始基变量,单纯形表见表 4-17. 表 4-17 例 4-7 单纯形表 C j -6 -3 -40 C BX BbX 1X 2X 3X 4 迭代 0次0X 4 -62 [-3] 10 0X 5 -4 -3601 jjzcz 0 -5 -300 C BX BbX 1X 2X 3X 4 迭代1次-3X 42 -2/3 1 -1/3 0 0X 3 -16 1021 jjzcz 6 -70 -10 在表 4-17 中,b=-16<0, 而y≥ 0, 故该问题无可行解. 注意: 对偶单纯形法仍是求解原问题, 它是适用于当原问题无可行基, 且所有检验数均为负的情况. 若原问题既无可行基, 而检验数中又有小于 0 的情况. 只能用人工变量法求解. 在计算机求解时, 只有人工变量法, 没有对偶单纯形法. 3. 对偶问题的最优解由对偶理论可知, 在原问题和对偶问题的最优解之间存在着密切的关系, 可以根据这些关系, 从求解原问题的最优单纯形表中, 得到对偶问题的最优解. (1) 设原问题(p) 为M in z= CX .0X b AX 则标准型(LP) 为M ax z= CX .0X b AX 其对偶线性规划( D )为 M ax z=b TY .0X b AX 用对偶单纯形法求解( LP ), 得最优基 B 和最优单纯形表 T(B)。对于( LP ) 来说,当 j=n+ i 时,有 Pj=-e i,c j =0 从而,在最优单纯形表 T(B )中,对于检验数,有(σ n+1 ,σ n+2 …σ n+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+2 …σ n+m ) T。可见,在( LP ) 的最优单纯形表中, 剩余变量对应的检验数就是对偶问题的最优解。同时,在最优单纯形表 T(B )中,由于剩余变量对应的系数所以 B -1=( -y n+1, -y n+2…-y n+m ) 例 4-8 求下列线性规划问题的对偶问题的最优解。 M inz =6x 1 +8 x2 . x 1+ 2x2 ≥ 20 3x 1+ 2x2 ≥ 50 Xj≥0( j=1,2 ) 解: 将问题转化为 M axz =-6x 1 -8x2 . -x 1 — 2x2 +x 3 =20 -3x 1- 2x2 +x 4 =50 Xj≥0( j=1,2 , 3,4 ) 用对偶单纯形法求解如表表 4-18 例 4-8 单纯形表 C j -6 -800 C BX BbX 1X 2X 3X