| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Perform one Simplex iteration |
| Difficulty | Moderate -0.5 This is a straightforward application of the Simplex algorithm requiring standard procedures: setting up the initial tableau with slack variables, identifying the pivot column (most negative coefficient in objective row), applying the ratio test, and performing row operations. While it involves multiple steps and careful arithmetic, it's a routine textbook exercise with no conceptual challenges or problem-solving required—students simply follow the mechanical algorithm they've been taught. |
| Spec | 7.07a Simplex tableau: initial setup in standard format7.07b Simplex iterations: pivot choice and row operations |
| Answer | Marks | Guidance |
|---|---|---|
| \(P\) | \(x\) | \(y\) |
| 1 | -5 | 4 |
| 0 | 2 | -3 |
| 0 | 6 | 5 |
| M1 | For overall structure correct, including two slack variable columns | |
| A1 | For a correct initial tableau, with no extra constraints added |
| Answer | Marks | Guidance |
|---|---|---|
| (2) M1 | For the correct pivot choice for their tableau | |
| A1 | For dealing with the pivot row correctly (formula or numerical) | |
| M1 | For dealing with the other rows correctly (formula or numerical) | |
| A1 | For a correct tableau (not fit) | |
| 1 | 0 | -3.5 |
| 0 | 1 | -1.5 |
| 0 | 0 | 14 |
| Answer | Marks |
|---|---|
| B1 (6) | For reading off \(x\), \(y\) and \(z\) from their tableau |
| B1 | For reading off \(P\) from their tableau |
| \(\mathbf{8}\) |
**(i)**
| $P$ | $x$ | $y$ | $z$ | $s$ | $t$ | |
|---|---|---|---|---|---|---|
| 1 | -5 | 4 | 3 | 0 | 0 | 0 |
| 0 | 2 | -3 | 4 | 1 | 0 | 10 |
| 0 | 6 | 5 | 4 | 0 | 1 | 60 |
| M1 | For overall structure correct, including two slack variable columns |
| A1 | For a correct initial tableau, with no extra constraints added |
**(ii)** Pivot on 2 in $x$ column
- $r1 = r1 + 5npr$
- $r2 = r2 + 2$
- $r3 = r3 - 6npr$
| (2) M1 | For the correct pivot choice for their tableau |
| A1 | For dealing with the pivot row correctly (formula or numerical) |
| M1 | For dealing with the other rows correctly (formula or numerical) |
| A1 | For a correct tableau (not fit) |
| 1 | 0 | -3.5 | 13 | 2.5 | 0 | 25 |
|---|---|---|---|---|---|---|
| 0 | 1 | -1.5 | 2 | 0.5 | 0 | 5 |
| 0 | 0 | 14 | -8 | -3 | 1 | 30 |
$x = 5, y = 0, z = 0$
$P = 25$
| B1 (6) | For reading off $x$, $y$ and $z$ from their tableau |
| B1 | For reading off $P$ from their tableau |
| | $\mathbf{8}$ |4 (i) Represent the linear programming problem below by an initial Simplex tableau.
$$\begin{array} { l l }
\text { Maximise } & P = 5 x - 4 y - 3 z , \\
\text { subject to } & 2 x - 3 y + 4 z \leqslant 10 , \\
& 6 x + 5 y + 4 z \leqslant 60 , \\
\text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 .
\end{array}$$
(ii) Perform one iteration of the Simplex algorithm and write down the values of $x , y , z$ and $P$ that result from this iteration.
\hfill \mbox{\textit{OCR D1 2006 Q4 [8]}}