Entering Variable Rule¶

Definition¶

In the course's maximization simplex tableau, the entering variable rule selects a nonbasic variable with the most negative coefficient in the objective row. If several coefficients tie for most negative, any tied variable may be chosen.

Interpretation¶

The rule decides which nonbasic variable to increase next: the one that raises the objective fastest per unit. Because the objective row is written with $z$ on the left, as $\displaystyle z+\sum_jq_jx_j=z_0$ $z_{0}$ , a coefficient $q_j<0$ means that $z$ rises by $-q_j$ for every unit increase of $x_j$ , so a more negative coefficient corresponds to a higher improvement rate.

An initial simplex tableau with an arrow at the column of x s, which has the most negative coefficient in the objective row and therefore enters the basis.

The arrow marks the $x_s$ column of the initial Giapetto tableau: its coefficient $-3$ is the most negative, since a soldier adds 3 to $z$ and a train only 2.

The sign convention is the point to remember. A variable with profit $c_j$ appears in the first tableau with coefficient $-c_j$ , so negative means improving. If no nonbasic coefficient is negative, no increase can raise $z$ , and the optimality test stops the method. Any variable with a negative coefficient would improve $z$ ; choosing the most negative one is a convention that fixes a definite next step.

The rule compares rates, not total gains. How far the entering variable can increase is decided afterwards by the minimum-ratio test. Here $x_s$ can rise only to 40, a gain of $3\cdot40=120$ $120$ , whereas $x_t$ could rise to 80, a gain of $2\cdot80=160$ $160$ .

Key Results¶

The selected variable defines the pivot column.
The greatest improvement rate is not necessarily the greatest total improvement, because allowable step sizes differ.
The ratio test determines how far the entering variable can increase while preserving feasibility.

Examples¶

The illustrated row is $z-3x_s-2x_t=0$ $0$ , so $x_s$ has the largest objective improvement rate per unit, $3>2$ $2$ , and enters. Choosing the smallest index is one possible tie convention; it is not required by the course rule. A feasible canonical tableau with no negative nonbasic objective-row coefficient is already optimal.

From $z-3x_1-2x_2=0$ $0$ , choose $x_1$ .
From $z-(1/2)x_2+(3/2)s_1=15$ $15$ , choose $x_2$ .

Prerequisites¶

Sources¶

OR Modelling · Week 2

Aliases: Dantzig's rule, most negative coefficient rule, largest coefficient rule Symbols: sum

Last updated: 20 October 2026 03:02