Year 10 Extended · Unit 2 Generalizing, coordinate geometry and linear programming · Lesson 6 of 6

Where in the allowed region is the best choice?

A decision with limits becomes a set of inequalities, and the quantity to make largest becomes a line that slides across the allowed region. This lesson asks where in the region the best choice can be, and why.

Number and AlgebraGDC optional

Warm-up

Three quick ones from earlier work. Try each in your head or on paper before you open the answer.

  1. From Year 9: solve x + y = 9 and 2x + y = 14.
    Answerx = 5 and y = 4. Subtract the first equation from the second.
  2. From lesson 5: is the point (3, 3) in the region x + y ≤ 6 and y ≥ 1?
    AnswerYes: 3 + 3 = 6 is allowed by ≤, and 3 ≥ 1.
  3. From Year 8: write “at most 18 boxes” as an inequality in b.
    Answerb ≤ 18.
Words used in this lesson
constraint
a limit written as an inequality. For example: x + y ≤ 30.
feasible region
all the points that satisfy every constraint. For example: the shaded polygon.
objective function
the quantity to be made largest or smallest. For example: profit = 8x + 5y.
vertex
a corner of the region, where two boundary lines meet. For example: where x = 2 meets y = 3.
optimum
the best value of the objective. For example: the largest profit.
maximize
make as large as possible. For example: the most money.

The best of what is allowed

A tailor's workshop in Kigali makes x large tote bags and y small embroidered purses each week. A tote uses 2 metres of cloth and a purse 1 metre, and there are 14 metres a week, so 2x + y ≤ 14. The workshop can finish at most 9 items a week, so x + y ≤ 9. A tote earns 3 thousand francs and a purse 2 thousand, so the takings are P = 3x + 2y thousand francs, and the tailor wants them as large as possible.

Predict first: the allowed pairs (x, y) fill a region. Where in the region do you expect the best choice to be: in the middle, along an edge, or at a corner? Write your guess and a reason. Then use the figure and slide the line to find out.

3
2
12
yesdoes the line meet the region
12value of P on the line

P = 3x + 2y at 12: the line 3x + 2y = 12 crosses the allowed region. Raise P and watch where the line last touches it.

Show me the steps
  1. P = 3x + 2y with the line at 12: it crosses the region. Raising P slides the line away from the origin.
  2. At 23 the line touches the region only at the corner (5, 4), and at 24 it has left. The corner values are 0, 21, 23 and 18, so the largest is 23.
  3. P = 2x + y: the line is parallel to the edge 2x + y = 14, so it leaves along the whole edge from (7, 0) to (5, 4). Both corners give 14.
  4. P = x + 5y: the line is steep, and the last corner it touches is (0, 9), where P = 45.

Four parts make a linear programming problem. The variables (x and y). The constraints, a system of linear inequalities, which together make the feasible region. The objective function, such as P = px + qy, which is to be made as large (or small) as possible. And a decision, said in the words of the problem.

Lines px + qy = P are parallel, and sliding them across the region, the last point touched is a vertex (or a whole edge when the line is parallel to it). So find every vertex, work out P at each, and choose the best. Then check that the vertex really is inside the region and answer in context, with units.

Two common mistakes. Using a corner that is not in the feasible region: two boundary lines meet somewhere, but if that point breaks another constraint it is not a vertex of the region. And testing only the corners that look promising: the best corner is not always the one farthest from the origin.

Worked examples

1. A bakery in Marrakesh bakes x trays of bread and y trays of pastries. The oven allows 3x + 2y ≤ 24 and there are at most 10 trays, x + y ≤ 10. A tray of bread earns 40 and a tray of pastries 30. Maximize P = 40x + 30y.

  1. The corners are (0, 0), (8, 0) and (0, 10), and where 3x + 2y = 24 meets x + y = 10: subtracting twice the second from the first gives x = 4, then y = 6, so (4, 6).
  2. P at the corners: 0, 320, 300 and 40 × 4 + 30 × 6 = 340. The best is 340 at (4, 6): 4 trays of bread and 6 of pastries.

2. Minimize C = 3x + 4y with x + y ≥ 6, x ≥ 1 and y ≥ 1.

  1. The corners are where x = 1 meets x + y = 6, which is (1, 5), and where y = 1 meets it, (5, 1). The corner (1, 1) fails x + y ≥ 6.
  2. C = 3 + 20 = 23 at (1, 5), and C = 15 + 4 = 19 at (5, 1). The minimum is 19 at (5, 1).

3. Maximize P = 3x + 6y on x ≥ 0, y ≥ 0, x + 2y ≤ 12 and x ≤ 8.

  1. The corners are (0, 0), (8, 0), (8, 2) and (0, 6). P = 0, 24, 36 and 36.
  2. Two corners tie, because P = 3(x + 2y) is parallel to the edge x + 2y = 12. The maximum is 36 at every point on that edge.

Your go. The first step is given. A stall sells x scarves and y hats with x + y ≤ 10, x + 3y ≤ 18, x ≥ 0 and y ≥ 0, and a profit of 6 on a scarf and 5 on a hat. The corners are (0, 0), (10, 0), (6, 4) and (0, 6). Maximize P = 6x + 5y.

  1. At (0, 0), P = 0. At (10, 0), P = 60.
  2. Now work out P at (6, 4) and (0, 6), then choose the best and say the decision in words.
Check the answer

At (6, 4), P = 36 + 20 = 56. At (0, 6), P = 30. The largest is 60 at (10, 0): sell 10 scarves and no hats. The corner (6, 4) looks like a balance but earns less.

With a GDC (optional)

A GDC can graph the boundary lines to check a sketch, and a list can hold the corner values: put the x coordinates in one list, the y coordinates in another, and calculate P in a third. Reading a corner off a graph by tracing is only approximate, so find each corner exactly by solving the two boundary equations.

The GDC speeds up checking; it does not decide the model. Everything on this page can be done by hand.

Check before you go on

1. A feasible region has corners (0, 0), (6, 0), (3, 5) and (0, 4). Which corner gives the largest value of P = 4x + y?

Your turn

Start at Level 1 and go as far as you can. Type negative numbers with a minus sign, for example -7. A wrong answer gets a reason, not just a cross: read it, then try again.

Level 1 · Getting started

2. A feasible region has corners (0, 0), (8, 0), (5, 5) and (0, 6). What is the largest value of P = 2x + 3y on the region?

3. A van carries small boxes (x of them, 3 cubic metres each) and large boxes (y of them, 5 cubic metres each) in a space of 60 cubic metres, so 3x + 5y ≤ 60. The boundary line meets the x-axis (where y = 0) at x = ?

Level 2 · Building

4. Maximize P = 5x + 4y subject to x + 2y ≤ 16, 3x + y ≤ 18, x ≥ 0 and y ≥ 0. What is the largest value of P?

5. Minimize C = 6x + 5y subject to x + y ≥ 8, x ≥ 2 and y ≥ 1. What is the smallest value of C?

Level 3 · Stretch

6. Over the region x + 2y ≤ 16, 3x + y ≤ 18, x ≥ 0, y ≥ 0, the objective P = 6x + ky takes the same value at the corners (6, 0) and (4, 6). What is k?

7. A workshop makes x chairs and y tables, both whole numbers, with 2x + 3y ≤ 14 and 4x + y ≤ 14. What is the largest value of x + y that can be made?

Something to think about

A bakery's best plan is at the corner (4, 6), but the oven is replaced by one that holds 10% more. Without recalculating, will the best corner move, and will the best profit rise by 10%?

One way to think about it

The corner stays where the same two lines meet, but it moves: 3x + 2y = 26.4 and x + y = 10 meet at (6.4, 3.6), where P = 256 + 108 = 364. That is 24 more than 340, about 7%, not 10%, because the tray limit did not grow. The profit rises by 10% only if every limit grows by 10%. (Trays are whole, so a real plan would then test the nearby whole-number points.)

Exit ticket

8. A linear programming problem has a bounded feasible region. Which statement can be false?