Practice: Reduced Costs and the Optimality Test

With $B=\{2,1\}$ in that order, and $c_B=(c_2,c_1{)}^{\mathsf{T}}=(4,1{)}^{\mathsf{T}}$. Then and . For $x_3$, with $c_3=0$ and $A_3=(1,0{)}^{\mathsf{T}}$, the reduced cost is ${\overline{c}}_3=0-(4,-3)\cdot (1,0{)}^{\mathsf{T}}=-4$. The reduced cost is negative, so $x_3$ does improve the objective and the basis is not optimal. The student's reasoning fails because a zero cost coefficient does not imply a zero reduced cost: the reduced cost also prices the compensating movement of the basic variables, captured by the term $y^{\mathsf{T}}{A}_j$. Since $y$ depends on the basis, the same variable has different reduced costs at different bases, so reduced costs must be recomputed after every basis change rather than read off $c$.

(c) The sign condition. For a minimisation, a basis is optimal when every reduced cost is NONNEGATIVE: a negative ${\overline{c}}_j$ means raising $x_j$ lowers the objective, which is an improvement. Here , so the basis is not optimal.

Applied to the same numbers, the maximisation condition, stop when every reduced cost is nonpositive, would look at ${\overline{c}}_3=-4\le 0$ and declare the basis optimal. Same arithmetic, opposite verdict. The condition is not a property of the reduced costs; it is chosen by the direction of the objective, and applying the wrong one terminates the algorithm at a point that is not optimal.

The stopping rule 'all reduced costs nonnegative' is derived for minimization: a negative reduced cost marks a direction that lowers the objective. For maximization the improving directions are the ones with positive reduced cost, so a rule that stops when none are negative will stop at the first basis where nothing is negative, which is typically immediately and has nothing to do with maximal value. The two correct routes are: convert the objective by minimizing $-c^{\mathsf{T}}x$ and keep the rule unchanged, in which case the reported minimum $v$ corresponds to an original maximum of $-v$; or keep the objective as $c^{\mathsf{T}}x$ and reverse the rule to stop when every reduced cost is nonpositive, in which case the reported value is the maximum directly. The colleague's result would be correct by coincidence only if the starting basis happened to be optimal for the maximization problem, which for this rule means every nonbasic reduced cost is exactly zero or the starting basis is already optimal in both senses, for instance when all nonbasic reduced costs are zero, so no direction changes the objective at all.