| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2017 |
| 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 forbidden assignments). It's mechanical application of a standard template with no problem-solving or optimization required. |
| Spec | 7.06a LP formulation: variables, constraints, objective function |
| 1 | 2 | 3 | 4 | |
| A | 53 | 84 | - | 20 |
| B | 87 | 72 | 41 | 38 |
| C | 70 | 51 | 52 | 25 |
| D | 45 | - | 81 | 70 |
| Answer | Marks |
|---|---|
| B1 | |
| B1 | |
| M1 A1 | |
| M1 A1 A1 |
| B1
| B1
| M1 A1
| M1 A1 A1
**Notes for Question 4:**
- **1B1:** Possible values of $x_{ij}$ (not just x) defined. Must be clear that $x_{ij}$ can take only the two values of 0 and 1 and 1 must be attributed to the worker doing the task (i and j do not need to be mentioned here) and 0 otherwise
- **2B1:** Defining the set of values for i and j – {} not required – this mark is not dependent on the first B mark
- **1M1:** Attempt at a '16' term expression, coefficients 'correct', 2 'large' values (must be at least 88) included, condone 2 slips (a slip here is an x missing from a term, an incorrect coefficient, ij confused in a single term or a missing/extra term)
- **1A1:** CAO + minimise
- **2M1:** Four equations with four variable terms, unit coefficients, = 1, allow x missing and ij confused but not using $x_{11}$ etc.
- **2A1:** Any four equations CAO
- **3A1:** All eight equations only CAO (ignore mention of $x_{ij} \geq 0$)
---4. Four workers, $\mathrm { A } , \mathrm { B } , \mathrm { C }$ and D , are to be assigned to four tasks, $1,2,3$ and 4 . Each worker must be assigned to only one task and each task must be done by only one worker.
Worker A cannot do task 3 and worker D cannot do task 2\\
The cost, in pounds, of assigning each worker to each task is shown in the table below.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 \\
\hline
A & 53 & 84 & - & 20 \\
\hline
B & 87 & 72 & 41 & 38 \\
\hline
C & 70 & 51 & 52 & 25 \\
\hline
D & 45 & - & 81 & 70 \\
\hline
\end{tabular}
\end{center}
The total cost is to be minimised.\\
Formulate the above situation as a linear programming problem. You must define your decision variables and make the objective function and constraints clear.
You do not need to solve this problem.\\
\hfill \mbox{\textit{Edexcel D2 2017 Q4 [7]}}