| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2007 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for minimisation |
| Difficulty | Moderate -0.5 This is a standard Hungarian algorithm application with clear structure: a 4×4 matrix, straightforward row/column reduction steps, and a direct interpretation. Part (c) adds mild complexity requiring understanding of sequential production flow, but the overall question follows textbook methodology with no novel insights required. Slightly easier than average due to small matrix size and routine application. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| cutting | stitching | filling | dressing | |
| \(A\) | 66 | 101 | 85 | 36 |
| \(B\) | 66 | 98 | 74 | 38 |
| \(C\) | 63 | 97 | 71 | 34 |
| \(D\) | 67 | 102 | 78 | 35 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Initial matrix: \(\begin{bmatrix} 66 & 101 & 85 & 36 \\ 66 & 98 & 74 & 38 \\ 63 & 97 & 71 & 34 \\ 67 & 102 & 78 & 35 \end{bmatrix}\) | ||
| Reducing rows first to give \(\begin{bmatrix} 30 & 65 & 49 & 0 \\ 28 & 60 & 36 & 0 \\ 29 & 63 & 37 & 0 \\ 32 & 67 & 43 & 0 \end{bmatrix}\) then columns | M1A1 | |
| \(\begin{bmatrix} 1 & 4 & 12 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 2 & 0 & 0 \\ 3 & 6 & 6 & 0 \end{bmatrix} \rightarrow \begin{bmatrix} 0 & 3 & 11 & 0 \\ 0 & 0 & 0 & 2 \\ 0 & 2 & 0 & 1 \\ 2 & 5 & 5 & 0 \end{bmatrix}\) | M1A1ftA1ft | |
| M1A1ftA1ft | ||
| A – cutting, B – stitching, C – filling, D – dressing | A1 | 9 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(66 + 98 + 71 + 35 = 270\) seconds | B1 | 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(20 \times 98 + 66 + 71 + 35 = 2132\) seconds | M1A1ft | |
| \(= 35\) minutes \(32\) seconds | A1 | 3 |
# Question 3:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Initial matrix: $\begin{bmatrix} 66 & 101 & 85 & 36 \\ 66 & 98 & 74 & 38 \\ 63 & 97 & 71 & 34 \\ 67 & 102 & 78 & 35 \end{bmatrix}$ | | |
| Reducing rows first to give $\begin{bmatrix} 30 & 65 & 49 & 0 \\ 28 & 60 & 36 & 0 \\ 29 & 63 & 37 & 0 \\ 32 & 67 & 43 & 0 \end{bmatrix}$ then columns | M1A1 | |
| $\begin{bmatrix} 1 & 4 & 12 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 2 & 0 & 0 \\ 3 & 6 & 6 & 0 \end{bmatrix} \rightarrow \begin{bmatrix} 0 & 3 & 11 & 0 \\ 0 & 0 & 0 & 2 \\ 0 & 2 & 0 & 1 \\ 2 & 5 & 5 & 0 \end{bmatrix}$ | M1A1ftA1ft | |
| | M1A1ftA1ft | |
| A – cutting, B – stitching, C – filling, D – dressing | A1 | 9 |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $66 + 98 + 71 + 35 = 270$ seconds | B1 | 1 |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $20 \times 98 + 66 + 71 + 35 = 2132$ seconds | M1A1ft | |
| $= 35$ minutes $32$ seconds | A1 | 3 |
---3. To raise money for charity it is decided to hold a Teddy Bear making competition. Teams of four compete against each other to make 20 Teddy Bears as quickly as possible.
There are four stages: first cutting, then stitching, then filling and finally dressing.\\
Each team member can only work on one stage during the competition. As soon as a stage is completed on each Teddy Bear the work is passed immediately to the next team member.
The table shows the time, in seconds, taken to complete each stage of the work on one Teddy Bear by the members $A , B , C$ and $D$ of one of the teams.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
& cutting & stitching & filling & dressing \\
\hline
$A$ & 66 & 101 & 85 & 36 \\
\hline
$B$ & 66 & 98 & 74 & 38 \\
\hline
$C$ & 63 & 97 & 71 & 34 \\
\hline
$D$ & 67 & 102 & 78 & 35 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Use the Hungarian algorithm, reducing rows first, to obtain an allocation that minimises the time taken by this team to produce one Teddy Bear. You must make your method clear and show the table after each iteration.
\item State the minimum time it will take this team to produce one Teddy Bear.
Using the allocation found in (a),
\item calculate the minimum total time this team will take to complete 20 Teddy Bears. You should make your reasoning clear and state your answer in minutes and seconds.\\
(Total 13 marks)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2007 Q3 [13]}}