D1-5 Linear programming — revision question pack

4 specification points · notes, questions, answers and worked methods

Checked against Edexcel 9FM0 section D1-5. Review basis: the qualification registry sourced from the Pearson Edexcel Level 3 Advanced GCE in Further Mathematics (9FM0) specification; registry verification recorded 17 July 2026.

How this checking works

D1-5.1 · Formulation of problems as linear programs including the meaning and use of slack, surplus and artificial variables.

Explanation

To formulate a linear program, define each decision variable precisely with its units, write the objective as a linear expression to be maximised or minimised, and write one inequality for each limited resource, together with the non-negativity conditions. To use the simplex algorithm every inequality must become an equation.
A constraint such as $3x+2y\leqslant20$ becomes $3x+2y+s_1=20$ , where the slack variable $s_1\geqslant0$ measures the unused amount of that resource.
A constraint such as $x+y\geqslant5$ becomes $x+y-s_3=5$ , where the surplus variable $s_3\geqslant0$ measures the excess over the minimum.
A surplus alone does not give a basic feasible starting point, because setting $x=y=0$ would force $s_3=-5$ , so an artificial variable is added: $x+y-s_3+t_1=5$ with $t_1\geqslant0$ .
Artificial variables have no meaning in the original problem, so the algorithm must drive every one of them to zero before the real optimisation begins.

Worked example

A factory makes $x$ tables and $y$ chairs. Wood is limited to $30$ units, with $5$ per table and $2$ per chair, and at least $4$ tables must be made. Each table yields a profit of $£40$ and each chair $£15$ . Formulate the problem and write the constraints as equations.

1.Maximise $P=40x+15y$ subject to $5x+2y\leqslant30$ and $x\geqslant4$ , with $x\geqslant0$ and $y\geqslant0$ .
2.The wood constraint becomes $5x+2y+s_1=30$ , where $s_1$ is the unused wood.
3.The table constraint becomes $x-s_2=4$ , where $s_2$ is the number of tables above the minimum.
4.Since $x=y=0$ would make $s_2=-4$ , add an artificial variable: $x-s_2+t_1=4$ .

Answer: Maximise $P=40x+15y$ subject to $5x+2y+s_1=30$ and $x-s_2+t_1=4$ , with all variables non-negative.

Common mistakes

Don't fall into the trap of adding a slack variable to a $\geqslant$ constraint instead of subtracting a surplus.
Don't fall into the trap of omitting the artificial variable, so the initial tableau is not feasible.
Don't fall into the trap of defining variables loosely, for example as "tables" rather than "the number of tables made each day".

Exam tip

Write the units into every variable definition; a formulation mark is often lost for a variable that is named but not quantified.

Tier 1 · Easy

1.
Write the constraint $4x+3y\leqslant36$ as an equation using a slack variable, and state what the slack variable measures.
(2)
(Total for Question 1 is 2 marks)
2.
Write the constraint $2x+5y\geqslant18$ as an equation, introducing whichever additional variables are needed for the simplex algorithm, and explain why each is required.
(3)
(Total for Question 2 is 3 marks)

Tier 2 · Standard

1.
A bakery makes $x$ loaves and $y$ rolls each day. A loaf uses $500$ g of flour and $12$ minutes of oven time; a roll uses $80$ g of flour and $3$ minutes. There are $60$ kg of flour and $600$ minutes of oven time available, and at least $40$ rolls must be made. A loaf sells for $£3$ and a roll for $£0.60$ . Formulate the problem as a linear program.
(6)
(Total for Question 1 is 6 marks)
2.
A linear program is to maximise $P=7x+4y+9z$ subject to $3x+2y+z\leqslant45$ , $2x+5y\leqslant50$ and $x+y+z\geqslant12$ , with $x$ , $y$ , $z\geqslant0$ . Write all three constraints as equations, naming each new variable and stating its type.
(5)
(Total for Question 2 is 5 marks)
3.
In the solution of a linear program, the slack variable $s_1$ for the constraint $6x+5y\leqslant72$ takes the value $0$ , while the slack variable $s_2$ for $4x+9y\leqslant108$ takes the value $27$ . Interpret both values, and state which constraint is binding.
(4)
(Total for Question 3 is 4 marks)

Tier 3 · Hard

1.
A haulier runs $x$ small vans, $y$ medium vans and $z$ large lorries each week. Small vans carry $2$ tonnes, medium $5$ tonnes and large $12$ tonnes, and at least $180$ tonnes must be moved. Weekly costs are $£300$ , $£550$ and $£1100$ , and the budget is $£28000$ . Drivers are available for at most $40$ vehicles in total, and the number of large lorries may not exceed the number of medium vans. Formulate the problem as a linear program and write every constraint as an equation.
(8)
(Total for Question 1 is 8 marks)
2.
Explain why an artificial variable must be driven to zero before the optimisation of the true objective begins, and state what it means if the algorithm finishes stage one with an artificial variable still positive.
(6)
(Total for Question 2 is 6 marks)
3.
A workshop makes $x$ standard units and $y$ deluxe units. Each standard unit needs $2$ hours of machining and $1$ hour of finishing; each deluxe unit needs $3$ hours of machining and $4$ hours of finishing. There are $120$ machining hours and $100$ finishing hours. At least a quarter of all units made must be deluxe, and the profits are $£30$ and $£50$ . Formulate the problem, taking care with the proportion constraint.
(8)
(Total for Question 3 is 8 marks)
4.
A linear program has the constraint $8x+5y+3z\leqslant96$ with slack variable $s_1$ . At the optimal solution $x=6$ , $y=4$ and $z=2$ . Calculate $s_1$ and interpret it. State the effect on the optimal value of the objective if the right-hand side of the constraint were reduced to $90$ .
(6)
(Total for Question 4 is 6 marks)
5.
Explain the difference between a surplus variable and an artificial variable, giving the constraint $3x+4y\geqslant24$ as an example, and state the value of each variable at the point $x=4$ , $y=6$ .
(7)
(Total for Question 5 is 7 marks)

D1-5.2 · Graphical solution of two variable problems using objective line and vertex methods including cases where integer solutions are required.

Explanation

For two variables, draw each constraint as a line and shade the region it excludes, leaving the feasible region unshaded. The optimum of a linear objective always occurs at a vertex, so the vertex method evaluates the objective at every corner of the feasible region and picks the best value.
The objective line method instead draws one line of the form $ax+by=k$ for a convenient $k$ and slides it parallel across the region;
the last vertex it touches on the way out is optimal, and this method also shows immediately when an edge is optimal, which happens when the objective line is parallel to a constraint and gives infinitely many optimal points.
When the variables must be whole numbers the optimal vertex is often not a lattice point, and it is not enough to round: test the integer points near the optimal vertex, checking each one against every constraint, and take the best feasible one.
That value is usually strictly worse than the continuous optimum.

Worked example

Maximise $P=5x+4y$ subject to $2x+3y\leqslant24$ and $3x+y\leqslant21$ , with $x$ , $y\geqslant0$ .

1.The lines meet where $2x+3y=24$ and $3x+y=21$ , giving $x=\frac{39}{7}$ and $y=\frac{30}{7}$ .
2.The other vertices are $(0,0)$ , $(7,0)$ and $(0,8)$ .
3.Evaluating $P$ gives $0$ , $35$ , $32$ and $5\left(\frac{39}{7}\right)+4\left(\frac{30}{7}\right)=\frac{315}{7}=45$ .
4.The largest value is $45$ .

Answer: The maximum is $P=45$ at $x=\frac{39}{7}$ , $y=\frac{30}{7}$ .

Common mistakes

Don't fall into the trap of shading the feasible side rather than the excluded side, so the region is unclear.
Don't fall into the trap of rounding a non-integer optimal vertex instead of testing nearby lattice points against every constraint.
Don't fall into the trap of testing only the vertices formed by the constraint lines and forgetting the axes.

Exam tip

Solve the two binding equations simultaneously rather than reading the intersection off the graph; examiners expect exact fractions, not measured values.

Tier 1 · Easy

1.
The feasible region of a linear program has vertices $(0,0)$ , $(6,0)$ , $(4,5)$ and $(0,7)$ . Use the vertex method to maximise $P=3x+2y$ .
(3)
(Total for Question 1 is 3 marks)
2.
Explain the objective line method for maximising $P=2x+5y$ , and state how to recognise from the objective line that a problem has more than one optimal point.
(3)
(Total for Question 2 is 3 marks)

Tier 2 · Standard

1.
Maximise $P=5x+4y$ subject to $2x+3y\leqslant24$ , $3x+y\leqslant21$ , $x\geqslant0$ and $y\geqslant0$ , using the vertex method. Give your answer exactly.
(6)
(Total for Question 1 is 6 marks)
2.
Minimise $C=4x+7y$ subject to $x+y\geqslant10$ , $2x+y\geqslant14$ and $x\leqslant8$ , with $x$ , $y\geqslant0$ .
(6)
(Total for Question 2 is 6 marks)
3.
Maximise $P=8x+5y$ subject to $3x+2y\leqslant54$ , $x+3y\leqslant45$ and $x\leqslant14$ , with $x$ , $y\geqslant0$ .
(6)
(Total for Question 3 is 6 marks)

Tier 3 · Hard

1.
Maximise $P=5x+4y$ subject to $2x+3y\leqslant24$ and $3x+y\leqslant21$ , with $x$ , $y\geqslant0$ , given that $x$ and $y$ must be whole numbers. Show that rounding the continuous optimum does not work, and find the integer optimum.
(8)
(Total for Question 1 is 8 marks)
2.
Maximise $P=3x+5y$ subject to $2x+y\leqslant16$ , $x+3y\leqslant27$ and $x+y\leqslant12$ , with $x$ , $y\geqslant0$ . Give the continuous optimum exactly, then find the optimum when $x$ and $y$ must be whole numbers.
(9)
(Total for Question 2 is 9 marks)
3.
A feasible region has vertices $(0,0)$ , $(9,0)$ , $(6,6)$ and $(0,10)$ . Determine the set of positive constants $k$ that place the maximum of $P=kx+3y$ at the vertex $(6,6)$ , and identify each $k$ at which the maximum is attained at more than one point.
(8)
(Total for Question 3 is 8 marks)
4.
Explain why the optimum of a linear program in two variables always occurs at a vertex of the feasible region, and describe what happens when the region is unbounded.
(6)
(Total for Question 4 is 6 marks)
5.
A company maximises $P=6x+9y$ over the region bounded by $2x+3y\leqslant30$ , $x+y\leqslant12$ , $x$ , $y\geqslant0$ . Show that the maximum is attained at more than one point, describe the set of optimal points, and state the optimal value.
(8)
(Total for Question 5 is 8 marks)

D1-5.3 · The Simplex algorithm and tableau for maximising and minimising problems with ≤ constraints.

Explanation

For a maximisation with only $\leqslant$ constraints, add a slack variable to each constraint and write one row per constraint plus an objective row in which the coefficients of the objective appear with their signs reversed. Each iteration has four steps.
Choose the pivot column as the one with the most negative entry in the objective row. Form the ratio of the value column to the pivot column entry for every row with a strictly positive entry there, and choose the pivot row with the smallest non-negative ratio.
Divide the pivot row by the pivot element so that the pivot becomes $1$ , then add or subtract multiples of the new pivot row from every other row, including the objective row, until the rest of the pivot column is zero.
The algorithm stops when the objective row has no negative entries; the value column then gives the basic variables, every non-basic variable is zero, and the bottom right entry is the optimal value.
To minimise $C$ , maximise $P=-C$ and negate the answer at the end.

Worked example

Maximise $P=5x+4y$ subject to $2x+3y\leqslant24$ and $3x+y\leqslant21$ . Carry out the first iteration.

1.The initial tableau has rows $s_1$ : $2, 3, 1, 0$ with value $24$ ; $s_2$ : $3, 1, 0, 1$ with value $21$ ; and $P$ : $-5, -4, 0, 0$ with value $0$ .
2.The most negative objective entry is $-5$ , so the pivot column is $x$ .
3.The ratios are $24\div2=12$ and $21\div3=7$ , so the pivot row is $s_2$ and the pivot element is $3$ .
4.Dividing gives the new $x$ row $1, \frac13, 0, \frac13$ with value $7$ , and eliminating leaves $s_1$ : $0, \frac73, 1, -\frac23$ with value $10$ , and $P$ : $0, -\frac73, 0, \frac53$ with value $35$ .

Answer: After one iteration $x=7$ , $y=0$ , $s_1=10$ and $P=35$ , and a further iteration is needed because $-\frac73$ is still negative.

Common mistakes

Don't fall into the trap of forming a ratio using a negative or zero entry in the pivot column.
Don't fall into the trap of forgetting to update the objective row, so the stopping test is applied to stale numbers.
Don't fall into the trap of reading the objective coefficients into the tableau without reversing their signs.

Exam tip

After each iteration state the current values of every variable and of $P$ ; those interim statements carry marks even if a later iteration goes wrong.

Tier 1 · Easy

1.
A simplex tableau has objective row entries $-6$ , $-9$ , $0$ , $0$ under the columns $x$ , $y$ , $s_1$ , $s_2$ . State the pivot column and explain your choice.
(2)
(Total for Question 1 is 2 marks)
2.
In a simplex tableau the pivot column is the $x$ column. The rows have $x$ entries $4$ , $-2$ and $5$ with values $36$ , $18$ and $30$ . Determine the pivot row and the pivot element.
(3)
(Total for Question 2 is 3 marks)

Tier 2 · Standard

1.
Maximise $P=5x+4y$ subject to $2x+3y\leqslant24$ and $3x+y\leqslant21$ with $x$ , $y\geqslant0$ , using the simplex algorithm. Give the final tableau and state the values of $x$ , $y$ , $s_1$ , $s_2$ and $P$ .
(8)
(Total for Question 1 is 8 marks)
2.
Explain how a minimisation problem with $\leqslant$ constraints is handled by the simplex algorithm, and write down the objective row for minimising $C=5x-4y-6z$ .
(4)
(Total for Question 2 is 4 marks)
3.
A simplex tableau for a problem in $x$ , $y$ and $z$ after two iterations is printed with its $z$ column missing. The columns shown are $x$ , $y$ , $s_1$ , $s_2$ , $s_3$ , and the rows are $x$ : $1, 0, \dfrac25, -\dfrac15, 0$ with value $8$ ; $y$ : $0, 1, -\dfrac{1}{10}, \dfrac{3}{10}, 0$ with value $18$ ; $s_3$ : $0, 0, -\dfrac35, -\dfrac15, 1$ with value $18$ ; and $P$ : $0, 0, \dfrac75, \dfrac45, 0$ with value $148$ . Read off the values the tableau does give, and explain why the tableau cannot be declared optimal from the columns shown.
(4)
(Total for Question 3 is 4 marks)

Tier 3 · Hard

1.
Maximise $P=5x+6y+4z$ subject to $3x+2y+z\leqslant60$ , $x+4y+2z\leqslant80$ and $2x+2y+3z\leqslant70$ , with $x$ , $y$ , $z\geqslant0$ . Carry out two iterations of the simplex algorithm, stating the pivots and the tableau after each.
(9)
(Total for Question 1 is 9 marks)
2.
Continue the previous problem for a third iteration and state the optimal solution, verifying it against all three original constraints.
(8)
(Total for Question 2 is 8 marks)
3.
Minimise $C=5x-4y-6z$ subject to $x+y+2z\leqslant40$ and $2x+3y+z\leqslant60$ , with $x$ , $y$ , $z\geqslant0$ , using the simplex algorithm.
(9)
(Total for Question 3 is 9 marks)
4.
Explain why the ratio test uses only rows with a strictly positive entry in the pivot column, and state what it means if no row has a positive entry there.
(7)
(Total for Question 4 is 7 marks)
5.
After one iteration of a simplex tableau for a maximisation, the objective row reads $0$ , $-\dfrac73$ , $0$ , $\dfrac53$ with value $35$ , under the columns $x$ , $y$ , $s_1$ , $s_2$ . Interpret the entries $-\dfrac73$ and $\dfrac53$ , and state the current values of all four variables and of $P$ .
(7)
(Total for Question 5 is 7 marks)

D1-5.4 · The two-stage Simplex and big-M methods for maximising and minimising problems which may include both ≤ and ≥ constraints.

Explanation

When a problem contains a $\geqslant$ constraint, the origin is not feasible, so the tableau needs an artificial variable and a way of removing it. The two-stage method runs the simplex twice.
Stage one minimises the sum of the artificial variables: express that sum in terms of the non-basic variables using the constraint rows, minimise it by ordinary pivoting, and stop when it reaches zero. If it cannot reach zero the original problem is infeasible.
Stage two then discards the artificial columns and the stage-one objective, and maximises the true objective from the feasible tableau that stage one produced.
The big-M method does the same work in one pass by subtracting $M$ times each artificial variable from the objective, where $M$ stands for a number larger than anything else in the problem.
Substituting the constraint rows to remove the artificial variables from the objective row gives coefficients containing $M$ , and because $M$ is huge those terms dominate the choice of pivot column, which forces the artificial variables out early.

Worked example

Maximise $P=3x+2y$ subject to $x+y\leqslant10$ and $x+2y\geqslant8$ . Set up the big-M tableau.

1.The constraints become $x+y+s_1=10$ and $x+2y-s_2+t_1=8$ .
2.The objective becomes $P=3x+2y-Mt_1$ , that is $P-3x-2y+Mt_1=0$ .
3.Substituting $t_1=8-x-2y+s_2$ removes $t_1$ from the objective row.
4.This gives $P-(3+M)x-(2+2M)y+Ms_2=-8M$ .

Answer: The initial tableau has rows $s_1$ : $1, 1, 1, 0, 0$ with value $10$ ; $t_1$ : $1, 2, 0, -1, 1$ with value $8$ ; and $P$ : $-(3+M), -(2+2M), 0, M, 0$ with value $-8M$ .

Common mistakes

Don't fall into the trap of leaving the artificial variable in the objective row instead of substituting it out, so the tableau is inconsistent.
Don't fall into the trap of treating $M$ as a small number when choosing the pivot column.
Don't fall into the trap of starting stage two without checking that every artificial variable has reached zero.

Exam tip

Write the objective row of a big-M tableau in the form $-(a+bM)$ so the comparison of columns is a comparison of the $M$ coefficients first; that is the whole point of the method.

Tier 1 · Easy

1.
State the purpose of stage one of the two-stage simplex method, and state what conclusion is drawn if stage one ends with a positive value.
(3)
(Total for Question 1 is 3 marks)
2.
The constraints of a linear program are $2x+y\leqslant18$ and $x+y\geqslant7$ . Write both as equations for the simplex algorithm and state the initial basic feasible solution of the resulting tableau.
(4)
(Total for Question 2 is 4 marks)

Tier 2 · Standard

1.
For the problem of maximising $P=3x+2y$ subject to $x+y\leqslant10$ and $x+2y\geqslant8$ , with $x$ , $y\geqslant0$ , write down the initial big-M tableau, showing how the artificial variable is removed from the objective row.
(6)
(Total for Question 1 is 6 marks)
2.
In the initial big-M tableau for maximising $P=3x+2y$ with $x+y+s_1=10$ and $x+2y-s_2+t_1=8$ , the objective row is $-(3+M)$ , $-(2+2M)$ , $0$ , $M$ , $0$ with value $-8M$ . Determine the first pivot, explaining why $M$ decides the choice.
(6)
(Total for Question 2 is 6 marks)
3.
Explain how the two-stage method sets up its stage-one objective for the constraint set $x+y+s_1=10$ and $x+2y-s_2+t_1=8$ , and state which variable should enter the basis first.
(6)
(Total for Question 3 is 6 marks)

Tier 3 · Hard

1.
Carry out the big-M method in full for maximising $P=3x+2y$ subject to $x+y\leqslant10$ and $x+2y\geqslant8$ , with $x$ , $y\geqslant0$ . State each pivot and the final solution.
(10)
(Total for Question 1 is 10 marks)
2.
Explain the relationship between the two-stage simplex method and the big-M method, and give one practical advantage of each.
(7)
(Total for Question 2 is 7 marks)
3.
A linear program is to maximise $P=4x+3y$ subject to $x+y\leqslant6$ , $x+y\geqslant9$ and $x$ , $y\geqslant0$ . Explain what happens when the two-stage simplex method is applied, and state the conclusion.
(7)
(Total for Question 3 is 7 marks)
4.
A big-M tableau for a maximisation has objective row entries $-(5+2M)$ , $-(7+M)$ , $0$ , $M$ , $0$ under the columns $x$ , $y$ , $s_1$ , $s_2$ , $t_1$ . Determine the pivot column, and state how the answer would change if the entries were $-(5+2M)$ and $-(19+2M)$ instead.
(7)
(Total for Question 4 is 7 marks)
5.
A problem is to minimise $C=4x+5y$ subject to $x+y\geqslant8$ , $2x+y\geqslant10$ , $x\leqslant6$ and $y\leqslant7$ , with $x$ , $y\geqslant0$ . Explain how the problem is prepared for the two-stage simplex method, state how many artificial variables are needed, and verify the optimal value by the vertex method.
(9)
(Total for Question 5 is 9 marks)

Answer key

Answers begin on a new printed page so the question pack can be completed without the solutions alongside it.

D1-5.1 · Formulation of problems as linear programs including the meaning and use of slack, surplus and artificial variables.

Tier 1 · Easy

Mark scheme for D1-5.1 Tier 1 · Easy
Question	Scheme	Marks
1	$4x+3y+s_1=36$ , where $s_1\geqslant0$ $s_1$ measures the amount of the resource that is left unused	2
(2 marks)		2
Notes
A slack variable takes up the difference between the left-hand side and the limit, so adding $s_1$ turns the inequality into an equation. Because the constraint is a maximum, $s_1$ is non-negative and equals $36-4x-3y$ , the quantity of the resource not consumed by the chosen values of $x$ and $y$ .
2	$2x+5y-s_1+t_1=18$ $s_1\geqslant0$ is a surplus variable, measuring the amount by which the minimum is exceeded $t_1\geqslant0$ is an artificial variable, needed because setting $x=y=0$ would otherwise force $s_1=-18$	3
(3 marks)		3
Notes
For a $\geqslant$ constraint the left-hand side is at least the bound, so the excess is subtracted: $2x+5y-s_1=18$ . That equation alone has no feasible basic solution at the origin, since $s_1$ would have to be negative. Adding a non-negative artificial variable gives $2x+5y-s_1+t_1=18$ , which has the feasible starting point $x=y=s_1=0$ and $t_1=18$ .

Tier 2 · Standard

Mark scheme for D1-5.1 Tier 2 · Standard
Question	Scheme	Marks
1	Let $x$ be the number of loaves made each day and $y$ the number of rolls made each day Maximise $P=3x+0.6y$ Flour: $500x+80y\leqslant60000$ , which simplifies to $25x+4y\leqslant3000$ Oven: $12x+3y\leqslant600$ , which simplifies to $4x+y\leqslant200$ Rolls: $y\geqslant40$ $x\geqslant0$ and $y\geqslant0$	6
(6 marks)		6
Notes
Define the variables with their units, then convert every quantity to consistent units before writing the inequalities: $60$ kg is $60000$ g, so the flour constraint is $500x+80y\leqslant60000$ , and dividing by $20$ gives $25x+4y\leqslant3000$ . The oven constraint $12x+3y\leqslant600$ divides by $3$ to give $4x+y\leqslant200$ . The minimum production of rolls is a $\geqslant$ constraint, and the objective is the total revenue in pounds.
2	$3x+2y+z+s_1=45$ , where $s_1$ is a slack variable $2x+5y+s_2=50$ , where $s_2$ is a slack variable $x+y+z-s_3+t_1=12$ , where $s_3$ is a surplus variable and $t_1$ is an artificial variable All of $s_1$ , $s_2$ , $s_3$ and $t_1$ are non-negative The initial basic feasible solution is $x=y=z=s_3=0$ , $s_1=45$ , $s_2=50$ , $t_1=12$	5
(5 marks)		5
Notes
Each $\leqslant$ constraint gains a slack variable that soaks up the unused capacity. The $\geqslant$ constraint loses a surplus variable that measures the excess over $12$ , and because that leaves no feasible basic solution at the origin it also gains an artificial variable. Reading the three equations with the four new variables as the basis gives a starting tableau in which $s_1$ , $s_2$ and $t_1$ are basic and take the values on the right-hand side.
3	$s_1=0$ means the first resource is fully used, so $6x+5y=72$ The first constraint is binding, and the optimal point lies on that line $s_2=27$ means $27$ units of the second resource are unused The second constraint is not binding at the optimum	4
(4 marks)		4
Notes
A slack variable records how much of a resource is left, so a value of zero means the resource is exhausted and the corresponding inequality holds with equality. Here $6x+5y=72$ , so the optimal vertex lies on that boundary line and the constraint is active, or binding. A positive slack of $27$ means the second constraint could be tightened by $27$ before it began to affect the answer.

Tier 3 · Hard

Mark scheme for D1-5.1 Tier 3 · Hard
Question	Scheme	Marks
1	Let $x$ , $y$ and $z$ be the numbers of small vans, medium vans and large lorries used each week Minimise $C=300x+550y+1100z$ Tonnage: $2x+5y+12z\geqslant180$ , so $2x+5y+12z-s_1+t_1=180$ Budget: $300x+550y+1100z\leqslant28000$ , so $300x+550y+1100z+s_2=28000$ Vehicles: $x+y+z\leqslant40$ , so $x+y+z+s_3=40$ Lorries against medium vans: $z\leqslant y$ , that is $z-y\leqslant0$ , so $z-y+s_4=0$ $x$ , $y$ , $z\geqslant0$ $s_1$ is a surplus, $t_1$ an artificial variable, and $s_2$ , $s_3$ , $s_4$ are slacks	8
(8 marks)		8
Notes
The objective is the weekly cost, which the haulier wants as small as possible, so this is a minimisation. Each requirement becomes one inequality: a lower bound on tonnage moved, an upper bound on cost, an upper bound on the fleet size and a comparison between two variables, which must be rearranged so that all the variables are on one side. Converting to equations adds a slack to each $\leqslant$ constraint and a surplus to the $\geqslant$ constraint, and the surplus row also needs an artificial variable so that the origin gives a valid starting basis.
2	An artificial variable does not appear in the original problem It was added only to give a feasible starting basis A solution with $t_1>0$ satisfies the modified equation but not the original constraint So the point is not in the true feasible region and cannot be optimal If stage one ends with an artificial variable still positive, no assignment satisfies all the constraints The original linear program is infeasible	6
(6 marks)		6
Notes
Writing $x+y-s_1+t_1=5$ means the true constraint $x+y-s_1=5$ holds only when $t_1=0$ ; any positive value of $t_1$ represents an amount by which the constraint is being violated and then patched up. The first stage therefore minimises the artificial variables, and only when they all reach zero does the current basic solution correspond to a genuine point of the feasible region. If that minimum is positive, the violation cannot be removed, which proves the feasible region is empty and the problem has no solution at all.
3	Let $x$ be the number of standard units and $y$ the number of deluxe units made Maximise $P=30x+50y$ Machining: $2x+3y\leqslant120$ Finishing: $x+4y\leqslant100$ Proportion: $y\geqslant\dfrac{1}{4}(x+y)$ Multiplying by $4$ gives $4y\geqslant x+y$ So the proportion constraint is $x-3y\leqslant0$ $x\geqslant0$ and $y\geqslant0$	8
(8 marks)		8
Notes
The two resource constraints are direct. The proportion condition says the deluxe units are at least a quarter of the total, which is $y\geqslant\frac14(x+y)$ ; clearing the fraction gives $4y\geqslant x+y$ , and collecting terms gives $3y\geqslant x$ , that is $x-3y\leqslant0$ . Writing it in this form keeps every constraint linear with the variables on the left, which is what the simplex tableau requires; leaving it as a fraction of a total is the usual source of error.
4	$8(6)+5(4)+3(2)=48+20+6=74$ $s_1=96-74=22$ $22$ units of the resource are unused at the optimum Reducing the limit to $90$ still leaves $90-74=16$ units spare The current optimal point remains feasible So the optimal value of the objective is unchanged	6
(6 marks)		6
Notes
The slack is the limit minus the amount actually consumed, so $s_1=96-74=22$ . A constraint with positive slack is not binding, which means the optimal vertex is determined by the other constraints. Tightening a non-binding constraint changes nothing until the slack is used up, and since $96-22=74$ is still below $90$ , the same point remains feasible and optimal; only a reduction below $74$ would begin to cut into the solution.
5	A surplus variable measures a genuine quantity: the amount by which the left-hand side exceeds the lower bound An artificial variable measures nothing in the original problem and exists only to create a starting basis The equation is $3x+4y-s_1+t_1=24$ At $x=4$ , $y=6$ the left-hand side is $12+24=36$ The constraint is satisfied, so $t_1=0$ $s_1=36-24=12$ The surplus of $12$ is meaningful, whereas $t_1$ has been driven to zero as required	7
(7 marks)		7
Notes
Subtracting the surplus converts the inequality into an equation that any feasible point satisfies with $s_1\geqslant0$ ; the surplus therefore has an interpretation, namely the excess over the requirement. The artificial variable is added purely so that the origin, where all the original variables are zero, gives a basic solution with non-negative values, and it must be removed before the answer means anything. At the feasible point $x=4$ , $y=6$ the constraint already holds with $12$ to spare, so a valid basic representation takes $s_1=12$ and $t_1=0$ .

D1-5.2 · Graphical solution of two variable problems using objective line and vertex methods including cases where integer solutions are required.

Tier 1 · Easy

Mark scheme for D1-5.2 Tier 1 · Easy
Question	Scheme	Marks
1	$P(0,0)=0$ $P(6,0)=18$ $P(4,5)=12+10=22$ $P(0,7)=14$ The maximum is $P=22$ at $(4,5)$	3
(3 marks)		3
Notes
A linear objective attains its extreme values at a vertex of the feasible region, so it is enough to evaluate $P$ at each of the four corners. The values are $0$ , $18$ , $22$ and $14$ , and the largest is $22$ , which occurs at the vertex $(4,5)$ .
2	Draw a line $2x+5y=k$ for a convenient value of $k$ and slide it parallel across the feasible region For a maximum, keep sliding away from the origin; the last point of the region the line touches is optimal If the objective line is parallel to a constraint edge, the line leaves the region along that whole edge Every point of that edge is then optimal, so there are infinitely many optimal solutions	3
(3 marks)		3
Notes
All lines $2x+5y=k$ are parallel, and $k$ increases as the line moves away from the origin, so the greatest feasible value of $P$ is found at the last contact between the sliding line and the region. Normally that contact is a single vertex. When the objective has the same gradient as one of the constraint lines, the sliding line meets the region along an entire edge at the moment of departure, and every point on that edge gives the same maximum value.

Tier 2 · Standard

Mark scheme for D1-5.2 Tier 2 · Standard
Question	Scheme	Marks
1	Vertices of the feasible region: $(0,0)$ , $(7,0)$ , $(0,8)$ and the intersection of the two lines Solving $2x+3y=24$ and $3x+y=21$ gives $7x=39$ , so $x=\dfrac{39}{7}$ and $y=\dfrac{30}{7}$ $P(0,0)=0$ $P(7,0)=35$ $P(0,8)=32$ $P\left(\dfrac{39}{7},\dfrac{30}{7}\right)=\dfrac{195+120}{7}=\dfrac{315}{7}=45$ The maximum is $P=45$	6
(6 marks)		6
Notes
The line $3x+y=21$ meets the $x$ -axis at $(7,0)$ and the line $2x+3y=24$ meets the $y$ -axis at $(0,8)$ ; each of these is feasible for the other constraint. Eliminating $y$ from $2x+3y=24$ and $9x+3y=63$ gives $7x=39$ , so $x=39/7$ and then $y=21-3(39/7)=30/7$ . Evaluating the objective at all four vertices gives $0$ , $35$ , $32$ and $45$ , so the maximum is $45$ .
2	The lines $x+y=10$ and $2x+y=14$ meet at $(4,6)$ The line $x+y=10$ meets $x=8$ at $(8,2)$ The line $x+y=10$ meets the $y$ -axis at $(0,10)$ , but $2(0)+10=10<14$ , so that point is infeasible The line $2x+y=14$ meets the $y$ -axis at $(0,14)$ , which is feasible $C(4,6)=16+42=58$ , $C(8,2)=32+14=46$ , $C(0,14)=98$ The minimum is $C=46$ at $(8,2)$	6
(6 marks)		6
Notes
The feasible region is unbounded above, so only the corners on its lower boundary matter. Those corners are $(0,14)$ where $2x+y=14$ meets the $y$ -axis, $(4,6)$ where the two lower-bound lines cross, and $(8,2)$ where $x+y=10$ meets the vertical line $x=8$ . The point $(0,10)$ fails the second constraint and is not a vertex of the region. Evaluating $C$ at the three vertices gives $98$ , $58$ and $46$ , so the minimum is $46$ .
3	$x=14$ meets $3x+2y=54$ where $2y=12$ , so $y=6$ , giving the vertex $(14,6)$ The lines $3x+2y=54$ and $x+3y=45$ meet where $x=\dfrac{72}{7}$ and $y=\dfrac{81}{7}$ $(14,0)$ and $(0,15)$ are also vertices $P(14,6)=112+30=142$ $P\left(\dfrac{72}{7},\dfrac{81}{7}\right)=\dfrac{576+405}{7}=\dfrac{981}{7}=140\tfrac17$ $P(14,0)=112$ and $P(0,15)=75$ The maximum is $P=142$ at $(14,6)$	6
(6 marks)		6
Notes
Substituting $x=14$ into $3x+2y=54$ gives $y=6$ , and that point satisfies $14+18=32\leqslant45$ . Eliminating from $3x+2y=54$ and $x+3y=45$ gives $7y=81$ , so $y=81/7$ and $x=45-3(81/7)=72/7$ , which satisfies $x\leqslant14$ . Including the axis vertices $(14,0)$ and $(0,15)$ , the four values of $P$ are $142$ , $981/7$ , $112$ and $75$ . Since $981/7=140\frac17<142$ , the maximum is $142$ .

Tier 3 · Hard

Mark scheme for D1-5.2 Tier 3 · Hard
Question	Scheme	Marks
1	The continuous optimum is $\left(\dfrac{39}{7},\dfrac{30}{7}\right)$ , that is about $(5.57, 4.29)$ , with $P=45$ Rounding gives $(6,4)$ , but $2(6)+3(4)=24\leqslant24$ and $3(6)+4=22>21$ , so $(6,4)$ is infeasible Test $(5,4)$ : $10+12=22\leqslant24$ and $15+4=19\leqslant21$ , feasible, $P=41$ Test $(6,3)$ : $12+9=21\leqslant24$ and $18+3=21\leqslant21$ , feasible, $P=42$ Test $(5,5)$ : $10+15=25>24$ , infeasible Test $(6,2)$ : feasible with $P=38$ ; test $(4,5)$ : $8+15=23\leqslant24$ and $12+5=17\leqslant21$ , feasible, $P=40$ The best feasible integer point is $(6,3)$ The integer maximum is $P=42$	8
(8 marks)		8
Notes
The continuous optimum sits at $x=39/7\approx5.57$ and $y=30/7\approx4.29$ , and rounding each coordinate to the nearest integer gives $(6,4)$ , which breaks the second constraint since $3(6)+4=22$ . The correct method is to examine the feasible lattice points near the optimum. Checking $(5,4)$ , $(6,3)$ , $(5,5)$ , $(6,2)$ and $(4,5)$ against both constraints leaves $(5,4)$ , $(6,3)$ , $(6,2)$ and $(4,5)$ feasible, with objective values $41$ , $42$ , $38$ and $40$ . No lattice point can beat the continuous bound of $45$ , and $(6,3)$ gives the largest feasible value, $42$ .
2	$2x+y=16$ and $x+3y=27$ meet where $5x=21$ , so $x=\dfrac{21}{5}$ and $y=\dfrac{38}{5}$ That point satisfies $x+y=\dfrac{59}{5}=11.8\leqslant12$ , so it is feasible $P=3\left(\dfrac{21}{5}\right)+5\left(\dfrac{38}{5}\right)=\dfrac{63+190}{5}=\dfrac{253}{5}=50.6$ The other vertices $(0,9)$ , $(8,0)$ and $(0,0)$ give $45$ , $24$ and $0$ , so the continuous maximum is $50.6$ Test $(4,8)$ : $x+3y=28>27$ , infeasible Test $(4,7)$ : $8+7=15$ , $4+21=25$ , $11$ , all satisfied, $P=47$ Test $(3,8)$ : $6+8=14$ , $3+24=27$ , $11$ , all satisfied, $P=49$ Test $(5,6)$ : $16$ , $23$ , $11$ , all satisfied, $P=45$ ; test $(2,8)$ : $P=46$ The integer maximum is $P=49$ at $(3,8)$	9
(9 marks)		9
Notes
Solving $2x+y=16$ with $x+3y=27$ gives $6x+3y=48$ and hence $5x=21$ , so $x=21/5$ and $y=16-42/5=38/5$ ; the third constraint is slack there, so the vertex is feasible and $P=253/5=50.6$ . For the integer problem, the continuous optimum lies near $(4.2, 7.6)$ , so the lattice points to test are those with $x$ in $\{2,3,4,5\}$ and $y$ near $7$ or $8$ . The binding constraint $x+3y\leqslant27$ rules out $(4,8)$ , and among the feasible candidates $(3,8)$ gives $49$ , beating $(4,7)$ at $47$ , $(2,8)$ at $46$ and $(5,6)$ at $45$ .
3	$P(9,0)=9k$ , $P(6,6)=6k+18$ , $P(0,10)=30$ $(6,6)$ beats $(9,0)$ when $6k+18\geqslant9k$ , that is $k\leqslant6$ $(6,6)$ beats $(0,10)$ when $6k+18\geqslant30$ , that is $k\geqslant2$ So the maximum is at $(6,6)$ for $2\leqslant k\leqslant6$ At $k=6$ the values at $(6,6)$ and $(9,0)$ are both $54$ At $k=2$ the values at $(6,6)$ and $(0,10)$ are both $30$ So the maximum is attained at more than one point when $k=2$ or $k=6$	8
(8 marks)		8
Notes
Because the objective is linear, the maximum is at a vertex, so it is enough to compare the three non-zero vertex values $9k$ , $6k+18$ and $30$ ; the origin gives $0$ and can be ignored for $k\geqslant0$ . Requiring $6k+18$ to be at least each of the others gives the two inequalities $k\leqslant6$ and $k\geqslant2$ . At each endpoint two vertices tie, which means the objective line is parallel to the edge joining them, so every point of that edge is optimal and there are infinitely many optimal solutions.
4	The feasible region is an intersection of half-planes, so it is convex The objective is linear, so its level curves are parallel straight lines Sliding a level line across a convex region, the last contact is either a single vertex or a whole edge If it is an edge, both endpoints of that edge are vertices with the same optimal value So checking the vertices always finds the optimal value If the region is unbounded in a direction in which the objective increases, no maximum exists and the problem is unbounded	6
(6 marks)		6
Notes
Each constraint cuts the plane into two, and the feasible region is the intersection of the retained halves, which is convex and bounded by straight edges. The objective takes a constant value on each line of a parallel family, so the greatest feasible value is reached where that family last meets the region. On a convex polygon the last contact is a corner, unless the family is parallel to an edge, in which case the whole edge is optimal and its endpoints are vertices attaining the same value. When the region extends without limit in a direction of increase, the sliding line never leaves it and the objective can be made arbitrarily large.
5	The objective $6x+9y$ is $3(2x+3y)$ The constraint gives $2x+3y\leqslant30$ , so $P\leqslant90$ $P=90$ exactly when $2x+3y=30$ The line $2x+3y=30$ meets the axes at $(15,0)$ and $(0,10)$ , and meets $x+y=12$ at $(6,6)$ $(15,0)$ fails $x+y\leqslant12$ , so the feasible part of that line runs from $(6,6)$ to $(0,10)$ Every point of the segment from $(6,6)$ to $(0,10)$ is optimal Check: $P(6,6)=36+54=90$ and $P(0,10)=90$ The optimal value is $P=90$	8
(8 marks)		8
Notes
Since $P=3(2x+3y)$ , the objective line has exactly the same gradient as the first constraint, so the sliding line leaves the region along that constraint rather than at a single corner. The bound $2x+3y\leqslant30$ gives $P\leqslant90$ , with equality precisely on the boundary line, so the optimal set is the feasible part of $2x+3y=30$ . That line leaves the region where $x+y=12$ cuts it, at $(6,6)$ , and ends at $(0,10)$ on the $y$ -axis, so the optimal points form the segment between them and every one of them gives $P=90$ .

D1-5.3 · The Simplex algorithm and tableau for maximising and minimising problems with ≤ constraints.

Tier 1 · Easy

Mark scheme for D1-5.3 Tier 1 · Easy
Question	Scheme	Marks
1	The pivot column is the $y$ column It contains the most negative entry in the objective row, $-9$	2
(2 marks)		2
Notes
Each negative entry in the objective row shows that increasing the corresponding variable from zero would increase $P$ , and the size of the entry is the rate of increase per unit. Choosing the most negative entry increases $P$ fastest per unit of the entering variable, so the $y$ column with $-9$ is chosen ahead of the $x$ column with $-6$ .
2	Only rows with a positive entry in the pivot column give a ratio Row $1$ : $36\div4=9$ ; row $3$ : $30\div5=6$ ; row $2$ is skipped because $-2$ is negative The smallest ratio is $6$ , so the pivot row is row $3$ and the pivot element is $5$	3
(3 marks)		3
Notes
The ratio test finds how far the entering variable can increase before a basic variable would go negative. A row with a negative or zero entry in the pivot column places no such limit, so it is excluded from the test. Comparing the two valid ratios, $9$ and $6$ , the binding one is $6$ , which selects row $3$ and the pivot element $5$ .

Tier 2 · Standard

Mark scheme for D1-5.3 Tier 2 · Standard
Question	Scheme	Marks
1	Initial tableau: $s_1$ row $2, 3, 1, 0$ with value $24$ ; $s_2$ row $3, 1, 0, 1$ with value $21$ ; $P$ row $-5, -4, 0, 0$ with value $0$ First pivot: column $x$ , ratios $12$ and $7$ , pivot row $s_2$ , pivot element $3$ After iteration $1$ : $s_1$ row $0, \dfrac73, 1, -\dfrac23$ with value $10$ ; $x$ row $1, \dfrac13, 0, \dfrac13$ with value $7$ ; $P$ row $0, -\dfrac73, 0, \dfrac53$ with value $35$ Second pivot: column $y$ , ratios $\dfrac{30}{7}$ and $21$ , pivot row $s_1$ , pivot element $\dfrac73$ Final tableau: $y$ row $0, 1, \dfrac37, -\dfrac27$ with value $\dfrac{30}{7}$ ; $x$ row $1, 0, -\dfrac17, \dfrac37$ with value $\dfrac{39}{7}$ ; $P$ row $0, 0, 1, 1$ with value $45$ $x=\dfrac{39}{7}$ , $y=\dfrac{30}{7}$ , $s_1=0$ , $s_2=0$ $P=45$	8
(8 marks)		8
Notes
The most negative objective entry is $-5$ , so $x$ enters; the ratios $24/2=12$ and $21/3=7$ select the $s_2$ row, and dividing by $3$ gives the $x$ row $1, \frac13, 0, \frac13$ with value $7$ . Subtracting twice that row from the $s_1$ row and adding five times it to the objective row completes the first iteration. The objective row still has $-\frac73$ under $y$ , so $y$ enters; the ratios are $10\div\frac73=\frac{30}{7}$ and $7\div\frac13=21$ , so the $s_1$ row is the pivot row. Dividing by $\frac73$ and eliminating gives an objective row with no negative entries, so the algorithm stops with both slacks zero and $P=45$ .
2	Set $P=-C$ and maximise $P$ So maximise $P=-5x+4y+6z$ The objective row reverses these signs, giving $5$ , $-4$ , $-6$ under $x$ , $y$ , $z$ The slack columns are $0$ and the value is $0$ At the end, the minimum of $C$ is the negative of the maximum of $P$	4
(4 marks)		4
Notes
The simplex tableau is built to increase a quantity, so a minimisation is converted by maximising the negative of the objective; the two problems have the same optimal point and their optimal values differ only by sign. Writing $P=-C=-5x+4y+6z$ and reversing the signs for the tableau row gives entries $5$ , $-4$ and $-6$ . The presence of negative entries shows that increasing $y$ or $z$ reduces $C$ , so the algorithm has somewhere to go.
3	The basic variables are $x=8$ , $y=18$ and $s_3=18$ , and the non-basic variables $s_1$ and $s_2$ are $0$ , giving $P=148$ at this stage The stopping test needs every entry of the objective row, including the entry in the missing $z$ column, to be non-negative The entries shown are all non-negative, but the $z$ entry has not been shown, so the test cannot be applied If that hidden entry is negative then $z$ enters the basis and $P$ increases further, so $148$ is only a lower bound for the optimum	4
(4 marks)		4
Notes
Each row is labelled by its basic variable and gives that variable's value directly, so $x=8$ , $y=18$ and $s_3=18$ , while every variable not labelling a row is zero; the bottom right entry gives $P=148$ for that basic solution. Deciding whether to stop is a separate question. The algorithm terminates only when no entry of the objective row is negative, and a column that has not been printed cannot be checked, so the shown entries $0$ , $0$ , $\frac75$ , $\frac45$ and $0$ prove nothing about $z$ . A negative entry there would make $z$ the pivot column and a further iteration would raise $P$ ; for the problem this tableau comes from the hidden entry is in fact $-1$ , and the third iteration takes $P$ from $148$ to $157$ .

Tier 3 · Hard

Mark scheme for D1-5.3 Tier 3 · Hard
Question	Scheme	Marks
1	Initial tableau: $s_1$ : $3, 2, 1, 1, 0, 0$ value $60$ ; $s_2$ : $1, 4, 2, 0, 1, 0$ value $80$ ; $s_3$ : $2, 2, 3, 0, 0, 1$ value $70$ ; $P$ : $-5, -6, -4, 0, 0, 0$ value $0$ Iteration $1$ : pivot column $y$ , ratios $30$ , $20$ , $35$ , pivot row $s_2$ , pivot element $4$ After iteration $1$ : $s_1$ : $\dfrac52, 0, 0, 1, -\dfrac12, 0$ value $20$ ; $y$ : $\dfrac14, 1, \dfrac12, 0, \dfrac14, 0$ value $20$ ; $s_3$ : $\dfrac32, 0, 2, 0, -\dfrac12, 1$ value $30$ ; $P$ : $-\dfrac72, 0, -1, 0, \dfrac32, 0$ value $120$ Iteration $2$ : pivot column $x$ , ratios $8$ , $80$ , $20$ , pivot row $s_1$ , pivot element $\dfrac52$ After iteration $2$ : $x$ : $1, 0, 0, \dfrac25, -\dfrac15, 0$ value $8$ ; $y$ : $0, 1, \dfrac12, -\dfrac{1}{10}, \dfrac{3}{10}, 0$ value $18$ ; $s_3$ : $0, 0, 2, -\dfrac35, -\dfrac15, 1$ value $18$ ; $P$ : $0, 0, -1, \dfrac75, \dfrac45, 0$ value $148$ After two iterations $x=8$ , $y=18$ , $z=0$ and $P=148$ The objective row still contains $-1$ under $z$ , so a third iteration is needed	9
(9 marks)		9
Notes
The most negative entry is $-6$ , so $y$ enters. The ratios $60/2=30$ , $80/4=20$ and $70/2=35$ select the $s_2$ row, and dividing by $4$ gives the $y$ row. Eliminating the $y$ column from the other three rows produces the tableau shown, with $P$ raised from $0$ to $120$ . The objective row now has $-\frac72$ under $x$ and $-1$ under $z$ , so $x$ enters; the ratios $20\div\frac52=8$ , $20\div\frac14=80$ and $30\div\frac32=20$ select the $s_1$ row with pivot $\frac52$ . Dividing and eliminating raises $P$ to $148$ , but the $z$ column is still negative, so the algorithm has not terminated.
2	Pivot column $z$ , since $-1$ is the only negative entry Ratios: the $x$ row has $0$ in the $z$ column so gives no ratio; $y$ gives $18\div\dfrac12=36$ ; $s_3$ gives $18\div2=9$ Pivot row $s_3$ , pivot element $2$ Final tableau: $x$ : $1, 0, 0, \dfrac25, -\dfrac15, 0$ value $8$ ; $y$ : $0, 1, 0, \dfrac{1}{20}, \dfrac{7}{20}, -\dfrac14$ value $\dfrac{27}{2}$ ; $z$ : $0, 0, 1, -\dfrac{3}{10}, -\dfrac{1}{10}, \dfrac12$ value $9$ ; $P$ : $0, 0, 0, \dfrac{11}{10}, \dfrac{7}{10}, \dfrac12$ value $157$ Optimal solution $x=8$ , $y=\dfrac{27}{2}$ , $z=9$ , $P=157$ Check $3(8)+2\left(\dfrac{27}{2}\right)+9=24+27+9=60$ Check $8+4\left(\dfrac{27}{2}\right)+2(9)=8+54+18=80$ Check $2(8)+2\left(\dfrac{27}{2}\right)+3(9)=16+27+27=70$	8
(8 marks)		8
Notes
Only the $z$ column is negative, so $z$ enters. The $x$ row contributes no ratio because its $z$ entry is zero, and comparing $36$ with $9$ selects the $s_3$ row, whose pivot element is $2$ . Dividing that row by $2$ and eliminating the $z$ column elsewhere gives an objective row of $0, 0, 0, \frac{11}{10}, \frac{7}{10}, \frac12$ , all non-negative, so the algorithm terminates. All three slack variables are non-basic and hence zero, which is confirmed by substituting the solution into the original constraints: each is satisfied with equality, and $P=5(8)+6\left(\frac{27}{2}\right)+4(9)=40+81+36=157$ .
3	Maximise $P=-C=-5x+4y+6z$ , so the objective row is $5, -4, -6, 0, 0$ with value $0$ Initial tableau: $s_1$ : $1, 1, 2, 1, 0$ value $40$ ; $s_2$ : $2, 3, 1, 0, 1$ value $60$ Iteration $1$ : pivot column $z$ , ratios $20$ and $60$ , pivot row $s_1$ , pivot element $2$ After iteration $1$ : $z$ : $\dfrac12, \dfrac12, 1, \dfrac12, 0$ value $20$ ; $s_2$ : $\dfrac32, \dfrac52, 0, -\dfrac12, 1$ value $40$ ; $P$ : $8, -1, 0, 3, 0$ value $120$ Iteration $2$ : pivot column $y$ , ratios $40$ and $16$ , pivot row $s_2$ , pivot element $\dfrac52$ Final tableau: $z$ : $\dfrac15, 0, 1, \dfrac35, -\dfrac15$ value $12$ ; $y$ : $\dfrac35, 1, 0, -\dfrac15, \dfrac25$ value $16$ ; $P$ : $\dfrac{43}{5}, 0, 0, \dfrac{14}{5}, \dfrac25$ value $136$ $x=0$ , $y=16$ , $z=12$ and $P=136$ The minimum is $C=-136$	9
(9 marks)		9
Notes
Converting to a maximisation gives $P=-5x+4y+6z$ , whose tableau row is $5, -4, -6, 0, 0$ . The most negative entry is $-6$ , so $z$ enters; the ratios $40/2=20$ and $60/1=60$ select the $s_1$ row, and dividing by $2$ gives the $z$ row. Eliminating leaves $-1$ under $y$ , so $y$ enters next; the ratios $20\div\frac12=40$ and $40\div\frac52=16$ select the $s_2$ row with pivot $\frac52$ . After that iteration every objective entry is non-negative, so the algorithm stops with $y=16$ , $z=12$ and $P=136$ . Checking, $C=5(0)-4(16)-6(12)=-136$ , and the constraints give $16+24=40$ and $48+12=60$ , both exactly met.
4	Each row says that the basic variable equals its value minus the pivot column entry times the entering variable If the entry is positive, increasing the entering variable reduces that basic variable The ratio is the value at which the basic variable would reach zero The smallest such ratio is the first basic variable to hit zero, so it limits the increase If the entry is zero or negative, the basic variable does not fall as the entering variable rises, so that row places no limit If no row has a positive entry, the entering variable can be increased without limit The objective is then unbounded and the problem has no finite optimum	7
(7 marks)		7
Notes
Reading a row as $b_i = v_i - a_i t$ , where $t$ is the amount by which the entering variable is increased, the requirement $b_i\geqslant0$ gives $t\leqslant v_i/a_i$ only when $a_i>0$ ; a non-positive $a_i$ makes $b_i$ increase or stay fixed, so the constraint is vacuous. The binding limit is therefore the smallest ratio over the positive entries, which identifies the leaving variable. When every entry in the pivot column is zero or negative, no basic variable is driven to zero, so $t$ and hence the objective can be made arbitrarily large.
5	$x$ and $s_1$ are basic, since their columns are $0$ in the objective row $y$ and $s_2$ are non-basic, so $y=0$ and $s_2=0$ $P=35$ at this stage The entry $-\dfrac73$ means each unit increase in $y$ would raise $P$ by $\dfrac73$ So the tableau is not yet optimal and $y$ should enter next The entry $\dfrac53$ means each unit increase in $s_2$ would reduce $P$ by $\dfrac53$ Equivalently, one more unit of the second resource would be worth $\dfrac53$ to the objective	7
(7 marks)		7
Notes
A variable is basic exactly when its column has been cleared, so $x$ and $s_1$ label rows and take the values in the value column, while $y$ and $s_2$ are held at zero. The objective row entries are rates of change of $P$ with respect to those non-basic variables, with the sign reversed by the tableau convention: a negative entry marks a variable worth increasing, so $y$ is the next entering variable, and a positive entry marks one that would cost the objective. Since $s_2$ is the slack of the second constraint, its positive entry of $\frac53$ also measures what an extra unit of that constraint's resource would be worth.

D1-5.4 · The two-stage Simplex and big-M methods for maximising and minimising problems which may include both ≤ and ≥ constraints.

Tier 1 · Easy

Mark scheme for D1-5.4 Tier 1 · Easy
Question	Scheme	Marks
1	Stage one minimises the sum of the artificial variables Its purpose is to find a basic feasible solution of the original problem, so that stage two can begin If the minimum is positive, no feasible solution exists and the problem is infeasible	3
(3 marks)		3
Notes
The artificial variables are added only to give the tableau a valid starting basis, and a point of the true feasible region is one at which they are all zero. Stage one therefore drives their sum down as far as possible. Reaching zero produces a genuine feasible point from which the real objective can be optimised; failing to reach zero shows that the constraints cannot all be satisfied at once.
2	$2x+y+s_1=18$ $x+y-s_2+t_1=7$ Initial basis: $s_1=18$ and $t_1=7$ The non-basic variables are $x=0$ , $y=0$ and $s_2=0$	4
(4 marks)		4
Notes
The $\leqslant$ constraint takes a slack variable and the $\geqslant$ constraint takes a surplus, which alone leaves no feasible basis at the origin, so an artificial variable is added to that row. Setting the three original and surplus variables to zero makes the two remaining variables basic, taking the right-hand side values $18$ and $7$ ; both are non-negative, so this is a valid starting point for the algorithm.

Tier 2 · Standard

Mark scheme for D1-5.4 Tier 2 · Standard
Question	Scheme	Marks
1	$x+y+s_1=10$ and $x+2y-s_2+t_1=8$ Objective: $P=3x+2y-Mt_1$ , so $P-3x-2y+Mt_1=0$ From the second constraint, $t_1=8-x-2y+s_2$ Substituting gives $P-3x-2y+M(8-x-2y+s_2)=0$ So $P-(3+M)x-(2+2M)y+Ms_2=-8M$ Initial tableau: $s_1$ : $1, 1, 1, 0, 0$ value $10$ ; $t_1$ : $1, 2, 0, -1, 1$ value $8$ ; $P$ : $-(3+M), -(2+2M), 0, M, 0$ value $-8M$	6
(6 marks)		6
Notes
The big-M objective penalises any positive artificial variable by a huge amount, so maximising it forces $t_1$ to zero. The objective row of a tableau must contain only non-basic variables, and $t_1$ is basic, so it is eliminated by substituting the constraint that defines it. Collecting terms gives the coefficients $-(3+M)$ and $-(2+2M)$ under $x$ and $y$ and $M$ under $s_2$ , with the constant $-8M$ appearing on the right.
2	The candidate columns are $x$ , with $-(3+M)$ , and $y$ , with $-(2+2M)$ For large $M$ the size of an entry is governed by its coefficient of $M$ The $y$ entry has $M$ coefficient $2$ and the $x$ entry has $M$ coefficient $1$ So $-(2+2M)$ is the more negative and $y$ is the pivot column Ratios: $10\div1=10$ for the $s_1$ row and $8\div2=4$ for the $t_1$ row The pivot row is the $t_1$ row and the pivot element is $2$	6
(6 marks)		6
Notes
The pivot column is the one with the most negative objective entry. Since $M$ stands for a number larger than every other quantity in the problem, comparing $-(3+M)$ with $-(2+2M)$ reduces to comparing the coefficients of $M$ : the difference is $-(2+2M)+(3+M)=1-M$ , which is negative for large $M$ , so the $y$ entry is the smaller. The ratio test then compares $10/1$ and $8/2$ , selecting the $t_1$ row, which is exactly the behaviour intended: the first pivot removes the artificial variable from the basis.
3	Stage one minimises $I=t_1$ , the sum of the artificial variables From the second constraint, $t_1=8-x-2y+s_2$ So $I=8-x-2y+s_2$ Increasing $x$ reduces $I$ at a rate of $1$ per unit and increasing $y$ reduces it at a rate of $2$ per unit Increasing $s_2$ would increase $I$ , so it is not a candidate $y$ should enter the basis first, since it reduces $I$ fastest	6
(6 marks)		6
Notes
The stage-one objective is written in terms of the non-basic variables by substituting for the artificial variable from its own constraint row, which is the same substitution the big-M method makes. The resulting expression $I=8-x-2y+s_2$ shows the rate at which each non-basic variable reduces the infeasibility. Choosing the fastest reduction picks $y$ , and this matches the choice the big-M method makes, since the two methods differ only in bookkeeping.

Tier 3 · Hard

Mark scheme for D1-5.4 Tier 3 · Hard
Question	Scheme	Marks
1	Initial: $s_1$ : $1, 1, 1, 0, 0$ value $10$ ; $t_1$ : $1, 2, 0, -1, 1$ value $8$ ; $P$ : $-(3+M), -(2+2M), 0, M, 0$ value $-8M$ Pivot $1$ : column $y$ , row $t_1$ , element $2$ After pivot $1$ : $s_1$ : $\dfrac12, 0, 1, \dfrac12, -\dfrac12$ value $6$ ; $y$ : $\dfrac12, 1, 0, -\dfrac12, \dfrac12$ value $4$ ; $P$ : $-2, 0, 0, -1, 1+M$ value $8$ Pivot $2$ : column $x$ , ratios $12$ and $8$ , row $y$ , element $\dfrac12$ After pivot $2$ : $s_1$ : $0, -1, 1, 1, -1$ value $2$ ; $x$ : $1, 2, 0, -1, 1$ value $8$ ; $P$ : $0, 4, 0, -3, 3+M$ value $24$ Pivot $3$ : column $s_2$ , only the $s_1$ row has a positive entry, ratio $2$ , element $1$ After pivot $3$ : $s_2$ : $0, -1, 1, 1, -1$ value $2$ ; $x$ : $1, 1, 1, 0, 0$ value $10$ ; $P$ : $0, 1, 3, 0, M$ value $30$ No negative entries remain, so the tableau is optimal $x=10$ , $y=0$ , $s_1=0$ , $s_2=2$ , $t_1=0$ and $P=30$ Check: $x+y=10\leqslant10$ and $x+2y=10\geqslant8$ , with $t_1=0$ as required	10
(10 marks)		10
Notes
The first pivot on $y$ removes the artificial variable, raising the objective from $-8M$ to $8$ and leaving $1+M$ in the $t_1$ column, which keeps $t_1$ out of the basis for good. The second pivot enters $x$ : the ratios are $6\div\frac12=12$ and $4\div\frac12=8$ , so $y$ leaves and $P$ rises to $24$ . The objective row still has $-3$ under $s_2$ , and only the $s_1$ row has a positive entry there, giving the ratio $2$ ; pivoting brings $s_2$ into the basis at value $2$ and $P$ to $30$ . All objective entries are then non-negative, so the maximum is $30$ at $x=10$ , $y=0$ , which is the vertex where $x+y=10$ meets the $x$ -axis.
2	Both remove the artificial variables before optimising the real objective The big-M method combines the two aims into one objective by attaching a huge penalty $M$ to each artificial variable For large $M$ the penalty term dominates, so the early pivots are the same as those the two-stage method would make An advantage of the two-stage method is that the arithmetic uses only ordinary numbers, so it is less error prone by hand It also detects infeasibility cleanly, as a positive stage-one minimum An advantage of the big-M method is that only one tableau and one run of the algorithm are needed It also gives the optimal value directly, without restarting with a new objective row	7
(7 marks)		7
Notes
The two methods solve the same underlying difficulty, namely that a $\geqslant$ constraint leaves the origin infeasible. Stage one of the two-stage method is exactly the minimisation of the artificial sum, and the leading term of the big-M objective row is a multiple of that same expression, which is why the pivot choices agree while any artificial variable remains basic. The choice between them is practical: symbolic entries in $M$ make comparisons quick to justify but are easy to mishandle in a written tableau, whereas two shorter numerical runs cost an extra setup but keep every entry concrete.
3	The constraints become $x+y+s_1=6$ and $x+y-s_2+t_1=9$ Stage one minimises $I=t_1=9-x-y+s_2$ Increasing $x$ or $y$ reduces $I$ , but the first constraint limits $x+y$ to at most $6$ So the smallest value $I$ can reach is $9-6=3$ Stage one ends with $t_1=3$ , which is positive No point satisfies both constraints, since $x+y$ cannot be both at most $6$ and at least $9$ The problem is infeasible and has no solution	7
(7 marks)		7
Notes
The two constraints are directly contradictory, and the algorithm discovers this rather than failing silently. Stage one drives $x+y$ up as far as the other constraint allows, which is $6$ , at which point $t_1=9-6=3$ and no further pivot can reduce it because every objective entry has become non-negative. A stage-one minimum that is strictly positive is exactly the certificate of infeasibility, so the algorithm stops and reports that the feasible region is empty; stage two is never started.
4	Compare $-(5+2M)$ with $-(7+M)$ The difference is $-(5+2M)+(7+M)=2-M$ , which is negative for large $M$ So $-(5+2M)$ is the more negative and the pivot column is $x$ With entries $-(5+2M)$ and $-(19+2M)$ the coefficients of $M$ are equal The comparison then falls to the constant terms $-(19+2M)$ is the more negative, so the pivot column would be $y$	7
(7 marks)		7
Notes
Because $M$ stands for a number larger than any other in the problem, entries are compared by their $M$ coefficients first. Here $x$ carries $2M$ against $y$ 's $M$ , so the $x$ entry is the more negative however large the constants are, and $x$ enters the basis. When two entries carry the same multiple of $M$ the $M$ terms cancel from the comparison and the ordinary constants decide, which is why $-(19+2M)$ beats $-(5+2M)$ and $y$ would enter instead.
5	Maximise $P=-C=-4x-5y$ $x+y-s_1+t_1=8$ $2x+y-s_2+t_2=10$ $x+s_3=6$ $y+s_4=7$ Two artificial variables are needed, one for each $\geqslant$ constraint Stage one minimises $I=t_1+t_2=18-3x-2y+s_1+s_2$ The feasible region has four vertices: $(2,6)$ , $(6,2)$ , $\left(\dfrac32,7\right)$ and $(6,7)$ , with $C=38$ , $34$ , $41$ and $59$ The minimum is $C=34$ at $(6,2)$	9
(9 marks)		9
Notes
A minimisation is converted by maximising $P=-C$ , and each of the two $\geqslant$ constraints needs both a surplus and an artificial variable, while the two upper bounds need one slack each. Stage one minimises the sum of the artificials, which is found by adding the two constraint rows: $t_1+t_2=(8-x-y+s_1)+(10-2x-y+s_2)=18-3x-2y+s_1+s_2$ . To check the answer independently, the corners of the region are where $x+y=8$ meets $2x+y=10$ , at $(2,6)$ ; where $x+y=8$ meets $x=6$ , at $(6,2)$ ; where $2x+y=10$ meets $y=7$ , at $\left(\frac32,7\right)$ ; and where the two upper bounds meet, at $(6,7)$ , which satisfies both $\geqslant$ constraints and so is a vertex of the region. The objective takes the values $38$ , $34$ , $41$ and $59$ there, so the minimum is $34$ at $(6,2)$ .