Standard +0.3 This is a standard Hungarian algorithm application with a 3×4 matrix requiring dummy row addition. The method is algorithmic and procedural—students follow mechanical steps (row reduction, column reduction, covering zeros, adjusting uncovered elements) taught directly in D2. While it requires careful bookkeeping across multiple stages for 10 marks, it demands no problem-solving insight or novel thinking, making it easier than average A-level questions that require mathematical reasoning.
A construction company has three teams of workers available, each of which is to be assigned to one of four jobs at a site. The following table shows the estimated cost, in tens of pounds, of each team doing each job:
\begin{array}{c|c|c|c|c}
& Windows & Conservatory & Doors & Greenhouse
\hline
Team A & 27 & 80 & 8 & 81
Team B & 28 & 60 & 5 & 71
Team C & 30 & 90 & 7 & 73
\end{array}
Use the Hungarian algorithm to find an allocation of jobs which will minimise the total cost. Show the state of the table after each stage in the algorithm and state the cost of the final assignment. [10 marks]
Note: a different choice of lines will lead to the same final assignment
4 lines required to cover all zeros so allocation is possible: Team A does windows, Team B does conservatory, Team C does doors, greenhouse not done. Total cost = \(10 \times (27 + 60 + 7) = £940\)
A1 A1
(10)
| Add dummy row giving row minimums: 8, 5, 7, 0 | M1 | |
| Reduce rows to get: 19 72 0 73; 23 55 0 66; 23 83 0 66; −0 −0 −0 −0 | M1 A1 | |
| Reducing columns makes no difference | B1 | |
| Apply algorithm with 2 lines required to cover zeros: 0 53 0 54; 4 36 0 47; 4 64 0 47; −0 −0 −19 −0 | B1 | |
| 3 lines required: 0ˆ 17 0ˆ 18; −4 0ˆ 0 11; 4 28 0ˆ 11; 36ˆ 0 55 0ˆ | M1 A1 | Note: a different choice of lines will lead to the same final assignment |
| 4 lines required to cover all zeros so allocation is possible: Team A does windows, Team B does conservatory, Team C does doors, greenhouse not done. Total cost = $10 \times (27 + 60 + 7) = £940$ | A1 A1 | (10) |
A construction company has three teams of workers available, each of which is to be assigned to one of four jobs at a site. The following table shows the estimated cost, in tens of pounds, of each team doing each job:
\begin{array}{c|c|c|c|c}
& Windows & Conservatory & Doors & Greenhouse \\
\hline
Team A & 27 & 80 & 8 & 81 \\
Team B & 28 & 60 & 5 & 71 \\
Team C & 30 & 90 & 7 & 73 \\
\end{array}
Use the Hungarian algorithm to find an allocation of jobs which will minimise the total cost. Show the state of the table after each stage in the algorithm and state the cost of the final assignment. [10 marks]
\hfill \mbox{\textit{OCR D2 Q4 [10]}}