| Exam Board | AQA |
|---|---|
| Module | Further Paper 3 Discrete (Further Paper 3 Discrete) |
| Year | 2023 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Perform one Simplex iteration |
| Difficulty | Standard +0.3 This is a standard Further Maths simplex algorithm question requiring routine mechanical steps: setting up a tableau, performing one iteration with given pivot, and reading off the solution. While it's a Further Maths topic, the execution is algorithmic with no novel problem-solving required, making it easier than average A-level questions overall. |
| Spec | 7.07a Simplex tableau: initial setup in standard format7.07b Simplex iterations: pivot choice and row operations7.07c Interpret simplex: values of variables, slack, and objective |
| \(P\) | \(x\) | \(y\) | \(r\) | \(S\) | value |
| \(P\) | \(x\) | \(y\) | \(r\) | \(s\) | value |
| \(P\) | \(x\) | \(y\) | \(r\) | \(s\) | value |
| 1 | 0 | 0 | \(\frac { 18 } { 5 }\) | \(\frac { 1 } { 5 }\) | 1986 |
| 0 | 0 | 1 | \(\frac { 2 } { 5 }\) | \(- \frac { 1 } { 5 }\) | 94 |
| 0 | 1 | 0 | \(\frac { 3 } { 5 }\) | \(\frac { 1 } { 5 }\) | 426 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| To use the simplex algorithm, the objective function \(P\) must be maximised | B1 | States that the objective function \(P\) must be maximised |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| At least one correct row in the initial simplex tableau | M1 | Translates problem and obtains at least one correct row |
| Fully correct initial simplex tableau: | A1 | |
| \[\begin{array}{c | ccccc | c} |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| At least one correct row other than the pivot row | M1 | |
| Fully correct simplex tableau: | A1 | |
| \[\begin{array}{c | ccccc | c} |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| There are no negative values in the objective row | B1 | Explains correctly that the objective row only contains non-negative values |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| From the simplex tableau, the maximum value of \(P\) is \(1986\) | M1 | Interprets the simplex tableau and obtains the correct optimal value for \(P\) or the correct values for \(x\) and \(y\) at the optimal solution |
| Therefore the minimum value of \(Q\) is \(-1986\) | A1 | Obtains the optimal value for \(Q\), the objective function of the original linear programming problem |
## Question 5:
### Part 5(a):
| Answer | Mark | Guidance |
|--------|------|----------|
| To use the simplex algorithm, the objective function $P$ must be maximised | B1 | States that the objective function $P$ must be maximised |
**Subtotal: 1 mark**
### Part 5(b)(i):
| Answer | Mark | Guidance |
|--------|------|----------|
| At least one correct row in the initial simplex tableau | M1 | Translates problem and obtains at least one correct row |
| Fully correct initial simplex tableau: | A1 | |
$$\begin{array}{c|ccccc|c}
P & x & y & r & s & \text{value} \\\hline
1 & -4 & -3 & 0 & 0 & 0 \\
0 & 1 & 1 & 1 & 0 & 520 \\
0 & 2 & -3 & 0 & 1 & 570
\end{array}$$
**Subtotal: 2 marks**
### Part 5(b)(ii):
| Answer | Mark | Guidance |
|--------|------|----------|
| At least one correct row other than the pivot row | M1 | |
| Fully correct simplex tableau: | A1 | |
$$\begin{array}{c|ccccc|c}
P & x & y & r & s & \text{value} \\\hline
1 & 0 & -9 & 0 & 2 & 1140 \\
0 & 0 & \frac{5}{2} & 1 & -\frac{1}{2} & 235 \\
0 & 1 & -\frac{3}{2} & 0 & \frac{1}{2} & 285
\end{array}$$
**Subtotal: 2 marks**
### Part 5(c)(i):
| Answer | Mark | Guidance |
|--------|------|----------|
| There are no negative values in the objective row | B1 | Explains correctly that the objective row only contains non-negative values |
**Subtotal: 1 mark**
### Part 5(c)(ii):
| Answer | Mark | Guidance |
|--------|------|----------|
| From the simplex tableau, the maximum value of $P$ is $1986$ | M1 | Interprets the simplex tableau and obtains the correct optimal value for $P$ or the correct values for $x$ and $y$ at the optimal solution |
| Therefore the minimum value of $Q$ is $-1986$ | A1 | Obtains the optimal value for $Q$, the objective function of the original linear programming problem |
**Subtotal: 2 marks**
**Question 5 Total: 8 marks**
---5 A student is solving the following linear programming problem.
$$\begin{array} { l r }
\text { Minimise } & Q = - 4 x - 3 y \\
\text { subject to } & x + y \leq 520 \\
& 2 x - 3 y \leq 570 \\
\text { and } & x \geq 0 , y \geq 0
\end{array}$$
5
\begin{enumerate}[label=(\alph*)]
\item The student wants to use the simplex algorithm to solve the linear programming problem.
They modify the linear programming problem by introducing the objective function
$$P = 4 x + 3 y$$
and the slack variables $r$ and $s$
State one further modification that must be made to the linear programming problem so that it can be solved using the simplex algorithm.
5
\item (i) Complete the initial simplex tableau for the modified linear programming problem.\\[0pt]
[2 marks]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
$P$ & $x$ & $y$ & $r$ & $S$ & value \\
\hline
& & & & & \\
\hline
& & & & & \\
\hline
& & & & & \\
\hline
\end{tabular}
\end{center}
5 (b) (ii) Hence, perform one iteration of the simplex algorithm.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
$P$ & $x$ & $y$ & $r$ & $s$ & value \\
\hline
& & & & & \\
\hline
& & & & & \\
\hline
& & & & & \\
\hline
\end{tabular}
\end{center}
5
\item The student performs one further iteration of the simplex algorithm, which results in the following correct simplex tableau.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
$P$ & $x$ & $y$ & $r$ & $s$ & value \\
\hline
1 & 0 & 0 & $\frac { 18 } { 5 }$ & $\frac { 1 } { 5 }$ & 1986 \\
\hline
0 & 0 & 1 & $\frac { 2 } { 5 }$ & $- \frac { 1 } { 5 }$ & 94 \\
\hline
0 & 1 & 0 & $\frac { 3 } { 5 }$ & $\frac { 1 } { 5 }$ & 426 \\
\hline
\end{tabular}
\end{center}
5 (c) (i) Explain how the student can tell that the optimal solution to the modified linear programming problem can be determined from the above simplex tableau.\\
5 (c) (ii) Find the optimal solution of the original linear programming problem.
\end{enumerate}
\hfill \mbox{\textit{AQA Further Paper 3 Discrete 2023 Q5 [8]}}