AQA D2 2006 January — Question 1

Exam BoardAQA
ModuleD2 (Decision Mathematics 2)
Year2006
SessionJanuary
TopicMatchings and Allocation

1 Five trainers, Ali, Bo, Chas, Dee and Eve, held an initial training session with each of four teams over an assault course. The completion times in minutes are recorded below.
AliBoChasDeeEve
Team 11619182524
Team 22221202625
Team 32122232124
Team 42021212320
Each of the four teams is to be allocated a trainer and the overall time for the four teams is to be minimised. No trainer can train more than one team.
  1. Modify the table of values by adding an extra row of values so that the Hungarian algorithm can be applied.
  2. Use the Hungarian algorithm, reducing columns first then rows, to decide which four trainers should be allocated to which team. State the minimum total training time for the four teams using this matching.