| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | January |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Complete Simplex solution |
| Difficulty | Standard +0.8 This is a complete Simplex algorithm problem requiring multiple iterations with 3 variables, setup of initial tableau, pivot selection, and interpretation of parameter changes. While mechanically procedural, it demands careful arithmetic across several iterations and understanding of sensitivity analysis in part (iv), making it moderately challenging but still within standard D1 scope. |
| 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 |
| maximise | \(P = 2 x - 5 y - z\), |
| subject to | \(5 x + 3 y - 5 z \leqslant 15\), |
| \(2 x + 6 y + 8 z \leqslant 24\), | |
| and | \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\). |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(5x + 3y - 5z + s = 15\) | B1 | For both equations correctly stated |
| \(2x + 6y + 8z + t = 24\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Initial tableau with \(\pm(-2\ 5\ 1)\) in objective row | B1 | For \(\pm(-2\ 5\ 1)\) in objective row; follow through from part (i) |
| \(5\ 3\ {-5}\ 1\ 0\ 15\) and \(2\ 6\ 8\ 0\ 1\ 24\) in constraint rows | B1 | For \(5\ 3\ {-5}\ 1\ 0\ 15\) and \(2\ 6\ 8\ 0\ 1\ 24\) or equivalent in constraint rows |
| Pivot on 5 in \(x\) column | B1 | For correct pivot choice for their tableau |
| Second tableau: row 1: \(1\ 0\ 6.2\ {-1}\ 0.4\ 0\ 6\); row 2: \(0\ 1\ 0.6\ {-1}\ 0.2\ 0\ 3\); row 3: \(0\ 0\ 4.8\ 10\ {-0.4}\ 1\ 18\) | M1 | For a correct method for their table and their pivot choice |
| M1 | For increasing \(P\) | |
| A1 | For correct tableau or equivalent, cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Pivot on 10 in \(z\) column | M1 | For correct pivot choice; ft their tableau provided not yet optimal |
| Final tableau: row 1: \(1\ 0\ 6.68\ 0\ 0.36\ 0.1\ 7.8\); row 2: \(0\ 1\ 1.08\ 0\ 0.16\ 0.1\ 4.8\); row 3: \(0\ 0\ 0.48\ 1\ {-0.04}\ 0.1\ 1.8\) | A1 | For correct tableau or equivalent, cao |
| \(x = 4.8,\ y = 0,\ z = 1.8\) | B1 | For all three correct values for their final tableau |
| \(P = 7.8\) | B1 | For correct value for their final tableau |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Must now pivot on the 2 in the \(x\) column, giving row 1: \(1\ 0\ 11\ 9\ 0\ 1\ 24\); row 2: \(0\ 0\ {-12}\ {-25}\ 1\ {-2.5}\ k{-60}\); row 3: \(0\ 1\ 3\ 4\ 0\ 0.5\ 12\) | M1 | For showing what happens to tableau; only need to show enough to be able to deduce answer (e.g. top row: \(0\ 11\ 9\ 0\ 1\) or \(y\) column) |
| Hence \(y = 0\); accept 'no change to \(y\)' | A1 | For correctly deducing \(y = 0\) in general case. Only using a specific value of \(k\) (e.g. \(k=60\)) with no general argument \(\Rightarrow\) M1, A0. Do not imply method mark from statement '\(y=0\)' with no method seen. |
# Question 6:
## Part (i)
| Answer | Mark | Guidance |
|--------|------|----------|
| $5x + 3y - 5z + s = 15$ | B1 | For both equations correctly stated |
| $2x + 6y + 8z + t = 24$ | B1 | |
## Part (ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Initial tableau with $\pm(-2\ 5\ 1)$ in objective row | B1 | For $\pm(-2\ 5\ 1)$ in objective row; follow through from part (i) |
| $5\ 3\ {-5}\ 1\ 0\ 15$ and $2\ 6\ 8\ 0\ 1\ 24$ in constraint rows | B1 | For $5\ 3\ {-5}\ 1\ 0\ 15$ and $2\ 6\ 8\ 0\ 1\ 24$ or equivalent in constraint rows |
| Pivot on 5 in $x$ column | B1 | For correct pivot choice for their tableau |
| Second tableau: row 1: $1\ 0\ 6.2\ {-1}\ 0.4\ 0\ 6$; row 2: $0\ 1\ 0.6\ {-1}\ 0.2\ 0\ 3$; row 3: $0\ 0\ 4.8\ 10\ {-0.4}\ 1\ 18$ | M1 | For a correct method for their table and their pivot choice |
| | M1 | For increasing $P$ |
| | A1 | For correct tableau or equivalent, cao |
## Part (iii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Pivot on 10 in $z$ column | M1 | For correct pivot choice; ft their tableau provided not yet optimal |
| Final tableau: row 1: $1\ 0\ 6.68\ 0\ 0.36\ 0.1\ 7.8$; row 2: $0\ 1\ 1.08\ 0\ 0.16\ 0.1\ 4.8$; row 3: $0\ 0\ 0.48\ 1\ {-0.04}\ 0.1\ 1.8$ | A1 | For correct tableau or equivalent, cao |
| $x = 4.8,\ y = 0,\ z = 1.8$ | B1 | For all three correct values for their final tableau |
| $P = 7.8$ | B1 | For correct value for their final tableau |
## Part (iv)
| Answer | Mark | Guidance |
|--------|------|----------|
| Must now pivot on the 2 in the $x$ column, giving row 1: $1\ 0\ 11\ 9\ 0\ 1\ 24$; row 2: $0\ 0\ {-12}\ {-25}\ 1\ {-2.5}\ k{-60}$; row 3: $0\ 1\ 3\ 4\ 0\ 0.5\ 12$ | M1 | For showing what happens to tableau; only need to show enough to be able to deduce answer (e.g. top row: $0\ 11\ 9\ 0\ 1$ or $y$ column) |
| Hence $y = 0$; accept 'no change to $y$' | A1 | For correctly deducing $y = 0$ in general case. Only using a specific value of $k$ (e.g. $k=60$) with no general argument $\Rightarrow$ M1, A0. Do not imply method mark from statement '$y=0$' with no method seen. |
---6 Consider the linear programming problem:
\begin{center}
\begin{tabular}{ l l }
maximise & $P = 2 x - 5 y - z$, \\
subject to & $5 x + 3 y - 5 z \leqslant 15$, \\
& $2 x + 6 y + 8 z \leqslant 24$, \\
and & $x \geqslant 0 , y \geqslant 0 , z \geqslant 0$. \\
\end{tabular}
\end{center}
(i) Using slack variables, $s$ and $t$, express the non-trivial constraints as two equations.\\
(ii) Represent the problem as an initial Simplex tableau. Perform one iteration of the Simplex algorithm.\\
(iii) Use the Simplex algorithm to find the values of $x , y$ and $z$ for which $P$ is maximised, subject to the constraints above.\\
(iv) The value 15 in the first constraint is increased to a new value $k$. As a result the pivot for the first iteration changes. Show what effect this has on the final value of $y$.
\hfill \mbox{\textit{OCR D1 2005 Q6 [13]}}