The Minimum Ratio Test and the Leaving Variable

After we've selected the entering variable $x_j$, we need to determine which basic variable leaves the basis. This is decided by the minimum ratio test.

For each row $i$ of the simplex tableau (excluding the objective row) whose pivot-column entry satisfies $a_{ij} > 0$, compute the ratio

$$\theta_i = \dfrac{b_i}{a_{ij}},$$

where $b_i$ is the right-hand side of row $i$. The row $r$ that achieves the minimum value of $\theta_i$ is the pivot row, and the basic variable currently in row $r$ is the leaving variable.

Why this works: as we increase $x_j$ from $0$, the basic variable in row $i$ takes the value $b_i - a_{ij}\,x_j$. Feasibility requires this to stay nonnegative, so $x_j \leq b_i / a_{ij}$. The tightest of these bounds is reached first, and that row's basic variable hits zero, forcing it to leave.

Quick illustration: with pivot-column entries $(2,\, 3,\, 1)$ and right-hand sides $(8,\, 9,\, 5)$, the ratios are $\tfrac{8}{2}=4$, $\tfrac{9}{3}=3$, and $\tfrac{5}{1}=5$. The minimum is $3$ in row $2$, so row $2$ is the pivot row.