| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Linear Programming |
| Type | Transportation problem formulation |
| Difficulty | Moderate -0.8 This is a standard textbook assignment problem requiring straightforward formulation of decision variables (binary variables for each gardener-task pair), a simple linear objective function (minimize total time), and routine constraints (each gardener assigned once, each task completed once). It involves direct translation from the problem statement with no problem-solving insight or computational work required. |
| Spec | 7.06a LP formulation: variables, constraints, objective function |
| \cline { 2 - 4 } \multicolumn{1}{c|}{} | Lawns | Hedgerows | Flower Beds |
| Alan | 4 | 4.5 | 6 |
| Beth | 3 | 4 | 5 |
| Colin | 3.5 | 5 | 6 |
| Answer | Marks | Guidance |
|---|---|---|
| Let \(x_{ij}\) = 1 if gardener \(i\) is assigned to job \(j\), 0 otherwise (where \(i \in \{A, B, C\}\), \(j \in \{L, H, F\}\)) | B1 B1 | B1 for defining binary variables, B1 for full definition |
| Answer | Marks | Guidance |
|---|---|---|
| Minimise \(P = 4x_{AL} + 4.5x_{AH} + 6x_{AF} + 3x_{BL} + 4x_{BH} + 5x_{BF} + 3.5x_{CL} + 5x_{CH} + 6x_{CF}\) | M1 A1 | M1 for attempt at objective function using their variables |
| Answer | Marks | Guidance |
|---|---|---|
| \(x_{AL} + x_{AH} + x_{AF} = 1\) — Alan does exactly one job | B1 | |
| \(x_{BL} + x_{BH} + x_{BF} = 1\) — Beth does exactly one job; \(x_{CL} + x_{CH} + x_{CF} = 1\) — Colin does exactly one job | B1 | |
| \(x_{AL} + x_{BL} + x_{CL} = 1\), \(x_{AH} + x_{BH} + x_{CH} = 1\), \(x_{AF} + x_{BF} + x_{CF} = 1\) — each job done by exactly one gardener | B1 | Award B1 for both row and column constraints explained |
# Question 1:
## Part (a)
| Let $x_{ij}$ = 1 if gardener $i$ is assigned to job $j$, 0 otherwise (where $i \in \{A, B, C\}$, $j \in \{L, H, F\}$) | B1 B1 | B1 for defining binary variables, B1 for full definition |
## Part (b)
| Minimise $P = 4x_{AL} + 4.5x_{AH} + 6x_{AF} + 3x_{BL} + 4x_{BH} + 5x_{BF} + 3.5x_{CL} + 5x_{CH} + 6x_{CF}$ | M1 A1 | M1 for attempt at objective function using their variables |
## Part (c)
| $x_{AL} + x_{AH} + x_{AF} = 1$ — Alan does exactly one job | B1 | |
| $x_{BL} + x_{BH} + x_{BF} = 1$ — Beth does exactly one job; $x_{CL} + x_{CH} + x_{CF} = 1$ — Colin does exactly one job | B1 | |
| $x_{AL} + x_{BL} + x_{CL} = 1$, $x_{AH} + x_{BH} + x_{CH} = 1$, $x_{AF} + x_{BF} + x_{CF} = 1$ — each job done by exactly one gardener | B1 | Award B1 for both row and column constraints explained |
---\begin{enumerate}
\item A team of gardeners is called in to attend to the grounds of a stately home. The three gardeners will each be assigned to one of three areas, the lawns, the hedgerows and the flower beds. The table below shows the estimated time, in hours, it will take each gardener to do each job.
\end{enumerate}
\begin{center}
\begin{tabular}{ | c | c | c | c | }
\cline { 2 - 4 }
\multicolumn{1}{c|}{} & Lawns & Hedgerows & Flower Beds \\
\hline
Alan & 4 & 4.5 & 6 \\
\hline
Beth & 3 & 4 & 5 \\
\hline
Colin & 3.5 & 5 & 6 \\
\hline
\end{tabular}
\end{center}
The team wishes to complete the tasks in the least total time.\\
Formulate this information as a linear programming problem.\\
(a) State your decision variables.\\
(b) Write down the objective function in terms of your decision variables.\\
(c) Write down the constraints and explain what each one represents.\\
\hfill \mbox{\textit{Edexcel D2 Q1 [7]}}