Write the cost objective function for an n\times n problem.

Minimise \sum{i=1}^{n}\sum{j=1}^{n}c{ij}x{ij}.

How is a maximum profit problem written as an LP?

Maximise \sum\sum p{ij}x{ij}, using the profit matrix directly.

How many variables and equality constraints in an n\times n problem?

n^2 variables and 2n equality constraints.

With more workers than tasks, what changes in the worker constraints?

Each worker does at most one task: x{i1}+\dots+x{in}\le1.

How is an impossible pairing handled in an LP?

Omit its variable, or add x{ij}=0.

Why can an extra condition such as x{11}+x{33}\le1 not be dealt with by the Hungarian algorithm?

It is not a one-per-worker or one-per-task condition, so the problem is no longer a pure assignment problem.

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

Card 1 of 120 of 12 known

Question

What does $x_{ij}$ mean in the assignment formulation?

Tap or press Space to reveal

Tap card or press Space to flip

See all 12 cards

What does $x_{ij}$ mean in the assignment formulation?: $x_{ij}=1$ if worker $i$ does task $j$ , and $0$ otherwise.
What values may $x_{ij}$ take?: $0$ or $1$ only (binary).
Write the cost objective function for an $n\times n$ problem.: Minimise $\sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}x_{ij}$ .
How is a maximum profit problem written as an LP?: Maximise $\sum\sum p_{ij}x_{ij}$ , using the profit matrix directly.
What constraint says worker $i$ does exactly one task?: $x_{i1}+x_{i2}+\dots+x_{in}=1$ .
What constraint says task $j$ is done by exactly one worker?: $x_{1j}+x_{2j}+\dots+x_{nj}=1$ .
How many variables and equality constraints in an $n\times n$ problem?: $n^2$ variables and $2n$ equality constraints.
With more workers than tasks, what changes in the worker constraints?: Each worker does at most one task: $x_{i1}+\dots+x_{in}\le1$ .
How is an impossible pairing handled in an LP?: Omit its variable, or add $x_{ij}=0$ .
What does $x_{23}=1$ mean?: Worker 2 does task 3.
Why can an extra condition such as $x_{11}+x_{33}\le1$ not be dealt with by the Hungarian algorithm?: It is not a one-per-worker or one-per-task condition, so the problem is no longer a pure assignment problem.
Total cost of the allocation $x_{12}=x_{21}=1$ with costs $c_{12}=9$ , $c_{21}=8$ ?: $9+8=17$ .

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).