| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Linear programming formulation for assignment |
| Difficulty | Moderate -0.5 This is a standard transportation problem formulation requiring systematic setup of variables, objective function, and constraints from given data. While it involves multiple variables (9 decision variables) and constraints, it follows a completely routine template with no problem-solving insight needed—students simply apply the standard LP formulation pattern taught in D2. |
| Spec | 7.06a LP formulation: variables, constraints, objective function7.06b Slack variables: converting inequalities to equations7.06c Working with constraints: algebra and ad hoc methods |
| \cline { 2 - 4 } \multicolumn{1}{c|}{} | \(D\) | \(E\) | \(F\) |
| \(A\) | 19 | 22 | 13 |
| \(B\) | 18 | 14 | 26 |
| \(C\) | 27 | 16 | 19 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(x_{ij}\) = number of crates sent from warehouse \(i\) to supermarket \(j\), where \(i \in \{A,B,C\}\), \(j \in \{D,E,F\}\) | B1 | Must define all 9 variables clearly |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Minimise \(C = 19x_{AD} + 22x_{AE} + 13x_{AF} + 18x_{BD} + 14x_{BE} + 26x_{BF} + 27x_{CD} + 16x_{CE} + 19x_{CF}\) | M1 A1 | M1 for correct structure, A1 all coefficients correct |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(x_{AD}+x_{AE}+x_{AF} = 42\) (supply at \(A\)) | B1 | Supply constraints |
| \(x_{BD}+x_{BE}+x_{BF} = 26\); \(x_{CD}+x_{CE}+x_{CF} = 32\) | ||
| \(x_{AD}+x_{BD}+x_{CD} = 29\) (demand at \(D\)) | B1 | Demand constraints |
| \(x_{AE}+x_{BE}+x_{CE} = 47\); \(x_{AF}+x_{BF}+x_{CF} = 24\) | ||
| All \(x_{ij} \geq 0\) | B1 | Non-negativity |
# Question 2:
## Part (a):
| Answer | Marks | Guidance |
|--------|-------|----------|
| $x_{ij}$ = number of crates sent from warehouse $i$ to supermarket $j$, where $i \in \{A,B,C\}$, $j \in \{D,E,F\}$ | B1 | Must define all 9 variables clearly |
## Part (b):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Minimise $C = 19x_{AD} + 22x_{AE} + 13x_{AF} + 18x_{BD} + 14x_{BE} + 26x_{BF} + 27x_{CD} + 16x_{CE} + 19x_{CF}$ | M1 A1 | M1 for correct structure, A1 all coefficients correct |
## Part (c):
| Answer | Marks | Guidance |
|--------|-------|----------|
| $x_{AD}+x_{AE}+x_{AF} = 42$ (supply at $A$) | B1 | Supply constraints |
| $x_{BD}+x_{BE}+x_{BF} = 26$; $x_{CD}+x_{CE}+x_{CF} = 32$ | | |
| $x_{AD}+x_{BD}+x_{CD} = 29$ (demand at $D$) | B1 | Demand constraints |
| $x_{AE}+x_{BE}+x_{CE} = 47$; $x_{AF}+x_{BF}+x_{CF} = 24$ | | |
| All $x_{ij} \geq 0$ | B1 | Non-negativity |
---2. A supplier has three warehouses, $A , B$ and $C$, at which there are 42,26 and 32 crates of a particular cereal respectively. Three supermarkets, $D , E$ and $F$, require 29, 47 and 24 crates of the cereal respectively.
The supplier wishes to minimise the cost in meeting the requirements of the supermarkets. The cost, in pounds, of supplying one crate of the cereal from each warehouse to each supermarket is given in the table below.
\begin{center}
\begin{tabular}{ | c | c | c | c | }
\cline { 2 - 4 }
\multicolumn{1}{c|}{} & $D$ & $E$ & $F$ \\
\hline
$A$ & 19 & 22 & 13 \\
\hline
$B$ & 18 & 14 & 26 \\
\hline
$C$ & 27 & 16 & 19 \\
\hline
\end{tabular}
\end{center}
Formulate this information as a linear programming problem.
\begin{enumerate}[label=(\alph*)]
\item State your decision variables.
\item Write down the objective function in terms of your decision variables.
\item Write down the constraints, explaining what each one represents.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 Q2 [6]}}