等式约束变不等式约束 :x1+a:;x+…:x i2 2 ln n a.x,+ax,+∴a.x.≤b x i1~1 +a12x,+…a;nxn≥b i2 2 n n 2021/1/27 山东大学软件学院 16
2021/1/27 山东大学 软件学院 16 ai1 x1 + ai2 x2 +ai n xn = bi ai1 x1 + ai2 x2 +ai n xn bi ai1 x1 + ai2 x2 +ai n xn bi 等式约束变不等式约束
不等式约束变等式约束 il'I +a i2~2 …a.x.≤b 松弛变量 slack variable an1x1+a2x2+…amxn+s1=b,s≥0 nx1+a12x2+…amxn≥b 剩余变量 surplus variable 1x1+a12x2+…mCn =b,s;≥0 2021/1/27 山东大学软件学院 17
2021/1/27 山东大学 软件学院 17 松弛变量 slack variable 剩余变量 surplus variable ai1 x1 + ai2 x2 +ai n xn bi ai1 x1 + ai2 x2 +ai n xn + si = bi ,si 0 ai1 x1 + ai2 x2 +ain xn bi ai1 x1 + ai2 x2 +ai n xn − si = bi ,si 0 不等式约束变等式约束
不等式约束变不等式约束 a1x1+a12x2+…amxn≤b a.x.≥-b 或 a1x1+a;x,+…anxn,≥ b- ↓ -ix -airx2-.-ainX s-b 2021/1/27 山东大学软件学院 18
2021/1/27 山东大学 软件学院 18 ai1 x1 + ai 2 x2 +ain xn bi i i in n i − a x − a x −− a x −b 1 1 2 2 或 ai1 x1 + ai 2 x2 +ain xn bi i i in n i − a x − a x −− a x −b 1 1 2 2 不等式约束变不等式约束
例2.1.3将LP由一般型转为标准型 max -x+x2 min x -(x, -x4) St.2x1-x,≥-2 st.2x1-(x3-x)-x5=-2 x1-2x,≤2 x1+x2≤5 x1+(x2-x +x2=5 x1≥0 Ⅵ1<i<7x.≥0 x2无限制 2021/1/27 山东大学软件学院 19
2021/1/27 山东大学 软件学院 19 2无限制 1 1 2 1 2 1 2 1 2 0 5 2 2 s.t. 2 2 max x x x x x x x x x x + − − − − + 例2.1.3 将LP由一般型转为标准型 1 7, 0 ( ) 5 2( ) 2 s.t. 2 ( ) 2 min ( ) 1 3 4 7 1 3 4 6 1 3 4 5 1 3 4 + − + = − − + = − − − = − − − i i x x x x x x x x x x x x x x x x