Question 3 - A-Level Maths

Edexcel FD2 2020 June — Question 3 16 marks

Exam Board	Edexcel
Module	FD2 (Further Decision 2)
Year	2020
Session	June
Marks	16
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Network Flows
Type	Transportation problem: stepping-stone method
Difficulty	Challenging +1.2 This is a standard Further Maths transportation problem requiring systematic application of the stepping-stone method with given entering cell, then one independent iteration, optimality check, LP formulation, and theoretical explanation. While it involves multiple parts and careful bookkeeping, each step follows a well-defined algorithm taught in FD2 with no novel problem-solving required. The difficulty is elevated above average (0.0) due to the Further Maths context and computational intensity, but remains routine for students who have practiced these techniques.

3. 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 three sales points, \(\mathrm { P } , \mathrm { Q }\) and R . It also shows the number of units held at each supply point and the number of units required at each sales point. A minimum cost solution is required. \begin{table}[h]

	P	Q	R	Supply
A	25	24	17	42
B	7	12	14	68
C	13	11	20	25
D	16	15	13	40
Demand	59	72	44

\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
A	42
B	17	51
C		21	4
D			40

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

\end{table}

Taking AR 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

Show mark scheme Show mark scheme source

Question 3:

Part (a):

Answer	Marks	Guidance
Answer/Working	Mark	Guidance
Northwest corner solution with \(\theta\) values: A-P: \(42-\theta\), A-R: \(\theta\), B-P: \(17+\theta\), B-Q: \(51-\theta\), C-Q: \(21+\theta\), C-R: \(4-\theta\), D-R: (40)	M1	A valid route, only one empty square used, \(\theta\)'s balance
Completed table: A-P: 38, A-R: 4, B-P: 21, B-Q: 47, C-Q: 25, D-R: 40	A1	cao

Part (b):

Answer	Marks	Guidance
Answer/Working	Mark	Guidance
Shadow costs: row values 25, 30, 17; column values 0, \(-18\), \(-19\), \(-4\)	M1	Finding all 7 shadow costs and 6 improvement indices for correct 9 entries
Improvement indices: A-Q: \(-6\), A-R: X, B-P: X, B-R: 15, C-P: 7, C-R: 22, D-P: \(-5\), D-Q: \(-11\), D-R: X	A1	Shadow costs and IIs CAO
Most negative II chosen; entering cell DQ, exiting cell AP	M1	Valid route, most negative II chosen, only one empty square used, \(\theta\)'s balance
New solution with entering cell DQ and exiting cell AP	A1	CAO including deduction of all entering and exiting cells

Part (c):

Answer	Marks	Guidance
Answer/Working	Mark	Guidance
New shadow costs: column values 14, 19, 17; row values 0, \(-7\), \(-8\), \(-4\)	M1	Finding all 7 shadow costs and 6 improvement indices (dependent on previous M mark in (b))
Improvement indices: A-P: 11, B-R: 4, C-P: 7, C-R: 11, D-Q: X, others X	A1	CAO (shadow costs and IIs)
No negative IIs so solution is optimal	A1	CSO including correct reasoning that solution is optimal because there are no negative IIs

Part (d):

Answer	Marks	Guidance
Answer/Working	Mark	Guidance
Let \(x_{ij}\) be the number of units (of stock) transported from (supply point) \(i\) to (sales point) \(j\)	B1	Correct definition of \(x_{ij}\)
where \(i \in \{A,B,C,D\}\) and \(j \in \{P,Q,R\}\) (\(x_{ij} \geq 0\))	B1	Correctly defining set of values that \(i\) and \(j\) can take
Minimise \(25x_{AP} + 24x_{AQ} + 17x_{AR} + 7x_{BP} + 12x_{BQ} + 14x_{BR}\) \(+13x_{CP} + 11x_{CQ} + 20x_{CR} + 16x_{DP} + 15x_{DQ} + 13x_{DR}\)	B1, B1	'Minimise' + correct number of terms; Correct objective function
\(\sum x_{Aj} \leq 42,\ \sum x_{Bj} \leq 68,\ \sum x_{Cj} \leq 25,\ \sum x_{Dj} \leq 40\)	B1	Correct supply constraints (allow 'equals' or written in full, e.g. \(x_{AP}+x_{AQ}+x_{AR} \leq 42\))
\(\sum x_{iP} \geq 59,\ \sum x_{iQ} \geq 72,\ \sum x_{iR} \geq 44\)	B1	Correct demand constraints (allow 'equals' or written in full)

Part (e):

Answer	Marks	Guidance
Answer/Working	Mark	Guidance
The Simplex algorithm cannot be used as not all the constraints are in the form \(\sum x \leq k\) where \(k\) is a positive constant	B1	Correct justification of why the Simplex algorithm cannot be used to solve transportation LP

# Question 3:

## Part (a):

| Answer/Working | Mark | Guidance |
|---|---|---|
| Northwest corner solution with $\theta$ values: A-P: $42-\theta$, A-R: $\theta$, B-P: $17+\theta$, B-Q: $51-\theta$, C-Q: $21+\theta$, C-R: $4-\theta$, D-R: (40) | M1 | A valid route, only one empty square used, $\theta$'s balance |
| Completed table: A-P: 38, A-R: 4, B-P: 21, B-Q: 47, C-Q: 25, D-R: 40 | A1 | cao |

## Part (b):

| Answer/Working | Mark | Guidance |
|---|---|---|
| Shadow costs: row values 25, 30, 17; column values 0, $-18$, $-19$, $-4$ | M1 | Finding all 7 shadow costs and 6 improvement indices for correct 9 entries |
| Improvement indices: A-Q: $-6$, A-R: X, B-P: X, B-R: 15, C-P: 7, C-R: 22, D-P: $-5$, D-Q: $-11$, D-R: X | A1 | Shadow costs and IIs CAO |
| Most negative II chosen; entering cell DQ, exiting cell AP | M1 | Valid route, most negative II chosen, only one empty square used, $\theta$'s balance |
| New solution with entering cell DQ and exiting cell AP | A1 | CAO including deduction of all entering and exiting cells |

## Part (c):

| Answer/Working | Mark | Guidance |
|---|---|---|
| New shadow costs: column values 14, 19, 17; row values 0, $-7$, $-8$, $-4$ | M1 | Finding all 7 shadow costs and 6 improvement indices (dependent on previous M mark in (b)) |
| Improvement indices: A-P: 11, B-R: 4, C-P: 7, C-R: 11, D-Q: X, others X | A1 | CAO (shadow costs and IIs) |
| No negative IIs so solution is optimal | A1 | CSO including correct reasoning that solution is optimal because there are no negative IIs |

## Part (d):

| Answer/Working | Mark | Guidance |
|---|---|---|
| Let $x_{ij}$ be the number of units (of stock) transported from (supply point) $i$ to (sales point) $j$ | B1 | Correct definition of $x_{ij}$ |
| where $i \in \{A,B,C,D\}$ and $j \in \{P,Q,R\}$ ($x_{ij} \geq 0$) | B1 | Correctly defining set of values that $i$ and $j$ can take |
| Minimise $25x_{AP} + 24x_{AQ} + 17x_{AR} + 7x_{BP} + 12x_{BQ} + 14x_{BR}$ $+13x_{CP} + 11x_{CQ} + 20x_{CR} + 16x_{DP} + 15x_{DQ} + 13x_{DR}$ | B1, B1 | 'Minimise' + correct number of terms; Correct objective function |
| $\sum x_{Aj} \leq 42,\ \sum x_{Bj} \leq 68,\ \sum x_{Cj} \leq 25,\ \sum x_{Dj} \leq 40$ | B1 | Correct supply constraints (allow 'equals' or written in full, e.g. $x_{AP}+x_{AQ}+x_{AR} \leq 42$) |
| $\sum x_{iP} \geq 59,\ \sum x_{iQ} \geq 72,\ \sum x_{iR} \geq 44$ | B1 | Correct demand constraints (allow 'equals' or written in full) |

## Part (e):

| Answer/Working | Mark | Guidance |
|---|---|---|
| The Simplex algorithm cannot be used as not all the constraints are in the form $\sum x \leq k$ where $k$ is a positive constant | B1 | Correct justification of why the Simplex algorithm cannot be used to solve transportation LP |

---

Show LaTeX source

3. 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 three sales points, $\mathrm { P } , \mathrm { Q }$ and R . It also shows the number of units held at each supply point and the number of units required at each sales point. A minimum cost solution is required.

\begin{table}[h]
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
 & P & Q & R & Supply \\
\hline
A & 25 & 24 & 17 & 42 \\
\hline
B & 7 & 12 & 14 & 68 \\
\hline
C & 13 & 11 & 20 & 25 \\
\hline
D & 16 & 15 & 13 & 40 \\
\hline
Demand & 59 & 72 & 44 &  \\
\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 | }
\hline
 & P & Q & R \\
\hline
A & 42 &  &  \\
\hline
B & 17 & 51 &  \\
\hline
C &  & 21 & 4 \\
\hline
D &  &  & 40 \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Table 2}
\end{center}
\end{table}
\begin{enumerate}[label=(\alph*)]
\item Taking AR as the entering cell, use the stepping-stone method to find an improved solution. Make your method clear.
\item Perform one further iteration of the stepping-stone method to obtain an improved solution. You must make your method clear by stating

\begin{itemize}
  \item shadow costs
  \item improvement indices
  \item route
  \item entering cell and exiting cell.
\item Determine whether the solution obtained from this second iteration is optimal, giving the reason for your answer.
\item Formulate this situation as a linear programming problem. You must define your decision variables and make the objective function and constraints clear.
\item Explain why the Simplex algorithm cannot be used to solve transportation linear programming problems such as that formulated in (d).
\end{itemize}
\end{enumerate}

\hfill \mbox{\textit{Edexcel FD2 2020 Q3 [16]}}

This paper (7 questions)

View full paper

Q1 8 Q2 7 Q3 16 Q4 8 Q5 10 Q6 14 Q7 12