| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2023 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Explain why pivot impossible |
| Difficulty | Standard +0.3 This is a standard simplex algorithm question requiring mechanical application of the method (part a), reading values from a tableau (part b), recognizing when no pivot is possible due to negative/zero entries in the pivot column (part c), and using the relationship between pivot operations and the objective function to find k (part d). All parts follow routine procedures taught in Further Discrete modules, with no novel problem-solving required beyond applying learned algorithms. |
| Spec | 7.07b Simplex iterations: pivot choice and row operations7.07c Interpret simplex: values of variables, slack, and objective |
| \(P\) | \(x\) | \(y\) | \(z\) | \(s\) | \(t\) | RHS |
| 1 | - 2 | 3 | - 1 | 0 | 0 | 0 |
| 0 | 5 | - 4 | 1 | 1 | 0 | 20 |
| 0 | 2 | - 1 | 0 | 0 | 1 | 6 |
| \(P\) | \(x\) | \(y\) | \(z\) | \(s\) | \(t\) | RHS |
| 1 | 3 | - 1 | 0 | 1 | 0 | 20 |
| 0 | 5 | - 4 | 1 | 1 | 0 | 20 |
| 0 | 2 | - 1 | 0 | 0 | 1 | 6 |
| \(P\) | \(x\) | \(y\) | \(z\) | \(s\) | \(t\) | RHS |
| 1 | 2 | - 3 | 1 | 0 | 0 | 0 |
| 0 | 5 | \(k\) | 1 | 1 | 0 | 20 |
| 0 | 2 | - 1 | 0 | 0 | 1 | 6 |
| Answer | Marks | Guidance |
|---|---|---|
| 3 | (a) | P x y z s t RHS |
| Answer | Marks |
|---|---|
| 0 1 -0.5 0 0 0.5 3 | M1 |
| Answer | Marks |
|---|---|
| [4] | 1.1 |
| Answer | Marks |
|---|---|
| 1.1 | Pivot row values correct for first iteration |
| Answer | Marks | Guidance |
|---|---|---|
| 3 | (b) | P = 20, x = 0, y = 0, z = 20, s = 0, t = 6 |
| Answer | Marks |
|---|---|
| [2] | 1.1 |
| 1.1 | For any three correct |
| Answer | Marks | Guidance |
|---|---|---|
| 3 | (c) | The next pivot would have to be chosen |
| Answer | Marks |
|---|---|
| So there is no valid pivot choice | M1 |
| Answer | Marks |
|---|---|
| [2] | 2.2a |
| 2.4 | Identifying y |
| Answer | Marks | Guidance |
|---|---|---|
| P | x | y |
| 3 | (d) | Pivot on k from y column |
| Answer | Marks |
|---|---|
| 60/k = 500 k = 60/500 = 3/25 = 0.12 | M1 |
| Answer | Marks |
|---|---|
| A1 | 3.1.a |
| Answer | Marks |
|---|---|
| 1.1 | Pivot choice correct e.g. y column or row 2 correct |
| Answer | Marks | Guidance |
|---|---|---|
| after one iteration x and z will still be 0 | Pivot will be chosen from y column, so | M1 |
| y becomes basic, x and z are non-basic | Pivot from y column so x and z are both 0 (soi) | |
| P = -2x + 3y – z so 3y = 500 y = 500/3 | A1 | 3y = 500 (o.e.) |
| So RHS of pivot row becomes 166.67 | M1 | Entry in RHS column of pivot row = 500/3 (or 167 or better |
| Answer | Marks | Guidance |
|---|---|---|
| 20/k = 500/3 k = 60/500 = 3/25 = 0.12 | A1 | k = 0.12 (o.e.) |
| Answer | Marks | Guidance |
|---|---|---|
| P | x | y |
Question 3:
3 | (a) | P x y z s t RHS
1 0 2 -1 0 1 6
0 0 -1.5 1 1 -2.5 5
0 1 -0.5 0 0 0.5 3
P x y z s t RHS
1 0 0.5 0 1 -1.5 11
0 0 -1.5 1 1 -2.5 5
0 1 -0.5 0 0 0.5 3 | M1
A1
M1 ft
A1
[4] | 1.1
1.1
1.1
1.1 | Pivot row values correct for first iteration
Constraint row values correct
Second iteration has a valid pivot and pivot row values are correct
(from their first iteration, provided not the same pivot as before)
Structure correct – but not matrix from QP (with P = 20)
3 | (b) | P = 20, x = 0, y = 0, z = 20, s = 0, t = 6 | B1
B1
[2] | 1.1
1.1 | For any three correct
For all six correct
3 | (c) | The next pivot would have to be chosen
from the y column
Since -1 is the only negative value in the
objective row
But there are no positive entries in the other
rows of the y column
So there is no valid pivot choice | M1
A1
[2] | 2.2a
2.4 | Identifying y
Explaining why there is no valid pivot choice
No other possible pivot col and no valid pivot row
P | x | y | z | s | t | RHS
3 | (d) | Pivot on k from y column
P x y z s t RHS
1 0 0 60/k
0 5/k 1 1/k 1/k 0 20/k
0 0 1
60/k = 500 k = 60/500 = 3/25 = 0.12 | M1
A1
M1
A1 | 3.1.a
2.2a
3.4
1.1 | Pivot choice correct e.g. y column or row 2 correct
or implied from written work (e.g. ‘pivot on k’)
Pivot row correct, in terms of k
Value of objective is 60/k, or implied from k = 0.12
k = 0.12 (o.e.)
Alternative method
Pivot will be chosen from y column, so
after one iteration x and z will still be 0 | Pivot will be chosen from y column, so | M1 | M1 | Pivot from y column so x and z are both 0 (soi)
y becomes basic, x and z are non-basic | Pivot from y column so x and z are both 0 (soi)
P = -2x + 3y – z so 3y = 500 y = 500/3 | A1 | 3y = 500 (o.e.)
So RHS of pivot row becomes 166.67 | M1 | Entry in RHS column of pivot row = 500/3 (or 167 or better
or implied from k = 0.12
20/k = 500/3 k = 60/500 = 3/25 = 0.12 | A1 | k = 0.12 (o.e.)
[4]
P | x | y | z | s | t | RHS3 An initial simplex tableau is given below.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | }
\hline
$P$ & $x$ & $y$ & $z$ & $s$ & $t$ & RHS \\
\hline
1 & - 2 & 3 & - 1 & 0 & 0 & 0 \\
\hline
0 & 5 & - 4 & 1 & 1 & 0 & 20 \\
\hline
0 & 2 & - 1 & 0 & 0 & 1 & 6 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Carry out two iterations of the simplex algorithm, choosing the first pivot from the $x$ column.
After three iterations the resulting tableau is as follows.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | }
\hline
$P$ & $x$ & $y$ & $z$ & $s$ & $t$ & RHS \\
\hline
1 & 3 & - 1 & 0 & 1 & 0 & 20 \\
\hline
0 & 5 & - 4 & 1 & 1 & 0 & 20 \\
\hline
0 & 2 & - 1 & 0 & 0 & 1 & 6 \\
\hline
\end{tabular}
\end{center}
\item State the values of $P , x , y , z , s$ and $t$ that result from these three iterations.
\item Explain why no further iterations are possible.
The initial simplex tableau is changed to the following, where $k$ is a positive real value.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | }
\hline
$P$ & $x$ & $y$ & $z$ & $s$ & $t$ & RHS \\
\hline
1 & 2 & - 3 & 1 & 0 & 0 & 0 \\
\hline
0 & 5 & $k$ & 1 & 1 & 0 & 20 \\
\hline
0 & 2 & - 1 & 0 & 0 & 1 & 6 \\
\hline
\end{tabular}
\end{center}
After one iteration of the simplex algorithm the value of $P$ is 500 .
\item Deduce the value of $k$.
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2023 Q3 [12]}}