Edexcel D2 2012 June — Question 1 9 marks

Exam BoardEdexcel
ModuleD2 (Decision Mathematics 2)
Year2012
SessionJune
Marks9
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicMatchings and Allocation
TypeHungarian algorithm for minimisation
DifficultyModerate -0.8 This is a straightforward application of the Hungarian algorithm with clear instructions to reduce rows first. The 5×5 table requires systematic but routine execution of the algorithm steps (row reduction, column reduction, covering zeros, improving). While it involves multiple stages and careful bookkeeping, it requires no problem-solving insight—just mechanical application of a learned procedure.
Spec7.07a Simplex tableau: initial setup in standard format
  1. Five workers, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }\) and E , are to be assigned to five tasks, \(1,2,3,4\) and 5 . Each worker is to be assigned to one task and each task must be assigned to one worker.
The cost, in pounds, of assigning each person to each task is shown in the table below. The cost is to be minimised.
12345
A129127122134135
B127125123131132
C142131121140139
D127127122131136
E141134129144143
  1. Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the cost. You must make your method clear and show the table after each stage.
  2. Find the minimum cost.
AnswerMarks Guidance
Answer/WorkingMarks Guidance
Reducing rows then columns: \(\begin{bmatrix}7 & 5 & 0 & 12 & 13\\4 & 2 & 0 & 8 & 9\\21 & 10 & 0 & 19 & 18\\5 & 5 & 0 & 9 & 14\\12 & 5 & 0 & 15 & 14\end{bmatrix} \to \begin{bmatrix}3 & 3 & 0 & 4 & 4\\0 & 0 & 0 & 0 & 0\\17 & 8 & 0 & 11 & 9\\1 & 3 & 0 & 1 & 5\\8 & 3 & 0 & 7 & 5\end{bmatrix}\)1M1 1A1 Reducing rows then columns – See special case
\(\begin{bmatrix}2 & 2 & 0 & 3 & 3\\0 & 0 & 1 & 0 & 0\\16 & 7 & 0 & 10 & 8\\0 & 2 & 0 & 0 & 4\\7 & 2 & 0 & 6 & 4\end{bmatrix}\)2M1 2A1ft ft on their previous table
\(\begin{bmatrix}0 & 0 & 0 & 1 & 1\\0 & 0 & 3 & 0 & 0\\14 & 5 & 0 & 8 & 6\\0 & 2 & 2 & 0 & 4\\5 & 0 & 0 & 4 & 2\end{bmatrix}\)3M1 3A1ft 4A1 cso
Allocation: \(A - 1, B - 5, C - 3, D - 4, E - 2\)5A1 = B1 8
(b) Cost is £647B1 Total 9
Notes for question 1:
- a1M1: Reducing rows and then columns – See special case
- a1A1: CAO
- a2M1: Double covered +e; one uncovered – e; and one single covered unchanged. 2 lines needed to 3 lines needed.
- a2A1ft: ft on their previous table.
- a3M1: Double covered +e; one uncovered – e; and one single covered unchanged. 3 lines needed to 5 lines needed. Watch out for 'slow Hungarian' (e.g. 2 'iterations' each subtracting 1), give M0 if seen.
- a3A1ft: ft on their previous table. Condone one 'new' error in table here.
- a4A1: CSO on final table
- a5A1 = B1 CAO
- b1B1: CAO
| Answer/Working | Marks | Guidance |
|---|---|---|
| Reducing rows then columns: $\begin{bmatrix}7 & 5 & 0 & 12 & 13\\4 & 2 & 0 & 8 & 9\\21 & 10 & 0 & 19 & 18\\5 & 5 & 0 & 9 & 14\\12 & 5 & 0 & 15 & 14\end{bmatrix} \to \begin{bmatrix}3 & 3 & 0 & 4 & 4\\0 & 0 & 0 & 0 & 0\\17 & 8 & 0 & 11 & 9\\1 & 3 & 0 & 1 & 5\\8 & 3 & 0 & 7 & 5\end{bmatrix}$ | 1M1 1A1 | Reducing rows then columns – See special case |
| $\begin{bmatrix}2 & 2 & 0 & 3 & 3\\0 & 0 & 1 & 0 & 0\\16 & 7 & 0 & 10 & 8\\0 & 2 & 0 & 0 & 4\\7 & 2 & 0 & 6 & 4\end{bmatrix}$ | 2M1 2A1ft | ft on their previous table |
| $\begin{bmatrix}0 & 0 & 0 & 1 & 1\\0 & 0 & 3 & 0 & 0\\14 & 5 & 0 & 8 & 6\\0 & 2 & 2 & 0 & 4\\5 & 0 & 0 & 4 & 2\end{bmatrix}$ | 3M1 3A1ft 4A1 cso | |
| Allocation: $A - 1, B - 5, C - 3, D - 4, E - 2$ | 5A1 = B1 8 | |
| **(b)** Cost is £647 | B1 | **Total 9** |

**Notes for question 1:**
- a1M1: Reducing rows and then columns – See special case
- a1A1: CAO
- a2M1: Double covered +e; one uncovered – e; and one single covered unchanged. 2 lines needed to 3 lines needed.
- a2A1ft: ft on their previous table.
- a3M1: Double covered +e; one uncovered – e; and one single covered unchanged. 3 lines needed to 5 lines needed. Watch out for 'slow Hungarian' (e.g. 2 'iterations' each subtracting 1), give M0 if seen.
- a3A1ft: ft on their previous table. Condone one 'new' error in table here.
- a4A1: CSO on final table
- a5A1 = B1 CAO
- b1B1: CAO

---
\begin{enumerate}
  \item Five workers, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }$ and E , are to be assigned to five tasks, $1,2,3,4$ and 5 . Each worker is to be assigned to one task and each task must be assigned to one worker.
\end{enumerate}

The cost, in pounds, of assigning each person to each task is shown in the table below. The cost is to be minimised.

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & 1 & 2 & 3 & 4 & 5 \\
\hline
A & 129 & 127 & 122 & 134 & 135 \\
\hline
B & 127 & 125 & 123 & 131 & 132 \\
\hline
C & 142 & 131 & 121 & 140 & 139 \\
\hline
D & 127 & 127 & 122 & 131 & 136 \\
\hline
E & 141 & 134 & 129 & 144 & 143 \\
\hline
\end{tabular}
\end{center}

(a) Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the cost. You must make your method clear and show the table after each stage.\\
(b) Find the minimum cost.\\

\hfill \mbox{\textit{Edexcel D2 2012 Q1 [9]}}
This paper (8 questions)
View full paper
Q1 9 Q2 7 Q3 12 Q4 8 Q5 9 Q6 11 Q7 7 Q8 12