Artificial Variable in Basis in Two-Phase Method in Linear Programming

Question

Suppose we have the following problem: $$Z = 3 x_{1} + 2 x_{2} + 3 x_{3} \to max$$ $$\begin{cases} 2 x_{1} + x_{2} + x_{3} = 4 \\ x_{1} + 3 x_{2} + x_{3} = 12 \\ 3 x_{1} + 4 x_{2} + 2 x_{3} = 16 \\ x_{1}, x_{2}, x_{3} \geq 0 \end{cases}$$

I'm trying to solve this using the two-phase method. I know that we need to get rid of artificial variables in basis at the Phase 1.

But in this case it impossible. According to this here the artificial variable is just removed, despite the fact that it is in basis!

Is there any reason for this?

Answer 1

The key is that the artificial variable stuck in the basis has value 0, which means that (a) the solution is feasible and (b) the constraints are linearly dependent (which is why you can't pivot the artificial variable out of the basis). As noted by @callculus42, you can remove a constraint (typically you would pick the one containing the artificial variable) and work with the reduced problem.

Answer 2

You don´t get in trouble if you omit one of the constraints. You can (must) do that, since the three constraints are lineary dependent. You obtain a zero row if you subtract constraint $1$ and constraint $2$ from constraint $3$. Here is the output of the calculator if the second constraint has been omitted.

$$Z = 3 x_{1} + 2 x_{2} + 3 x_{3} \to \textrm{max}$$

$$ 2 x_{1} + x_{2} + x_{3} = 4$$ $$3 x_{1} + 4 x_{2} + 2 x_{3} = 16 $$ $$x_{1}, x_{2}, x_{3} \geq 0 $$