| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Perform one Simplex iteration |
| Difficulty | Standard +0.3 This is a standard Simplex algorithm question requiring routine application of the taught procedure: introducing slack variables, setting up the initial tableau, identifying the pivot using the standard rules, and performing one iteration. While it involves multiple steps and careful arithmetic, it requires no problem-solving insight—just methodical execution of the algorithm as taught in D1. |
| Spec | 7.06b Slack variables: converting inequalities to equations7.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 = x - 2 y - 3 z\), |
| subject to | \(2 x - 5 y + 2 z \leqslant 10\), |
| \(2 x \quad + 3 z \leqslant 30\), | |
| and | \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\). |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(2x - 5y + 2z + s = 10\) | B1 [1] | Slack variables used correctly |
| \(2x + 3z + t = 30\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Initial tableau: \(P, x, y, z, s, t\) with rows \((1,-1,2,3,0,0\mid 0)\); \((0,2,-5,2,1,0\mid 10)\); \((0,2,0,3,0,1\mid 30)\) | M1, A1 [2] | For overall structure correct including two slack variable columns and column for RHS; For a completely correct initial tableau, with no extra constraints added |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Pivot on \(x\) column since it is the only column with a negative value in the objective row | B1 | For negative in objective row, top row, pay-off row, or equivalent |
| \(10 \div 2 = 5\); \(30 \div 2 = 15\); \(5 < 15\) so pivot on this row | B1 [2] | For these two divisions shown |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| New row 2 \(=\) row \(2 \div 2\) | B1 | For dealing with the pivot row correctly |
| New row 1 \(=\) row \(1 +\) new row 2; New row 3 \(=\) row \(3 - 2 \times\) new row 2 | B1 [2] | For dealing with the other rows correctly; May be coded by rows of table |
| Updated tableau: \((1,0,-0.5,4,0.5,0\mid 5)\); \((0,1,-2.5,1,0.5,0\mid 5)\); \((0,0,5,1,-1,1\mid 20)\) | M1, M1, A1 [3] | For updating their pivot row correctly; For a reasonable attempt at updating other rows; For correct values in tableau |
| \(x = 5,\ y = 0,\ z = 0\); \(P = 5\) | B1, B1 | For reading off \(x, y, z\); For reading off \(P\) |
| Not the maximum feasible value of \(P\) since there is still a negative value in the objective row | B1 [3] | 'No' seen or implied and a correct reason |
# Question 5:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $2x - 5y + 2z + s = 10$ | B1 [1] | Slack variables used correctly |
| $2x + 3z + t = 30$ | | |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Initial tableau: $P, x, y, z, s, t$ with rows $(1,-1,2,3,0,0\mid 0)$; $(0,2,-5,2,1,0\mid 10)$; $(0,2,0,3,0,1\mid 30)$ | M1, A1 [2] | For overall structure correct including two slack variable columns and column for RHS; For a completely correct initial tableau, with no extra constraints added |
## Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Pivot on $x$ column since it is the only column with a **negative value in the objective row** | B1 | For negative in objective row, top row, pay-off row, or equivalent |
| $10 \div 2 = 5$; $30 \div 2 = 15$; $5 < 15$ so pivot on this row | B1 [2] | For these two divisions shown |
## Part (iv)
| Answer | Marks | Guidance |
|--------|-------|----------|
| New row 2 $=$ row $2 \div 2$ | B1 | For dealing with the pivot row correctly |
| New row 1 $=$ row $1 +$ new row 2; New row 3 $=$ row $3 - 2 \times$ new row 2 | B1 [2] | For dealing with the other rows correctly; May be coded by rows of table |
| Updated tableau: $(1,0,-0.5,4,0.5,0\mid 5)$; $(0,1,-2.5,1,0.5,0\mid 5)$; $(0,0,5,1,-1,1\mid 20)$ | M1, M1, A1 [3] | For updating their pivot row correctly; For a reasonable attempt at updating other rows; For correct values in tableau |
| $x = 5,\ y = 0,\ z = 0$; $P = 5$ | B1, B1 | For reading off $x, y, z$; For reading off $P$ |
| **Not** the maximum feasible value of $P$ since there is still a **negative** value in the **objective row** | B1 [3] | 'No' seen or implied and a correct reason |
---5 Consider the linear programming problem:
\begin{center}
\begin{tabular}{ l l }
maximise & $P = x - 2 y - 3 z$, \\
subject to & $2 x - 5 y + 2 z \leqslant 10$, \\
& $2 x \quad + 3 z \leqslant 30$, \\
and & $x \geqslant 0 , y \geqslant 0 , z \geqslant 0$. \\
\end{tabular}
\end{center}
(i) Using slack variables, $s \geqslant 0$ and $t \geqslant 0$, express the two non-trivial constraints as equations.\\
(ii) Represent the problem as an initial Simplex tableau.\\
(iii) Explain why the pivot element must be chosen from the $x$-column and show the calculations that are used to choose the pivot.\\
(iv) Perform one iteration of the Simplex algorithm. Show how you obtained each row of your tableau and write down the values of $x , y , z$ and $P$ that result from this iteration. State whether or not this is the maximum feasible value of $P$ and describe how you know this from the values in the tableau.
\hfill \mbox{\textit{OCR D1 2006 Q5 [13]}}