| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2013 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Perform one Simplex iteration |
| Difficulty | Moderate -0.5 This is a routine mechanical application of the Simplex algorithm requiring identification of pivot column (given), pivot row (ratio test), and performing row operations. While it involves fractions and multiple steps, it's a standard textbook procedure with no problem-solving or insight required—slightly easier than average due to being purely algorithmic. |
| Spec | 7.07b Simplex iterations: pivot choice and row operations7.07c Interpret simplex: values of variables, slack, and objective7.07d Simplex terminology: basic feasible solution, basic/non-basic variable |
| Basic variable | \(x\) | \(y\) | \(z\) | \(r\) | \(s\) | \(t\) | Value |
| \(r\) | \(\frac { 1 } { 2 }\) | \(- \frac { 1 } { 2 }\) | 0 | 1 | 0 | \(- \frac { 1 } { 2 }\) | 10 |
| \(s\) | \(1 \frac { 1 } { 2 }\) | \(2 \frac { 1 } { 2 }\) | 0 | 0 | 1 | \(- \frac { 1 } { 2 }\) | 5 |
| \(z\) | \(\frac { 1 } { 2 }\) | \(\frac { 1 } { 2 }\) | 1 | 0 | 0 | \(\frac { 1 } { 2 }\) | 5 |
| \(P\) | -5 | -10 | 0 | 0 | 0 | 20 | 220 |
| Answer | Marks | Guidance |
|---|---|---|
| Part (a) | \(\begin{array}{c\ | ccccccc\ |
| M1, A1, A1 | a1A1: pivot row correct including change of b.v. a2M1: (ft) One row (excluding the pivot row) correct or one column either the value, \(x\), \(s\) or \(t\) column correct; a2A1ft: Correct row operations used at least once. One column either the value, \(x\) or \(t\) column correct on the ft. a3A1: CAO. | |
| (5) | ||
| Part (b) | \(P + x + 4s + 18t = 240\) | B1 |
| (1) | ||
| Part (c) | \(P = 240 - x - 4s - 18t\) and at present \(x, s\) and \(t\) are zero. If we increase any of these the profit will decrease. | B2, 1, 0 |
| (2) | c2B1: Good explanation – dependent on the correct equation being stated in (b). | |
| Total | 8 marks |
| **Part (a)** | $\begin{array}{c\|ccccccc\|c\|c} b.v & x & y & z & r & s & t & \text{Value} & \text{Row ops} \\ \hline r & \frac{4}{5} & 0 & 0 & 1 & \frac{1}{5} & -\frac{3}{5} & 11 & R_1 + \frac{1}{5}R_2 \\ y & \frac{2}{5} & 1 & 0 & 0 & \frac{2}{5} & -\frac{1}{5} & 2 & R_2 + 2.5 \\ z & \frac{1}{5} & 0 & 1 & 0 & -\frac{1}{5} & \frac{3}{5} & 4 & R_3 - \frac{1}{5}R_2 \\ P & 1 & 0 & 0 & 0 & 4 & 18 & 240 & R_4 + 10R_2 \end{array}$ | M1, A1 | a1M1: correct pivot located, attempt to divide row. If choosing negative pivot M0M0. |
|---|---|---|---|---|---|---|---|---|---|
| | | M1, A1, A1 | a1A1: pivot row correct including change of b.v. a2M1: (ft) One row (excluding the pivot row) correct or one column either the value, $x$, $s$ or $t$ column correct; a2A1ft: Correct row operations used at least once. One column either the value, $x$ or $t$ column correct on the ft. a3A1: CAO. |
| | | **(5)** | |
| **Part (b)** | $P + x + 4s + 18t = 240$ | B1 | b1B1: CAO |
| | | **(1)** | |
| **Part (c)** | $P = 240 - x - 4s - 18t$ and at present $x, s$ and $t$ are zero. If we increase any of these the profit will decrease. | B2, 1, 0 | c2B1: Using their profit equation to make a pertinent statement. Maybe muddled, if bod give this mark only. No 'negatives' in their profit equation. |
| | | **(2)** | c2B1: Good explanation – dependent on the correct equation being stated in (b). |
| | **Total** | **8 marks** | |
---5. A three-variable linear programming problem in $x , y$ and $z$ is to be solved. The objective is to maximise the profit, $P$.\\
The following tableau is obtained.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
Basic variable & $x$ & $y$ & $z$ & $r$ & $s$ & $t$ & Value \\
\hline
$r$ & $\frac { 1 } { 2 }$ & $- \frac { 1 } { 2 }$ & 0 & 1 & 0 & $- \frac { 1 } { 2 }$ & 10 \\
\hline
$s$ & $1 \frac { 1 } { 2 }$ & $2 \frac { 1 } { 2 }$ & 0 & 0 & 1 & $- \frac { 1 } { 2 }$ & 5 \\
\hline
$z$ & $\frac { 1 } { 2 }$ & $\frac { 1 } { 2 }$ & 1 & 0 & 0 & $\frac { 1 } { 2 }$ & 5 \\
\hline
$P$ & -5 & -10 & 0 & 0 & 0 & 20 & 220 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Starting by increasing $y$, perform one complete iteration of the Simplex algorithm, to obtain a new tableau, T. State the row operations you use.
\item Write down the profit equation given by T .
\item Use the profit equation from part (b) to explain why T is optimal.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2013 Q5 [8]}}