Graphical solution of linear programs

Graphical solution of linear programs

Spec 5.2 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • Each constraint is a half-plane; shade out the unwanted side to leave the feasible region.
  • The optimum is always at a vertex of the feasible region.
  • With the objective line method, slide a line parallel to the objective: last vertex to maximise, first to minimise.
  • With the vertex method, evaluate the objective at every vertex.
  • For integer solutions, rounding is unsafe: compare nearby whole-number feasible points.

The feasible region

Draw each boundary line, shade out the side that fails the inequality, and keep the region inside all constraints in the first quadrant.

With two variables each constraint is a half-plane bounded by a straight line.

  1. Draw the line, e.g. 2x+y=122x+y=12 through (6,0)(6,0) and (0,12)(0,12).
  2. Test a point such as (0,0)(0,0) to decide which side satisfies the inequality.
  3. Shade out the unwanted side.

What is left, inside all constraints and in the first quadrant, is the feasible region. Its corners are vertices, found by solving two boundary equations simultaneously.

−11234567824681012xy(6, 0)(0, 5)(14/3, 8/3)2x + y = 12x + 2y = 10
The boundary lines meet at (14/3, 8/3).
65OABC
The feasible region for 2x+y≤122x+y\le12, x+2y≤10x+2y\le10, x,y≥0x,y\ge0.

Where do 2x+y=122x+y=12 and x+2y=10x+2y=10 meet?

The objective line method

Slide the objective line parallel across the region. To maximise, the optimum is the last vertex it touches.

For P=5x+4yP=5x+4y the objective line 5x+4y=k5x+4y=k has gradient −54-\frac54, and every point on it gives the same P=kP=k.

Draw one such line (for example k=20k=20) and slide it parallel across the feasible region.

  • To maximise, move it away from the origin: the optimum is the last vertex it touches.
  • To minimise, move it towards the origin: the optimum is the first vertex it touches.

Then read off the vertex and substitute to find the optimal value.

−1123456782468xyoptimum2x + y = 12x + 2y = 105x + 4y = 20
Dashed: the objective line 5x + 4y = 20, to slide parallel.

Worked example

Find the optimal value of P=5x+4yP=5x+4y at the vertex (143,83)\left(\frac{14}{3},\frac83\right).

What is the gradient of the line 5x+4y=k5x+4y=k?

The vertex method

Find every vertex, evaluate the objective at each, and take the largest (maximise) or smallest (minimise).

The optimum of a linear objective over a feasible region always occurs at a vertex. Find the coordinates of every vertex, evaluate the objective at each, and pick the largest (maximise) or smallest (minimise).

If the objective line is parallel to a boundary edge, two vertices tie and every point on that edge is optimal. For example, maximising 2x+y2x+y with vertices (5,0)(5,0) and (3,4)(3,4) gives 10 at both.

−1123456782468xy(6, 0): 30(14/3, 8/3): 34(0, 5): 202x + y = 12x + 2y = 105x + 4y = 34
Values of P = 5x + 4y at each vertex; the dashed line 5x + 4y = 34 touches only the optimum.

(0,0)(0,0)

  • 0

(6,0)(6,0)

  • 30

(143,83)\left(\frac{14}{3},\frac83\right)

  • 34

(0,5)(0,5)

  • 20

Maximise P=5x+4yP=5x+4y using only the vertices (0,0)(0,0), (6,0)(6,0), (0,5)(0,5). Which gives the largest PP?

Integer solutions

Rounding the optimum is unsafe. Find the non-integer optimum, then compare nearby whole-number feasible points.

Sometimes the variables must be whole numbers (vehicles, boxes). The optimal vertex is often not whole, and rounding is unsafe: the rounded point may be infeasible or not optimal.

Find the non-integer optimum first, then list whole-number feasible points close to it, calculate the objective at each and compare.

If the objective has whole-number coefficients, a whole-number point gives a whole-number value, which gives a neat bound.

−1123456782468xy(6.5, 0)(5, 2)4x + 3y = 26x + 2y = 103x + 2y = 19.5
Maximise 3x + 2y: the optimum (6.5, 0) is not whole; (5, 2) is the best whole point.

Worked example

Maximise P=3x+2yP=3x+2y subject to 4x+3y≤264x+3y\le26, x+2y≤10x+2y\le10, with x,yx,y whole numbers.

Why is rounding the vertex (6.5,0)(6.5,0) up to (7,0)(7,0) wrong here?

Minimising

Find the vertices and compare the cost at each. For whole numbers, round the bound up and look for a feasible point reaching it.

To minimise C=3x+4yC=3x+4y with x+y≥8x+y\ge8 and 2x+5y≥302x+5y\ge30, find the vertices and compare.

For a minimum, the region lies away from the origin, so the optimum is the first vertex the objective line touches as it moves from the origin.

State the answer in context with units, for example "minimum cost £29 using 3 kg of X and 5 kg of Y".

246810121416246810xy(0, 8): 32(10/3, 14/3): 28.67(15, 0): 45x + y = 82x + 5y = 30C = 86/3
Minimising C = 3x + 4y: the dashed line 3x + 4y = 86/3 touches the region first at the optimum.

(0,8)(0,8)

  • 32

(103,143)\left(\frac{10}{3},\frac{14}{3}\right)

  • 863≈28.67\frac{86}{3}\approx28.67

(15,0)(15,0)

  • 45

Worked example

The cost is in whole kilograms. Find the minimum with xx and yy whole.

Why can the minimum whole-number cost not be below 29?

Try an exam question

Maximise P=4x+3yP=4x+3y subject to x+y≤10x+y\le10, x+3y≤18x+3y\le18, x≥0x\ge0, y≥0y\ge0, by finding the vertices of the feasible region.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Find the coordinates of the point where the lines 2x+y=122x+y=12 and x+2y=10x+2y=10 meet.

1 mark, marked against the mark scheme

Revision notes