Optimality and Termination - Simplex, Pivot by Pivot

Simplex stops when no reduced cost can improve the objective. This lesson treats the final z-row as a certificate and shows the deterministic Bland tie-break used by the engine. It is a computation certificate for these LPs, not a full termination proof.

highlighted = computed this step

Optimality certificate

At the final tableau, the reduced costs are nonnegative, including 1/3 and 1/3 under the slack columns. Why: with no negative reduced cost, no nonbasic variable can improve z.

\text{all reduced costs are nonnegative}

Bland tie-break

In the tie-break example, the second pivot leaves row 1 by the lowest-basis rule. Why: deterministic ties prevent cycling in the pivot rule used here.

\text{lowest basis index breaks ratio ties}

What is shown

The diagrams show termination on the exact LPs rendered here, not a general proof. Why: the proof belongs to the theory, while the tableau certifies these computations.

\text{certificate for these exact tableaus}

Diagram note

Stopping is honest only when the displayed final z-row has no negative reduced costs. Pixel positions are rounded for layout; every number shown is exact.

\text{no negative reduced costs means stop}