D1.5.4 The two-stage Simplex and big-M methods for maximising and…
Section
D1.5 Linear programming
Level
A level only
Statement
The two-stage Simplex and big-M methods for maximising and minimising problems which may include both ≤ and ≥ constraints.
Guidance
Problems will be restricted to those with a maximum of four variables (excluding slack, surplus and artificial variables) and four constraints, in addition to any non-negativity conditions.
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
In part (a) the majority of candidates attempted to set up the initial tableau, mostly with reasonable success. Some marks were lost owing to (minor) slips in translating from their equations to the tableau. A small number of candidates confused which equations needed slack variables versus which needed surplus and artificial variables. A small number of candidates added surplus variables and subtracted artificial variables, rather than the reverse. Most understood the process of employing big-M, with occasional slips in gathering terms leading to an incorrect objective function, although some did not form an objective function of the right format. Populating the table correctly was achieved by many candidates – with errors in correct identification of basic variables in each row indicated perhaps a lack of depth of understanding of the overall approach and what the simplex tableau is achieving.
Key points from the mark scheme and examiner's report
read constraints from Figure 5: 3x + 4y ≤ 20, 3x + y ≤ 8 (slacks), x ≥ 1, 2x + 3y ≥ 6 (surplus and artificial)
P = 11x + ky − M(a₁ + a₂) with a₁ + a₂ = 7 − 3x − 3y + s₂ + s₃
P row −(11 + 3M), −(k + 3M), …, −7M
June 2025 · Paper 3D (Decision 1) · Q7(b)5 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Part (b) was less well answered. A good number of candidates did score full marks, or just lost one mark, if they did not show consideration of both inequalities. Most arrived at the equation for P and scored the first mark, and some wrote at least one correct inequality. If they used a correct inequality, candidates generally chose k = 11/3 as their value of k to substitute into their equation, meaning if a value for P was found it was often 88/3. Some considered both inequalities but then chose the wrong range, using k = 16.5. A small number of candidates used the expression from the a2 column to form an inequality, which was incorrect. Some candidates decided that k needed to be an integer and typically chose k = 3 as the greatest integer less than 11/3. This could score full marks, as could the very small number of candidates who stated a range of possible values for P. Several candidates decided to use the original graph to answer this part of the question instead of the simplex tableau. Although this was a valid approach, it involved significant additional work and generally restricted the candidate to a maximum of 4 out of 5 marks as they only compared one vertex with the optimal point. Candidates should be reminded that questions are designed to be answered from the information provided, which in this case was the simplex tableau.
Key points from the mark scheme and examiner's report
P = 198/7 + 2k/7 at x = 18/7, y = 2/7
optimal needs 11/7 − 3k/7 ≥ 0 and 33/7 − 2k/7 ≥ 0, so k ≤ 11/3 and P = 88/3 at k = 11/3
consider both inequalities (16.5 chosen wrongly by some)
June 2024 · Paper 3D (Decision 1) · Q5(a)6 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
In part (a) many responses demonstrated that candidates understood how to use slack, surplus and artificial variables to construct their constraints successfully. However, there were errors seen in establishing the initial inequalities including a common error in translation of the multiplicative relationship between x and y resulting in rather than Errors in the direction of one or more inequalities were also seen which, of course, impacted on the introduction of the dummy variables. Setting up the new the objective function was the least successful part of the process, with seen frequently. Sign issues were almost usually the barrier here. In fact, many candidates omitted this step completely perhaps highlighting a lack of understanding for this aspect of the specification. In most cases, candidates could transfer their constraints to the tableau although, again, some issues with signs were seen, as were errors in the basic variable labels.
Key points from the mark scheme and examiner's report
x − y ≥ 100, x ≤ 5y, 2x + 3y ≥ 350
minimise x + y as maximise P = −x − y − M(a₁ + a₂) with a₁, a₂ substituted
P row 1 − 3M, 1 − 2M, M, 0, M, … −450M
x ≤ 5y often written y ≤ 5x
June 2024 · Paper 3D (Decision 1) · Q5(b)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Part (b)(i) was usually correct, and most candidates went on to substitute this into at least one inequality. However, substitution into all three constraint inequalities or the critical two was not always seen and the required processing to obtain was sometimes not achieved. Insufficient reasoning therefore meant that the conclusion was not always fully justified for the award of the final mark. A common incorrect answer was the use of to obtain .
Key points from the mark scheme and examiner's report
x = 130 from the row
substitute into all constraints: y ≤ 30 from x − y ≥ 100 and y ≥ 30 from 2x + 3y ≥ 350, so y = 30
June 2023 · Paper 3D (Decision 1) · Q7(b)6 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Almost all candidates attempted this question, though it seemed that some ran out of time part way through. Only a few candidates gained full marks. There were several common mistakes then led to incorrect responses in part (b). In general, most candidates were confident using slack, surplus and artificial variables. One recurrent error was to rearrange the constraint x >= 3y as x – 3y >= 0 so that a third artificial variable was incorrectly introduced, in spite of the question stating, “using exactly two artificial variables”. Those candidates who did have two artificial variables usually went on to set up an equation for I using their a1 and a2, gaining the associated method mark. But the correct corresponding accuracy mark was frequently lost by candidates not explicitly stating the correct equations for both I and P, with variables on one side and constant on the other, before filling in the tableau. Most candidates managed to complete the tableau and achieve the method mark for two completely correct rows, though the associated accuracy mark was often lost due to prior errors. For a few candidates their only error was to write surplus variables, rather than artificial variables, in the basic variable column. The answer to part (c) was independent of the earlier parts of the question, providing
Key points from the mark scheme and examiner's report
slacks s₁, s₄, surplus s₂, s₃ and artificials a₁, a₂
I = −(a₁ + a₂) gives I − 2x − 6y − 13z + s₂ + s₃ = −5200
equations must be shown, not just the tableau
June 2023 · Paper 3D (Decision 1) · Q7(c)5 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Almost all candidates attempted this question, though it seemed that some ran out of time part way through. Only a few candidates gained full marks. There were several common mistakes column. The answer to part (c) was independent of the earlier parts of the question, providing an opportunity for those who had struggled previously to still make progress. Most candidates appeared well prepared in performing an iteration of the Simplex method, so many gained all five marks or lost just one mark due to a computational slip. There were some tables left blank, possibly due to timing issues. Only a handful of candidates chose the wrong pivot. Many candidates gained the mark in part (d)(i) for reading off the correct answer of £20 500
Key points from the mark scheme and examiner's report
most negative is −56/11 in the s₃ column, pivot 3 in the s₁ row (s₃ enters, s₁ leaves)
state row operations
P = 216000/11
June 2022 · Paper 3D (Decision 1) · Q4(a)4 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question proved to be a good discriminator between candidates. A not-insignificant number of candidates left this question out entirely, but the vast majority attempted it and were able to access one or more marks, with a reasonable number achieving full marks. The first half of (a) was generally answered well. A significant majority of candidates were able to give the correct inequalities for the three constraints, and the modal score for the two independent accuracy marks was full marks by some margin. The mistakes that were seen, with relatively low frequency, were to use strict inequalities, to reverse the direction of the inequality or, most commonly of these, to include the use of slack/artificial variables in their inequalities, thereby losing both marks. A small number of numerical slips were also seen.
Key points from the mark scheme and examiner's report
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
In the second part of (a) candidates were asked to give the two possible objective functions. The standard on this part was much more variable. Several candidates omitted this part; a huge number of objective functions featuring M or artificial variables were also seen. Of those who did achieve a function, was marginally the more common. 2 x - + 3 y z + A few candidates did correctly state both functions, but many did not attempt to classify them as max/min objectives. Part (b) was unusual, in that several candidates clearly understood how to find the correct pivot but were either partially or entirely unable to explain what they were doing. For the first mark, a good majority knew that pivoting on the x-column was required, and generally ‘most negative’ (in the objective row) was given as reasoning. However, several candidates failed to refer to either/both the ‘2 – 4M’ or the objective row. There were very few mentions of M being arbitrarily large, however this was not required (on this occasion) to achieve the mark. Many candidates failed to score the second mark as they simply stated that “3 (in the x- column/a2 row) is the pivot because the 𝜃 value is the least (positive)” (or equivalent). This did not achieve the mark because it did not show the calculations for all the 𝜃-values. A number of candidates also lost the mark for simply stating “3 is the pivot” after comparing the correct values – due to this being ambiguous it could not score full marks. Overall, it was a minority of candidates who responded with sufficient precision to earn this mark, and less than a quarter of responses seen scored both marks in (b). As well as the above errors in (b), a surprisingly number completed the correct calculations but then proceeded to pivot on the incorrect item or stated the correct column but then proceeded to calculate 𝜃-values for the wrong column. 6
Key points from the mark scheme and examiner's report
2 − 4M is the only negative in the objective row so x column
ratios 12/3 = 4 < 8/1 and 13/2 so pivot 3 in the a₂ row
must show all three ratios
Nov 2021 · Paper 3D (Decision 1) · Q8(b)6 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
It wasn’t obvious if time was a factor in why a few attempts at the final question were left blank or whether it was the demand(s) of the question itself. Most candidates who did attempt this question scored a good number of marks in (a) and (b) for setting up the linear programming problem and the corresponding two-stage Simplex tableau. Most candidates knew what to do in
Key points from the mark scheme and examiner's report
slacks s₁, s₂, surplus s₃ and artificial a₁ for x + z ≥ 28
I = −a₁ gives I − x − z + s₃ = −28
five-row tableau
Nov 2021 · Paper 3D (Decision 1) · Q8(c)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
It wasn’t obvious if time was a factor in why a few attempts at the final question were left blank or whether it was the demand(s) of the question itself. Most candidates who did attempt this part (c) but didn’t give sufficient detail for why the 5 in the 2s row was the pivot. In part (d) many attempted the iteration of the second stage, and while some got the correct values of x, y, and z, many did not give their final answer in the context of the number of hours spent swimming, cycling, and running.
Key points from the mark scheme and examiner's report
only negative in P row is −1 (z column)
62/5 = 12.4 < 28/1 so pivot 5 in the s₂ row
must compare the ratios, not just say "least"
Nov 2021 · Paper 3D (Decision 1) · Q8(d)5 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
It wasn’t obvious if time was a factor in why a few attempts at the final question were left blank or whether it was the demand(s) of the question itself. Most candidates who did attempt this part (c) but didn’t give sufficient detail for why the 5 in the 2s row was the pivot. In part (d) many attempted the iteration of the second stage, and while some got the correct values of x, y, and z, many did not give their final answer in the context of the number of hours spent swimming, cycling, and running.
Key points from the mark scheme and examiner's report
row operations stated
x = 78/5, y = 11, z = 62/5, P = 117/5
answer in context: 15.6 h swimming, 11 h cycling, 12.4 h running (context often missing)
Oct 2020 · Paper 3D (Decision 1) · Q7(b)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
on to correctly complete the bottom row of the tableau in (b). In (c) (i) was often answered correctly but many then lost a mark when omitting the zero valued variables in (ii). There was some indication that candidates could be running out of time on this question with partially completed simplex tableaux, but a good number of continuing candidates scored four or five marks. Instances of choosing an incorrect pivot were extremely rare. The final three marks in (e)
Key points from the mark scheme and examiner's report
A = −(a₁ + a₂) with a₁, a₂ substituted: A row −2, −2, −4, 0, 1, 1, 0, 0, −13
Oct 2020 · Paper 3D (Decision 1) · Q7(c)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
on to correctly complete the bottom row of the tableau in (b). In (c) (i) was often answered correctly but many then lost a mark when omitting the zero valued variables in (ii). There was some indication that candidates could be running out of time on this question with partially completed simplex tableaux, but a good number of continuing candidates scored four or five marks. Instances of choosing an incorrect pivot were extremely rare. The final three marks in (e)
Key points from the mark scheme and examiner's report
A = 0 so the artificial variables are zero and a basic feasible solution is found
x = 3, z = 7/4, s₁ = 147/4, y = s₂ = s₃ = 0 (zero variables often omitted)
Oct 2020 · Paper 3D (Decision 1) · Q7(d)5 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Only a few candidates were unable to make any attempt here. The two stage simplex is another recent addition to the specification, but a good proportion of candidates showed at least some understanding of the method. Many candidates realised what was required to formulate the linear programming problem and were able to interpret the content of the simplex tableau accordingly, though some had all three constraint inequalities reversed. Candidates should recognise that it is essential to state whether the objective is to be maximised or minimised and failure to do so will always result in one mark lost. It was pleasing to see a proportion of candidates showing clear working in order to go
Key points from the mark scheme and examiner's report
most negative is −11/12 in the s₂ column, pivot 7/12 in the s₁ row
state row operations
P = 69
Oct 2020 · Paper 3D (Decision 1) · Q7(e)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
of choosing an incorrect pivot were extremely rare. The final three marks in (e) were only accessible to those who had completed their tableau. The last mark penalised those who stated values for all six variables as the question specifically asked for just the basic variables.
Key points from the mark scheme and examiner's report
no negative entries in the P row so optimal
P = 69
basic variables only: s₂ = 63, x = 24, z = 7
June 2019 · Paper 3D (Decision 1) · Q6(a)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
In part (a) many candidates gave a correct response, but these varied from statements such as “the problem contains >= constraints”, to “simplex can only deal with <= constraints” through to a thorough explanation that “for this problem the origin is not in the feasible region as 8 x y z and therefore the problem had to be modified to accommodate this”. Incorrect responses included statements such as “the problem has three variables” or “it needs artificial variables”.
Key points from the mark scheme and examiner's report
the ≥ constraints mean the origin is not feasible, so Simplex (≤ constraints only) cannot start
"three variables" or "needs artificial variables" scored 0
June 2019 · Paper 3D (Decision 1) · Q6(b)7 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
In part (b) most candidates made a good attempt at setting up the initial tableau, generally converting the three constraints into equations of the correct form. Most used the notation provided in the question, although a small number used r, s and t instead of 1 2 , s s and 3, s although only some candidates changed the headings in their tableau. A small number made sign errors with the second and third constraints, adding surplus variables and subtracting artificial variables. A significant number of candidates made mistakes with their objective function, ranging from the basic form with errors such as 1 2 2 2 0 P x y z M a a or 1 2 2 2 P x y z M a a seen or an expression with the equals sign omitted. Other errors followed when attempting to substitute for 1 2 a a or when simplifying the equation. There were some common errors seen in the three constraints when they were written in the tableau, such as 0 4 2 in the third row being entered as 4 2 0, the b.v. column being left empty or an x, y or z appearing in a cell. Some candidates left one or more cells blank. There were a significant number of errors made in the objective row, many of which came from simplification errors noted above. Common errors included 0 instead of 23M in the value column and M instead of M in the 2s and 3s columns.
Key points from the mark scheme and examiner's report
slack s₁, surplus s₂ s₃ and artificial a₁ a₂
P = 2x + 2y − z − M(a₁ + a₂) with a₁ + a₂ = 23 − x − 3y − 3z + s₂ + s₃ substituted
objective row errors were common
June 2019 · Paper 3D (Decision 1) · Q6(c)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
In part (c) most candidates stated the correct values for the three non-zero variables although a small number made errors here. Some failed to state the value of the five zero variables and a small number of candidates either omitted one of these or added an extra one, sometimes duplicating one of the non- zero variables.
Key points from the mark scheme and examiner's report
s₁ = 26.25, a₁ = 11.75, y = 3.75, x = z = s₂ = s₃ = a₂ = 0
state the zero variables too
June 2019 · Paper 3D (Decision 1) · Q6(d)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
In part (d) the majority of candidates failed to give a correct reason or explanation of why the solution was not feasible, with many stating that there were negative values in the objective row or making a general comment such as “not all the artificial variables are zero” or “the sum of the artificial variables is not zero”. Other incorrect statements included “ 1a has a value”. Correct answers included “ 1a is not zero” and “ 1a = 11.75” or even a full statement to explain that 8 x y z is not satisfied with x = 0, y = 3.75 and z = 0 and therefore it is not a feasible solution.
Key points from the mark scheme and examiner's report
a₁ = 11.75 ≠ 0 and artificial variables must be zero in a feasible solution
"negative values in the objective row" scored 0
June 2019 · Paper 3D (Decision 1) · Q6(e)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
In part (e) some candidates were unsure of the choice of pivot column with a significant number incorrectly choosing the x column. Some of those who chose the correct z column failed to state a reason for their choice. Of those who chose the z column and gave the correct reason, some then went on to simply stated that 0.5 had the smallest ratio value without showing the three calculations and others, who did show all their calculations correctly, stated that 7.5 was the next pivot.
Key points from the mark scheme and examiner's report
most negative entry 2 − 1.5M gives the z column
ratios 3.75/0.5 = 7.5 less than 26.25/1.5 and 11.75/1.5 so pivot 0.5 in the y row
many chose the x column or gave no ratios
Find an Edexcel Further Maths tutor
Stuck on this? Book a trial lesson with our Further Maths tutor.