| Exam Board | Edexcel |
|---|---|
| Module | FD2 (Further Decision 2) |
| Year | 2021 |
| Session | June |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Linear Programming |
| Type | Transportation problem formulation |
| Difficulty | Moderate -0.3 This is a straightforward formulation exercise requiring students to define binary decision variables, write an objective function summing costs, and state standard assignment constraints plus two additional restrictions. It's mechanical application of a standard technique with no problem-solving or algorithmic work required, making it slightly easier than average. |
| Spec | 7.06a LP formulation: variables, constraints, objective function |
| 1 | 2 | 3 | |
| A | 53 | - | 62 |
| B | 48 | 57 | 59 |
| C | 55 | 63 | 58 |
| D | 69 | 49 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Let \(x_{ij}\) be 0 or 1; \(\begin{cases} 1 & \text{if worker } (i) \text{ does task } (j) \\ 0 & \text{otherwise} \end{cases}\) | B1 | Defining \(x_{ij}\) correctly |
| where \(i \in \{A,B,C,D\}\) and \(j \in \{1,2,3,4\}\) | B1 | Correct definition of values \(i\) and \(j\) can take |
| minimise \(C = 53x_{A1} + \text{'100'}x_{A2} + 62x_{A3} + 48x_{B1} + 57x_{B2} + 59x_{B3}\) \(+55x_{C1} + 63x_{C2} + 58x_{C3} + 69x_{D1} + 49x_{D2} + \text{'100'}x_{D3}\) | M1, A1 | M1: Attempt at 12 term expression, coefficients 'correct', 2 'large' values included, condone 2 slips. A1: cao including 'minimise' |
| Subject to \(\sum x_{Aj}=1, \sum x_{Bj}=1, \sum x_{Cj}=1, \sum x_{Dj}=1\) \(\sum x_{i1}=1, \sum x_{i2}=1, \sum x_{i3}=1, \sum x_{i4}=1\) | M1, A1 | M1: At least four correct equations, each in three or four variables, unit coefficients, equal to 1. A1: cao (all eight equations) |
| Special cases: No dummy column: max B1B0M1A1M0A0 | No 'large' values in A2 and D3: max B1B1M0A0M1A1 | No 'large' values or dummy column: max B1B0M0A0M0A0 |
## Question 1:
| Answer/Working | Marks | Guidance |
|---|---|---|
| Let $x_{ij}$ be 0 or 1; $\begin{cases} 1 & \text{if worker } (i) \text{ does task } (j) \\ 0 & \text{otherwise} \end{cases}$ | B1 | Defining $x_{ij}$ correctly |
| where $i \in \{A,B,C,D\}$ and $j \in \{1,2,3,4\}$ | B1 | Correct definition of values $i$ and $j$ can take |
| minimise $C = 53x_{A1} + \text{'100'}x_{A2} + 62x_{A3} + 48x_{B1} + 57x_{B2} + 59x_{B3}$ $+55x_{C1} + 63x_{C2} + 58x_{C3} + 69x_{D1} + 49x_{D2} + \text{'100'}x_{D3}$ | M1, A1 | M1: Attempt at 12 term expression, coefficients 'correct', 2 'large' values included, condone 2 slips. A1: cao including 'minimise' |
| Subject to $\sum x_{Aj}=1, \sum x_{Bj}=1, \sum x_{Cj}=1, \sum x_{Dj}=1$ $\sum x_{i1}=1, \sum x_{i2}=1, \sum x_{i3}=1, \sum x_{i4}=1$ | M1, A1 | M1: At least four correct equations, each in three or four variables, unit coefficients, equal to 1. A1: cao (all eight equations) |
**Special cases:** No dummy column: max **B1B0M1A1M0A0** | No 'large' values in A2 and D3: max **B1B1M0A0M1A1** | No 'large' values or dummy column: max **B1B0M0A0M0A0**
---\begin{enumerate}
\item Four workers, A, B, C and D, are to be assigned to three tasks, 1, 2 and 3 . Each task must be assigned to just one worker and each worker can do one task only.
\end{enumerate}
Worker A cannot do task 2 and worker D cannot do task 3\\
The cost of assigning each worker to each task is shown in the table below.\\
The total cost is to be minimised.
\begin{center}
\begin{tabular}{ | c | c | c | c | }
\hline
& 1 & 2 & 3 \\
\hline
A & 53 & - & 62 \\
\hline
B & 48 & 57 & 59 \\
\hline
C & 55 & 63 & 58 \\
\hline
D & 69 & 49 & - \\
\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.\\
(6)
\section*{(Total for Question 1 is 6 marks)}
\hfill \mbox{\textit{Edexcel FD2 2021 Q1 [6]}}