| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2012 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Transportation problem: stepping-stone method |
| Difficulty | Moderate -0.5 This is a standard algorithmic application of the stepping-stone method with clear instructions. Students follow a mechanical procedure: calculate shadow costs, find improvement indices, identify the loop, and perform iterations. While it requires careful bookkeeping and multiple steps, it's a routine textbook exercise with no conceptual insight or problem-solving required—just methodical execution of a learned algorithm. |
| Spec | 7.06d Graphical solution: feasible region, two variables |
| D | E | F | G | Supply | |
| A | 17 | 19 | 21 | 20 | 18 |
| B | 21 | 20 | 19 | 22 | 23 |
| C | 18 | 17 | 16 | 21 | 29 |
| Demand | 15 | 24 | 18 | 13 |
| D | E | F | G | Supply | |
| A | 15 | 3 | 18 | ||
| B | 21 | 2 | 23 | ||
| C | 16 | 13 | 29 | ||
| Demand | 15 | 24 | 18 | 13 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Shadow costs: Initial table with exiting square BF, \(\theta = 2\) | 1M1 1A1 | a1M1: A valid route, AG used as the empty square, 0's balance. IF AG not used mark as a misread. a1A1: A correct route, correctly stating exiting cell, up to my improved solution with no extra zeros. |
| \(\begin{array}{c\ | ccccc} & D & E & F & G & \text{Supply} \\ 0 & A & 15 & 1 & & 2 & 18 \\ 1 & B & & 23 & & & 23 \\ 1 & C & & & 18 & 11 & 29 \\ \hline \text{Demand} & 15 & 24 & 18 & 13 & 70 \end{array}\) | 2M1 2A1 |
| Improvement indices: \(AF = 21 - 0 - 15 = 6\), \(BG = 22 - 1 - 20 = 1\), \(BD = 21 - 1 - 17 = 3\), \(BF = 19 - 1 - 15 = 3\), \(CD = 18 - 1 - 17 = 0\), \(CE = 17 - 1 - 19 = -3\) | 3A1 | a3A1: Improvement indices CAO |
| Entering square CE. New table: \(\begin{array}{c\ | ccccc} & D & E & F & G & \text{Supply} \\ A & 15 & 1-0 & & 2+0 & 18 \\ B & & & 23 & & 23 \\ C & & 0 & 18 & 11-0 & 29 \\ \hline \text{Demand} & 15 & 24 & 18 & 13 & 70 \end{array}\) | 3M1 4A1ft |
| Exiting square is AE, \(\theta = 1\). Final table: \(\begin{array}{c\ | ccccc} & D & E & F & G & \text{Supply} \\ A & 15 & & & 3 & 18 \\ B & & & 23 & & 23 \\ C & & 1 & 18 & 10 & 29 \\ \hline \text{Demand} & 15 & 24 & 18 & 13 & 70 \end{array}\) | 5A1 cso |
| Total 8 |
| Answer/Working | Marks | Guidance |
|---|---|---|
| Shadow costs: Initial table with exiting square BF, $\theta = 2$ | 1M1 1A1 | a1M1: A valid route, AG used as the empty square, 0's balance. IF AG not used mark as a misread. a1A1: A correct route, correctly stating exiting cell, up to my improved solution with no extra zeros. |
| $\begin{array}{c\|ccccc} & D & E & F & G & \text{Supply} \\ 0 & A & 15 & 1 & & 2 & 18 \\ 1 & B & & 23 & & & 23 \\ 1 & C & & & 18 & 11 & 29 \\ \hline \text{Demand} & 15 & 24 & 18 & 13 & 70 \end{array}$ | 2M1 2A1 | a2M1: Finding 7 shadow costs and 6 IIs. a2A1: Shadow costs CAO [Alt: A(17), B(18), C(18), D(0), E(2), F(-2), G(3)] |
| Improvement indices: $AF = 21 - 0 - 15 = 6$, $BG = 22 - 1 - 20 = 1$, $BD = 21 - 1 - 17 = 3$, $BF = 19 - 1 - 15 = 3$, $CD = 18 - 1 - 17 = 0$, $CE = 17 - 1 - 19 = -3$ | 3A1 | a3A1: Improvement indices CAO |
| Entering square CE. New table: $\begin{array}{c\|ccccc} & D & E & F & G & \text{Supply} \\ A & 15 & 1-0 & & 2+0 & 18 \\ B & & & 23 & & 23 \\ C & & 0 & 18 & 11-0 & 29 \\ \hline \text{Demand} & 15 & 24 & 18 & 13 & 70 \end{array}$ | 3M1 4A1ft | a3M1: A valid route, their most negative II chosen, only one empty square used, 0's balance. a4A1ft: A correct route, correctly stating entering cell, exiting cell. |
| Exiting square is AE, $\theta = 1$. Final table: $\begin{array}{c\|ccccc} & D & E & F & G & \text{Supply} \\ A & 15 & & & 3 & 18 \\ B & & & 23 & & 23 \\ C & & 1 & 18 & 10 & 29 \\ \hline \text{Demand} & 15 & 24 & 18 & 13 & 70 \end{array}$ | 5A1 cso | a5A1 cso: CSO, my solution no extra zeros. |
| **Total 8** | | |
**Notes for question 3:**
- Some candidates are starting by confirming that they should use AG as their first entering square. So if the candidate starts by finding initial shadow costs and II's to confirm that AG has the most negative II, ignore this work and start marking from their first route. Do not credit shadow costs and IIs found here.
- a3M1: A valid route, their most negative II chosen, only one empty square used, 0's balance.
- a3A1: Improvement indices CAO
- a4A1ft: A correct route, correctly stating entering cell, exiting cell.
- a5A1: CSO, my solution no extra zeros.
- b1M1: Finding 7 shadow costs and all 6 IIs or at least1 negative II found.
- b1A1: Shadow costs CAO [Alt SC: A(17), B(21), C(18), D(0), E(-1), F(-2), G(3)]
- b2A1: BG = -2 found as an II.
- b3A1ft: CAO + conclusion. If candidates go on to perform a third iteration and determine that it is optimal, please allow this final mark. Must make link between negative II and not optimal.
---3. The table below shows the cost, in pounds, of transporting one tonne of concrete from each of three supply depots, $\mathrm { A } , \mathrm { B }$ and C , to each of four building sites, $\mathrm { D } , \mathrm { E } , \mathrm { F }$ and G . It also shows the number of tonnes that can be supplied from each depot and the number of tonnes required at each building site. A minimum cost solution is required.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
& D & E & F & G & Supply \\
\hline
A & 17 & 19 & 21 & 20 & 18 \\
\hline
B & 21 & 20 & 19 & 22 & 23 \\
\hline
C & 18 & 17 & 16 & 21 & 29 \\
\hline
Demand & 15 & 24 & 18 & 13 & \\
\hline
\end{tabular}
\end{center}
The north-west corner method gives the following possible solution.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
& D & E & F & G & Supply \\
\hline
A & 15 & 3 & & & 18 \\
\hline
B & & 21 & 2 & & 23 \\
\hline
C & & & 16 & 13 & 29 \\
\hline
Demand & 15 & 24 & 18 & 13 & \\
\hline
\end{tabular}
\end{center}
Taking AG as the first entering cell,
\begin{enumerate}[label=(\alph*)]
\item use the stepping stone method twice to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, routes, entering cells and exiting cells.
\item Determine whether your current solution is optimal. Justify your answer.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2012 Q3 [12]}}