| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Session | Specimen |
| Marks | 15 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Formulate LP from context |
| Difficulty | Standard +0.3 This is a standard LP formulation question from Further Maths Decision module. Part (a) requires translating a word problem into constraints (routine for this topic), part (b) asks for non-negativity (trivial), and parts (c)-(e) involve reading and interpreting simplex tableaux using standard rules. While this is Further Maths content, these are mechanical applications of taught procedures with no novel problem-solving required. |
| Spec | 7.06a LP formulation: variables, constraints, objective function7.07a Simplex tableau: initial setup in standard format |
| b.v. | \(x\) | \(y\) | \(z\) | \(r\) | \(s\) | \(t\) | Value |
| \(r\) | \(- \frac { 1 } { 4 }\) | 0 | \(- \frac { 1 } { 2 }\) | 1 | 0 | \(- \frac { 3 } { 4 }\) | 8 |
| \(s\) | \(\frac { 5 } { 2 }\) | 0 | 2 | 0 | 1 | \(- \frac { 1 } { 2 }\) | 92 |
| \(y\) | \(\frac { 3 } { 4 }\) | 1 | \(\frac { 1 } { 2 }\) | 0 | 0 | \(\frac { 1 } { 4 }\) | 24 |
| \(P\) | 3 | 0 | -6 | 0 | 0 | 5 | 480 |
| b.v. | \(x\) | \(y\) | \(z\) | \(r\) | \(s\) | \(t\) | Value |
| \(r\) | \(\frac { 3 } { 8 }\) | 0 | 0 | 1 | \(\frac { 1 } { 4 }\) | \(- \frac { 7 } { 8 }\) | 31 |
| \(s\) | \(\frac { 5 } { 4 }\) | 0 | 1 | 0 | \(\frac { 1 } { 2 }\) | \(- \frac { 1 } { 4 }\) | 46 |
| \(y\) | \(\frac { 1 } { 8 }\) | 1 | 0 | 0 | \(- \frac { 1 } { 4 }\) | \(\frac { 3 } { 8 }\) | 1 |
| \(P\) | \(\frac { 21 } { 2 }\) | 0 | 0 | 0 | 3 | \(\frac { 7 } { 2 }\) | 756 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Maximise \(P = 12x + 20y + 16z\) | B1 | |
| Subject to \(2x + 3y + z \leq 80\) | M1 | |
| \(4x + 2y + 3z \leq 140\) | A1 | |
| \(3x + 4y + 2z \leq 96\) | A1 | |
| \(x, y, z \geq 0\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| The values must all be integers | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Variable \(y\) entered the basic variable column... | M1 | |
| ...so \(y\) was increased first | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \((80 + 140 + 96) - (8 + 92) = 216\) plants | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| The next pivot must come from a column which has a negative value in the objective row so therefore the pivot must come from column \(z\) | M1 | |
| The pivot must be positive and the least of \(92/2 = 46\) and \(24/0.5 = 48\) so the pivot must be the 2 (from column \(z\)) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(P + 10.5x + 3s + 3.5t = 756\) so increasing \(x\), \(s\) or \(t\) will decrease profit | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Make 1 *Drama* basket and 46 *Peaceful* baskets | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| The slack variable, \(r\), associated with this type of plant, is currently at 31. Increasing the number of *Impact* plants by a further 20 would have no effect | M1 | |
| A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Correct objective function/expression (accept pence e.g. \(1200x + 2000y + 1600z\)) | B1 | Accept pounds or pence |
| Correct coefficients and correct RHS for at least one inequality | M1 | Accept any inequality or equals |
| Two correct (non-trivial) inequalities | A1 | |
| All three non-trivial inequalities correct | A1 | |
| \(x, y, z \geq 0\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| cao | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Correct reasoning that \(y\) has become a basic variable | M1 | |
| Correct deduction that \(y\) was therefore increased first | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| cao | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Correct reasoning that pivot value must come from column \(z\) | M1 | |
| Correctly deduce (from correctly stated calculations) that pivot value is the 2 in column \(z\) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| States correct objective function and mention of increasing \(x\), \(s\) or \(t\) will decrease profit | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| cao | B1 | In context so not in terms of \(y\) and \(z\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Identifies slack variable \(r\) and its current value of 31 | M1 | |
| Correct interpretation that increasing the number of Impact plants would have no effect | A1 |
# Question 5:
## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| Maximise $P = 12x + 20y + 16z$ | B1 | |
| Subject to $2x + 3y + z \leq 80$ | M1 | |
| $4x + 2y + 3z \leq 140$ | A1 | |
| $3x + 4y + 2z \leq 96$ | A1 | |
| $x, y, z \geq 0$ | B1 | |
## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| The values must all be integers | B1 | |
## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| Variable $y$ entered the basic variable column... | M1 | |
| ...so $y$ was increased first | A1 | |
## Part (d)
| Answer | Mark | Guidance |
|--------|------|----------|
| $(80 + 140 + 96) - (8 + 92) = 216$ plants | B1 | |
## Part (e)
| Answer | Mark | Guidance |
|--------|------|----------|
| The next pivot must come from a column which has a negative value in the objective row so therefore the pivot must come from column $z$ | M1 | |
| The pivot must be positive and the least of $92/2 = 46$ and $24/0.5 = 48$ so the pivot must be the 2 (from column $z$) | A1 | |
## Part (f)
| Answer | Mark | Guidance |
|--------|------|----------|
| $P + 10.5x + 3s + 3.5t = 756$ so increasing $x$, $s$ or $t$ will decrease profit | B1 | |
## Part (g)
| Answer | Mark | Guidance |
|--------|------|----------|
| Make 1 *Drama* basket and 46 *Peaceful* baskets | B1 | |
## Part (h)
| Answer | Mark | Guidance |
|--------|------|----------|
| The slack variable, $r$, associated with this type of plant, is currently at 31. Increasing the number of *Impact* plants by a further 20 would have no effect | M1 | |
| | A1 | |
# Question 5:
## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct objective function/expression (accept pence e.g. $1200x + 2000y + 1600z$) | B1 | Accept pounds or pence |
| Correct coefficients and correct RHS for at least one inequality | M1 | Accept any inequality or equals |
| Two correct (non-trivial) inequalities | A1 | |
| All three non-trivial inequalities correct | A1 | |
| $x, y, z \geq 0$ | B1 | |
## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| cao | B1 | |
## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct reasoning that $y$ has become a basic variable | M1 | |
| Correct deduction that $y$ was therefore increased first | A1 | |
## Part (d)
| Answer | Mark | Guidance |
|--------|------|----------|
| cao | B1 | |
## Part (e)
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct reasoning that pivot value must come from column $z$ | M1 | |
| Correctly deduce (from correctly stated calculations) that pivot value is the 2 in column $z$ | A1 | |
## Part (f)
| Answer | Mark | Guidance |
|--------|------|----------|
| States correct objective function and mention of increasing $x$, $s$ or $t$ will decrease profit | B1 | |
## Part (g)
| Answer | Mark | Guidance |
|--------|------|----------|
| cao | B1 | In context so not in terms of $y$ and $z$ |
## Part (h)
| Answer | Mark | Guidance |
|--------|------|----------|
| Identifies slack variable $r$ and its current value of 31 | M1 | |
| Correct interpretation that increasing the number of Impact plants would have no effect | A1 | |
---5. A garden centre makes hanging baskets to sell to its customers. Three types of hanging basket are made, Sunshine, Drama and Peaceful. The plants used are categorised as Impact, Flowering or Trailing.
Each Sunshine basket contains 2 Impact plants, 4 Flowering plants and 3 Trailing plants. Each Drama basket contains 3 Impact plants, 2 Flowering plants and 4 Trailing plants. Each Peaceful basket contains 1 Impact plant, 3 Flowering plants and 2 Trailing plants.
The garden centre can use at most 80 Impact plants, at most 140 Flowering plants and at most 96 Trailing plants each day.
The profit on Sunshine, Drama and Peaceful baskets are $\pounds 12 , \pounds 20$ and $\pounds 16$ respectively. The garden centre wishes to maximise its profit.
Let $x , y$ and $z$ be the number of Sunshine, Drama and Peaceful baskets respectively, produced each day.
\begin{enumerate}[label=(\alph*)]
\item Formulate this situation as a linear programming problem, giving your constraints as inequalities.
\item State the further restriction that applies to the values of $x , y$ and $z$ in this context.
The Simplex algorithm is used to solve this problem. After one iteration, the tableau is
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
b.v. & $x$ & $y$ & $z$ & $r$ & $s$ & $t$ & Value \\
\hline
$r$ & $- \frac { 1 } { 4 }$ & 0 & $- \frac { 1 } { 2 }$ & 1 & 0 & $- \frac { 3 } { 4 }$ & 8 \\
\hline
$s$ & $\frac { 5 } { 2 }$ & 0 & 2 & 0 & 1 & $- \frac { 1 } { 2 }$ & 92 \\
\hline
$y$ & $\frac { 3 } { 4 }$ & 1 & $\frac { 1 } { 2 }$ & 0 & 0 & $\frac { 1 } { 4 }$ & 24 \\
\hline
$P$ & 3 & 0 & -6 & 0 & 0 & 5 & 480 \\
\hline
\end{tabular}
\end{center}
\item State the variable that was increased in the first iteration. Justify your answer.
\item Determine how many plants in total are being used after only one iteration of the Simplex algorithm.
\item Explain why for a second iteration of the Simplex algorithm the 2 in the $z$ column is the pivot value.
After a second iteration, the tableau is
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
b.v. & $x$ & $y$ & $z$ & $r$ & $s$ & $t$ & Value \\
\hline
$r$ & $\frac { 3 } { 8 }$ & 0 & 0 & 1 & $\frac { 1 } { 4 }$ & $- \frac { 7 } { 8 }$ & 31 \\
\hline
$s$ & $\frac { 5 } { 4 }$ & 0 & 1 & 0 & $\frac { 1 } { 2 }$ & $- \frac { 1 } { 4 }$ & 46 \\
\hline
$y$ & $\frac { 1 } { 8 }$ & 1 & 0 & 0 & $- \frac { 1 } { 4 }$ & $\frac { 3 } { 8 }$ & 1 \\
\hline
$P$ & $\frac { 21 } { 2 }$ & 0 & 0 & 0 & 3 & $\frac { 7 } { 2 }$ & 756 \\
\hline
\end{tabular}
\end{center}
\item Use algebra to explain why this tableau is optimal.
\item State the optimal number of each type of basket that should be made.
The manager of the garden centre is able to increase the number of Impact plants available each day from 80 to 100 . She wants to know if this would increase her profit.
\item Use your final tableau to determine the effect of this increase. (You should not carry out any further calculations.)
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 Q5 [15]}}