Minimum-Ratio Test¶

Definition¶

For a feasible canonical tableau and an entering variable with constraint-column coefficients $a_{ik}$ and right-hand sides $b_i\ge0$ $0$ , the minimum-ratio test selects

\theta=\min_{i\colon a_{ik}>0}\frac{b_i}{a_{ik}}.

A row attaining the minimum supplies the leaving basic variable. Zero ratios are eligible; only the denominator must be strictly positive.

Interpretation¶

Once the entering variable is chosen, the ratio test decides how far it may increase: as far as possible while every basic variable stays nonnegative. The test finds the first basic variable that reaches zero; a larger step would violate nonnegativity, so that variable leaves.

An initial simplex tableau with a ratio column for the entering column x s; the smallest ratio, 40, is in the row of s3, which leaves the basis.

In the figure, each right-hand side is divided by the positive entry of the $x_s$ column. The smallest ratio, 40 in the $s_3$ row, is the step length: at $x_s=40$ the slack $s_3$ reaches zero while $s_1=20$ and $s_2=40$ are still positive. In the graph of the Giapetto model, moving from the origin along the $x_s$ -axis, the boundary $x_s=40$ is the first one met, at the corner $(40,0)$ .

In row $i$ the basic variable equals $b_i-a_{ik}t$ when the entering variable is raised to $t$ , so it reaches zero at $t=b_i/a_{ik}$ if $a_{ik}>0$ $0$ . Rows with $a_{ik}\le0$ are skipped because their basic variable stays the same or grows. Taking the minimum guarantees that no basic variable becomes negative. If no row has $a_{ik}>0$ $0$ , nothing limits the increase, and an improving column then shows that the LP is unbounded.

A common slip is to compute ratios for rows with negative entries: a negative "ratio" would then win the minimum and pick a wrong leaving variable. A ratio of zero, by contrast, is eligible and gives a step of length zero.

Key Results¶

Rows with zero or negative pivot-column coefficients do not restrict the increase.
A tie may be broken arbitrarily in the course procedure and can lead to degeneracy.
If there is no positive coefficient and the objective improves along this column, the objective is unbounded.

Examples¶

In the illustrated tableau, increasing $x_s$ gives $s_1=100-2x_s$ $2 x_{s}$ , $s_2=80-x_s$ and $s_3=40-x_s$ $x_{s}$ . The limits $50,80,40$ give step length 40, so $s_3$ leaves.

The initial ratios $10/2=5$ and $15/1=15$ make $s_1$ leave.
The next ratios are $5/(1/2)=10$ and $10/(5/2)=4$ $4$ , so $s_2$ leaves.

Prerequisites¶

Sources¶

OR Modelling · Week 2

Aliases: minimum ratio rule, leaving variable rule Keywords: ratio test Symbols: theta

Last updated: 20 October 2026 03:02