Linear Programming: Optimizing with Constraints

Quick answer

Linear programming finds the largest or smallest value of a linear expression, such as the profit 50x + 30y, when x and y must satisfy a system of linear inequalities. The inequalities cut out a feasible region of allowed choices. The best value always occurs at a vertex of that region, so the method is to graph the constraints, find the corners by solving pairs of boundary equations, evaluate the objective at each corner, and pick the best.

What you'll learn

Write constraints and an objective function from a word problem
Graph a feasible region and find its vertices
Explain why an optimum occurs at a vertex
Find a maximum or minimum, or recognize that none exists

Choosing the best mix

A workshop builds bookshelves and tables. A bookshelf takes $2$ hours of cutting and $1$ hour of finishing; a table takes $1$ hour of each. Each week the workshop has $16$ hours of cutting time and $10$ hours of finishing time. A bookshelf earns $50$ dollars of profit and a table $30$ dollars. How many of each should it build?

Let $x$ be the number of bookshelves and $y$ the number of tables. The time limits and the fact that counts cannot be negative give the constraints:

\begin{aligned} 2x + y &\le 16 && \text{cutting}\\ x + y &\le 10 && \text{finishing}\\ x \ge 0, \quad y &\ge 0 \end{aligned}

The profit is the objective function, $P = 50x + 30y$ . Maximizing or minimizing a linear objective under linear constraints is called linear programming. The points that satisfy every constraint form the feasible region: every allowed week of work.

2x + y = 16
x + y = 10
50x + 30y = 420

The workshop's feasible region

Why the best point is a corner

Pick any profit, say $300$ dollars. The weeks that earn exactly $300$ lie on the line $50x + 30y = 300$ . Another profit gives a parallel line, and bigger profits sit farther up and to the right. To find the maximum, slide the line in that direction for as long as it still touches the feasible region. At the last moment of contact it meets the region at a corner, or along a whole edge when the line runs parallel to that edge. The lines of equal profit are parallel, so as they sweep across a polygon the last point they touch is a corner, and checking the corners is enough.

Corner point principle. If a linear objective has a maximum or a minimum on a feasible region, it occurs at a vertex of the region.

The method

Name the variables and write the constraints and the objective.
Graph the feasible region.
Find each vertex by solving the two boundary equations that meet there.
Evaluate the objective at every vertex and choose the best.

Example 1 — The workshop

Find the most profitable week for the workshop.

Three corners sit on the axes: $(0, 0)$ , $(8, 0)$ and $(0, 10)$ . The fourth is where the cutting and finishing lines cross. Subtracting $x + y = 10$ from $2x + y = 16$ gives $x = 6$ , and then $y = 4$ .

Vertex	$P = 50x + 30y$
$(0, 0)$	$0$
$(8, 0)$	$400$
$(6, 4)$	$420$
$(0, 10)$	$300$

The best week is $6$ bookshelves and $4$ tables, for $420$ dollars. The dashed line in the graph is $50x + 30y = 420$ , and it touches the region only at that corner.

Worked examples

Example 2 — Minimizing a cost

A farmer mixes two feeds. Each kilogram of feed A has $2$ units of protein and $1$ unit of fat; each kilogram of feed B has $1$ unit of each. The mix needs at least $8$ units of protein and at least $6$ units of fat. Feed A costs $3$ dollars per kilogram and feed B costs $2$ dollars. Find the cheapest mix.

With $x$ kilograms of A and $y$ of B, the constraints are $2x + y \ge 8$ , $x + y \ge 6$ , $x \ge 0$ and $y \ge 0$ , and the cost is $C = 3x + 2y$ . The region is unbounded: it runs off up and to the right. Its corners are $(0, 8)$ , $(6, 0)$ , and $(2, 4)$ , where the two boundary lines cross.

Vertex	$C = 3x + 2y$
$(0, 8)$	$16$
$(2, 4)$	$14$
$(6, 0)$	$18$

The cheapest mix is $2$ kg of A and $4$ kg of B, for $14$ dollars. There is no most expensive mix, since the region lets the cost grow without limit.

Common mistakes

Practice problems

A feasible region has vertices $(0, 0)$ , $(5, 0)$ , $(3, 4)$ and $(0, 6)$ . Find the maximum and minimum of $P = 4x + 3y$ .

Answer

Maximum $24$ at $(3, 4)$ ; minimum $0$ at $(0, 0)$

Full solution

At the vertices $P$ is $0$ , $20$ , $24$ and $18$ .
Find the vertices of the region $x \ge 0$ , $y \ge 0$ , $x + 2y \le 8$ , $3x + y \le 9$ .

Answer

$(0, 0)$ , $(3, 0)$ , $(2, 3)$ and $(0, 4)$

Full solution

On the axes: $3x + y \le 9$ stops the $x$ -axis at $3$ , and $x + 2y \le 8$ stops the $y$ -axis at $4$ . The slanted lines cross where $y = 9 - 3x$ and $x + 2(9 - 3x) = 8$ , so $x = 2$ and $y = 3$ .
Maximize $P = 2x + 5y$ over the region in exercise 2.

Answer

$20$ at $(0, 4)$

Full solution

At the vertices $P$ is $0$ , $6$ , $19$ and $20$ .
Maximize $P = 5x + 2y$ over the region in exercise 2.

Answer

$16$ at $(2, 3)$

Full solution

At the vertices $P$ is $0$ , $15$ , $16$ and $8$ .
Minimize $C = 4x + 5y$ subject to $x + y \ge 5$ , $x + 3y \ge 9$ , $x \ge 0$ and $y \ge 0$ .

Answer

$22$ at $(3, 2)$

Full solution

The corners are $(0, 5)$ , $(9, 0)$ , and $(3, 2)$ , where $x + y = 5$ meets $x + 3y = 9$ . The costs are $25$ , $36$ and $22$ .
A student can work at most $12$ hours a week: tutoring at $15$ dollars an hour and at a store at $10$ dollars an hour. The store needs at least $4$ hours, and tutoring is limited to $6$ hours. How should the student split the week to earn the most?

Answer

$6$ hours of tutoring and $6$ at the store, for $150$ dollars

Full solution

With $x$ hours tutoring and $y$ at the store: $x + y \le 12$ , $y \ge 4$ and $0 \le x \le 6$ . The corners are $(0, 4)$ , $(6, 4)$ , $(6, 6)$ and $(0, 12)$ , and $E = 15x + 10y$ gives $40$ , $130$ , $150$ and $120$ .
Explain why $P = x + y$ has no maximum on the region $x \ge 0$ , $y \ge 0$ , $x + y \ge 4$ . What is its minimum?

Answer

The region is unbounded; the minimum is $4$ .

Full solution

Points such as $(100, 100)$ lie in the region, and $P$ can be made as large as we like. The smallest value, $4$ , occurs all along the edge from $(4, 0)$ to $(0, 4)$ .
Maximize $P = 2x + 2y$ subject to $x \ge 0$ , $y \ge 0$ , $x + y \le 5$ and $2x + y \le 8$ .

Answer

$10$ , at $(3, 2)$ , at $(0, 5)$ , and at every point of the edge between them

Full solution

The corners are $(0, 0)$ , $(4, 0)$ , $(3, 2)$ and $(0, 5)$ , with $P$ equal to $0$ , $8$ , $10$ and $10$ . The objective’s lines are parallel to the edge $x + y = 5$ .
Could the workshop build $5$ bookshelves and $5$ tables in one week? How does that profit compare with the best week?

Answer

Yes; it earns $400$ dollars, $20$ less than the best week.

Full solution

Cutting takes $2(5) + 5 = 15 \le 16$ hours and finishing $5 + 5 = 10 \le 10$ hours, so the point is in the region, on its edge. Its profit is $50(5) + 30(5) = 400$ , less than $420$ at $(6, 4)$ .
A student maximizes $P = 3x + 2y$ over the workshop’s region by checking only $(8, 0)$ and $(0, 10)$ , and reports $24$ at $(8, 0)$ . What went wrong?

Hint

How many corners does the region have?

Answer

The student skipped the corner $(6, 4)$ , where $P = 26$ is the maximum.

Full solution

The region has four corners. At $(0, 0)$ , $(8, 0)$ , $(6, 4)$ and $(0, 10)$ the values are $0$ , $24$ , $26$ and $20$ . The corner where the two constraint lines cross beats both corners on the axes.

Frequently asked questions

What is linear programming?

A method for finding the largest or smallest value of a linear expression, the objective, when the variables must satisfy a system of linear inequalities, the constraints.

What is a feasible region?

The set of points that satisfy every constraint. In two variables it is a region of the plane, often a polygon.

Why is the maximum always at a vertex?

The points with one objective value form a line, and changing the value slides that line parallel to itself. Pushed as far as the region allows, the line last touches a corner.

What if two vertices give the same best value?

Then every point on the edge between them is also best. The objective's lines are parallel to that edge.

Can a linear programming problem have no maximum?

Yes, when the feasible region is unbounded in the direction that increases the objective. A minimum may still exist.

What to learn next

Systems of Three Equations in Three VariablesSolve linear systems in x, y and z by elimination: reduce to two equations in two unknowns, solve, substitute back, and see why a solution is where three planes meet.

Standards alignment

This lesson covers the following Common Core State Standards for Mathematics.

CCSS.MATH.CONTENT.HSA.CED.A.3Creating EquationsRepresent constraints by equations or inequalities, and by systems of equations and/or inequalities, and interpret solutions as viable or nonviable options in a modeling context.
CCSS.MATH.CONTENT.HSA.REI.D.12Reasoning with Equations and InequalitiesGraph the solutions to a linear inequality in two variables as a half-plane (excluding the boundary in the case of a strict inequality), and graph the solution set to a system of linear inequalities in two variables as the intersection of the corresponding half-planes.

For teachersPrint problems onlyTick to print a blank worksheet; leave it clear to print the lesson with the full answer key.