| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2007 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for maximisation |
| Difficulty | Moderate -0.8 This is a straightforward application of the Hungarian algorithm with minimal problem-solving required. The question provides the necessary transformation (subtract from 6), explicitly tells students to reduce rows first, and uses a small 4×4 matrix. Part (i) tests basic understanding that the algorithm minimises rather than maximises. The mechanical execution of the algorithm is routine for D2 students who have practiced this standard technique. |
| Spec | 7.06a LP formulation: variables, constraints, objective function7.06b Slack variables: converting inequalities to equations7.06c Working with constraints: algebra and ad hoc methods7.06d Graphical solution: feasible region, two variables |
|
|
|
| |||||||||
| Phil | 5 | 1 | 0 | 4 | ||||||||
| Rob | 1 | 6 | 1 | 2 | ||||||||
| Sam | 4 | 2 | 2 | 3 | ||||||||
| Tim | 3 | 5 | 0 | 0 |
| Answer | Marks | Guidance |
|---|---|---|
| (i) | The Hungarian algorithm finds the minimum cost allocation, we need to subtract each score from 6 to convert a maximisation into a minimisation. | B1 |
| (ii) | First subtract each entry from 6 | B1 |
| Reduce rows: 0, 4, 5, 1 / 5, 0, 5, 4 / 0, 2, 2, 1 / 2, 0, 5, 5 | M1 | Reducing rows first |
| Then reduce columns: 0, 4, 3, 0 / 5, 0, 3, 3 / 0, 2, 0, 0 / 2, 0, 3, 4 | M1 dep | Then reducing columns |
| Cover 0's using 3 lines: 0, 4, 3, 0 / 5, 0, 3, 3 / 0, 2, 0, 0 / 2, 0, 3, 4 | A1 | A correct reduced cost matrix from rows reduced first (cao) |
| Augment by 2: 0, 6, 3, 0 / 3, 0, 1, 1 / 0, 4, 0, 0 / 0, 0, 1, 2 | M1 | Covering zeros using minimum number of lines and augmenting by (their) 2 |
| A1 | A correct augmented matrix (cao) from rows reduced first | |
| Phil = Front room, Rob = Back room, Sam = Downstairs room, Tim = Attic room | B1 | Correct matching |
| [7] |
(i) | The Hungarian algorithm finds the minimum cost allocation, we need to subtract each score from 6 to convert a maximisation into a minimisation. | B1 | A valid reference to maximising/minimising |
(ii) | First subtract each entry from 6 | B1 | Correctly subtracting each entry from 6 (cao) |
| Reduce rows: 0, 4, 5, 1 / 5, 0, 5, 4 / 0, 2, 2, 1 / 2, 0, 5, 5 | M1 | Reducing rows first |
| Then reduce columns: 0, 4, 3, 0 / 5, 0, 3, 3 / 0, 2, 0, 0 / 2, 0, 3, 4 | M1 dep | Then reducing columns |
| Cover 0's using 3 lines: 0, 4, 3, 0 / 5, 0, 3, 3 / 0, 2, 0, 0 / 2, 0, 3, 4 | A1 | A correct reduced cost matrix from rows reduced first (cao) |
| Augment by 2: 0, 6, 3, 0 / 3, 0, 1, 1 / 0, 4, 0, 0 / 0, 0, 1, 2 | M1 | Covering zeros using minimum number of lines and augmenting by (their) 2 |
| | A1 | A correct augmented matrix (cao) from rows reduced first |
| Phil = Front room, Rob = Back room, Sam = Downstairs room, Tim = Attic room | B1 | Correct matching |
| | [7] | |
---1 Four friends have rented a house and need to decide who will have which bedroom. The table below shows how each friend rated each room, so the higher the rating the more the room was liked.
\begin{center}
\begin{tabular}{ | c | c c c c | }
\hline
& \begin{tabular}{ c }
Attic \\
room \\
\end{tabular} & \begin{tabular}{ c }
Back \\
room \\
\end{tabular} & \begin{tabular}{ c }
Downstairs \\
room \\
\end{tabular} & \begin{tabular}{ c }
Front \\
room \\
\end{tabular} \\
\hline
Phil & 5 & 1 & 0 & 4 \\
Rob & 1 & 6 & 1 & 2 \\
Sam & 4 & 2 & 2 & 3 \\
Tim & 3 & 5 & 0 & 0 \\
\hline
\end{tabular}
\end{center}
The Hungarian algorithm is to be used to find the matching with the greatest total. Before the Hungarian algorithm can be used, each rating is subtracted from 6.\\
(i) Explain why the ratings could not be used as given in the table.\\
(ii) Apply the Hungarian algorithm, reducing rows first, to match the friends to the rooms. You must show your working and say how each matrix was formed.
\hfill \mbox{\textit{OCR D2 2007 Q1 [8]}}