Reduced Costs and the Optimality Criterion

Consider a linear program in standard form:

$$\text{minimize } \mathbf{c}^T\mathbf{x} \quad \text{subject to} \quad A\mathbf{x}=\mathbf{b},\ \mathbf{x}\geq\mathbf{0}.$$

At a basic feasible solution, the variables split into basic variables $\mathbf{x}_B$ (with cost vector $\mathbf{c}_B$) and nonbasic variables $\mathbf{x}_N$. The columns of $A$ corresponding to the basic variables form the invertible basis matrix $B$.

For any nonbasic variable $x_j$, the reduced cost is defined as

$$\bar{c}_j = c_j - \mathbf{c}_B^T B^{-1} \mathbf{A}_j,$$

where $\mathbf{A}_j$ is the $j$th column of $A$.

The quantity $\mathbf{y}_j = B^{-1}\mathbf{A}_j$ is exactly the column of $x_j$ in the simplex tableau after row-reduction, so we will write the formula compactly as

$$\bar{c}_j = c_j - \mathbf{c}_B^T \mathbf{y}_j.$$

Interpretation: $\bar{c}_j$ is the rate of change of the objective per unit increase of $x_j$ above $0$. If $\bar{c}_j<0$, pushing $x_j$ up decreases the objective; if $\bar{c}_j>0$, pushing $x_j$ up makes things worse.

Note: For every basic variable, $\bar{c}_j=0$ — the column $\mathbf{y}_j$ is a unit vector $\mathbf{e}_i$, and $\mathbf{c}_B^T\mathbf{e}_i=c_{B_i}=c_j$.

Illustrative computation. Suppose a nonbasic variable has $c_j=5$, $\mathbf{c}_B=\begin{bmatrix}2\\4\end{bmatrix}$, and $\mathbf{y}_j=\begin{bmatrix}1\\-1\end{bmatrix}$. Then

$$\bar{c}_j = 5 - \begin{bmatrix}2 & 4\end{bmatrix}\begin{bmatrix}1\\-1\end{bmatrix} = 5 - (2-4) = 5-(-2) = 7.$$