AS June 2018 Q1
1. Four workers, A, B, C and D, are to be assigned to four tasks, P, Q, R and S. Each worker must be assigned to exactly one task and each task must be done by only one worker. The time, in hours, that each worker takes to complete each task is shown in the table below.
| P | Q | R | S | |
|---|---|---|---|---|
| A | 7.5 | 3.5 | 8 | 9.5 |
| B | 5 | 2 | 7 | 7.5 |
| C | 4 | 3.5 | 3.5 | 8 |
| D | 6 | 5 | 3.5 | 4 |
Reducing rows first, use the Hungarian algorithm to obtain an allocation which minimises the total time. You must explain your method and show the table after each stage. (5)
| Scheme | Marks | AO | ||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Reducing rows
| M1 A1 | 1.1b 1.1b | ||||||||||||||||||||||||||||||||||||||||||||||||||
augment by 2.5
| M1 A1ft | 1.1b 1.1b | ||||||||||||||||||||||||||||||||||||||||||||||||||
| A – Q, B – P, C – R, D – S | A1ft | 2.2a | ||||||||||||||||||||||||||||||||||||||||||||||||||
| (5 marks) |
Notes
M1: simplifying the initial matrix by reducing rows and then columns
A1: cao
M1: develop an improved solution – need to see one double covered +e; one uncovered –e; and one single covered unchanged. 3 lines to 4 lines needed
A1ft: allow follow through from one numerical slip only during row/column reduction
A1ft: dependent on all previous M marks and one A mark – to deduce the optimal allocation from the location of the zeros in the table