Practice: Canonical Form for a Basis

(a) Partition and inverse. With $B=\{2,4\}$ and nonbasic order $(x_1,x_3)$,

The inverse is

checked by . (b) The canonical form. First , and

So

For the objective, , giving $z_0=y^{\mathsf{T}}b=-4(8)+0(18)=-32$ and

The canonical form is $z=-32+3x_1+4x_3$. (c) The basic solution. Setting $x_N=0$ gives $x_2=8$, $x_4=-6$, so $x=(0,8,0,-6{)}^{\mathsf{T}}$. It is not feasible: violates the sign restriction. The objective value at this point is $-32$, computed as $c^{\mathsf{T}}x=-4(8)=-32$, which agrees with $z_0$. (d) Optimality. Both reduced costs, $3$ and $4$, are nonnegative, which for a minimisation is the optimality condition. But the condition applies to a basic feasible solution, and this point is infeasible, so the basis is not an optimum of the program: there is nothing here to be optimal. The constant $-32$ plays no part in either judgement. It records where the objective stands and shifts $z$ equally whichever nonbasic variable is raised, so it cannot distinguish between the available moves; only the signs of the coefficients can. Deriving the form requires only that $A_B$ be invertible. Feasibility is the separate test $A_B^{-1}b\ge 0$, and a canonical form with a clean-looking optimality verdict can describe a point outside the feasible set entirely.

The fault: comparing constants instead of reading signs. Optimality is not a comparison between two bases. It is a statement about one basis: whether any available move improves the objective. The constant records where the objective stands and shifts $z$ equally whichever nonbasic variable is raised, so it cannot say whether a better point exists.

What basis P establishes. ${\overline{c}}_5=-3$ is negative, so raising $x_5$ lowers the objective by 3 per unit. P is not optimal, despite having the lower constant. The verdict the student drew is exactly inverted for this basis: the attractive value is what makes the negative coefficient easy to overlook.

What basis Q establishes. Both nonbasic coefficients, $1.5$ and $0.5$, are nonnegative. Every available move raises the objective or leaves it alone. Q is optimal, and its basic solution has no negative component, so it is a basic feasible solution and the optimum is attained there.

The correct conclusion. The optimal value is $-25$, attained at $(10,0,6,0,3{)}^{\mathsf{T}}$. The $-40$ of basis P is the objective value at a point the program permits improving on, and, since P is not optimal, the method would move away from it rather than stop there.

Why two constants can differ this way. Each is $c_B^{\mathsf{T}}{A}_B^{-1}b$ for its own basis, so both are genuine objective values at genuine points. Neither is wrong as a number. What is wrong is treating the smaller one as the answer: minimisation seeks the smallest value over the feasible set, and the only evidence that a given point achieves it comes from the signs of that basis's reduced costs.