| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Topic | Network Flows |
| Type | Transportation problem: north-west corner |
| Difficulty | Standard +0.3 This is a standard transportation problem using the North-West corner method, improvement indices, and stepping-stone algorithm—all routine D2 techniques. While it requires multiple steps and careful arithmetic across four parts, it follows a completely algorithmic procedure with no problem-solving insight needed, making it slightly easier than average for A-level. |
| Spec | 7.03c Working with algorithms: trace, interpret, adapt7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Business | |||
| \(B_1\) | \(B_2\) | \(B_3\) | |
| \(F_1\) | 10 | 4 | 11 |
| Factory \(F_2\) | 12 | 5 | 8 |
| \(F_3\) | 9 | 6 | 7 |
A steel manufacturer has 3 factories $F_1$, $F_2$ and $F_3$ which can produce 35, 25 and 15 kilotomnes of steel per year, respectively. Three businesses $B_1$, $B_2$ and $B_3$ have annual requirements of 20, 25 and 30 kilotomnes respectively. The table below shows the cost $C_{ij}$ in appropriate units, of transporting one kilotome of steel from factory $F_i$ to business $B_j$.
\begin{tabular}{c|ccc}
& & Business & \\
& $B_1$ & $B_2$ & $B_3$ \\
\hline
$F_1$ & 10 & 4 & 11 \\
Factory $F_2$ & 12 & 5 & 8 \\
$F_3$ & 9 & 6 & 7
\end{tabular}
The manufacturer wishes to transport the steel to the businesses at minimum total cost.
\begin{enumerate}[label=(\alph*)]
\item Write down the transportation pattern obtained by using the North-West corner rule. [2]
\item Calculate all of the improvement indices $I_{ij}$ and hence show that this pattern is not optimal. [5]
\item Use the stepping-stone method to obtain an improved solution. [3]
\item Show that the transportation pattern obtained in part (c) is optimal and find its cost. [4]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 Q7 [14]}}