| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Perform one Simplex iteration |
| Difficulty | Moderate -0.8 This is a routine Simplex algorithm question requiring standard mechanical procedures: setting up a tableau, identifying pivot elements using basic rules (most negative in objective row, minimum ratio test), and performing one iteration. These are well-practiced techniques from D1 with no conceptual challenges or problem-solving required—purely algorithmic execution that's easier than average A-level content. |
| 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 objective |
| Answer | Marks | Guidance |
|---|---|---|
| (i) | B1 | |
| \(P\) | 1 | -3 |
| 0 | 1 | 5 |
| 0 | -1 | -5 |
| 0 | 3 | 10 |
| B1 | For \(\pm(-3 \; 5)\) in objective row | |
| B1 | For \(1 \; 5 \; 12\), \(1 \; -5 \; 10\) and \(3 \; 10 \; 45\) in constraint rows | |
| (ii) | Pivot on second 1 in \(x\) column \(x\) column has a negative entry in objective row \(12 \div 1 = 12\), \(10 \div 1 = 10\), \(45 \div 3 = 15\) Least non-negative ratio is 10 so pivot on the second 1 | B1, 3 |
| (iii) | ||
| \(P\) | 1 | 0 |
| 0 | 0 | 10 |
| 0 | 1 | -5 |
| 0 | 0 | 25 |
| M1, M1, M1, A1 | For correct method evident for objective row For a correct method evident for pivot row For a correct method evident for other rows For correct tableau CAO | |
| (iv) | \(x = 10\), \(y = 0\) \(P = 30\) | B1, B1 |
| \(11 + 5(0.2) = 12\) or \(s = 0\) \(11 - 5(0.2) = 10\) or \(t = 0\) \(3(11) - 10(2) = 35\) or \(u = 0\) so all the constraints are satisfied | B1 | For showing (not just stating) that constraints are satisfied |
| \(P = 3(11) - 5(0.2) = 32\) which is bigger than 30 from (iii) | B1, 2, 13 | For calculating 32, or equivalent (eg 3x has increased by 3 but -5y has only decreased by 1) |
(i) | | B1 | For correct use of three slack variable columns
| $P$ | 1 | -3 | 5 | 0 | 0 | 0 | 0 |
| --- | --- | --- | --- | --- | --- | --- | --- |
| | 0 | 1 | 5 | 1 | 0 | 0 | 12 |
| | 0 | -1 | -5 | 0 | 1 | 0 | 10 |
| | 0 | 3 | 10 | 0 | 0 | 1 | 45 |
| B1 | For $\pm(-3 \; 5)$ in objective row
| B1 | For $1 \; 5 \; 12$, $1 \; -5 \; 10$ and $3 \; 10 \; 45$ in constraint rows
(ii) | Pivot on second 1 in $x$ column $x$ column has a negative entry in objective row $12 \div 1 = 12$, $10 \div 1 = 10$, $45 \div 3 = 15$ Least non-negative ratio is 10 so pivot on the second 1 | B1, 3 | For correct pivot choice (cao) For "negative in top row for $x$", or equivalent, and a correct explanation of choice of row "least ratio 10 $\pm 1$ (their pivot column)
(iii) | | | fit their tableau if possible for method marks
| $P$ | 1 | 0 | -10 | 0 | 3 | 0 | 30 |
| --- | --- | --- | --- | --- | --- | --- | --- |
| | 0 | 0 | 10 | 1 | -1 | 0 | 2 |
| | 0 | 1 | -5 | 0 | 1 | 0 | 10 |
| | 0 | 0 | 25 | 0 | -3 | 1 | 15 |
| M1, M1, M1, A1 | For correct method evident for objective row For a correct method evident for pivot row For a correct method evident for other rows For correct tableau CAO
(iv) | $x = 10$, $y = 0$ $P = 30$ | B1, B1 | For correct values from their tableau For correct value from their tableau
| $11 + 5(0.2) = 12$ or $s = 0$ $11 - 5(0.2) = 10$ or $t = 0$ $3(11) - 10(2) = 35$ or $u = 0$ so all the constraints are satisfied | B1 | For showing (not just stating) that constraints are satisfied
| $P = 3(11) - 5(0.2) = 32$ which is bigger than 30 from (iii) | B1, 2, 13 | For calculating 32, or equivalent (eg 3x has increased by 3 but -5y has only decreased by 1)
---4 Consider the linear programming problem:
$$\begin{array} { l l }
\text { maximise } & P = 3 x - 5 y , \\
\text { subject to } & x + 5 y \leqslant 12 , \\
& x - 5 y \leqslant 10 , \\
& 3 x + 10 y \leqslant 45 , \\
\text { and } & x \geqslant 0 , y \geqslant 0 .
\end{array}$$
(i) Represent the problem as an initial Simplex tableau.\\
(ii) Identify the entry on which to pivot for the first iteration of the Simplex algorithm. Explain how you made your choice of column and row.\\
(iii) Perform oneiteration of the Simplex algorithm. Write down the values of $\mathrm { x } , \mathrm { y }$ and P after this iteration.\\
(iv) Show that $\mathrm { x } = 11 , \mathrm { y } = 0.2$ is a feasible solution and that it gives a bigger value of P than that in part (iii).
\hfill \mbox{\textit{OCR D1 2007 Q4 [13]}}