Linear programming (NF)
A standard method from Inequalities and linear programming: the steps and worked examples.
Steps
- Define the unknowns: "Let x be the number of …".
- Write the constraints as inequalities, including x ≥ 0, y ≥ 0 and "integers" if needed.
- Draw each boundary line and find the feasible region, where every constraint is true. Follow the question's shading convention.
- Find the vertices of the region (solve pairs of boundary lines simultaneously).
- Test the objective function at each vertex. The maximum or minimum is at a vertex.
- If the answer must be an integer and a vertex isn't, test the nearby integer points inside the region.
Why a vertex: the objective function is a straight line sliding across the region; it last touches the region at a corner.
Worked examples
Example 1: Linear programming (NF): maximise P = 30x + 40y subject to x + y ≤ 12, x + 2y ≤ 16, x ≥ 0, y ≥ 0.
vertices: (0, 0), (12, 0), (8, 4), (0, 8)
[(8, 4) from x + y = 12 and x + 2y = 16]
P: 0, 360, 400, 320
maximum P = 400 at x = 8, y = 4Example 2: Linear programming (NF), a word problem: a workshop makes chairs and tables. A chair needs 1 hour of cutting and 2 hours of finishing; a table needs 3 hours of cutting and 2 hours of finishing. Each day there are at most 15 hours of cutting and 14 hours of finishing. The profit is $50 per chair and $90 per table. How many of each give the greatest profit?
Let x be the number of chairs and y the number of tables.
constraints: x + 3y ≤ 15 cutting
2x + 2y ≤ 14, i.e. x + y ≤ 7 finishing
x ≥ 0, y ≥ 0, x and y integers
objective: P = 50x + 90y
vertices: (0, 0), (7, 0), (3, 4), (0, 5)
[(3, 4) from x + 3y = 15 and x + y = 7]
P: 0, 350, 510, 450
greatest profit $510: 3 chairs and 4 tablesFor the whole topic, read Inequalities and linear programming: key points, common mistakes and how the DSE tests it.