| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2003 |
| Session | June |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Linear Programming |
| Type | Transportation problem formulation |
| Difficulty | Moderate -0.8 This is a standard textbook transportation problem using well-defined algorithms (North-West corner, shadow costs, stepping-stone method). While it requires multiple steps and careful arithmetic, it involves direct application of memorized procedures with no problem-solving insight or novel thinking required. The small problem size (3×3) makes calculations manageable. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Airport \(D\) | Airport \(E\) | Airport \(F\) | Cars available | |
| Garage \(A\) | £20 | £40 | £10 | 6 |
| Garage \(B\) | £20 | £30 | £40 | 5 |
| Garage C | £10 | £20 | £30 | 8 |
| Cars required | 6 | 9 | 4 |
| Answer | Marks | Guidance |
|---|---|---|
| (a) | e.g. | M1 A1 |
| D | E | F |
| A | 6 | |
| B | 0 | 5 |
| C | 4 |
| Answer | Marks | Guidance |
|---|---|---|
| D | E | F |
| A | 6 | 0 |
| B | ||
| C | 4 | |
| cost £470 | A1 | |
| (b) | \(S_A = 0, S_B = 0, S_C = -10\); \(D_D = 20, D_E = 30, D_F = 40\); \(I_{AE} = 40 - 30 = 10\), \(I_{AF} = 10 - 40 = -30\), \(I_{BF} = 40 - 40 = 0\), \(I_{CD} = 10 - 10 = 0\) (or \(S_A = 0, S_B = -10, S_C = -20\); \(D_D = 20, D_E = 40, D_F = 50\); \(I_{AF} = 10 - 50 = -40\), \(I_{BD} = 20 - 10 = 10\), \(I_{BF} = 40 - 40 = 0\), \(I_{CD} = 10 - 0 = 10\)) | M1 A1 M1 A1 |
| Choose AF as entering route: \(AF(+) \to CF(-) \to CE(+) \to BE(-) \to BD(+) \to AD(-)\). Exiting route CF \(\theta = 4\) (or \(AF(+) \to CF(-) \to CE(+) \to AE(-) \to BD(+) \to AD(-)\). Exiting route AE \(\theta = 0\)) | M1 A1 ft | - |
| D | E | F |
| A | 2 | |
| B | 4 | 1 |
| C | 8 | |
| \(S_A = 0, S_B = 0, S_C = -10\); \(D_D = 20, D_E = 30, D_F = 10\); \(I_{AE} = 10, I_{BF} = 30, I_{CD} = 0, I_{CF} = 30\) ∴ optimal, cost £350 | A1 | 3 |
| (Second option) \(AF(+) \to CF(-) \to CE(+) \to AE(-) \to BD(+) \to AD(-)\). Exiting route AE \(\theta = 0\) | M1 A1 ft | - |
| D | E | F |
| A | 2 | |
| B | 5 | |
| C | 4 | 4 |
| \(S_A = 0, S_B = 30, S_C = 20\); \(D_D = 20, D_E = 0, D_F = 10\); \(I_{AE} = 40, I_{BD} = -30, I_{BF} = 20, I_{CD} = -30\) | M1 A1 A1 | - |
| \(CD(+) \to AD(-) \to AF(+) \to CF(-)\). \(\theta = 4\) | A1 | 7 |
(a) | e.g. | M1 A1 | 3 |
| | D | E | F |
|---|---|---|---|
| A | 6 | | |
| B | 0 | 5 | |
| C | | 4 | 4 |
or
| | D | E | F |
|---|---|---|---|
| A | 6 | 0 | |
| B | | | 5 |
| C | | 4 | 4 |
cost £470 | A1 | |
(b) | $S_A = 0, S_B = 0, S_C = -10$; $D_D = 20, D_E = 30, D_F = 40$; $I_{AE} = 40 - 30 = 10$, $I_{AF} = 10 - 40 = -30$, $I_{BF} = 40 - 40 = 0$, $I_{CD} = 10 - 10 = 0$ (or $S_A = 0, S_B = -10, S_C = -20$; $D_D = 20, D_E = 40, D_F = 50$; $I_{AF} = 10 - 50 = -40$, $I_{BD} = 20 - 10 = 10$, $I_{BF} = 40 - 40 = 0$, $I_{CD} = 10 - 0 = 10$) | M1 A1 M1 A1 | 4 |
Choose AF as entering route: $AF(+) \to CF(-) \to CE(+) \to BE(-) \to BD(+) \to AD(-)$. Exiting route CF $\theta = 4$ (or $AF(+) \to CF(-) \to CE(+) \to AE(-) \to BD(+) \to AD(-)$. Exiting route AE $\theta = 0$) | M1 A1 ft | - |
| | D | E | F |
|---|---|---|---|
| A | 2 | | 4 |
| B | 4 | 1 | |
| C | | 8 | |
$S_A = 0, S_B = 0, S_C = -10$; $D_D = 20, D_E = 30, D_F = 10$; $I_{AE} = 10, I_{BF} = 30, I_{CD} = 0, I_{CF} = 30$ ∴ optimal, cost £350 | A1 | 3 |
(Second option) $AF(+) \to CF(-) \to CE(+) \to AE(-) \to BD(+) \to AD(-)$. Exiting route AE $\theta = 0$ | M1 A1 ft | - |
| | D | E | F |
|---|---|---|---|
| A | 2 | | 4 |
| B | | 5 | |
| C | 4 | 4 | |
$S_A = 0, S_B = 30, S_C = 20$; $D_D = 20, D_E = 0, D_F = 10$; $I_{AE} = 40, I_{BD} = -30, I_{BF} = 20, I_{CD} = -30$ | M1 A1 A1 | - |
$CD(+) \to AD(-) \to AF(+) \to CF(-)$. $\theta = 4$ | A1 | 7 |5. The manager of a car hire firm has to arrange to move cars from three garages $A , B$ and $C$ to three airports $D , E$ and $F$ so that customers can collect them. The table below shows the transportation cost of moving one car from each garage to each airport. It also shows the number of cars available in each garage and the number of cars required at each airport. The total number of cars available is equal to the total number required.
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
& Airport $D$ & Airport $E$ & Airport $F$ & Cars available \\
\hline
Garage $A$ & £20 & £40 & £10 & 6 \\
\hline
Garage $B$ & £20 & £30 & £40 & 5 \\
\hline
Garage C & £10 & £20 & £30 & 8 \\
\hline
Cars required & 6 & 9 & 4 & \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Use the North-West corner rule to obtain a possible pattern of distribution and find its cost.\\
(3)
\item Calculate shadow costs for this pattern and hence obtain improvement indices for each route.
\item Use the stepping-stone method to obtain an optimal solution and state its cost.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2003 Q5 [14]}}