Consider a maximisation LP problem. In the Simplex method, one of the rules for choosing which non-basic variable enters the new basis is too look at which one of the non-basic variables will give the largest increase to the objective function, and then proceed. However, why can't it happen that all of the basic variables, one of which should exit, will all give a larger decrease to the objective function than the increase the entering variable will give, so that no matter which variable we will choose for exit, our objective function will decrease? What argument forbids that?
My conditions are in the form of $Ax=b$, where $b=(7,-5,3)^T$, $A=\begin{bmatrix}12&12&1&1&-1\\-8&-6&0&-1&0\\11&10&1&1&-2\end{bmatrix}$.
I introduce artificial variables $a_1,a_2, a_3$ for each row. And try to minimise their sum. I proceed with the simplex algorithm, where square brackets indicate pivotal elements.
\begin{bmatrix}x_1&x_2&x_3&x_4&x_5&a_1&a_2&a_3\\12&12&1&1&-1&1&0&0&7\\-8&-6&0&-1&0&0&1&0&-5\\11&\boxed{10}&1&1&-2&0&0&1&3\\-15&-16&-2&-1&3&0&0&0&-5\end{bmatrix} (here I rewrote the last row in terms of the non-basic variables, as it is laid out here: http://www.maths.qmul.ac.uk/~ffischer/teaching/opt/notes/notes8.pdf )
\begin{bmatrix}-1.2&0&-0.2&-0.2&1.4&1&0&-1.2&3.4\\-1.4&0&0.6&-0.4&-1.2&0&1&0.6&-3.2\\1.1&1&\boxed{0.1}&0.1&-0.2&0&0&0.1&0.3\\2.6&0&-0.4&0.6&-0.2&0&0&1.6&-0.2\end{bmatrix}
\begin{bmatrix}1&2&0&0&\boxed{1}&1&0&-1&4\\-8&-6&0&-1&0&0&1&0&-5\\11&10&1&1&-2&0&0&1&3\\7&4&0&1&-1&0&0&2&1\end{bmatrix}
\begin{bmatrix}1&2&0&0&1&1&0&-1&4\\-8&-6&0&-1&0&0&1&0&-5\\13&14&1&1&0&2&0&-1&11\\8&6&0&1&0&1&0&1&5\end{bmatrix}
I stop since there are no negative coefficients left. However, it appears that the minimum of $a_1+a_2+a_3$ is 5, instead of 0. Must I have made a mistake somwhere? And the basis I ended up with is $(x_5,a_2,x_3)$. Shouldn't all a's be gone from the basis to proceed to phase 2?