Contents · 0% complete

Learning objectives
Core idea
Key formulae
Worked examples
Explore the graph
Common mistakes
Exam tip
Guided practice
Practice questions
Challenge
Summary
Quick quiz
Same topic, different board
Past paper questions

Learn9FM0Option · Decision Mathematics 2Allocation problemsThe Hungarian algorithm

Allocation problems · Subtopic 1 of 1

Allocation Problems

Assign $n$ workers to $n$ tasks at least total cost. The Hungarian algorithm reduces rows then columns so each has a zero; cover all zeros with the fewest lines; if fewer than $n$ lines, subtract the smallest uncovered value from uncovered cells and add it at intersections. With $n$ lines an optimal allocation of zeros exists.

Edexcel 9FM0 Option≈ 45 minRevision 1 · updated 2026-10-27

Practise this topicTimed test Ask Salam Tutor

Section 1 of 14

Learning objectives

Apply row and column reduction.
Cover zeros and adjust the matrix.
Read off an optimal allocation.
Handle dummies, maximisation and forbidden pairings.

Pause and think

Three workers, three jobs: why not just give each worker their cheapest job?

Section 2 of 14

Core idea

Start hereWho does what?

Three workers, three jobs, and each worker charges differently for each job. Everyone may want the same cheap job. The Hungarian algorithm untangles this, finding the cheapest one-to-one allocation without checking every possibility.

The big idea

Subtracting a constant from a whole row or column doesn't change which allocation is best. Reduce until zeros appear, then adjust until $n$ independent zeros exist: they mark the optimal allocation.

1. The algorithm

Why reduction is allowed

$\text{every allocation uses one cell per row}$
Each worker gets exactly one job.
$\text{subtract }c\text{ from a row}\Rightarrow\text{every total falls by }c$
All allocations change equally.
$\text{ranking of allocations unchanged}$
So the optimum is the same.

Worked exampleA 3×3 problem

$P$ : $4,2,8$ ; $Q$ : $4,3,7$ ; $R$ : $3,1,6$ . Minimise total cost.

Goal: Allocation.
Strategy: Reduce, cover, adjust.

$P:2,0,6;\ Q:1,0,4;\ R:2,0,5$
Row minima $2,3,1$ .
$P:1,0,2;\ Q:0,0,0;\ R:1,0,1$
Column minima $1,0,4$ .
$2\text{ lines}<3;\ m=1$
Row $Q$ and column 2 cover all zeros.
$P:0,0,1;\ Q:0,1,0;\ R:0,0,0$
$-1$ uncovered, $+1$ at the intersection.

Answere.g.

P\to2

Q\to3

R\to1

2+7+3=12

✓ CheckAll six allocations:

13,12,12,12,13,14

; minimum

12

✓.

Hungarian algorithm

Drawing diagram…

Loop until enough lines are needed.

TrickMaximising Subtract each entry from the largest entry, then minimise.

Common misconceptionReport true cost Add up the original costs, not the reduced ones.

Pause and think

Why does adjusting never make an entry negative?

Summary

Reduce rows, columns.
Cover zeros; adjust.
Dummies, maximisation, restrictions.

Allocation: One-to-one matching of workers to tasks.
Dummy: Extra row or column of zeros to square the matrix.

HistoryKuhn and the Hungarians. Harold Kuhn published the method in 1955, naming it after Hungarian mathematicians Kőnig and Egerváry, whose 1930s work it built on.

Fun factFactorial explosion. 10 workers and 10 jobs have

3\,628\,800

possible allocations. The Hungarian method needs only about

10^3

steps.

Section 3 of 14

Key formulae

Reduction

\text{subtract row minima, then column minima}

Optimal test

\text{fewest lines covering all zeros}=n

Adjustment

-m\ \text{uncovered},\ +m\ \text{at intersections}

TrickMaximising. To maximise (e.g. scores), subtract every entry from the largest entry first, then minimise as usual.

Section 4 of 14

Worked examples

Example 1 · Hungarian0 / 3 steps

Costs:

P

4,2,8

;

Q

4,3,7

;

R

3,1,6

for jobs

1,2,3

. Find the minimum cost.

Section 5 of 14

Explore the graph

Brute force vs Hungarian

Loading the interactive graph…

Try this

$x^3$ is roughly the Hungarian method's work for an $x\times x$ matrix.
$2^x$ is already explosive, and checking all $x!$ allocations grows faster still.

Polynomial beats exponential.

In the real worldRide-hailing. Taxi apps assign nearby drivers to passengers in batches using assignment algorithms to cut total waiting time.

Section 6 of 14

Common mistakes

IncorrectColumn-reduce first

CorrectRows first (unless told otherwise)

Follow the standard order; answers can differ in steps.

IncorrectUsing the reduced values as the cost

CorrectUse the original costs

Reduced numbers aren't costs.

IncorrectNon-square matrix

CorrectAdd a dummy row or column of zeros

The algorithm needs

n\times n

Three workers want job 2

Hungarian algorithm: calm down, everyone.

Section 7 of 14

Exam tip

Exam tipForbidden pairings. Replace a forbidden cost with a very large number so that cell is never chosen.

Section 8 of 14

Guided practice

SA-DM-AS-G011 markL1 FoundationNon-calculatorHungarian

Row

P

of a cost matrix is

4,2,8

. After row reduction, what is the entry in column 3?

Salam Academy Original Practice · Proposed mark scheme

Section 9 of 14

Practice questions

SA-DM-AS-0013 marksL3 ExamNon-calculatorHungarian

Costs:

P

4,2,8

;

Q

4,3,7

;

R

3,1,6

(jobs 1–3). Find the minimum total cost.

Salam Academy Original Practice · Proposed mark scheme

SA-DM-AS-0021 markL1 FoundationNon-calculatorVariants

Three workers are to be assigned to four jobs. How many dummy workers (rows) are needed?

Salam Academy Original Practice · Proposed mark scheme

SA-DM-AS-0031 markL2 StandardNon-calculatorVariants

To maximise, entries are subtracted from the largest entry,

20

. What does an entry of

14

become?

Salam Academy Original Practice · Proposed mark scheme

More questions on every skill in this subtopic are in the question bank under Practise.

Section 10 of 14

Challenge

SA-DM-AS-0042 marksL3 ExamNon-calculatorHungarian

After reduction a

4\times4

matrix has all zeros covered by

3

lines, and the smallest uncovered entry is

2

. A cell covered by two lines had value

1

. What is its value after adjustment?

Salam Academy Original Practice · Proposed mark scheme

Section 11 of 14

Summary

Reduce rows, columns.
Cover zeros with fewest lines.
Adjust if fewer than $n$ .
Dummies; maximise by subtracting from max.

Section 12 of 14

Quick quiz

Q1 · SA-DM-AS-Q011 markL1 FoundationNon-calculatorHungarian

An optimal allocation can be read from an

n\times n

reduced matrix when

Salam Academy Original Practice · Proposed mark scheme

Section 13 of 14

Same topic, different board

Specification: A level Further Mathematics 9FM0
Where: Decision 2 · Allocation (assignment) problems
Expected: Hungarian algorithm with row then column reduction; covering zeros; adjusting; dummy rows or columns; maximising by subtracting from the largest; incomplete data; formulating as a linear programme.
Calculator: Permitted; show enough working to earn the method marks.
Typical style: Edexcel often opens with a routine part and builds to a "show that" or "prove" part.
Open in: 9FM0 · Option

Section 14 of 14

Past paper questions

No past paper questions are tagged to this subtopic yet. We add papers every week.

Browse past papers

Salam Academy original content · Content status: reviewed and published. Syllabus mapping: Pearson Edexcel 9FM0, First teaching 2017 (official specification).