Hungarian algorithm as a linear programmeEdexcel A-Level Further Maths: Revision notes

Section 1

Turning an allocation problem into an LP

An allocation problem can be written as a linear programme. For $n$ workers and $n$ tasks, define a binary variable for every pairing: $x_{ij}=\begin{cases}1&\text{if worker } i \text{ does task } j,\\0&\text{otherwise.}\end{cases}$ The first subscript is the worker (row of the matrix) and the second is the task (column). A complete allocation is a choice of values of $x_{ij}$ , and the cost is read from the cost matrix.

Key termslinear programmebinary variable

Common mistake

Swapping the subscripts. $x_{23}=1$ means worker 2 does task 3, not worker 3 does task 2.

Section 2

The objective function

Only chosen pairings ( $x_{ij}=1$ ) add their cost, so the total cost is $\sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}x_{ij}.$ To minimise cost, minimise this expression. For maximum profit, use profits $p_{ij}$ and maximise $\sum\sum p_{ij}x_{ij}$ (no conversion to a minimum is needed in an LP). Example: costs $\begin{pmatrix}6&9\\8&5\end{pmatrix}$ give minimise $6x_{11}+9x_{12}+8x_{21}+5x_{22}$ .

Key termsobjective function

Section 3

The constraints

Each worker does exactly one task, and each task is done by exactly one worker:

for each worker $i$ : $x_{i1}+x_{i2}+\dots+x_{in}=1$ ( $n$ constraints);
for each task $j$ : $x_{1j}+x_{2j}+\dots+x_{nj}=1$ ( $n$ constraints). Also $x_{ij}\in\{0,1\}$ . That is $2n$ equality constraints and $n^2$ variables. Example, $3\times3$ : worker 2 gives $x_{21}+x_{22}+x_{23}=1$ , and task 3 gives $x_{13}+x_{23}+x_{33}=1$ .

Key termsconstraint

Exam tip

Check by counting: an $n\times n$ problem has $2n$ equalities and $n^2$ variables.

Section 4

Unequal numbers and impossible pairings

Unequal numbers. With more workers than tasks, every task is still done exactly once, but each worker does at most one task: $x_{i1}+\dots+x_{in}\le1$ . Equalities for every worker would be impossible. (This does the same job as adding a dummy task.) Impossible pairing. If worker $i$ cannot do task $j$ , leave $x_{ij}$ out of the objective and constraints, or add $x_{ij}=0$ . This does the same job as the large number $M$ in the algorithm. Maximising. Keep the profit matrix and write maximise $\sum\sum p_{ij}x_{ij}$ .

Key termsat most oneimpossible pairing

Section 5

Worked example and what the algorithm cannot do

Three technicians and three tasks with profits $\begin{pmatrix}14&11&9\\8&13&-\\10&7&12\end{pmatrix}$ (the dash means impossible): maximise $14x_{11}+11x_{12}+9x_{13}+8x_{21}+13x_{22}+10x_{31}+7x_{32}+12x_{33}$ subject to $x_{11}+x_{12}+x_{13}=1$ , $x_{21}+x_{22}=1$ , $x_{31}+x_{32}+x_{33}=1$ , $x_{11}+x_{21}+x_{31}=1$ , $x_{12}+x_{22}+x_{32}=1$ , $x_{13}+x_{33}=1$ . The best choice is $x_{11}=x_{22}=x_{33}=1$ with profit $14+13+12=39$ . The LP form is more flexible. A condition such as $x_{11}+x_{33}\le1$ (the two pairings cannot both be used) is not a row or column condition, so the Hungarian algorithm cannot handle it, but it can be added to the LP. Here it rules out the best allocation, and the best remaining one is $x_{13}=x_{22}=x_{31}=1$ with profit $9+13+10=32$ .

Key termsformulation

Common mistake

Using equalities for the workers when there are more workers than tasks. Use at most one for the workers.

That's the notes covered.

Carry on to the next subtopic.

Exam questions on Hungarian algorithm as a linear programme

A hospital assigns three nurses, 1, 2 and 3, to three wards, 1, 2 and 3, with one nurse on each ward. Let $x_{ij}=1$ if nurse $i$ is assigned to ward $j$ , and $x_{ij}=0$ otherwise. The cost, in £ hundred, of nurse $i$ on ward $j$ is the entry in row $i$ , column $j$ of $\begin{pmatrix} 6 & 9 & 7 \\ 8 & 5 & 10 \\ 7 & 8 & 4 \end{pmatrix}$ . The hospital wants the total cost to be as small as possible and formulates the problem as a linear programme.
Write down the constraint that ensures nurse 2 is assigned to exactly one ward, and state the values each $x_{ij}$ may take.2 marks
A company has four representatives and four regions. Let $p_{ij}$ be the profit, in £ hundred, when representative $i$ works in region $j$ , and let $x_{ij}=1$ if representative $i$ is sent to region $j$ and $x_{ij}=0$ otherwise. Each representative goes to exactly one region and each region receives exactly one representative. The company wants to maximise the total profit and formulates the problem as a linear programme.
The allocation $x_{11}=x_{22}=x_{33}=x_{44}=1$ , with all other variables $0$ , has $p_{11}=12$ , $p_{22}=9$ , $p_{33}=14$ and $p_{44}=11$ . Show that this allocation satisfies the constraints for representative 1 and for region 1, and find its total profit.2 marks
A firm has four workers and three tasks. Each task must be done by exactly one worker and each worker does at most one task. The time, in hours, for worker $i$ to do task $j$ is the entry in row $i$ , column $j$ of $\begin{pmatrix} 9 & 6 & 8 \\ 7 & 8 & 5 \\ 6 & 9 & 7 \\ 8 & 5 & 9 \end{pmatrix}$ . The firm wants the total time to be as small as possible and formulates the problem as a linear programme.
Define suitable variables and write down the objective function.3 marks

See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).