Reduced Cost Problems

Reduced cost problems ask you to compute reduced costs for a basis and use them to test optimality or choose an entering variable.

Formula

For standard-form minimization:

\[\min c^Tx\]

subject to:

\[Ax=b, \qquad x\ge 0,\]

the reduced cost of variable $x_j$ is:

\[\bar c_j=c_j-c_B^TB^{-1}A_j.\]

Vector Formula

For all variables:

\[\bar c^T=c^T-c_B^TB^{-1}A.\]

Basic variables have reduced cost zero.

Optimality Test

For a minimization problem, if the current basis is feasible and:

\[\bar c_j\ge 0\]

for every nonbasic variable, then the current BFS is optimal.

Entering Variable

If some nonbasic variable has:

\[\bar c_j<0,\]

then increasing $x_j$ can decrease the objective value.

That variable is a candidate entering variable.

Common Calculation Steps

  1. Identify $B$ and $c_B$.
  2. Compute $B^{-1}$.
  3. Compute $p^T=c_B^TB^{-1}$.
  4. Compute each $\bar c_j=c_j-p^TA_j$.
  5. Check signs.
  6. State optimal or choose an entering variable.

Checklist

Be careful with:

  • basis column order
  • matching $c_B$ to the same order
  • minimization sign convention
  • not recomputing reduced costs for basic variables unnecessarily

See Also

Added drill source

Use Reduced Cost and Optimality Worked Example for full calculations.

Exam checkpoint

Practice under exam timing. Write the full pipeline: model, standard form if needed, BFS/reduced costs if asked, simplex iterations if asked, final objective value and interpretation.