Allocation problems and the Hungarian algorithm: VCE General Mathematics Unit 4 Networks and decision mathematics
“Use a bipartite graph and its tabular or matrix form to represent a matching problem, and determine the optimum assignment of people or machines to tasks by inspection or by the Hungarian algorithm for larger problems”
Represent the problem as a bipartite graph (people on one side, tasks on the other) or a square cost table. For small tables, list the allocations. Otherwise: subtract each row's minimum from its row, then each column's minimum from its column; cover all zeros with the fewest lines. If the number of lines equals the table size, choose one zero in each row and column; if not, subtract the smallest uncovered number from all uncovered numbers, add it where lines cross, and cover again. The optimal total comes from the original table.
What this dot point is asking
The Study Design's Matching problems topic has two parts: "use of a bipartite graph and its tabular or matrix form to represent a matching problem" and "determination of the optimum assignment(s) of people or machines to tasks by inspection or by use of the Hungarian algorithm for larger scale problems". So you need to:
- read and draw a bipartite graph for an allocation problem, and its cost table;
- solve small problems by inspection;
- carry out the Hungarian algorithm step by step, including the adjustment step;
- read off the allocation and its total from the original table, and recognise when there is more than one optimum.
Allocation questions are usually worth one mark each on Examination 1 (2023 Questions 34 and 36, and ; 2025 Question 39, ), where a single slip in a step picks the wrong option. Examination 2 can ask for the steps themselves.
The answer
Bipartite graphs and cost tables
A bipartite graph has two sets of vertices, with every edge joining a vertex in one set to a vertex in the other and none within a set. In an allocation problem one set is the people (or machines) and the other is the tasks. An edge means "this person can do this task", and a weight on it is the cost, time or distance.
The same information is kept in a cost table (or matrix): one row per person, one column per task. An allocation (a matching) gives each person exactly one task and each task exactly one person, so the table must be square. An optimum allocation has the smallest total cost.
Allocation by inspection
With 3 people there are only possible allocations, so listing them is quick and safe. With 4 people there are , which is when the Hungarian algorithm pays off. A useful inspection check: a person with a much smaller cost for one task than any alternative usually gets that task, but always compare complete allocations before concluding.
The Hungarian algorithm
- Row reduction. Subtract the smallest number in each row from every number in that row.
- Column reduction. In the new table, subtract the smallest number in each column from every number in that column.
- Cover the zeros with the fewest possible horizontal and vertical lines.
- Test. If the number of lines equals the number of rows, an optimal allocation can be made from the zeros: go to step 6.
- Adjust. Find the smallest uncovered number. Subtract it from every uncovered number and add it to every number where two lines cross. Numbers covered by one line do not change. Return to step 3.
- Allocate. Choose one zero in each row and each column. Start with any row or column that has a single zero, since that choice is forced, and cross out its row and column. Draw a bipartite graph of the zeros if it helps.
- Total. Add the numbers from the original table in the chosen positions.
The order of steps 1 and 2 matters for the intermediate tables: 2025 Examination 1 Question 39 had options built from doing only the column step and from doing the steps in reverse order.
Why the method works: every allocation uses exactly one number from each row and each column. Subtracting a constant from a whole row or column lowers the total of every allocation by the same amount, so the best allocation stays the best. When a full set of independent zeros appears, that allocation costs nothing in the reduced table, so it must be optimal in the original.
Reading off the allocation
In the final table, look for a row or column with only one zero and assign it first. Then remove that row and column and repeat. The thick edges below come from the worked example with an adjustment step: Bella has only one zero (Task 2), which forces Dana to Task 4, then Chen to Task 3 and Amir to Task 1.
If there is a choice at some stage (two independent sets of zeros), there is more than one optimal allocation, each with the same total. Questions that ask for "the optimum assignment(s)" may expect all of them.
Maximising and unbalanced problems
- Maximising (profit, points, satisfaction): subtract every entry from the largest entry in the table, then run the algorithm as usual. The allocation that minimises the converted table maximises the original, and the maximum is read from the original table.
- Unbalanced (more tasks than people): add a dummy person (a row of zeros) so the table is square; whoever is matched to a dummy is not used, or the task matched to a dummy is not done.
Finishing Martha's allocation (2025 Examination 1 Question 39)
After row and column reduction the table is:
| Site 1 | Site 2 | Site 3 | Site 4 | |
|---|---|---|---|---|
| 1300 | 0 | 0 | 0 | |
| 0 | 0 | 1850 | 750 | |
| 4100 | 0 | 3750 | 3500 | |
| 5938 | 0 | 1000 | 300 |
Step 1: cover the zeros. Row , column 1 and column 2 cover every zero: 3 lines, fewer than 4. (Both and have their only zero in Site 2, so no allocation is possible yet.)
Step 2: adjust. The uncovered numbers are 1850, 750, 3750, 3500, 1000 and 300; the smallest is 300. Subtract 300 from each of them, add 300 where row crosses columns 1 and 2, and leave the rest.
| Site 1 | Site 2 | Site 3 | Site 4 | |
|---|---|---|---|---|
| 1600 | 300 | 0 | 0 | |
| 0 | 0 | 1550 | 450 | |
| 4100 | 0 | 3450 | 3200 | |
| 5938 | 0 | 700 | 0 |
- Step 3: cover again
- Four lines are now needed, so allocate.
- Step 4: allocate
- has one zero: Site 2. Then must take Site 4, Site 1, and Site 3.
- Answer
- From the original costs: Site 3 ($22 750), Site 1 ($14 500), Site 2 ($12 400), Site 4 ($18 000), a minimum total of $67 650. Checking all 24 allocations confirms this is the only optimum.
A four-by-four problem with an adjustment
Times (minutes) for four workers to do four tasks:
| Task 1 | Task 2 | Task 3 | Task 4 | |
|---|---|---|---|---|
| Amir | 5 | 10 | 9 | 3 |
| Bella | 13 | 4 | 15 | 11 |
| Chen | 12 | 15 | 8 | 8 |
| Dana | 14 | 8 | 12 | 10 |
Step 1: row reduction (minimums 3, 4, 8, 8). Amir 2, 7, 6, 0; Bella 9, 0, 11, 7; Chen 4, 7, 0, 0; Dana 6, 0, 4, 2.
Step 2: column reduction (minimums 2, 0, 0, 0). Amir 0, 7, 6, 0; Bella 7, 0, 11, 7; Chen 2, 7, 0, 0; Dana 4, 0, 4, 2.
- Step 3: cover
- Rows Amir and Chen and column 2 cover all zeros: 3 lines, fewer than 4.
- Step 4: adjust
- Uncovered numbers: Bella 7, 11, 7 and Dana 4, 4, 2. The smallest is 2. Subtract 2 from each; add 2 where the lines cross (Amir Task 2 and Chen Task 2 become 9). New table: Amir 0, 9, 6, 0; Bella 5, 0, 9, 5; Chen 2, 9, 0, 0; Dana 2, 0, 2, 0.
- Step 5: cover again
- Four lines are needed.
- Step 6: allocate
- Bella's only zero is Task 2. Dana's zeros are Tasks 2 and 4; Task 2 is taken, so Task 4. Chen's zeros are Tasks 3 and 4; Task 4 is taken, so Task 3. Amir takes Task 1.
- Answer
- Amir Task 1 (5), Bella Task 2 (4), Chen Task 3 (8), Dana Task 4 (10): a minimum total time of 27 minutes.
Marker's note: a common slip is to subtract 2 from the singly covered numbers too. Only uncovered numbers go down, and only crossing points go up.
- Doing the steps in the wrong order, or only one of them
- Rows first, then columns on the new table.
- Covering the zeros with more lines than needed
- Use the fewest lines; otherwise you may think an allocation exists when it does not.
- Allocating too early
- If the fewest lines are fewer than the table size, you cannot choose one zero per row and column yet. Adjust first.
- Adjusting the wrong numbers
- Subtract from uncovered numbers only; add at crossing points only.
- Adding up the final table
- The total comes from the original costs.
- Forgetting to convert a maximising problem
- The algorithm always minimises.
Missing a second optimal allocation when a question asks for all of them.
In multiple-choice questions, check options against the first row and first column before working the whole table: the row step fixes a zero in every row, and the column step then fixes a zero in every column. In written answers, show each table with its row or column minimums written beside it, state the number of lines, and finish with a sentence naming each person and task and the total from the original table.
An allocation problem is about matching people to jobs, one each, as cheaply as possible. For three people you can just try all six ways. For more, the Hungarian method makes the table simpler without changing which matching is best: take the smallest number off each row, then off each column, until there are enough zeros to give everyone a "free" job. If there are not enough, shuffle the numbers with the adjustment step and try again. The best matching is where the zeros are, and its true cost comes from the original table.
Exam-style questions
Questions in the style of VCAA exam questions on this dot point, each with a worked answer. They are written by ExamExplained unless tagged "Past paper"; the year shows the paper a question is modelled on.
2023 VCAA-style1 markA bipartite graph is typically used to display which one of the following? A. the allocation of tasks on a construction site B. the path used to visit five different construction sites C. the total distance travelled between two construction sites D. the critical path of activities to be completed in a construction project E. the minimum length of cable required to connect six construction sitesShow worked answer →
A bipartite graph has two separate groups of vertices (for example workers and tasks), with edges only between the groups. That is exactly the structure of an allocation problem: option A ( correct).
The other options belong to other topics: B is a Hamiltonian path, C a shortest path, D critical path analysis, and E a minimum spanning tree.
Source: VCAA 2023 General Mathematics Examination 1, Question 34, and the 2023 examination report.
2023 VCAA-style1 markFour employees are each assigned a different duty. The time taken, in minutes, is: Anthea (Duty 1 to 4) = 8, 7, 7, 8; Bob = 10, 8, 10, 9; Cho = 8, 9, 7, 10; Dario = 7, 7, 8, 9. The duties are allocated to minimise the total time taken. The minimum total time, in minutes, is A. 29 B. 30 C. 31 D. 32 E. 33Show worked answer →
Row reduction (row minimums 7, 8, 7, 7): Anthea 1, 0, 0, 1; Bob 2, 0, 2, 1; Cho 1, 2, 0, 3; Dario 0, 0, 1, 2.
Column reduction (column minimums 0, 0, 0, 1): Anthea 1, 0, 0, 0; Bob 2, 0, 2, 0; Cho 1, 2, 0, 2; Dario 0, 0, 1, 1.
The zeros need four lines (Dario can only use Duty 1 or 2, Cho only Duty 3), so an allocation of zeros exists: Dario to Duty 1, Cho to Duty 3, then Anthea and Bob share Duties 2 and 4 either way.
Minimum time from the original table: Anthea Duty 2 (7), Bob Duty 4 (9), Cho Duty 3 (7), Dario Duty 1 (7) minutes. The swap Anthea Duty 4 (8), Bob Duty 2 (8) also totals 30. Option B ( correct).
Source: VCAA 2023 General Mathematics Examination 1, Question 36, and the 2023 examination report.
2025 VCAA-style1 markThe cost, in dollars, for four contractors P, Q, R, S to complete work at four sites is: P (Site 1 to 4) = 15 400, 9600, 22 750, 18 300; Q = 14 500, 10 000, 25 000, 19 450; R = 21 000, 12 400, 29 300, 24 600; S = 19 438, 9000, 23 150, 18 000. Using the Hungarian algorithm, Martha first subtracts the minimum entry in each row from each element in that row, then, using this new table, subtracts the minimum entry in each column from each element in that column. Which one of the following tables correctly displays the results after these two steps are completed?Show worked answer →
Row reduction. Row minimums are P 9600, Q 10 000, R 12 400, S 9000, giving P: 5800, 0, 13 150, 8700; Q: 4500, 0, 15 000, 9450; R: 8600, 0, 16 900, 12 200; S: 10 438, 0, 14 150, 9000. (This is option A, which stops after one step.)
Column reduction on that table. Column minimums are 4500, 0, 13 150 and 8700, giving P: 1300, 0, 0, 0; Q: 0, 0, 1850, 750; R: 4100, 0, 3750, 3500; S: 5938, 0, 1000, 300.
This matches option B ( correct). The report notes that option C comes from doing only the column step, and option D from doing the column step first and then the row step.
Source: VCAA 2025 General Mathematics Examination 1, Question 39, and the 2025 examination report. (The worked examples below finish this allocation.)
Practice questions
Original practice questions graded from foundation to exam level, each with a full worked solution. Try them before revealing the solution.
foundation2 marksThree cleaners, X, Y and Z, are to be allocated one room each. The times (minutes) are X: 12, 9, 15; Y: 10, 14, 11; Z: 13, 8, 12 for rooms 1, 2 and 3. (a) By listing all possible allocations, find the minimum total time. (b) How many optimal allocations are there?
Show worked solution →
(a) There are allocations (room for X, then Y, then Z):
- 1, 2, 3:
- 1, 3, 2:
- 2, 1, 3:
- 2, 3, 1:
- 3, 1, 2:
- 3, 2, 1:
Minimum total time 31 minutes. (1 mark)
(b) Two: X room 1, Y room 3, Z room 2; or X room 2, Y room 1, Z room 3. (1 mark)
core3 marksFour workers W, X, Y and Z are allocated one job each. Times (hours) for jobs 1 to 4: W 9, 11, 14, 11; X 6, 15, 13, 13; Y 12, 13, 6, 8; Z 11, 9, 10, 12. Use the Hungarian algorithm to find the allocation with the minimum total time.
Show worked solution →
Row reduction (minimums 9, 6, 6, 9): W 0, 2, 5, 2; X 0, 9, 7, 7; Y 6, 7, 0, 2; Z 2, 0, 1, 3.
Column reduction (minimums 0, 0, 0, 2): W 0, 2, 5, 0; X 0, 9, 7, 5; Y 6, 7, 0, 0; Z 2, 0, 1, 1. (1 mark)
Cover the zeros. The zeros at X job 1, Z job 2, Y job 3 and W job 4 are all in different rows and columns, so no 3 lines can cover them: 4 lines are needed and an allocation exists. (1 mark)
Allocate. X has only one zero: job 1. Z has only one zero: job 2. Then W must take job 4 (its job 1 is gone) and Y job 3. Total from the original table: hours. (1 mark)
core2 marksAfter row and column reduction, a table can have all its zeros covered by 3 lines. The smallest uncovered number is 5. Describe exactly what happens to the numbers in the table in the next step.
Show worked solution →
Subtract 5 from every uncovered number, add 5 to every number where two lines cross, and leave every number covered by exactly one line unchanged. (1 mark)
Then cover the zeros again with the fewest lines; if 4 lines are now needed, an allocation can be made, otherwise repeat the adjustment. (1 mark)
exam3 marksA manager expects the following weekly profits (thousands of dollars) from assigning sales representatives A, B and C to regions 1, 2 and 3. A: 40, 55, 35. B: 50, 45, 60. C: 45, 50, 55. Each representative gets one region. (a) Convert the table so that the Hungarian algorithm can be used. (b) Find an allocation that maximises profit and the maximum profit. (c) Is the optimal allocation unique?
Show worked solution →
(a) The algorithm minimises, so subtract every entry from the largest entry, 60: A 20, 5, 25; B 10, 15, 0; C 15, 10, 5. (1 mark)
(b) Row reduction (minimums 5, 0, 5): A 15, 0, 20; B 10, 15, 0; C 10, 5, 0. Column reduction (minimums 10, 0, 0): A 5, 0, 20; B 0, 15, 0; C 0, 5, 0. Three lines are needed, so allocate: A must take region 2; then B and C share regions 1 and 3. A region 2 (55), B region 3 (60), C region 1 (45): profit , that is $160 000. (1 mark)
(c) No. A region 2 (55), B region 1 (50), C region 3 (55) also gives . Both use zeros of the final table. (1 mark)
Practise this
Sources & how we know this
- VCE General Mathematics Examination 1 (2023) and examination report — VCAA (2023)
- VCE General Mathematics Examination 1 (2025) and examination report — VCAA (2025)
- VCE Mathematics Study Design: General Mathematics (from 2023) — VCAA
- VCE General Mathematics: examination specifications, past examinations and reports — VCAA