Formulating and graphical solution of LPs

Formulating and graphical solution of LPs

Spec DD1–DD2 · AQA A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A linear programme has decision variables, a linear objective function and linear constraints, including x≥0x\ge0, y≥0y\ge0.
  • Each constraint is drawn as a boundary line; shade the unwanted side to leave the feasible region.
  • The optimum is always at a vertex of the feasible region.
  • Slide the objective line away from the origin to maximise and towards it to minimise, or test every vertex.
  • Give the answer in context: how many of each, and the profit or cost.

Formulating a linear programme

Define the variables, write the objective to maximise or minimise, write each limit as an inequality, and add x≥0x\ge0, y≥0y\ge0.

To formulate a problem:

  1. Define the decision variables, e.g. xx tables and yy chairs.
  2. Write the objective function to maximise (profit) or minimise (cost), e.g. P=50x+30yP=50x+30y.
  3. Write each constraint as an inequality in consistent units, e.g. 4x+2y≤404x+2y\le40 for 40 hours of carpentry when a table takes 4 hours and a chair takes 2.
  4. Include the non-negativity constraints x≥0x\ge0, y≥0y\ge0.
246810125101520xy(0, 20)(5, 10)4x + 2y = 40y = 2x
4x + 2y ≤ 40 and y ≥ 2x with x, y ≥ 0: the feasible region has vertices (0, 0), (0, 20) and (5, 10).

Words

  • at most
  • at least
  • at least twice as many chairs (yy) as tables (xx)

Inequality

  • ≤\le
  • ≥\ge
  • y≥2xy\ge2x

Worked example

A firm makes tables (xx) and chairs (yy). A table takes 4 hours of carpentry and a chair 2 hours, with 40 hours available. Profit is £50 per table and £30 per chair. Formulate the problem.

Which inequality means 'at least twice as many chairs (yy) as tables (xx)'?

Drawing the feasible region

Draw each boundary line, shade the side you do not want, and the region left clear is feasible.

For each constraint, draw its boundary line using two points, often the axis intercepts. For 2x+y≤142x+y\le14 the intercepts are (7,0)(7,0) and (0,14)(0,14).

Test a point such as the origin to see which side satisfies the inequality, and shade the unwanted side. The feasible region is the set of points satisfying every constraint, and its corners are vertices.

A vertex is an axis intercept or comes from solving two boundary equations simultaneously: 2x+y=142x+y=14 and x+2y=10x+2y=10 meet at (6,2)(6,2).

12345678910112468101214xy(7, 0)(6, 2)(0, 5)2x + y = 14x + 2y = 10
Feasible region below both lines; vertices (0, 0), (7, 0), (6, 2), (0, 5).

What are the axis intercepts of 3x+2y=123x+2y=12?

The objective line method

Slide a line of constant objective value across the region; the last (or first) vertex it touches is optimal.

Write the objective as ax+by=kax+by=k. It is a line of gradient −ab-\frac ab, and different values of kk give parallel lines. Draw one through the feasible region, then slide it parallel to itself.

  • To maximise, move it away from the origin to the last point of the region it touches, the optimal vertex.
  • To minimise, move it towards the origin to the first point it touches.

Example: P=3x+2yP=3x+2y has gradient −32-\frac32, between the gradients −2-2 and −12-\frac12 of the two constraint lines, so the optimum is (6,2)(6,2), giving P=22P=22.

12345678910112468101214xy(6, 2)2x + y = 14x + 2y = 103x + 2y = 22
The objective line (dashed) touches the region only at the optimum (6, 2).

To minimise a cost, which way do you slide the objective line?

The vertex testing method

The optimum is always at a vertex, so evaluate the objective at each vertex and pick the greatest or least.

List every vertex, evaluate the objective function at each, and choose the greatest (maximise) or least (minimise).

For P=3x+2yP=3x+2y the vertices (0,0)(0,0), (7,0)(7,0), (6,2)(6,2), (0,5)(0,5) give 00, 2121, 2222, 1010, so the maximum is 22.

This method is reliable, and it also shows near-optimal vertices.

05101520(0, 0)(7, 0)(6, 2)(0, 5)VertexP
P=3x+2yP=3x+2y at each vertex: the maximum is 22 at (6, 2).

Worked example (minimising)

Minimise C=3x+4yC=3x+4y over the vertices (6,3)(6,3), (4,6)(4,6) and (8,2)(8,2).

Maximise P=2x+3yP=2x+3y over the vertices (1,4)(1,4), (3,3)(3,3) and (5,1)(5,1). Which vertex is optimal?

Solving and interpreting in context

State the answer in the language of the problem, with units, and recheck the optimum if a constraint changes.

Say how many of each item to make, and the maximum profit or minimum cost.

Example: in a school shop with 3x+2y≤1203x+2y\le120, x+y≤50x+y\le50, y≥15y\ge15 and profit 4x+3y4x+3y, the optimum is (20,30)(20,30) with profit £170. Adding x≥yx\ge y makes (20,30)(20,30) infeasible, and the new optimum is (24,24)(24,24) with profit £168.

To check a point is feasible, substitute it into every constraint. A point such as (5,4)(5,4) in a feed problem requiring protein 3x+2y≥243x+2y\ge24 gives 2323, so it fails.

510152025303540451020304050xy(20, 30)(24, 24)3x + 2y = 120x + y = 50y = 15y = x
3x + 2y ≤ 120, x + y ≤ 50, y ≥ 15. The profit 4x + 3y is greatest at (20, 30), £170. Adding x ≥ y (dashed) moves the optimum to (24, 24), £168.

Original constraints

  • Optimum (20,30)(20,30)
  • Profit £170

With x≥yx\ge y added

  • (20,30)(20,30) is infeasible
  • Optimum (24,24)(24,24)
  • Profit £168

Is (4,3)(4,3) feasible for 2x+y≤142x+y\le14 and x+2y≤10x+2y\le10?

Try an exam question

Maximise P=5x+4yP=5x+4y subject to x+y≤8x+y\le8, 2x+y≤122x+y\le12, x≥0x\ge0, y≥0y\ge0. Use the vertices of the feasible region.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Which inequality models the carpentry limit?

1 mark, marked against the mark scheme

Revision notes