Formulating and graphical solution of LPs
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 , .
- 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 , .
To formulate a problem:
- Define the decision variables, e.g. tables and chairs.
- Write the objective function to maximise (profit) or minimise (cost), e.g. .
- Write each constraint as an inequality in consistent units, e.g. for 40 hours of carpentry when a table takes 4 hours and a chair takes 2.
- Include the non-negativity constraints , .
Words
- at most
- at least
- at least twice as many chairs () as tables ()
Inequality
Worked example
A firm makes tables () and chairs (). 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.
- 1
Decision variables: = number of tables, = number of chairs.
- 2
Objective: maximise .
- 3
Carpentry: .
- 4
Quantities cannot be negative: , .
Which inequality means 'at least twice as many chairs () as tables ()'?
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 the intercepts are and .
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: and meet at .
What are the axis intercepts of ?
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 . It is a line of gradient , and different values of 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: has gradient , between the gradients and of the two constraint lines, so the optimum is , giving .
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 the vertices , , , give , , , , so the maximum is 22.
This method is reliable, and it also shows near-optimal vertices.
Worked example (minimising)
Minimise over the vertices , and .
- 1
At : .
- 2
At : .
- 3
At : .
- 4
Choose the least value.
Maximise over the vertices , and . 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 , , and profit , the optimum is with profit £170. Adding makes infeasible, and the new optimum is with profit £168.
To check a point is feasible, substitute it into every constraint. A point such as in a feed problem requiring protein gives , so it fails.
Original constraints
- Optimum
- Profit £170
With added
- is infeasible
- Optimum
- Profit £168
Is feasible for and ?
Try an exam question
Maximise subject to , , , . Use the vertices of the feasible region.
[4 marks]
- [1]The vertices on the axes are , and .
- [1]Solving and gives the vertex .
- [1]The values of are , , and .
- [1]The maximum is at .
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
Which inequality models the carpentry limit?
1 mark, marked against the mark scheme