Decision Mathematics 2: Allocation (assignment) problemsEdexcel A-Level Further Maths: Topic test

1. 1
   A film festival has four volunteers, 1, 2, 3 and 4, to set up four venues, A, B, C and D. Each volunteer sets up exactly one venue. The time, in minutes, that each volunteer needs for each venue is: volunteer 1: A 12, B 9, C 14, D 10; volunteer 2: A 8, B 11, C 7, D 13; volunteer 3: A 10, B 12, C 9, D 8; volunteer 4: A 15, B 10, C 11, D 14. The Hungarian algorithm is used to minimise the total time, reducing rows first.

   (a)

   By how much is each entry in the row for volunteer 3 reduced in the row reduction?

   [1 mark]

   • A$10$
   • B$12$
   • C$8$
   • D$9$

   (b)

   After the rows have been reduced, by how much is the column for venue A reduced in the column reduction?

   [1 mark]

   • A$1$
   • B$3$
   • C$8$
   • D$0$

   (c)

   Complete the column reduction. Find the minimum number of lines needed to cover all the zeros, and state what this shows about the solution.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A consultancy has three consultants, 1, 2 and 3, to assign to three clients, X, Y and Z, one consultant for each client. The profit, in £ hundred, for each pairing is: consultant 1: X 14, Y 11, Z 9; consultant 2: X 10, Y 15, Z 12; consultant 3: X 8, Y 10, Z 13. The firm wants the maximum total profit and uses the Hungarian algorithm.

   (a)

   To change this into a minimising problem, every profit is subtracted from the largest profit. What is the new entry for consultant 3 with client X?

   [1 mark]

   • A$8$
   • B$7$
   • C$-7$
   • D$23$

   (b)

   Once the least-cost allocation has been found from the converted matrix, how is the maximum profit found?

   [1 mark]

   • AAdd the converted values of the allocated pairs
   • BSubtract the total converted value from 15
   • CTake the largest converted value
   • DAdd the original profits of the allocated pairs

   (c)

   Convert the profits and reduce the rows. Hence find the allocation that gives the maximum profit, and the maximum profit.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   An events company has four stewards, 1, 2, 3 and 4, and three gates, X, Y and Z. Each gate needs exactly one steward and each steward works at most one gate. The cost, in £, of each steward at each gate is: steward 1: X 18, Y 24, Z 21; steward 2: X 20, Z 19; steward 3: X 22, Y 25, Z 20; steward 4: X 17, Y 24, Z 22. Steward 2 is not allowed to work at gate Y. The total cost is to be minimised.

   (a)

   Explain how the problem is changed so that the Hungarian algorithm can be used, and write down the matrix that results.

   [3 marks]

   (b)

   Use the Hungarian algorithm to find the least-cost allocation, and state which steward is not given a gate and the minimum cost.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A bakery has four bakers, 1, 2, 3 and 4, and four products, W, X, Y and Z. Each baker makes exactly one product and each product is made by exactly one baker. The time, in minutes, each baker needs for each product is: baker 1: W 21, X 23, Y 8, Z 8; baker 2: W 19, X 18, Y 19, Z 18; baker 3: W 17, X 21, Y 12, Z 17; baker 4: W 24, X 22, Y 23, Z 6. The total time is to be minimised.

   (a)

   Reduce the rows and then the columns of the matrix. Find the minimum number of lines needed to cover all the zeros, and explain why an allocation cannot yet be made.

   [6 marks]

   (b)

   Using the three lines from part (a), complete the Hungarian algorithm. Give the allocation and the minimum total time.

   [6 marks]

   Total for question 4: 12 marks

5. 5
   A hotel assigns three receptionists, 1, 2 and 3, to three shifts: morning (1), afternoon (2) and night (3). Each receptionist works exactly one shift and each shift has exactly one receptionist. Let $x_{ij}=1$ if receptionist $i$ works shift $j$, and $x_{ij}=0$ otherwise. The cost, in £, for shifts 1, 2 and 3 is: receptionist 1: 30, 25, 40; receptionist 2: 28, 35, 32; receptionist 3: 26, 31, 29. The total cost is to be minimised.

   (a)

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

   [1 mark]

   • AReceptionist 2 works the afternoon shift
   • BReceptionist 2 does not work the night shift
   • CReceptionist 3 works the afternoon shift
   • DReceptionist 2 works the night shift

   (b)

   Which equation makes sure that receptionist 1 works exactly one shift?

   [1 mark]

   • A$x_{11}+x_{21}+x_{31}=1$
   • B$x_{11}+x_{12}+x_{13}=1$
   • C$x_{11}+x_{12}+x_{13}=3$
   • D$x_{12}+x_{22}+x_{32}=1$

   (c)

   Write down the objective function, and the constraint that makes sure the night shift is covered by exactly one receptionist.

   [2 marks]

   Total for question 5: 4 marks

6. 6
   A charity has four volunteers, 1, 2, 3 and 4, for three stalls, 1, 2 and 3. Each stall has exactly one volunteer and each volunteer works at most one stall. Let $x_{ij}=1$ if volunteer $i$ works stall $j$, and $x_{ij}=0$ otherwise. The money raised, in £, is: volunteer 1: 40, 55, 35; volunteer 2: 50, 45, 60; volunteer 3: 55, 40, 50; volunteer 4: 45, 60, 40, for stalls 1, 2 and 3 respectively. The total raised is to be maximised.

   (a)

   Which constraint is correct for volunteer 2?

   [1 mark]

   • A$x_{21}+x_{22}+x_{23}\le1$
   • B$x_{21}+x_{22}+x_{23}=1$
   • C$x_{12}+x_{22}+x_{32}+x_{42}\le1$
   • D$x_{21}+x_{22}+x_{23}\ge1$

   (b)

   Volunteer 1 works stall 2, volunteer 2 works stall 3, volunteer 3 works stall 1 and volunteer 4 works no stall. What is the value of the objective function, in £?

   [1 mark]

   • A$155$
   • B$230$
   • C$170$
   • D$115$

   (c)

   Write down the constraint for volunteer 4, and the constraint for stall 3.

   [2 marks]

   Total for question 6: 4 marks

7. 7
   A garden centre has three staff, 1, 2 and 3, to do three jobs, 1, 2 and 3. Each member of staff does exactly one job and each job is done by exactly one member of staff. Let $x_{ij}=1$ if staff $i$ does job $j$, and $x_{ij}=0$ otherwise. The time, in minutes, for jobs 1, 2 and 3 is: staff 1: 53, 56, 36; staff 2: 51, 34, 30; staff 3: 36, 59, 41. The total time is to be minimised.

   (a)

   Formulate this as a linear programming problem. Write down the objective function and the constraints.

   [3 marks]

   (b)

   Use the Hungarian algorithm to solve the problem. State the values of the variables that equal 1 and the minimum total time.

   [4 marks]

   Total for question 7: 7 marks

8. 8
   A tour company has three guides, 1, 2 and 3, to lead three tours, 1, 2 and 3. Each guide leads exactly one tour and each tour has exactly one guide. The profit, in £ hundred, for tours 1, 2 and 3 is: guide 1: 38, 46, 64; guide 2: 60, 33, 52; guide 3: 44, 42, 37. The company wants the maximum total profit. Let $x_{ij}=1$ if guide $i$ leads tour $j$, and $x_{ij}=0$ otherwise.

   (a)

   Formulate this as a linear programming problem, writing down the objective function and all the constraints, and explain why the constraints are equalities.

   [6 marks]

   (b)

   Use the Hungarian algorithm to find the allocation that gives the maximum profit. State the values of the variables that equal 1 and the maximum profit.

   [6 marks]

   Total for question 8: 12 marks

End of questions