Practise › Questions › Linear programming: formulation and graphical solution
Linear programming: formulation and graphical solution questions
Turn a description into inequalities, shade what is allowed, and the best answer will be sitting at a corner. Half the marks are for the translation and half for knowing where to look.
7 original questions · 26 marks · the linear programming: formulation and graphical solution notes · Decision Mathematics 1
Every question here is written for this library rather than taken from a past paper. Write your answer out before opening the worked one: the answers award marks point by point, and the marks are easier to see when you have something of your own to compare against.
State the three things a formulated linear program must contain, and one thing candidates most often leave out.
Worked answer
The variables defined in words with their units, the objective to be maximised or minimised, and the constraints as inequalities. B1 for the three components of the formulation, B1 for naming the usual omission. The non-negativity conditions are the commonest omission; they bound the region and carry a mark of their own.Write 3x + 2y ≤ 20 and 5x + 2y ≥ 30 as equations, introducing the appropriate extra variables.
Worked answer
3x + 2y + s1 = 20, where s1 is a slack variable taking up the unused amount. 5x + 2y − s2 + t1 = 30, where s2 is a surplus recording the excess over 30 and t1 is an artificial variable providing a starting solution. B1 for the slack equation, B1 for the surplus, B1 for the artificial variable.A workshop makes tables and chairs. Each table needs 4 hours of machining and 2 hours of finishing; each chair needs 1 hour of machining and 2 hours of finishing. At most 40 machining hours and 36 finishing hours are available in a week. The profit is £30 on a table and £16 on a chair. Formulate this as a linear program.
Worked answer
Let x be the number of tables made in a week and y the number of chairs. Both must be defined in words; a formulation that opens with an inequality loses the first mark.
Maximise P = 30x + 16y (profit in pounds).
Machining: 4x + y ≤ 40.
Finishing: 2x + 2y ≤ 36, which simplifies to x + y ≤ 18.
And x ≥ 0, y ≥ 0. B1 for defining the variables in words, B1 for the objective, B1 for the two resource constraints, B1 for the non-negativity conditions. Keep the units straight throughout: hours on the left of the resource constraints, pounds in the objective.Maximise P = 4x + 5y subject to x + y ≤ 10, 2x + 3y ≤ 24 and x, y ≥ 0, using the vertex method.
Worked answer
The vertices are (0, 0), (10, 0), (0, 8) and the intersection of the two lines. Solving x + y = 10 with 2x + 3y = 24: 2x + 3(10 − x) = 24, so 30 − x = 24 and x = 6, y = 4. Evaluating P: 0, 40, 40 and 44. The maximum is 44 at (6, 4). M1 for listing the vertices, M1 for solving the two lines simultaneously, A1 for the intersection, A1 for the maximum. Test every vertex and show the values; naming the corner without them scores the answer mark only.For the linear program of maximising P = 4x + 5y subject to x + y ≤ 10, 2x + 3y ≤ 24 and x, y ≥ 0, describe the objective line method and say what it shows that testing the vertices does not.
Worked answer
Draw one line of constant objective value, say 4x + 5y = 20, and slide it parallel away from the origin. The last corner it touches before leaving the region is the optimum, here (6, 4). It also shows at once when the objective is parallel to a constraint, in which case a whole edge is optimal and there are infinitely many solutions. Testing the vertices would report that only as a tie between two corners. B1 for drawing a line of constant objective value, B1 for sliding it to the last point of the region, B1 for the parallel-edge case.The linear program of maximising P = 4x + 5y subject to x + y ≤ 10, 2x + 3y ≤ 24 and x, y ≥ 0 has its optimum at (6, 4). Find the value of each slack variable there and say what it means.
Worked answer
At (6, 4): 6 + 4 + s1 = 10 gives s1 = 0, and 12 + 12 + s2 = 24 gives s2 = 0. Both constraints are binding, so there is no spare capacity in either. M1 for substituting into the constraints, A1 for both slacks being zero, B1 for the interpretation. Relaxing either one on its own would allow a larger P.Maximise P = 5x + 4y subject to 2x + 3y ≤ 12, 4x + y ≤ 10 and x, y ≥ 0. Find the optimum by the vertex method, then find the optimum when x and y must both be whole numbers, and explain why rounding the first answer does not give the second.
Worked answer
The vertices are (0, 0), (2.5, 0), (0, 4) and the intersection of the two constraint lines. From 4x + y = 10, y = 10 − 4x; substituting into 2x + 3y = 12 gives 2x + 30 − 12x = 12, so x = 1.8 and y = 2.8.
Values of P: 0, 12.5, 16 and 5(1.8) + 4(2.8) = 9 + 11.2 = 20.2. The maximum is 20.2 at (1.8, 2.8).
Rounding up to (2, 3) gives 4(2) + 3 = 11, which breaks 4x + y ≤ 10, so that point is outside the feasible region and cannot be used at all. Rounding down to (1, 2) is feasible but gives only P = 13.
Test the lattice points of the region instead. Those satisfying both constraints include (0, 4) with P = 16, (1, 3) with P = 17 and (2, 2) with P = 18, which is the largest. Note that 4(2) + 2 = 10 and 2(2) + 3(2) = 10, so (2, 2) sits on one constraint line and inside the other. The integer optimum is P = 18 at (2, 2).
M1 for the vertices, M1 for solving the two lines, A1 for the intersection, A1 for the continuous maximum, M1 for testing lattice points, A1 for the integer optimum, B1 for why rounding fails.
Neither rounding found it, because (2, 2) is not a neighbour of (1.8, 2.8) in the y direction at all. The integer optimum can sit some way from the continuous one. Search the region; do not round the corner.
The same practice on paper: the printable workbook for this topic, questions and a worked answer book.
Practise linear programming: formulation and graphical solution one question at a time
The player marks nothing for you. It shows one question, waits, then shows the worked answer so you can mark yourself, and brings a question back sooner when it went badly.