| Exam Board | OCR MEI |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2011 |
| Session | June |
| Marks | 20 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Two-stage Simplex method |
| Difficulty | Challenging +1.2 This is a standard two-stage simplex problem with straightforward formulation and interpretation. While it requires multiple steps (formulation, standard simplex, two-stage method, interpretation), each component follows textbook procedures without requiring novel insight. The context is accessible and the constraints are simple, making it slightly above average difficulty due to length and the two-stage requirement, but well within the scope of routine D2 examination questions. |
| Spec | 7.06a LP formulation: variables, constraints, objective function7.06b Slack variables: converting inequalities to equations7.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 | Mark | Guidance |
| Definition of variables | B1 | needs to say "number of" |
| Maximise \(5x + 9y + 15z\) | B1 | objective |
| Subject to \(x + 2y + 4z \leq 60\) and \(15x + 25y + 40z \leq 700\) | B1 | constraints |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Correct initial tableau with two slack variables | M1, A1 | ft |
| First iteration with correct pivot identified | M1, A1 | ft; identifying correct pivot |
| Second iteration with correct pivot identified | M1, A1 | ft; identifying correct pivot |
| Identification of basic variables (\(y\) and \(z\)) | B1 | ft |
| Values including objective | B1 | ft |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Final simplex tableau with all correct entries including new objective row | B1 | \(\geq\) row |
| New objective row correct | B1 | new objective |
| Pivot operation correct | M1 | pivot |
| Objectives cao (correct answer only) | A1 | objectives cao |
| Constraints cao for basic variables | A1 | constraints cao for basic variables |
| Answer | Marks | Guidance |
|---|---|---|
| P | x | y |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
| 0 | 0 | 1 |
| 0 | 0 | 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(x=5,\ y=15,\ z=6\) at £250000 | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(x=8,\ y=12,\ z=7\) is feasible | B1 | |
| Gives £253000 | B1 | |
| IP solution need not be "near" to LP solution | B1 |
# Question 4:
## Part (i)
| Answer | Mark | Guidance |
|--------|------|----------|
| Definition of variables | B1 | needs to say "number of" |
| Maximise $5x + 9y + 15z$ | B1 | objective |
| Subject to $x + 2y + 4z \leq 60$ and $15x + 25y + 40z \leq 700$ | B1 | constraints |
## Part (ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct initial tableau with two slack variables | M1, A1 | ft |
| First iteration with correct pivot identified | M1, A1 | ft; identifying correct pivot |
| Second iteration with correct pivot identified | M1, A1 | ft; identifying correct pivot |
| Identification of basic variables ($y$ and $z$) | B1 | ft |
| Values including objective | B1 | ft |
## Question (iii):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Final simplex tableau with all correct entries including new objective row | B1 | $\geq$ row |
| New objective row correct | B1 | new objective |
| Pivot operation correct | M1 | pivot |
| Objectives cao (correct answer only) | A1 | objectives cao |
| Constraints cao for basic variables | A1 | constraints cao for basic variables |
**Final tableau (condensed form):**
| P | x | y | z | s1 | s2 | s3 | a | RHS |
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 3/4 | 3/10 | 1/4 | -1/4 | 253.75 |
| 0 | 0 | 0 | 1 | 5/4 | -1/10 | -1/4 | 1/4 | 6.25 |
| 0 | 0 | 1 | 0 | -2 | 1/5 | 1 | -1 | 15 |
| 0 | 0 | 1 | 0 | 0 | 0 | -1 | 1 | 5 |
*Note: If working from scratch, M1 for first pivot, A1 for final objective row(s) and A1 for final constraint rows.*
---
## Question (iv):
| Answer/Working | Marks | Guidance |
|---|---|---|
| $x=5,\ y=15,\ z=6$ at £250000 | B1 | |
---
## Question (v):
| Answer/Working | Marks | Guidance |
|---|---|---|
| $x=8,\ y=12,\ z=7$ is feasible | B1 | |
| Gives £253000 | B1 | |
| IP solution need not be "near" to LP solution | B1 | |4 A small alpine hotel is planned. Permission has been obtained for no more than 60 beds, and these can be accommodated in rooms containing one, two or four beds.
The total floor areas needed are $15 \mathrm {~m} ^ { 2 }$ for a one-bed room, $25 \mathrm {~m} ^ { 2 }$ for a two-bed room and $40 \mathrm {~m} ^ { 2 }$ for a four-bed room. The total floor area of the bedrooms must not exceed $700 \mathrm {~m} ^ { 2 }$.
Marginal profit contributions per annum, in thousands of euros, are estimated to be 5 for a one-bed room, 9 for a two-bed room and 15 for a four-bed room.\\
(i) Formulate a linear programming problem to find the mix of rooms which will maximise the profit contribution within the two constraints.\\
(ii) Use the simplex algorithm to solve the problem, and interpret your solution.
It is decided that, for marketing reasons, at least 5 one-bed rooms must be provided.\\
(iii) Solve this modified problem using either the two-stage simplex method or the big-M method. You may wish to adapt your final tableau from part (ii) to produce an initial tableau, but you are not required to do so.\\
(iv) The simplex solution to the revised problem is to provide 5 one-bed rooms, 15 two-bed rooms and 6.25 four-bed rooms, giving a profit contribution of $€ 253750$. Interpret this solution in terms of the real world problem.\\
(v) Compare the following solution to your answer to part (iv): 8 one-bed rooms, 12 two-bed rooms and 7 four-bed rooms. Explain your findings.
\hfill \mbox{\textit{OCR MEI D2 2011 Q4 [20]}}