Simplex Optimality Test¶

Proposition¶

For a maximization LP with a feasible canonical tableau written as $\displaystyle z+\sum_{j\in N}q_jx_j=z_0$ $z_{0}$ , if $q_j\ge0$ for every nonbasic variable, the current basic feasible solution is optimal. Here $N$ is the nonbasic index set and every variable is nonnegative.

Interpretation¶

The optimality test tells the simplex method when to stop. It checks whether increasing any nonbasic variable from zero could raise $z$ ; if none could, the current basic feasible solution is optimal, and the tableau itself is the proof.

An optimal simplex tableau with the objective-row coefficients of the nonbasic variables s1 and s2 highlighted; both are nonnegative, so no increase can improve z.

In the final Giapetto tableau the nonbasic variables are the slacks $s_1$ and $s_2$ , both with objective-row coefficient $1$ . Read as an equation, the row says $z=180-s_1-s_2$ $s_{2}$ . Since slacks are nonnegative, no feasible solution has $z>180$ $180$ , and the current solution with $s_1=s_2=0$ reaches this bound.

Each condition has a role. The objective row comes from the original equations by row operations, so it holds for every feasible solution, not only the current one; this turns a sign check into a proof. Canonical form makes the row express $z$ through the nonbasic variables only, so $z_0$ is the current value and $q_j$ is the effect of increasing $x_j$ alone. Feasibility is needed because the row only gives the bound $z\le z_0$ $z_{0}$ , and this bound is the optimum only because a feasible point attains it.

With the objective on the left, $z+q_jx_j=\ldots$ means that $z$ falls by $q_j$ per unit of $x_j$ . A negative $q_j$ therefore signals possible improvement, which is why the entering variable rule looks for the most negative coefficient. A coefficient $q_j=0$ means $x_j$ could increase without changing $z$ , which often points to multiple optimal solutions.

Key Results¶

The sign test depends on the course objective-row convention.
Feasibility and canonical form are required before applying the test.
A negative coefficient calls for further simplex analysis; degeneracy means it does not alone prove that a strictly better feasible vector exists.

Examples¶

In the figure, $z=180-s_1-s_2$ and $s_1,s_2\ge0$ certify $z\le180$ $180$ . Setting both nonbasic slacks to zero gives $x_s=20$ $20$ , $x_t=60$ $60$ , $s_3=20$ $20$ , attaining 180. A zero nonbasic objective coefficient can indicate an alternative optimum, but a distinct solution requires a positive feasible movement; a degenerate zero-length pivot is insufficient.

$z+(7/5)s_1+(1/5)s_2=17$ proves $z\le17$ $17$ .
$z-(1/2)x_2+(3/2)s_1=15$ still has a negative coefficient to investigate.

Prerequisites¶

Sources¶

OR Modelling · Week 2

Aliases: optimality test Symbols: element of, sum

Last updated: 20 October 2026 03:02