| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | January |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Variable transformation problems |
| Difficulty | Standard +0.8 This is a multi-part D1 question requiring variable transformation to convert a minimization problem with upper bounds into standard maximization form, then applying the Simplex algorithm. While the transformation in part (i) is algebraically straightforward verification, it requires careful manipulation of inequalities. Part (ii) demands proper Simplex tableau setup and iteration with full justification. The question tests understanding beyond routine application, combining transformation techniques with algorithmic execution, placing it moderately above average difficulty for A-level. |
| Spec | 7.07a Simplex tableau: initial setup in standard format7.07b Simplex iterations: pivot choice and row operations |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Substituting \(a=20-x\), \(b=10-y\), \(c=8-z\) into objective and constraints and simplifying to obtain given forms | M1 M1 A1 | Full substitution shown for at least objective and one constraint |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Initial tableau set up correctly with slack variables | M1 A1 | |
| Pivot column chosen (most positive in objective row: \(x\) column, coefficient 2) | M1 | |
| Correct pivot element identified with minimum ratio test | M1 | |
| New tableau after one iteration correct | A1 A1 | |
| Values of \(x,y,z\) stated | A1 | |
| Corresponding \(a,b,c\) values stated | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(x \leq 20\), \(y \leq 10\), \(z \leq 8\) | B1 B1 | Since \(a=20-x \geq 0 \Rightarrow x \leq 20\) etc. |
# Question 5:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Substituting $a=20-x$, $b=10-y$, $c=8-z$ into objective and constraints and simplifying to obtain given forms | M1 M1 A1 | Full substitution shown for at least objective and one constraint |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Initial tableau set up correctly with slack variables | M1 A1 | |
| Pivot column chosen (most positive in objective row: $x$ column, coefficient 2) | M1 | |
| Correct pivot element identified with minimum ratio test | M1 | |
| New tableau after one iteration correct | A1 A1 | |
| Values of $x,y,z$ stated | A1 | |
| Corresponding $a,b,c$ values stated | A1 | |
## Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $x \leq 20$, $y \leq 10$, $z \leq 8$ | B1 B1 | Since $a=20-x \geq 0 \Rightarrow x \leq 20$ etc. |
---5 Consider the following LP problem.
$$\begin{aligned}
\text { Minimise } & 2 a - 3 b + c + 18 , \\
\text { subject to } & a + b - c \geqslant 14 , \\
& - 2 a + 3 c \leqslant 50 , \\
\text { and } & a \leqslant 4 a \leqslant 5 b , \\
& a \leqslant 20 , b \leqslant 10 , c \leqslant 8 .
\end{aligned}$$
(i) By replacing $a$ by $20 - x , b$ by $10 - y$ and $c$ by $8 - z$, show that the problem can be expressed as follows.
$$\begin{aligned}
\text { Maximise } & 2 x - 3 y + z , \\
\text { subject to } & x + y - z \leqslant 8 , \\
& 2 x - 3 z \leqslant 66 , \\
& 4 x - 5 y \leqslant 40 , \\
\text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 .
\end{aligned}$$
(ii) Represent the problem as an initial Simplex tableau. Perform one iteration of the Simplex algorithm. Explain how the choice of pivot was made and show how each row was obtained. Write down the values of $x , y$ and $z$ at this stage. Hence write down the corresponding values of $a , b$ and $c$.\\
(iii) If, additionally, the variables $a , b$ and $c$ are non-negative, what additional constraints are there on the values of $x , y$ and $z$ ?
\hfill \mbox{\textit{OCR D1 2010 Q5 [16]}}