A2 June 2023 Q7
7. A publisher plans to produce three versions of the same book: a paperback, a hardcover, and a deluxe edition.
- Each paperback takes 4 minutes to print and 1 minute to bind
- Each hardcover takes 8 minutes to print and 5 minutes to bind
- Each deluxe edition takes 15 minutes to print and 12 minutes to bind
The printing machine is available for at most 150 hours and the binding machine must be used for at least 60 hours.
The publisher decides to produce
- at least 1600 books in total
- at least three times as many paperbacks as hardcovers
The profit on each paperback sold is £8, the profit on each hardcover sold is £20 and the profit on each deluxe edition sold is £40
Let \(x\), \(y\) and \(z\) represent the number of paperbacks, hardcovers and deluxe editions produced.
The publisher decides to solve this linear programming problem by using the two-stage simplex method.
As part of your solution, you must show how
- the constraints have been made into equations by using slack variables, exactly two surplus variables and exactly two artificial variables
- the rows for the two objective functions are formed
The following tableau is obtained after two iterations of the first stage of the two-stage simplex method.
| b.v. | \(x\) | \(y\) | \(z\) | \(s_1\) | \(s_2\) | \(s_3\) | \(s_4\) | \(a_1\) | \(a_2\) | Value |
|---|---|---|---|---|---|---|---|---|---|---|
| \(s_1\) | 0 | 0 | 0 | 1 | 1 | 3 | 0 | \(-1\) | \(-3\) | 600 |
| \(z\) | 0 | \(\dfrac{4}{11}\) | 1 | 0 | \(-\dfrac{1}{11}\) | \(\dfrac{1}{11}\) | 0 | \(\dfrac{1}{11}\) | \(-\dfrac{1}{11}\) | \(\dfrac{2000}{11}\) |
| \(x\) | 1 | \(\dfrac{7}{11}\) | 0 | 0 | \(\dfrac{1}{11}\) | \(-\dfrac{12}{11}\) | 0 | \(-\dfrac{1}{11}\) | \(\dfrac{12}{11}\) | \(\dfrac{15600}{11}\) |
| \(s_4\) | 0 | \(\dfrac{40}{11}\) | 0 | 0 | \(\dfrac{1}{11}\) | \(-\dfrac{12}{11}\) | 1 | \(-\dfrac{1}{11}\) | \(\dfrac{12}{11}\) | \(\dfrac{15600}{11}\) |
| \(P\) | 0 | \(-\dfrac{4}{11}\) | 0 | 0 | \(-\dfrac{32}{11}\) | \(-\dfrac{56}{11}\) | 0 | \(\dfrac{32}{11}\) | \(\dfrac{56}{11}\) | \(\dfrac{204800}{11}\) |
| \(I\) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
After three iterations of the second stage of the two-stage simplex method, the following tableau is obtained.
| b.v. | \(x\) | \(y\) | \(z\) | \(s_1\) | \(s_2\) | \(s_3\) | \(s_4\) | Value |
|---|---|---|---|---|---|---|---|---|
| \(s_2\) | 0 | 0 | 0 | 1 | 1 | 3 | 0 | 600 |
| \(z\) | 0 | 0 | 1 | \(\dfrac{1}{10}\) | 0 | \(\dfrac{1}{2}\) | \(-\dfrac{1}{10}\) | 100 |
| \(x\) | 1 | 0 | 0 | \(-\dfrac{3}{40}\) | 0 | \(-\dfrac{9}{8}\) | \(-\dfrac{7}{40}\) | 1125 |
| \(y\) | 0 | 1 | 0 | \(-\dfrac{1}{40}\) | 0 | \(-\dfrac{3}{8}\) | \(\dfrac{11}{40}\) | 375 |
| \(P\) | 0 | 0 | 0 | \(\dfrac{29}{10}\) | 0 | \(\dfrac{7}{2}\) | \(\dfrac{1}{10}\) | 20500 |
Given that the publisher produces the optimal number of each version of the book,
| Scheme | Marks | AO |
|---|---|---|
| Maximise \(P = 8x + 20y + 40z\) | B1 | 3.3 |
| \(4x + 8y + 15z \leqslant 9000\) \(x + 5y + 12z \geqslant 3600\) | M1 A1 | 3.3 1.1b |
| \(x + y + z \geqslant 1600\) | B1 | 3.3 |
| \(-x + 3y \leqslant 0\) \((x, y, z \geqslant 0)\) | B1 | 3.3 |
| (5) |
Notes
B1: Correct objective function \((8x + 20y + 40z)\) plus ‘maximise’ or ‘max’ but not ‘maximum’ (and ‘\(P =\)’ is not required)
M1: Either one correct inequality (need not be simplified) or both \(4x + 8y + 15z \leqslant k_1\) and \(x + 5y + 12z \geqslant k_2\) where \(k_1, k_2 \gt 0\)
A1: Both correct (\(4x + 8y + 15z \leqslant 9000,\ x + 5y + 12z \geqslant 3600\)) – allow equivalent answers (provided 4 terms only and integer coefficients e.g. \(2x + 10y + 24z - 7200 \geqslant 0\))
B1: CAO (\(x + y + z \geqslant 1600\) oe provided 4 terms only and integer coefficients)
B1: CAO (\(3y \leqslant x\) oe provided 2 terms only and integer coefficients)
| Scheme | Marks | AO | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \(4x + 8y + 15z + s_1 = 9000\) \(x + 5y + 12z - s_2 + a_1 = 3600\) \(x + y + z - s_3 + a_2 = 1600\) \(-x + 3y + s_4 = 0\) | B1 B1 | 1.1b 2.5 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| \(I = -(a_1 + a_2)\) where \(a_1 = 3600 - x - 5y - 12z + s_2\) and \(a_2 = 1600 - x - y - z + s_3\) | M1 | 2.1 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| \(I - 2x - 6y - 13z + s_2 + s_3 = -5200\) and \(P - 8x - 20y - 40z = 0\) | A1 | 2.2a | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
e.g.
| M1 A1 | 3.4 2.2a | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (6) |
Notes
(b) Note in this part that the numbering of the suffices for the slack, surplus and artificial variables seen in both the candidate’s equations and Simplex tableau will most likely be different from what is seen in the MS (e.g. \(4x + 8y + 15z + s_3 = 9000\) is correct). The correct values in the rows of the tableau do NOT imply the first four marks (the question explicitly asked for the constraints as equations and the rows for the two objectives to be explicitly stated)
B1: Any two correct inequalities converted into equations correctly (condone the same letter, say \(s_3\), being used twice) – any equivalent forms of the correct equations are acceptable (e.g. variables do not need to be on the same side)
B1: All four correct equations (using distinct slack, surplus and artificial variables) – any equivalent forms of the correct equations are acceptable
M1: Using \(I = -(a_1 + a_2)\) with their expressions for \(a_1\) and \(a_2\) (allow slips in forming \(I\) from their two expressions for the two artificial variables) but must be a clear intention to calculate \(I = -(a_1 + a_2)\)) – must be exactly two artificial variables in their expression for \(I\) for this mark
A1: CAO for \(I\) and \(P\) (must be stated as \(P - 8x - 20y - 40z = 0\) (A0 if = 0 missing) and \(I - 2x - 6y - 13z + s_2 + s_3 = -5200\) - so variables on one side and constant on the other)
M1: setting up initial tableau – all six rows complete (with no blanks) and two correct rows (but ignore b.v. column for this mark)
A1: CAO (any equivalent correct form) - note that the candidate’s order in which the rows appear in the tableau (and choice of letter to represent the slack, surplus and artificial variables) may be different – check to ensure that the basic variable column is consistent with their choice of lettering for the slack and artificial variables
| Scheme | Marks | AO | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| B1 M1 A1 A1 B1 | 1.1b 2.1 1.1b 1.1b 2.4 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (5) |
Notes
B1: Pivot (top) row completely correct including change of b.v. (but not ‘Row Ops’ column)
M1: All values in one of the non-pivot rows correct (so ignore b.v. column and ‘Row Ops’ column) or one of the ‘non zero and one’ columns (which are \(y, s_1, s_2\) or Value) correct (must have pivoted on the correct value)
A1: Row operations used correctly at least twice, i.e. two of the ‘non zero and one’ columns (\(s_1, s_2\), \(y\) or Value) correct
A1: CAO all values including b.v. column – ignore ‘Row Ops’ column for this mark
B1: Correct row operations stated – alternatives are \(\dfrac{1}{3}\text{r}_1,\ \text{r}_2 - \dfrac{1}{33}\text{r}_1,\ \text{r}_3 + \dfrac{12}{33}\text{r}_1,\ \text{r}_4 + \dfrac{12}{33}\text{r}_1,\ \text{r}_5 + \dfrac{56}{33}\text{r}_1\)
| Scheme | Marks | AO |
|---|---|---|
| (i) £20 500 | B1 | 3.4 |
| (ii) 1125 + 5(375) + 12(100) = (4200 minutes so) 70 (hours) | B1 | 2.2a |
| (2) |
Notes
(d)(i)
B1: CAO (20 500)
(ii)
B1: CAO (70 only)
| Scheme | Marks | AO |
|---|---|---|
| e.g. there is no guarantee that all the books will be sold | B1 | 3.5b |
| (1) | ||
| (19 marks) |
Notes
B1: CAO – must explicitly mention the fact that it is possible that not all the books will be sold. Ignore reasons for why, provided they do not relate to the publisher producing less than the optimal number of books