| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | June |
| Marks | 19 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Formulate LP from context |
| Difficulty | Standard +0.3 This is a standard linear programming question requiring routine application of the Simplex algorithm. Students must formulate constraints from a table (straightforward arithmetic), write an objective function, set up the initial tableau, and perform two specified pivots. While multi-step, it follows a completely algorithmic procedure taught directly in D1 with no problem-solving insight required. The question even specifies which columns to pivot on, removing decision-making. Slightly above average difficulty only due to length and potential for arithmetic errors. |
| Spec | 7.06a LP formulation: variables, constraints, objective function7.06c Working with constraints: algebra and ad hoc methods |
| Printing (seconds) | Stamping out (seconds) | Fixing pin (seconds) | Checking (seconds) | Profit (£) | |
| Laminated | 15 | 5 | 50 | 100 | 4 |
| Metallic | 15 | 8 | 50 | 50 | 3 |
| Plastic | 30 | 10 | 50 | 20 | 1 |
| Total time available | 9000 | 3600 | 25000 | 10000 |
| Answer | Marks | Guidance |
|---|---|---|
| \(10x + 5y + 2z \leq 1000\) | B1 | \(15x + 15y + 30z \leq 9000\) |
| B1 | \(5x + 8y + 10z \leq 3600\) | |
| B1 | \(x + y + z \leq 500\) | |
| B1 | \(10x + 5y + 2z \leq 1000\) | |
| [4] |
| Answer | Marks | Guidance |
|---|---|---|
| \(x, y\) and \(z\) are non-negative | B1 | \(x \geq 0, y \geq 0\) and \(z \geq 0\) |
| [1] |
| Answer | Marks | Guidance |
|---|---|---|
| \((P =) 4x + 3y + z\) | B1 | cao |
| [1] |
| Answer | Marks | Guidance |
|---|---|---|
| \(P\) | \(x\) | \(y\) |
| 1 | -4 | -3 |
| 0 | 1 | 1 |
| 0 | 5 | 8 |
| 0 | 1 | 1 |
| 0 | 10 | 5 |
| B1 | -4 -3 -1 in objective row | |
| B1 | Correct use of slack variables | |
| M1 | 1 1 2 and 600 correct | |
| A1 | All constraint rows correct. Accept variations in order of rows and columns | |
| [4] |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | 0 | -1 |
| 0 | 0 | 0.5 |
| 0 | 0 | 5.5 |
| 0 | 0 | 0.5 |
| 0 | 1 | 0.5 |
| B1 | Correct choice of pivot from x-column | |
| M1 | [Follow through their tableau and valid pivot if possible: no negative values in RHS column and \(P\) value has not decreased] | |
| A1 | Pivot row correct | |
| A1 | Other rows correct | |
| [3] |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | 2 | 0 |
| 0 | -1 | 0 |
| 0 | -11 | 0 |
| 0 | -1 | 0 |
| 0 | 2 | 1 |
| B1 | Correct choice of pivot from y-column | |
| M1 | [Follow through their tableau and valid pivot if possible] | |
| A1 | Pivot row correct | |
| A1 | Other rows correct | |
| [3] |
| Answer | Marks | Guidance |
|---|---|---|
| Make 20000 metallic badges (and no laminated badges or plastic badges) | B1 | Interpretation of their \(x, y\) and \(z\) values in context (may imply zero entries) |
| B1 | Interpretation of their \(P\) value in context | |
| B1 | Interpretation of their slack variable values | |
| To give a profit of £600 | [3] | |
| 6000 seconds (100 min) of printing time not used, 2000 seconds (33 min 20 sec) of stamping out time not used, 15000 seconds (250 min) of fixing pin time not used. All the checking time is used | [3] |
## (i)
$15x + 15y + 30z \leq 9000$
[divide through by 15 to get $x+y+2z \leq 600$ as given]
Stamping out: $5x + 8y + 10z \leq 3600$
Fixing pin: $50x + 50y + 50z \leq 25000$
$x + y + z \leq 500$
Checking: $100x + 50y + 20z \leq 10000$
$10x + 5y + 2z \leq 1000$ | B1 | $15x + 15y + 30z \leq 9000$
| B1 | $5x + 8y + 10z \leq 3600$
| B1 | $x + y + z \leq 500$
| B1 | $10x + 5y + 2z \leq 1000$
| [4] |
## (ii)
$x, y$ and $z$ are non-negative | B1 | $x \geq 0, y \geq 0$ and $z \geq 0$
| [1] |
## (iii)
$(P =) 4x + 3y + z$ | B1 | cao
| [1] |
## (iv)
| $P$ | $x$ | $y$ | $z$ | $s$ | $t$ | $u$ | $v$ | RHS |
|---|---|---|---|---|---|---|---|---|
| 1 | -4 | -3 | -1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 2 | 1 | 0 | 0 | 0 | 600 |
| 0 | 5 | 8 | 10 | 0 | 1 | 0 | 0 | 3600 |
| 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 500 |
| 0 | 10 | 5 | 2 | 0 | 0 | 0 | 1 | 1000 |
| B1 | -4 -3 -1 in objective row
| B1 | Correct use of slack variables
| M1 | 1 1 2 and 600 correct
| A1 | All constraint rows correct. Accept variations in order of rows and columns
| [4] |
## (v)
Pivot on the 10 in the x-column
| 1 | 0 | -1 | -0.2 | 0 | 0 | 0 | 0.4 | 400 |
| 0 | 0 | 0.5 | 1.8 | 1 | 0 | 0 | -0.1 | 500 |
| 0 | 0 | 5.5 | 9 | 0 | 1 | 0 | -0.5 | 3100 |
| 0 | 0 | 0.5 | 0.8 | 0 | 0 | 1 | -0.1 | 400 |
| 0 | 1 | 0.5 | 0.2 | 0 | 0 | 0 | 0.1 | 100 |
| B1 | Correct choice of pivot from x-column
| M1 | [Follow through their tableau and valid pivot if possible: no negative values in RHS column and $P$ value has not decreased]
| A1 | Pivot row correct
| A1 | Other rows correct
| [3] |
Pivot on 0.5 in the last row of y-column
| 1 | 2 | 0 | 0.2 | 0 | 0 | 0 | 0.6 | 600 |
| 0 | -1 | 0 | 1 | 1 | 0 | 0 | -0.2 | 400 |
| 0 | -11 | 0 | 6.8 | 0 | 1 | 0 | -1.6 | 2000 |
| 0 | -1 | 0 | 0.6 | 0 | 0 | 1 | -0.2 | 300 |
| 0 | 2 | 1 | 0.4 | 0 | 0 | 0 | 0.2 | 200 |
| B1 | Correct choice of pivot from y-column
| M1 | [Follow through their tableau and valid pivot if possible]
| A1 | Pivot row correct
| A1 | Other rows correct
| [3] |
$x = 0, y = 200, z = 0, P = 600$
Make 20000 metallic badges (and no laminated badges or plastic badges) | B1 | Interpretation of their $x, y$ and $z$ values in context (may imply zero entries)
| B1 | Interpretation of their $P$ value in context
| B1 | Interpretation of their slack variable values
To give a profit of £600 | [3] |
6000 seconds (100 min) of printing time not used, 2000 seconds (33 min 20 sec) of stamping out time not used, 15000 seconds (250 min) of fixing pin time not used. All the checking time is used | [3] |
---
**Total = 19**\textit{Badgers} is a small company that makes badges to customers' designs. Each badge must pass through four stages in its production: printing, stamping out, fixing pin and checking. The badges can be laminated, metallic or plastic.
The times taken for \textbf{100 badges} of each type to pass through each of the stages and the profits that \textit{Badgers} makes on every 100 badges are shown in the table below. The table also shows the total time available for each of the production stages.
\begin{center}
\begin{tabular}{|l|c|c|c|c|c|}
\hline
& Printing (seconds) & Stamping out (seconds) & Fixing pin (seconds) & Checking (seconds) & Profit (£) \\
\hline
Laminated & 15 & 5 & 50 & 100 & 4 \\
\hline
Metallic & 15 & 8 & 50 & 50 & 3 \\
\hline
Plastic & 30 & 10 & 50 & 20 & 1 \\
\hline
Total time available & 9000 & 3600 & 25000 & 10000 & \\
\hline
\end{tabular}
\end{center}
Suppose that the company makes $x$ hundred laminated badges, $y$ hundred metallic badges and $z$ hundred plastic badges.
\begin{enumerate}[label=(\roman*)]
\item Show that the printing time leads to the constraint $x + y + 2z \leq 600$. Write down and simplify constraints for the time spent on each of the other production stages. [4]
\item What other constraint is there on the values of $x$, $y$ and $z$? [1]
\end{enumerate}
The company wants to maximise the profit from the sale of badges.
\begin{enumerate}[label=(\roman*)]
\setcounter{enumi}{2}
\item Write down an appropriate objective function, to be maximised. [1]
\item Represent \textit{Badgers}' problem as an initial Simplex tableau. [4]
\item Use the Simplex algorithm, pivoting first on a value chosen from the $x$-column and then on a value chosen from the $y$-column. Interpret your solution and the values of the slack variables in the context of the original problem. [9]
\end{enumerate}
\hfill \mbox{\textit{OCR D1 2009 Q5 [19]}}