| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2012 |
| 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 standard textbook formulation exercise requiring students to define binary decision variables x_ij, write a minimization objective function summing costs, and state the assignment constraints (each worker to one task, each task to one worker). It's purely mechanical with no problem-solving or insight required, making it easier than average, though the bookkeeping of 16 variables and 8 constraints requires care. |
| Spec | 7.06a LP formulation: variables, constraints, objective function |
| P | Q | R | S | |
| A | 23 | 41 | 34 | 44 |
| B | 21 | 45 | 33 | 42 |
| C | 26 | 43 | 31 | 40 |
| D | 20 | 47 | 35 | 46 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Let \(x_{ij}\) be 0 or 1: \(1\) if worker (\(i\)) does task (\(j\)), \(0\) otherwise where \(i \in \{A, B, C, D\}\) and \(j \in \{P, Q, R, S\}\) | B1 | |
| Minimise \(P = 23x_{AP} + 41x_{AQ} + 34x_{AR} + 44x_{AS} + 21x_{BP} + 45x_{BQ} + 33x_{BR} + 42x_{BS} + 26x_{CP} + 43x_{CQ} + 31x_{CR} + 40x_{CS} + 20x_{DP} + 47x_{DQ} + 35x_{DR} + 46x_{DS}\) | 1M1 1A1 | |
| Subject to: \(x_{AP} + x_{AQ} + x_{AR} + x_{AS} = 1\) or \(\sum x_{AJ} = 1\) | 2M1 | |
| \(x_{BP} + x_{BQ} + x_{BR} + x_{BS} = 1\) or \(\sum x_{BJ} = 1\) | 2A1 | |
| \(x_{CP} + x_{CQ} + x_{CR} + x_{CS} = 1\) or \(\sum x_{CJ} = 1\) | 3M1 | |
| \(x_{DP} + x_{DQ} + x_{DR} + x_{DS} = 1\) or \(\sum x_{DJ} = 1\) | ||
| \(x_{AP} + x_{BP} + x_{CP} + x_{DP} = 1\) or \(\sum x_{iP} = 1\) | 3A1 | 7 |
| \(x_{AQ} + x_{BQ} + x_{CQ} + x_{DQ} = 1\) or \(\sum x_{iQ} = 1\) | Total 7 | |
| \(x_{AR} + x_{BR} + x_{CR} + x_{DR} = 1\) or \(\sum x_{iR} = 1\) | ||
| \(x_{AS} + x_{BS} + x_{CS} + x_{DS} = 1\) or \(\sum x_{iS} = 1\) |
| Answer/Working | Marks | Guidance |
|---|---|---|
| Let $x_{ij}$ be 0 or 1: $1$ if worker ($i$) does task ($j$), $0$ otherwise where $i \in \{A, B, C, D\}$ and $j \in \{P, Q, R, S\}$ | B1 | |
| Minimise $P = 23x_{AP} + 41x_{AQ} + 34x_{AR} + 44x_{AS} + 21x_{BP} + 45x_{BQ} + 33x_{BR} + 42x_{BS} + 26x_{CP} + 43x_{CQ} + 31x_{CR} + 40x_{CS} + 20x_{DP} + 47x_{DQ} + 35x_{DR} + 46x_{DS}$ | 1M1 1A1 | |
| Subject to: $x_{AP} + x_{AQ} + x_{AR} + x_{AS} = 1$ or $\sum x_{AJ} = 1$ | 2M1 | |
| $x_{BP} + x_{BQ} + x_{BR} + x_{BS} = 1$ or $\sum x_{BJ} = 1$ | 2A1 | |
| $x_{CP} + x_{CQ} + x_{CR} + x_{CS} = 1$ or $\sum x_{CJ} = 1$ | 3M1 | |
| $x_{DP} + x_{DQ} + x_{DR} + x_{DS} = 1$ or $\sum x_{DJ} = 1$ | | |
| $x_{AP} + x_{BP} + x_{CP} + x_{DP} = 1$ or $\sum x_{iP} = 1$ | 3A1 | **7** |
| $x_{AQ} + x_{BQ} + x_{CQ} + x_{DQ} = 1$ or $\sum x_{iQ} = 1$ | | **Total 7** |
| $x_{AR} + x_{BR} + x_{CR} + x_{DR} = 1$ or $\sum x_{iR} = 1$ | | |
| $x_{AS} + x_{BS} + x_{CS} + x_{DS} = 1$ or $\sum x_{iS} = 1$ | | |
**Notes for question 7:**
- 1B1: Defining variables fully both 'bits' values and subscripts. Penalise poor variable choice, (AP etc.) here.
- 1M1: Attempt at a 16 term expression, coefficients 'correct', but condone 2 slips.
- 1A1: CAO + minimise. Penalise reversed subscripts once only per question.
- 2M1: Four eqns, each in four vars, coeffs of 1, all 16 vars included, = 1, accept ≤1,≥ 1 here for this M only
- 2A1: Any 4 CAO. Penalise reversed subscripts once only per question.
- 3M1: All 8 equations, each in four variables, unitary coefficients, all 16 variables included = 1.
- 3A1: CAO. Penalise reversed subscripts once only per question.
---7. Four workers, A, B, C and D, are to be assigned to four tasks, P, Q, R and S. Each worker is to be assigned to exactly one task and each task must be assigned to just one worker. The cost, in pounds, of using each worker for each task is given in the table below. The total cost is to be minimised.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
& P & Q & R & S \\
\hline
A & 23 & 41 & 34 & 44 \\
\hline
B & 21 & 45 & 33 & 42 \\
\hline
C & 26 & 43 & 31 & 40 \\
\hline
D & 20 & 47 & 35 & 46 \\
\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.\\
(Total 7 marks)\\
\hfill \mbox{\textit{Edexcel D2 2012 Q7 [7]}}