| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 16 |
| 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 transportation problem using well-defined algorithms (north-west corner rule, stepping-stone method) taught in D2. While it requires careful bookkeeping across multiple steps, the procedures are mechanical and routine for students who have learned the topic. The problem is straightforward with no unusual features or insights required, making it slightly easier than average A-level maths questions which typically involve more problem-solving. |
| Spec | 7.06b Slack variables: converting inequalities to equations7.06c Working with constraints: algebra and ad hoc methods7.06d Graphical solution: feasible region, two variables |
| \cline { 2 - 4 } \multicolumn{1}{c|}{} | \(S _ { 1 }\) | \(S _ { 2 }\) | \(S _ { 3 }\) |
| \(W _ { 1 }\) | 8 | 7 | 11 |
| \(W _ { 2 }\) | 9 | 10 | 11 |
| Answer | Marks |
|---|---|
| NW corner: \(W_1S_1 = 40\), \(W_1S_2 = 5\), \(W_2S_2 = 18\), \(W_2S_3 = 22\) | M1 A1 |
| Cost \(= 40(8)+5(7)+18(10)+22(11) = 320+35+180+242 = 777\) | A1 |
| Answer | Marks |
|---|---|
| Set up shadow costs \(u_i + v_j = c_{ij}\) for used routes | M1 A1 |
| Improvement index for \(W_1S_3 = 11 - u_1 - v_3\) | M1 |
| \(W_1S_3\): index \(= +2\); \(W_2S_1\): index \(= -2\) | A1 A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Enter \(W_2S_1\), stepping-stone loop, \(\theta = \min(18,40) = 18\) | M1 A1 | |
| New solution: \(W_1S_1=22\), \(W_1S_2=23\), \(W_2S_1=18\), \(W_2S_3=22\) | A1 | |
| Recalculate indices; all non-negative → optimal | M1 A1 | |
| Cost \(= 22(8)+23(7)+18(9)+22(11) = 176+161+162+242 = 741\) | A1 A1 | A1 solution, A1 cost |
# Question 5:
## Part (a)
| NW corner: $W_1S_1 = 40$, $W_1S_2 = 5$, $W_2S_2 = 18$, $W_2S_3 = 22$ | M1 A1 | |
| Cost $= 40(8)+5(7)+18(10)+22(11) = 320+35+180+242 = 777$ | A1 | |
## Part (b)
| Set up shadow costs $u_i + v_j = c_{ij}$ for used routes | M1 A1 | |
| Improvement index for $W_1S_3 = 11 - u_1 - v_3$ | M1 | |
| $W_1S_3$: index $= +2$; $W_2S_1$: index $= -2$ | A1 A1 | |
## Part (c)
| Enter $W_2S_1$, stepping-stone loop, $\theta = \min(18,40) = 18$ | M1 A1 | |
| New solution: $W_1S_1=22$, $W_1S_2=23$, $W_2S_1=18$, $W_2S_3=22$ | A1 | |
| Recalculate indices; all non-negative → optimal | M1 A1 | |
| Cost $= 22(8)+23(7)+18(9)+22(11) = 176+161+162+242 = 741$ | A1 A1 | A1 solution, A1 cost |
---5. A carpet manufacturer has two warehouses, $W _ { 1 }$ and $W _ { 2 }$, which supply carpets for three sales outlets, $S _ { 1 } , S _ { 2 }$ and $S _ { 3 }$. At one point $S _ { 1 }$ requires 40 rolls of carpet, $S _ { 2 }$ requires 23 rolls of carpet and $S _ { 3 }$ requires 37 rolls of carpet. At this point $W _ { 1 }$ has 45 rolls in stock and $W _ { 2 }$ has 40 rolls in stock. The following table shows the cost, in pounds, of transporting one roll from each warehouse to each sales outlet:
\begin{center}
\begin{tabular}{ | c | c | c | c | }
\cline { 2 - 4 }
\multicolumn{1}{c|}{} & $S _ { 1 }$ & $S _ { 2 }$ & $S _ { 3 }$ \\
\hline
$W _ { 1 }$ & 8 & 7 & 11 \\
\hline
$W _ { 2 }$ & 9 & 10 & 11 \\
\hline
\end{tabular}
\end{center}
The company's manager wishes to supply the 85 rolls that are in stock such that transportation costs are kept to a minimum.
\begin{enumerate}[label=(\alph*)]
\item Use the north-west corner rule to obtain an initial solution to the problem.
\item Calculate improvement indices for the unused routes.
\item Use the stepping-stone method to obtain an optimal solution.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 Q5 [16]}}