D1.5 Linear programming
⤓ Presentation⤓ PowerPointPresentation: opens offline in any browser, simulations live. PowerPoint: editable.
Decision Mathematics 1 (AS), specification sections 5.1–5.3: formulating problems and solving them graphically, including integer solutions. The simplex algorithm is not part of this unit.
What this page covers
7 points
- Decision variables, constraints (including non-negativity) and the objective function
- Formulating a problem from context, including “at least”, “at most”, ratio and percentage conditions
- Drawing constraint lines and identifying the feasible region
- The objective line (ruler) method for maximising and minimising
- The vertex method: testing every corner of the feasible region
- Unbounded regions and problems with more than one optimal solution
- Integer solutions when the optimal vertex does not have integer coordinates
In one minute
6 points
- Linear programming finds the values of two decision variables that make a linear objective as large or as small as possible, subject to linear inequality constraints, by drawing the feasible region and finding its best corner.
- Decision variables: say exactly what \(x\) and \(y\) count, with the time period (“the number of vases made each week”).
- Constraints: one linear inequality per restriction, plus \(x \ge 0\), \(y \ge 0\). Simplify by dividing through by common factors.
- Feasible region: draw each boundary line from two points, decide the side with a test point, and label the region R that satisfies every constraint.
- Optimum: slide an objective line parallel to itself (the last point of R it touches), or evaluate the objective at every vertex.
- Integers: if the best vertex is not a whole-number point, test the integer points near it against every constraint and pick the best one.
Contents
13 sections
- What is a linear programming problem?
- How do you formulate a problem from a description?
- How do you draw the feasible region?
- How does the objective line (ruler) method work?
- How does the vertex method work, and how do you minimise?
- What if the answer must be a whole number?
- How do the pieces fit together in a full question?
- Exam tips for D1.5
- Common misconceptions
- How this topic connects
- Key formulae
- Check your understanding
- Specification checklist
What is a linear programming problem?
A business has limited clay, limited machine hours or a limited budget, and wants the plan that makes the most profit or costs the least. When every restriction and the goal can be written as linear expressions in two unknowns, the problem can be solved on a graph. That is linear programming.
- Decision variables (\(x\), \(y\)): the quantities you choose, such as how many of each product, how many hours or how many vehicles.
- Constraints: linear inequalities such as \(3x + 2y \le 60\) that come from limited resources, minimum requirements or ratios.
- Non-negativity constraints: \(x \ge 0\) and \(y \ge 0\). You cannot make a negative number of anything, so always include them.
- Objective function: the quantity to optimise, for example profit \(P = 15x + 12y\) (maximise) or cost \(C = 400x + 250y\) (minimise).
A feasible solution satisfies every constraint; the feasible region is the set of all feasible solutions; an optimal solution is a feasible solution with the best value of the objective. Because every boundary is a straight line, the feasible region is a convex polygon (or an unbounded convex region), and its corners are called vertices.
The standard layout of a formulation
\[\text{Maximise (or minimise) } P = ax + by \quad \text{subject to constraints},\ x \ge 0,\ y \ge 0\]\(a, b\) = profit (or cost) per unit of each variable; each constraint is “(amount used per unit) × variable … ≤ (amount available)”. Not in the formulae list: learn the layout.
How do you formulate a problem from a description?
Formulating is where most of the thinking happens. Work through the text in a fixed order:
- Define the variables in words, with units and the time period.
- Go through the text sentence by sentence; every limit, requirement or comparison becomes one inequality.
- Write the objective and say whether it is maximised or minimised.
- Add \(x \ge 0\), \(y \ge 0\) and simplify each constraint (divide by common factors, clear fractions).
The table translates the phrases that come up most often. Ratio and percentage conditions are the ones to slow down on: write them first exactly as the words say, then rearrange.
| Words | Inequality |
|---|---|
| at least 20 tablets | \(y \ge 20\) |
| no more than 16 deluxe benches | \(y \le 16\) |
| at least 60 devices in total | \(x + y \ge 60\) |
| the number of standard benches is at most three times the number of deluxe benches | \(x \le 3y\) |
| at least a quarter of the devices are laptops | \(x \ge \tfrac14(x + y)\), i.e. \(y \le 3x\) |
| at least 2 rolls for every 3 loaves | \(\dfrac{y}{x} \ge \dfrac23\), i.e. \(3y \ge 2x\) |
A pottery makes vases and bowls. Each vase uses 3 kg of clay and 1 hour of glazing; each bowl uses 2 kg of clay and 2 hours of glazing. Each week 60 kg of clay and 32 hours of glazing time are available. At least 3 bowls must be made each week. The profit is £15 on a vase and £12 on a bowl. Formulate this as a linear programming problem, stating your decision variables clearly.
Variables. Let \(x\) = the number of vases and \(y\) = the number of bowls made each week.
Constraints, one sentence at a time: clay \(3x + 2y \le 60\); glazing \(x + 2y \le 32\); bowls \(y \ge 3\); \(x \ge 0\).
Objective. Maximise \(P = 15x + 12y\) subject to \(3x + 2y \le 60,\ x + 2y \le 32,\ y \ge 3,\ x \ge 0\).
\(y \ge 0\) is already implied by \(y \ge 3\), so it does not need to be written separately (writing it is not wrong).
A school buys laptops at £400 each and tablets at £250 each. It needs at least 60 devices, at least 20 of which are tablets, and at least a quarter of all the devices must be laptops. The school wants to keep the cost as low as possible. Formulate this as a linear programming problem, simplifying each constraint.
Variables. \(x\) = number of laptops, \(y\) = number of tablets bought.
Constraints. \(x + y \ge 60\); \(y \ge 20\); \(x \ge \tfrac14(x + y) \Rightarrow 4x \ge x + y \Rightarrow y \le 3x\); \(x \ge 0\).
Minimise \(C = 400x + 250y\) subject to \(x + y \ge 60,\ y \ge 20,\ y \le 3x,\ x \ge 0\).
Reversing a ratio. “At most three times as many standard as deluxe” means \(x \le 3y\), not \(3x \le y\). Test it with numbers: 30 standard and 10 deluxe should be allowed, and \(30 \le 3 \times 10\) ✓.
How do you draw the feasible region?
- For each constraint draw the boundary line (replace the inequality sign by =), using two easy points, usually the intercepts.
- Decide which side is allowed with a test point not on the line. O is easiest unless the line passes through it; then try (1, 0) or (0, 1).
- Lines of the form \(y = mx\), from ratio constraints, pass through the origin: plot a second point such as \((10, 10m)\).
- The feasible region R is where every constraint holds. Either shade the parts you do not want, leaving R clear, or shade R itself. Say which you have done, and label R.
- Find each vertex by solving the equations of the two lines that cross there; do not rely on reading a graph if exact values are needed.
Continue worked example 1. Draw the feasible region R and find the coordinates of its vertices.
Boundary lines from their intercepts: \(3x + 2y = 60\) through (20, 0) and (0, 30); \(x + 2y = 32\) through (32, 0) and (0, 16); \(y = 3\).
Sides. O satisfies the two ≤ constraints; R is above \(y = 3\) and to the right of the \(y\)-axis.
The vertex where clay and glazing both run out: \((3x + 2y) - (x + 2y) = 60 - 32 \Rightarrow 2x = 28 \Rightarrow x = 14,\ y = 9\).
The other vertices: \(3x + 2(3) = 60 \Rightarrow (18, 3)\); and (0, 16), (0, 3). Vertices (0, 3), (18, 3), (14, 9), (0, 16).
How does the objective line (ruler) method work?
For a fixed value of \(P\), the equation \(ax + by = P\) is a straight line. Changing \(P\) moves the line but does not change its gradient, \(-\tfrac{a}{b}\). So the objective lines form a family of parallel lines, and larger values of \(P\) (with \(a, b \gt 0\)) lie further from O.
- Draw one objective line accurately (pick a convenient value of \(P\), such as a multiple of \(a\) and \(b\)) and place a ruler along it.
- To maximise, slide the ruler parallel to itself away from O; the last point of R it touches is optimal.
- To minimise, slide it towards O; the last point of R it touches is optimal.
- The optimal point is at a vertex. Find it exactly by solving the two boundary equations that meet there.
- If the objective line is parallel to an edge of R that it finishes on, every point on that edge is optimal.
Which vertex is optimal?
For \(P = ax + by\), the vertex is optimal when the gradient of the objective line, \(-\tfrac{a}{b}\), lies between the gradients of the two edges that meet at that vertex. Not in the formulae list: derive it from the gradient of \(ax + by = c\).
Continue worked example 3. Use the objective line method to find the number of vases and bowls the pottery should make to maximise its weekly profit, and state the maximum profit.
Gradient of the objective line: \(15x + 12y = c\) has gradient \(-\tfrac{15}{12} = -\tfrac54\).
Compare with the edges: clay \(-\tfrac32\), glazing \(-\tfrac12\). Since \(-\tfrac32 \lt -\tfrac54 \lt -\tfrac12\), the last point touched is where clay and glazing meet.
14 vases and 9 bowls per week; \(P = 15(14) + 12(9) = 318\), a profit of £318.
At this point all the clay (\(3 \times 14 + 2 \times 9 = 60\) kg) and all the glazing time (\(14 + 2 \times 9 = 32\) h) are used.
Draw the objective line clearly and label it, for example “\(15x + 12y = 120\)”, so that the method can be seen on your graph. An optimal point with no visible objective line or vertex testing is just a claim.
How does the vertex method work, and how do you minimise?
The vertex method avoids drawing an objective line: find the exact coordinates of every vertex of R, evaluate the objective at each, and choose the largest (maximising) or smallest (minimising). It works because a linear objective on a convex region always takes its best value at a vertex. Set the work out as a table (vertex, value of the objective), then state the answer in context.
Minimising problems often have an unbounded region, because constraints like \(x + y \ge 60\) do not cap anything. A minimum can still exist, but there is no maximum. Checking only the listed vertices is enough, because the objective increases as you move away into R.
Continue worked example 2. Find the vertices of the feasible region and hence the number of laptops and tablets that minimises the cost. State the minimum cost.
Vertices. \(x + y = 60\) and \(y = 3x\): \(4x = 60 \Rightarrow (15, 45)\). \(x + y = 60\) and \(y = 20 \Rightarrow (40, 20)\).
| Vertex | \(C = 400x + 250y\) |
|---|---|
| (15, 45) | 6000 + 11 250 = 17 250 |
| (40, 20) | 16 000 + 5000 = 21 000 |
15 laptops and 45 tablets, minimum cost £17 250.
The region is unbounded, but moving further into it only raises the cost (for example (100, 20) costs £45 000), so the minimum is at a vertex.
For a minimising problem, sliding the objective line away from O, or quoting a “maximum” for an unbounded region. Ask which way the objective gets better, then slide that way.
What if the answer must be a whole number?
When the variables count objects (vases, buses, batches) the solution must be an integer point of R. If the optimal vertex is not an integer point, the best integer solution is usually near it, but not always the point you get by rounding.
- List the integer points close to the vertex, check each one against every constraint and evaluate the objective at the feasible ones.
- Alternatively, slide the objective line back from the vertex until it meets the first integer point in R.
- Rounding both coordinates down keeps you feasible for ≤ constraints but is often not optimal; rounding up can break a constraint.
A caterer prepares \(x\) batches of hot meals and \(y\) batches of cold meals each day, where \(5x + 3y \le 45\) (kitchen hours), \(2x + 5y \le 40\) (fridge space) and \(x, y \ge 0\). The profit is £40 per batch of hot meals and £30 per batch of cold meals. Only whole batches can be made. Find the number of batches of each type that maximises the profit.
Optimal vertex. The objective gradient \(-\tfrac43\) lies between \(-\tfrac53\) and \(-\tfrac25\), so the optimum is where the two constraints meet: \(25x + 15y = 225\) and \(6x + 15y = 120 \Rightarrow 19x = 105 \Rightarrow V\left(\tfrac{105}{19}, \tfrac{110}{19}\right) \approx (5.53, 5.79)\), \(P \approx 394.7\).
Test integer points near V against both constraints:
| Point | \(5x + 3y \le 45\)? | \(2x + 5y \le 40\)? | \(P = 40x + 30y\) |
|---|---|---|---|
| (5, 5) | 40 ✓ | 35 ✓ | 350 |
| (5, 6) | 43 ✓ | 40 ✓ | 380 |
| (6, 5) | 45 ✓ | 37 ✓ | 390 |
| (6, 6) | 48 ✗ | 42 ✗ | not feasible |
| (7, 3) | 44 ✓ | 29 ✓ | 370 |
6 batches of hot and 5 batches of cold meals, profit £390.
Why nothing beats 390: \(P = 10(4x + 3y)\) and the largest value of \(4x + 3y\) in R is \(\tfrac{750}{19} \approx 39.5\). For integers \(4x + 3y\) is a whole number, so it is at most 39, giving \(P \le 390\). Rounding V down to (5, 5) gives only £350.
How do the pieces fit together in a full question?
A long question usually runs: formulate → draw and label R → find the optimum with an objective line or the vertices → interpret. It sometimes asks how far a profit could change before the optimal plan changes; that is the gradient comparison from the ruler-method section, run backwards.
A workshop makes standard and deluxe garden benches. A standard bench needs 2 hours of cutting and 4 hours of finishing; a deluxe bench needs 3 hours of cutting and 3 hours of finishing. Each week there are 60 hours of cutting and 90 hours of finishing available. Only 16 sets of deluxe fittings arrive each week, and the number of standard benches made must not be more than three times the number of deluxe benches. The profit is £30 on a standard bench and £40 on a deluxe bench.
(a) Formulate this as a linear programming problem. (b) Draw the constraints and label the feasible region R. (c) Use the objective line method to find the optimal number of each bench, and the maximum weekly profit. (d) The profit on a deluxe bench changes to £\(k\), the profit on a standard bench staying at £30. Find the range of values of \(k\) for which your answer to (c) remains optimal.
(a) \(x\) = number of standard and \(y\) = number of deluxe benches made each week. Maximise \(P = 30x + 40y\) subject to \(2x + 3y \le 60,\ 4x + 3y \le 90,\ y \le 16,\ x \le 3y,\ x, y \ge 0\).
(b) Lines through (30, 0) and (0, 20); (22.5, 0) and (0, 30); \(y = 16\); \(x = 3y\) through O and (18, 6). R has vertices (0, 0), (18, 6), (15, 10), (6, 16), (0, 16).
(c) Objective gradient \(-\tfrac{30}{40} = -\tfrac34\), between \(-\tfrac43\) (finishing) and \(-\tfrac23\) (cutting). \((4x + 3y) - (2x + 3y) = 90 - 60 \Rightarrow 2x = 30 \Rightarrow x = 15,\ y = 10\). 15 standard and 10 deluxe benches, \(P = 450 + 400 = 850\), i.e. £850.
Check by the vertex method: \(P = 0, 780, 850, 820, 640\) at the five vertices, and 850 is the largest ✓.
(d) (15, 10) stays optimal while the gradient \(-\tfrac{30}{k}\) lies between \(-\tfrac43\) and \(-\tfrac23\): \(\tfrac23 \le \tfrac{30}{k} \le \tfrac43 \Rightarrow\) \(22.5 \le k \le 45\).
At \(k = 45\) or \(k = 22.5\) the objective line lies along an edge, so (15, 10) is still optimal but no longer the only optimum.
Exam tips for D1.5
“Let \(x\) = vases” is too vague. Write “let \(x\) be the number of vases made each week”. The definition decides whether the constraints and the objective make sense.
Divide each constraint by any common factor: \(400x + 250y \le 20\,000\) becomes \(8x + 5y \le 400\). Smaller numbers make intercepts, sketches and simultaneous equations quicker and safer.
Use a ruler, extend lines across the whole grid, label each line with its equation and label the feasible region R. A small error in a line can move the optimal vertex.
Read the graph to see which two lines meet at the optimum, then solve their equations simultaneously: exact coordinates such as \(\left(\tfrac{105}{19}, \tfrac{110}{19}\right)\) cannot be read from a grid. Finish with a sentence in context, and if whole numbers are needed give the integer solution, not the vertex.
Common misconceptions
| Misconception | Why it is wrong | Correct idea |
|---|---|---|
| The non-negativity constraints are obvious, so leave them out. | They are part of the model, and they bound the region. | Always state \(x \ge 0\), \(y \ge 0\) (unless implied by a stronger constraint such as \(y \ge 3\)). |
| “\(x\) is at most three times \(y\)” means \(3x \le y\). | The multiplier belongs with the smaller quantity. | \(x \le 3y\); test with numbers, e.g. \(x = 30\), \(y = 10\) should satisfy it. |
| The optimal point can be inside R. | A linear objective always improves by moving towards an edge. | The optimum is at a vertex (or along a whole edge). |
| Round the optimal vertex to the nearest integers. | Rounding can leave R or miss a better point. | Test nearby integer points against every constraint and compare objective values. |
| For a minimum, slide the objective line away from O. | Moving away from O increases \(ax + by\) when \(a, b \gt 0\). | Minimise: slide towards O; maximise: slide away from O. |
| An unbounded region has no optimal solution. | It has no maximum for a positive objective, but it can have a minimum. | Check which way the objective improves before deciding. |
How this topic connects
P1 Straight-line graphs and inequalities
Every constraint boundary is a straight line; intercepts, gradients (\(-a \div b\)) and simultaneous equations are the tools for drawing R and finding its vertices. Shading the region that satisfies a linear inequality is the same skill as in P1.
D1.4 Critical path analysis and other D1 topics
Like critical path analysis and minimum spanning trees, linear programming is about finding the best plan under restrictions; here the restrictions are inequalities and the plan is a point on a graph.
Beyond this unit
Real problems with many variables are solved with the simplex algorithm and computer solvers; the two-variable graphical method shows why the optimum always lies at a corner.
Key formulae
| Formula | Use | In the formulae list? |
|---|---|---|
| maximise/minimise \(P = ax + by\), subject to constraints, \(x \ge 0\), \(y \ge 0\) | Layout of a formulation | No — learn it |
| gradient of \(ax + by = c\) is \(-\tfrac{a}{b}\) | Objective lines and boundary lines | No — derive it |
| intercepts of \(ax + by = c\): \(\left(\tfrac{c}{a}, 0\right)\) and \(\left(0, \tfrac{c}{b}\right)\) | Drawing a constraint line | No — derive it |
| “at least \(p\)% are \(x\)”: \(x \ge \tfrac{p}{100}(x + y)\) | Percentage constraints | No — learn it |
| “at least \(m\) of \(y\) for every \(n\) of \(x\)”: \(ny \ge mx\) | Ratio constraints | No — learn it |
| vertex stays optimal while \(-\tfrac{a}{b}\) lies between the gradients of the two edges meeting there | Sensitivity of the optimum to the objective | No — derive it |
Check your understanding
1. \(x\) red tiles and \(y\) blue tiles are used. The number of red tiles must be at most twice the number of blue tiles. Write this as an inequality.
\(x \le 2y\). Check: 20 red and 10 blue is allowed, \(20 \le 20\) ✓.
2. Why is the optimal value of a linear objective always found at a vertex of the feasible region?
The objective lines are parallel. Sliding one across R in the improving direction, the last contact with a convex polygon is at a corner, or along a whole edge if the line is parallel to that edge, which still includes the corners at each end.
3. In worked example 7 the profit becomes \(P = 6x + 9y\). What happens to the optimal solution?
\(6x + 9y = 3(2x + 3y)\) is parallel to the cutting line, so every point on the edge from (6, 16) to (15, 10) gives the maximum \(P = 180\). The integer points on that edge are (6, 16), (9, 14), (12, 12) and (15, 10).
4. A feasible region has vertices (0, 0), (10, 0), (4, 8) and (0, 6), as in the first figure. Find the maximum of \(P = 3x + y\).
\(P = 0, 30, 20, 6\) at the four vertices, so the maximum is 30 at (10, 0).
5. The feasible region for a problem is unbounded. Can you always find a minimum? A maximum?
For an objective with positive coefficients and the region away from O, there is no maximum (it increases without limit), but a minimum exists at a vertex. Check the direction in which the objective improves.
6. In worked example 1, the profit on a bowl rises to £20 while a vase stays at £15. Does (14, 9) remain optimal?
The objective gradient is now \(-\tfrac{15}{20} = -\tfrac34\), which is still between \(-\tfrac32\) (clay) and \(-\tfrac12\) (glazing), so yes: (14, 9) remains optimal, with \(P = 15(14) + 20(9) = 390\), i.e. £390.
Specification checklist
- (D1 5.1) Define decision variables precisely and write an objective function to be maximised or minimised.
- (D1 5.1) Turn limits, requirements, ratios and percentages in a description into simplified linear inequalities, including non-negativity.
- (D1 5.2) Draw constraint lines accurately, decide the allowed side with a test point and label the feasible region.
- (D1 5.2) Use an objective line, moving it in the correct direction, to locate the optimal vertex for a maximum or a minimum.
- (D1 5.2) Find the exact coordinates of vertices and use the vertex method to find the optimal value.
- (D1 5.2) Recognise unbounded regions and objectives parallel to an edge, and find when a vertex remains optimal as an objective coefficient changes.
- (D1 5.3) Find the optimal integer solution by testing integer points near a non-integer vertex against every constraint.