| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2008 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Transportation problem: dummy location |
| Difficulty | Moderate -0.8 This is a standard textbook transportation problem requiring routine application of well-defined algorithms (north-west corner rule, stepping-stone method). While multi-step with 13 marks, it involves mechanical execution of learned procedures rather than problem-solving or insight. The dummy location concept is a basic feature of the transportation algorithm taught in D2. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| London (L) | Edinburgh (E) | Supply | |
| A | 80 | 70 | 55 |
| B | 60 | 50 | 45 |
| Demand | 35 | 60 |
| L | E | Dummy | Supply | |
| A | 80 | 70 | 55 | |
| B | 60 | 50 | 45 | |
| Demand | 35 | 60 | 100 |
| Answer | Marks | Guidance |
|---|---|---|
| (a) Maximax: we seek a route where the shortest arc used is a great as possible. Minimax: we seek a route where the longest arc used is a small as possible. | B2,1,0 | 2 |
| (b) | M1A1 | 2 |
| Stage | State | Action |
| 1 | G | GR |
| H | HR | R |
| I | IR | R |
| D | DG | G |
| DH | H | \(\min(160,175) = 160^*\) |
| 2 | E | EG |
| EH | H | \(\min(144,175) = 144^*\) |
| EI | I | \(\min(102,139) = 102\) |
| F | FH | H |
| FI | I | \(\min(210,139) = 139\) |
| 3 | A | AD |
| AE | E | \(\min(279,144) = 144\) |
| B | BD | D |
| BE | E | \(\min(250,144) = 144^*\) |
| BF | F | \(\min(123,145) = 123\) |
| C | CE | E |
| CF | F | \(\min(170,145) = 145^*\) |
| 4 | L | LA |
| LB | B | \(\min(190,144) = 144\) |
| LC | C | \(\min(148,145) = 145\) |
| Maximax route: LADHR | A1ft | 5 |
**(a)** Maximax: we seek a route where the shortest arc used is a great as possible. Minimax: we seek a route where the longest arc used is a small as possible. | B2,1,0 | 2 |
**(b)** | M1A1 | 2 |
| Stage | State | Action | Dest. | Value |
|-------|-------|--------|-------|-------|
| 1 | G | GR | R | $132^*$ |
| | H | HR | R | $175^*$ |
| | I | IR | R | $139^*$ |
| | D | DG | G | $\min(175,132) = 132$ | M1A1 |
| | | DH | H | $\min(160,175) = 160^*$ |
| 2 | E | EG | G | $\min(162,132) = 132$ | A1 |
| | | EH | H | $\min(144,175) = 144^*$ |
| | | EI | I | $\min(102,139) = 102$ |
| | F | FH | H | $\min(145,175) = 145^*$ |
| | | FI | I | $\min(210,139) = 139$ |
| 3 | A | AD | D | $\min(185,160) = 160^*$ | M1A1ft |
| | | AE | E | $\min(279,144) = 144$ |
| | B | BD | D | $\min(119,160) = 119$ | A1ft |
| | | BE | E | $\min(250,144) = 144^*$ |
| | | BF | F | $\min(123,145) = 123$ |
| | C | CE | E | $\min(240,144) = 144$ |
| | | CF | F | $\min(170,145) = 145^*$ |
| 4 | L | LA | A | $\min(155,160) = 155^*$ | A1ft |
| | | LB | B | $\min(190,144) = 144$ |
| | | LC | C | $\min(148,145) = 145$ |
Maximax route: LADHR | A1ft | 5 |3. Jameson cars are made in two factories A and B. Sales have been made at the two main showrooms in London and Edinburgh. Cars are to be transported from the factories to the showrooms. The table below shows the cost, in pounds, of transporting one car from each factory to each showroom. It also shows the number of cars available at each factory and the number required at each showroom.
\begin{center}
\begin{tabular}{ | c | c | c | c | }
\hline
& London (L) & Edinburgh (E) & Supply \\
\hline
A & 80 & 70 & 55 \\
\hline
B & 60 & 50 & 45 \\
\hline
Demand & 35 & 60 & \\
\hline
\end{tabular}
\end{center}
It is decided to use the transportation algorithm to obtain a minimal cost solution.
\begin{enumerate}[label=(\alph*)]
\item Explain why it is necessary to add a dummy demand point.
\item Complete the table below.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
& L & E & Dummy & Supply \\
\hline
A & 80 & 70 & & 55 \\
\hline
B & 60 & 50 & & 45 \\
\hline
Demand & 35 & 60 & & 100 \\
\hline
\end{tabular}
\end{center}
\item Use the north-west corner rule to obtain a possible pattern of distribution.\\
(1)
\item Taking the most negative improvement index to indicate the entering square, use the stepping-stone method to obtain an optimal solution. You must make your shadow costs and improvement indices clear and demonstrate that your solution is optimal.\\
(7)
\item State the cost of your optimal solution.\\
(1) (Total 13 marks)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2008 Q3 [13]}}