Additional Mathematics notes, chapter 7
Linear Programming
Textbook Additional Mathematics Form 5 (DLP), pages 232–249
What this chapter covers
- Represent a situation as a linear programming model, by identifying the decision variables, the objective function and the constraints (7.1)
- Draw and shade the graph of a linear inequality in two variables, using a solid or a dashed line (7.1)
- Optimise an objective function k = ax + by by moving a parallel line across the feasible region, or by testing the vertices (7.1)
- Solve linear programming problems graphically in business, production and planning situations (7.2)
7.1Linear programming model
Linear programming shares out limited resources (money, workers, materials, time) in the best possible way, so that a cost is as small as possible or a profit is as large as possible.
A situation is turned into a linear programming model in three steps.
| Step | What to do | Example: a baker makes x cakes and y pies |
|---|---|---|
| 1. Decision variables | Choose x and y for the quantities to be decided | x = number of cakes, y = number of pies |
| 2. Objective function | Write the expression to be maximised or minimised, k = ax + by | Profit k = 5x + 3y |
| 3. Constraints | Write each limit as a linear inequality (or equation) in x and y | x + y ≤ 40 (at most 40 items) |
Turning words into symbols
| Words | Symbol | Line on the graph |
|---|---|---|
| at least, not less than, minimum of | ≥ | solid |
| at most, not more than, not exceed, maximum of | ≤ | solid |
| more than, exceeds, less than (strictly) | > or < | dashed |
Example (textbook p. 235): forming constraints
A hawker sells x kg of spinach at RM3.50 per kg and y kg of mustard leaves at RM4.50 per kg. The total sales are at least RM350 a day.Sales are 3.50x + 4.50y, and "at least" means ≥, so 3.50x + 4.50y ≥ 350.
Constraints are written only in terms of the decision variables. Also remember the hidden constraints x ≥ 0 and y ≥ 0, because you cannot make a negative number of items.
Graphing a linear inequality
Draw the line ax + by = c first. Then choose the side to shade.
- If b > 0, the region above the line satisfies ax + by > c (or ≥) and the region below satisfies ax + by < c (or ≤).
- For a vertical line x = c, the right side is x > c and the left side is x < c.
- If b < 0, the sides swap. The safest method is to test a point, such as (0, 0), in the inequality.
Shading "above the line" just because the sign is ">". When b is negative the inequality flips. Test a point, or divide by b and reverse the symbol first. Also check solid or dashed.
The objective function and its optimum
The feasible region R is the region where all the constraints are true together. The optimum (maximum or minimum) value of k = ax + by is found at a vertex of R.
Two ways to find it:
- Draw the line k = ax + by for an easy value of k, then slide it parallel to itself across R. The last vertex it touches gives the maximum (or the first, the minimum).
- Read the coordinates of each vertex of R and put them into k = ax + by. Pick the largest or smallest value.
Choose k as a common multiple of a and b so the line has whole-number intercepts. For k = 4x + 8y, take k = 32: x-intercept 8 and y-intercept 4.
Example 4 (textbook p. 237): testing vertices
The vertices of a region are (15, 55), (47, 23) and (15, 8). Find the greatest and least value of k = x + 2y.(15, 55): k = 15 + 110 = 125
(47, 23): k = 47 + 46 = 93
(15, 8): k = 15 + 16 = 31
The maximum value is 125 and the minimum value is 31.
(a) Write "the number of vans y is at most three times the number of lorries x" as an inequality. (b) Is the line for 2x + y > 8 solid or dashed? (c) Which vertex of (1, 2), (4, 1), (3, 5) gives the largest value of 2x + 3y?
Show answerHide answer
(a) y ≤ 3x
(b) Dashed, because the symbol is strict (>)
(c) 2x + 3y gives 8, 11 and 21, so (3, 5)
(b) Dashed, because the symbol is strict (>)
(c) 2x + 3y gives 8, 11 and 21, so (3, 5)
7.2Applications of linear programming
To solve a problem, follow these steps.
- Read the problem and choose the variables x and y.
- Write the constraints as linear inequalities (a table of the data helps).
- Draw the lines and shade to find the feasible region R.
- Write the objective function and find its optimum at a vertex of R.
Example 6 (textbook p. 242): buying tables
A school buys x tables P (RM200 each, 1 m² each) and y tables Q (RM100 each, 2 m² each). The conditions are:I The total area is at least 30 m². II The money spent is at most RM6 000. III Tables Q are at most twice tables P.
| Table P | Table Q | |
|---|---|---|
| Price | RM200 | RM100 |
| Area | 1 m² | 2 m² |
I: x + 2y ≥ 30
II: 200x + 100y ≤ 6 000, which simplifies to 2x + y ≤ 60
III: y ≤ 2x
Most pupils. Table P seats 4 pupils and table Q seats 8, so k = 4x + 8y. Test the vertices:
| Vertex | k = 4x + 8y |
|---|---|
| (6, 12) | 24 + 96 = 120 |
| (15, 30) | 60 + 240 = 300 |
| (30, 0) | 120 + 0 = 120 |
Find a vertex by solving the two equations that meet there. Here 2x + y = 60 and y = 2x give 4x = 60, so x = 15 and y = 30.
Putting a point on a dashed line into the answer. Points on a dashed line are not in the region. With solid lines, the points on the line are allowed. Also check that a point makes sense: you cannot buy 2.5 tables, so the answer must be whole numbers.
A shop sells x pens (RM2 profit each) and y books (RM5 profit each). The feasible region has vertices (0, 10), (20, 0) and (10, 20). Find the maximum profit and where it happens.
Show answerHide answer
k = 2x + 5y: (0, 10) gives 50, (20, 0) gives 40, (10, 20) gives 120.
The maximum profit is RM120 at (10, 20).
The maximum profit is RM120 at (10, 20).
Summary
| Remember | Key fact |
|---|---|
| Model | Variables x and y, objective function k = ax + by, constraints as inequalities |
| Line type | ≤ and ≥ solid; < and > dashed |
| Shading | Test (0, 0) when the line does not pass through it |
| Feasible region R | Where every constraint holds at once |
| Optimum | At a vertex of R: test every vertex in k, or slide a parallel line |
| Vertex | Solve the two line equations simultaneously |