The variable that is going to enter the basis with revised Simplex already is in it

Question

I am looking to solve the following program using the revised Simplex method : $$ \begin{cases} \begin{aligned} \max \ & x_1&+ x_2\\ &x_1&-x_2&\le 1\\ &-2x_1&-x_2&\le -2\\ &-2x_1&+x_2&\le 2\\ \forall i, x_i \end{aligned} \end{cases} $$ Yet, I have a problem, the variable that is going to enter the matrix already is in it!

It all started with the following basis for the first iteration : $J_0=\{x_2;x_3;x_5\}$. I already did an iteration that didn't offered any difficulty and led me to the following bases $J_1=\{x_2;x_4;x_5\}$. It also provided me $\hat{A_4}$ and $\hat b$:

\begin{align*} \hat{A_{4}}&=(A^{J_0})^{-1}A^4\\ &=\begin{pmatrix} 0 & -1 & 0\\ 1 & -1 &0\\ 0 & 1 & 1 \end{pmatrix} \begin{pmatrix} 0\\ 1\\ 0 \end{pmatrix}\\ \hat{A_{4}}&=\begin{pmatrix} -1\\-1\\1 \end{pmatrix} \end{align*}

And naturally $\hat b_4=\begin{pmatrix}1\\-2\\2\end{pmatrix}$

Then I follow up with Iteration 1: as far as I took the minimum $>0$ between $\hat A_2/b=-1,\hat A_3/b=1/2,\hat A_5/b=1/2$, taking therfore $x_3$.

I first have

$$(A^{J_1})^{-1}=D_1(A^{J_0})^{-1}$$

Then I calculate the change of basis matrix : $$D_1=\begin{pmatrix}1 & 1 & 0\\ 0 & -1 & 0\\ 0 & 2 & 1\end{pmatrix}$$

Therfore

\begin{align}(A^{J_1})^{-1}&= \begin{pmatrix}1 & 1 & 0\\ 0 & -1 & 0\\ 0 & 2 & 1\end{pmatrix} \begin{pmatrix}0 & -1 & 0\\ 1 & -1 & 0\\ 0 & 1 & 1\end{pmatrix}\\ (A^{J_1})^{-1}&=\begin{pmatrix}1 &-2 &0\\ -1 & 1 & 0\\ 2 & -1 & 1\end{pmatrix} \end{align}

Then I calculated \begin{align}\Pi&=c(A^{J_1})^{-1}\\ &=\begin{pmatrix} 1 & 0 & 0 \end{pmatrix} \begin{pmatrix}1 &-2 &0\\ -1 & 1 & 0\\ 2 & -1 & 1\end{pmatrix}\\ \Pi&=\begin{pmatrix}1 & -2 & 0\end{pmatrix} \end{align}

It allows me to calculate the new $\hat c = c - \Pi A$

\begin{align*} \hat c &=\begin{pmatrix} 1 & 1 & 0 & 0 & 0 \end{pmatrix}- \begin{pmatrix} 1 & -2 & 0 \end{pmatrix} \begin{pmatrix} 1 & -1 & 1 & 0 & 0\\ -2 & -1 & 0 & 1 & 0\\ -2 & 1 & 0 & 0 & 1 \end{pmatrix}\\ &=\begin{pmatrix} 1 & 1 & 0 & 0 & 0 \end{pmatrix}- \begin{pmatrix} 5 & 1 & 1 & -2 & 0 \end{pmatrix}\\ \hat c&=\begin{pmatrix} -4 & 0 & -1 & 2 & 0 \end{pmatrix} \end{align*}

Theferore $x_4$ entered the matrix. Yet, this is impossible because it already is!

Answer 1

for $J_0=\{x_2;x_3;x_5\}$, the determinant is $$\begin{vmatrix} -1&1&0\\ -1&0&0\\ 1&0&1 \end{vmatrix}=-1$$ this base is feasible.

Yet, for $J_1=\{x_2;x_4;x_5\}$ $$\begin{vmatrix} -1&1&0\\ -1&0&1\\ 1&0&0 \end{vmatrix}=0$$ It is therfore unfeasible.