A tableau can be optimal in its objective row and infeasible in its right-hand column, which is exactly the state a new constraint or an out-of-range change leaves. The dual simplex method restores feasibility while preserving optimality: the leaving row is a negative right-hand side, and the entering column comes from a ratio test along that row against the objective row. It is the primal simplex run on the dual, seen in the primal tableau, and it is why re-optimisation and branch-and-bound are affordable at all.
Core ideas
One hard idea: the old tableau describes the old basis, and that basis is still a basis of the new problem. Everything else is the two rules swapping places.
The objective row and the right-hand column can be checked independently. The primal simplex keeps the right-hand column non-negative and hunts for a non-negative objective row; the dual simplex keeps the objective row non-negative and hunts for a non-negative right-hand column. Both are walking from a basis to a neighbouring basis; they differ in which property they refuse to give up.
In the primal method the entering column is chosen first, by the objective row, and a ratio test down that column picks the leaving row. Here the leaving row is chosen first, by the right-hand column, and a ratio test along that row picks the entering column. The ratio is |zⱼ| ÷ |a_rj| over the negative entries only, because only a negative entry can lift a negative right-hand side.
For a maximisation the reported value on an infeasible tableau is an overstatement — it is what the basis would earn if the plan were legal — so each pivot lowers it, monotonically, until feasibility is restored and the number is real. On the workshop cut it goes 36, 27, 25. That direction is a check: if the value rises, the ratio test was misapplied.
The material
The starting state, the two rules, what each pivot does to the value, and the two ways the method can stop.
A new constraint has just been added and the plan breaks it. The temptation is to start again, on the reasoning that the old tableau described the old problem. It described the old basis, and that basis is still a basis of the new problem — just not a feasible one. Restoring feasibility is cheaper than rebuilding, and this is the method that does it.
Given a tableau whose objective row is non-negative (optimal) but whose right-hand column has a negative entry (infeasible), one dual pivot is: choose as the leaving row r the one with the most negative right-hand entry; choose as the entering column the j minimising |zⱼ| ÷ |a_rj| over the columns with a_rj < 0; and pivot on (r, j).
The dual simplex method repeats that until no right-hand entry is negative, at which point the tableau is both feasible and optimal, or until some leaving row has no negative entry at all, at which point the problem is infeasible.
The ratio is worth reading rather than memorising. The entering column has to have a negative entry in row r, because raising that variable must raise a negative right-hand side towards zero. Among those candidates, |zⱼ| ÷ |a_rj| is the amount of objective given up per unit of infeasibility removed, so choosing the smallest is choosing the cheapest way to become legal. That is why the objective-row entries appear in the numerator: this is a cost-per-unit comparison, not an amount.
And why it is the primal simplex on the dual. A negative right-hand entry in the primal tableau is a violated dual constraint; the row with the most negative entry is the dual's entering variable under the steepest rule; and the ratio test along that row is the dual's own leaving-variable ratio test. Everything happens in the primal tableau, so no second tableau has to be built, which is the practical point.
Add x1 + x2 ≤ 10 instead. After the same two row operations the new row's right-hand entry is +1 rather than −3, so there is no negative entry anywhere and the method performs zero pivots. The tableau was already feasible and already optimal.
That is the cheapest possible outcome and it is the common one. The previous lesson's substitution test predicts it without doing even this much work: the plan reads 8 against a limit of 10.
The plan (2, 6, 0) earns 46 and uses 8 units in total. Add x1 + x2 + x3 ≤ 6, which it breaks by 2. After the row operations the new row reads 0, 0, −1, 0, −1, 0, 1 | −2, and the ratio test over its two negative entries gives |4| ÷ |−1| = 4 for x3 and |2| ÷ |−1| = 2 for s2.
So s2 enters, one pivot is enough, and the answer is 42 at (4, 2, 0). One pivot to re-optimise a programme that a fresh solve would have restarted from an initial basis.
It stops successfully when no right-hand entry is negative: the tableau is feasible, the objective row was never allowed to go negative, so the basis is optimal and the number is real. It stops unsuccessfully when the chosen leaving row has no negative entry at all. That row then asserts that a non-negative combination of non-negative variables equals a negative number, which nothing satisfies, and the new problem is infeasible. Adding x1 + x2 ≥ 9 to the workshop does exactly that: the region's largest total is 8, and the lab reports the rule as unsatisfiable rather than pivoting for ever.
One habit is worth building here and the lab's hint asks for it directly: before moving the slider, try to say which plan the method will land on. You will usually be wrong, and being wrong on purpose is how the ratio test along the objective row stops being a rule to apply and starts being a reason. On the workshop cut, most readers predict (2, 3) or (4, 1) — plans that obey the new rule and look like small adjustments — and the answer is (0, 5), which abandons the first product altogether.
This method is also the reason a search tree is affordable. Integer Programming re-solves every branch-and-bound child exactly this way, starting from its parent's final tableau with one bound added, which is one cut and a handful of dual pivots rather than a fresh solve per node. A tree with hundreds of nodes costs what a few dozen solves would, and this lesson is where that becomes believable rather than asserted.
Interactive
the dual ratio test tabulated at every pivot, and the objective moving the other way
Method
Append, clear, then alternate between the right-hand column and one row. Both rules are simpler than their primal counterparts.
The new row arrives in terms of the original variables, and the basic variables have to be eliminated from it before it is a tableau row. One row operation per basic variable that appears in it; the lab prints each one with the variable it removed.
The most negative entry. Note that this is a choice about infeasibility and involves the objective not at all — which is the mirror of the primal method, where the entering column is chosen from the objective row and involves feasibility not at all.
|zⱼ| ÷ |a_rj| for each nonbasic column with a negative entry in the row. A positive or zero entry is ineligible, because raising that variable cannot lift a negative right-hand side. The smallest ratio enters; a tie is a choice, as it is in the primal method.
For a maximisation it must fall. If it rises, the ratio test was taken over the wrong entries or the wrong row was chosen. Repeat until no right-hand entry is negative — or until a leaving row has no negative entry, which means the new problem is infeasible.
The starting tableau is the workshop's own final tableau with one row appended. Nothing is rebuilt, and the ratio test is written out in full at both pivots, including the entries that were not eligible.
The two pivots cost what two pivots cost, and the fresh solve they replace would have started from an initial basis and worked up. On a two-variable programme that difference is a curiosity. On a branch-and-bound tree with one added bound per node it is the difference between a tractable search and an impossible one.
The ineligible entry at pivot 2 is worth pausing on. s4 has a +1 in row 1, and raising s4 would make that row's right-hand side more negative rather than less. The ratio test's restriction to negative entries is that observation, and it is the half of the rule most often dropped.
For a faded rehearsal, cut the three-activity programme with x1 + x2 + x3 ≤ 6. The supplied move is that the plan reads 8 there, so the new row's right-hand entry after clearing is −2. Find the ratio test's two candidates, say which enters, predict the plan it lands on, and only then check — the prediction is the exercise.
You should be able to append a row and clear the basic variables out of it, choose the leaving row from the right-hand column, take the ratio test along that row over the negative entries only, state why the value falls at every pivot, and recognise the row with no negative entry as a proof of infeasibility.
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.