Selecting the Entering Variable

How to choose which nonbasic variable enters the basis at each simplex iteration, using Dantzig's rule for both minimization and maximization, Bland's rule to break ties and prevent cycling, and reading reduced costs directly from a simplex tableau.

Step 1 of 157%

Tutorial

Dantzig's Rule for Minimization

When the current basic feasible solution (BFS) is not optimal, the simplex method improves it by bringing one nonbasic variable into the basis. The choice of which nonbasic variable to bring in is called selecting the entering variable.

For a minimization LP, the reduced cost $\bar c_j$ of a nonbasic variable $x_j$ tells us how the objective changes per unit increase of $x_j$ . If $\bar c_j < 0,$ increasing $x_j$ decreases the cost, so $x_j$ is a candidate to enter the basis.

Dantzig's rule (minimization). Among all nonbasic variables with $\bar c_j < 0,$ select as the entering variable the one with the most negative reduced cost:

k \;=\; \arg\min_{j \,\in\, N} \bar c_j,

where $N$ is the set of nonbasic indices. This maximizes the rate of objective decrease per unit increase of the entering variable.

For instance, suppose the nonbasic variables have reduced costs

\bar c_1 = 4, \quad \bar c_3 = -2, \quad \bar c_5 = -7, \quad \bar c_6 = 1.

The eligible variables (those with negative reduced cost) are $x_3$ and $x_5.$ The most negative is $\bar c_5 = -7,$ so $x_5$ is selected as the entering variable.