| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2006 |
| Session | June |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Transportation problem: north-west corner |
| Difficulty | Moderate -0.5 This is a standard D2 transportation problem requiring routine application of taught algorithms (north-west corner method and stepping-stone method). Parts (a) and (b) test basic definitions, part (c) is mechanical application of a simple algorithm, and part (d) follows a structured procedure with clear steps. While lengthy (10 marks), it requires no novel insight—just careful execution of standard techniques taught in the module. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| 1 | 2 | Supply | |
| \(A\) | 62 | 47 | 15 |
| \(B\) | 61 | 48 | 12 |
| \(C\) | 68 | 58 | 17 |
| Demand | 16 | 11 |
| 1 | 2 | 3 | |
| \(A\) | |||
| \(B\) | 0 | ||
| \(C\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Either e.g. In an \(n \times m\) problem, a degenerate solution occurs when the number of cells used is less than \((n + m – 1)\) or e.g. when all the demand for one destination is satisfied by all the supply from a source, before the final demand and supplies are allocated, B2 cao, B1 close "bod" is B1 | B2,1,0 | 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: If the total supply > total demand a dummy is used to absorb the excess, B1 cao must (cannot decipher copy properly) | B1 | 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: \(\begin{bmatrix} 15 \\ 1 & 11 & 0 \\ & & 17 \end{bmatrix}\), B1 cao total of five numbers | B1 | 1 |
| Answer | Marks | Guidance |
|---|---|---|
| ⊕ A | 15–θ | 0 |
| ⊖ B | 1+θ | 11–θ |
| ⊕ C | ||
| Entering A2, exiting B2, \(\theta = 0\) | M1 A1 A1ft | 3 |
| Answer | Marks | Guidance |
|---|---|---|
| ⊕ A | 4–θ | 11 |
| ⊖ B | 12+θ | |
| ⊖ C | ||
| Entering A3, exiting B3, \(\theta = 0\) | M1 A1 A1ft | 3 |
| Answer | Marks | Guidance |
|---|---|---|
| ⊕ A | 4 | 11 |
| ⊕ B | 12 | |
| ⊖ C | ||
| Shadow costs: \(S_A = 0\), \(S_B = -1\), \(S_C = 0\); \(D_1 = 62\), \(D_2 = 47\), \(D_3 = 0\) | M1 A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Cost 1497 units | B1 | 4 |
## Part (a)
**Answer:** Either e.g. In an $n \times m$ problem, a degenerate solution occurs when the number of cells used is less than $(n + m – 1)$ or e.g. when all the demand for one destination is satisfied by all the supply from a source, before the final demand and supplies are allocated, B2 cao, B1 close "bod" is B1 | B2,1,0 | 2
## Part (b)
**Answer:** If the total supply > total demand a dummy is used to absorb the excess, B1 cao must (cannot decipher copy properly) | B1 | 1
## Part (c)
**Answer:** $\begin{bmatrix} 15 \\ 1 & 11 & 0 \\ & & 17 \end{bmatrix}$, B1 cao total of five numbers | B1 | 1
## Part (d)
**Answer:** Shadow costs: $S_A = 0$, $S_B = -1$, $S_C = -1$; $D_1 = 62$, $D_2 = 49$, $D_3 = 1$
Improvement indices: $I_{A2} = 47 – 0 – 49 = -2^*$, $I_{A3} = 0 – 0 – 1 = -1$, $I_{C1} = 68 + 1 – 62 = 7$, $I_{C2} = 58 + 1 – 49 = 10$
| | | | |
|---|---|---|---|
| ⊕ A | 15–θ | 0 | | |
| ⊖ B | 1+θ | 11–θ | 0 | |
| ⊕ C | | | 17 | |
Entering A2, exiting B2, $\theta = 0$ | M1 A1 A1ft | 3
Shadow costs: $S_A = 0$, $S_B = -1$, $S_C = -1$; $D_1 = 62$, $D_2 = 47$, $D_3 = 1$
Improvement indices: $I_{A3} = 0 – 0 – 1 = -1^*$, $I_{B2} = 48 + 1 – 47 = 2$, $I_{C1} = 68 + 1 – 62 = 7$, $I_{C2} = 58 + 1 – 47 = 12$
| | | | |
|---|---|---|---|
| ⊕ A | 4–θ | 11 | 0 | |
| ⊖ B | 12+θ | | 0–θ | |
| ⊖ C | | | 17 | |
Entering A3, exiting B3, $\theta = 0$ | M1 A1 A1ft | 3
| | | | |
|---|---|---|---|
| ⊕ A | 4 | 11 | 0 | |
| ⊕ B | 12 | | | |
| ⊖ C | | | 17 | |
Shadow costs: $S_A = 0$, $S_B = -1$, $S_C = 0$; $D_1 = 62$, $D_2 = 47$, $D_3 = 0$ | M1 A1 |
Improvement indices: $I_{B2} = 48 + 1 – 47 = 2$, $I_{B3} = 0 + 1 – 0 = 1$, $I_{C1} = 68 – 0 – 62 = 6$ B1, $I_{C2} = 58 – 0 – 47 = 11$
$\therefore$ Optimal
Cost 1497 units | B1 | 4
---\begin{enumerate}[label=(\alph*)]
\item Explain briefly the circumstances under which a \textbf{degenerate} feasible solution may occur to a transportation problem. [2]
\item Explain why a dummy location may be needed when solving a transportation problem. [1]
\end{enumerate}
The table below shows the cost of transporting one unit of stock from each of three supply points $A$, $B$ and $C$ to each of two demand points 1 and 2. It also shows the stock held at each supply point and the stock required at each demand point.
\begin{tabular}{|c|c|c|c|}
\hline
& 1 & 2 & Supply \\
\hline
$A$ & 62 & 47 & 15 \\
\hline
$B$ & 61 & 48 & 12 \\
\hline
$C$ & 68 & 58 & 17 \\
\hline
Demand & 16 & 11 & \\
\hline
\end{tabular}
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{2}
\item Complete the table below to show a possible initial feasible solution generated by the north-west corner method.
\begin{tabular}{|c|c|c|c|}
\hline
& 1 & 2 & 3 \\
\hline
$A$ & & & \\
\hline
$B$ & & & 0 \\
\hline
$C$ & & & \\
\hline
\end{tabular}
[1]
\item Use the stepping-stone method to obtain an optimal solution and state its cost. You should make your method clear by stating shadow costs, improvement indices, stepping-stone route, and the entering and exiting squares at each stage. [10]
\end{enumerate}
(Total 14 marks)
\hfill \mbox{\textit{Edexcel D2 2006 Q6 [14]}}