| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2024 |
| Session | June |
| Marks | 9 |
| 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 tableau setup, one mechanical iteration following the algorithm, and geometric interpretation. While it involves multiple parts and Further Maths content, each step follows a well-defined procedure taught in the syllabus with no novel problem-solving required. |
| 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\) | \(u\) | RHS |
| 1 | 0 | 0 | -2 | 0 | 2.5 | 0.5 | 16 |
| 0 | 0 | 0 | -2 | 1 | -2.5 | 0.5 | 16 |
| 0 | 1 | 0 | -1 | 0 | 1.5 | 0.5 | 10 |
| 0 | 0 | 1 | -1 | 0 | 0.5 | 0.5 | 4 |
| Answer | Marks | Guidance |
|---|---|---|
| 2 | (a) | P = 2x – y + z P – 2x + y – z = 0 |
| Answer | Marks |
|---|---|
| 0 -1 3 -2 0 0 1 2 | M1 |
| Answer | Marks |
|---|---|
| [3] | 1.1 |
| Answer | Marks |
|---|---|
| 1.1 | Dealing with objective |
| Answer | Marks | Guidance |
|---|---|---|
| 2 | (b) | Pivot on 1 in x column |
| Answer | Marks |
|---|---|
| 0 0 2 -2 0 1 1 8 | M1 |
| Answer | Marks |
|---|---|
| [3] | 1.1 |
| Answer | Marks |
|---|---|
| 1.1 | Pivot row and column correct for a valid pivot choice for their |
| Answer | Marks | Guidance |
|---|---|---|
| 2 | (c) | x = 6, y = 0, z = 0 |
| [1] | 2.2a | ft their iterated tableau from part (b) |
| 2 | (d) | Move along edge z = 0, t = 0 |
| Answer | Marks |
|---|---|
| to x = 10, y = 4, z = 0, s = 16, t = 0, u = 0 | B1FT |
| Answer | Marks |
|---|---|
| [2] | 3.1b |
| 2.2a | (i.e. both are = 0 in each row of table below) |
| Answer | Marks | Guidance |
|---|---|---|
| P | x | y |
| 2 | -3 | c |
| -3 | b | 4 |
| a | -1 | -2 |
| 2 | -3 | c |
| -3 | b | 4 |
| a | -1 | -2 |
| 2 | 6 |
Question 2:
2 | (a) | P = 2x – y + z P – 2x + y – z = 0
3x – 4y – z 30 3x – 4y – z + s = 30
x – y 6 x – y + t = 6
x – 3y + 2z –2 –x + 3y – 2z ≤ 2
–x + 3y – 2z + u = 2
P x y z s t u RHS
1 -2 1 -1 0 0 0 0
0 3 -4 -1 1 0 0 30
0 1 -1 0 0 1 0 6
0 -1 3 -2 0 0 1 2 | M1
M1
A1
[3] | 1.1
3.1a
1.1 | Dealing with objective
and using slack variables to remove inequalities
May be implied from tableau
Dealing with constraint
May be implied from tableau
Correct tableau, or equivalent
2 | (b) | Pivot on 1 in x column
P x y z s t u RHS
1 0 -1 -1 0 2 0 12
0 0 -1 -1 1 -3 0 12
0 1 -1 0 0 1 0 6
0 0 2 -2 0 1 1 8 | M1
M1
A1
[3] | 1.1
1.1
1.1 | Pivot row and column correct for a valid pivot choice for their
initial tableau, pivot must be positive and from minimum positive
ratio (RHS pivot col), but condone any non-zero value in P row
M0 if no valid pivot choice available
Structure of iterated tableau correct (4 appropriate basis columns,
non-negative values in RHS column and value of P has increased)
Correct tableau, or equivalent
2 | (c) | x = 6, y = 0, z = 0 | B1FT
[1] | 2.2a | ft their iterated tableau from part (b)
2 | (d) | Move along edge z = 0, t = 0
From x = 6, y = 0, z = 0, s = 12, t = 0, u = 8
to x = 10, y = 4, z = 0, s = 16, t = 0, u = 0 | B1FT
B1FT
[2] | 3.1b
2.2a | (i.e. both are = 0 in each row of table below)
Sufficient to have the (exactly) 3 zero values correct in each row
ft their iterated tableau from part (b)
P | x | y | z | s | t | u | RHS
2 | -3 | c
-3 | b | 4
a | -1 | -2
2 | -3 | c
-3 | b | 4
a | -1 | -2
2 | 62 A linear programming problem is
Maximise $\mathrm { P } = 2 \mathrm { x } - \mathrm { y } + \mathrm { z }$\\
subject to\\
$3 x - 4 y - z \leqslant 30$\\
$x - y \leqslant 6$\\
$x - 3 y + 2 z \geqslant - 2$\\
and $x \geqslant 0 , y \geqslant 0 , z \geqslant 0$
\begin{enumerate}[label=(\alph*)]
\item Complete the table in the Printed Answer Booklet to represent the problem as an initial simplex tableau.
\item Carry out one iteration of the simplex algorithm.
\item State the values of $x , y$ and $z$ that result from your iteration.
After two iterations the resulting tableau is
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
$P$ & $x$ & $y$ & $z$ & $s$ & $t$ & $u$ & RHS \\
\hline
1 & 0 & 0 & -2 & 0 & 2.5 & 0.5 & 16 \\
\hline
0 & 0 & 0 & -2 & 1 & -2.5 & 0.5 & 16 \\
\hline
0 & 1 & 0 & -1 & 0 & 1.5 & 0.5 & 10 \\
\hline
0 & 0 & 1 & -1 & 0 & 0.5 & 0.5 & 4 \\
\hline
\end{tabular}
\end{center}
The boundaries of the feasible region are planes, with edges each defined by two of $x , y , z , s , t , u$ being zero.\\
At each vertex of the feasible region there are three basic variables and three non-basic variables.
\item Interpret the second iteration geometrically by stating which edge of the feasible region is being moved along. As part of your geometrical interpretation, you should state the beginning vertex and end vertex of the second iteration.
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2024 Q2 [9]}}