Linear Programming
Linear programming turns a practical constraint problem into inequalities, shades the region where every constraint holds at once, and then finds the best point in that region. Each constraint becomes a straight line: a strict inequality is drawn as a dashed line and one with an equals part as a solid line, and the side satisfying the inequality is identified by testing a point. The feasible region is the area satisfying all the constraints simultaneously. Because the objective being maximised or minimised is itself linear, its best value always occurs at a vertex of the feasible region, so the method is to find the vertices and evaluate the objective at each.
Before you start
No specific prerequisites - this is a good place to start.
Method
- Define the variables explicitly, saying what x and y stand for, including units, before writing anything else.
- Turn each sentence of the problem into an inequality. At least becomes greater than or equal to, at most becomes less than or equal to, and quantities that cannot be negative give x greater than or equal to 0 and y greater than or equal to 0.
- Draw each boundary line by finding two points, usually where it crosses each axis. Use a dashed line for a strict inequality and a solid line where equality is allowed.
- Decide which side to shade by testing a point not on the line, usually the origin: if it satisfies the inequality, that is the side that holds. State clearly whether you are shading the required region or the unwanted region, and label R.
- Identify the vertices of the feasible region, reading them from the graph and confirming them by solving the two boundary equations simultaneously where the reading is not exact.
- Evaluate the objective at every vertex and choose the largest or smallest as required. If the answer must be a whole number of items, check the nearest lattice points inside the region rather than accepting a fractional vertex.
Worked example
A workshop makes x chairs and y tables. It can make at most 10 items in total, must make at least 2 tables, and must make at least 1 chair. The profit is 5 pounds per chair and 3 pounds per table. Find the number of each that maximises profit.
- Write the constraints: x + y is less than or equal to 10, y is greater than or equal to 2, and x is greater than or equal to 1.
- The objective is P = 5x + 3y, to be maximised.
- Find the vertices of the feasible region. The lines x = 1 and y = 2 meet at (1, 2). The line x = 1 meets x + y = 10 at (1, 9). The line y = 2 meets x + y = 10 at (8, 2).
- Evaluate the objective at each vertex: at (1, 2), P = 5 + 6 = 11; at (1, 9), P = 5 + 27 = 32; at (8, 2), P = 40 + 6 = 46.
- The largest value is 46, at the vertex (8, 2).
- Answer in context: make 8 chairs and 2 tables for a maximum profit of 46 pounds. Both values are whole numbers, so no adjustment is needed.
Practice questions
Type your answer and press Check to be marked straight away, or reveal the answer and mark yourself.
Q1Write the inequality for: the number of tickets, t, must be at least 15.Show answer
Answer: t is greater than or equal to 15.
Q2When is a boundary line drawn dashed rather than solid?Show answer
Answer: When the inequality is strict (greater than or less than), so points on the line itself are not included.
Q3How do you decide which side of a line to shade?Show answer
Answer: Substitute the coordinates of a point not on the line, usually the origin, into the inequality. If it is satisfied, that side is the one the inequality describes.
Q4Why is it enough to test only the vertices of the feasible region?Show answer
Answer: Because the objective is linear, so its maximum and minimum over a polygonal region always occur at a vertex.
Q5Find where the lines x + y = 12 and y = 3 intersect.Show answer
Answer: Substituting y = 3 gives x = 9, so they meet at (9, 3).
Q6A feasible region has vertices (0, 4), (3, 3) and (5, 0). Find the maximum of P = 2x + 4y.Show answer
Answer: At (0, 4), P = 16; at (3, 3), P = 18; at (5, 0), P = 10. The maximum is 18 at (3, 3).
Q7Why might a fractional vertex not be the final answer in a real problem?Show answer
Answer: If the variables count whole objects, the answer must be a whole number, so the nearest lattice points inside the region must be tested instead.
Exam-style questions
Written in the style of a IGCSE Maths exam paper, with a full mark scheme.
A shop stocks x small boxes and y large boxes. It has room for at most 30 boxes in total, it must stock at least 5 large boxes, and the number of small boxes must be at least twice the number of large boxes. Write down the three inequalities, and find the maximum value of 4x + 7y subject to them.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 7 available
Explain why, when a linear programming problem asks for a maximum profit and the feasible region is unbounded above, the problem may have no maximum. Illustrate your answer with an example.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 3 available
Free printable worksheet
Want more practice on paper? Download the linear programming worksheet pack - 7 pages of exam-style questions with a full mark scheme. One email opens every download in this browser for 14 days - no account, no card. Print it for personal and classroom use.
Next topics
Not quite what you needed?
Tell us what is missing on linear programming, or which topic to write up next. Every request is read, and we reply to every one.
Build a full practice pack.
This topic is one of hundreds in the library - pick the ones a student needs and generate a printable PDF in minutes.