Question 1 - A-Level Maths

Edexcel FD2 2019 June — Question 1 10 marks

Exam Board	Edexcel
Module	FD2 (Further Decision 2)
Year	2019
Session	June
Marks	10
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Network Flows
Type	Transportation problem: stepping-stone method
Difficulty	Challenging +1.2 This is a standard algorithmic application of the stepping-stone method with clear instructions. Students follow a mechanical procedure (given the entering cell in part a, then computing shadow costs and improvement indices in part b). While it requires careful bookkeeping and understanding of the algorithm, it involves no novel problem-solving or insight—just methodical execution of a taught technique from Further Maths Decision 2.
Spec	7.07f Algebraic interpretation: explain simplex calculations

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, \(\mathrm { P } , \mathrm { Q } , \mathrm { R }\) and S . 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{table}[h]

	P	Q	R	S	Supply
A	15	14	17	11	23
B	10	9	16	12	42
C	11	13	8	10	18
D	15	13	16	17	19
Demand	25	45	12	20

\captionsetup{labelformat=empty} \caption{Table 1}

\end{table} Table 2 shows an initial solution given by the north-west corner method. \begin{table}[h]

	P	Q	R	S
A	23
B	2	40
C		5	12	1
D				19

\captionsetup{labelformat=empty} \caption{Table 2}

\end{table}

Taking DQ as the entering cell, use the stepping-stone method to find an improved solution. Make your method clear.
Perform one further iteration of the stepping-stone method to obtain an improved solution. You must make your method clear by stating the
- shadow costs
- improvement indices
- route
- entering cell and exiting cell.
- Determine whether the solution obtained from this second iteration is optimal, giving a reason for your answer.
- State the cost of the solution found in (b).

Show mark scheme Show mark scheme source

Question 1:

Part (a)

Answer	Marks	Guidance
Answer	Marks	Guidance
Valid route using northwest corner method with one empty square, \(\theta\)'s balance. Result: A-P: 23, B-P: 2, B-Q: 40, C-R: 12, C-S: 6, D-Q: 5, D-S: 14	1M1	Valid route, only one empty square used, \(\theta\)'s balance. If not entering in DQ, allow for valid route and entry in CP or DP only
Correct answer as shown	1A1	CAO

(2 marks)

Part (b)

Answer	Marks	Guidance
Answer	Marks	Guidance
Finding exactly 8 shadow costs and exactly 9 improvement indices for improved solution. Shadow costs: A(15), B(10), C(7), D(14), P(0), Q(-1), R(1), S(3)	1M1	1.1b
Shadow costs CAO as listed	1A1	Alt shadow costs listed in notes
Valid route with most negative II chosen, one empty square, \(\theta\)'s balance	2M1	1.1b
CAO including deduction of all entering and exiting cells. Entering cell AS, exiting cell DS	2A1	2.2a

(4 marks)

Part (c)

Answer	Marks	Guidance
Answer	Marks	Guidance
Finding all 8 shadow costs and all 9 negative improvement indices, or sufficient number of shadow costs for at least 1 negative II found	1M1	Dependent on previous M mark in (b)
Negative II (e.g. PC = \(-3\)) identified from correct working	1A1	CAO negative II from correct working
Solution is not optimal because there is a negative improvement index	2A1	CSO for (a),(b),(c) including correct reasoning. Do not allow 'some IIs are not positive'

(3 marks)

Part (d)

Answer	Marks	Guidance
Answer	Marks	Guidance
£1086	1B1	CAO, ignore lack of or incorrect units

(1 mark)

(10 marks total)

# Question 1:

## Part (a)

| Answer | Marks | Guidance |
|--------|-------|----------|
| Valid route using northwest corner method with one empty square, $\theta$'s balance. Result: A-P: 23, B-P: 2, B-Q: 40, C-R: 12, C-S: 6, D-Q: 5, D-S: 14 | 1M1 | Valid route, only one empty square used, $\theta$'s balance. If not entering in DQ, allow for valid route and entry in CP or DP only |
| Correct answer as shown | 1A1 | CAO |

**(2 marks)**

---

## Part (b)

| Answer | Marks | Guidance |
|--------|-------|----------|
| Finding exactly 8 shadow costs and exactly 9 improvement indices for improved solution. Shadow costs: A(15), B(10), C(7), D(14), P(0), Q(-1), R(1), S(3) | 1M1 | 1.1b |
| Shadow costs CAO as listed | 1A1 | Alt shadow costs listed in notes |
| Valid route with most negative II chosen, one empty square, $\theta$'s balance | 2M1 | 1.1b |
| CAO including deduction of all entering and exiting cells. Entering cell AS, exiting cell DS | 2A1 | 2.2a |

**(4 marks)**

---

## Part (c)

| Answer | Marks | Guidance |
|--------|-------|----------|
| Finding all 8 shadow costs and all 9 negative improvement indices, or sufficient number of shadow costs for at least 1 negative II found | 1M1 | Dependent on previous M mark in (b) |
| Negative II (e.g. PC = $-3$) identified from correct working | 1A1 | CAO negative II from correct working |
| Solution is not optimal because there is a negative improvement index | 2A1 | CSO for (a),(b),(c) including correct reasoning. Do not allow 'some IIs are not positive' |

**(3 marks)**

---

## Part (d)

| Answer | Marks | Guidance |
|--------|-------|----------|
| £1086 | 1B1 | CAO, ignore lack of or incorrect units |

**(1 mark)**

---
**(10 marks total)**

Show LaTeX source

\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, $\mathrm { P } , \mathrm { Q } , \mathrm { R }$ and S . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required.
\end{enumerate}

\begin{table}[h]
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & P & Q & R & S & Supply \\
\hline
A & 15 & 14 & 17 & 11 & 23 \\
\hline
B & 10 & 9 & 16 & 12 & 42 \\
\hline
C & 11 & 13 & 8 & 10 & 18 \\
\hline
D & 15 & 13 & 16 & 17 & 19 \\
\hline
Demand & 25 & 45 & 12 & 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
 & P & Q & R & S \\
\hline
A & 23 &  &  &  \\
\hline
B & 2 & 40 &  &  \\
\hline
C &  & 5 & 12 & 1 \\
\hline
D &  &  &  & 19 \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Table 2}
\end{center}
\end{table}

(a) Taking DQ as the entering cell, use the stepping-stone method to find an improved solution. Make your method clear.\\
(b) Perform one further iteration of the stepping-stone method to obtain an improved solution. You must make your method clear by stating the

\begin{itemize}
  \item shadow costs
  \item improvement indices
  \item route
  \item entering cell and exiting cell.\\
(c) Determine whether the solution obtained from this second iteration is optimal, giving a reason for your answer.\\
(d) State the cost of the solution found in (b).
\end{itemize}

\hfill \mbox{\textit{Edexcel FD2 2019 Q1 [10]}}

This paper (6 questions)

View full paper

Q1 10 Q2 7 Q3 13 Q4 14 Q5 11 Q6 8