| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2012 |
| Session | January |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Identify pivot and justify |
| Difficulty | Standard +0.3 This is a standard Simplex algorithm question requiring routine application of the method: identifying the pivot column (most negative in P-row), selecting pivot via minimum ratio test, performing row operations, and reading off the solution. While it involves multiple steps and careful arithmetic, it follows a completely algorithmic procedure taught directly in D2 with no problem-solving insight required. Slightly easier than average A-level 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 variable7.07e Graphical interpretation: iterations as edges of convex polygon7.07f Algebraic interpretation: explain simplex calculations |
| \(\boldsymbol { P }\) | \(\boldsymbol { x }\) | \(\boldsymbol { y }\) | \(\boldsymbol { Z }\) | \(\boldsymbol { s }\) | \(\boldsymbol { t }\) | \(\boldsymbol { u }\) | value |
| 1 | -2 | 11 | 0 | 3 | 0 | 0 | 6 |
| 0 | 2 | 3 | 1 | 1 | 0 | 0 | 2 |
| 0 | 6 | -30 | 0 | -6 | 1 | 0 | 3 |
| 0 | -1 | -9 | 0 | -3 | 0 | 1 | 4 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Pivot column is \(y\) (most positive value in P-row: \(+11\) is not valid — look at objective row... column \(y\) has value \(11\) — largest positive in P-row) | B1 | Must identify \(y\) column |
| Ratios: \(6/11\), \(2/3\), \(3/(-30)\) ignore negative, \(4/(-9)\) ignore negative → minimum positive ratio is \(2/3\) | M1 | Must show ratio calculation |
| Pivot is \(3\) (row 2, \(y\) column) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| New row 2 = old row 2 \(\div 3\) | M1 | |
| Eliminate \(y\) from other rows using row operations | M1 | |
| Correct new tableau produced | A1 A1 | One mark per two correct rows |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| All values in the \(P\)-row are \(\leq 0\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(2\) of the inequalities still have slack | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(P = 6\), \(x = 0\), \(y = 2\), \(z = 0\) (read from final tableau) | B1 B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(P = kx - 2y + 3z \Rightarrow 6 = k(0) - 2(2) + 3(0)\)... use correct values | M1 | |
| \(k = 5\) | A1 | From \(P\)-row coefficient back-calculation |
# Question 4:
## Part (a)(i)
| Answer | Mark | Guidance |
|--------|------|----------|
| Pivot column is $y$ (most positive value in P-row: $+11$ is not valid — look at objective row... column $y$ has value $11$ — largest positive in P-row) | B1 | Must identify $y$ column |
| Ratios: $6/11$, $2/3$, $3/(-30)$ ignore negative, $4/(-9)$ ignore negative → minimum positive ratio is $2/3$ | M1 | Must show ratio calculation |
| Pivot is $3$ (row 2, $y$ column) | A1 | |
## Part (a)(ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| New row 2 = old row 2 $\div 3$ | M1 | |
| Eliminate $y$ from other rows using row operations | M1 | |
| Correct new tableau produced | A1 A1 | One mark per two correct rows |
## Part (b)(i)
| Answer | Mark | Guidance |
|--------|------|----------|
| All values in the $P$-row are $\leq 0$ | B1 | |
## Part (b)(ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| $2$ of the inequalities still have slack | B1 | |
## Part (c)(i)
| Answer | Mark | Guidance |
|--------|------|----------|
| $P = 6$, $x = 0$, $y = 2$, $z = 0$ (read from final tableau) | B1 B1 | |
## Part (c)(ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| $P = kx - 2y + 3z \Rightarrow 6 = k(0) - 2(2) + 3(0)$... use correct values | M1 | |
| $k = 5$ | A1 | From $P$-row coefficient back-calculation |4 A linear programming problem consists of maximising an objective function $P$ involving three variables, $x , y$ and $z$, subject to constraints given by three inequalities other than $x \geqslant 0 , y \geqslant 0$ and $z \geqslant 0$. Slack variables $s , t$ and $u$ are introduced and the Simplex method is used to solve the problem. One iteration of the method leads to the following tableau.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
$\boldsymbol { P }$ & $\boldsymbol { x }$ & $\boldsymbol { y }$ & $\boldsymbol { Z }$ & $\boldsymbol { s }$ & $\boldsymbol { t }$ & $\boldsymbol { u }$ & value \\
\hline
1 & -2 & 11 & 0 & 3 & 0 & 0 & 6 \\
\hline
0 & 2 & 3 & 1 & 1 & 0 & 0 & 2 \\
\hline
0 & 6 & -30 & 0 & -6 & 1 & 0 & 3 \\
\hline
0 & -1 & -9 & 0 & -3 & 0 & 1 & 4 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item State the column from which the pivot for the next iteration should be chosen. Identify this pivot and explain the reason for your choice.
\item Perform the next iteration of the Simplex method.
\end{enumerate}\item \begin{enumerate}[label=(\roman*)]
\item Explain why you know that the maximum value of $P$ has been achieved.
\item State how many of the three original inequalities still have slack.
\end{enumerate}\item \begin{enumerate}[label=(\roman*)]
\item State the maximum value of $P$ and the values of $x , y$ and $z$ that produce this maximum value.
\item The objective function for this problem is $P = k x - 2 y + 3 z$, where $k$ is a constant. Find the value of $k$.\\
\begin{center}
\includegraphics[max width=\textwidth, alt={}]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-11_2486_1714_221_153}
\end{center}
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D2 2012 Q4 [13]}}