Adding a New Variable to an Optimal LP

After an LP has been solved to optimality, suppose a new decision variable $x_j$ is added — for instance, a new product or activity becomes available. We ask whether the current optimal basis is still optimal, or whether the new variable should enter the basis.

The test uses the shadow prices (dual values) of the original optimal solution. Let the LP be a maximization with $m$ constraints having shadow prices $y_1, y_2, \ldots, y_m$, and let the new variable $x_j$ have profit coefficient $c_j$ and constraint column

$$A_j = \begin{bmatrix} a_{1j} \\ a_{2j} \\ \vdots \\ a_{mj} \end{bmatrix}.$$

The reduced cost of $x_j$ is

$$\bar{c}_j = c_j - \sum_{i=1}^m y_i \, a_{ij} = c_j - \mathbf{y}^T A_j.$$

Optimality test (maximization).

• If $\bar{c}_j \leq 0$: the current solution is still optimal — do not introduce $x_j$.
• If $\bar{c}_j > 0$: introducing $x_j$ improves the objective — $x_j$ should enter the basis.

For example, suppose an LP has shadow prices $y_1 = 3$ and $y_2 = 2$, and a new variable $x_3$ is proposed with $c_3 = 25$ and $A_3 = \begin{bmatrix} 4 \\ 5 \end{bmatrix}.$ Then

$$\bar{c}_3 = 25 - (3)(4) - (2)(5) = 25 - 12 - 10 = 3 > 0,$$

so $x_3$ should enter the basis.