| Exam Board | OCR MEI |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2009 |
| Session | June |
| Marks | 20 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Linear Programming |
| Type | Simplex algorithm execution |
| Difficulty | Standard +0.8 This is a multi-part simplex algorithm question requiring setup, execution, and understanding of advanced variants (two-stage/big-M). While simplex execution is mechanical, this tests conceptual understanding of formulation, optimality conditions, and handling equality constraints. The D2 module represents Further Maths content, placing it above typical A-level. However, it's a standard textbook-style question without novel problem-solving, so not exceptionally hard for its level. |
| 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 | Marks | Guidance |
| \(a, b, c, d\) = number of acres of crops A, B, C, D respectively | B1 | |
| \(a + b \leq 20\): acres of A and B must not exceed acres of C and D; since \(c + d \leq 40 - (a+b)\), so \(a + b \leq c + d\) combined with total \(\leq 40\) gives \(a+b \leq 20\) | B1 | |
| Since maximising profit with positive coefficients, all land will be used at optimum (constraint \(\leq 40\) will be tight) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Initial tableau set up correctly with slack variables \(s_1, s_2\) | M1 | |
| Correct initial tableau | A1 | |
| Correct pivot selection (most negative in objective row) | M1 | |
| First pivot operation correct | A1 | |
| Second pivot operation correct | A1 | |
| Optimal tableau identified | M1 | |
| \(a = 20, b = 0, c = 20, d = 0\) or equivalent optimal solution | A1 | |
| Maximum profit \(= 50(20) + 40(20) = £1800\) | A1 | |
| Correct reading of solution from tableau | A1 A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Equality constraint \(a+b+c+d=40\) requires artificial variable \(r\): \(a+b+c+d+r=40\) | B1 | |
| Two-stage: Stage 1 minimise \(r\); initial tableau shown with \(r\) as basic variable | M1 A1 | |
| Description: pivot to remove \(r\) from basis, then Stage 2 optimise original objective | B1 | |
| Big-M: Add \(Mr\) to objective (minimise) or subtract from maximisation; tableau shown | M1 A1 | |
| Description: proceed with simplex, large \(M\) penalises artificial variable | B1 |
# Question 3:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $a, b, c, d$ = number of acres of crops A, B, C, D respectively | B1 | |
| $a + b \leq 20$: acres of A and B must not exceed acres of C and D; since $c + d \leq 40 - (a+b)$, so $a + b \leq c + d$ combined with total $\leq 40$ gives $a+b \leq 20$ | B1 | |
| Since maximising profit with positive coefficients, all land will be used at optimum (constraint $\leq 40$ will be tight) | B1 | |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Initial tableau set up correctly with slack variables $s_1, s_2$ | M1 | |
| Correct initial tableau | A1 | |
| Correct pivot selection (most negative in objective row) | M1 | |
| First pivot operation correct | A1 | |
| Second pivot operation correct | A1 | |
| Optimal tableau identified | M1 | |
| $a = 20, b = 0, c = 20, d = 0$ or equivalent optimal solution | A1 | |
| Maximum profit $= 50(20) + 40(20) = £1800$ | A1 | |
| Correct reading of solution from tableau | A1 A1 | |
## Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Equality constraint $a+b+c+d=40$ requires artificial variable $r$: $a+b+c+d+r=40$ | B1 | |
| **Two-stage:** Stage 1 minimise $r$; initial tableau shown with $r$ as basic variable | M1 A1 | |
| Description: pivot to remove $r$ from basis, then Stage 2 optimise original objective | B1 | |
| **Big-M:** Add $Mr$ to objective (minimise) or subtract from maximisation; tableau shown | M1 A1 | |
| Description: proceed with simplex, large $M$ penalises artificial variable | B1 | |
---3 A farmer has 40 acres of land. Four crops, A, B, C and D are available.\\
Crop A will return a profit of $\pounds 50$ per acre. Crop B will return a profit of $\pounds 40$ per acre.\\
Crop C will return a profit of $\pounds 40$ per acre. Crop D will return a profit of $\pounds 30$ per acre.\\
The total number of acres used for crops A and B must not be greater than the total number used for crops C and D.
The farmer formulates this problem as:\\
Maximise $\quad 50 a + 40 b + 40 c + 30 d$,\\
subject to $\quad a + b \leqslant 20$,\\
$a + b + c + d \leqslant 40$.\\
(i) Explain what the variables $a , b , c$ and $d$ represent.
Explain how the first inequality was obtained.\\
Explain why expressing the constraint on the total area of land as an inequality will lead to a solution in which all of the land is used.\\
(ii) Solve the problem using the simplex algorithm.
Suppose now that the farmer had formulated the problem as:\\
Maximise $\quad 50 a + 40 b + 40 c + 30 d$,\\
subject to $\quad a + b \leqslant 20$,\\
$a + b + c + d = 40$.\\
(iii) Show how to adapt this problem for solution either by the two-stage simplex method or the big-M method. In either case you should show the initial tableau and describe what has to be done next. You should not attempt to solve the problem.
\hfill \mbox{\textit{OCR MEI D2 2009 Q3 [20]}}