| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2006 |
| Session | June |
| 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 of the assignment problem as a linear programming problem. It requires only direct application of a well-defined algorithm taught in D2 with no problem-solving insight—students define 9 binary variables, write the minimization objective as a sum of costs, and state the standard row/column constraints. The 7 marks reflect the mechanical writing required rather than conceptual difficulty. |
| Spec | 7.06a LP formulation: variables, constraints, objective function |
| Cost (in £100s) | Task 1 | Task 2 | Task 3 |
| Worker \(P\) | 8 | 7 | 3 |
| Worker \(Q\) | 9 | 5 | 6 |
| Worker \(R\) | 10 | 4 | 4 |
Three workers, $P$, $Q$ and $R$, are to be assigned to three tasks, 1, 2 and 3. Each worker is to be assigned to one task and each task must be assigned to one worker. The cost, in hundreds of pounds, of using each worker for each task is given in the table below. The cost is to be minimised.
\begin{tabular}{|c|c|c|c|}
\hline
Cost (in £100s) & Task 1 & Task 2 & Task 3 \\
\hline
Worker $P$ & 8 & 7 & 3 \\
\hline
Worker $Q$ & 9 & 5 & 6 \\
\hline
Worker $R$ & 10 & 4 & 4 \\
\hline
\end{tabular}
Formulate the above situation as a linear programming problem, defining the decision variables and making the objective and constraints clear.
(Total 7 marks)
\hfill \mbox{\textit{Edexcel D2 2006 Q2}}