Say we have a linear program where we wish to maximise some function Z, and we have the following equality constraints:
$3x_1 + 2x_2 + x_3 + 2x_4 = 225$
$x_1 + x_2 + x_3 + x_4 = 117$
$4x_1 + 3x_2 + 3x_3 + 4x_4 = 420$
Why would we need to add artificial variables to each of the constraints in the first phase of the two phase simplex method?
Why is it not sufficient to set 4-3 = 1 (4 decision variables and 3 constraint equations) of the decision variables to 0 and solve to find an initial basic feasible solution?
E.g. if we chose $x_1 = 0$, we could find $x_2 =39, x_3 = 9, x_4 = 69$. This looks like a basic feasible solution to me, which surely means it could be used as an initial vertex for the simplex algorithm? Though I am unsure how this BFS might be represented/arranged in the initial tableau.
Best Answer
There are some issues with linear dependence that are not too troubling; e.g. in \begin{align} 2x_1 + x_2 - x_3 &= 5 \\ 3x_1 + x_2 - x_3 &= 6 \end{align} you should not set $x_1$ to $0$ and try to solve for $x_2, x_3$ because you will fail. But that's not the real reason; Gaussian elimination exists to solve this kind of problem.
The problem is that picking some basic variables at random like you're suggesting will give you a basic solution, but that solution will only be feasible by chance. When you chose $x_1 = 0$ and got $x_2 =39$, $x_3 = 9$, and $x_4 = 69$, you won three coin flips in a row by getting $x_2 \ge 0$, $x_3 \ge 0$, and $x_4 \ge 0$. In a system with $50$ variables and $100$ equations, setting $50$ variables to $0$ arbitrarily has a $\frac1{2^{50}}$ chance of working, which is basically $0$.
(In my example above, which has easier numbers: if you set $x_1=0$, you don't get a basic solution. If you set $x_2=0$, you get $x_1=1$ and $x_3 = -3$, which is not feasible. Only if you set $x_3 = 0$ do you get a basic solution: $x_1 = 1$, $x_2 = 3$.)
Not only does this method not work, we know that in general, there's no method to find an initial basic solution which takes less effort than solving a linear program from a basic solution. Phase I is just as hard as Phase II. That's because it's possible (most easily using duality, which you probably have not learned yet) to turn an optimization problem (maximize this linear function subject to these equations and inequalities) into a feasibility problem (find a point that satisfies all these equations and inequalities). This tells us that there can't be an easy trick that does feasibility much faster than optimization.