| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2008 |
| Session | June |
| Marks | 10 |
| 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 two iterations following a prescribed pivot rule. While it involves fractional arithmetic and multiple row operations, it's purely algorithmic with no problem-solving or insight required—students simply execute the mechanical procedure they've been taught. This is easier than average A-level maths questions which typically require some problem-solving. |
| 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 |
| Basic variable | \(x\) | \(y\) | \(z\) | \(r\) | \(S\) | \(t\) | Value |
| \(r\) | 4 | \(\frac { 7 } { 3 }\) | \(\frac { 5 } { 2 }\) | 1 | 0 | 0 | 64 |
| \(s\) | 1 | 3 | 0 | 0 | 1 | 0 | 16 |
| \(t\) | 4 | 2 | 2 | 0 | 0 | 1 | 60 |
| \(P\) | -5 | \(- \frac { 7 } { 2 }\) | -4 | 0 | 0 | 0 | 0 |
| b.v. | \(x\) | \(y\) | \(z\) | \(r\) | S | \(t\) | Value | Row operations |
| \(P\) |
| b.v. | \(x\) | \(y\) | \(z\) | \(r\) | \(s\) | \(t\) | Value | Row operations |
| \includegraphics[max width=\textwidth, alt={}]{151644c7-edef-448e-ac2a-b374d79f264c-4_86_102_967_374} | ||||||||
| \(P\) |
| b.v. | \(x\) | \(y\) | \(z\) | \(r\) | \(s\) | \(t\) | Value | Row operations |
| \(P\) |
| b.v. | \(x\) | \(y\) | \(z\) | \(r\) | \(S\) | \(t\) | Value | Row operations |
| \(P\) |
| Answer | Marks | Guidance |
|---|---|---|
| b.v. | \(x\) | \(y\) |
| \(r\) | 4 | \(\frac{7}{3}\) |
| \(s\) | 1 | 3 |
| \(t\) | 4 | 2 |
| \(P\) | -5 | \(-\frac{7}{2}\) |
| b.v. | \(x\) | \(y\) |
| \(r\) | 0 | \(\frac{1}{3}\) |
| \(s\) | 0 | \(\frac{5}{2}\) |
| \(x\) | 1 | \(\frac{1}{2}\) |
| \(P\) | 0 | -1 |
| b.v. | \(x\) | \(y\) |
| \(z\) | 0 | \(\frac{2}{3}\) |
| \(s\) | 0 | \(\frac{17}{6}\) |
| \(x\) | 1 | \(\frac{1}{6}\) |
| \(P\) | 0 | 0 |
| (b) There is still negative numbers in the profit row. | B1 | 1 |
**(a)**
| b.v. | $x$ | $y$ | $z$ | $R$ | $s$ | $t$ | Value |
|-----|-----|-----|-----|-----|-----|-----|-------|
| $r$ | 4 | $\frac{7}{3}$ | $\frac{5}{2}$ | 1 | 0 | 0 | 64 |
| $s$ | 1 | 3 | 0 | 0 | 1 | 0 | 16 |
| $t$ | 4 | 2 | 2 | 0 | 0 | 1 | 60 |
| $P$ | -5 | $-\frac{7}{2}$ | -4 | 0 | 0 | 0 | 0 |
| b.v. | $x$ | $y$ | $z$ | $R$ | $s$ | $t$ | Value | Row ops |
|-----|-----|-----|-----|-----|-----|-----|-------|---------|
| $r$ | 0 | $\frac{1}{3}$ | $\frac{1}{2}$ | 1 | 0 | -1 | 4 | $R_1 - 4R_3$ | M1A1 |
| $s$ | 0 | $\frac{5}{2}$ | $-\frac{1}{2}$ | 0 | 1 | $-\frac{1}{4}$ | 1 | $R_2 - R_3$ | M1A1ftA1 |
| $x$ | 1 | $\frac{1}{2}$ | $\frac{1}{2}$ | 0 | 0 | $\frac{1}{4}$ | 15 | $R_3 \div 4$ |
| $P$ | 0 | -1 | $-\frac{3}{2}$ | 0 | 0 | $\frac{5}{4}$ | 75 | $R_4 + 5R_3$ |
| b.v. | $x$ | $y$ | $z$ | $R$ | $s$ | $t$ | Value | Row ops |
|-----|-----|-----|-----|-----|-----|-----|-------|---------|
| $z$ | 0 | $\frac{2}{3}$ | 1 | 2 | 0 | -2 | 8 | $R_1 \div \frac{1}{2}$ | M1A1ft |
| $s$ | 0 | $\frac{17}{6}$ | 0 | 1 | 1 | $\frac{5}{4}$ | 5 | $R_2 + \frac{1}{2}R_1$ | M1A1 |
| $x$ | 1 | $\frac{1}{6}$ | 0 | -1 | 0 | $\frac{5}{4}$ | 11 | $R_3 - \frac{1}{2}R_1$ | 9 |
| $P$ | 0 | 0 | 0 | 3 | 0 | $-\frac{7}{4}$ | 87 | $R_4 + \frac{3}{2}R_1$ |
**(b)** There is still negative numbers in the profit row. | B1 | 1 |
[10]8. The tableau below is the initial tableau for a maximising linear programming problem in $x , y$ and $z$.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
Basic variable & $x$ & $y$ & $z$ & $r$ & $S$ & $t$ & Value \\
\hline
$r$ & 4 & $\frac { 7 } { 3 }$ & $\frac { 5 } { 2 }$ & 1 & 0 & 0 & 64 \\
\hline
$s$ & 1 & 3 & 0 & 0 & 1 & 0 & 16 \\
\hline
$t$ & 4 & 2 & 2 & 0 & 0 & 1 & 60 \\
\hline
$P$ & -5 & $- \frac { 7 } { 2 }$ & -4 & 0 & 0 & 0 & 0 \\
\hline
\end{tabular}
\end{center}
(a) Taking the most negative number in the profit row to indicate the pivot column at each stage, perform two complete iterations of the simplex algorithm. State the row operations you use. You may not need to use all of these tableaux.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
b.v. & $x$ & $y$ & $z$ & $r$ & S & $t$ & Value & Row operations \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
$P$ & & & & & & & & \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
b.v. & $x$ & $y$ & $z$ & $r$ & $s$ & $t$ & Value & Row operations \\
\hline
& & & & & & & & \\
\hline
\includegraphics[max width=\textwidth, alt={}]{151644c7-edef-448e-ac2a-b374d79f264c-4_86_102_967_374}
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
$P$ & & & & & & & & \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
b.v. & $x$ & $y$ & $z$ & $r$ & $s$ & $t$ & Value & Row operations \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
$P$ & & & & & & & & \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
b.v. & $x$ & $y$ & $z$ & $r$ & $S$ & $t$ & Value & Row operations \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
$P$ & & & & & & & & \\
\hline
\end{tabular}
\end{center}
\hfill \mbox{\textit{Edexcel D2 2008 Q8 [10]}}