| Exam Board | OCR MEI |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2014 |
| Session | June |
| Marks | 20 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Interpret optimal tableau |
| Difficulty | Standard +0.3 This is a standard simplex algorithm question requiring setup interpretation, routine iterations following the algorithm mechanically, and basic interpretation of the optimal tableau including degeneracy. Part (iv) on two-stage simplex setup is bookwork. While multi-part, each component is straightforward application of learned procedures without novel problem-solving. |
| 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 |
| P | a | b | c | s 1 | s 2 | s 3 | RHS |
| 1 | - 4 | - 3 | - 1 | 0 | 0 | 0 | 0 |
| 0 | 10 | 5 | 12 | 1 | 0 | 0 | 12000 |
| 0 | 5 | 5 | 7 | 0 | 1 | 0 | 12000 |
| 0 | 5 | 3 | 5 | 0 | 0 | 1 | 9000 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Let \(a\) be the number of kg of A ... | B1 | variable defs. |
| Line \(1 \Leftrightarrow \max(7-3)a+(5-2)b+(4-3)c \Leftrightarrow 4a+3b+c\) | B1 | objective |
| B1 | \((7-3)\)... | |
| Line \(2 \Leftrightarrow 10a+5b+12c \leq 12000\) (availability of X) | B1 | identifying constraints |
| Line \(3 \Leftrightarrow 5a+5b+7c \leq 12000\) (availability of Y) | B1 | LHS (used) |
| Line \(4 \Leftrightarrow 5a+3b+5c \leq 9000\) (availability of Z) | B1 | \(\leq\) + RHS (available) |
| [6] |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Initial tableau with P, a, b, c, s1, s2, s3, RHS: rows \((1,-4,-3,-1,0,0,0,0)\); \((0,10,5,12,1,0,0,12000)\); \((0,5,5,7,0,1,0,12000)\); \((0,5,3,5,0,0,1,9000)\) | B1 | Pivot |
| Second tableau rows: \((1,0,-1,3.8,0.4,0,0,4800)\); \((0,1,0.5,1.2,0.1,0,0,1200)\); \((0,0,2.5,1,-0.5,1,0,6000)\); \((0,0,0.5,-1,-0.5,0,1,3000)\) | M1A1 | |
| Final tableau rows: \((1,2,0,6.2,0.6,0,0,7200)\); \((0,2,1,2.4,0.2,0,0,2400)\); \((0,-5,0,-5,-1,1,0,0)\); \((0,-1,0,-2.2,-0.6,0,1,1800)\) | B1 | Pivot \(\checkmark\) |
| M1 | ||
| A1 | cao | |
| Make 2400 kg of B | B1 | must refer to kg |
| at a profit of £7200 with 1.8 kg of Z left | B1 | |
| [8] |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Either... It means that the second constraint is coincidentally exactly satisfied at the solution, or... It means that product A is in the solution, but at zero value. (Candidates may refer to degeneracy, which will earn the mark.) | B1 | |
| [1] |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| New tableau with Q, P, a, b, c, s1, s2, s3, s4, f, RHS: \((1,0,1,0,0,0,0,0,-1,0,500)\); \((0,1,-4,-3,-1,0,0,0,0,0,0)\); \((0,0,10,5,12,1,0,0,0,0,12000)\); \((0,0,5,5,7,0,1,0,0,0,12000)\); \((0,0,5,3,5,0,0,1,0,0,9000)\); \((0,0,1,0,0,0,0,0,-1,1,500)\) | B1 | new objective |
| B1 | surplus+artificial | |
| B1 | new constraint | |
| Minimise Q until 0 (if feasible). Then drop Q and f and proceed to optimum. | B1 | |
| B1 | ||
| Allow up to 3 out of 5 for big M. | ||
| [5] |
# Question 3(i):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Let $a$ be the number of kg of A ... | B1 | variable defs. |
| Line $1 \Leftrightarrow \max(7-3)a+(5-2)b+(4-3)c \Leftrightarrow 4a+3b+c$ | B1 | objective |
| | B1 | $(7-3)$... |
| Line $2 \Leftrightarrow 10a+5b+12c \leq 12000$ (availability of X) | B1 | identifying constraints |
| Line $3 \Leftrightarrow 5a+5b+7c \leq 12000$ (availability of Y) | B1 | LHS (used) |
| Line $4 \Leftrightarrow 5a+3b+5c \leq 9000$ (availability of Z) | B1 | $\leq$ + RHS (available) |
| **[6]** | | |
---
# Question 3(ii):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Initial tableau with P, a, b, c, s1, s2, s3, RHS: rows $(1,-4,-3,-1,0,0,0,0)$; $(0,10,5,12,1,0,0,12000)$; $(0,5,5,7,0,1,0,12000)$; $(0,5,3,5,0,0,1,9000)$ | B1 | Pivot |
| Second tableau rows: $(1,0,-1,3.8,0.4,0,0,4800)$; $(0,1,0.5,1.2,0.1,0,0,1200)$; $(0,0,2.5,1,-0.5,1,0,6000)$; $(0,0,0.5,-1,-0.5,0,1,3000)$ | M1A1 | |
| Final tableau rows: $(1,2,0,6.2,0.6,0,0,7200)$; $(0,2,1,2.4,0.2,0,0,2400)$; $(0,-5,0,-5,-1,1,0,0)$; $(0,-1,0,-2.2,-0.6,0,1,1800)$ | B1 | Pivot $\checkmark$ |
| | M1 | |
| | A1 | cao |
| Make 2400 kg of B | B1 | must refer to kg |
| at a profit of £7200 with 1.8 kg of Z left | B1 | |
| **[8]** | | |
---
# Question 3(iii):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Either... It means that the second constraint is coincidentally exactly satisfied at the solution, or... It means that product A is in the solution, but at zero value. (Candidates may refer to degeneracy, which will earn the mark.) | B1 | |
| **[1]** | | |
---
# Question 3(iv):
| Answer | Marks | Guidance |
|--------|-------|----------|
| New tableau with Q, P, a, b, c, s1, s2, s3, s4, f, RHS: $(1,0,1,0,0,0,0,0,-1,0,500)$; $(0,1,-4,-3,-1,0,0,0,0,0,0)$; $(0,0,10,5,12,1,0,0,0,0,12000)$; $(0,0,5,5,7,0,1,0,0,0,12000)$; $(0,0,5,3,5,0,0,1,0,0,9000)$; $(0,0,1,0,0,0,0,0,-1,1,500)$ | B1 | new objective |
| | B1 | surplus+artificial |
| | B1 | new constraint |
| Minimise Q until 0 (if feasible). Then drop Q and f and proceed to optimum. | B1 | |
| | B1 | |
| Allow up to 3 out of 5 for big M. | | |
| **[5]** | | |
---3 Three products, A, B and C are to be made.\\
Three supplements are included in each product. Product A has 10 g per kg of supplement $\mathrm { X } , 5 \mathrm {~g}$ per kg of supplement Y and 5 g per kg of supplement Z .
Product B has 5 g per kg of supplement $\mathrm { X } , 5 \mathrm {~g}$ per kg of supplement Y and 3 g per kg of supplement Z .\\
Product C has 12 g per kg of supplement $\mathrm { X } , 7 \mathrm {~g}$ per kg of supplement Y and 5 g per kg of supplement Z .\\
There are 12 kg of supplement X available, 12 kg of supplement Y , and 9 kg of supplement Z .\\
Product A will sell at $\pounds 7$ per kg and costs $\pounds 3$ per kg to produce. Product B will sell at $\pounds 5$ per kg and costs $\pounds 2$ per kg to produce. Product C will sell at $\pounds 4$ per kg and costs $\pounds 3$ per kg to produce.
The profit is to be maximised.\\
(i) Explain how the initial feasible tableau shown in Fig. 3 models this problem.
\begin{table}[h]
\begin{center}
\begin{tabular}{ | l | c | c | c | c | c | c | c | }
\hline
P & a & b & c & s 1 & s 2 & s 3 & RHS \\
\hline
1 & - 4 & - 3 & - 1 & 0 & 0 & 0 & 0 \\
\hline
0 & 10 & 5 & 12 & 1 & 0 & 0 & 12000 \\
\hline
0 & 5 & 5 & 7 & 0 & 1 & 0 & 12000 \\
\hline
0 & 5 & 3 & 5 & 0 & 0 & 1 & 9000 \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Fig. 3}
\end{center}
\end{table}
(ii) Use the simplex algorithm to solve this problem, and interpret the solution.\\
(iii) In the solution, one of the basic variables appears at a value of 0 . Explain what this means.
There is a contractual requirement to provide at least 500 kg of product A .\\
(iv) Show how to incorporate this constraint into the initial tableau ready for an application of the two-stage simplex method.
Briefly describe how the method works. You are not required to perform the iterations.
\hfill \mbox{\textit{OCR MEI D2 2014 Q3 [20]}}