| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2004 |
| Session | June |
| Marks | 18 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Transportation problem: add dummy |
| Difficulty | Moderate -0.8 This is a standard textbook application of the transportation algorithm with routine procedural steps. Part (a) requires simple recall of a real-world context, part (b) tests understanding of balanced transportation problems, and parts (c)-(e) involve mechanical application of well-defined algorithms (north-west corner rule, shadow costs, stepping-stone method) with no novel problem-solving or insight required. The 16 marks reflect length rather than conceptual difficulty. |
| Spec | 7.03c Working with algorithms: trace, interpret, adapt7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| \(d\) | \(e\) | Supply | |
| \(A\) | 5 | 3 | 45 |
| \(B\) | 4 | 6 | 35 |
| \(C\) | 2 | 4 | 40 |
| Demand | 50 | 60 |
| \(d\) | \(e\) | \(f\) | Supply | |
| \(A\) | 5 | 3 | 45 | |
| \(B\) | 4 | 6 | 35 | |
| \(C\) | 2 | 4 | 40 | |
| Demand | 50 | 60 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Idea of many supply and demand points and many units to be moved. Costs are variable and dependent upon the supply and demand points, need to minimise costs. Practical costs proportional to number of units | B2, 1, 0 | 2 marks |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Supply = 120, Demand = 110 so not balanced | B1 | 1 mark |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Adds 0, 0, 0, 10 to column \(f\) | M1 A1, M1 A1 | |
| d | e | f |
| A | 45 | |
| B | 5 | 30 |
| C | 30 | |
| Cost 545 | B1 ft | 5 marks |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: \(R_1 = 0\), \(R_2 = -1\), \(R_3 = -3\), \(k_1 = 5\), \(k_2 = 7\), \(k_3 = 3\) | M1 A1 | |
| \(Ae = 3 - 0 - 7 = -4\), \(Af = 0 - 0 - 3 = -3\), \(Bf = 0 + 1 - 3 = -2\), \(Cd = 2 + 3 - 5 = 0\) | M1 A1 ft, A1 ft | 5 marks |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: \(Ae^+ \to Bc^- \to Bd^+ \to Ad^-\) send 30 | M1 A1 ft | |
| d | e | f |
| A | 15 | 30 |
| B | 35 | |
| C | 30 | |
| Cost 425 | depM1, A1 ft, A1 | 5 marks |
### (a)
**Answer:** Idea of many supply and demand points and many units to be moved. Costs are variable and dependent upon the supply and demand points, need to minimise costs. Practical costs proportional to number of units | B2, 1, 0 | 2 marks
### (b)
**Answer:** Supply = 120, Demand = 110 so not balanced | B1 | 1 mark
### (c)
**Answer:** Adds 0, 0, 0, 10 to column $f$ | M1 A1, M1 A1 |
| | d | e | f |
|---|---|---|---|
| A | 45 | | |
| B | 5 | 30 | |
| C | | 30 | 10 |
Cost 545 | B1 ft | 5 marks
### (d)
**Answer:** $R_1 = 0$, $R_2 = -1$, $R_3 = -3$, $k_1 = 5$, $k_2 = 7$, $k_3 = 3$ | M1 A1 |
$Ae = 3 - 0 - 7 = -4$, $Af = 0 - 0 - 3 = -3$, $Bf = 0 + 1 - 3 = -2$, $Cd = 2 + 3 - 5 = 0$ | M1 A1 ft, A1 ft | 5 marks
### (e)
**Answer:** $Ae^+ \to Bc^- \to Bd^+ \to Ad^-$ send 30 | M1 A1 ft |
| | d | e | f |
|---|---|---|---|
| A | 15 | 30 | |
| B | 35 | | |
| C | | 30 | 10 |
Cost 425 | depM1, A1 ft, A1 | 5 marks
---\begin{enumerate}[label=(\alph*)]
\item Describe a practical problem that could be solved using the transportation algorithm. [2]
\end{enumerate}
A problem is to be solved using the transportation problem. The costs are shown in the table. The supply is from $A$, $B$ and $C$ and the demand is at $d$ and $e$.
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
& $d$ & $e$ & Supply \\
\hline
$A$ & 5 & 3 & 45 \\
\hline
$B$ & 4 & 6 & 35 \\
\hline
$C$ & 2 & 4 & 40 \\
\hline
Demand & 50 & 60 & \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{1}
\item Explain why it is necessary to add a third demand $f$. [1]
\item Use the north-west corner rule to obtain a possible pattern of distribution and find its cost.
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
& $d$ & $e$ & $f$ & Supply \\
\hline
$A$ & 5 & 3 & & 45 \\
\hline
$B$ & 4 & 6 & & 35 \\
\hline
$C$ & 2 & 4 & & 40 \\
\hline
Demand & 50 & 60 & & \\
\hline
\end{tabular}
\end{center} [5]
\item Calculate shadow costs and improvement indices for this pattern. [5]
\item Use the stepping-stone method once to obtain an improved solution and its cost. [5]
\end{enumerate}
(Total 16 marks)
\hfill \mbox{\textit{Edexcel D2 2004 Q5 [18]}}