I'm trying to understand how the two-phase simplex algorithm works, this site explains it using a simple example: http://optlab.mcmaster.ca/feng/4O03/Two.Phase.Simplex.pdf
I've tried to come up with some edge cases myself, and I'm stuck on this one, what am I doing wrong?
Minimize $x$ where $x \ge 1000$ and $x \ge 1000$
Obviously this is a dumb example, but the same issue arises when some constraints are linear combinations of each other.
Phase 1
We rewrite this linear program as a system of equations, where $s_1$, $s_2$ are the surplus variables and $a_1$ and $a_2$ are the artificial variables:
$\left\{ \begin{array}{c} x - s_1 +a_1=1000\\ x - s_2 +a_2=1000 \end{array} \right.$
We start by minimizing $a_1 + a_2$, so maximize $p = -a_1 - a_2 = (x - s_1 - 1000) + (x - s_2 - 1000) = 2x - s_1 - s_2 - 2000$
$\iff -2x - s_1 - s_2 + p = -2000$
This gives our starting tableau:
$$ \begin{array}{c|cccccc|c} &x&s_1&s_2&a_1&a_2&p&A\\ \hline a_1&1&-1&0&1&0&0&1000\\ a_2&1&0&-1&0&1&0&1000\\ \hline p&-2&1&1&0&0&1&-2000 \end{array} $$
After pivoting around column $1$, row $1$:
$$ \begin{array}{c|cccccc|c} &x&s_1&s_2&a_1&a_2&p&A\\ \hline x&1&-1&0&1&0&0&1000\\ a_2&0&1&-1&-1&1&0&0\\ \hline p&0&-1&1&2&0&1&0 \end{array} $$
The next column to pivot around is row $2$, but there's no row that works! There isn't a positive $\frac{A}{pivot}$ ratio:
$\frac{1000}{-1} = -1000 \le 0$
$\frac{0}{1} = 0 \le 0$
It seems like every explanation of the algorithm assumes there will always be a row with a positive ratio. It looks like the algorithm got stuck, we didn't even get to Phase 2, but the program definitely has a valid solution. What went wrong?
I'm looking for an answer that works in every case, not just this trival example. Just removing one of the constraints isn't a real solution.
The salient point is that the entries of the RHS have to be non-negative. You calculate the minimum of the fractions. Only the entries in the matrix has to be positive. The short notation is
$\min\bigg\{\frac{b_i}{a_{ij^*}}|a_{ij^*}>0\bigg\} $
where $b_{i}\geq 0$
In your case $\min\bigg\{\frac{b_2}{a_{22^*}}\bigg\}= \min\bigg\{\frac{0}{1}\bigg\}= 0 \quad \color{green} \checkmark $
Thus the final simlex tableau is
$$ \begin{array}{c|cccccc|c} &x&s_1&s_2&a_1&a_2&p&RHS\\ \hline x&1&0&-1&-1&1&0&1000\\ s_2&0&1&-1&-1&1&0&0\\ \hline p&0&0&0&1&1&1&0 \end{array} $$