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

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.

### 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.

• 1. You need 3 basic variables to start; 2. Your starting point does not satisfy the constraints. 3. Is there no nonnegativity constraint? – LinAlg Feb 22 at 1:50
• @LinAlg (1) why do I need three variables to start (because that's the dimension of the row-space and solution?) (2) what do you mean? That my starting point is $x_3 = 1$, and if all other $x_i=0$ the second (and first) equalities (constraints) are false (3) There is - I'll add that – baxx Feb 22 at 2:30
• 1. since you have 3 constraints; 2. 'are false': that is not ok. You need basic feasible solutions in every iterate (so basic AND feasible; you have neither) – LinAlg Feb 22 at 2:46

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 in exams/tests so save the trouble of doing phase I. However, finding initial BFS like this is never a general method.