UPI Study › Courses › Quantitative Analysis › Free lessons › Lesson 13.2 Free with a free account
Step by Step Through the Hungarian Algorithm
Quantitative Analysis · Chapter 13: Assignment ModelsSection 13.2 · lesson 55 of 5512 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Quantitative Analysis.
Lesson complete
Earn the 3 college credits for Quantitative Analysis
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
In this lesson
Solving assignment problems optimally with nothing but row and column arithmetic on the cost matrix.
- Execute all 6 steps of the algorithm on a minimisation problem
- Convert a maximisation problem using opportunity costs
- Handle dummy rows, prohibited cells and multiple optima
- Check the Hungarian answer against the LP formulation
Transcript
Everything said in the video, section by section (1,773 words). Read along, or search it.
Assignment Problems · Chapter 13.2
Step by Step Through the Hungarian Algorithm
Welcome to Section thirteen point two of Quantitative Analysis. In the previous section you learned to formulate an assignment problem. You wrote it as a binary linear program, and that formulation was correct. Correct, but slower to solve than it needs to be. An assignment problem has so much structure that a specialised method beats the general one. That method is the Hungarian algorithm, and it is pure arithmetic. No pivots, no tableaux, no solver required. Only row subtractions, column subtractions, and lines drawn through zeros. By the end you will run all six steps by hand, on real data.
Why This Method
A Special Case That Earns Its Own Algorithm
Why does this problem deserve an algorithm all of its own? An assignment problem pairs n workers with n tasks at minimum total cost. It is a special case of the transportation problem from Chapter twelve. The special part is that every supply and every demand equals one. The simplex method would solve it, and so would the transportation algorithm. But both are inefficient here, because most of their machinery goes to waste. Harold Kuhn published the efficient method in nineteen fifty-five, and it runs in cubic time. He built on earlier work by two Hungarian mathematicians, Denes Konig and Jeno Egervary. Now subtract a constant from any one row of the cost matrix. Every assignment uses exactly one cell in that row, so every total drops equally. The ranking of assignments never changes. Only the numbers do.
The Six Steps
The Algorithm, for a Minimisation Problem
Six steps. Learn them in order, because the order carries the logic. Step one is row reduction. Subtract each row's smallest entry from that whole row. Every row now contains a zero, sitting at that worker's cheapest task. Step two is column reduction, the same move turned sideways. Subtract each column's smallest entry, and now every column holds a zero too. Step three covers the zeros, and this is where students slow down. Draw the fewest horizontal and vertical lines that cover every zero. Call that number L. Step four checks optimality. If L equals n, an optimal set of zeros already exists. If L is smaller than n, you are not done, so go to step five. Step five adjusts. Let k be the smallest entry that no line touches. Subtract k from every uncovered entry, and add k wherever two lines cross. Entries under exactly one line stay as they are. Then return to step three. Step six assigns any row or column holding exactly one uncovered zero, then crosses it out. One warning that costs marks. Take the total from the original matrix, never the reduced one.
The Inner Loop
Cover, Test, Adjust - and Why It Works
Notice the shape of the algorithm. Steps one and two run once each. Steps three, four and five form a loop that can run several times. When step five fires, it redistributes cost inside the matrix to manufacture new zeros. Subtracting k from the uncovered region creates at least one fresh zero there. Adding k back at the crossings keeps the row and column arithmetic honest. So the optimal assignment survives every pass, even though the numbers change. Now the deeper question. Why count lines instead of counting zeros? Because zeros can pile up in one row and still be useless to you. Konig's theorem answers that precisely. The minimum number of covering lines equals the largest set of independent zeros, no two sharing a row or a column. So L equals n is exactly the condition for a complete zero assignment to exist.
Maximisation
Turn Profit Into Opportunity Cost
Every step you have seen minimises. Many real problems want to maximise. Fit scores, profits, satisfaction ratings, expected revenue. Higher is better. Run the algorithm as it stands, and the zeros would chase the worst cells. Find the single largest entry in the profit matrix, and subtract every entry from it. That gives the opportunity-cost matrix, and now smaller is better. Each cell answers a sharp question. How much value do we give up by choosing this pairing? Minimising total opportunity cost is the very same problem as maximising total profit. Then one last move, and this is where people lose marks. Do not add up the numbers in the cost matrix you built. Go back to the original score matrix, and sum the cells the algorithm chose.
Special Cases
Unbalanced, Prohibited, and Tied
Three situations break the plain recipe, and all three come up constantly. The first is an unbalanced problem, where workers and tasks differ in number. The algorithm needs a square matrix, so add dummy rows or columns with zero cost. Afterwards, an assignment to a dummy means that worker or that task is not used. The second case is a prohibited pairing, maybe a missing certification or a contract ban. Do not delete the cell. Load it with a very large cost, written as capital M. Since the algorithm minimises, it will never pick that cell unless the problem is infeasible. The third case is multiple optimal solutions, and it is the most interesting. Several different zero patterns can each cover all rows and columns, at identical total cost. There the mathematics is genuinely indifferent, and the manager earns their salary instead. Choose on worker preferences, workload balance, robustness to absences, or strategic relationships.
Worked Example 1
4 Drivers, 4 Routes, Minimum Total Time
Time for a full worked example, start to finish. A shipping company has four drivers and four delivery routes. Each number is the time in minutes that driver needs on that route. Every driver takes one route, every route takes one driver, and total time is minimised. Driver one needs twenty-two, eighteen, thirty, and twenty-four minutes. Driver two needs eighteen, twenty-four, twenty-six, and twenty. Driver three needs twenty-five, twenty-seven, twenty-one, and twenty-three. Driver four needs twenty, twenty-two, twenty-eight, and nineteen. Step one asks for the smallest entry in each row. Those minima are eighteen, eighteen, twenty-one and nineteen. Subtract each from its own row, and a zero appears at each driver's fastest route.
Worked Example 1
Reduce, Cover, Then Read the Answer
Here is the matrix after row reduction, and the pattern is already striking. Driver one's row reads four, zero, twelve, six. Driver two's reads zero, six, eight, two. Driver three's reads four, six, zero, two, and driver four's reads one, three, nine, zero. Step two asks for the column minima, and every column already contains a zero. So every column minimum is zero, and column reduction changes nothing. Never assume that. Step three. Those four zeros sit in four different rows and four different columns. No single line catches two of them, so covering them takes four lines. L equals four and n equals four, so step four passes and step five never fires. Driver one takes route B, driver two takes route A, driver three takes route C. Driver four takes route D. Now read those cells from the original matrix. Eighteen plus eighteen plus twenty-one plus nineteen gives seventy-six minutes. Twenty-four pairings were possible, that is four factorial, and this is the unique best.
Worked Example 2
Consultants and Projects, Where Higher Is Better
Second worked example, and this one runs the other way. Section thirteen point one introduced a consultant-project fit problem. Four consultants, four projects, and a score for how well each pair fits. Higher is better here, so these numbers are the opposite of costs. Consultant one scores nine, eleven, fourteen, ten across projects A to D. Consultant two scores eight, thirteen, twelve, fourteen. Consultant three scores twelve, ten, eleven, thirteen, and consultant four scores ten, twelve, thirteen, eleven. The largest entry anywhere in the matrix is fourteen. So subtract every entry from fourteen to build the opportunity-cost matrix. A pairing already scoring fourteen costs nothing. A pairing scoring nine costs five. Minimising that total opportunity cost is exactly equivalent to maximising total fit.
Worked Example 2
Six Steps on the Opportunity-Cost Matrix
Here is the opportunity-cost matrix, and now the ordinary six steps apply. Consultant one's row reads five, three, zero, four. Consultant two's reads six, one, two, zero. Consultant three's reads two, four, three, one, and consultant four's reads four, two, one, three. Step one subtracts the row minima, which are zero, zero, one and one. The first two rows already hold a zero, so they do not move. Step two subtracts the column minima, which are one, one, zero and zero. The reduced matrix now carries seven zeros, spread across every row and column. Four lines cover all seven, and four is also the size of the matrix. So L equals n on the first pass, and we go straight to step six. Consultant one takes project C, two takes D, three takes A, and four takes B. Read those cells from the original score matrix, never from the reduced one. Fourteen plus fourteen plus twelve plus twelve gives a total fit of fifty-two.
Verification
The Same Optimum, From the LP Formulation
A method you cannot check is a method you cannot trust. Section thirteen point one wrote this same problem as a binary linear program. Maximise the sum, over all consultants and projects, of fit score times decision variable. Subject to one constraint per consultant, saying each takes exactly one project. And one constraint per project, saying each is staffed by exactly one consultant. Every decision variable is binary. It is either zero or one, never a fraction. Hand that to Excel Solver, or to any package, and it returns total fit fifty-two. A third check hides in the arithmetic, and it is worth knowing. The reductions removed four units of cost in total, across the rows and columns. Four consultants at a top score of fourteen is fifty-six, less four, giving fifty-two. The Hungarian algorithm got there in cubic time, with no linear programming at all.
Extension
A Fifth Consultant, and a Dummy Project
One last extension, because real teams do not arrive in tidy square matrices. A fifth consultant joins, scoring eleven, nine, fourteen and twelve. Now there are five consultants and only four projects. Someone will sit out. The algorithm needs a square matrix, so add a dummy project scoring zero for everyone. Convert to opportunity costs as usual, subtracting from the maximum, which is still fourteen. Zero profit becomes fourteen units of opportunity cost, right down the dummy column. This is also the first problem here where step five actually fires. The first cover of the reduced matrix needs only four lines, and four is less than five. So take the smallest uncovered entry, which is one, adjust, and cover again with five lines. Consultants one to four take projects C, D, A and B, exactly as before. Consultant five goes to the dummy, which means consultant five sits out. Total fit on real projects is fifty-two, unchanged by the new arrival. That is no judgement on consultant five's ability, and a tie proves the point. Consultant one and consultant five both score fourteen on project C, so either could sit out. If management wants everybody placed, load the dummy column with a strategic penalty instead of zero.
About Quantitative Analysis at UPI Study
Quantitative Analysis (Math 250) is a self-paced online course of 55 video lessons in 13 chapters, from decision analysis and simulation to inventory and queuing models, project scheduling, linear programming and transportation models. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus All Math courses Every course with PRO →
Compare: Statistics vs Quantitative Analysis
Why take it here
Why students take Quantitative Analysis with UPI Study
Where the credit goes
Universities that work with NCCRS
Quantitative Analysis carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Step by Step Through the Hungarian Algorithm
What are the steps of the Hungarian algorithm?
Why does the Hungarian algorithm count covering lines?
How do you use the Hungarian algorithm for a maximization problem?
How does the Hungarian algorithm handle unequal numbers of workers and tasks?
About the Quantitative Analysis course
How many college credits is Quantitative Analysis?
How much does Quantitative Analysis cost and what is included?
Which universities accept UPI Study credits?
How long does Quantitative Analysis take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Quantitative Analysis.
55 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →