| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | January |
| Marks | 18 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Formulate LP from context |
| Difficulty | Standard +0.3 This is a standard Simplex algorithm question requiring formulation of constraints, performing tableau iterations with given row operations, and interpretation. While it involves multiple steps and careful arithmetic, it follows a completely mechanical procedure taught directly in D1 with no novel problem-solving required. The question guides students through each stage explicitly, making it slightly easier than average A-level questions. |
| Spec | 7.06a LP formulation: variables, constraints, objective function7.07a Simplex tableau: initial setup in standard format7.07b Simplex iterations: pivot choice and row operations |
| 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 |
| Answer | Marks |
|---|---|
| Maximize \(P = 50x + 80y + 60z\) | B1 |
| Answer | Marks |
|---|---|
| - \(x, y, z \geq 0\) | B3, 2, 1, 0 (4) |
| Answer | Marks | Guidance |
|---|---|---|
| Initial tableau with correct setup | B1 A1 | |
| Row operations with correct pivot choices (\(R_2\), dividing \(R_2\) by 2) | M1 A1 | |
| States correct row operations: \(R_1 - R_2\), \(R_3 - 2R_2\), \(R_4 + 80R_2\), \(R_2 ÷ 2\) | B2, 1, 0 (4) | Clear and correct pivot, divide \(R_2\) by 2 |
| Answer | Marks |
|---|---|
| Solution found after one iteration has shade of 10 units of black putty | B2, 1, 0 (2) |
| 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 | \(-\frac{20}{3}\) | 0 |
| Answer | Marks |
|---|---|
| Not optimal; a negative value in objective row | B1 / M1 A1 / A1 (4) |
| Answer | Marks |
|---|---|
| \(x = 0\), \(y = 16\frac{2}{3}\), \(z = 6\frac{2}{3}\) | M1 A1 / |
| \(P = \pm 1733.33\), \(r = 0\), \(s = 0\), \(t = 10\) | A1 / A1 (4) |
## Part (a)
Maximize $P = 50x + 80y + 60z$ | B1
Subject to:
- $x + y + 2z \leq 30$
- $x + 2y + z \leq 40$
- $3x + 2y + z \leq 50$
- $x, y, z \geq 0$ | B3, 2, 1, 0 (4)
## Part (b)
Initial tableau with correct setup | B1 A1
Row operations with correct pivot choices ($R_2$, dividing $R_2$ by 2) | M1 A1
States correct row operations: $R_1 - R_2$, $R_3 - 2R_2$, $R_4 + 80R_2$, $R_2 ÷ 2$ | B2, 1, 0 (4) | Clear and correct pivot, divide $R_2$ by 2
## Part (c)
Solution found after one iteration has shade of 10 units of black putty | B2, 1, 0 (2)
## Part (d)
### Part (i)
| 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 | -10 | 0 | 40 | 0 | 1600 | | M1 A1
| 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}$ | $R_1 ÷ \frac{3}{2}$
| y | $\frac{1}{3}$ | 1 | 0 | $-\frac{1}{3}$ | $\frac{2}{3}$ | 0 | $16\frac{2}{3}$ | $R_2 - \text{no change}$
| t | 2 | 0 | 0 | 0 | -1 | 1 | 10 | $R_4 + 20R_1$
| P | $-\frac{20}{3}$ | 0 | 0 | $\frac{20}{3}$ | $\frac{80}{3}$ | 0 | $1733\frac{1}{3}$ | | M1 A1 (4)
### Part (ii)
Not optimal; a negative value in objective row | B1 / M1 A1 / A1 (4)
### Part (iii)
$x = 0$, $y = 16\frac{2}{3}$, $z = 6\frac{2}{3}$ | M1 A1 /
$P = \pm 1733.33$, $r = 0$, $s = 0$, $t = 10$ | A1 / A1 (4)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]
\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.
\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}
\hfill \mbox{\textit{Edexcel D1 2005 Q7 [18]}}