Graphical solution of linear programs
Studying this course? Keep your progress in one place.
Key facts
- Draw each boundary line, test a point, and shade out the unwanted side to leave the feasible region.
- The optimum is at a vertex of the feasible region: evaluate the objective at every vertex.
- In the ruler method, slide the objective line parallel to itself: the last point touched gives a maximum, the first gives a minimum.
- A minimisation problem usually has constraints, so its region lies away from the origin.
- With integer variables, test integer points inside the region: never just round, and the integer optimum is never better.
Drawing the feasible region
Draw each constraint as a boundary line, shade out the unwanted side, and the region left clear is the feasible region. Its corners are the vertices.
For each constraint, draw the boundary line by replacing the inequality sign with . Test a point such as the origin to decide which side satisfies it.
Shade out the unwanted side so that the feasible region is left clear. The axes bound it from .
The corners are its vertices. Find exact coordinates by solving the two boundary equations. For and , subtracting gives , so the vertex is .
Is the origin in the feasible region for the constraint ?
The vertex method
An optimum always occurs at a vertex of the feasible region, so evaluate the objective at every vertex and pick the largest or smallest.
An optimal solution of a linear program always occurs at a vertex of the feasible region, or along an edge between two vertices that give the same value.
- Find the coordinates of every vertex.
- Evaluate the objective function at each vertex.
- Choose the largest value (maximise) or the smallest (minimise).
State the values of both variables and the objective at the end.
| P = 5x + 4y | Compare | |
|---|---|---|
| (0, 0) | 0 | Smaller |
| (6, 0) | 30 | Smaller |
| (4, 6) | 44 | Largest: the maximum |
| (0, 10) | 40 | Smaller |
P = 5x + 4y
- (0, 0):
- 0
- (6, 0):
- 30
- (4, 6):
- 44
- (0, 10):
- 40
Compare
- (0, 0):
- Smaller
- (6, 0):
- Smaller
- (4, 6):
- Largest: the maximum
- (0, 10):
- Smaller
Worked example
Maximise with vertices , , and .
- 1
At : .
- 2
At : .
- 3
At : .
- 4
At : .
Vertices give , , and . Which is the maximum, and where?
The ruler method
The objective function is a family of parallel lines. Slide a ruler along one of them: the last feasible point it touches moving away from the origin is the maximum.
The objective gives parallel lines, one for each value of , each with gradient .
- Draw one objective line, choosing a convenient value of .
- Slide a ruler parallel to it.
- To maximise, move away from the origin: the optimum is the last point of the region touched. To minimise, the optimum is the first point touched.
- Read off the vertex, solve the boundary equations for exact coordinates, then calculate .
- Gradient of
What is the gradient of the objective line ?
Minimisation problems
Minimisation problems usually have ≥ constraints, so the region lies on the far side of the lines from the origin, and the optimum is the first point touched.
Minimisation problems usually have constraints of the form , such as requirements for energy or protein.
The optimum is the point that makes the objective as small as possible. With the ruler, it is the first point of the region touched when the line moves away from the origin.
Worked example
Minimise subject to , , .
- 1
The vertices are , , and . The point is found by solving and .
- 2
At : .
- 3
At : .
- 4
At : . At : .
For , what is at the vertex ?
Integer solutions
The optimum is the best integer point inside the feasible region. The optimal vertex may be fractional, so do not just round.
If and must be whole numbers, the optimal vertex may be fractional. The solution is then the best integer point inside the feasible region.
Do not just round: a rounded point may lie outside the region or not be the best.
Find the optimal vertex, then test integer points near it, checking every constraint. Or move the objective line back from the optimal vertex until it first passes through a feasible integer point.
The integer optimum is never better than the non-integer optimum.
Worked example
Maximise subject to and , with integers.
- 1
The vertex is , giving .
- 2
is infeasible: .
- 3
is feasible with .
- 4
The other points are worse: gives and gives .
In a maximisation problem with integer variables, how does the integer optimum compare with the non-integer optimum?
Try an exam question
Maximise subject to , , and . Use the vertex method, showing the vertices of the feasible region and the value of at each.
[4 marks]
- [1]Vertices (0, 0), (6, 0), (4, 4) and (0, 8), with (4, 4) found by solving and .
- [1]P = 0 at (0, 0) and P = 18 at (6, 0).
- [1]P = 20 at (4, 4) and P = 16 at (0, 8).
- [1]The maximum is P = 20 when x = 4 and y = 4.
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