Linear programming
Studying this course? Keep your progress in one place.
Key facts
- Each limit becomes a constraint, an inequality; counts also satisfy , .
- Draw each boundary: solid for , and dashed for , ; test to shade.
- The feasible region is where all constraints are met; its corners are vertices.
- The best value of the objective function is at a vertex.
- Answer in a sentence in context.
Forming inequalities
Choose variables, then turn each limit into a constraint using the correct inequality sign.
Each limit becomes a constraint. Counts cannot be negative, so also write and .
A ratio statement becomes an inequality: "children at most three times the adults" is .
Resource limits add up each item's use: .
| At most, no more than | At least, no fewer than | Fewer than | More than | |
|---|---|---|---|---|
| Symbol | ||||
| Example |
At most, no more than
- Symbol:
- Example:
At least, no fewer than
- Symbol:
- Example:
Fewer than
- Symbol:
- Example:
More than
- Symbol:
- Example:
A café bakes x cakes and y pies. It must bake at least twice as many pies as cakes. Which inequality is correct?
Graphing an inequality
Draw the boundary line, solid for ≤ or ≥ and dashed for < or >, then shade the side where a test point makes it true.
- Change the inequality to an equals sign and draw the boundary line using two points, such as the axis intercepts.
- Solid line for , ; dashed for , .
- Test and shade the side where the inequality is true.
For the boundary passes through and . is true, so shade the side containing the origin.
Worked example
Show on a graph.
- 1
Boundary passes through and .
- 2
The sign is , so draw a solid line.
- 3
Test : is false.
- 4
So shade the side that does not contain the origin.
What kind of boundary line does need?
The feasible region and its vertices
The feasible region is where all the shaded regions overlap; find each vertex by solving the two boundary equations that meet there.
Every point inside satisfies every constraint. Take , , and . The vertices on the axes are , and ; the fourth is where the two lines cross.
Worked example
Find the vertex where and meet.
- 1
From the first equation, .
- 2
Substitute into the second: .
- 3
Expand: , so and .
- 4
Then .
Is the point in the feasible region?
The objective function
Evaluate the objective function at every vertex and choose the largest (to maximise) or smallest (to minimise).
The objective function is the quantity to maximise or minimise, such as .
For vertices the values are . The maximum profit is \260(6,4)$.
Minimising works the same way: for with vertices and , the minimum is at .
The vertices are and . Where is largest?
Solving a real-life problem
Define variables, write the constraints and objective, find the vertices, evaluate and answer in context.
If the variables must be whole numbers, check that the optimal vertex is a whole-number point; if not, test nearby whole-number points inside the region.
- 1
Define the variables
for example x and y
- 2
Write the constraints
and the objective function
- 3
Draw the feasible region
or find its vertices
- 4
Evaluate at each vertex
the objective function
- 5
Answer in context
a sentence about the real situation
Worked example
A charity has 40 kg of rice and 36 kg of lentils. A Type A parcel uses 4 kg rice and 2 kg lentils. A Type B parcel uses 2 kg rice and 3 kg lentils. Type A feeds 5 people and Type B feeds 4. Find the plan that feeds the most people.
- 1
Let be the Type A parcels and the Type B parcels.
- 2
Constraints: , , , .
- 3
Objective: maximise people fed, .
- 4
Vertices: , , and , where solves both boundary equations.
- 5
Values of : .
Why must the final answer be written as a sentence in context?
Try an exam question
The vertices of a feasible region are , , and . Find the maximum value of .
[3 marks]
- [1]Evaluate P at each vertex: 0, 240, 140 and 260.
- [1]The largest value is at the vertex (6, 4).
- [1]The maximum value of P is 260.
That's the notes covered.
Carry on to the next subtopic.
Try a question
Which inequality shows that the minibus carries at most 14 people?
1 mark, marked against the mark scheme
Which inequality shows that the minibus carries at most 14 people?
1 mark, marked against the mark scheme