Optimality Conditions

For standard-form minimization, a feasible basis is optimal when all reduced costs are nonnegative.

Feasibility

A basis is feasible if $B^{-1}b\ge0$.

Reduced Costs

The reduced costs are $\bar c^T=c^T-c_B^TB^{-1}A$.

Optimal Basis

A basis is optimal if $B^{-1}b\ge0$ and $\bar c\ge0$.

Why

In canonical form, $c^Tx=c_B^TB^{-1}b+\bar c_N^Tx_N$. Since $x_N\ge0$, nonnegative $\bar c_N$ cannot decrease the cost.

Checklist

Check feasibility and reduced-cost nonnegativity.

See Also

• Reduced Costs
• Canonical Form

Exam checkpoint

For simplex questions in minimization form, negative reduced costs indicate possible improvement. Use $u=B^{-1}A_j$, apply the ratio test only to positive components of $u$, then update the basis.