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

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?

1. Approach 1 is invalid for the reason that you've mentioned: missing value $$2$$ on the RHS.
2. Approach 2 is simply the 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.