| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | January |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Perform one Simplex iteration |
| Difficulty | Moderate -0.3 This is a standard Simplex algorithm question testing routine procedural knowledge: setting up a tableau, identifying pivot elements using standard rules, performing one iteration with row operations, and recognizing when the algorithm fails (negative z-value). While multi-step with 13 marks total, each part follows textbook procedures with no novel problem-solving required, making it slightly easier than average. |
| 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 | -25 | -14 |
| 0 | 6 | -4 |
| 0 | 5 | -3 |
| Rows and columns may be in any order; Objective row with -25, -14, -32 | B1 | |
| Constraint rows correct (condone omission of \(P\) column) | B1 | |
| [2] |
| Answer | Marks |
|---|---|
| \(x\) column has a negative value in objective row | B1 |
| 'negative in top row', '-25', or similar; 'most negative in top row' ⇒ bod B1 | B1 |
| Cannot use \(y\) column since it has negative entries in all the other rows | B1 |
| Correct reason for not choosing \(y\) column | B1 |
| \(24 \div 6 = 4\); \(15 \div 5 = 3\); Least non-negative ratio is 3, so pivot on 5 | B1 |
| Both divisions seen and correct choice made (or both divisions seen and correct choice implied from pivoting) | B1 |
| [3] |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | 0 | -29 |
| 0 | 0 | -0.4 |
| 0 | 1 | -0.6 |
| Follow through their sensible tableau (with two slack variable columns) and pivot | M1 | |
| Pivot row correct (no numerical errors); Other rows correct (no numerical errors) | A1 | |
| New row 3 = \(\frac{1}{5}\) row 3 | B1 | |
| New row 1 = row 1 + 25×new row 3 o.e. | B1 | |
| New row 2 = row 2 - 6×new row 3 o.e. | B1 | |
| Calculation for pivot row; Calculation for objective row; Calculation for other row | B1 | |
| \(x = 3\), \(y = 0\), \(z = 0\) | B1 ft | |
| \(P = 75\) | B1 ft | |
| \(x\), \(y\) and \(z\) from their tableau; \(P\) from their tableau, provided \(P \geq 0\) | B1 | |
| [2] |
| Answer | Marks |
|---|---|
| Problem is unbounded; No limit to how big \(y\) (and hence \(P\)) can be; Only negative in objective row is \(y\) column, but all entries in this column are negative | B1 |
| Any one of these, or equivalent. If described in terms of pivot choices, must be complete and convincing | B1 |
| [1] |
## (i)
| P | x | y | z | s | t |
|---|---|---|---|---|---|
| 1 | -25 | -14 | 32 | 0 | 0 |
| 0 | 6 | -4 | 3 | 1 | 0 | 24 |
| 0 | 5 | -3 | 10 | 0 | 1 | 15 |
Rows and columns may be in any order; Objective row with -25, -14, -32 | B1 |
Constraint rows correct (condone omission of $P$ column) | B1 |
| [2] |
## (ii)
$x$ column has a negative value in objective row | B1 |
'negative in top row', '-25', or similar; 'most negative in top row' ⇒ bod B1 | B1 |
Cannot use $y$ column since it has negative entries in all the other rows | B1 |
Correct reason for not choosing $y$ column | B1 |
$24 \div 6 = 4$; $15 \div 5 = 3$; Least non-negative ratio is 3, so pivot on 5 | B1 |
Both divisions seen and correct choice made (or both divisions seen and correct choice implied from pivoting) | B1 |
| [3] |
## (iii)
| | 1 | 0 | -29 | 82 | 0 | 5 | 75 |
| | 0 | 0 | -0.4 | -9 | 1 | -1.2 | 6 |
| | 0 | 1 | -0.6 | 2 | 0 | 0.2 | 3 |
Follow through their sensible tableau (with two slack variable columns) and pivot | M1 |
Pivot row correct (no numerical errors); Other rows correct (no numerical errors) | A1 |
New row 3 = $\frac{1}{5}$ row 3 | B1 |
New row 1 = row 1 + 25×new row 3 o.e. | B1 |
New row 2 = row 2 - 6×new row 3 o.e. | B1 |
Calculation for pivot row; Calculation for objective row; Calculation for other row | B1 |
$x = 3$, $y = 0$, $z = 0$ | B1 ft |
$P = 75$ | B1 ft |
$x$, $y$ and $z$ from their tableau; $P$ from their tableau, provided $P \geq 0$ | B1 |
| [2] |
## (iv)
Problem is unbounded; No limit to how big $y$ (and hence $P$) can be; Only negative in objective row is $y$ column, but all entries in this column are negative | B1 |
Any one of these, or equivalent. If described in terms of pivot choices, must be complete and convincing | B1 |
| [1] |
---\begin{enumerate}[label=(\roman*)]
\item Represent the linear programming problem below by an initial Simplex tableau. [2]
Maximise \quad $P = 25x + 14y - 32z$,
subject to \quad $6x - 4y + 3z \leqslant 24$,
\qquad\qquad\quad $5x - 3y + 10z \leqslant 15$,
and \qquad\qquad $x \geqslant 0$, $y \geqslant 0$, $z \geqslant 0$.
\item Explain how you know that the first iteration will use a pivot from the $x$ column. Show the calculations used to find the pivot element. [3]
\item Perform one iteration of the Simplex algorithm. Show how each row was calculated and write down the values of $x$, $y$, $z$ and $P$ that result from this iteration. [7]
\item Explain why the Simplex algorithm cannot be used to find the optimal value of $P$ for this problem. [1]
\end{enumerate}
\hfill \mbox{\textit{OCR D1 2008 Q6 [13]}}