Solve uᵢ + vⱼ = cᵢⱼ on the occupied cells and every empty cell gets a reduced cost. A negative one means an improvement, and taking it means finding the unique cycle that cell closes in the basis and alternating plus and minus round it. The potentials are the dual solution, the reduced costs are the dual constraints, and the method is the simplex method with the tableau drawn differently.
Core ideas
Two of these are the simplex method in disguise. The third is the one readers get wrong on paper, because the shape they expect is not always the shape they get.
There are m + n potentials and only m + n − 1 equations, so the system is under-determined by exactly one degree of freedom. Fixing u₁ = 0 is a normalisation, not a fact: fix any other potential instead and every u and every v moves, while not one reduced cost changes. The lab recomputes the entire reduced-cost table under any normalisation you choose, so this is watched rather than asserted.
c̄ᵢⱼ = cᵢⱼ − uᵢ − vⱼ is the difference between shipping through cell (i, j) and shipping the same unit round the basis. Negative means the route is cheaper than the current plan by that much per unit; zero on every empty cell means no route is cheaper, which is optimality. This is the dual-feasibility test from the duality course, written for a tableau.
Adding one cell to a spanning tree creates exactly one cycle, and that cycle is what the flow moves round. Readers reach for a rectangle — along the row, down the column, back — and on the lab's default start the very first pivot has a six-cornered staircase instead, with the rectangle's fourth corner falling on an empty cell. A cycle may cross an empty cell; it may only turn at an occupied one.
The material
The potentials and what they are, then the reduced costs, then the pivot in full on a table where the obvious shape fails.
Given a basis of m + n − 1 occupied cells, the potentials uᵢ and vⱼ are the solution of uᵢ + vⱼ = cᵢⱼ over those cells, with one potential fixed arbitrarily. The reduced cost of any cell is c̄ᵢⱼ = cᵢⱼ − uᵢ − vⱼ.
Basic cells have reduced cost zero by construction. If every empty cell has c̄ᵢⱼ ≥ 0 the current plan is optimal; otherwise a cell with c̄ᵢⱼ < 0 enters.
The system is solvable exactly when the occupied cells form a spanning tree, which is why the count mattered so much in “The Transportation Problem”. Connected gives every potential a value; acyclic stops two equations from disagreeing about one of them. Solve it by starting anywhere and walking the tree: each basic cell hands a known u to an unknown v or the other way round.
Fix u_A = 0 and the potentials are u = (0, 5, 3), v = (10, 2, 4, 15). Fix v_D1 = 0 instead and they become u = (10, 15, 13), v = (0, −8, −6, 5) — every one of the seven has moved, by 10. Not one of the twelve reduced costs changes, because each is cᵢⱼ − uᵢ − vⱼ and the shift cancels. The lab has a control for each of the seven and reports the shift each produces: 0, 5, 3, −10, −2, −4, −15.
The basis is a spanning tree of the rows and columns. Adding one more cell to a spanning tree creates exactly one cycle, and that cycle alternates between moving along a row and moving down a column. Put a plus on the entering cell, then alternate signs round the cycle. Every plus cell gains θ, every minus cell loses it, and the row and column sums are unchanged for every θ.
(C, D1) enters with a reduced cost of −9. The cycle the lab computes has six corners: (C,D1)+ (C,D4)− (B,D4)+ (B,D2)− (A,D2)+ (A,D1)−. The rectangle a reader guesses — along row C, up column D1 — would need to turn at (B, D1), and (B, D1) is empty, so the guess is refused and the walk goes further.
θ is the smallest allocation on a minus cell: the minus cells carry 10, 5 and 5, so θ = 5 and (B, D2) leaves. The cost falls from 520 to 475, which is 9 × 5 less.
The lab draws the guess alongside the computed cycle and names the corner that breaks it. On the second pivot of the same run the guess closes and the two agree; on the third, the entering cell's column holds no other occupied cell at all, so there is no rectangle to draw. The guess is not always wrong, which is exactly why it has to be checked.
The second pivot of the default run brings (A, D4) in, and the smallest allocation on a minus cell is 0 — the zero at (A, D1). So θ = 0: the cell enters, (A, D1) leaves, the basis is different, and the cost stands still at 475.
The run's costs are 520 → 475 → 475 → 435, and an implementation asserting that every iteration is strictly cheaper would fail on the shipped example. Non-increasing is the claim. This is the degeneracy of the simplex course, arriving in a tableau that looks nothing like a simplex tableau.
Three pivots from the north-west start, one from the least-cost start, and both land on 435 at the same plan. The entering rule moves the path and not the destination: on the surplus table, Dantzig's rule takes three pivots from either start while Bland's takes four from one and six from the other, all four finishing at 605.
And the dummy question from “The Transportation Problem” can now be settled with a number. Price the dummy column at ten times the dearest real route — 160 rather than 0 — and re-solve the surplus table. The real shipping bill is 605 either way. Every feasible plan sends the same 10 units to the dummy, so the penalty adds a constant of 1600 to every plan and the cheapest one cannot move. What does move is the least-cost start, from 665 to 635, because that rule reads the cost table; the north-west start does not move at all, because it never reads one.
Interactive
u and v price the empty cells, and a closed path of ±θ does the pivot
Method
Potentials, prices, entering cell, cycle, theta, leaving cell. Then do it again; there is nothing else in the method.
Fix one — any one — and walk the tree, each basic cell determining one new potential from one already known. If you get stuck with potentials still unknown, the basis is disconnected and the repair from “The Transportation Problem” is needed.
c̄ᵢⱼ = cᵢⱼ − uᵢ − vⱼ. The basic cells must all price at zero; if one does not, the potentials are wrong and there is no point going on. All non-negative on the empty cells means you have finished.
Most negative, or first negative in row order. Say which you are using: they pick different cells on the very first tableau of the worked example, and they take different numbers of pivots to the same answer.
From the entering cell, alternate row moves and column moves back to where you started. Every corner after the first must be an occupied cell. You may cross an empty cell in passing; you may not turn at one, and the cycle is unique so there is nothing to choose.
θ is the smallest allocation on a minus corner. Add it to the plus corners, take it off the minus corners, and remove exactly one cell that hit zero — if two did, keep one as a basic zero, or the count breaks.
Three pivots. Everything below is what the lab reports at each step, including the degenerate one and the two occasions on which the rectangle guess fails.
Pivot 2 is the one to sit with. A cell enters, a cell leaves, the plan does not move an ounce of anything, and the cost is identical. That is not a bug and it is not a waste: the basis has changed, and the next tableau prices the cells differently because of it, which is how pivot 3 becomes available.
For a rehearsal, run the same table from the least-cost start. It opens at 475 and one pivot takes it to 435. Then ask which start you would rather have: the cheaper opening took fewer pivots here, and on the surplus table it takes more under one of the two entering rules. There is no theorem in this neighbourhood, which is worth knowing.
The harder rehearsal: switch the entering rule to Bland's and run the default table again. The first cell to enter is now (1,4) at −4 rather than (3,1) at −9, and the path is different all the way down. Both finish at 435. A pivot rule is a policy about the route, not about the destination.
You should be able to solve the potentials from any normalisation, price every empty cell, state the entering rule you are using and apply it, trace the unique cycle turning only at occupied cells, compute θ over the minus corners, and say which cell leaves — including when θ is zero.
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.