Max $Z=4x_1+5x_2$ Using two phase simplex

Question

max $$z=4x_1+5x_2$$ s.t $$3x_1+x_2\leq27$$ $$x_1+x_2=12$$ $$3x_1+2x_2\geq 30$$ $$x_1,x_2\geq 0$$

To start the process we find an initial solution, so we add a slack variables:

$$3x_1+x_2+x_3 = 27$$ $$x_1+x_2+x_4=12$$ $$3x_1+2x_2-x_5= 30$$ $$x_1,x_2, x_3,x_4,x_5\geq 0$$

or should it be

$$3x_1+x_2+x_3 = 27$$ $$x_1+x_2+x_4=12$$ $$3x_1+2x_2-x_5+x_6= 30$$ $$x_1,x_2, x_3,x_4,x_5,x_6\geq 0$$

Answer 1

To set up an LP in augmented form, to prepare it for either the two-phase method or the big-$M$, method:

• Each $\le$ constraint gets a slack variable
• Each $=$ constraint gets an artificial variable
• Each $\ge$ constraint gets both a surplus variable and an artificial variable

So, your second set of constraints is correct.

• $x_3$ is a slack variable
• $x_4$ is an artificial variable
• $x_5$ is a surplus variable and $x_6$ is an artificial variable.