Half-planes and the best corner
Tonight's idea
The line \(y = 2x - 1\) cuts the plane in two. The points with \(y > 2x - 1\) fill one side, a half-plane. Which side? Test a point off the line: at \((0, 0)\), \(0 > -1\) is true, so shade the origin's side. Dash the line for a strict inequality (its points are not included), solid for \(\le\) or \(\ge\).
Several inequalities shade their overlap, the feasible region: the points obeying every constraint, usually a polygon. Now suppose you want \(3x + 2y\) as large as possible inside that region. The points with \(3x + 2y = P\) form a line, and different \(P\) give parallel lines. Raise \(P\) and the line slides across the region; at the last moment it still touches, it rests on a corner (or, if parallel to an edge, on a whole edge). So:
A linear expression's largest and smallest values over a polygon region are at corners. Check the corners and you are done.
Watch one: brownies and cookies
A tray of brownies uses 1 kg of flour and 3 hours; a tray of cookies 2 kg and 1 hour. With 10 kg and 15 hours, make \(x\) trays of brownies and \(y\) of cookies: \(x + 2y \le 10\), \(3x + y \le 15\), \(x \ge 0\), \(y \ge 0\). Brownies earn 3, cookies 2. Maximise \(P = 3x + 2y\).
The corner \((4, 3)\) is where the two lines cross (solve them as a pair). Check the corners: \(P(0,0) = 0\), \(P(5,0) = 15\), \(P(4,3) = 18\), \(P(0,5) = 10\). Best: 4 trays of brownies and 3 of cookies, earning 18.
Your turn
- Shade the region given by \(x + y \le 4\), \(x \ge 1\), \(y \ge 0\). Give its three corners and its area.
- Which of the points \((1, 3)\), \((2, 3)\), \((0, 4)\), \((3, 1)\) satisfy both \(y > 2x - 1\) and \(x + y \lt 5\)? For each rejected point, say which inequality fails.
- Use the brownies-and-cookies region. (a) Cookies now earn 5: find the best corner for \(P = 2x + 5y\). (b) Now \(P = x + 2y\). Check all four corners. What is odd about the answer, and why does it happen?
- A club sells bracelets (\(x\)) and keychains (\(y\)). A bracelet takes 20 minutes and 1 dollar of materials, a keychain 10 minutes and 2 dollars. There are 240 minutes and 30 dollars. Bracelets earn 3, keychains 2. Write the constraints, find the corners, and find the best plan.
Stretch: cheapest, not biggest
A diet needs \(x + y \ge 4\) and \(2x + y \ge 6\), with \(x, y \ge 0\). Food \(x\) costs 4 per unit and \(y\) costs 3. Sketch the region. It is unbounded, with no top edge. Why does a minimum still exist? Find the cheapest diet.
Answers
- A triangle with corners \((1, 0)\), \((4, 0)\) and \((1, 3)\): base 3, height 3, area \(\tfrac92 = 4.5\).
- \((1, 3)\): \(3 > 1\) and \(4 \lt 5\), yes. \((2, 3)\): \(3 > 3\) is false (the point is on the dashed line), and \(5 \lt 5\) fails too, so it is out. \((0, 4)\): \(4 > -1\) and \(4 \lt 5\), yes. \((3, 1)\): \(1 > 5\) is false. Two of the four.
- (a) \(P = 0, 10, 23, 25\) at \((0,0), (5,0), (4,3), (0,5)\): best is \((0, 5)\), all cookies, earning 25. (b) \(P = 0, 5, 10, 10\). Two corners tie at 10, and so does every point on the edge between them. The level lines \(x + 2y = P\) are parallel to the constraint line \(x + 2y = 10\), so the top level line lies along that whole edge.
- \(20x + 10y \le 240\), that is \(2x + y \le 24\); \(x + 2y \le 30\); \(x, y \ge 0\). Corners \((0,0)\), \((12,0)\), \((6,12)\) (solving the pair: \(y = 24 - 2x\), so \(x + 48 - 4x = 30\), \(x = 6\)) and \((0,15)\). \(P = 3x + 2y\) gives \(0, 36, 42, 30\). Best: 6 bracelets and 12 keychains, earning 42.
Stretch. Corners: \((0, 6)\), \((4, 0)\), and \((2, 2)\) where \(x + y = 4\) meets \(2x + y = 6\). Cost \(C = 4x + 3y\) is 18, 16 and 14, so the cheapest diet is 2 of each, costing 14. Moving out into the unbounded part only adds food and cost, so the missing top edge cannot hide a cheaper point. A maximum, by contrast, would not exist.