| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | January |
| Marks | 18 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Explain unbounded solution |
| Difficulty | Standard +0.8 This is a substantial multi-part question requiring understanding of the Simplex algorithm mechanics, recognition of unbounded solutions (a non-standard scenario), and algebraic manipulation of constraints. Part (iv) requires conceptual insight into why unboundedness occurs, and parts (vi-vii) demand problem-solving beyond routine algorithm application. Significantly harder than standard D1 questions but not requiring novel mathematical invention. |
| 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 |
|---|---|
| \[\begin{array}{c | ccccc} |
| Answer | Marks |
|---|---|
| B1, B1, B1 | Correct use of two slack variable columns. \(+(-3, -5, -4)\) in objective row. \(1, 2, -3\); \(12\) and \(2, 5, -8\); \(40\) in constraint rows. Entries for potential pivots are not positive. |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Pivot on 1 in \(x\) column. \(x\) and \(z\) columns have negative entries in obj. row but no value in \(z\) column is positive so choose \(x\). \(12 \div 1 = 12\); \(40 \div 2 = 20\). Least positive ratio is \(12 \le\) pivot on the \(1\). | B1, B1, B1 | Follow through their table. Negative in top row for a and a correct explanation of choice of row 'least ratio \(12 \div 1\)'. Follow through their tableau if possible. Correct method evident. |
| Answer | Marks |
|---|---|
| \[\begin{array}{c | ccccc} |
| Answer | Marks | Guidance |
|---|---|---|
| \(x = 12, y = 0, z = 0\) | M1, A1 | Correct non-negative values for their tableau. |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: \(z\) can increase without limit and increasing \(z\) will increase \(P\) | B1, B1 | Discussing the effect of increasing \(z\). Not just referring to pivoting in tableau. |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Initial tableau is unchanged except entry in \(z\) col of obj. row becomes +40. First iteration tableau is also unchanged except for this entry which becomes 31. No other changes. 36 stated (cao). | B1, B1, B1, B1 | Describing change to obj. row of initial tableau or showing tableau that results. Identifying 31 instead of -13 (cao). No other changes. 36 stated (cao). |
| Answer | Marks |
|---|---|
| Answer: Adding the constraints gives \(3x - 5y + 7z \le 52\) so \(Q \le 52\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: \(x - 3z = 12\) and \(2x + 10z = 40\) (Accept \(\le\)). \(\phi 10z + 6z = 40 - 24\) | M1, M1 | Eliminating \(y\) terms (may be implied). Trying to solve simultaneous equations. |
| Answer: \(\phi x = 15\) and \(z = 1\) | A1 | Correct values (may imply method marks). |
**(i)**
Answer:
$$\begin{array}{c|ccccc}
P & x & y & z & s & t \\
\hline
1 & -3 & -5 & -4 & 0 & 0 \\
0 & 1 & 2 & -3 & 1 & 0 \\
0 & 2 & 5 & -8 & 0 & 1
\end{array}$$
| B1, B1, B1 | Correct use of two slack variable columns. $+(-3, -5, -4)$ in objective row. $1, 2, -3$; $12$ and $2, 5, -8$; $40$ in constraint rows. Entries for potential pivots are not positive.
**(ii)**
Answer: Pivot on 1 in $x$ column. $x$ and $z$ columns have negative entries in obj. row but no value in $z$ column is positive so choose $x$. $12 \div 1 = 12$; $40 \div 2 = 20$. Least positive ratio is $12 \le$ pivot on the $1$. | B1, B1, B1 | Follow through their table. Negative in top row for a and a correct explanation of choice of row 'least ratio $12 \div 1$'. Follow through their tableau if possible. Correct method evident.
**(iii)**
Answer:
$$\begin{array}{c|ccccc}
P & x & y & z & s & t \\
\hline
1 & 0 & 11 & -13 & 3 & 0 \\
0 & 1 & 2 & -3 & 1 & 0 \\
0 & 0 & 1 & -2 & -2 & 1
\end{array}$$
$x = 12, y = 0, z = 0$ | M1, A1 | Correct non-negative values for their tableau.
**(iv)**
Answer: $z$ can increase without limit and increasing $z$ will increase $P$ | B1, B1 | Discussing the effect of increasing $z$. Not just referring to pivoting in tableau.
**(v)**
Answer: Initial tableau is unchanged except entry in $z$ col of obj. row becomes +40. First iteration tableau is also unchanged except for this entry which becomes 31. No other changes. 36 stated (cao). | B1, B1, B1, B1 | Describing change to obj. row of initial tableau or showing tableau that results. Identifying 31 instead of -13 (cao). No other changes. 36 stated (cao).
**(vi)**
Answer: Adding the constraints gives $3x - 5y + 7z \le 52$ so $Q \le 52$ | B1 |
**(vii)**
Answer: $x - 3z = 12$ and $2x + 10z = 40$ (Accept $\le$). $\phi 10z + 6z = 40 - 24$ | M1, M1 | Eliminating $y$ terms (may be implied). Trying to solve simultaneous equations.
Answer: $\phi x = 15$ and $z = 1$ | A1 | Correct values (may imply method marks).
**Total: 18**6 Consider the linear programming problem:
$$\begin{array} { l r }
\text { maximise } & P = 3 x - 5 y + 4 z , \\
\text { subject to } & x + 2 y - 3 z \leqslant 12 , \\
& 2 x + 5 y - 8 z \leqslant 40 , \\
\text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 .
\end{array}$$
(i) Represent the problem as an initial Simplex tableau.\\
(ii) Explain why it is not possible to pivot on the $z$ column of this tableau. 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 one iteration of the Simplex algorithm. Write down the values of $x , y$ and $z$ after this iteration.\\
(iv) Explain why $P$ has no finite maximum.
The coefficient of $z$ in the objective is changed from + 4 to - 40 .\\
(v) Describe the changes that this will cause to the initial Simplex tableau and the tableau that results after one iteration. What is the maximum value of $P$ in this case?
Now consider this linear programming problem:
$$\begin{array} { l l }
\text { maximise } & Q = 3 x - 5 y + 7 z , \\
\text { subject to } & x + 2 y - 3 z \leqslant 12 , \\
& 2 x - 7 y + 10 z \leqslant 40 , \\
\text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 .
\end{array}$$
Do not use the Simplex algorithm for these parts.\\
(vi) By adding the two constraints, show that $Q$ has a finite maximum.\\
(vii) There is an optimal point with $y = 0$. By substituting $y = 0$ in the two constraints, calculate the values of $x$ and $z$ that maximise $Q$ when $y = 0$.
\hfill \mbox{\textit{OCR D1 2007 Q6 [18]}}