One worker per job and one job per worker: a transportation problem with every supply and every demand equal to one, so its corners are the permutations. The Hungarian method takes constants off rows and columns until the zeros carry a complete assignment, and the constants it has taken are a dual solution whose total climbs until it equals the assignment's cost. The one step that is done properly here is the cover, which is a matching and not a drawing.
Core ideas
The reductions are easy to justify and easy to believe. The cover is the step that is usually taught wrong, and the dual is the reason any of it terminates.
Every complete assignment uses exactly one cell of each row, so subtracting t from a whole row lowers every assignment's total by exactly t. Not by at most t, not by between zero and t — by t. The lab measures this rather than asserting it: on its five-by-five example the two rounds of reductions take off 37 in total, and all 120 complete assignments are cheaper in the reduced matrix by the same 37, one number and not a range.
“Draw lines through the zeros until you cannot do better” has no stopping rule and no tie-break, and on the lab's own default example it does not even give an answer: cover whichever line holds the most uncovered zeros and, at the second cover step, breaking ties towards rows draws four lines while breaking them towards columns draws three — same matrix, same rule. The lab computes a maximum matching on the zero cells instead and reads the cover off it, which is König's theorem and is why the number is well defined.
Row constant uᵢ, column constant vⱼ; the reduced entries stay non-negative throughout, which says uᵢ + vⱼ ≤ cᵢⱼ everywhere — dual feasibility. So Σuᵢ + Σvⱼ is a lower bound on every assignment, and it never falls. The method stops when it equals the cost of an assignment it has actually found, and at that moment both are optimal.
The material
Why the reductions are legitimate, why the cover has to be computed, and what the running total is.
Given an n × n cost matrix C, the assignment problem is to choose a permutation σ of {1, …, n} minimising Σᵢ cᵢ,σ(i) — one job per worker, one worker per job.
Written as a linear programme it is the transportation problem with every supply and every demand equal to one, so the previous lessons apply unchanged; and since its matrix is a node-arc incidence matrix, its corners are whole and are exactly the permutations.
That last sentence is worth pausing on, because it is what makes the problem tractable. There are n! permutations — 24 on a four-by-four table, 120 on a five-by-five — and yet the linear relaxation does not need a single integrality constraint. The relaxation's corners are the permutations, by the determinant argument of “Total Unimodularity and Integer Corners”.
Subtracting a constant from every entry of a row, or from every entry of a column, changes the cost of every complete assignment by that same constant. The set of optimal assignments is therefore unchanged, and the optimal value of the original problem is the optimal value of the reduced one plus the total subtracted.
The proof is the counting observation: a complete assignment meets each row once and each column once, so it picks up each constant exactly once. The lab verifies it by brute force on its five-by-five example rather than by restating it.
The reduced matrix above has seven zeros. The question is whether they carry a complete assignment — four zeros, no two in the same row or column — and the answer is that they do not: the largest matching on the zero cells has three pairs, so by König's theorem three lines suffice to cover every zero, and three is fewer than four. The lab prints both numbers side by side at every cover step, because they are always equal and that equality is the whole justification for counting lines at all.
After one adjustment the matrix is 0 4 1 2 / 0 3 0 4 / 2 0 1 0 / 1 3 0 4, with six zeros. The minimum cover is 3 and it is attained exactly one way: the third row together with the first and third columns.
Apply the usual eye test — cover whichever row or column holds the most still-uncovered zeros, and repeat — and the answer depends on how ties are broken: towards rows it draws four lines, towards columns three. Four is n, so the reader who broke ties towards rows now goes looking for a complete assignment among six zeros that cannot supply one. The recipe is not a function of the matrix, and that is why this lab does not implement it.
When the cover is short of n, adjust: let θ be the smallest uncovered entry, subtract it from every uncovered entry and add it to every entry covered twice. Entries covered once are untouched. Nothing becomes negative, no existing zero is destroyed, and at least one new zero appears. This is again a row-and-column operation in disguise, so the previous theorem still applies and the answer still cannot move.
Run the method on the four fitters. The constants taken off total 32, then 46, then 47, then 49; the adjustments are θ = 1 and then θ = 2, and the third cover has four lines. The final zeros carry the assignment A to the fourth job, B to the first, C to the second and D to the third, costing 15 + 10 + 16 + 8 = 49.
The constants recovered as a dual solution are u = (10, 10, 9, 11) and v = (0, 7, −3, 5), which add to 49 as well, and satisfy uᵢ + vⱼ ≤ cᵢⱼ in all sixteen cells. A feasible dual point and a feasible primal point with the same value: that is strong duality, on this instance, and it is the certificate the method hands you rather than a claim that it terminated.
The dual total never falls — 32, 46, 46, 47, 47, 49, 49 step by step, standing still at the cover steps and rising at the adjustments — and it is dual feasible at every one of them, not only at the end. So the method can be stopped early and what you have is still a genuine lower bound, which is more than most hand methods offer.
Take the cheapest cell, strike out its row and column, repeat. On the fitters it picks (B, J3) at 7, then (A, J1) at 10, (C, J4) at 14 and (D, J2) at 19, for 50 — one more than the optimum. On the four crews and four sites it opens at 35 and ends at 315 against an optimum of 275, forty too much. On the five drivers it lands on 38, which is exactly right.
That third case is the one to remember. Greed produced the optimum and produced no reason to believe it, and a right answer with no certificate is not a method. The Hungarian run on the same table ends with a dual total of 38 beside a primal cost of 38, and that pair is the difference.
Interactive
the minimum cover is a maximum matching, and the reductions are the dual
Method
Two reductions, then a loop of cover-and-adjust. The only step with any judgement in it is the one you should not be exercising judgement on.
Order matters only for the arithmetic, not for the outcome. Keep a running total of everything subtracted; that total is the bound, and forgetting it is how readers end up with the reduced answer and no way back to the real one.
Pair rows to columns using zero cells only, no two pairs sharing a row or a column, as many pairs as you can. On a small table this is a minute's work by hand, and it is the number the cover is about to equal.
The minimum cover has exactly as many lines as the matching has pairs. If that is n, the matching is a complete assignment and you have finished. Do not count lines by eye instead: the eye test has no tie-break and gives different answers on the same matrix.
Subtract θ from every uncovered entry, add it to every entry covered by two lines, leave the singly covered alone. Add θ × (number of uncovered rows) worth of bookkeeping to your running total if you are tracking it by hand — or simply re-derive the total from the current constants, which the lab does.
The deliverable is a pair of numbers, not one: an assignment costing z and row and column constants adding to z. Quote both. That pair is a proof, and it is checkable in the time it takes to add up n numbers twice.
Every matrix below is what the lab holds at that step, and every total is the row and column constants recovered from it and added up.
The two 49s are the point of the whole lesson. One is the cost of something you can do; the other is a bound on everything you could have done; and because they are equal, neither needs any further argument. Quote both or you have quoted half a result.
For a rehearsal, run the five drivers and five routes. Greed happens to land on 38, which is optimal, and the method reaches 38 as well — but watch where the constants come from: 35 off the rows, 2 off the columns, the cheapest assignment in the reduced matrix costing 1, and 1 + 37 = 38. The reduced matrix still has work left in it, which is why 37 alone was not the answer.
The harder rehearsal: on the four crews and four sites, stop the method at the second cover step and write down what you have. A dual total of 270 and no assignment. That is still a real statement — no assignment on that table costs less than 270 — and the optimum turns out to be 275. Being able to stop early with something true is what dual feasibility at every step buys you.
You should be able to justify the reductions by the one-cell-per-row argument, find a maximum matching on the zero cells and read the cover off it, adjust by the smallest uncovered entry, keep the running total, and state the pair of equal numbers that ends the method.
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.