| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2014 |
| Session | June |
| Marks | 7 |
| 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 transportation problem formulation requiring only routine application of a learned template: define 12 decision variables (x_PA, x_PB, etc.), write the cost minimization objective function, and state supply/demand constraints. No problem-solving insight or novel reasoning is required—just careful bookkeeping of a well-practiced procedure. |
| Spec | 7.06a LP formulation: variables, constraints, objective function7.06b Slack variables: converting inequalities to equations |
| A | B | C | D | Supply | |
| \(P\) | 11 | 22 | 13 | 17 | 25 |
| \(Q\) | 21 | 8 | 19 | 14 | 27 |
| \(R\) | 15 | 10 | 9 | 12 | 28 |
| Demand | 18 | 16 | 20 | 26 |
| Answer | Marks | Guidance |
|---|---|---|
| Scheme | Marks | Guidance |
| Let \(x_{ij}\) be the number of washing machines transported from \(i\) to \(j\) where \(i \in \{P,Q,R\}\) and \(j \in \{A,B,C,D\}\) | B1 | 1B1: Variables defined correctly – without this mark if definition of \(x_{ij}\) or the elements of sets \(i\) and \(j\) are inconsistent with their later use in the objective function and constraints. Penalise poor variable choice, (AP etc.) here. |
| The objective is to minimise \(C = 11x_{PA} + 22x_{PB} + 13x_{PC} + 17x_{PD} + 21x_{QA} + 8x_{QB} + 19x_{QC} + 14x_{QD} +15x_{RA} + 10x_{RB} + 9x_{RC} + 12x_{RD}\) | B1 B1 | 2B1: Minimise + an attempt at an objective with at least 5 correct terms. 3B1: Objective function correct (minimised not required for this mark). |
| Subject to \(x_{PA} + x_{PB} + x_{PC} + x_{PD} = 25\) or \(\sum x_{Pj} = 25\) \(x_{QA} + x_{QB} + x_{QC} + x_{QD} = 27\) or \(\sum x_{Qj} = 27\) \(x_{RA} + x_{RB} + x_{RC} + x_{RD} = 28\) or \(\sum x_{Rj} = 28\) \(x_{rA} + x_{QA} + x_{RA} = 18\) or \(\sum x_{iA} = 18\) \(x_{PB} + x_{QB} + x_{RB} = 16\) or \(\sum x_{iB} = 16\) \(x_{PC} + x_{QC} + x_{RC} = 20\) or \(\sum x_{iC} = 20\) \(x_{PD} + x_{QD} + x_{RD} = 26\) or \(\sum x_{iD} = 26\) \(x_{ij} \geq 0\) | M1 A1 A1 A1 | 1M1: At least 3 'correct' constraints listed with unit coefficients (accept = or any inequality for the M mark) – rhs values must be correct. 1A1: At least 3 correct constraints (accept consistent use of = or \(\leq\) on at least 3). 2A1: At least 6 correct constraints (accept consistent use of = or \(\leq\) on at least 6). 3A1: All 8 constraints correct (first seven constraints consistently either = or \(\leq\) but final constraint must be \(\geq 0\)). |
| 7 marks |
| Scheme | Marks | Guidance |
|--------|-------|----------|
| Let $x_{ij}$ be the number of washing machines transported from $i$ to $j$ where $i \in \{P,Q,R\}$ and $j \in \{A,B,C,D\}$ | B1 | 1B1: Variables defined correctly – without this mark if definition of $x_{ij}$ or the elements of sets $i$ and $j$ are inconsistent with their later use in the objective function and constraints. Penalise poor variable choice, (AP etc.) here. |
| The objective is to minimise $C = 11x_{PA} + 22x_{PB} + 13x_{PC} + 17x_{PD} + 21x_{QA} + 8x_{QB} + 19x_{QC} + 14x_{QD} +15x_{RA} + 10x_{RB} + 9x_{RC} + 12x_{RD}$ | B1 B1 | 2B1: Minimise + an attempt at an objective with at least 5 correct terms. 3B1: Objective function correct (minimised not required for this mark). |
| Subject to $x_{PA} + x_{PB} + x_{PC} + x_{PD} = 25$ or $\sum x_{Pj} = 25$ $x_{QA} + x_{QB} + x_{QC} + x_{QD} = 27$ or $\sum x_{Qj} = 27$ $x_{RA} + x_{RB} + x_{RC} + x_{RD} = 28$ or $\sum x_{Rj} = 28$ $x_{rA} + x_{QA} + x_{RA} = 18$ or $\sum x_{iA} = 18$ $x_{PB} + x_{QB} + x_{RB} = 16$ or $\sum x_{iB} = 16$ $x_{PC} + x_{QC} + x_{RC} = 20$ or $\sum x_{iC} = 20$ $x_{PD} + x_{QD} + x_{RD} = 26$ or $\sum x_{iD} = 26$ $x_{ij} \geq 0$ | M1 A1 A1 A1 | 1M1: At least 3 'correct' constraints listed with unit coefficients (accept = or any inequality for the M mark) – rhs values must be correct. 1A1: At least 3 correct constraints (accept consistent use of = or $\leq$ on at least 3). 2A1: At least 6 correct constraints (accept consistent use of = or $\leq$ on at least 6). 3A1: All 8 constraints correct (first seven constraints consistently either = or $\leq$ but final constraint must be $\geq 0$). |
| | **7 marks** | |
---6. Three warehouses, $\mathrm { P } , \mathrm { Q }$ and R , supply washing machines to four retailers, $\mathrm { A } , \mathrm { B } , \mathrm { C }$ and D . The table gives the cost, in pounds, of transporting a washing machine from each warehouse to each retailer. It also shows the number of washing machines held at each warehouse and the number of washing machines required by each retailer. The total cost of transportation is to be minimised.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
& A & B & C & D & Supply \\
\hline
$P$ & 11 & 22 & 13 & 17 & 25 \\
\hline
$Q$ & 21 & 8 & 19 & 14 & 27 \\
\hline
$R$ & 15 & 10 & 9 & 12 & 28 \\
\hline
Demand & 18 & 16 & 20 & 26 & \\
\hline
\end{tabular}
\end{center}
Formulate this transportation problem as a linear programming problem. You must define your decision variables and make the objective function and constraints clear.\\
You do not need to solve this problem.\\
(Total 7 marks)\\
\hfill \mbox{\textit{Edexcel D2 2014 Q6 [7]}}