Consider the following problem min SX1 6x2 4x3 s t x1 2x

Consider the following problem min SX_1 - 6x_2 + 4x_3 s. t. - x_1 + 2x2 lessthanorequalto 1 3x_1 - x_2 greaterthanorequalto2 3x_2 + x_3 =3 X_1 urs,x_2 greaterthanorequalto 0, x_3 lessthanorequalto 0 Convert this linear programming (LP) problem to the standard form. Introduce the artificial variables and big M to get an initial solution: What is the LP problem after you adding artificial variables and big M?

Solution

To convert a linear program into standard form 5x1-6x2+4x3, -x1+2x2<=1, 3x1-x2>=2, 3x2+x3=3, x2>=0

x3<=0.

We consider a inequality constraint -x1+2x2<=1

converting <= variable to a standard form, we add a slack variable -x1+2x2<=1

-x1 + 2x2 +s1=1

s1 = 1 +x1 - 2x2.

To convert a >= variable to a standard form we add a surplus variable 3x1-x2>=2

3x1-x2-s2=2

s2 = 3x1-x2 -2

max Z= 5x1-6x2+4x3   

x1-2x2-s1=-1

3x1-x2-s2=2

x2>=0, x3<=0

s1>=0, S2 >=0

x1 = -1 + 2x2 +s1

eliminating x1... i.e.,

substituting this will give

3 (-1 + 2x2 +s1) -s2-x2 = 2

5x2 +3s1-s2=5.

substituting in first

5(-1 + 2x2 +s1)-6x2+4x3=0

4x2 +5s1+4x3=5

Finally standard form

5x2 +3s1-s2=5.

4x2 +5s1+4x3=5.

x2>=0 , x3<=0, s1>=0 , s2>=0