On the injection of exactly two artificial variables into the Phase I of a two-phase simplex

Question

I am relatively new still to linear optimization and as I understand it, the two phase method is a common practice for finding the bfs before using the simplex or a simplex like solver (a solver relying on an initial bfs). I am using this document as a resource to understand how to construct a phase I, but I am getting doubts that the author has provided all the information needed.

I'll skip to the standard form of the problem which is as follows

\begin{align*} \text{max } & 2x_1 &+ 3x_2 &+ x_3 & \\ \end{align*}

Subject to

\begin{align*} &x_1 & +x_2 & +x_3 & +x_4 & & & =40\\ 2&x_1 & + x_2 & -x_3 & & -x_5 & & =10\\ & & -x_2 & +x_3 & & &-x_6 & =10\\ \end{align*}

Where

\begin{align*} x_1,x_2,x_3,x_4,x_5,x_6\geq0 \end{align*}

We can see that we have 3 constraints and yet we only add two artificial variables $x_7$ and $x_8$. I believe that 2 artificial variables are always sufficient because it is explained that if $x_7+x_8=0$ then both independently equal 0.

The author doesn't state that two is sufficient but I believe it is what he is implying. Is this the correct interpretation?

Answer 1

\begin{align*} x_1 + x_2 + x_3 + x_4 & =40\\ 2x_1 + x_2− x_3 − x_5 & =10\\ −x_2 + x_3− x_6 & =10 \end{align*}

Solve all three equations for $x_4$, $x_5$, and $x_6$ after setting $x_1 = x_2 = x_3 = 0$. Now, \begin{align*} x_4 & = 40\\ -x_5 & = 10\\ -x_6 & = 10. \end{align*}

So we need only two artificial variables for the negative slack variables.