I've been running into an issue choosing a pivot when there are constraints with an RHS of zero. It appears that sometimes you should include zero test ratios when searching for the minimum test ratio, and sometimes you shouldn't. What is the hard and fast rule to handle zero test ratios?
For a simple demo, say you want to maximize $y$ subject to $x + y \le 1$ and $y \le x$. An x/y graph of the solution space shows a triangle with the top at $x = \frac{1}{2}, y = \frac{1}{2}$. To maximize $y$ we should end up at this point.
The first table:
$$0:
\begin{bmatrix}
& x & y & s_1 & s_2 & = \\
s_1 & 1 & 1 & 1 & 0 & 1 \\
s_2 & -1 & 1 & 0 & 1 & 0 \\
& 0 & -1 & 0 & 0 & 0
\end{bmatrix}
$$
The only possible entering variable is $y$ with a negative cost of -1. Then to select the pivot row, we find the two ratios. Row 1 $1 / 1 = 1$, row 2 $0 / 1 = 0$. Here is the problem. As I understood, in order to choose a pivot row, the ratio test must be positive. If we follow that rule, it leaves only one option of leaving variable, $s_1$. So let's try following the rule:
$$1:
\begin{bmatrix}
& x & y & s_1 & s_2 & = \\
y & 1 & 1 & 1 & 0 & 1 \\
s_2 & -2 & 0 & -1 & 1 & -1 \\
& 1 & 0 & 1 & 0 & 1
\end{bmatrix}
$$
This breaks another rule: $s_2$ shouldn't be negative, right? Second, there is no negative in the objective row, so we're done. But we're at $x = 0, y = 1$ which isn't even a solution, because $s_2$ is an illegal value. Let's try picking row 2 instead, the one with the test ratio of 0:
$$1':
\begin{bmatrix}
& x & y & s_1 & s_2 & = \\
s_1 & 2 & 0 & 1 & -1 & 1 \\
y & -1 & 1 & 0 & 1 & 0 \\
& -1 & 0 & 0 & 1 & 0
\end{bmatrix}
$$
Now $x$ must enter. We are supposed to only pivot on positive test ratios. We didn't follow that rule last time, but we'll arbitrarily follow it now and have $s_1$ leave:
$$2:
\begin{bmatrix}
& x & y & s_1 & s_2 & = \\
x & 1 & 0 & \frac{1}{2} & -\frac{1}{2} & \frac{1}{2} \\
y & 0 & 1 & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\
& 0 & 0 & \frac{1}{2} & \frac{1}{2} & \frac{1}{2}
\end{bmatrix}
$$
And this is the answer. Out of curiosity, since we arbitrarily broke the 'positive' rule for pivot $1'$ and arbitrarily followed it for pivot $2$, let's try being consistent and always including zero when searching for the minimum test ratio. That means for pivot $2$ we should have chosen $y$ as the leaving variable since its test ratio ($0 / -1 = 0$) is smaller than the top row's ($1 / 2 = \frac{1}{2}$).
$$2':
\begin{bmatrix}
& x & y & s_1 & s_2 & = \\
s_1 & 0 & 2 & 1 & 1 & 1 \\
x & 1 & -1 & 0 & -1 & 0 \\
& 0 & -1 & 0 & 0 & 0
\end{bmatrix}
$$
Row 2 is always going to have a zero test ratio, apparently. So if we're going to consistently include zeros, we have to choose it again. $y$ enters, $x$ leaves.
$$3:
\begin{bmatrix}
& x & y & s_1 & s_2 & = \\
s_1 & 2 & 0 & 1 & -1 & 1 \\
y & -1 & 1 & 0 & 1 & 0 \\
& -1 & 0 & 0 & 1 & 0
\end{bmatrix}
$$
Which is identical to pivot $1'$, and we will cycle without arriving at a minimum.
To recap: how does one know exactly when and when not to include zeros when searching for the minimum test ratio, since excluding all zeros leads to invalid pivots and including all zeros leads to cycling? Or did I somehow start with a matrix that isn't in standard form?
Best Answer
Indebted to zifyoip for clearing up a fundamental misunderstanding for me: