| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2014 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Linear programming formulation for assignment |
| Difficulty | Moderate -0.8 This is a straightforward formulation exercise requiring students to define binary decision variables x_ij, write a linear objective function (sum of costs), and state standard assignment constraints (each worker to one task, each task to one worker) plus two simple exclusion constraints. It's mechanical application of a standard template with no problem-solving or optimization required—just translation into mathematical notation. |
| Spec | 7.06a LP formulation: variables, constraints, objective function7.06b Slack variables: converting inequalities to equations |
| 1 | 2 | 3 | 4 | |
| A | 29 | 15 | 32 | 30 |
| B | 34 | 26 | 40 | 32 |
| C | 28 | 27 | 35 | - |
| D | - | 21 | 33 | 31 |
| Answer | Marks | Guidance |
|---|---|---|
| \(B1\) | — | Defining variables fully both 'bits' values and subscripts. Penalise poor variable choice, (AP etc.) here |
| \(M1 A1\) | — | Attempt at a 16 term expression, coefficients 'correct', 2 'large' values included, condone 2 slips |
| \(A1\) | — | CAO + minimise. Penalise reversed subscripts once only per question |
| \(M1\) | — | Four equations, each in four variables, unit coefficients, all 16 variables included, \(= 1\), accept \(\leq 1, \geq 1\) here for this M only |
| \(2A1\) | — | Any 4 CAO |
| \(3M1\) | — | All 8 equations, each in four variables, unit coefficients, all 16 variables included \(= 1\) |
| \(3A1\) | (7) | CAO |
| $B1$ | — | Defining variables fully both 'bits' values and subscripts. Penalise poor variable choice, (AP etc.) here |
| $M1 A1$ | — | Attempt at a 16 term expression, coefficients 'correct', 2 'large' values included, condone 2 slips |
| $A1$ | — | CAO + minimise. Penalise reversed subscripts once only per question |
| $M1$ | — | Four equations, each in four variables, unit coefficients, all 16 variables included, $= 1$, accept $\leq 1, \geq 1$ here for this M only |
| $2A1$ | — | Any 4 CAO |
| $3M1$ | — | All 8 equations, each in four variables, unit coefficients, all 16 variables included $= 1$ |
| $3A1$ | (7) | CAO |
---6. Four workers, A, B, C and D, are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to just one task and each task must be done by just one worker.
Worker C cannot do task 4 and worker D cannot do task 1.
The cost of assigning each worker to each task is shown in the table below. The total cost is to be minimised.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 \\
\hline
A & 29 & 15 & 32 & 30 \\
\hline
B & 34 & 26 & 40 & 32 \\
\hline
C & 28 & 27 & 35 & - \\
\hline
D & - & 21 & 33 & 31 \\
\hline
\end{tabular}
\end{center}
Formulate the above situation as a linear programming problem. You must define your decision variables and make the objective function and constraints clear.\\
\hfill \mbox{\textit{Edexcel D2 2014 Q6 [7]}}