| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2020 |
| Session | November |
| Marks | 12 |
| 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: identifying the pivot column (most negative coefficient in objective row), calculating ratios to find pivot row, performing row operations, 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 objective7.07e Graphical interpretation: iterations as edges of convex polygon |
| \(P\) | \(x\) | \(y\) | \(z\) | \(s\) | \(t\) | RHS |
| 1 | -3 | 1 | 0 | 0 | 0 | 0 |
| 0 | 2 | 0 | 1 | 1 | 0 | 18 |
| 0 | -1 | 2 | 3 | 0 | 1 | 20 |
| Answer | Marks |
|---|---|
| 3 | For reference: |
| Answer | Marks | Guidance |
|---|---|---|
| 3 | (a) | Maximise P = 3x – y |
| Answer | Marks |
|---|---|
| [2] | 3x – y |
| Answer | Marks | Guidance |
|---|---|---|
| 3 | (b) | Slack variables are added to ≤ inequalities to form equations |
| –x + 2y + 3z ≤ 20 becomes –x + 2y + 3z + t = 20, where t ≥ 0 | M1 |
| Answer | Marks |
|---|---|
| [2] | An appropriate description about removing inequalities |
| Answer | Marks | Guidance |
|---|---|---|
| 3 | (c) | Pivot on 2 in x column |
| Answer | Marks |
|---|---|
| (from the origin to (9, 0, 0)) | B1 |
| Answer | Marks |
|---|---|
| [8] | Pivot choice stated or indicated on tableau (not just implied) |
| Answer | Marks | Guidance |
|---|---|---|
| P | x | y |
Question 3:
3 | For reference:
P x y z s t RHS
1 –3 1 0 0 0 0
0 2 0 1 1 0 18
0 –1 2 3 0 1 20
3 | (a) | Maximise P = 3x – y | B1
B1
[2] | 3x – y
Max P
3 | (b) | Slack variables are added to ≤ inequalities to form equations
–x + 2y + 3z ≤ 20 becomes –x + 2y + 3z + t = 20, where t ≥ 0 | M1
A1
[2] | An appropriate description about removing inequalities
–x + 2y + 3z ≤ 20 or –x + 2y + 3z + t = 20
(allow a different letter is used for slack variable)
3 | (c) | Pivot on 2 in x column
P x y z s t RHS
1 0 1 1.5 1.5 0 27
0 1 0 0.5 0.5 0 9
0 0 2 3.5 0.5 1 29
P = 27
x = 9, y = 0, z = 0
Moves along an edge of a convex polyhedron (or 3-dimensional
convex polygon) or along the x-axis in 3-dimensional space
(from the origin to (9, 0, 0)) | B1
M1
M1
A1
B1
M1
A1
B1
[8] | Pivot choice stated or indicated on tableau (not just implied)
(x column and value 2 or x column and middle row)
Their pivot row divided through by their positive pivot value
A tableau with basis cols P, their pivot col and either s or t
in which the values in the final col are non-negative
A correct tableau
27
Reading off ≥ 0 x, y, z values from their final tableau, not all 0
(9, 0, 0) oe
‘edge’ or ‘x-axis’ (not just implied from coordinates) and
3 dimensions (which may be implied from coordinates stated)
P | x | y | z | s | t | RHS3 An initial simplex tableau is shown below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
$P$ & $x$ & $y$ & $z$ & $s$ & $t$ & RHS \\
\hline
1 & -3 & 1 & 0 & 0 & 0 & 0 \\
\hline
0 & 2 & 0 & 1 & 1 & 0 & 18 \\
\hline
0 & -1 & 2 & 3 & 0 & 1 & 20 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Write down the objective for the problem that is represented by this initial tableau.
Variables $s$ and $t$ are slack variables.
\item Use the final row of the initial tableau to explain what a slack variable is.
\item Carry out one iteration of the simplex algorithm and hence:
\begin{itemize}
\item give the pivot column used and the value of the pivot element
\item write down the value of $P$ after this iteration
\item find the values of $x , y$ and $z$ after this iteration
\item describe the effect of the iteration geometrically.
\end{itemize}
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2020 Q3 [12]}}