第三步换基迭代.以最上面基变量负值对应行中 所有负数分别去除检验数,其中最小商对应的除数就 是主元素,用行初等变换将主元素所在列其他元素化 为零,将主元素化为1,得新基对应的单纯形矩阵 重复第二步、第三步,一定能得最优解或判定问 题无最优解
第三步 换基迭代. 以最上面基变量负值对应行中 所有负数分别去除检验数, 其中最小商对应的除数就 是主元素, 用行初等变换将主元素所在列其他元素化 为零, 将主元素化为1，得新基对应的单纯形矩阵. 重复第二步、第三步, 一定能得最优解或判定问 题无最优解
例1解线性规划问题 maxz=-3x1-4x x1+2x2≥5 3x1+x,≥ 6 x1+x2≥4 x≥0(j=1,2)
例1 解线性规划问题 = + + + = − − 0 ( 1,2) 4 3 6 2 5 max 3 4 1 2 1 2 1 2 1 2 x j x x x x x x z x x j s t
解引进松弛变量x3,x2x,将问题标准化为 min z'=3x1+4x2 x,1-2x+ 5 3 3.x s·t +x5 0(j=1,2,…,5) 取基B=(P3,P4,P5)其对应的单纯形矩阵为 3-40000 T(B)2-3-1010-6
解 引进松弛变量 x3 , x4 , x5 .将问题标准化为 取基B = (P3 , P4 , P5 ), 其对应的单纯形矩阵为 = − − + = − − − + = − − − + = − = + 0 ( 1,2, ,5) 4 3 6 2 5 s t min 3 4 1 2 5 1 2 4 1 2 3 1 2 x j x x x x x x x x x z x x j ≥ − − − − − − − − − − − = 1 1 0 0 1 4 3 1 0 1 0 6 1 2 1 0 0 5 3 4 0 0 0 0 T(B)
在T(B)中,检验数都非正,但a1=-5<0所以基B 不是可行基,而是对偶可行基 Om(3142}=-4-2=2 取b12=-2为主元素,进行换基迭代,得新基B=(P2P,P5 对应的单纯形矩阵. 10-200-10 5 00 T(B)=5 10 0 7—23-2
在T(B)中, 检验数都非正, 但d1= -5<0. 所以基B 不是可行基, 而是对偶可行基. 取b12= -2为主元素, 进行换基迭代, 得新基B1=(P2 ,P4 ,P5 ) 对应的单纯形矩阵. 1 2 2 min 3 1, 4 2 4 2 b = − − − − = − − = − − − − − − − − − − = 2 3 0 1 2 1 0 2 1 2 7 1 0 2 1 0 2 5 2 5 0 0 2 1 1 2 1 1 0 2 0 0 10 1 T(B )
在T(B1)中检验数都非正,但d2=-72<0 0=min 72272/2b 取b2=-5/2为主元素,进行换基迭代得新基B2=(P2P1P5) 对应单纯形矩阵 00 0-11 01 535 T(B2) 10 5 52-51-5
在 T(B1 )中 检验数都非正, 但d2= －7/2<0 取 b21= －5/2 为主元素,进行换基迭代,得新基B2=(P2 ,P1 ,P5 ). 对应单纯形矩阵 2 1 1 2 5 1 2 1 , 2 2 5 min 1 b = − − = − − = − − − − − − − − − − = 5 4 1 5 1 5 2 0 0 5 7 0 5 2 5 1 1 0 5 9 0 5 1 5 3 0 1 5 2 0 11 5 2 5 9 0 0 2 T(B )