Questions on linear programming: formulation and graphical solution

Question 1

State the three things a formulated linear program must contain, and state the further condition it is incomplete without.

Accepted 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 the non-negativity conditions. State those as part of the formulation; they bound the feasible region.

Question 2

Write 3x + 2y ≤ 20 and 5x + 2y ≥ 30 as equations, introducing the appropriate extra variables.

Accepted Answer

3x + 2y + s₁ = 20, where s₁ is a slack variable taking up the unused amount. 5x + 2y − s₂ + t₁ = 30, where s₂ is a surplus recording the excess over 30 and t₁ is an artificial variable providing a starting solution. B1 for the slack equation, B1 for the surplus, B1 for the artificial variable.

Question 3

State what the feasible region of a linear program is, and state why the optimum of a linear objective over a bounded feasible region can always be found at a vertex.

Accepted Answer

The feasible region is the set of points satisfying every constraint at once, non-negativity included: on a two-variable graph it is the region left unshaded by all of them together. B1.
Along any straight line the objective changes at a constant rate, so on a segment of the region's boundary its largest and smallest values occur at the ends. Working outwards from any interior point to the boundary and then along it brings you to a corner without ever making the objective worse, so a vertex always attains the optimum. B1.
The optimum need not be at only one vertex: when the objective runs parallel to an edge, every point of that edge is optimal, and both of its ends are among them.

Question 4

A linear program maximises P = 5x + 3y. Two vertices of its feasible region are (2, 6) and (5, 1). Write down the gradient of a line of constant P, and state which of the two vertices the objective prefers.

Accepted Answer

Lines of constant P satisfy 5x + 3y = c, that is y = (c − 5x)/3, so the gradient is −5/3. B1.
At (2, 6): P = 10 + 18 = 28. At (5, 1): P = 25 + 3 = 28. M1 for evaluating at both vertices.
The two are tied, so neither is preferred. A1.
The segment joining (2, 6) to (5, 1) has gradient (1 − 6)/(5 − 2) = −5/3, the same as the objective line, so the objective runs parallel to that edge and takes the value 28 at every point of it, the midpoint (3.5, 3.5) included. A tie between two adjacent vertices is the sign of this, and the answer to give is the whole edge rather than a choice between its ends.

Question 5

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.

Accepted 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 opens with the objective function, not with a constraint.
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.

Question 6

Maximise P = 4x + 5y subject to x + y ≤ 10, 2x + 3y ≤ 24 and x, y ≥ 0, using the vertex method.

Accepted 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.

Question 7

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.

Accepted 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.

Question 8

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.

Accepted Answer

At (6, 4): 6 + 4 + s₁ = 10 gives s₁ = 0, and 12 + 12 + s₂ = 24 gives s₂ = 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.

Question 9

A farmer mixes two feeds. Feed X costs £4 a sack and supplies 3 units of protein and 1 unit of fibre; feed Y costs £6 a sack and supplies 2 units of protein and 4 units of fibre. The mix must supply at least 24 units of protein and at least 20 units of fibre, and at most 12 sacks in total may be used. Formulate this as a linear program.

Accepted Answer

Let x be the number of sacks of feed X used and y the number of sacks of feed Y. B1 for defining both variables in words with their units.
Minimise C = 4x + 6y, the cost in pounds. B1 for the objective, and for saying that it is to be minimised.
Protein: 3x + 2y ≥ 24. Fibre: x + 4y ≥ 20. B1 for the two supply constraints.
Sacks: x + y ≤ 12, with x ≥ 0, y ≥ 0. B1 for the sack limit together with the non-negativity conditions.
The inequalities point in both directions here, which is what a minimising problem usually looks like: a requirement to be met at least, and a resource not to be exceeded. Write the units on each line while forming it, since a protein constraint and a sack constraint are not measured in the same thing.

Question 10

Minimise C = 4x + 6y subject to 3x + 2y ≥ 24, x + 4y ≥ 20, x + y ≤ 12 and x, y ≥ 0, using the vertex method.

Accepted Answer

The feasible region is bounded by the three constraint lines and the axes. Testing the possible intersections, it has three vertices: (0, 12), where 3x + 2y = 24 meets x + y = 12; (9⅓, 2⅔), where x + 4y = 20 meets x + y = 12; and the meeting of the two supply lines. M1 for identifying the vertices.
Solving 3x + 2y = 24 with x + 4y = 20: from the second, x = 20 − 4y, so 60 − 12y + 2y = 24, giving −10y = −36, y = 3.6 and x = 5.6. M1 for solving the pair simultaneously, A1 for (5.6, 3.6).
Cost at each vertex: (0, 12) gives 0 + 72 = 72; (9⅓, 2⅔) gives 37⅓ + 16 = 53⅓; (5.6, 3.6) gives 22.4 + 21.6 = 44. M1 for evaluating C at every vertex, A1 for the minimum of £44 at (5.6, 3.6).
Both supply constraints are tight there, at exactly 24 units of protein and 20 of fibre, while the mix uses 9.2 of the 12 sacks allowed. There is no vertex on the x-axis: 24 units of protein from feed X alone would take 8 sacks, but 20 units of fibre would take 20, and 20 sacks break the sack limit.

Question 11

For the linear program that maximises P = 4x + ky subject to x + y ≤ 10, 2x + 3y ≤ 24 and x, y ≥ 0, the optimum is at (6, 4) when k = 5. Find the values of k for which (6, 4) is still optimal.

Accepted Answer

The vertex (6, 4) is where x + y = 10 meets 2x + 3y = 24. The first line has gradient −1 and the second −2/3. M1 for both gradients.
A line of constant P satisfies 4x + ky = c, so it has gradient −4/k. The last corner an objective line touches on its way out of the region is (6, 4) exactly while that gradient lies between the gradients of the two edges meeting there: −1 ≤ −4/k ≤ −2/3, that is 2/3 ≤ 4/k ≤ 1. M1 for placing the objective gradient between the two.
With k positive, 4/k ≤ 1 gives k ≥ 4 and 4/k ≥ 2/3 gives k ≤ 6. A1 for one end, A1 for 4 ≤ k ≤ 6.
At each end the objective runs parallel to one of the edges and a whole edge is optimal: at k = 4 the value 40 is shared with (10, 0), and at k = 6 the value 48 is shared with (0, 8). Outside the interval the optimum moves to whichever of those two vertices the objective now favours.

Question 12

The shaded region on the graph is the feasible region of a linear programming problem in x and y. Use the graph to find the maximum value of P = 3x + 5y over that region, and state the point at which it occurs. The return on y then falls, so that the objective becomes P = 3x + 3y. Find the maximum value of this new objective and the point at which it now occurs.

Accepted Answer

A linear objective over a bounded feasible region takes its greatest value at a vertex, so read the vertices off the grid: (0, 0), (8, 0), (6, 4), (2, 7) and (0, 5). M1 for reading all five vertices off the graph.
Evaluating P = 3x + 5y at each: 3(0) + 5(0) = 0; 3(8) + 5(0) = 24; 3(6) + 5(4) = 18 + 20 = 38; 3(2) + 5(7) = 6 + 35 = 41; 3(0) + 5(5) = 25. A1 for the five values.
The maximum is P = 41, at (2, 7). A1 for the maximum and the vertex it occurs at.
With P = 3x + 3y the same five vertices give 0; 24; 18 + 12 = 30; 6 + 21 = 27; 15. M1 for re-evaluating at every vertex rather than assuming the old vertex still wins.
The maximum is now P = 30, at (6, 4). A1 for the new maximum and its vertex.
Cutting the coefficient of y has tilted the objective line from a gradient of −3/5 to one of −1, steep enough for the last corner it leaves to change: the optimum moves from (2, 7) to (6, 4).

Question 13

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.

Accepted 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) rounds x up but y down.

Question 14

A linear program maximises P = 4x + 5y subject to x + y ≤ 10, 2x + 3y ≤ 24 and x, y ≥ 0, and its optimum is P = 44 at (6, 4). One extra unit of the first resource is offered, so that the first constraint becomes x + y ≤ 11. Find the new optimum, and state what the extra unit is worth. Do the same for a change of the second constraint to 2x + 3y ≤ 25.

Accepted Answer

With x + y ≤ 11 and 2x + 3y ≤ 24: solving x + y = 11 with 2x + 3y = 24 gives 22 − 2y + 3y = 24, so y = 2 and x = 9. The vertices are (0, 0), (11, 0) with P = 44, (0, 8) with P = 40 and (9, 2) with P = 36 + 10 = 46. M1 for re-solving, A1 for (9, 2) and 46.
The gain is 46 − 44 = 2, so one more unit of the first resource is worth 2. B1.
With x + y ≤ 10 and 2x + 3y ≤ 25: solving gives 20 − 2y + 3y = 25, so y = 5 and x = 5, and P = 20 + 25 = 45, against 40 at (10, 0) and 41⅔ at (0, 8⅓). M1 for re-solving with the second constraint changed, A1 for 45, so the second resource is worth 1 a unit.
Both slacks were zero at (6, 4), which is why relaxing either constraint gains anything at all. Relaxing a constraint that still has slack at the optimum adds no profit, because the optimum is not pressing against it. Neither figure holds for ever: enough extra units and the optimal vertex moves onto a different pair of lines, after which the next unit is worth something else.

Question 15

Maximise P = 5x + 4y subject to 2x + 3y ≤ 12, 4x + y ≤ 10 and x, y ≥ 0, where x and y must both be whole numbers. The corresponding problem without the whole-number requirement has its optimum P = 20.2 at (1.8, 2.8). Use branch and bound, branching first on x, to find the integer optimum.

Accepted Answer

The relaxation gives x = 1.8, which is not a whole number, so branch on x into x ≤ 1 and x ≥ 2: no integer point is excluded, since no whole number lies strictly between 1 and 2. M1 for the branching.
Branch x ≥ 2. The constraint 4x + y ≤ 10 caps x at 2.5, and the best point of this branch is (2, 2), where 4(2) + 2 = 10 and 2(2) + 3(2) = 10, giving P = 18. Both coordinates are whole numbers, so this is a genuine solution and 18 becomes the best value found so far. A1.
Branch x ≤ 1. Its relaxation sits at (1, 10/3), giving P = 5 + 40/3 = 18⅓. That exceeds 18, so the branch may still hold something better and must be explored. M1 for the bound, A1 for 18⅓.
y = 10/3 is not a whole number, so branch again into y ≤ 3 and y ≥ 4. With x ≤ 1 and y ≤ 3 the best point is (1, 3), giving P = 17. With x ≤ 1 and y ≥ 4, the constraint 2x + 3y ≤ 12 forces x = 0 and y = 4, giving P = 16. M1 for the second branching.
Both are below 18, so both branches close and the integer optimum is P = 18 at (2, 2). A1.
A branch is closed either by producing a whole-number point or by having a bound no better than the best solution already in hand.

Question 16

The constraints y ≤ x + 4, y ≥ x − 4, x ≥ 0 and y ≥ 0 define an unbounded feasible region. Show that P = x + y has no maximum there, and state what would have to be added to give it one. State also why a bounded non-empty feasible region always gives a maximum.

Accepted Answer

Take the point (t, t) for any t ≥ 0. Then y ≤ x + 4 reads t ≤ t + 4, which holds; y ≥ x − 4 reads t ≥ t − 4, which holds; and both coordinates are non-negative. So every such point is feasible. M1 for testing a family of points.
There P = t + t = 2t, which can be made as large as we please by taking t large: 10 at t = 5, 1000 at t = 500. So P has no maximum on this region. A1.
Adding any constraint that closes the region off in the direction the objective grows would give one, for instance x + y ≤ 30, or separate limits x ≤ 20 and y ≤ 20. B1 for a constraint that bounds the region.
On a bounded region the reasoning runs the other way. The objective changes at a constant rate along any straight line, so on each edge its greatest value is at an end, and a region with finitely many vertices has finitely many such values to compare. B1 for the constant rate along an edge, B1 for the greatest value being attained at a vertex.
An unbounded region is not by itself a failure: minimising x + y on this same region gives 0 at the origin without difficulty.