情形1若=minz=0,且问题(Ⅱ)的最优基B中不 含人工变量列,则B就是原问题I)的可行基这时,只要 在T(B中去掉S,yy2mn所在列及第一行,便得原问 题(I)关于B的单纯形矩阵,再应用单纯形方法,即可求 解原问题(I 例1求解线性规划问题 min S=-x+ 2x2+ x3 2x1-x2+x3>-4 Sx1+2x2=6 3>0
情形1 若z0 = minz = 0,且问题(Ⅱ)的最优基 中不 含人工变量列, 则 就是原问题(Ⅰ)的可行基.这时,只要 在T( )中去掉 S, y1 ,y2 ,…,ym 所在列及第一行, 便得原问 题(Ⅰ)关于 的单纯形矩阵,再应用单纯形方法, 即可求 解原问题(Ⅰ). 例1 求解线性规划问题 min S = - x1+ 2x2+ x3 2x1 - x2 + x3≥ -4 x1+ 2x2 = 6 x1 , x2 , x3 ≥0 B B B s t B
解引进松弛变量x将问题化为标准形式 (I) min S=-x+ 2x2+ x3 2x1+x2-x3+x4=4 stx1+2x2=6 1,x2,x3,x4>0
解 引进松弛变量 x4 , 将问题化为标准形式 (Ⅰ) min S = - x1+ 2x2+ x3 - 2x1+ x2 - x3+ x4 = 4 x1+ 2x2 = 6 x1 , x2 , x3 , x4≥0 s t
由于没有现成的可行基,故引入辅助问题 minz=V1+y2 +x1-2x2-x3=0 2x1+x 2-x3+x4=4 S·t +x1+2x x≥0,y≥0(i=1,2,3,4;j=1,2
由于没有现成的可行基, 故引入辅助问题. (Ⅱ) min z = y1+ y2 S + x1－2x2－x3 = 0 y1 －2x1 + x2 －x3 + x4 = 4 y2 + x1 + 2x2 = 6 xi≥0, yj≥0 ( i = 1, 2, 3, 4; j = 1, 2 ) s t
001-2-10 A=010-21-11人造基B=(P,P2P3) 0-1-100000 1001-2-100 (LP) 010-21-1 4 00112006
− − − − − − = = − − − − = 0 0 1 1 2 0 0 6 0 1 0 2 1 1 1 4 1 0 0 1 2 1 0 0 0 1 1 0 0 0 0 0 ( ) ( , , ) 0 0 1 1 2 0 0 0 1 0 2 1 1 1 1 0 0 1 2 1 0 0 1 2 3 L P A 人造基B P P P
000-13-1110 001-2-100 (1)+(3)+(4) 010-211,-B)=T(P,P,P) 00112006 000 -106 T(B)=T(P1,P2,P3) 1003
( ) ( , , ) 1 0 0 3 2 1 2 1 0 0 0 1 1 1 2 5 2 1 0 1 1 0 1 2 0 1 0 6 0 1 1 1 2 5 2 3 0 0 ( ) ( , , ) 0 0 1 1 2 0 0 6 0 1 0 2 1 1 1 4 1 0 0 1 2 1 0 0 0 0 0 1 3 1 1 10 1 1 2 5 0 1 2 3 (1) (3) (4) T B T P P P T B T P P P = = − − − − − − − ⎯⎯⎯⎯→ = = − − − − − − ⎯⎯+ ⎯+ ⎯→