| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2010 |
| Session | January |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm with unequal sets |
| Difficulty | Moderate -0.3 This is a standard textbook application of the Hungarian algorithm with clear instructions to add a dummy row and reduce rows first. The arithmetic is straightforward, and the method is algorithmic rather than requiring problem-solving insight. However, it requires careful execution of multiple steps and correct interpretation of the dummy row, placing it slightly below average difficulty. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Hotel | |||||
| \cline { 2 - 6 } | Palace | Regent | Sunnyside | Tall Trees | |
| \cline { 2 - 6 } | April | 30 | 28 | 32 | 25 |
| \cline { 2 - 6 } Daughter | May | 32 | 34 | 32 | 35 |
| \cline { 2 - 6 } | June | 40 | 40 | 39 | 38 |
| \cline { 2 - 6 } | |||||
| \cline { 2 - 6 } | |||||
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Adding dummy row with all equal values (40,40,40,40) | B1 | Adding a dummy row of all equal values |
| Substantially correct attempt to reduce matrix (condone 1 numerical slip) | M1 | Substantially correct attempt to reduce matrix |
| Correct reduced cost matrix from reducing rows, first statement of how table was formed, including reference to columns | A1 | cao |
| Cross through zeros using minimum number of lines | B1 | |
| Correct augmented matrix and statement of how table was formed | B1 | cao |
| \(A = T,\ M = P,\ J = S\) | B1 | cao |
| Total cost \(= £9600\) | B1 | £9600 (cao) with units |
# Question 2:
## Hungarian Algorithm
| Answer/Working | Mark | Guidance |
|---|---|---|
| Adding dummy row with all equal values (40,40,40,40) | B1 | Adding a dummy row of all equal values |
| Substantially correct attempt to reduce matrix (condone 1 numerical slip) | M1 | Substantially correct attempt to reduce matrix |
| Correct reduced cost matrix from reducing rows, first statement of how table was formed, including reference to columns | A1 | cao |
| Cross through zeros using minimum number of lines | B1 | |
| Correct augmented matrix and statement of how table was formed | B1 | cao |
| $A = T,\ M = P,\ J = S$ | B1 | cao |
| Total cost $= £9600$ | B1 | £9600 (cao) with units |
---2 Dudley has three daughters who are all planning to get married next year. The girls are named April, May and June, after the months in which they were born. Each girl wants to get married on her own birthday.
Dudley has already obtained costings from four different hotels. From past experience, Dudley knows that when his family get together they are likely to end up with everyone fighting one another, so he cannot use the same hotel twice.
The table shows the costs, in $\pounds 100$, for each hotel to host each daughter's wedding.
\begin{center}
\begin{tabular}{ l | l | c | c | c | c | }
\multicolumn{6}{c}{Hotel} \\
\cline { 2 - 6 }
& & Palace & Regent & Sunnyside & Tall Trees \\
\cline { 2 - 6 }
& April & 30 & 28 & 32 & 25 \\
\cline { 2 - 6 }
Daughter & May & 32 & 34 & 32 & 35 \\
\cline { 2 - 6 }
& June & 40 & 40 & 39 & 38 \\
\cline { 2 - 6 }
& & & & & \\
\cline { 2 - 6 }
\end{tabular}
\end{center}
Dudley wants to choose the three hotels to minimise the total cost.\\
Add a dummy row and then apply the Hungarian algorithm to the table, reducing rows first, to find an optimal allocation between the hotels and Dudley's daughters. State how each table is formed and write out the final solution and its cost to Dudley.
\hfill \mbox{\textit{OCR D2 2010 Q2 [7]}}