| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2017 |
| 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 north-west corner method and stepping-stone method with clear step-by-step instructions. While it requires careful bookkeeping across multiple parts, it involves routine application of prescribed algorithms rather than problem-solving or insight, making it slightly easier than average. |
| Spec | 7.06f Integer programming: branch-and-bound method7.07f Algebraic interpretation: explain simplex calculations |
| 1 | 2 | 3 | 4 | Supply | |
| A | 15 | 17 | 20 | 11 | 33 |
| B | 12 | 11 | 18 | 21 | 21 |
| C | 18 | 13 | 10 | 16 | 25 |
| Demand | 21 | 17 | 28 | 13 |
| Answer | Marks |
|---|---|
| B1 (1) |
| Answer | Marks |
|---|---|
| M1 A1 (2) |
| Answer | Marks |
|---|---|
| M1 A1 (4) |
| Answer | Marks |
|---|---|
| M1 A1 | |
| Not optimal as there is a negative improvement index (A3) | A1 (3) |
**Part (a):**
| B1 (1)
**Part (b):**
| M1 A1 (2)
**Part (c):**
| M1 A1 (4)
**Part (d):**
| M1 A1
Not optimal as there is a negative improvement index (A3) | A1 (3)
**Notes for Question 2:**
- **a1B1:** CAO
- **b1M1:** A valid route, only one empty square A4 used, $\theta$'s balance – some candidates are verifying that A4 is the entering cell (which is fine). For those that start at an incorrect entering cell then the M marks only are available in subsequent parts (unless recovered to the answers given in the scheme)
- **b1A1:** Correct route, up to an improved solution (six numbers no zeros) – if there is a zero in cell A2 then A0 unless corrected in part (b)
- **c1M1:** Finding 7 shadow costs and 6 improvement indices
- **c1A1:** Shadow costs [AE: A(15), B(28), C(20), I(0), 2(-17), 3(-10), 4(-4)] and improvement indices CAO
- **c2M1:** A valid route, their most negative II chosen, only one empty square used, $\theta$'s balance
- **c2A1:** CSO (for part (c)) – so all previous marks in this part must have been awarded – **including exiting and entering cells stated correctly** (entering is B1 and exiting is C4) – six numbers no zeros
- **d1M1:** Finding 7 shadow costs and all 6 IIs or sufficient number of shadow costs for at least 1 negative II found
- **d1A1:** CAO A3 = -1 as an II from correct working
- **d2A1:** CSO (for part (d)) + not optimal + reason [Alt shadow costs: A(15), B(12), C(4), I(0), 2(-1), 3(6), 4(-4)]
---2. The table shows the cost, in pounds, of transporting one unit of stock from each of three supply points, $\mathrm { A } , \mathrm { B }$ and C , to each of four demand points, $1,2,3$ and 4 . 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 | c | }
\hline
& 1 & 2 & 3 & 4 & Supply \\
\hline
A & 15 & 17 & 20 & 11 & 33 \\
\hline
B & 12 & 11 & 18 & 21 & 21 \\
\hline
C & 18 & 13 & 10 & 16 & 25 \\
\hline
Demand & 21 & 17 & 28 & 13 & \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Use the north-west corner method to obtain an initial solution.\\
(1)
\item Taking A4 as the entering cell, use the stepping-stone method to find an improved solution. Make your route clear.\\
(2)
\item Taking the most negative improvement index to indicate the entering cell, use the stepping-stone method once 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 2017 Q2 [10]}}