Linear Programming: Steps & Examples

Linear programming is a method for finding the largest or smallest value of a quantity, such as profit or cost, when the variables must follow several linear limits. You graph the limits, find the corners of the region they form, and test each corner in the formula you want to maximize or minimize.

Before this lesson: You should know Graphing Linear Inequalities in Two Variables, Systems of Inequalities and the Elimination Method.

The Idea Behind Linear Programming

A business can’t make unlimited products. It runs out of time, money or materials. Each limit is an inequality called a constraint.

The points that meet every constraint form the feasible region. The formula you want to make as large or as small as possible is the objective function, such as $P = 3x + 2y$ .

Here is the key fact. When the feasible region is a closed polygon, the maximum and the minimum always happen at a corner, called a vertex. So you only need to test the corners, not every point.

How to Solve a Linear Programming Problem

Write the constraints as inequalities. Include $x \ge 0$ and $y \ge 0$ when the amounts can’t be negative.
Write the objective function.
Graph the constraints and shade the feasible region.
Find every vertex. Solve a system of two boundary lines where they cross.
Put each vertex into the objective function.
Pick the largest value for a maximum or the smallest value for a minimum.

Worked Examples

Example 1: Find a maximum

Maximize $P = 3x + 2y$ with these constraints.

x \ge 0, \quad y \ge 0, \quad x + y \le 8, \quad 2x + y \le 12

Coordinate grid with the lines x + y = 8 and 2x + y = 12. The feasible region, shaded blue, is the area in the first quadrant below both lines. Its corners are (0, 0), (6, 0), (4, 4) and (0, 8). Testing P = 3x + 2y at each corner gives 0, 18, 20 and 16, so the maximum is 20 at (4, 4). — The feasible region has four corners. The largest value of P is 20, at (4, 4).

Two corners are on the axes: $(0, 0)$ , and $(0, 8)$ where $x + y = 8$ meets the y-axis.
Find where $2x + y = 12$ meets the x-axis. Set $y = 0$ : $2x = 12$
Divide both sides by 2: $x = 6$ , so the corner is $(6, 0)$
Find where the two lines cross (see elimination method). Subtract $x + y = 8$ from $2x + y = 12$ : $x = 4$
Substitute into $x + y = 8$ : $4 + y = 8$
Subtract 4 from both sides: $y = 4$ , so the corner is $(4, 4)$
Test $(0, 0)$ : $3(0) + 2(0) = 0$
Test $(6, 0)$ : $3(6) + 2(0) = 18$
Test $(4, 4)$ : $3(4) + 2(4) = 12 + 8 = 20$
Test $(0, 8)$ : $3(0) + 2(8) = 16$

Answer: The maximum is $P = 20$ at $(4, 4)$ .

Example 2: Find a minimum and a maximum

Find the minimum and maximum of $C = 4x + 5y$ with these constraints.

x + 2y \ge 6, \quad 0 \le x \le 6, \quad 0 \le y \le 4

The region is the rectangle from $x = 0$ to $x = 6$ and $y = 0$ to $y = 4$ , above the line $x + 2y = 6$ .
Find where $x + 2y = 6$ meets the y-axis. Set $x = 0$ : $2y = 6$ , so $y = 3$ . The corner is $(0, 3)$
Find where it meets the x-axis. Set $y = 0$ : $x = 6$ . The corner is $(6, 0)$
The other corners are $(0, 4)$ and $(6, 4)$ .
Test $(0, 3)$ : $4(0) + 5(3) = 15$
Test $(0, 4)$ : $4(0) + 5(4) = 20$
Test $(6, 4)$ : $4(6) + 5(4) = 24 + 20 = 44$
Test $(6, 0)$ : $4(6) + 5(0) = 24$

Answer: The minimum is $C = 15$ at $(0, 3)$ . The maximum is $C = 44$ at $(6, 4)$ .

Example 3: Use substitution to find a corner

Maximize $P = 5x + 4y$ with $x \ge 0$ , $y \ge 0$ , $2x + y \le 10$ and $x + 2y \le 8$ .

Axis corners: $(0, 0)$ , $(5, 0)$ from $2x = 10$ , and $(0, 4)$ from $2y = 8$ .
Solve $2x + y = 10$ for $y$ (see substitution method): $y = 10 - 2x$
Substitute into $x + 2y = 8$ : $x + 2(10 - 2x) = 8$
Distribute: $x + 20 - 4x = 8$
Combine like terms: $-3x + 20 = 8$
Subtract 20 from both sides: $-3x = -12$
Divide both sides by −3: $x = 4$
Find $y$ : $y = 10 - 2(4) = 2$ , so the corner is $(4, 2)$
Test the corners: $(0, 0) \to 0$ , $(5, 0) \to 25$ , $(0, 4) \to 16$
Test $(4, 2)$ : $5(4) + 4(2) = 20 + 8 = 28$

Answer: The maximum is $P = 28$ at $(4, 2)$ .

Example 4: Word problem with profit

A shop makes tables and chairs. A table takes 4 hours of carpentry and 1 hour of finishing. A chair takes 2 hours of carpentry and 2 hours of finishing. Each week there are 40 carpentry hours and 22 finishing hours. A table earns $60 and a chair earns $35. How many of each should the shop make to earn the most?

Let $x$ be the number of tables and $y$ the number of chairs. Carpentry: $4x + 2y \le 40$
Finishing: $x + 2y \le 22$
No negative amounts: $x \ge 0$ and $y \ge 0$
Objective: $P = 60x + 35y$
Axis corners: $(0, 0)$ , $(10, 0)$ from $4x = 40$ , and $(0, 11)$ from $2y = 22$
Find where the lines cross. Subtract $x + 2y = 22$ from $4x + 2y = 40$ : $3x = 18$
Divide both sides by 3: $x = 6$
Substitute into $x + 2y = 22$ : $6 + 2y = 22$
Subtract 6 from both sides: $2y = 16$
Divide both sides by 2: $y = 8$ , so the corner is $(6, 8)$
Test $(10, 0)$ : $60(10) = 600$ . Test $(0, 11)$ : $35(11) = 385$
Test $(6, 8)$ : $60(6) + 35(8) = 360 + 280 = 640$

Answer: Make 6 tables and 8 chairs for a profit of $640 a week.

Example 5: Word problem with lowest cost

A farmer mixes two feeds. A bag of Feed A has 3 units of protein and 1 unit of fiber and costs $5. A bag of Feed B has 1 unit of protein and 2 units of fiber and costs $4. The mix needs at least 12 units of protein and at least 9 units of fiber. What mix costs the least?

Let $x$ be bags of Feed A and $y$ bags of Feed B. Protein: $3x + y \ge 12$
Fiber: $x + 2y \ge 9$
Also $x \ge 0$ and $y \ge 0$ . Objective: $C = 5x + 4y$
The region is above both lines and has no upper edge. Its corners are where it meets the axes and where the lines cross.
Protein line on the y-axis: $y = 12$ , so $(0, 12)$ . Fiber line on the x-axis: $x = 9$ , so $(9, 0)$
Solve $3x + y = 12$ for $y$ : $y = 12 - 3x$
Substitute into $x + 2y = 9$ : $x + 2(12 - 3x) = 9$
Distribute: $x + 24 - 6x = 9$
Combine like terms: $-5x + 24 = 9$
Subtract 24 from both sides: $-5x = -15$
Divide both sides by −5: $x = 3$
Find $y$ : $y = 12 - 3(3) = 3$ , so the corner is $(3, 3)$
Test $(0, 12)$ : $5(0) + 4(12) = 48$ . Test $(9, 0)$ : $5(9) + 4(0) = 45$
Test $(3, 3)$ : $5(3) + 4(3) = 15 + 12 = 27$

Answer: Use 3 bags of each feed for the lowest cost, $27. This region is open, so the cost has no maximum.

Common Mistakes

Mistake	Example of the error	Fix
Testing points inside the region	Trying $(2, 2)$ in Example 1	Only the corners can give the maximum or minimum.
Missing a corner	Testing only the axis corners in Example 1 and getting 18	Find every place two boundary lines cross, including the corner between them.
Forgetting $x \ge 0$ and $y \ge 0$	Using a corner like $(-2, 10)$	Amounts of things can’t be negative. Add these constraints.
Reporting the corner, not the value	Saying “the maximum is (4, 4)”	Give both: the maximum is 20, at $(4, 4)$ .
Claiming a maximum on an open region	Saying the feed mix has a highest cost	On an open region, check which value can keep growing. Only one of max or min may exist.

Practice Problems

Maximize $P = 2x + 3y$ with $x \ge 0$ , $y \ge 0$ , $x + y \le 6$ and $x \le 4$ .
Find the minimum and maximum of $C = x + 2y$ with $x \ge 1$ , $y \ge 1$ and $x + y \le 5$ .
Maximize $P = 4x + 3y$ with $x \ge 0$ , $y \ge 0$ , $2x + y \le 8$ and $x + y \le 5$ .
Find the vertices of the region $x \ge 0$ , $y \ge 0$ , $x + 2y \le 10$ and $3x + y \le 15$ .
Use the region in Problem 4 to maximize $P = x + 4y$ .
Minimize $C = 2x + 3y$ with $x + y \ge 6$ , $x \ge 1$ and $y \ge 2$ .
Use the region in Problem 3 to maximize $P = 3x + 3y$ . What is special about the answer?
Maya tutors for $15 an hour and works at a store for $12 an hour. She can work at most 20 hours a week and tutor at most 8 hours. How many hours of each earn the most?
A baker makes cakes and pies. A cake uses 3 cups of flour and 1 hour. A pie uses 2 cups of flour and 1 hour. There are 36 cups of flour and 14 hours. A cake earns $10 and a pie earns $8. How many of each earn the most?
A school needs at least 160 seats for a trip. A van holds 10 people and costs $80. A bus holds 40 people and costs $250. There are only 7 drivers, so at most 7 vehicles. What mix costs the least?

Show answers

Corners: $(0, 0)$ , $(4, 0)$ , $(0, 6)$ , and where $x = 4$ meets $x + y = 6$
Substitute $x = 4$ : $4 + y = 6$ , so $y = 2$ . Corner $(4, 2)$
Test: $(0, 0) \to 0$ , $(4, 0) \to 8$ , $(4, 2) \to 8 + 6 = 14$ , $(0, 6) \to 18$
Maximum $P = 18$ at $(0, 6)$
Corners: $(1, 1)$ , where $y = 1$ meets $x + y = 5$ , and where $x = 1$ meets it
$x + 1 = 5$ , so $x = 4$ . Corner $(4, 1)$
$1 + y = 5$ , so $y = 4$ . Corner $(1, 4)$
Test: $(1, 1) \to 3$ , $(4, 1) \to 6$ , $(1, 4) \to 9$
Minimum 3 at $(1, 1)$ , maximum 9 at $(1, 4)$
Axis corners: $(0, 0)$ , $(4, 0)$ , $(0, 5)$
Subtract $x + y = 5$ from $2x + y = 8$ : $x = 3$
Substitute: $3 + y = 5$ , so $y = 2$ . Corner $(3, 2)$
Test: $0$ , $16$ , $15$ , and $4(3) + 3(2) = 18$
Maximum $P = 18$ at $(3, 2)$
Axis corners: $(0, 0)$ , $(5, 0)$ from $3x = 15$ , $(0, 5)$ from $2y = 10$
Solve $3x + y = 15$ for $y$ : $y = 15 - 3x$
Substitute: $x + 2(15 - 3x) = 10$
Distribute: $x + 30 - 6x = 10$
Combine: $-5x + 30 = 10$
Subtract 30: $-5x = -20$ , so $x = 4$
Then $y = 15 - 12 = 3$
Vertices: $(0, 0)$ , $(5, 0)$ , $(4, 3)$ , $(0, 5)$
Test: $(0, 0) \to 0$ , $(5, 0) \to 5$ , $(4, 3) \to 4 + 12 = 16$ , $(0, 5) \to 20$
Maximum $P = 20$ at $(0, 5)$
The region is open. Corners: $x = 1$ meets $x + y = 6$ at $(1, 5)$
$y = 2$ meets $x + y = 6$ at $(4, 2)$
Test: $(1, 5) \to 2 + 15 = 17$ , $(4, 2) \to 8 + 6 = 14$
Minimum $C = 14$ at $(4, 2)$
Test: $(0, 0) \to 0$ , $(4, 0) \to 12$ , $(3, 2) \to 15$ , $(0, 5) \to 15$
Maximum 15 at two corners, $(3, 2)$ and $(0, 5)$
Every point on the edge between them also gives 15.
Let $x$ = tutoring hours, $y$ = store hours. Constraints: $x + y \le 20$ , $x \le 8$ , $x \ge 0$ , $y \ge 0$
Objective: $E = 15x + 12y$
Corners: $(0, 0)$ , $(8, 0)$ , $(0, 20)$ , and $x = 8$ with $8 + y = 20$ , so $(8, 12)$
Test: $(8, 0) \to 120$ , $(0, 20) \to 240$ , $(8, 12) \to 120 + 144 = 264$
Tutor 8 hours and work 12 store hours to earn $264.
Let $x$ = cakes, $y$ = pies. Constraints: $3x + 2y \le 36$ , $x + y \le 14$ , $x \ge 0$ , $y \ge 0$
Objective: $P = 10x + 8y$
Axis corners: $(0, 0)$ , $(12, 0)$ , $(0, 14)$
Multiply $x + y = 14$ by 2: $2x + 2y = 28$
Subtract from $3x + 2y = 36$ : $x = 8$
Then $y = 14 - 8 = 6$ . Corner $(8, 6)$
Test: $(12, 0) \to 120$ , $(0, 14) \to 112$ , $(8, 6) \to 80 + 48 = 128$
Make 8 cakes and 6 pies to earn $128.
Let $x$ = vans, $y$ = buses. Constraints: $10x + 40y \ge 160$ , $x + y \le 7$ , $x \ge 0$ , $y \ge 0$
Objective: $C = 80x + 250y$
Divide the seat constraint by 10: $x + 4y \ge 16$
Subtract $x + y = 7$ from $x + 4y = 16$ : $3y = 9$ , so $y = 3$
Then $x = 7 - 3 = 4$ . Corner $(4, 3)$
Other corners on the y-axis: $(0, 4)$ and $(0, 7)$
Test: $(0, 4) \to 1000$ , $(4, 3) \to 320 + 750 = 1070$ , $(0, 7) \to 1750$
Rent 4 buses and no vans for $1,000.

FAQ

What are the steps of linear programming?

Write the constraints and the objective function. Graph the feasible region, find its vertices, and test each vertex in the objective function.

What is a feasible region?

It is the set of all points that meet every constraint. On a graph, it is the area where all the shaded regions overlap.

Why is the answer always at a vertex?

The objective function is linear, so its value rises steadily in one direction across the region. The largest and smallest values happen where the region ends, at a corner.

What if two vertices give the same maximum?

Then every point on the edge between them gives that maximum too. The problem has many best answers.

Summary

Linear programming finds the maximum or minimum of an objective function under linear constraints.
The feasible region is where every constraint is true.
On a closed region, the maximum and minimum happen at vertices.
Find each vertex by solving two boundary equations, then test every vertex.
On an open region, only a maximum or only a minimum may exist.

Previous lesson: Systems of Equations in Three Variables

Next lesson: Complex Numbers

Back to the Algebra 2 Index