Transforming a linear program into its canonical form for use in the simplex algorithm

Question

A typical example of a LP in my lectures looks like this:

From what I've learnt, we are ready to implement the simplex algorithm on this LP, since $x_3, x_4, x_5$ all have positive signs, and so are the right hand sides of the constraints.

Now I have the following LP:

maximize $z = x_1 - x_2 + 2x_3$

subject to:

$-2x_1 + 2x_2 + 2x_3 - x_4 = 2$

$2x_1 - 2x_2 + x_3 + x_5 =2$

$x_1,x_2,x_3,x_4,x_5 \geq 0$

I'm trying to turn this into the required form, and I'm considering two approaches:

Approach 1: multiplying the first constraint by $-1$, so that it becomes $2x_1 - 2x_2 - 2x_3 + x_4 = -2$, then introduce a variable $x_6 \geq 0$ into it so that the RHS becomes non-negative, i.e. $2x_1 - 2x_2 - 2x_3 + x_4 + x_6 = 0$, and then proceed to let $x_5 \text{ and } x_6$ be the basic variables.

However this approach doesn't seem right to me, since then wouldn't $x_6$ must have the value $2$? (and hence not really a variable?)

Approach 2: starting with the solution $(0,0,0,0)$, we see that the 2 LHSs must be "corrected" to attain the desired values, so we introduce $x_6, x_7 \geq 0$ to make up for the differences. But what we really want is for those two new variables to be $0$, so our LP becomes:

maximize $z = -x_6 - x_7$

subject to:

$-2x_1 + 2x_2 + 2x_3 - x_4 + x_6 = 2$

$2x_1 - 2x_2 + x_3 + x_5 + x_7 =2$

$x_1,x_2,x_3,x_4,x_5,x_6,x_7 \geq 0$

Is any of the two approaches valid? If not, why is it so, and how should I think about and resolve the issue mentioned above?

Answer 1

1. Approach 1 is invalid for the reason that you've mentioned: missing value $2$ on the RHS.
2. Approach 2 is simply the two-phase-simplex method. To improve the efficiency, you don't need to introduce $x_7$. Simply take $x_5 = x_6 = 2$ at the beginning of phase I, and eliminate $x_6$ from the current basis so as to obtain a basic feasible solution for phase II.
3. Inspection approach: find an intial basic feasible solution by inspection: observe that $x_5$ doesn't appear in the first constraint, so choose either $x_2$ or $x_3$ to be the first basic variable, and $x_5$ as the second basic variable. This should save work for introducing additional terms.