A tableau is the standard-form system [A | b] with one extra row for the objective, z - cᵀx = 0. When the basic columns are identity columns the basic feasible solution can be read straight out of the right-hand column with no solving at all, and one step of the method is a single Gauss-Jordan pivot applied to every row of the tableau — the objective row included, because it is one more equation.
Core ideas
The arithmetic is “Gaussian Elimination” and nothing else. What is new is the extra row, and the habit of reading a solution instead of solving for one.
Every row is an equation that stays true. The top m rows are the constraints in standard form, and the bottom row is the objective rearranged to z - c₁x₁ - … - cₙxₙ = 0, which is why it begins life holding the negated objective coefficients. Nothing in the tableau is a note to yourself; it is all the same system written in a different basis.
When the basic columns are identity columns, row i says x_{B(i)} + (nonbasic terms) = b_i, and the nonbasic terms are all zero. So the basic variable in row i equals that row's right-hand entry, every other variable is zero, and the bottom-right entry is z. That free reading is the entire reason for keeping the tableau in this shape.
Choose an entry a_rj that is not zero. Divide row r by it so the entry becomes 1, then subtract multiples of that row from every other row until the rest of column j is zero. Column j is now an identity column and the column that used to carry row r's basic variable is not, so x_j has entered the basis and that variable has left.
The material
Where every entry comes from, why the objective row is inside the row operations rather than beside them, and what an illegal pivot produces.
For a standard-form programme maximise cᵀx subject to Ax = b, x ≥ 0 with A of size m × n, the tableau at a basis B is the m constraint rows together with an objective row representing z - cᵀx = 0. It is held so that each basic column is an identity column and the objective row has a zero in every basic column.
“Standard Form, Slack and Surplus” already did the work of turning inequalities into equations. Take maximise 3x₁ + 5x₂ subject to x₁ ≤ 4, 2x₂ ≤ 12, 3x₁ + 2x₂ ≤ 18; add one slack per row and the three slacks are already an identity, so the first tableau needs no work beyond writing -3 and -5 in the objective row.
Read it. The basic columns are s₁, s₂, s₃, so s₁ = 4, s₂ = 12, s₃ = 18, the nonbasic x₁ and x₂ are zero, and z = 0. That is the origin, and the three slacks at their full values say that no plant hours have been used. Nothing was solved: the right-hand column was copied out.
A pivot on row r and column j with a_rj ≠ 0 is the pair of row operations: replace row r by row r ÷ a_rj, then for every other row — including the objective row — replace it by row - (its entry in column j) × (the new row r). The entering variable is x_j and the leaving variable is the one row r was carrying.
Take the pivot on row 2, column x₂, whose entry is 2. Halving row 2 makes it 1. Row 1 has a zero in column x₂ so it does not change at all. Row 3 has a 2 there, so it loses twice the new row 2. The objective row has -5, so it gains five times the new row 2.
The basis is now {s₁, x₂, s₃}. Reading again: x₂ = 6, s₁ = 4, s₃ = 6, x₁ = 0, z = 30. That is the corner (0, 6) and the objective value listed for it in “Adjacent Corners and the Simplex Idea”. One pivot, one edge, and the new reading is free for the same reason the old one was.
Because it is an equation. z - 3x₁ - 5x₂ = 0 is as true as the three constraint rows, and a row operation that keeps a system equivalent has to be applied to all of it. Carry the objective row along and the bottom-right entry is always the objective value at the current basis, with no separate arithmetic to get wrong.
Leave it out and the tableau still looks finished: the constraint rows are right, the reading of x is right, and only z and the objective row entries are stale. This is the same error as dropping the constant column part-way through an elimination, which “Gaussian Elimination” named on the Algebra path, and it fails the same way — silently, with a plausible answer at the end.
Any non-zero entry is a legal row operation, and the arithmetic does not care whether the result is a corner. Pivot the same tableau on row 3 and column x₂ instead and you get x₂ = 9, s₂ = -6, a bottom-right entry of 45 — higher than the true optimum of 36 — and a point, (0, 9), that is outside the region because it uses 18 of plant B's 12 hours. The tableau is a correct system throughout; what it has stopped describing is a feasible point.
Choosing the row so that this cannot happen is “The Ratio Test”, and choosing the column so that the objective actually improves is “Reduced Costs and the Optimality Test”. Until then, pivot by hand and check the right-hand column for a negative entry every time.
Interactive
A Gauss-Jordan step on a chosen column, with the objective row carried through like any other
Method
Two minutes of setup saves the error that is hardest to find later: a tableau that is arithmetically perfect and describes the wrong system.
One slack per ≤ row, and the objective rearranged to z - cᵀx = 0. Write the column names across the top and keep them; half the mistakes in a tableau are a column read in the wrong place.
maximise 3x₁ + 5x₂ gives -3 and -5, not 3 and 5. The row is the equation z - 3x₁ - 5x₂ = 0 with the z column left implicit, and the sign is what makes an improving column show up as a negative entry.
Name the basic variable of each row, copy the right-hand entry as its value, set the rest to zero, and read z from the bottom right. If any basic value is negative, stop: this tableau is not at a corner.
New row r is the old one over a_rj. Then every other row, objective row included, loses its column-j entry times the new row r. Column j should end as an identity column with a zero in the objective row.
Name the new basis, read the values and z, and check the change in z against the pivot: for a maximisation it should not have gone down. A negative right-hand entry means the leaving row was chosen badly, and choosing it well is the subject of “The Ratio Test”.
The entering column is x₂ and the leaving row is row 2. Watch the objective row: it is the fourth row of the arithmetic, not a summary written afterwards.
Three things to notice. Row 1 did not change, because its entry in the pivot column was already zero — a row with a zero there is untouched by the pivot, which is worth knowing before “The Ratio Test” explains that such a row also imposes no limit. Column x₂ is now an identity column with a zero in the objective row, which is the signature of a basic column. And s₂ has left the basis: its column is (0, 1/2, -1, 5/2), no longer an identity column.
The objective row also carries a fact about s₂. Its entry is 5/2, meaning that pushing s₂ back up from zero — leaving plant B hours unused again — would cost 5/2 per hour. That number is a reduced cost, and “Reduced Costs and the Optimality Test” is about reading the whole row that way.
For a faded rehearsal, pivot the same starting tableau on row 1, column x₁ instead. The supplied first move is that the pivot entry is 1, so no division is needed and the fractions never appear. Carry out the other three row operations, read the new basis, point and z, and then say which column of the new tableau shows that the method is not finished. Check all four rows against the lab before opening the quiz.
You should be able to write the objective row from a maximisation, name the basic variable of every row, read the point and z off the right-hand column, carry out a named pivot with the objective row inside it, and say what a negative right-hand entry afterwards means.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.