| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2013 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Complete Simplex solution |
| Difficulty | Standard +0.8 This is a multi-stage Simplex algorithm problem requiring interpretation of a partially-completed tableau, identification of the pivot variable from a previous iteration, execution of multiple pivot operations with explicit row operations, and interpretation of the final solution. While the mechanical steps are procedural, the question demands careful attention to detail across multiple iterations, correct identification of pivot elements, and accurate arithmetic throughout—more demanding than standard single-iteration exercises but still within the structured D2 syllabus framework. |
| Spec | 7.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\) | - 1 | 2 | 0 | 1 | 0 | 1 | 8 |
| \(s\) | - 1 | 3 | 0 | 0 | 1 | 1 | 22 |
| \(z\) | - 2 | 1 | 1 | 0 | 0 | 1 | 11 |
| \(P\) | 2 | - 5 | 0 | 0 | 0 | \(\frac { 1 } { 2 }\) | 15 |
| Answer | Marks | Guidance |
|---|---|---|
| (a) Variable z was increased first, since it has become a basic variable. | B1 | (1) |
| Answer | Marks | Guidance |
|---|---|---|
| b.v | x | y |
| r | -1 | 2 |
| s | -1 | 3 |
| z | -2 | 1 |
| P | 2 | -5 |
| Answer | Marks | Guidance |
|---|---|---|
| b.v | X | y |
| y | \(-\frac{1}{2}\) | 1 |
| s | \(\frac{1}{2}\) | 0 |
| z | \(-\frac{3}{2}\) | 0 |
| P | \(-\frac{1}{2}\) | 0 |
| Answer | Marks | Guidance |
|---|---|---|
| b.v | X | y |
| y | 0 | 1 |
| x | 1 | 0 |
| z | 0 | 0 |
| P | 0 | 0 |
| 3M1A1ft 4M1A1 | (4) | |
| (c) \(P = 45\); \(x = 20\); \(y = 14\); \(z = 37\); \(r = s = t = 0\). | M1 A1 | (2) Total 11 |
**(a)** Variable z was increased first, since it has become a basic variable. | B1 | (1)
**(b)** First tableau:
| b.v | x | y | z | r | s | t | value |
|---|---|---|---|---|---|---|---|
| r | -1 | 2 | 0 | 1 | 0 | 1 | 8 |
| s | -1 | 3 | 0 | 0 | 1 | 1 | 22 |
| z | -2 | 1 | 1 | 0 | 0 | 1 | 11 |
| P | 2 | -5 | 0 | 0 | 0 | $\frac{1}{2}$ | 15 |
Second tableau:
| b.v | X | y | z | r | s | t | value | row ops |
|---|---|---|---|---|---|---|---|---|
| y | $-\frac{1}{2}$ | 1 | 0 | $\frac{1}{2}$ | 0 | $\frac{1}{2}$ | 4 | $R_1 \div 2$ |
| s | $\frac{1}{2}$ | 0 | 0 | $-\frac{3}{2}$ | 1 | $-\frac{1}{2}$ | 10 | $R_2 - 3R_1$ |
| z | $-\frac{3}{2}$ | 0 | 1 | $-\frac{1}{2}$ | 0 | $\frac{1}{2}$ | 7 | $R_3 - R_1$ |
| P | $-\frac{1}{2}$ | 0 | 0 | $\frac{5}{2}$ | 0 | 3 | 35 | $R_4 + 5R_1$ |
Third tableau:
| b.v | X | y | z | r | s | t | value | row ops |
|---|---|---|---|---|---|---|---|---|
| y | 0 | 1 | 0 | -1 | 1 | 0 | 14 | $R_1 +\frac{1}{2}R_2$ |
| x | 1 | 0 | 0 | -3 | 2 | -1 | 20 | $R_2 \div \frac{1}{2}$ |
| z | 0 | 0 | 1 | -5 | 3 | -1 | 37 | $R_3 +\frac{3}{2}R_2$ |
| P | 0 | 0 | 0 | 1 | 1 | $\frac{5}{2}$ | 45 | $R_4 +\frac{1}{2}R_2$ | | 1M1A1 2M1A1 | (4)
| 3M1A1ft 4M1A1 | (4)
**(c)** $P = 45$; $x = 20$; $y = 14$; $z = 37$; $r = s = t = 0$. | M1 A1 | (2) Total 11
a1B1 Identifies z, refers to basic variable.
b1M1 Correct pivot located, attempt to divide row. If choosing negative pivot M0M0.
b1A1 CAO pivot row correct including change of b.v.
b2M1 (ft) Correct row operations used at least once, column x, r, t or value correct.
b2A1 CAO including row operations
b3M1 Their correct pivot located, attempt to divide row. If choosing negative pivot M0M0.
b3A1ft pivot row correct including change of b.v.
b4M1 (ft) Correct row operations used at least once, column r, s, t or value correct.
b4A1 CAO
c1M1 Their correct values stated for at least P, x, y, z from their 'optimal' iteration. No negatives. Two M marks in part (b) must have been awarded
c1A1 CAO for all 7 values.
---5. In solving a three-variable maximising linear programming problem, the following tableau was obtained after the first iteration.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | c | }
\hline
Basic variable & $x$ & $y$ & $z$ & $r$ & $s$ & $t$ & Value \\
\hline
$r$ & - 1 & 2 & 0 & 1 & 0 & 1 & 8 \\
\hline
$s$ & - 1 & 3 & 0 & 0 & 1 & 1 & 22 \\
\hline
$z$ & - 2 & 1 & 1 & 0 & 0 & 1 & 11 \\
\hline
$P$ & 2 & - 5 & 0 & 0 & 0 & $\frac { 1 } { 2 }$ & 15 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item State which variable was increased first, giving a reason for your answer.
\item Solve this linear programming problem. Make your method clear by stating the row operations you use.
\item State the final value of the objective function and the final values of each variable.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2013 Q5 [11]}}