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

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

   (a)

   What does $x_{23}=1$ mean?

   [1 mark]

   • ANurse 3 is assigned to ward 2
   • BWard 2 costs £$3$ hundred
   • CNurse 2 is assigned to ward 3
   • DNurse 2 is not assigned to ward 3

   (b)

   What is the total cost, in £ hundred, when $x_{12}=x_{21}=x_{33}=1$ and all other variables are $0$?

   [1 mark]

   • A$21$
   • B$15$
   • C$19$
   • D$27$

   (c)

   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]

   Total for question 1: 4 marks

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

   (a)

   Which of these is the objective function?

   [1 mark]

   • AMinimise $\sum_{i=1}^{4}\sum_{j=1}^{4}p_{ij}x_{ij}$
   • BMaximise $\sum_{i=1}^{4}\sum_{j=1}^{4}x_{ij}$
   • CMaximise $\sum_{i=1}^{4}\sum_{j=1}^{4}p_{ij}$
   • DMaximise $\sum_{i=1}^{4}\sum_{j=1}^{4}p_{ij}x_{ij}$

   (b)

   How many equality constraints (not counting the conditions on the values of $x_{ij}$) does the formulation have?

   [1 mark]

   • A$4$
   • B$8$
   • C$16$
   • D$12$

   (c)

   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]

   Total for question 2: 4 marks

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

   (a)

   Define suitable variables and write down the objective function.

   [3 marks]

   (b)

   Write down the constraints, and explain why the constraints for the workers are not all equalities.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A theatre has three technicians, Raj, Sam and Tess, and three tasks: lighting (1), sound (2) and staging (3). Each technician does one task and each task is done by one technician. The value, in £ hundred, of each technician on each task is given below in the order lighting, sound, staging. Raj: 14, 11, 9. Sam: 8, 13, – (Sam cannot do staging). Tess: 10, 7, 12. The theatre wants the total value to be as large as possible. Technicians Raj, Sam and Tess are numbered 1, 2 and 3.

   (a)

   Formulate this as a linear programming problem.

   [6 marks]

   (b)

   The booking system means that Raj on lighting and Tess on staging cannot both be chosen. (i) Write this as a constraint. (ii) Explain why the Hungarian algorithm cannot now be used. (iii) Given that without this condition the maximum total value is £$3900$, find the new maximum and the allocation.

   [6 marks]

   Total for question 4: 12 marks

End of questions