| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | June |
| Marks | 15 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Set up initial Simplex tableau |
| Difficulty | Moderate -0.3 This is a standard D1 Simplex algorithm question requiring mechanical application of the algorithm with straightforward interpretation. While it has multiple parts (15 marks), each step follows textbook procedures: identifying slack variables, performing a pivot operation, reading off values, and checking optimality. No novel insight or complex problem-solving is required—students simply execute the learned algorithm systematically. |
| Spec | 7.07a Simplex tableau: initial setup in standard format7.07b Simplex iterations: pivot choice and row operations |
| Basic variable | \(x\) | \(y\) | \(z\) | \(r\) | \(s\) | \(t\) | Value |
| \(r\) | 4 | 5 | 10 | 1 | 0 | 0 | 140 |
| \(s\) | 2 | 1 | 4 | 0 | 1 | 0 | 60 |
| \(t\) | 1 | 2 | 3 | 0 | 0 | 1 | 60 |
| \(P\) | \(-350\) | \(-350\) | \(-650\) | 0 | 0 | 0 | 0 |
| Answer | Marks |
|---|---|
| r, s and L are unused amounts of bird seed (ints), suet block, and peanuts (in kg). That Polly has at the end of each week after she has made up and sold her packs. | B2, 1, 0 |
| Answer | Marks | Guidance |
|---|---|---|
| Basic feasible solution presented in tableau | M1, A1 | |
| b.v. | x | y |
| 2 | \(\frac{2}{5}\) | \(-\frac{1}{2}\) |
| 5 | \(⊚\left(\frac{2}{3}\right)\) | \(-1\) |
| L | \(-\frac{1}{4}\) | \(\frac{1}{4}\) |
| P | \(-90\) | \(-25\) |
| M1, A2∧, 1∧, 0 |
| Answer | Marks |
|---|---|
| \(x = 0, y = 0, z = 14, r = 0, s = 4, L = 18, P = 491\) | M1, A2∧, ∧0 |
| Answer | Marks |
|---|---|
| \(P - 90x - 25y + 65r = 9100\) (o.e.) | M1, A1∧ |
| Answer | Marks | Guidance |
|---|---|---|
| \(P = 9100 + 90x + 25y - 65r\), so increasing \(x\) or \(y\) would increase the profit | (B)∧ |
| Answer | Marks | Guidance |
|---|---|---|
| The \(\frac{2}{3}\) in the x column and 2nd (\(c\)) row. | B2∧, 1, 0 |
| Answer | Marks |
|---|---|
| 7(a)B2 | Ref L "unused" "t bird seed", suet block & peanuts". |
| B1 | Ref to "unused" or "bird seed" or "t or mundled explanation". "bad set B1" must engage with context |
| 7(b)M1 | comect pivot char |
| A1 | pivot as comect c.a.o. incl b.v. |
| M1∧ | comect row operation used (all i) – at least 1 non-zero or 1 item comect is each row. ∀ may M0 |
| A2∧ | non-pivot rows comect; –1 each row ∧ on error in pivot chare only . penalize b.v. once only |
| 7(c)M1 | 3 variables stated – must have completed b.v.+ value column (or ∫ saw up) on tableau. Any negative M0 |
| A2∧ | all 7 c.a.o (c.endore P:9100) |
| A1∧ | at least ⅓: c.a.o (c.endore P:9100) |
| 7(d)M1∧ | P, (−90x, −25y, 65r and 9100 (or i) all present and one = sign |
| A1∧ | C A O (o.e.) |
| 7(e) | B∧) stating that increasing x ⊕ y would increase p∂ft, pariably re-arenssing p∂ft equation. (Generaus. |
| B2∧ | ⅔ identified, x column and 2nd (\(c\)) row. Accept ringed in last tableau |
| B1∧ | 'bad set B1, if ∧ from there 'optim' tableau B1, |
## Part (a)
| r, s and L are unused amounts of bird seed (ints), suet block, and peanuts (in kg). That Polly has at the end of each week after she has made up and sold her packs. | B2, 1, 0 | |
## Part (b)
| Basic feasible solution presented in tableau | M1, A1 | |
| | | | |
| b.v. | x | y | z | r | s | L | value |
|---|---|---|---|---|---|---|---|
| 2 | $\frac{2}{5}$ | $-\frac{1}{2}$ | 1 | $\frac{1}{10}$ | 0 | 0 | 14 | $R_1 ÷ 10$ |
| 5 | $⊚\left(\frac{2}{3}\right)$ | $-1$ | 0 | $-\frac{3}{5}$ | 1 | 0 | 4 | $R_2 - 4R_1$ |
| L | $-\frac{1}{4}$ | $\frac{1}{4}$ | 0 | $-\frac{3}{10}$ | 0 | 1 | 18 | $R_3 - 3R_1$ |
| P | $-90$ | $-25$ | 0 | 65 | 0 | 0 | 9100 | $R_4 + 650R_1$ |
| | | | | M1, A2∧, 1∧, 0 | |
## Part (c)
| $x = 0, y = 0, z = 14, r = 0, s = 4, L = 18, P = 491$ | M1, A2∧, ∧0 | |
## Part (d)
| $P - 90x - 25y + 65r = 9100$ (o.e.) | M1, A1∧ | |
## Part (e)
| $P = 9100 + 90x + 25y - 65r$, so increasing $x$ or $y$ would increase the profit | | (B)∧ |
## Part (f)
| The $\frac{2}{3}$ in the x column and 2nd ($c$) row. | | B2∧, 1, 0 |
### Notes
| **7(a)B2** | Ref L "unused" "t bird seed", suet block & peanuts". | | |
| | B1 | Ref to "unused" or "bird seed" or "t or mundled explanation". "bad set B1" must engage with context | | |
| **7(b)M1** | comect pivot char | | |
| | A1 | pivot as comect c.a.o. incl b.v. | | |
| | M1∧ | comect row operation used (all i) – at least 1 non-zero or 1 item comect is each row. ∀ may M0 | | |
| | A2∧ | non-pivot rows comect; –1 each row ∧ on error in pivot chare only . penalize b.v. once only | | |
| **7(c)M1** | 3 variables stated – must have completed b.v.+ value column (or ∫ saw up) on tableau. Any negative M0 | | |
| | A2∧ | all 7 c.a.o (c.endore P:9100) | | |
| | A1∧ | at least ⅓: c.a.o (c.endore P:9100) | | |
| **7(d)M1∧** | P, (−90x, −25y, 65r and 9100 (or i) all present and one = sign | | |
| | A1∧ | C A O (o.e.) | | |
| **7(e)** | B∧) stating that increasing x ⊕ y would increase p∂ft, pariably re-arenssing p∂ft equation. (Generaus. | | |
| | B2∧ | ⅔ identified, x column and 2nd ($c$) row. Accept ringed in last tableau | | |
| | B1∧ | 'bad set B1, if ∧ from there 'optim' tableau B1, | | |
---Polly has a bird food stall at the local market. Each week she makes and sells three types of packs $A$, $B$ and $C$.
Pack $A$ contains 4 kg of bird seed, 2 suet blocks and 1 kg of peanuts.
Pack $B$ contains 5 kg of bird seed, 1 suet block and 2 kg of peanuts.
Pack $C$ contains 10 kg of bird seed, 4 suet blocks and 3 kg of peanuts.
Each week Polly has 140 kg of bird seed, 60 suet blocks and 60 kg of peanuts available for the packs.
The profit made on each pack of $A$, $B$ and $C$ sold is £3.50, £3.50 and £6.50 respectively. Polly sells every pack on her stall and wishes to maximise her profit, $P$ pence.
Let $x$, $y$ and $z$ be the numbers of packs $A$, $B$ and $C$ sold each week.
An initial Simplex tableau for the above situation is
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
Basic variable & $x$ & $y$ & $z$ & $r$ & $s$ & $t$ & Value \\
\hline
$r$ & 4 & 5 & 10 & 1 & 0 & 0 & 140 \\
\hline
$s$ & 2 & 1 & 4 & 0 & 1 & 0 & 60 \\
\hline
$t$ & 1 & 2 & 3 & 0 & 0 & 1 & 60 \\
\hline
$P$ & $-350$ & $-350$ & $-650$ & 0 & 0 & 0 & 0 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Explain the meaning of the variables $r$, $s$ and $t$ in the context of this question. [2]
\item Perform one complete iteration of the Simplex algorithm to form a new tableau $T$. Take the most negative number in the profit row to indicate the pivotal column. [5]
\item State the value of every variable as given by tableau $T$. [3]
\item Write down the profit equation given by tableau $T$. [2]
\item Use your profit equation to explain why tableau $T$ is not optimal. [1]
\end{enumerate}
Taking the most negative number in the profit row to indicate the pivotal column,
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{5}
\item identify clearly the location of the next pivotal element. [2]
\end{enumerate}
(Total 15 marks)
\hfill \mbox{\textit{Edexcel D1 2005 Q7 [15]}}