| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for minimisation |
| Difficulty | Easy -1.2 This is a straightforward application of the Hungarian algorithm to a standard 4×4 minimisation problem with no complications. The algorithm is mechanical and routine for D2 students, requiring only careful execution of the standard steps (row reduction, column reduction, covering zeros, and adjustment if needed) with no problem-solving insight or novel thinking required. |
| Spec | 7.03m Packing extensions: 2D/3D packing and knapsack problems |
| Film | Musical | Ballet | Concert | |
| Andrew | 5 | 20 | 12 | 18 |
| Betty | 6 | 18 | 15 | 16 |
| Carlos | 4 | 21 | 9 | 15 |
| Davina | 5 | 16 | 11 | 13 |
| Answer | Marks | Guidance |
|---|---|---|
| Content | Marks | Guidance |
| Row reduction showing: 0 15 7 13; 0 12 9 10; 0 17 5 11; 0 11 6 8 with column minima: 0 11 5 8 | M1 A1 | |
| Reducing columns gives: 0 4 2 5; 0 1 4 2; 0 6 0 3; (line drawn through fourth row) | M1 A1 | Note: a different choice of lines will lead to the same final assignment |
| 3 lines required to cover all zeros, apply algorithm showing: 0' 3 1 4; 0 0'-3 1; (line drawn) 1 6 0'-3; 2'-0 1 0' | M1 A1 | |
| 4 lines required to cover all zeros so allocation is possible | B1 | |
| Andrew reviews a film; Betty reviews a musical; Carlos reviews a ballet; Davina reviews a concert | A1 | |
| total cost = 5 + 18 + 9 + 13 = £45 | A1 | (9) |
| Content | Marks | Guidance |
|---------|-------|----------|
| Row reduction showing: 0 15 7 13; 0 12 9 10; 0 17 5 11; 0 11 6 8 with column minima: 0 11 5 8 | M1 A1 | |
| Reducing columns gives: 0 4 2 5; 0 1 4 2; 0 6 0 3; (line drawn through fourth row) | M1 A1 | Note: a different choice of lines will lead to the same final assignment |
| 3 lines required to cover all zeros, apply algorithm showing: 0' 3 1 4; 0 0'-3 1; (line drawn) 1 6 0'-3; 2'-0 1 0' | M1 A1 | |
| 4 lines required to cover all zeros so allocation is possible | B1 | |
| Andrew reviews a film; Betty reviews a musical; Carlos reviews a ballet; Davina reviews a concert | A1 | |
| total cost = 5 + 18 + 9 + 13 = £45 | A1 | (9) |3. Four people are contributing to the entertainment section of an email magazine. For one issue reviews are required for a film, a musical, a ballet and a concert such that each person reviews one show. The people in charge of the magazine will pay each person's expenses and the cost, in pounds, for each reviewer to attend each show are given below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
& Film & Musical & Ballet & Concert \\
\hline
Andrew & 5 & 20 & 12 & 18 \\
\hline
Betty & 6 & 18 & 15 & 16 \\
\hline
Carlos & 4 & 21 & 9 & 15 \\
\hline
Davina & 5 & 16 & 11 & 13 \\
\hline
\end{tabular}
\end{center}
Use the Hungarian algorithm to find an optimal assignment which minimises the total cost. State the total cost of this allocation.
\hfill \mbox{\textit{OCR D2 Q3 [9]}}