| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2004 |
| Session | June |
| Marks | 18 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Formulate LP from context |
| Difficulty | Moderate -0.5 This is a standard D2 linear programming question requiring formulation of constraints and one iteration of the simplex algorithm with guided steps. The formulation is routine (translating word problem to inequalities), and the simplex iteration is mechanical arithmetic following a prescribed rule. While it requires careful calculation, it involves no problem-solving insight or novel techniques—just application of a learned algorithm. |
| Spec | 7.06a LP formulation: variables, constraints, objective function7.06b Slack variables: converting inequalities to equations7.07a Simplex tableau: initial setup in standard format |
| Basic variable | \(x\) | \(y\) | \(z\) | \(r\) | \(s\) | \(t\) | Value |
| \(r\) | \(\frac{1}{2}\) | 0 | \(1\frac{1}{2}\) | 1 | \(-\frac{1}{2}\) | 0 | 10 |
| \(y\) | \(\frac{1}{2}\) | 1 | \(\frac{1}{2}\) | 0 | \(\frac{1}{2}\) | 0 | 20 |
| \(t\) | 2 | 0 | 0 | 0 | \(-1\) | 1 | 10 |
| P | \(-10\) | 0 | \(-20\) | 0 | 40 | 0 | 1600 |
| Basic variable | \(x\) | \(y\) | \(z\) | \(r\) | \(s\) | \(t\) | Value | Row operations |
| \(r\) | ||||||||
| \(s\) | ||||||||
| \(t\) | ||||||||
| P |
| Basic variable | \(x\) | \(y\) | \(z\) | \(r\) | \(s\) | \(t\) | Value | Row operations |
| Basic variable | \(x\) | \(y\) | \(z\) | \(r\) | \(s\) | \(t\) | Value | Row operations |
| Basic variable | \(x\) | \(y\) | \(z\) | \(r\) | \(s\) | \(t\) | Value | Row operations |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Maximise \(P = 50x + 80y + 60z\) subject to \(x + y + 2z \leq 30\), \(x + 2y + z \leq 40\), \(3x + 2y + z \leq 50\) where \(x, y, z \geq 0\) | B1, B3, 2, 1,0 | 4 marks |
| Answer | Marks | Guidance |
|---|---|---|
| bv | x | y |
| r | 1 | 1 |
| s | 1 | 2 |
| t | 3 | 2 |
| p | -50 | -80 |
| chooses correct pivot, divides \(R_2\) by 2, states correct row operation \(R_1 - R_2\), \(R_3 - 2R_2\), \(R_4 + 80R_2\), \(R_2 + 2\) | B1ft M1, A1 ft, A1 | 4 marks |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: The solution found after one iteration has a stack of 10 units of black per day | B2, 1, 0 | 2 marks |
| Answer | Marks | Guidance |
|---|---|---|
| bv | x | y |
| r | \(\frac{1}{2}\) | 0 |
| y | \(\frac{1}{2}\) | 1 |
| t | 2 | 0 |
| p | -10 | 0 |
| bv | x | y |
| z | \(\frac{1}{3}\) | 0 |
| y | \(\frac{1}{3}\) | 1 |
| t | 2 | 0 |
| p | \(-3\frac{1}{3}\) | 0 |
| \(R_1 \div \frac{2}{3}\), \(R_2 - \frac{1}{2} R_1\), \(R_3\) - no change, \(R_4 + 20R\) | M1 A1, M1 A1 | 4 marks |
| (ii) not optimal, a negative value in profit row | B1ft | |
| (iii) \(x = 0\), \(y = 16\frac{2}{3}\), \(z = 6\frac{2}{3}\), \(p = £1733.33\), \(r = 0\), \(s = 0\), \(t = 10\) | M1 A1ft, A1ft | 4 marks |
### (a)
**Answer:** Maximise $P = 50x + 80y + 60z$ subject to $x + y + 2z \leq 30$, $x + 2y + z \leq 40$, $3x + 2y + z \leq 50$ where $x, y, z \geq 0$ | B1, B3, 2, 1,0 | 4 marks
### (b)
**Answer:**
| bv | x | y | z | r | s | t | value |
|----|---|---|---|---|---|---|-------|
| r | 1 | 1 | 2 | 1 | 0 | 0 | 30 |
| s | 1 | **2** | 1 | 0 | 1 | 0 | 40 |
| t | 3 | 2 | 1 | 0 | 0 | 1 | 50 |
| p | -50 | -80 | -60 | 0 | 0 | 0 | 0 |
chooses correct pivot, divides $R_2$ by 2, states correct row operation $R_1 - R_2$, $R_3 - 2R_2$, $R_4 + 80R_2$, $R_2 + 2$ | B1ft M1, A1 ft, A1 | 4 marks
### (c)
**Answer:** The solution found after one iteration has a stack of 10 units of black per day | B2, 1, 0 | 2 marks
### (d)(i)
**Answer:**
| bv | x | y | z | r | s | t | value |
|----|----|----|----|----|----|----|-------|
| r | $\frac{1}{2}$ | 0 | $\frac{3}{2}$ | 1 | $-\frac{1}{2}$ | 0 | 10 |
| y | $\frac{1}{2}$ | 1 | $\frac{1}{2}$ | 0 | $\frac{1}{2}$ | 0 | 20 |
| t | 2 | 0 | 0 | 0 | -1 | 1 | 10 |
| p | -10 | 0 | -20 | 0 | 40 | 0 | 1600 |
| bv | x | y | z | r | s | t | value |
|----|----|----|----|----|----|----|-------|
| z | $\frac{1}{3}$ | 0 | 1 | $\frac{2}{3}$ | $-\frac{1}{3}$ | 0 | $6\frac{2}{3}$ |
| y | $\frac{1}{3}$ | 1 | 0 | $-\frac{1}{3}$ | $\frac{2}{3}$ | 0 | $16\frac{2}{3}$ |
| t | 2 | 0 | 0 | 0 | -1 | 1 | 10 |
| p | $-3\frac{1}{3}$ | 0 | 0 | $13\frac{1}{3}$ | $33\frac{1}{3}$ | 0 | $1733\frac{1}{3}$ |
$R_1 \div \frac{2}{3}$, $R_2 - \frac{1}{2} R_1$, $R_3$ - no change, $R_4 + 20R$ | M1 A1, M1 A1 | 4 marks
(ii) not optimal, a negative value in profit row | B1ft |
(iii) $x = 0$, $y = 16\frac{2}{3}$, $z = 6\frac{2}{3}$, $p = £1733.33$, $r = 0$, $s = 0$, $t = 10$ | M1 A1ft, A1ft | 4 marks
---Flatland UK Ltd makes three types of carpet, the Lincoln, the Norfolk and the Suffolk. The carpets all require units of black, green and red wool.
For each roll of carpet,
the Lincoln requires 1 unit of black, 1 of green and 3 of red,
the Norfolk requires 1 unit of black, 2 of green and 2 of red,
and the Suffolk requires 2 units of black, 1 of green and 1 of red.
There are up to 30 units of black, 40 units of green and 50 units of red available each day.
Profits of £50, £80 and £60 are made on each roll of Lincoln, Norfolk and Suffolk respectively. Flatland UK Ltd wishes to maximise its profit.
Let the number of rolls of the Lincoln, Norfolk and Suffolk made daily be $x$, $y$ and $z$ respectively.
\begin{enumerate}[label=(\alph*)]
\item Formulate the above situation as a linear programming problem, listing clearly the constraints as inequalities in their simplest form, and stating the objective function. [4]
\end{enumerate}
This problem is to be solved using the Simplex algorithm. The most negative number in the profit row is taken to indicate the pivot column at each stage.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{1}
\item Stating your row operations, show that after one complete iteration the tableau becomes
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
Basic variable & $x$ & $y$ & $z$ & $r$ & $s$ & $t$ & Value \\
\hline
$r$ & $\frac{1}{2}$ & 0 & $1\frac{1}{2}$ & 1 & $-\frac{1}{2}$ & 0 & 10 \\
\hline
$y$ & $\frac{1}{2}$ & 1 & $\frac{1}{2}$ & 0 & $\frac{1}{2}$ & 0 & 20 \\
\hline
$t$ & 2 & 0 & 0 & 0 & $-1$ & 1 & 10 \\
\hline
P & $-10$ & 0 & $-20$ & 0 & 40 & 0 & 1600 \\
\hline
\end{tabular}
\end{center} [4]
\end{enumerate}
\textit{You may not need to use all of the tableaux.}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
Basic variable & $x$ & $y$ & $z$ & $r$ & $s$ & $t$ & Value & Row operations \\
\hline
$r$ & & & & & & & & \\
\hline
$s$ & & & & & & & & \\
\hline
$t$ & & & & & & & & \\
\hline
P & & & & & & & & \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
Basic variable & $x$ & $y$ & $z$ & $r$ & $s$ & $t$ & Value & Row operations \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{2}
\item Explain the practical meaning of the value 10 in the top row. [2]
\item \begin{enumerate}[label=(\roman*)]
\item Perform one further complete iteration of the Simplex algorithm.
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
Basic variable & $x$ & $y$ & $z$ & $r$ & $s$ & $t$ & Value & Row operations \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
Basic variable & $x$ & $y$ & $z$ & $r$ & $s$ & $t$ & Value & Row operations \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
\end{tabular}
\end{center}
\item State whether your current answer to part (d)(i) is optimal. Give a reason for your answer.
\item Interpret your current tableau, giving the value of each variable. [8]
\end{enumerate}
\end{enumerate}
(Total 18 marks)
\hfill \mbox{\textit{Edexcel D2 2004 Q10 [18]}}