| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2006 |
| Session | June |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Complete Simplex solution |
| Difficulty | Standard +0.3 This is a standard Simplex algorithm question requiring mechanical application of the method: reading constraints from a tableau, identifying pivots using the ratio test, performing row operations, and recognizing optimality. While it involves multiple steps, each follows a well-defined algorithmic procedure taught directly in D2 with no novel problem-solving or insight required. Slightly easier than average due to its purely procedural nature. |
| 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 objective7.07d Simplex terminology: basic feasible solution, basic/non-basic variable |
| \(\boldsymbol { P }\) | \(\boldsymbol { x }\) | \(\boldsymbol { y }\) | \(r\) | \(s\) | \(\boldsymbol { t }\) | value |
| 1 | -4 | -9 | 0 | 0 | 0 | 0 |
| 0 | 3 | 7 | 1 | 0 | 0 | 33 |
| 0 | 1 | 2 | 0 | 1 | 0 | 10 |
| 0 | 2 | 7 | 0 | 0 | 1 | 26 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(3x + 7y \leq 33\) | M1 | One correct inequality, or all using \(<\) |
| \(x + 2y \leq 10\) | ||
| \(2x + 7y \leq 26\) | A1 | All correct; Total: 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Compare \(\frac{33}{3},\ \frac{10}{1},\ \frac{26}{2}\) | E1 | |
| Choose smallest positive value \(\Rightarrow\) pivot \(= 1\) | E1 | Total: 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| First tableau after pivot on \(s\)-column: \(P\ x\ y\ r\ s\ t\ \text{Value}\): row 1: \(1\ 0\ -1\ 0\ 4\ 0\ 40\); row 2: \(0\ 0\ 1\ 1\ -3\ 0\ 3\); row 3: \(0\ 1\ 2\ 0\ 1\ 0\ 10\); row 4: \(0\ 0\ \frac{2}{3}\ 0\ -2\ 1\ 6\) | M1 A1 A1 | Row operation; Correct one row (other than pivot row); All correct |
| Next \(y\) pivot on \(\frac{2}{3}\); second tableau rows: \(1\ 0\ 0\ 0\ 3\frac{1}{3}\ \frac{1}{3}\ 42\); \(0\ 0\ 0\ 1\ -2\frac{1}{3}\ -\frac{1}{3}\ 1\); \(0\ 1\ 0\ 0\ 2\frac{1}{3}\ -\frac{2}{3}\ 6\); \(0\ 0\ 1\ 0\ -\frac{2}{3}\ \frac{1}{3}\ 2\) | M1 m1 A1 A1 | Row operation; Correct one row (other than pivot row); All correct (condone multiples of given rows); max 6 if \(y\)-pivot used first; Total: 7 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| No negative number in top row | E1 | |
| \(P_{\max} = 42\) | \(\text{B1}\sqrt{}\) | ft if M3 scored and optimum reached |
| \(x = 6,\ y = 2\) | \(\text{B1}\sqrt{}\) | Total: 3 |
# Question 5:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $3x + 7y \leq 33$ | M1 | One correct inequality, or all using $<$ |
| $x + 2y \leq 10$ | | |
| $2x + 7y \leq 26$ | A1 | All correct; Total: 2 |
## Part (b)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Compare $\frac{33}{3},\ \frac{10}{1},\ \frac{26}{2}$ | E1 | |
| Choose smallest positive value $\Rightarrow$ pivot $= 1$ | E1 | Total: 2 |
## Part (b)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| First tableau after pivot on $s$-column: $P\ x\ y\ r\ s\ t\ \text{Value}$: row 1: $1\ 0\ -1\ 0\ 4\ 0\ 40$; row 2: $0\ 0\ 1\ 1\ -3\ 0\ 3$; row 3: $0\ 1\ 2\ 0\ 1\ 0\ 10$; row 4: $0\ 0\ \frac{2}{3}\ 0\ -2\ 1\ 6$ | M1 A1 A1 | Row operation; Correct one row (other than pivot row); All correct |
| Next $y$ pivot on $\frac{2}{3}$; second tableau rows: $1\ 0\ 0\ 0\ 3\frac{1}{3}\ \frac{1}{3}\ 42$; $0\ 0\ 0\ 1\ -2\frac{1}{3}\ -\frac{1}{3}\ 1$; $0\ 1\ 0\ 0\ 2\frac{1}{3}\ -\frac{2}{3}\ 6$; $0\ 0\ 1\ 0\ -\frac{2}{3}\ \frac{1}{3}\ 2$ | M1 m1 A1 A1 | Row operation; Correct one row (other than pivot row); All correct (condone multiples of given rows); max 6 if $y$-pivot used first; Total: 7 |
## Part (b)(iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| No negative number in top row | E1 | |
| $P_{\max} = 42$ | $\text{B1}\sqrt{}$ | ft if M3 scored and optimum reached |
| $x = 6,\ y = 2$ | $\text{B1}\sqrt{}$ | Total: 3 |5 A linear programming problem involving variables $x$ and $y$ is to be solved. The objective function to be maximised is $P = 4 x + 9 y$. The initial Simplex tableau is given below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
$\boldsymbol { P }$ & $\boldsymbol { x }$ & $\boldsymbol { y }$ & $r$ & $s$ & $\boldsymbol { t }$ & value \\
\hline
1 & -4 & -9 & 0 & 0 & 0 & 0 \\
\hline
0 & 3 & 7 & 1 & 0 & 0 & 33 \\
\hline
0 & 1 & 2 & 0 & 1 & 0 & 10 \\
\hline
0 & 2 & 7 & 0 & 0 & 1 & 26 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Write down the three inequalities in $x$ and $y$ represented by this tableau.
\item The Simplex method is to be used to solve this linear programming problem by initially choosing a value in the $x$-column as the pivot.
\begin{enumerate}[label=(\roman*)]
\item Explain why the initial pivot has value 1.
\item Perform two iterations using the Simplex method.
\item Comment on how you know that the optimum solution has been achieved and state your final values of $P , x$ and $y$.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D2 2006 Q5 [14]}}