| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2019 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Complete Simplex solution |
| Difficulty | Standard +0.3 This is a standard D2 simplex algorithm question requiring routine mechanical steps: setting up the initial tableau with slack variables, performing one pivot iteration using given rules, reading off values, and recognizing that negative coefficients in the profit row with no positive entries in that column indicate unboundedness. While multi-step, it follows a completely algorithmic procedure taught explicitly in the syllabus with no problem-solving or insight required. |
| 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\) | 0 | 2 | -3 | 1 | 0 | 0 | 30 |
| \(s\) | 0 | 13 | -2 | 0 | 1 | 3 | 300 |
| \(x\) | 1 | 4 | -1 | 0 | 0 | 1 | 80 |
| \(P\) | 0 | 5 | -3 | 0 | 0 | 2 | 160 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \(\begin{array}{c\ | ccccccc} \text{b.v.} & x & y & z & r & s & t & \text{value} \\ r & 0 & 2 & -3 & 1 & 0 & 0 & 30 \\ s & -3 & 1 & 1 & 0 & 1 & 0 & 60 \\ t & 1 & 4 & -1 & 0 & 0 & 1 & 80 \\ P & -2 & -3 & -1 & 0 & 0 & 0 & 0 \end{array}\) | M1 A1 |
| B1 (3) | b.v. column correct |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Pivot on 2 in column \(y\); \(R_1 \div 2\) | M1 | Correct pivot located (2 in column \(y\)), attempt to divide row |
| \(\begin{array}{c\ | ccccccc\ | c} \text{b.v.} & x & y & z & r & s & t & \text{value} & \text{row ops} \\ y & 0 & 1 & -\frac{3}{2} & \frac{1}{2} & 0 & 0 & 15 & R_1 \div 2 \end{array}\) |
| \(\begin{array}{c\ | ccccccc\ | c} s & -3 & 0 & \frac{5}{2} & -\frac{1}{2} & 1 & 0 & 45 & R_2 - R_1 \end{array}\) |
| \(\begin{array}{c\ | ccccccc\ | c} t & 1 & 0 & 5 & -2 & 0 & 1 & 20 & R_3 - 4R_1 \end{array}\) |
| \(\begin{array}{c\ | ccccccc\ | c} P & -2 & 0 & -\frac{11}{2} & \frac{3}{2} & 0 & 0 & 45 & R_4 + 3R_1 \end{array}\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \(P - 2x - \frac{11}{2}z + \frac{3}{2}r = 45\) | B1ft | Follow their profit equation from (b) dependent on scoring both M marks in (b) |
| \(r = 0,\ s = 45,\ t = 20\) | B1 (2) | CAO (no follow through) for slack variables |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| All values in the (next) pivot column (the \(z\) column) are negative and so no further iterations can occur or no viable pivot. | B1 (1) | CAO |
# Question 5:
## Part (a):
| Answer/Working | Mark | Guidance |
|---|---|---|
| $\begin{array}{c\|ccccccc} \text{b.v.} & x & y & z & r & s & t & \text{value} \\ r & 0 & 2 & -3 & 1 & 0 & 0 & 30 \\ s & -3 & 1 & 1 & 0 & 1 & 0 & 60 \\ t & 1 & 4 & -1 & 0 & 0 & 1 & 80 \\ P & -2 & -3 & -1 & 0 & 0 & 0 & 0 \end{array}$ | M1 A1 | Any one row correct (but ignore b.v. column). All four rows correct (but ignore b.v. column) |
| | B1 **(3)** | b.v. column correct |
## Part (b):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Pivot on 2 in column $y$; $R_1 \div 2$ | M1 | Correct pivot located (2 in column $y$), attempt to divide row |
| $\begin{array}{c\|ccccccc\|c} \text{b.v.} & x & y & z & r & s & t & \text{value} & \text{row ops} \\ y & 0 & 1 & -\frac{3}{2} & \frac{1}{2} & 0 & 0 & 15 & R_1 \div 2 \end{array}$ | A1 | Pivot row correct including change of b.v. |
| $\begin{array}{c\|ccccccc\|c} s & -3 & 0 & \frac{5}{2} & -\frac{1}{2} & 1 & 0 & 45 & R_2 - R_1 \end{array}$ | M1 | All values in one of the non-pivot rows correct or one of the non zero and one columns ($x, z, r$ or value) correct following through their choice of pivot from column $y$ |
| $\begin{array}{c\|ccccccc\|c} t & 1 & 0 & 5 & -2 & 0 & 1 & 20 & R_3 - 4R_1 \end{array}$ | A1ft | Row operations used correctly at least twice |
| $\begin{array}{c\|ccccccc\|c} P & -2 & 0 & -\frac{11}{2} & \frac{3}{2} & 0 & 0 & 45 & R_4 + 3R_1 \end{array}$ | A1 **(5)** | CAO – no follow through – all values and row operations correctly stated |
## Part (c):
| Answer/Working | Mark | Guidance |
|---|---|---|
| $P - 2x - \frac{11}{2}z + \frac{3}{2}r = 45$ | B1ft | Follow their profit equation from (b) dependent on scoring both M marks in (b) |
| $r = 0,\ s = 45,\ t = 20$ | B1 **(2)** | CAO (no follow through) for slack variables |
## Part (d):
| Answer/Working | Mark | Guidance |
|---|---|---|
| All values in the (next) pivot column (the $z$ column) are negative and so no further iterations can occur or no viable pivot. | B1 **(1)** | CAO |
**Total: 11 marks**5. A linear programming problem in $x , y$ and $z$ is described as follows.
Maximise $P = 2 x + 3 y + z$\\
subject to $\quad 2 y - 3 z \leqslant 30$
$$\begin{array} { r }
- 3 x + y + z \leqslant 60 \\
x + 4 y - z \leqslant 80
\end{array}$$
\begin{enumerate}[label=(\alph*)]
\item Complete the initial tableau in the answer book for this linear programming problem.\\
(3)
\item Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the simplex algorithm to obtain a new tableau, T. Make your method clear by stating the row operations you use.\\
(5)
\item Write down the profit equation given by T and state the values of the slack variables given by T .
The following tableau is obtained after further iterations.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
Basic variable & $x$ & $y$ & $z$ & $r$ & $s$ & $t$ & Value \\
\hline
$r$ & 0 & 2 & -3 & 1 & 0 & 0 & 30 \\
\hline
$s$ & 0 & 13 & -2 & 0 & 1 & 3 & 300 \\
\hline
$x$ & 1 & 4 & -1 & 0 & 0 & 1 & 80 \\
\hline
$P$ & 0 & 5 & -3 & 0 & 0 & 2 & 160 \\
\hline
\end{tabular}
\end{center}
\item Explain why no optimal solution can be found by applying the simplex algorithm to the above tableau.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2019 Q5 [11]}}