| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 18 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Formulate LP from context |
| Difficulty | Standard +0.3 This is a standard D1 simplex algorithm question with straightforward setup and execution. Parts (a)-(c) involve routine formulation and tableau construction (basic recall), while part (d) requires mechanical application of the simplex method following a prescribed procedure. The question is slightly easier than average because it guides students through each step, tells them which variable to increase first, and the arithmetic is manageable with only 3 variables and 3 constraints. |
| Spec | 7.06a LP formulation: variables, constraints, objective function7.06b Slack variables: converting inequalities to equations7.07a Simplex tableau: initial setup in standard format |
| Basic Variable | \(x\) | \(y\) | \(z\) | \(r\) | \(s\) | \(t\) | Value |
| \(r\) | 6 | 15 | 12 | 1 | 0 | 0 | 185 |
| \(s\) | 3 | 3 | 1 | 0 | 1 | 0 | 30 |
| \(t\) | 1 | 4 | 4 | 0 | 0 | 1 | 60 |
| \(P\) | \(-4\) | \(-9\) | \(-6\) | 0 | 0 | 0 | 0 |
| Answer | Marks |
|---|---|
| \(x + 4y + 4z \leq 60\) | A3 |
| (b) there are 3 independent variables | B1 |
| Answer | Marks |
|---|---|
| need to maximise \(I = 40x + 90y + 60z\), considering 10's of pounds gives objective function \(P - 4x - 9y - 6z = 0\), hence given tableau | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Basic Var. | \(x\) | \(y\) |
| \(r\) | \(-9\) | \(0\) |
| \(y\) | \(1\) | \(1\) |
| \(t\) | \(-3\) | \(0\) |
| \(P\) | \(5\) | \(0\) |
| M2 A2 |
| Answer | Marks | Guidance |
|---|---|---|
| Basic Var. | \(x\) | \(y\) |
| \(z\) | \(-\frac{9}{7}\) | \(0\) |
| \(y\) | \(\frac{10}{21}\) | \(1\) |
| \(t\) | \(\frac{3}{7}\) | \(0\) |
| \(P\) | \(\frac{8}{7}\) | \(0\) |
| M2 A2 | ||
| optimal solution as all values on the objective row are \(\geq 0\) | B1 | |
| (e) 0 of X, \(8\frac{1}{3}\) of Y and 5 of Z, giving \(P = 105\) so profit = £1050 | A1 | |
| (f) try integer coordinates around the optimal solution e.g. (0, 8, 5) (1, 8, 5) (0, 9, 5) etc. checking feasible and seeking optimum | B2 | (18) |
| Answer | Marks |
|---|---|
| Total | (75) |
**(a)** $6x + 15y + 12z \leq 185$
$3x + 3y + z \leq 30$
$x + 4y + 4z \leq 60$ | A3 |
**(b)** there are 3 independent variables | B1 |
**(c)** rewriting with slack variables gives
$6x + 15y + 12z + r = 185$
$3x + 3y + z + s = 30$
$x + 4y + 4z + t = 60$
need to maximise $I = 40x + 90y + 60z$, considering 10's of pounds gives objective function $P - 4x - 9y - 6z = 0$, hence given tableau | A1 |
**(d)** $\theta$ values are $12\frac{1}{3}$, 10 and 15 so pivot row is 2nd row
| Basic Var. | $x$ | $y$ | $z$ | $r$ | $s$ | $t$ | Value |
|---|---|---|---|---|---|---|---|
| $r$ | $-9$ | $0$ | $7$ | $1$ | $-5$ | $0$ | $35$ |
| $y$ | $1$ | $1$ | $\frac{1}{3}$ | $0$ | $\frac{1}{3}$ | $0$ | $10$ |
| $t$ | $-3$ | $0$ | $\frac{8}{3}$ | $0$ | $-\frac{4}{3}$ | $1$ | $20$ |
| $P$ | $5$ | $0$ | $-3$ | $0$ | $3$ | $0$ | $90$ |
| M2 A2 |
increase $z$ next, $\theta$ values are 5, 30 and $7\frac{1}{2}$ so pivot row is 1st row
| Basic Var. | $x$ | $y$ | $z$ | $r$ | $s$ | $t$ | Value |
|---|---|---|---|---|---|---|---|
| $z$ | $-\frac{9}{7}$ | $0$ | $1$ | $\frac{1}{7}$ | $-\frac{5}{7}$ | $0$ | $5$ |
| $y$ | $\frac{10}{21}$ | $1$ | $0$ | $-\frac{1}{21}$ | $\frac{4}{7}$ | $0$ | $8\frac{1}{3}$ |
| $t$ | $\frac{3}{7}$ | $0$ | $0$ | $-\frac{8}{21}$ | $\frac{4}{7}$ | $1$ | $6\frac{2}{3}$ |
| $P$ | $\frac{8}{7}$ | $0$ | $0$ | $\frac{3}{7}$ | $\frac{6}{7}$ | $0$ | $105$ |
| M2 A2 |
optimal solution as all values on the objective row are $\geq 0$ | B1 |
**(e)** 0 of X, $8\frac{1}{3}$ of Y and 5 of Z, giving $P = 105$ so profit = £1050 | A1 |
**(f)** try integer coordinates around the optimal solution e.g. (0, 8, 5) (1, 8, 5) (0, 9, 5) etc. checking feasible and seeking optimum | B2 | (18) |
---
**Total** | (75) |An engineer makes three components $X$, $Y$ and $Z$. Relevant details are as follows:
Component $X$ requires 6 minutes turning, 3 minutes machining and 1 minute finishing.
Component $Y$ requires 15 minutes turning, 3 minutes machining and 4 minutes finishing.
Component $Z$ requires 12 minutes turning, 1 minute machining and 4 minutes finishing.
The engineer gets access to 185 minutes turning, 30 minutes machining and 60 minutes finishing each day. The profits from selling components $X$, $Y$ and $Z$ are £40, £90 and £60 respectively and the engineer wishes to maximise the profit from her work each day.
Let the number of components $X$, $Y$ and $Z$ the engineer makes each day be $x$, $y$ and $z$ respectively.
\begin{enumerate}[label=(\alph*)]
\item Write down the 3 inequalities that apply in addition to $x \geq 0$, $y \geq 0$ and $z \geq 0$. [3 marks]
\item Explain why it is not appropriate to use a graphical method to solve the problem. [1 mark]
\end{enumerate}
It is decided to use the simplex algorithm to solve the problem.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{2}
\item Show that a possible initial tableau 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$ & 6 & 15 & 12 & 1 & 0 & 0 & 185 \\
$s$ & 3 & 3 & 1 & 0 & 1 & 0 & 30 \\
$t$ & 1 & 4 & 4 & 0 & 0 & 1 & 60 \\
$P$ & $-4$ & $-9$ & $-6$ & 0 & 0 & 0 & 0 \\
\hline
\end{tabular}
\end{center}
[2 marks]
\end{enumerate}
It is decided to increase $y$ first.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{3}
\item Perform sufficient complete iterations to obtain a final tableau and explain how you know that your solution is optimal. You may assume that \textit{work in progress} is allowed. [9 marks]
\item State the number of each component that should be made per day and the total daily profit that this gives, assuming that all items can be sold. [1 mark]
\item If \textit{work in progress} is not practicable, explain how you would obtain an integer solution to this problem. You are not expected to find this solution. [2 marks]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q7 [18]}}