| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2011 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Explain unbounded solution |
| Difficulty | Standard +0.8 This D1 question requires setting up and performing two simplex iterations, then recognizing and explaining an unbounded solution from both the tableau and original formulation. While the mechanical steps are standard, identifying unboundedness requires conceptual understanding beyond routine application, and the final part demands insight into why the LP structure permits unbounded growth—making this moderately challenging for A-level. |
| 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 |
| Maximise | \(P = - 3 w + 5 x - 7 y + 2 z\), |
| subject to | \(w + 2 x - 2 y - z \leqslant 10\), |
| \(2 w + 3 y - 4 z \leqslant 12\), | |
| and | \(4 w + 5 x + y \leqslant 30\), |
| \(w \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0\). |
| Answer | Marks |
|---|---|
| (i) Objective row correct (3, 3, 7, 2) | B1 |
| Constructing two sources slack | B1 |
| x has negative value (in the objective row) Clearly the value (in objective row) | B1 |
| Use signs of entries in columns to show that Only follow through their initial tableau if it (unless also say negative) | |
| r column has negative value in objective (unless also say negative) possible negative columns | B1 |
| (ii) Column required in part (ii) | M1 A1 |
| A column of 0 > M_0 | |
| Rows and columns, one ignore any writing "any written, (can) ignore any writing | B1 |
| Follow through two iterations can) ignore any writing "ignore values for slack variables given" | B1 |
(i) Objective row correct (3, 3, 7, 2) | B1 |
Constructing two sources slack | B1 |
x has negative value (in the objective row) Clearly the value (in objective row) | B1 |
Use signs of entries in columns to show that Only follow through their initial tableau if it (unless also say negative) | |
r column has negative value in objective (unless also say negative) possible negative columns | B1 |
(ii) Column required in part (ii) | M1 A1 |
A column of 0 > M_0 | |
Rows and columns, one ignore any writing "any written, (can) ignore any writing | B1 |
Follow through two iterations can) ignore any writing "ignore values for slack variables given" | B1 |
---4 Consider the following LP problem.
\begin{center}
\begin{tabular}{ l l }
Maximise & $P = - 3 w + 5 x - 7 y + 2 z$, \\
subject to & $w + 2 x - 2 y - z \leqslant 10$, \\
& $2 w + 3 y - 4 z \leqslant 12$, \\
and & $4 w + 5 x + y \leqslant 30$, \\
& $w \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0$. \\
\end{tabular}
\end{center}
(i) Represent the problem as an initial Simplex tableau. Explain why the pivot can only be chosen from the $x$ column.\\
(ii) Perform one iteration of the Simplex algorithm. Show how each row was obtained and write down the values of $w , x , y , z$ and $P$ at this stage.\\
(iii) Perform a second iteration of the Simplex algorithm. Write down the values of $w , x , y , z$ and $P$ at this stage and explain how you can tell from this tableau that $P$ can be increased without limit. How could you have known from the LP formulation above that $P$ could be increased without limit?
\hfill \mbox{\textit{OCR D1 2011 Q4 [13]}}