Algebra 2 · A.CED.A.3

Linear programming

A shaded region holds every plan that keeps within the limits. Which of those endless plans makes the most money, or costs the least?

You need

The overlap of two shaded regionsAlgebra 1

Where you are 4 in Systems of linear inequalities

Algebra9

Systems of equations7

Systems of linear inequalities4

Graphing a linear inequality in two variables

Linear programming

The overlap of two shaded regions Writing and interpreting constraints

When you reach for it

Writing and interpreting constraints turns the limits in a situation into inequalities, and The overlap of two shaded regions draws them: the feasible region is the set of points that satisfy every constraint at once. That region usually holds infinitely many plans. This lesson answers the next question: which one is best?

“Best” is measured by an amount built from the variables, such as a profit P = 25x + 40y or a cost C = 5x + 10y. When that amount has the form

z = ax + by

with a and b fixed numbers, it is called a linear objective, and the task of making it as large as possible (maximizing) or as small as possible (minimizing) over a region cut out by linear inequalities is linear programming. The word “programming” is old and means planning, not computer code.

The move you reach for is the corner principle: if the objective has a best value on the region, that value is reached at a corner. So instead of searching infinitely many points, you find the few corners and compare.

The procedure

Part 1 (the first day) explains why corners decide everything and uses that on regions closed in on every side. Part 2 (the second day) handles the cases a closed region hides: a minimum on a region that runs off without end, two corners that tie, and an objective with no best value at all.

Part 1: level lines and the corner principle

Name the variables, the constraints and the objective. Say what x and y count, write each limit as an inequality, and write the objective as a formula in x and y, with its units.

Graph the feasible region and find its corners exactly. A corner is a crossing of two boundary lines that also satisfies every other constraint. Find it by solving those two boundary equations as a system, usually by elimination. A crossing that breaks another constraint is outside the region and is not a corner.

Level lines. Fix a value k. The points where ax + by = k form a straight line, called a level line of the objective: every point on it gives the same value k. When b \ne 0, solving for y gives

y = -\frac{a}{b}x + \frac{k}{b}

so every level line has the same slope \displaystyle -\frac{a}{b}, and changing k slides the line without turning it. The level lines are parallel. When b > 0, a bigger k means a higher line.

Why the best point is a corner. Picture the level lines sweeping across the region as k grows. The largest k whose line still meets the region is the maximum. Push the line any further and it leaves the region entirely; at that last moment it can only be touching the region along its edge, and a line touching a polygon from outside touches it at a corner, or along a whole edge whose two ends are corners. The same picture, sweeping the other way, gives the minimum.

The algebra behind the picture is short. Take two points Q_1 and Q_2 and a point Q on the segment between them, written Q = (1 - t)Q_1 + tQ_2 with 0 \le t \le 1. Because the objective is linear, its value there is

z(Q) = (1 - t)\,z(Q_1) + t\,z(Q_2)

a weighted average of the two end values, so it lies between them. Every point of a bounded polygon lies on a segment between two points of its edges, and every edge point lies on a segment between two corners. So no point can beat the best corner, and no point can fall below the worst corner.

Compare the corners. Work out the objective at each corner, in a table. The largest value is the maximum and the smallest is the minimum. Read the answer back into the situation: which plan, and what it gives.

Is the best corner usable? When x and y count whole things and the best corner is a fraction, it is not a plan; the whole-number points near it must be tested against every constraint, as in Writing and interpreting constraints.

Part 2: minimizing, ties and unbounded regions

Minimizing uses the same corners and the same table: take the smallest value. With costs, the constraints are usually floors (at least so many pounds, at least so many seats), and the region then runs off without end.

A region that runs off without end is called unbounded. Its corners are still the only candidates, but now the objective may keep growing (or keep falling) along the open side, and then it has no best value in that direction. Settle it by following the open side: find points of the region that run off along it, and see whether the objective grows or falls along them. If the objective has a best value, it is at a corner; if it does not, no corner table can show it, so the check comes first.

A neat way to prove that a corner value really is best is to build the objective out of the constraints. If every point of the region has 2x + y \ge 10 and x + 3y \ge 15, then 5x + 10y = (2x + y) + 3(x + 3y) \ge 10 + 45 = 55 at every point, so no point costs less than 55. The multipliers (1 and 3 here) must be positive, since multiplying an inequality by a negative number reverses it.

Ties. If two corners give the same best value, the level line for that value runs along the whole edge joining them, and by the averaging formula every point of that edge gives the same value. The answer is then the whole edge, not a single point. This happens exactly when the objective’s level lines are parallel to that edge.

Changing the objective. The region stays put when prices change; only the slope of the level lines moves. As long as the objective still grows toward the same side of the region, a corner stays best while the slope of the level lines lies between the slopes of the two edges that meet at it. Past either end, the neighboring corner takes over, and at the end itself the two tie.

Worked examples

Examples 1 to 3 belong to Part 1, Examples 4 to 7 to Part 2.

Example 1

A bakery’s best weekend

A bakery makes trays of muffins and trays of pies for the weekend market. A tray of muffins takes 1 hour of oven time and 3 pounds of flour; a tray of pies takes 2 hours of oven time and 2 pounds of flour. The oven is free for 20 hours and there are 36 pounds of flour. Each tray of muffins makes a profit of 25 dollars and each tray of pies 40 dollars. How many of each should the bakery make to earn the most?

Solution

Let x be the number of trays of muffins and y the number of trays of pies. The constraints are oven hours, flour, and counts that cannot be negative:

\begin{cases} x + 2y \le 20 \\ 3x + 2y \le 36 \\ x \ge 0, \ y \ge 0 \end{cases}

and the objective, in dollars, is P = 25x + 40y, to be maximized.

The corners. The axes give the origin (0, 0). On the x-axis, flour runs out first: 3x = 36 gives (12, 0), and oven time there is 12 \le 20. (The oven line meets the axis at (20, 0), which needs 60 pounds of flour, so it is outside.) On the y-axis, the oven runs out first: 2y = 20 gives (0, 10), and flour there is 20 \le 36. The two limits meet where both are equations; subtracting the oven equation from the flour equation removes 2y:

\begin{aligned} (3x + 2y) - (x + 2y) &= 36 - 20 \\ 2x &= 16 \end{aligned}

so x = 8, and then 8 + 2y = 20 gives y = 6. The fourth corner is (8, 6).

The level lines. P = 200 is the line 25x + 40y = 200, through (8, 0) and (0, 5). Every level line has slope \displaystyle -\frac{25}{40} = -\frac{5}{8}, and raising P slides it up and to the right (Figure 1).

Figure 1Example 1. Each dashed line joins plans with the same profit. Sliding the line up and to the right raises P; the last line that still meets the region is P = 440, and it meets it only at the corner (8, 6).

Compare the corners.

Corner	P = 25x + 40y
(0, 0)	0
(12, 0)	300
(8, 6)	200 + 240 = 440
(0, 10)	400

The bakery should make 8 trays of muffins and 6 trays of pies, for a profit of 440 dollars. It is a whole-number plan, and it uses every resource: 8 + 12 = 20 oven hours and 24 + 12 = 36 pounds of flour. Making only pies earns just 400 dollars, because each pie tray needs twice the oven time, so the oven caps pies at 10 trays.

Example 2

The same region, a largest and a smallest value

The region is given by y \le x + 3, x + y \le 9, y \ge 1 and x \ge 0. Find the largest and the smallest values of z = 4x - 3y on it.

Solution

Find the corners by pairing the boundary lines and keeping only the crossings that satisfy everything else.

x = 0 with y = 1: A(0, 1). Check: 1 \le 3 and 1 \le 9.

y = 1 with x + y = 9: B(8, 1). Check: 1 \le 11.

y = x + 3 with x + y = 9: substituting, x + x + 3 = 9, so x = 3 and C(3, 6). Check: 6 \ge 1.

x = 0 with y = x + 3: D(0, 3). Check: 3 \le 9 and 3 \ge 1.

The other two crossings fail: y = 1 meets y = x + 3 at (-2, 1), where x < 0, and x = 0 meets x + y = 9 at (0, 9), where 9 \le 3 is false.

Figure 2Example 2. The region with corners A(0, 1), B(8, 1), C(3, 6) and D(0, 3).

Corner	z = 4x - 3y
A(0, 1)	0 - 3 = -3
B(8, 1)	32 - 3 = 29
C(3, 6)	12 - 18 = -6
D(0, 3)	0 - 9 = -9

The region is closed in on every side, so both answers come from the table. The largest value is 29, at B(8, 1), and the smallest is -9, at D(0, 3). The negative coefficient of y makes z larger lower down, so the winner sits on the bottom edge and the loser on the left.

Example 3

How far can the price of a pie move?

In Example 1, keep the muffin profit at 25 dollars a tray but let the profit on a tray of pies be p dollars, with p > 0. For which values of p is 8 trays of muffins and 6 of pies still a best plan?

Solution

The region has not changed, so the corners are still (0, 0), (12, 0), (8, 6) and (0, 10). The profits there are 0, 300, 200 + 6p and 10p. The corner (8, 6) is a best plan when its profit is at least each of the others.

Against (12, 0): 200 + 6p \ge 300 gives 6p \ge 100, so \displaystyle p \ge \frac{50}{3}.

Against (0, 10): 200 + 6p \ge 10p gives 200 \ge 4p, so p \le 50.

Against (0, 0): 200 + 6p > 0 for every positive p.

So (8, 6) is a best plan exactly when \displaystyle \frac{50}{3} \le p \le 50, that is, from about 16.67 to 50 dollars a tray.

The slopes tell the same story. The level lines of 25x + py have slope \displaystyle -\frac{25}{p}. The flour edge has slope \displaystyle -\frac{3}{2} and the oven edge \displaystyle -\frac{1}{2}. The corner (8, 6) wins while \displaystyle -\frac{3}{2} \le -\frac{25}{p} \le -\frac{1}{2}, which gives the same range. At p = 50 the level lines are parallel to the oven edge and (8, 6) ties with (0, 10), both earning 500 dollars; above 50 only pies is best. At \displaystyle p = \frac{50}{3} it ties with (12, 0) at 300 dollars; below that, only muffins is best.

Example 4

The cheapest mix of two fertilizers

A gardener needs at least 10 pounds of nitrogen and at least 15 pounds of phosphate for a lawn. A bag of brand A holds 2 pounds of nitrogen and 1 pound of phosphate and costs 5 dollars. A bag of brand B holds 1 pound of nitrogen and 3 pounds of phosphate and costs 10 dollars. How many bags of each give the cheapest mix? Is there a most expensive one?

Solution

Let x be the number of bags of A and y the number of bags of B. The constraints are 2x + y \ge 10 (nitrogen), x + 3y \ge 15 (phosphate), x \ge 0 and y \ge 0, and the cost in dollars is C = 5x + 10y, to be minimized.

The corners. Both limits are floors, so the region is the part of the first quadrant above both lines, and it runs off without end (Figure 3).

On the y-axis, x = 0: nitrogen needs y \ge 10 and phosphate y \ge 5, so the corner is (0, 10). On the x-axis, nitrogen needs x \ge 5 and phosphate x \ge 15, so the corner is (15, 0). The two limits cross where y = 10 - 2x and x + 3(10 - 2x) = 15, so -5x = -15, x = 3 and y = 4: the corner (3, 4). The crossings (5, 0) and (0, 5) fall short on phosphate and on nitrogen, so they are not corners.

Figure 3Example 4. The region has no far edge, so the cost has no largest value, but sliding a level line down and to the left stops at C = 55, at the corner (3, 4).

Corner	C = 5x + 10y
(0, 10)	100
(3, 4)	15 + 40 = 55
(15, 0)	75

Is 55 really the least? The region is unbounded, so check it directly. Every point of the region satisfies both floors, and

\begin{aligned} 5x + 10y &= (2x + y) + 3(x + 3y) \\ &\ge 10 + 3(15) = 55 \end{aligned}

So no mix costs less than 55 dollars, and (3, 4) reaches it. The cheapest mix is 3 bags of A and 4 bags of B, for 55 dollars, giving exactly 6 + 4 = 10 pounds of nitrogen and 3 + 12 = 15 pounds of phosphate.

No most expensive mix. The points (t, 0) with t \ge 15 all lie in the region, and their cost 5t grows without limit. Buying more bags always costs more, so the cost has a least value but no greatest.

Example 5

A whole edge is best

On the region of Example 2, find where z = 7x + 7y is largest, and where w = x - y is smallest.

Solution

Use the corners already found.

Corner	z = 7x + 7y	w = x - y
A(0, 1)	7	-1
B(8, 1)	63	7
C(3, 6)	63	-3
D(0, 3)	21	-3

The largest value of z is 63, at both B and C. The level lines 7x + 7y = k are the lines \displaystyle x + y = \frac{k}{7}, parallel to the edge CB, which lies on x + y = 9. So the level line z = 63 lies along the whole edge (Figure 4), and every point of it gives 63: for example (5, 4) gives 35 + 28 = 63, and so does (6.5, 2.5). The maximum is 63, reached on the whole segment from (3, 6) to (8, 1).

Figure 4Example 5. The level lines of z = 7x + 7y are parallel to the side CB, so the last one to touch the region lies along that whole side.

The smallest value of w is -3, at both C and D. The edge DC lies on y = x + 3, which is the line x - y = -3, a level line of w. So w = -3 at every point of the edge from (0, 3) to (3, 6), such as (1, 4) and (2, 5), and nowhere smaller.

Example 6

One unbounded region, three questions

The region is x \ge 0, x + 2y \ge 8 and x - y \le 2. Find, if they exist, (a) the smallest value of z = 2x + y, (b) the largest value of z = x - 4y, (c) the largest value of z = 2x + y.

Solution

The corners. x = 0 meets x + 2y = 8 at (0, 4); there x - y = -4 \le 2. The lines x + 2y = 8 and x - y = 2 meet where subtracting gives 3y = 6, so y = 2 and x = 4: the corner (4, 2), with x \ge 0. The third crossing, x = 0 with x - y = 2, is (0, -2), where x + 2y = -4 < 8, so it is outside. The region has just these two corners and runs off upward between the y-axis and the line x - y = 2 (Figure 5).

Figure 5Example 6. An unbounded region with only two corners. Whether an objective has a best value here depends on which way it grows.

Corner	2x + y	x - 4y
(0, 4)	4	-16
(4, 2)	10	-4

(a) The smaller corner value of 2x + y is 4, at (0, 4). To prove nothing in the region does better, write 2x + y from the constraints with positive multipliers:

\begin{aligned} 2x + y &= \tfrac{1}{2}(x + 2y) + \tfrac{3}{2}x \\ &\ge \tfrac{1}{2}(8) + 0 = 4 \end{aligned}

So the least value is 4, at (0, 4).

(b) The larger corner value of x - 4y is -4, at (4, 2). The constraint x - y \le 2 gives 2(x - y) \le 4, and x + 2y \ge 8 gives -(x + 2y) \le -8. Adding,

\begin{aligned} x - 4y &= 2(x - y) - (x + 2y) \\ &\le 4 - 8 = -4 \end{aligned}

so the greatest value is -4, at (4, 2), even though the region is unbounded.

(c) Follow the open side along the edge x - y = 2: the points (t + 2, t) with t \ge 2 satisfy x - y = 2, x \ge 0 and x + 2y = 3t + 2 \ge 8, so all lie in the region. There 2x + y = 3t + 4, which grows without limit. So 2x + y has no largest value, although the corner table would have suggested 10. That is why the open side is checked before the table is trusted.

Example 7

Buses and vans

A club is taking at least 120 people on a trip. A bus seats 40 and costs 300 dollars to hire; a van seats 10 and costs 90 dollars. Only 2 buses are available, and there are only 8 drivers, one per vehicle. How many of each should the club hire to pay the least?

Solution

Let x be the number of buses and y the number of vans. Seats: 40x + 10y \ge 120, which dividing by 10 is 4x + y \ge 12. Buses: x \le 2. Drivers: x + y \le 8. Also x \ge 0 and y \ge 0. The cost in dollars is C = 300x + 90y, to be minimized.

The corners. x = 2 with 4x + y = 12: y = 4, the point (2, 4); it uses 6 drivers. x = 2 with x + y = 8: y = 6, the point (2, 6); seats 8 + 6 = 14 \ge 12. The seats line and the drivers line meet where subtracting x + y = 8 from 4x + y = 12 gives 3x = 4, so \displaystyle x = \frac{4}{3} and \displaystyle y = \frac{20}{3}; there x \le 2 holds. The axes add nothing: (3, 0) needs a third bus and (0, 12) needs twelve drivers. The region is a triangle.

Corner	C = 300x + 90y
(2, 4)	600 + 360 = 960
(2, 6)	600 + 540 = 1140
\displaystyle \left(\frac{4}{3}, \frac{20}{3}\right)	400 + 600 = 1000

The least cost over the whole region is 960 dollars, at (2, 4). That corner is whole, so it is a real booking: 2 buses and 4 vans, seating exactly 80 + 40 = 120 people with 2 drivers to spare. The fractional corner does not need rounding, because it is not the best one, and no whole-number plan can beat the least value over all points. The answer also makes sense: a bus seat costs 300 \div 40 = 7.5 dollars and a van seat 9 dollars, so the club uses every bus it can get.

Boundaries

Everything must be linear. The corner principle needs a linear objective and linear constraints. A bulk discount, a cost that grows like x^2, or a curved limit breaks the averaging formula, and the best point can then sit in the middle of an edge or inside the region.

The region must not be empty. If the constraints contradict each other, such as x + y \le 2 and x + y \ge 5, there are no plans and nothing is best.

An unbounded region may have no best value. A best value, when it exists, is at a corner, but whether it exists has to be checked along the open side first, as in Examples 4 and 6.

Strict inequalities can lose the best value. If the constraint is x + y < 4, the corner on that line is not in the region, and x + y gets as close to 4 as you like without reaching it. Then there is no maximum at all.

Whole numbers are a further condition. For counts, a fractional best corner is not a plan; the best whole-number plan must be found by testing the whole points near it, and it may not be a corner.

Two variables, for drawing. The corner principle holds with any number of variables, but the graph and the level lines need exactly two.

Where this goes next

With three variables the constraints are planes, as in Systems in three variables, and the region is a solid with flat faces; the best value still sits at a corner, where three planes meet. Real problems have hundreds of variables, and the corners are far too many to list; methods built on Matrices walk from corner to better corner instead of checking all of them.

Looking for the best value at the ends is also the idea of optimization on a closed interval in calculus, where a function on an interval reaches its extremes at an endpoint or at a turning point. Here the turning points cannot happen, because the objective is linear, which is why the corners are enough.

Exercises

Day 1: level lines and corners given

Write the level line of z = 5x + 3y that passes through (2, 5), and give its slope.
A region is the quadrilateral with corners (0, 0), (6, 0), (4, 3) and (0, 5). Find the largest value of z = 4x + 7y on it and where it occurs.
On the region of Exercise 2, find the smallest value of z = 2x - 5y and where it occurs.

Day 1: graph the region and optimize

Maximize z = 7x + 9y subject to x \ge 0, y \ge 0, x + y \le 10 and x + 3y \le 18.
On the region of Exercise 4, find the largest and the smallest values of z = 5x - y.
Maximize z = x + 2y subject to y \ge 0, y \le 4x and x + y \le 5.
Maximize z = x + y subject to x \ge 0, y \ge 0, 5x + 2y \le 20 and x + 4y \le 8. Give the answer as an exact fraction.

Day 1: in context

A workshop has room to build at most 50 pieces a week, bookcases and benches. A bookcase takes 4 hours of finishing and a bench 2 hours, and 160 hours of finishing are available. Each bookcase makes a profit of 150 dollars and each bench 100 dollars. With the profit P = 150x + 100y, where x is the number of bookcases and y the number of benches, find the most profitable plan.
In Exercise 8, keep the bench profit at 100 dollars and let the profit on a bookcase be c dollars. For which values of c is the plan you found still a best plan?
The bakery of Example 1 gets 4 more pounds of flour, so the flour constraint becomes 3x + 2y \le 40. Find the new best plan and how much more profit it makes.

Day 2: minimizing, ties and unbounded regions

Minimize C = 5x + 6y subject to x \ge 0, y \ge 0, x + y \ge 6 and x + 3y \ge 10.
On the region of Exercise 11, minimize z = x + 5y.
Maximize z = 5x + 5y subject to x \ge 0, y \ge 0, x + y \le 7 and x \le 4. Describe every point where the maximum occurs, and check one that is not a corner.
Minimize z = 4x + 8y subject to x \ge 0, y \ge 0, x + 2y \ge 10 and 3x + y \ge 15. Describe every point where the minimum occurs.
The region is x \ge 0, y \ge 2 and y \le x + 4. Find the largest and the smallest values of z = y - 3x, or explain why one does not exist.
A library orders pizzas for a reading night and needs at least 120 slices. A small pizza has 6 slices and costs 9 dollars; a large pizza has 10 slices and costs 13 dollars. At least 4 pizzas must be small, to be made gluten-free. Find the least cost over the region, then the cheapest order of whole pizzas, C = 9x + 13y with x small and y large.

Reasoning

Explain, with level lines, why a linear objective z = ax + by, with a and b not both 0, cannot reach its maximum over a bounded region only at a point strictly inside the region.
Two corners Q_1 and Q_2 give the same value m of a linear objective. Show that every point of the segment between them also gives m.
Show that z = x + y has no largest value on the region of Exercise 11.
Explain why z = x + y has a least value but no largest value on the region x \ge 0, y \ge 0, x + y < 4.

Answers

5x + 3y = 25, slope \displaystyle -\frac{5}{3}. At (2, 5), z = 10 + 15 = 25, and solving 5x + 3y = 25 for y gives \displaystyle y = -\frac{5}{3}x + \frac{25}{3}.
37, at (4, 3). The corner values are 0, 24, 16 + 21 = 37 and 35.
-25, at (0, 5). The corner values are 0, 12, 8 - 15 = -7 and -25.
78, at (6, 4). The corners are (0, 0), (10, 0), (0, 6) and, subtracting x + y = 10 from x + 3y = 18, 2y = 8, so (6, 4). Values: 0, 70, 54 and 42 + 36 = 78.
Largest 50, at (10, 0); smallest -6, at (0, 6). The corner values are 0, 50, 30 - 4 = 26 and -6.
9, at (1, 4). The corners are (0, 0), (5, 0) and, from x + 4x = 5, (1, 4). Values: 0, 5 and 1 + 8 = 9.
\displaystyle \frac{14}{3}, at \displaystyle \left(\frac{32}{9}, \frac{10}{9}\right). Doubling the first boundary gives 10x + 4y = 40; subtracting x + 4y = 8 leaves 9x = 32, then \displaystyle 4y = 8 - \frac{32}{9} = \frac{40}{9}. The other corners (0, 0), (4, 0) and (0, 2) give 0, 4 and 2, and \displaystyle \frac{32}{9} + \frac{10}{9} = \frac{42}{9} = \frac{14}{3}.
30 bookcases and 20 benches, for 6500 dollars. Constraints x + y \le 50, 4x + 2y \le 160, x, y \ge 0. Corners: (0, 0), (40, 0), (0, 50), and from 2x + y = 80 minus x + y = 50, (30, 20). Profits: 0, 6000, 5000 and 4500 + 2000 = 6500.
100 \le c \le 200. At (30, 20) the profit is 30c + 2000. It must be at least 40c, from (40, 0), so c \le 200, and at least 5000, from (0, 50), so c \ge 100.
10 trays of muffins and 5 of pies, for 450 dollars, which is 10 dollars more. Corners: (0, 0), \displaystyle \left(\frac{40}{3}, 0\right), (0, 10) and, subtracting the oven equation, 2x = 20, so (10, 5). Profits: 0, about 333.33, 400 and 250 + 200 = 450.
32, at (4, 2). Corners: (0, 6), (10, 0) and, subtracting, 2y = 4, so (4, 2). Costs: 36, 50 and 20 + 12 = 32. It is the least because \displaystyle 5x + 6y = \frac{9}{2}(x + y) + \frac{1}{2}(x + 3y) \ge 27 + 5 = 32.
10, at (10, 0). Corner values 30, 14 and 10; and x + 5y = (x + 3y) + 2y \ge 10 + 0.
35, at every point of the edge from (4, 3) to (0, 7) on x + y = 7. Corner values: 0, 20, 35 and 35. The point (2, 5) is on that edge and gives 10 + 25 = 35.
40, at every point of the edge from (4, 3) to (10, 0) on x + 2y = 10. Corners: (0, 15), (4, 3) and (10, 0), with values 120, 40 and 40. Since 4x + 8y = 4(x + 2y) \ge 40, nothing is lower.
Largest 4, at (0, 4); no smallest value. From y \le x + 4, y - 3x \le 4 - 2x \le 4, and (0, 4) reaches it. The points (t, 2), t \ge 0, are all in the region and give 2 - 3t, which falls without limit.
Least over the region 160.8 dollars, at \displaystyle \left(4, \frac{48}{5}\right); cheapest whole order 5 small and 9 large, for 162 dollars. Constraints 6x + 10y \ge 120, x \ge 4, y \ge 0, with corners \displaystyle \left(4, \frac{48}{5}\right) and (20, 0), costing 36 + 124.8 = 160.8 and 180; the cost grows along the open side, so 160.8 is the least over the region. A whole order therefore costs at least 161 dollars. The whole solutions of 9x + 13y = 161 are (15, 2), only 110 slices, and (2, 11), too few small ones, so none works. (5, 9) gives 30 + 90 = 120 slices and 45 + 117 = 162 dollars.
If the maximum m were reached at an inside point Q, the level line ax + by = m through Q would have points of the region on both sides of it, since a small disc around Q lies in the region. On one side ax + by > m, so some point of the region beats m, which is impossible. So the maximum is reached on the boundary, and by the corner principle at a corner.
A point of the segment is (1 - t)Q_1 + tQ_2 with 0 \le t \le 1. Because z is linear, its value there is (1 - t)z(Q_1) + t\,z(Q_2) = (1 - t)m + tm = m.
The points (t, 0) with t \ge 10 satisfy x + y = t \ge 6, x + 3y = t \ge 10 and both sign constraints, so they are in the region, and there z = t, which grows without limit.
Least value 0, at (0, 0), since x \ge 0 and y \ge 0 make x + y \ge 0. No largest value: every point has x + y < 4, but for any such point, \displaystyle \left(\frac{s + 4}{2}, 0\right) with s = x + y is in the region and gives \displaystyle \frac{s + 4}{2}, which is more than s. The points of the line x + y = 4 are left out, so 4 is never reached.