| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2006 |
| Session | January |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for maximisation |
| Difficulty | Moderate -0.8 This is a standard textbook application of the Hungarian algorithm with clear instructions to reduce rows first. The question requires methodical execution of a learned procedure with no problem-solving insight or adaptation needed. While it has multiple stages (13 marks), each step is mechanical and follows the algorithm directly. The maximisation context is routine (convert to minimisation by subtracting from maximum). Easier than average A-level maths due to its purely procedural nature. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Hot dogs and beef burgers (H) | Ice cream (I) | Popcorn, candyfloss and drinks (P) | Snacks and hot drinks (S) | |
| Site A | 267 | 272 | 276 | 261 |
| Site B | 264 | 271 | 278 | 263 |
| Site C | 267 | 273 | 275 | 263 |
| Site D | 261 | 269 | 274 | 257 |
(a) Define the terms (i) cut, (ii) minimum cut, as applied to a directed network flow.
(2)
B1: A cut is a partition of the vertices into two disjoint sets, one containing the source and one containing the sink.
B1: A minimum cut is a cut with the smallest total capacity of arcs going from the source side to the sink side.
(b) State the values of the cuts $C_1$ and $C_2$.
(3)
M1: Identify all arcs crossing $C_1$ (or $C_2$)
A1: Value of $C_1 = 729 + 408 + 236 = 1373$ (or equivalent correct calculation)
A1: Value of $C_2 = 307 + 214 + 129 + 251 + 285 = 1186$ (or equivalent correct calculation)
(c) Find a maximum flow pattern by inspection, and show it on the diagram below.
(3)
M1: Identify that the minimum cut value is 1186
A1: Maximum flow value is 1186
A1: A valid maximum flow pattern shown on diagram (flow values on each arc shown correctly, respecting capacities and conservation of flow at intermediate vertices)
(d) Find a second minimum cut for this network.
(1)
A1: State a second minimum cut with value 1186 (e.g., separating $\{S, A, B, D, F\}$ from $\{C, E, G, T\}$ or other valid partition with same capacity value)
(e) State, with a reason, which of these arcs should be added, and the value of the increased flow.
(2)
B1: The arc from D to E should be added (with reason: the arc D to G is already at capacity in the maximum flow, whereas adding D to E provides additional capacity that increases flow)
A1: The new maximum flow value is 1286 (or 1186 + 100)\begin{enumerate}
\item A theme park has four sites, A, B, C and D, on which to put kiosks. Each kiosk will sell a different type of refreshment. The income from each kiosk depends upon what it sells and where it is located. The table below shows the expected daily income, in pounds, from each kiosk at each site.
\end{enumerate}
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
& Hot dogs and beef burgers (H) & Ice cream (I) & Popcorn, candyfloss and drinks (P) & Snacks and hot drinks (S) \\
\hline
Site A & 267 & 272 & 276 & 261 \\
\hline
Site B & 264 & 271 & 278 & 263 \\
\hline
Site C & 267 & 273 & 275 & 263 \\
\hline
Site D & 261 & 269 & 274 & 257 \\
\hline
\end{tabular}
\end{center}
Reducing rows first, use the Hungarian algorithm to determine a site for each kiosk in order to maximise the total income. State the site for each kiosk and the total expected income. You must make your method clear and show the table after each stage.\\
(Total 13 marks)\\
\hfill \mbox{\textit{Edexcel D2 2006 Q1 [13]}}