Simplex Algorithm, determining Two Phase is required and choice of artificial variables

Question

Given the following system :

\begin{align*} \text{minimise } z = &2x_1 &+ 3x_2 &+ 3x_3 &+ x_4 &- 2x_5& \\ \end{align*}

Subject to \begin{align*} & x_1 &+ 3x_2 & &+x_4 &+ x_5 &= 2 \\ & x_1 &+ 2x_2 & &- 3x_4 &+ x_5 &= 2 \\ - &x_1 &- 4x_2 & +x_3 & & &= 1 \\ \end{align*}

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

There should be Phase I and then Phase II of the simplex method.

---

Q1 - how to explain why Phase I is required here

Q2 - how to know which rows should have artificial variables added

---

For question 1, the objective function can be written as

\begin{align*} -z + 2x_1 + 3x_2 + 3x_3 + x_4 - 2x_5 = 0\\ \end{align*}

The way that the system is initially set up has basic variables $x_3$ and non-basic variables $x_1,x_2,x_4,x_5 = 0$.

Meaning the objective function is

\begin{align*} -z + 3x_3 = 0\\ \end{align*}

Or

\begin{align*} z = 3x_3 \end{align*}

Why is this an issue?

For Question 2 I'm not sure what to consider.

Answer 1

Point (2) in OP's comment is very near to the an answer.

For each of the first two constraints, there's no decision variable

• which has nonzero coefficient, and
• which doesn't appear in the other two rows.

For a concrete counterexample, you may consider the third row, in which $x_3$

• has coefficient one
• doesn't appear in the first two constraints.

Therefore, in general, the first two rows need artificial coefficients.

Remarks: Observe that $\begin{vmatrix} 1 & 3 & 0 \\ 1 & 2 & 0 \\ -1 & -4 & 1 \end{vmatrix} \ne 0$ and $\begin{vmatrix} 0 & 1 & 1 \\ 0 & -3 & 1 \\ 1 & 0 & 0 \end{vmatrix} \ne 0$, so you may actually solve it as in linear-algebra in exams/tests so save the trouble of doing phase I. However, finding initial BFS like this is never a general method.