| Exam Board | OCR MEI |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2013 |
| Session | June |
| Marks | 20 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Complete Simplex solution |
| Difficulty | Standard +0.8 This is a comprehensive multi-part Simplex algorithm question requiring constraint formulation, tableau setup, multiple iterations of the algorithm, interpretation, modifications (removing variables, adding equality constraints), and consideration of integer programming. While the individual steps are methodical, the length, multiple modifications, and requirement to handle two-stage/big-M method make this substantially harder than a standard A-level question, though still within the scope of Further Maths D2 content. |
| Spec | 7.06a LP formulation: variables, constraints, objective function7.06b Slack variables: converting inequalities to equations7.06c Working with constraints: algebra and ad hoc methods7.06d Graphical solution: feasible region, two variables7.07a Simplex tableau: initial setup in standard format7.07b Simplex iterations: pivot choice and row operations7.07c Interpret simplex: values of variables, slack, and objective |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| materials: \(15b + 6c + 2f \leq 100\) | B1 | cao |
| time: \(4b + 2c + \frac{1}{2}f \leq 30\) | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Objective row correct (cao) | B1 | objective … cao |
| Remaining rows correct (cao) | B1 | rest … cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| First pivot identified | B1 | pivot |
| First iteration performed | M1 | first iteration |
| First iteration correct (cao) | A1 | cao |
| Second pivot identified | B1 | pivot |
| Second iteration performed | M1 | second iteration |
| Second iteration correct (cao) | A1 | cao |
| Non-integer solution: \(3\frac{1}{3}\) bowls and \(8\frac{1}{3}\) candleholders using all budget and all available time | B1 | solution ft |
| Income of £225 | B1 | resources and income cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Any valid simplex approach (may omit "b" column) | M1 | Might miss out "b" col. Any valid approach using simplex |
| Make 15 candleholders. Same income as before, but £10 materials remain (integer solution this time). | A1, A1 | solution ft; comment cao |
| Answer | Marks | Guidance |
|---|---|---|
| \end{array}\] | B1 | new objective |
| B1 | \(\text{bowls} \leq 4\) | |
| B1 | \(\text{bowls} \geq 4\) |
| Answer | Marks | Guidance |
|---|---|---|
| \end{array}\] | B1 | objective |
| B1 | \(\text{bowls} \leq 4\) | |
| B1 | \(\text{bowls} \geq 4\) | |
| Special case ... Candidates may ignore the instruction and set up an ordinary simplex with \(b\) excluded and with reduced resources of £40 and 14 hours. | SC2 | \(-1\) each error |
| Answer | Marks |
|---|---|
| 4 bowls, 6 candle holders and 2 key fobs. (Uses all of the budget. Leaves an hour to spare. Gives an income of £216.) | B1 |
| Answer | Marks |
|---|---|
| There might be another solution with less income, but even less expenditure. | B1 |
## Question 4:
### Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| materials: $15b + 6c + 2f \leq 100$ | B1 | cao |
| time: $4b + 2c + \frac{1}{2}f \leq 30$ | B1 | cao |
**Total: [2]**
### Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Objective row correct (cao) | B1 | objective … cao |
| Remaining rows correct (cao) | B1 | rest … cao |
**Total: [2]**
### Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| First pivot identified | B1 | pivot |
| First iteration performed | M1 | first iteration |
| First iteration correct (cao) | A1 | cao |
| Second pivot identified | B1 | pivot |
| Second iteration performed | M1 | second iteration |
| Second iteration correct (cao) | A1 | cao |
| Non-integer solution: $3\frac{1}{3}$ bowls and $8\frac{1}{3}$ candleholders using all budget and all available time | B1 | solution ft |
| Income of £225 | B1 | resources and income cao |
**Total: [8]**
### Part (iv)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Any valid simplex approach (may omit "b" column) | M1 | Might miss out "b" col. Any valid approach using simplex |
| Make 15 candleholders. Same income as before, but £10 materials remain (integer solution this time). | A1, A1 | solution ft; comment cao |
**Total: [3]**
## Question 4:
### Part (v):
**Two-phase method:**
$$\begin{array}{ccccccccccc}
A & I & b & c & f & s1 & s2 & s3 & s4 & a & \text{RHS} \\
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 4 \\
0 & 1 & -30 & -15 & -3 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 15 & 6 & 2 & 1 & 0 & 0 & 0 & 0 & 100 \\
0 & 0 & 4 & 2 & \frac{1}{2} & 0 & 1 & 0 & 0 & 0 & 30 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 4 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 4
\end{array}$$ | B1 | new objective |
| B1 | $\text{bowls} \leq 4$ |
| B1 | $\text{bowls} \geq 4$ |
**OR Big-M method:**
$$\begin{array}{ccccccccc}
I & b & c & f & s1 & s2 & s3 & s4 & \text{RHS} \\
1 & -30-M & -15 & -3 & 0 & 0 & 0 & M & -4M \\
0 & 15 & 6 & 2 & 1 & 0 & 0 & 0 & 100 \\
0 & 4 & 2 & \frac{1}{2} & 0 & 1 & 0 & 0 & 30 \\
0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 4 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & -1 & 4
\end{array}$$ | B1 | objective |
| B1 | $\text{bowls} \leq 4$ |
| B1 | $\text{bowls} \geq 4$ |
Special case ... Candidates may ignore the instruction and set up an ordinary simplex with $b$ excluded and with reduced resources of £40 and 14 hours. | SC2 | $-1$ each error |
**[3]**
---
### Part (vi):
4 bowls, 6 candle holders and 2 key fobs. (Uses all of the budget. Leaves an hour to spare. Gives an income of £216.) | B1 | |
**[1]**
---
### Part (vii):
There might be another solution with less income, but even less expenditure. | B1 | |
**[1]**4 Colin has a hobby from which he makes a small income. He makes bowls, candle holders and key fobs.\\
The materials he uses include wood, metal parts, polish and sandpaper. They cost, on average, $\pounds 15$ per bowl, $\pounds 6$ per candle holder and $\pounds 2$ per key fob. Colin has a monthly budget of $\pounds 100$ for materials.
Colin spends no more than 30 hours per month on manufacturing these objects. Each bowl takes 4 hours, each candle holder takes 2 hours and each key fob takes half an hour.\\
(i) Let $b$ be the number of bowls Colin makes in a month, $c$ the number of candle holders and $f$ the number of key fobs. Write out, in terms of these variables, two constraints corresponding to the limit on monthly expenditure on materials, and to the limit on Colin's time.
Colin sells the objects at craft fairs. He charges $\pounds 30$ for a bowl, $\pounds 15$ for a candle holder and $\pounds 3$ for a key fob.\\
(ii) Set up an initial simplex tableau for the problem of maximising Colin's monthly income subject to your constraints from part (i), assuming that he sells all that he produces.\\
(iii) Use the simplex algorithm to solve your LP, and interpret the solution from the simplex algorithm.
Over a spell of several months Colin finds it difficult to sell bowls so he stops making them.\\
(iv) Modify and solve your LP, using simplex, to find how many candle holders and how many key fobs he should make, and interpret your solution.
At the next craft fair Colin takes an order for 4 bowls. He promises to make exactly 4 bowls in the next month.\\
(v) Set up this modified problem either as an application of two-stage simplex, or as an application of the big-M method. You are not required to solve the problem.
The solution now is for Colin to produce 4 bowls, $6 \frac { 2 } { 3 }$ candle holders and no key fobs.\\
(vi) What is Colin's best integer solution to the problem?\\
(vii) Your answer to part (vi) is not necessarily the integer solution giving the maximum profit for Colin. Explain why.
\hfill \mbox{\textit{OCR MEI D2 2013 Q4 [20]}}