| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2018 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Transportation problem: stepping-stone method |
| Difficulty | Moderate -0.5 This is a standard textbook application of the stepping-stone method with all steps clearly specified. Students must explain a degeneracy resolution (the zero placement), calculate shadow costs and improvement indices, and identify a stepping-stone route. While it requires understanding of the algorithm, it involves routine mechanical application rather than problem-solving 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 | 24 | 32 | 21 | 34 | 27 |
| B | 28 | 31 | 29 | 37 | 41 |
| C | 25 | 41 | 33 | 35 | 31 |
| D | 23 | 32 | 31 | 36 | 14 |
| Demand | 33 | 35 | 25 | 20 |
| 1 | 2 | 3 | 4 | |
| A | 27 | |||
| B | 6 | 35 | ||
| C | 0 | 25 | 6 | |
| D | 14 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| A zero is placed in C2 because the NW corner method requires \(m + n - 1 = 4 + 4 - 1 = 7\) occupied cells, but only 6 are naturally occupied (degenerate solution) | B1 | Must mention need for 7 cells / degeneracy |
| The zero could have been placed in B3 | B1 | Accept any valid alternative cell that maintains a non-degenerate basis |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Shadow costs: \(R_A = 0\), \(R_B = 4\), \(R_C = 7\), \(R_D = 9\); \(K_1 = 24\), \(K_2 = 27\), \(K_3 = 26\), \(K_4 = 28\) | M1 | Method for finding shadow costs using occupied cells |
| Correct shadow costs | A1 | Allow follow through from table |
| Improvement indices correctly calculated for all unoccupied cells | A1 | e.g. A2: \(32-0-27=5\), A3: \(21-0-26=-5\), A4: \(34-0-28=6\), B3: \(29-4-26=-1\), B4: \(37-4-28=5\), D1: \(23-9-24=-10\), D2: \(32-9-27=-4\), D3: \(31-9-26=-4\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Entering cell: D1 (most negative index \(-10\)) | B1 | Must identify D1 as entering cell |
| Stepping-stone route: D1(+), B1(−), B2(−), C2(+), C4(−), D4... or equivalent valid loop; Exiting cell identified correctly | M1A1 | Route must form a valid closed loop through basic cells |
# Question 1:
## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| A zero is placed in C2 because the NW corner method requires $m + n - 1 = 4 + 4 - 1 = 7$ occupied cells, but only 6 are naturally occupied (degenerate solution) | B1 | Must mention need for 7 cells / degeneracy |
| The zero could have been placed in B3 | B1 | Accept any valid alternative cell that maintains a non-degenerate basis |
## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| Shadow costs: $R_A = 0$, $R_B = 4$, $R_C = 7$, $R_D = 9$; $K_1 = 24$, $K_2 = 27$, $K_3 = 26$, $K_4 = 28$ | M1 | Method for finding shadow costs using occupied cells |
| Correct shadow costs | A1 | Allow follow through from table |
| Improvement indices correctly calculated for all unoccupied cells | A1 | e.g. A2: $32-0-27=5$, A3: $21-0-26=-5$, A4: $34-0-28=6$, B3: $29-4-26=-1$, B4: $37-4-28=5$, D1: $23-9-24=-10$, D2: $32-9-27=-4$, D3: $31-9-26=-4$ |
## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| Entering cell: D1 (most negative index $-10$) | B1 | Must identify D1 as entering cell |
| Stepping-stone route: D1(+), B1(−), B2(−), C2(+), C4(−), D4... or equivalent valid loop; Exiting cell identified correctly | M1A1 | Route must form a valid closed loop through basic cells |
---\begin{enumerate}
\item Table 1 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 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 to this transportation problem is required.
\end{enumerate}
\begin{table}[h]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& 1 & 2 & 3 & 4 & Supply \\
\hline
A & 24 & 32 & 21 & 34 & 27 \\
\hline
B & 28 & 31 & 29 & 37 & 41 \\
\hline
C & 25 & 41 & 33 & 35 & 31 \\
\hline
D & 23 & 32 & 31 & 36 & 14 \\
\hline
Demand & 33 & 35 & 25 & 20 & \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Table 1}
\end{center}
\end{table}
Table 2 shows an initial solution given by the north-west corner method.
\begin{table}[h]
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 \\
\hline
A & 27 & & & \\
\hline
B & 6 & 35 & & \\
\hline
C & & 0 & 25 & 6 \\
\hline
D & & & & 14 \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Table 2}
\end{center}
\end{table}
(a) Explain why a zero has been placed in cell C 2 in Table 2. State the other cell in Table 2 in which the zero could have been placed.\\
(b) State the shadow costs clearly and enter the improvement indices into Table 3 in your answer book.
Taking the most negative improvement index to indicate the entering cell,\\[0pt]
(c) list the stepping-stone route that should be used to obtain the next solution. You should make clear the cells that are included in your route and state your entering and exiting cells. [You do not need to state the next solution. You do not need to solve this problem.]\\
\hfill \mbox{\textit{Edexcel D2 2018 Q1 [7]}}