Graphical solution of linear programs
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.
- Draw the line, e.g. through and .
- Test a point such as to decide which side satisfies the inequality.
- 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.
Where do and meet?
The objective line method
Slide the objective line parallel across the region. To maximise, the optimum is the last vertex it touches.
For the objective line has gradient , and every point on it gives the same .
Draw one such line (for example ) 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.
Worked example
Find the optimal value of at the vertex .
- 1
Substitute: .
- 2
.
What is the gradient of the line ?
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 with vertices and gives 10 at both.
- 0
- 30
- 34
- 20
Maximise using only the vertices , , . Which gives the largest ?
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.
Worked example
Maximise subject to , , with whole numbers.
- 1
Ignoring the integer condition, the optimum is with .
- 2
is infeasible and gives only 18.
- 3
Try : and , so it is feasible, with .
- 4
and is a whole number, so .
Why is rounding the vertex up to 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 with and , 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".
- 32
- 45
Worked example
The cost is in whole kilograms. Find the minimum with and whole.
- 1
The minimum is at with .
- 2
is a whole number, so .
- 3
Try : and , so it is feasible, with .
Why can the minimum whole-number cost not be below 29?
Try an exam question
Maximise subject to , , , , by finding the vertices of the feasible region.
[4 marks]
- [1]The axis vertices , and are found.
- [1]Solving and gives the vertex .
- [1] at the vertices is 0, 40, 18 and 36.
- [1]The maximum is at .
That's the notes covered.
Carry on to the next subtopic.
Try a question
Find the coordinates of the point where the lines and meet.
1 mark, marked against the mark scheme
Find the coordinates of the point where the lines and meet.
1 mark, marked against the mark scheme