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

Exam questions on Hungarian algorithm as a linear programme

1. 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
2. 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
3. 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