| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2011 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Linear programming formulation for assignment |
| Difficulty | Moderate -0.3 This is a standard D2 assignment problem requiring routine formulation of LP constraints and a textbook transformation for the Hungarian algorithm. Part (a) follows a template structure (define 9 binary variables, write objective function, add row/column constraints), and part (b) requires the standard trick of subtracting from the maximum value. While it requires careful notation and systematic thinking, it involves no problem-solving insight beyond applying learned procedures, making it slightly easier than average. |
| Spec | 7.06a LP formulation: variables, constraints, objective function7.07a Simplex tableau: initial setup in standard format |
| Task A | Task B | Task C | |
| Worker P | 27 | 31 | 25 |
| Worker Q | 26 | 30 | 34 |
| Worker R | 35 | 29 | 32 |
| Task A | Task B | Task C | |
| Worker P | 33 | 37 | 31 |
| Worker Q | 32 | 36 | 40 |
| Worker R | 41 | 35 | 38 |
# Question 6: Assignment Problem
## (a) Formulate as Linear Programming Problem
**Marks: (7)**
**B1** for defining decision variables: $x_{ij} = 1$ if worker $i$ assigned to task $j$, else $0$ (for $i \in \{P, Q, R\}$, $j \in \{A, B, C\}$)
**B1** for objective function: minimise $27x_{PA} + 31x_{PB} + 25x_{PC} + 26x_{QA} + 30x_{QB} + 34x_{QC} + 35x_{RA} + 29x_{RB} + 32x_{RC}$
**B1** for each worker constraint: $x_{PA} + x_{PB} + x_{PC} = 1$ (and similar for $Q$ and $R$)
**B1** for each task constraint: $x_{PA} + x_{QA} + x_{RA} = 1$ (and similar for $B$ and $C$)
**B1** for binary constraints: $x_{ij} \in \{0, 1\}$ for all $i, j$
**B1** for clarity of notation and presentation
**B1** for complete and correct formulation
---
## (b) Modify Table for Hungarian Algorithm
**Marks: (2)**
**B1** for subtracting all entries from maximum value (41): new table has entries $41 - \text{original value}$
**B1** for correctly showing modified table with all non-negative entries where maximum profit values become minimum cost values for algorithm application
---6. Three workers, $\mathrm { P } , \mathrm { Q }$ and R , are to be assigned to three tasks, A, B and C. Each worker must be assigned to just one task and each task must be assigned to just one worker.\\
Table 1 shows the cost of using each worker for each task. The total cost is to be minimised.
\begin{table}[h]
\begin{center}
\begin{tabular}{ | c | c | c | c | }
\hline
& Task A & Task B & Task C \\
\hline
Worker P & 27 & 31 & 25 \\
\hline
Worker Q & 26 & 30 & 34 \\
\hline
Worker R & 35 & 29 & 32 \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Table 1}
\end{center}
\end{table}
\begin{enumerate}[label=(\alph*)]
\item Formulate the above situation as a linear programming problem. You must define your decision variables and make the objective and constraints clear.\\
You are not required to solve the problem.
Table 2 shows the profit gained by using each worker for each task. The total profit is to be maximised.
\begin{table}[h]
\begin{center}
\begin{tabular}{ | c | c | c | c | }
\hline
& Task A & Task B & Task C \\
\hline
Worker P & 33 & 37 & 31 \\
\hline
Worker Q & 32 & 36 & 40 \\
\hline
Worker R & 41 & 35 & 38 \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Table 2}
\end{center}
\end{table}
\item Modify Table 2 in the answer book so that the Hungarian Algorithm could be used to find the maximum total profit. You are not required to solve the problem.\\
(2)\\
(Total 9 marks)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2011 Q6 [9]}}