The Full Tableau Simplex Method

One simplex iteration is already familiar: price the columns, pick one that improves, run the ratio test, update the basis. Doing that repeatedly by forming $A_B^{-1}$ each time is possible and slow.

The tableau keeps the whole system in one table and updates it in place. Every quantity an iteration needs is already sitting in the array, so a pivot is row operations and nothing else, and the two stopping conditions are patterns visible on the page.

What this adds beyond the single iteration is termination: deciding at each step whether to continue, and on stopping saying which condition fired and what the table now reports. A learner who can pivot but cannot say why the method stopped has the arithmetic without the algorithm.

Setting up. The program must already be in standard form: minimisation, equality constraints, all variables nonnegative.

1. Write the $m$ constraint rows as coefficients followed by the right-hand side.
2. Add an objective row holding $c^{\mathsf{T}}$ and a final entry of $0$.
3. Make the tableau canonical for the starting basis: divide and eliminate until each basic variable's column is a unit vector in the constraint rows and zero in the objective row.

Step 3 is the one most often skipped. If a basic variable has a nonzero entry in the objective row, that row does not hold reduced costs and the optimality test reads the wrong numbers. When the starting basis is a set of slack variables with zero cost, the tableau is already canonical and no work is needed, which is why the step is easy to forget when it is required.

Each iteration.

Reading the current state. At any point the right-hand column holds the basic variables' values in the order their unit columns appear; every nonbasic variable is zero. The bottom-right entry is $-z_0$, so the objective value is its negation.

On the entering choice. Any negative reduced cost is a legitimate choice. Taking the most negative is a convention with no guarantee attached: it maximises the improvement per unit of the entering variable, not the improvement actually achieved, because the step length is decided separately by the ratio test.

Start from $B=\{3,4\}$, the slack basis.

The initial tableau. Both basic variables have zero cost, so their objective-row entries are already zero and the tableau is canonical as written.

The basic solution is $x=(0,0,4,6)$ with objective $0$.

Iteration 1.

Optimality test. ${\overline{c}}_1=-3$ and ${\overline{c}}_2=-2$ are negative, so continue.

Entering column. Most negative is ${\overline{c}}_1=-3$, so $x_1$ enters.

Ratio test. Column 1 has entries $1$ and $1$, both positive. Ratios $4/1=4$ and $6/1=6$. The minimum is $4$ in row 1, so $x_3$ leaves and $\theta =4$.

Pivot. The pivot entry is already $1$, so row 1 is unchanged. Eliminate column 1 elsewhere: row 2 becomes row 2 minus row 1; the objective row becomes objective row plus $3\times$ row 1.

Row 2: $(1,3,0,1\mid 6)-(1,1,1,0\mid 4)=(0,2,-1,1\mid 2)$.

Objective: $(-3,-2,0,0\mid 0)+3(1,1,1,0\mid 4)=(0,1,3,0\mid 12)$.

Iteration 2.

Optimality test. The reduced costs are $(0,1,3,0)$. None is negative, so the method stops: optimal.

The basic variables are $x_1$ from row 1 and $x_4$ from row 2, taking the right-hand values $4$ and $2$. The nonbasic variables $x_2$ and $x_3$ are zero. So

the objective value being the negation of the bottom-right entry $12$.

Checking without trusting the table. Substituting into the original program: $x_1+x_2+x_3=4+0+0=4$ and $x_1+3x_2+x_4=4+0+2=6$, both satisfied, all components nonnegative. The objective is $-3(4)-2(0)=-12$, matching. The check is worth running because a pivot arithmetic error produces a tableau that still looks well formed.

What the reduced costs now say. ${\overline{c}}_2=1$ means raising $x_2$ from zero would raise the objective by $1$ per unit. The wrong direction for a minimisation. ${\overline{c}}_3=3$ says the same of the departed slack $x_3$. Both being positive is exactly why no further move improves.

A tableau with an arithmetic error still looks like a tableau. These four checks cost seconds and catch most of what goes wrong.

Every basic column is a unit vector. After a pivot, each basic variable's column must have a $1$ in its own row, $0$ in every other constraint row, and $0$ in the objective row. A nonzero objective-row entry for a basic variable means the elimination was not carried through, and the reduced costs in that row are not reduced costs.

The right-hand column is nonnegative. Every basic variable's value must be $\ge 0$. A negative entry means the current point is not feasible, which cannot happen if the ratio test was applied correctly, so a negative right-hand side is a signal that the wrong leaving row was chosen, not a result to carry forward.

The objective value moved the right way. For a minimisation the objective must not increase. Comparing the bottom-right entry before and after a pivot: it should grow or stay equal, since it holds $-z_0$. A step with that leaves it unchanged, or moves it the wrong way, indicates an error in the objective-row update.

The reported point satisfies the original constraints. On termination, substitute back into the program as first written. This is the only check that does not rely on the tableau being correct, so it is the one worth running before reporting an answer.

A note on what these do not catch. All four checks pass on a tableau built from a program that was converted to standard form incorrectly. The arithmetic is then correct throughout and the answer solves a different problem. Nothing inside the method detects that; it is caught by re-reading the conversion against the original description.

Two situations stop or stall the method, and both are visible in the tableau rather than reported by anything.

Unboundedness: an entering column with no positive entry.

Take $min-x_1$ subject to $x_1-x_2+x_3=3$, $x\ge 0$, from the basis $\{3\}$. The initial tableau is

$x_1$ enters; the ratio test has one candidate, $3/1=3$, so $x_3$ leaves at $\theta =3$. After pivoting:

Now ${\overline{c}}_2=-1$, so $x_2$ enters. Its column holds the single entry $-1$, which is not positive. No leaving variable exists. Raising $x_2$ increases $x_1$ by the same amount, the basic variable rises rather than falls, so feasibility is never lost and the objective decreases without limit. The program is unbounded, and the tableau says so structurally.

The practical warning: an unbounded linear program almost always means a missing constraint, not a business opportunity. Something that limits the activity in reality was not written down.

Degeneracy: a tie in the ratio test.

Take $min-2x_1-x_2$ subject to $x_1+x_2+x_3=4$, $2x_1+2x_2+x_4=8$, $x\ge 0$, from $\{3,4\}$. With $x_1$ entering, the ratios are $4/1=4$ and $8/2=4$. A tie. Taking row 1, so $x_3$ leaves:

The basic variable $x_4$ now sits at zero: the basic feasible solution is degenerate. The reduced costs are all nonnegative, so this tableau is optimal, at $x=(4,0,0,0)$ with objective $-8$.

What degeneracy costs in general is that a later pivot may have $\theta =0$: the basis changes and the point does not, so the objective does not fall. A sequence of such steps can in principle return to a basis already visited, and the method cycles. Anti-cycling rules such as Bland's prevent this by constraining the entering and leaving choices; the tableau alone offers no protection.

What a degenerate tableau does not mean. It is not an error, and it does not make the answer wrong or the problem ill-posed. It means one basic variable happens to sit at zero, so more than one basis describes the same corner.

Including a nonpositive entry in the ratio test. The entering column holds $2$, $-1$ and $3$; the learner computes all three ratios and takes the most negative as the minimum. A basic variable with a nonpositive entry does not fall as the entering variable rises, so it never limits the step. Including it produces a step that drives another basic variable negative, and the next tableau has a negative right-hand entry. The point is no longer feasible.

Forgetting the objective row. The entering column is eliminated from every constraint row and the objective row is left alone. The tableau now looks canonical, but the bottom row still holds the previous basis's reduced costs. The optimality test reads stale numbers, and the method either stops early or chooses a column that does not improve.

Stopping at the first nonnegative reduced cost. Seeing ${\overline{c}}_2=1$, the learner concludes optimality. The test is over every nonbasic column, not one: a single positive reduced cost says only that raising that particular variable would not help. Optimality requires no negative entry anywhere in the row.

Reporting only the basic variables. The final tableau shows $x_1=4$ and $x_4=2$, and the answer is given as $(4,2)$. The solution is a vector over all variables, and the nonbasic ones are zero: $x=(4,0,0,2)$. Dropping them loses the distinction between a variable that is zero and a variable that is absent, and makes the answer impossible to check against the original constraints.

What the four have in common is that each leaves the tableau looking well formed. Three of them are caught by the checks in the previous block; the fourth is caught only by substituting the reported point back into the program as first written.

The same iteration can be carried two ways, and they differ in what they store, not in what they decide.

Why the tableau is taught first. Every number an iteration needs is on the page, so the decisions are visible and the method can be executed and checked by hand. That makes it the right vehicle for learning what the algorithm does.

Why it is not what solvers do. On a program with many more columns than rows, updating every entry each pivot is wasted work, since most columns are never examined. Practical implementations keep a factorisation of $A_B$ and price columns selectively; the revised simplex method is the same algorithm organised that way.

What is identical. The entering choice, the ratio test, the step, the sequence of bases, and the optimum. Given the same pivoting rule, both produce the same path. A disagreement between them is an arithmetic error in one, not a difference of method.

The learning risk. Because the tableau updates rather than derives, fluent pivoting can coexist with not knowing what $A_B^{-1}$ currently is or why a reduced cost has its value. Reconstructing one reduced cost from $c_j-p^{\mathsf{T}}{A}_j$ and checking it against the table is the exercise that keeps the two connected.