I'm trying to implement my own Simplex solver and I'm encountering some issues. When choosing the leaving variable, one is supposed to pick the element with the smallest positive $b_i/x_{i,j}$ where $j$ is the entering column chosen earlier. Are there more constraints for a pivot to be valid?
In the (maximizing) example below my implementation chooses S16 (slack var) to leave and X5 to enter:
C -1 -1 -1 -1 -0.5 -100 -100 -100 -100 -100 -100 0 0 0 0 0
Basis Cb b X1 X2 X3 X4 >> X5 X6 X7 X8 X9 X10 X11 S12 S13 S14 S15 S16
X2 -1 0 -1 1 0 0 0.5 0 0 0 0 0 0 0 0 0 0 0
X4 -1 0 -1 0 0 1 0.5 0 0 0 0 0 0 0 0 0 0 0
X3 -1 0 -1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
S12 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
S13 0 1 1 0 0 0 -0.5 0 0 0 0 0 0 0 1 0 0 0
S14 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
S15 0 1 1 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 1 0
<< S16 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1
Z = 0 3 -1 0 0 0 0 0 0
Cj - Zj -4 0.5 -100 -100 -100 -100 -100 -100
This causes two of the $b$ values to become negative, which clearly isn't a valid solution.
C -1 -1 -1 -1 -0.5 -100 -100 -100 -100 -100 -100 0 0 0 0 0
Basis Cb b X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 S12 S13 S14 S15 S16
X2 -1 -0.5 -1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5
X4 -1 -0.5 -1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 -0.5
X3 -1 0 -1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
S12 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
S13 0 1.5 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0.5
S14 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
S15 0 1.5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0.5
X5 -0.5 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1
Z = 0.5 3 0 0 0 0 0 0 0.5
Cj - Zj -4 -100 -100 -100 -100 -100 -100 -0.5
The $C_j – Z_j = 0.5$ would seem to suggest there is a better solution, but I am clearly missing some exit condition here as the solution before the pivot is already optimal.
Best Answer
The rule is not precisely "pick a leaving variable with the smallest positive ratio". There are two mostly-equivalent rules:
Sometimes there's a tie, in which case any way to break the tie gives us another valid tableau after we pivot.
Moreover, when the ratio is $0$, you are doing degenerate pivoting: a pivoting step that changes the basis but does not actually change the solution (or the objective value). This is not inherently a problem, but it does mean that you should be worried about cycling: you could get stuck in a loop of degenerate pivoting steps and never make progress.
There are all sorts of refinements to the simplex pivoting rule that tell you how to break ties in an effort to avoid this.