| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2015 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Complete Simplex solution |
| Difficulty | Standard +0.8 This is a complete Simplex algorithm problem requiring tableau setup, pivot selection with justification, two full iterations, and interpretation. While mechanically procedural, it demands careful arithmetic across multiple steps where errors compound, and requires understanding of pivot selection rules (minimum ratio test). More demanding than standard calculus questions due to length and error-prone nature, but follows a well-defined algorithm taught in D2. |
| 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 | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Introduce slack variables \(s_1, s_2, s_3\) | B1 | |
| Initial tableau: \(\begin{array}{c | ccccccc} & x & y & z & s_1 & s_2 & s_3 & \text{Value} \\ \hline s_1 & 1 & 1 & 2 & 1 & 0 & 0 & 20 \\ s_2 & 3 & 2 & 1 & 0 & 1 & 0 & 30 \\ s_3 & 2 & 3 & 1 & 0 & 0 & 1 & 40 \\ \hline P & -2 & -3 & -4 & 0 & 0 & 0 & 0 \end{array}\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Pivot is \(2\) (from row 1, \(z\)-column) | B1 | |
| Chosen because it gives the minimum ratio: \(20/2 = 10\), \(30/1 = 30\), \(40/1 = 40\), so row 1 gives smallest ratio | B1 | Must reference minimum ratio test |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| New \(s_1\) row (pivot row) \(\div 2\): \(\frac{1}{2}, \frac{1}{2}, 1, \frac{1}{2}, 0, 0 \mid 10\) | M1 | Dividing pivot row by pivot element |
| Updating remaining rows correctly | M1 | Row operations on other rows |
| \(\begin{array}{c | ccccccc} & x & y & z & s_1 & s_2 & s_3 & \text{Value} \\ \hline z & \frac{1}{2} & \frac{1}{2} & 1 & \frac{1}{2} & 0 & 0 & 10 \\ s_2 & \frac{5}{2} & \frac{3}{2} & 0 & -\frac{1}{2} & 1 & 0 & 20 \\ s_3 & \frac{3}{2} & \frac{5}{2} & 0 & -\frac{1}{2} & 0 & 1 & 30 \\ \hline P & 0 & -1 & 0 & 2 & 0 & 0 & 40 \end{array}\) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Pivot column is \(y\) (most negative in \(P\) row), pivot element is \(\frac{5}{2}\) (row 3, ratios: \(10/\frac{1}{2}=20\), \(20/\frac{3}{2}=13.\overline{3}\), \(30/\frac{5}{2}=12\)) | M1 | Correct identification of pivot |
| New \(s_3\) row \(\div \frac{5}{2}\): \(\frac{3}{5}, 1, 0, -\frac{1}{5}, 0, \frac{2}{5} \mid 12\) | M1 | |
| \(\begin{array}{c | ccccccc} & x & y & z & s_1 & s_2 & s_3 & \text{Value} \\ \hline z & \frac{2}{5} & 0 & 1 & \frac{3}{5} & 0 & -\frac{1}{5} & 4 \\ s_2 & \frac{8}{5} & 0 & 0 & -\frac{1}{5} & 1 & -\frac{3}{5} & 2 \\ y & \frac{3}{5} & 1 & 0 & -\frac{1}{5} & 0 & \frac{2}{5} & 12 \\ \hline P & \frac{3}{5} & 0 & 0 & \frac{9}{5} & 0 & \frac{2}{5} & 52 \end{array}\) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| All values in \(P\) row non-negative, so optimal solution reached | B1 | |
| \(P = 52\), \(x = 0\), \(y = 12\), \(z = 4\) | B1 | |
| Slack variables: \(s_1 = 0\), \(s_2 = 2\), \(s_3 = 0\) | B1 | Must state all three slack variable values |
# Question 4:
## Part (a): Display in Simplex Tableau
| Answer | Marks | Guidance |
|--------|-------|----------|
| Introduce slack variables $s_1, s_2, s_3$ | B1 | |
| Initial tableau: $\begin{array}{c|ccccccc} & x & y & z & s_1 & s_2 & s_3 & \text{Value} \\ \hline s_1 & 1 & 1 & 2 & 1 & 0 & 0 & 20 \\ s_2 & 3 & 2 & 1 & 0 & 1 & 0 & 30 \\ s_3 & 2 & 3 & 1 & 0 & 0 & 1 & 40 \\ \hline P & -2 & -3 & -4 & 0 & 0 & 0 & 0 \end{array}$ | B1 | |
## Part (b)(i): Identify pivot
| Answer | Marks | Guidance |
|--------|-------|----------|
| Pivot is $2$ (from row 1, $z$-column) | B1 | |
| Chosen because it gives the minimum ratio: $20/2 = 10$, $30/1 = 30$, $40/1 = 40$, so row 1 gives smallest ratio | B1 | Must reference minimum ratio test |
## Part (b)(ii): First iteration
| Answer | Marks | Guidance |
|--------|-------|----------|
| New $s_1$ row (pivot row) $\div 2$: $\frac{1}{2}, \frac{1}{2}, 1, \frac{1}{2}, 0, 0 \mid 10$ | M1 | Dividing pivot row by pivot element |
| Updating remaining rows correctly | M1 | Row operations on other rows |
| $\begin{array}{c|ccccccc} & x & y & z & s_1 & s_2 & s_3 & \text{Value} \\ \hline z & \frac{1}{2} & \frac{1}{2} & 1 & \frac{1}{2} & 0 & 0 & 10 \\ s_2 & \frac{5}{2} & \frac{3}{2} & 0 & -\frac{1}{2} & 1 & 0 & 20 \\ s_3 & \frac{3}{2} & \frac{5}{2} & 0 & -\frac{1}{2} & 0 & 1 & 30 \\ \hline P & 0 & -1 & 0 & 2 & 0 & 0 & 40 \end{array}$ | A1 | |
## Part (c)(i): Second iteration
| Answer | Marks | Guidance |
|--------|-------|----------|
| Pivot column is $y$ (most negative in $P$ row), pivot element is $\frac{5}{2}$ (row 3, ratios: $10/\frac{1}{2}=20$, $20/\frac{3}{2}=13.\overline{3}$, $30/\frac{5}{2}=12$) | M1 | Correct identification of pivot |
| New $s_3$ row $\div \frac{5}{2}$: $\frac{3}{5}, 1, 0, -\frac{1}{5}, 0, \frac{2}{5} \mid 12$ | M1 | |
| $\begin{array}{c|ccccccc} & x & y & z & s_1 & s_2 & s_3 & \text{Value} \\ \hline z & \frac{2}{5} & 0 & 1 & \frac{3}{5} & 0 & -\frac{1}{5} & 4 \\ s_2 & \frac{8}{5} & 0 & 0 & -\frac{1}{5} & 1 & -\frac{3}{5} & 2 \\ y & \frac{3}{5} & 1 & 0 & -\frac{1}{5} & 0 & \frac{2}{5} & 12 \\ \hline P & \frac{3}{5} & 0 & 0 & \frac{9}{5} & 0 & \frac{2}{5} & 52 \end{array}$ | A1 | |
## Part (c)(ii): Interpret final tableau
| Answer | Marks | Guidance |
|--------|-------|----------|
| All values in $P$ row non-negative, so optimal solution reached | B1 | |
| $P = 52$, $x = 0$, $y = 12$, $z = 4$ | B1 | |
| Slack variables: $s_1 = 0$, $s_2 = 2$, $s_3 = 0$ | B1 | Must state all three slack variable values |
---4
\begin{enumerate}[label=(\alph*)]
\item Display the following linear programming problem in a Simplex tableau.
$$\begin{array} { l r }
\text { Maximise } & P = 2 x + 3 y + 4 z \\
\text { subject to } & x + y + 2 z \leqslant 20 \\
& 3 x + 2 y + z \leqslant 30 \\
& 2 x + 3 y + z \leqslant 40 \\
\text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0
\end{array}$$
\item \begin{enumerate}[label=(\roman*)]
\item The first pivot to be chosen is from the $z$-column. Identify the pivot and explain why this particular value is chosen.
\item Perform one iteration of the Simplex method.
\end{enumerate}\item \begin{enumerate}[label=(\roman*)]
\item Perform one further iteration.
\item Interpret your final tableau and state the values of your slack variables.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D2 2015 Q4 [13]}}