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
- Identify $B$ and $c_B$.
- Compute $B^{-1}$.
- Compute $p^T=c_B^TB^{-1}$.
- Compute each $\bar c_j=c_j-p^TA_j$.
- Check signs.
- 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.