Simplex Method: Why should the value produced by the Minimum Ratio Test be positive?

Question

The divisor of the minimum ratio test shouldn't be negative or 0, but why is this? I'd like to understand the reason.

Also, why do we choose the smallest number in the ratio test column be the pivoting row?

Answer 1

The Minimum Ratio Test is measuring of amount of change in the tableau if the Simplex algorithm is going to traverse along an edge (constraint) from one extreme point to another. In other words, the Simplex algorithm is picking a direction it wants to move. When we have negative values, or a situation where we are dividing by zero, if the Simplex method chose that row to traverse, then the values in the resulting tableau would be infeasible as we have left the feasible region of the model. For example, let's look at the following model:

$$max \text{ } z = x + y$$ Subject to, $$2x+y\le 4$$ $$-x+y\le2$$ $$x,y\ge0$$

We can graphically represent it as such with the purple shaded region denoting the feasible region of the model:

The Simplex algorithm will start at the first extreme point (0,0) at the origin. From here, it will pick a direction that'll let it traverse across a constraint from one extreme point to another (in this case from the origin, either (0,2) or (2,0)). Let's depict this in tabular form:

Here, we can choose the $x$ column to pivot. When we do the minimum ratio test, we are saying that the resulting ratio values are the amount of units we are moving to reach a new extreme point. Notice that the second row is moving two units to the right of $x$, which will represent $x$ moving from what it currently is as a non-basic variable $x=0$ to $x=2$ once it becomes a basic variable after this pivot. However, if we choose the bottom row to pivot, we are effectively having the simplex go backwards into infeasibility by -2 units, as shown graphically here:

Thus, this is why we choose the minimum ratio row, as any other row selection will cause our current tableau to become infeasible.