| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2013 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Linear programming formulation for assignment |
| Difficulty | Moderate -0.8 This is a standard textbook assignment problem requiring routine application of the Hungarian algorithm setup and LP formulation. Part (a) involves simple arithmetic (subtracting from row/column maxima), and part (b) requires writing out standard constraints (binary variables, one-to-one assignment) with no novel problem-solving insight needed. |
| Spec | 7.06a LP formulation: variables, constraints, objective function |
| Task 1 | Task 2 | Task 3 | |
| Harriet | 251 | 243 | 257 |
| Jason | 244 | 247 | 255 |
| Katherine | 249 | 252 | 246 |
| Answer | Marks | Guidance |
|---|---|---|
| \(\begin{pmatrix} 9 & 17 & 3 \\ 16 & 13 & 5 \\ 11 & 8 & 14 \end{pmatrix}\) \((n = 257\) \(\begin{bmatrix} 6 & 14 & 0 \\ 13 & 10 & 2 \\ 8 & 5 & 11 \end{bmatrix}\), \(n = 258\) \(\begin{bmatrix} 7 & 15 & 1 \\ 14 & 11 & 3 \\ 9 & 6 & 12 \end{bmatrix})\) | 1B1 | (1) |
| Answer | Marks | Guidance |
|---|---|---|
| b2A1 All six equations CAO (consistent notation required) | 1B1 1B1 2B1 (2) 3B1 4B1 (2) M1 1A1 2A1 (3) | Total 8 |
**(a)** Since maximising subtract all elements from some $n \ge 257$, say 260.
$\begin{pmatrix} 9 & 17 & 3 \\ 16 & 13 & 5 \\ 11 & 8 & 14 \end{pmatrix}$ $(n = 257$ $\begin{bmatrix} 6 & 14 & 0 \\ 13 & 10 & 2 \\ 8 & 5 & 11 \end{bmatrix}$, $n = 258$ $\begin{bmatrix} 7 & 15 & 1 \\ 14 & 11 & 3 \\ 9 & 6 & 12 \end{bmatrix})$ | 1B1 | (1)
**(b)** $x_{ij} = \begin{cases} 1 & \text{if worker } i \text{ does task } j \\ 0 & \text{otherwise} \end{cases}$
Where $x_{ij}$ indicates worker $i$ being assigned to task $j$
$i \in \{H, K, J\}$ and $j \in \{1,2,3\}$
E.g. Minimise
$P = 9x_{H1} + 17x_{H2} + 3x_{H3} + 16x_{J1} + 13x_{J2} + 5x_{J3} + 11x_{K1} + 8x_{K2} + 14x_{K3}$
(or Maximise
$P = 251x_{H1} + 243x_{H2} + 257x_{H3} + 244x_{J1} + 247x_{J2} + 255x_{J3} + 249x_{K1} + 252x_{K2} + 246x_{K3}$)
Subject to:
$x_{H1} + x_{H2} + x_{H3} = 1$ or $\sum x_{Hi} = 1$
$x_{J1} + x_{J2} + x_{J3} = 1$ or $\sum x_{Jj} = 1$
$x_{K1} + x_{K2} + x_{K3} = 1$ or $\sum x_{Ki} = 1$
$x_{H1} + x_{J1} + x_{K1} = 1$ or $\sum x_{i1} = 1$
$x_{H2} + x_{J2} + x_{K2} = 1$ or $\sum x_{i2} = 1$
$x_{H3} + x_{J3} + x_{K3} = 1$ or $\sum x_{i3} = 1$
a1B1 CAO (o.e.)
b1B1 possible values of $x_{ij}$ defined
b2B1 Defining $x_{ij}$ including the set of values for $i$ and $j$
b3B1 Objective function
b4B1 Minimise/Maximise but consistent with objective function
b1M1 Three equations, unit coefficients, =1
b1A1 Any three equations CAO (condone inconsistent notation)
b2A1 All six equations CAO (consistent notation required) | 1B1 1B1 2B1 (2) 3B1 4B1 (2) M1 1A1 2A1 (3) | Total 8
---6. Three workers, Harriet, Jason and Katherine, are to be assigned to three tasks, 1, 2 and 3. Each worker must be assigned to just one task and each task must be done by just one worker.
The amount each person would earn, in pounds, while assigned to each task is shown in the table below.
\begin{center}
\begin{tabular}{ | l | c | c | c | }
\hline
& Task 1 & Task 2 & Task 3 \\
\hline
Harriet & 251 & 243 & 257 \\
\hline
Jason & 244 & 247 & 255 \\
\hline
Katherine & 249 & 252 & 246 \\
\hline
\end{tabular}
\end{center}
The total income is to be maximised.
\begin{enumerate}[label=(\alph*)]
\item Modify the table so it can be used to find the maximum income.
\item Formulate the above situation as a linear programming problem. You must define your decision variables and make your objective function and constraints clear.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2013 Q6 [8]}}