| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2018 |
| Session | June |
| Marks | 17 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Effect of parameter changes |
| Difficulty | Challenging +1.2 This is a structured multi-part simplex algorithm question with parameter k. Parts (a)-(b) and (d) are standard mechanical applications of the simplex method. Parts (c), (e), and (g) require understanding how the parameter affects optimality conditions, which adds modest conceptual depth beyond routine execution. The question guides students through each step explicitly, making it more accessible than an unstructured optimization problem, but the parameter analysis elevates it slightly above average A-level difficulty. |
| 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\) | -2 | -6 | 1 | 1 | 0 | 0 | 40 |
| \(s\) | 2 | 3 | 2 | 0 | 1 | 0 | 80 |
| \(t\) | 1 | 2 | 2 | 0 | 0 | 1 | 50 |
| \(P\) | -4 | -2 | -k | 0 | 0 | 0 | 0 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(-2x - 6y + z \leq 40\) i.e. \(2x + 6y - z \geq -40\) or \(r = 40 + 2x + 6y - z\) | B1 | |
| \(2x + 3y + 2z \leq 80\) | B1 | |
| \(x + 2y + 2z \leq 50\) | Accept with slack variables shown |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Pivot on \(x\) column; identify pivot row using minimum ratio test: \(80/2 = 40\), \(50/1 = 50\), so \(s\)-row is pivot row | M1 | |
| \(R_s \div 2\); new \(s\)-row: \(1, \frac{3}{2}, 1, 0, \frac{1}{2}, 0, 40\) | A1 | |
| Eliminate \(x\) from other rows: \(R_r + 2R_s\); \(R_t - R_s\); \(R_P + 4R_s\) | M1 | |
| Correct tableau \(T_1\) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(T_1\) not optimal requires a negative entry in \(P\)-row; inspect \(z\) column: coefficient is \(-k+2\) (or similar); \(-k + 2 < 0 \Rightarrow k > 2\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Identify pivot column (most negative in \(P\)-row of \(T_1\)) and pivot row via ratio test | M1 | |
| Correct row operations stated | A1 | |
| Correct tableau \(T_2\) obtained | A1A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(T_2\) optimal requires all \(P\)-row entries \(\geq 0\); derive inequality e.g. \(k \leq\) some value | B1B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Values of \(x\), \(y\), \(z\) read from \(T_2\) | B1 | |
| \(P\) expressed in terms of \(k\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Range of \(P\) found using inequalities on \(k\) from (c) and (e) | M1A1 |
# Question 5:
## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| $-2x - 6y + z \leq 40$ i.e. $2x + 6y - z \geq -40$ or $r = 40 + 2x + 6y - z$ | B1 | |
| $2x + 3y + 2z \leq 80$ | B1 | |
| $x + 2y + 2z \leq 50$ | | Accept with slack variables shown |
## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| Pivot on $x$ column; identify pivot row using minimum ratio test: $80/2 = 40$, $50/1 = 50$, so $s$-row is pivot row | M1 | |
| $R_s \div 2$; new $s$-row: $1, \frac{3}{2}, 1, 0, \frac{1}{2}, 0, 40$ | A1 | |
| Eliminate $x$ from other rows: $R_r + 2R_s$; $R_t - R_s$; $R_P + 4R_s$ | M1 | |
| Correct tableau $T_1$ | A1 | |
## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| $T_1$ not optimal requires a negative entry in $P$-row; inspect $z$ column: coefficient is $-k+2$ (or similar); $-k + 2 < 0 \Rightarrow k > 2$ | B1 | |
## Part (d)
| Answer | Mark | Guidance |
|--------|------|----------|
| Identify pivot column (most negative in $P$-row of $T_1$) and pivot row via ratio test | M1 | |
| Correct row operations stated | A1 | |
| Correct tableau $T_2$ obtained | A1A1 | |
## Part (e)
| Answer | Mark | Guidance |
|--------|------|----------|
| $T_2$ optimal requires all $P$-row entries $\geq 0$; derive inequality e.g. $k \leq$ some value | B1B1 | |
## Part (f)
| Answer | Mark | Guidance |
|--------|------|----------|
| Values of $x$, $y$, $z$ read from $T_2$ | B1 | |
| $P$ expressed in terms of $k$ | B1 | |
## Part (g)
| Answer | Mark | Guidance |
|--------|------|----------|
| Range of $P$ found using inequalities on $k$ from (c) and (e) | M1A1 | |5. The initial tableau for a linear programming problem in $x , y$ and $z$ is shown below. The objective function to be maximised is $P = 4 x + 2 y + k z$, where $k$ is a positive constant.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
Basic Variable & $x$ & $y$ & $z$ & r & $s$ & $t$ & Value \\
\hline
$r$ & -2 & -6 & 1 & 1 & 0 & 0 & 40 \\
\hline
$s$ & 2 & 3 & 2 & 0 & 1 & 0 & 80 \\
\hline
$t$ & 1 & 2 & 2 & 0 & 0 & 1 & 50 \\
\hline
$P$ & -4 & -2 & -k & 0 & 0 & 0 & 0 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Using the information in the tableau, write down the three constraints as inequalities.
\item By increasing $x$, perform one complete iteration of the simplex algorithm to obtain tableau $T _ { 1 }$ and state the row operations you use.
\item Given that $T _ { 1 }$ is not optimal, find an inequality for the value of $k$.
\item Perform a second complete iteration of the simplex algorithm to obtain tableau $T _ { 2 }$ and state the row operations you use.
\item Given that $T _ { 2 }$ is optimal, find a second inequality for the value of $k$.
\item State the final value of each variable and give an expression for the final value of $P$ in terms of $k$.
\item Hence find the range of possible values of $P$.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2018 Q5 [17]}}