| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2013 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Transportation problem: stepping-stone method |
| Difficulty | Moderate -0.3 This is a standard algorithmic question testing the stepping-stone method for transportation problems. While it requires careful bookkeeping across multiple iterations, it follows a mechanical procedure taught directly in D2 with no novel problem-solving or insight required. The north-west corner method and stepping-stone algorithm are routine applications, making this slightly easier than average A-level difficulty. |
| Spec | 7.06a LP formulation: variables, constraints, objective function7.06b Slack variables: converting inequalities to equations7.06c Working with constraints: algebra and ad hoc methods7.06d Graphical solution: feasible region, two variables |
| 1 | 2 | 3 | Supply | |
| A | 10 | 11 | 20 | 18 |
| B | 15 | 7 | 13 | 14 |
| C | 24 | 15 | 12 | 21 |
| D | 9 | 21 | 18 | 12 |
| Demand | 27 | 18 | 20 |
| Answer | Marks | Guidance |
|---|---|---|
| (a) | 1 | |
| A | 18 | |
| B | 9 | 5 |
| C | 13 | |
| D | ||
| Demand | 27 | 18 |
| (b) | 1 | |
| A | 18 | |
| B | \(9-\theta\) | \(5+\theta\) |
| C | \(13-\theta\) | |
| D | \(\theta\) | |
| (c) Shadow costs table with cells containing X and values | 1M1A1 | (see scheme image) |
| (d) | 1 | |
| A | \(18-\theta\) | \(\theta\) |
| B | 14 | |
| C | \(4-\theta\) | |
| D | \(9+\theta\) |
**(a)** | | 1 | 2 | 3 | Supply |
|---|---|---|---|---|
| A | 18 | | | 18 |
| B | 9 | 5 | | 14 |
| C | | 13 | 8 | 21 |
| D | | | 12 | 12 |
| Demand | 27 | 18 | 20 | 65 | | B1 | (1)
**(b)** | | 1 | 2 | 3 | | | 1 | 2 | 3 |
|---|---|---|---|---|---|---|---|---|
| A | 18 | | | | giving | A | 18 | | |
| B | $9-\theta$ | $5+\theta$ | | | | B | | 14 | |
| C | | $13-\theta$ | $8+\theta$ | | | C | | 4 | 17 |
| D | $\theta$ | | $12-\theta$ | | | D | 9 | | 3 | | M1A1 | (2)
**(c)** Shadow costs table with cells containing X and values | 1M1A1 | (see scheme image)
**(d)** | | 1 | 2 | 3 | | | 1 | 2 | 3 |
|---|---|---|---|---|---|---|---|---|
| A | $18-\theta$ | $\theta$ | | | giving | A | 15 | 3 | |
| B | | 14 | | | | B | | 14 | |
| C | | $4-\theta$ | $17+\theta$ | | | C | | 1 | 20 |
| D | $9+\theta$ | | $3-\theta$ | | | D | 12 | | | | 2M1A1 | (4)
($\theta = 3$) entering cell A2, exiting cell D3
---2. The table shows the cost, in pounds, of transporting one unit of stock from each of four supply points, $\mathrm { A } , \mathrm { B } , \mathrm { C }$ and D , to each of three demand points, 1, 2 and 3 . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & Supply \\
\hline
A & 10 & 11 & 20 & 18 \\
\hline
B & 15 & 7 & 13 & 14 \\
\hline
C & 24 & 15 & 12 & 21 \\
\hline
D & 9 & 21 & 18 & 12 \\
\hline
Demand & 27 & 18 & 20 & \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Use the north-west corner method to obtain an initial solution.\\
(1)
\item Taking D1 as the entering cell, use the stepping stone method to find an improved solution. Make your route clear.\\
(2)
\item Perform one further iteration of the stepping stone method to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, route, entering cell and exiting cell.
\item Determine whether your current solution is optimal, giving a reason for your answer.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2013 Q2 [10]}}