7.7: Linear Programming
Suppose a craftsman can make bracelets and necklaces. A bracelet requires 10 beads and takes 10 minutes to make, while a necklace requires 20 beads and takes 40 minutes to make. The craftsman has 1000 beads to work with, and he has 1600 minutes in which to work. If a bracelet costs $5 and a necklace costs $7.50, what is the maximum revenue that the craftsman can take in? How do you know? In this Concept, you'll use systems of linear inequalities and linear programming to solve problems such as this one.
Watch This
Multimedia Link: For help with graphing systems of inequalities and how to use your graphing calculator to graph a system of inequalities, visit the CK-12 Basic Algebra: 33 Graph System of Inequalities
- Teacher Tube video or this video by CK-12 Basic Algebra: Graphing Systems of Linear Inequalities.
- Gdawgenterprises.
Guidance
Systems of Linear Inequalities
This lesson moves on to the concept of systems of linear inequalities. In previous Concepts, you learned how to graph a linear inequality in two variables.
Step 1: Graph the equation using the most appropriate method.
- Slope-intercept form uses the \begin{align*}y-\end{align*}intercept and slope to find the line.
- Standard form uses the intercepts to graph the line.
- Point-slope uses a point and the slope to graph the line.
Step 2: If the equal sign is not included draw a dashed line. Draw a solid line if the equal sign is included.
Step 3: Shade the half plane above the line if the inequality is “greater than.” Shade the half plane under the line if the inequality is “less than.”
In this Concept, we will learn how to graph two or more linear inequalities on the same coordinate plane. The inequalities are graphed separately on the same graph and the solution for the system of inequalities is the common shaded region between all the inequalities in the system.
The common shaded region of the system of inequalities is called the feasible region.
Example A
Solve the system of inequalities \begin{align*}\begin{cases} 2x+3y\le18\\ x-4y\le12 \end{cases}\end{align*}.
Solution:
The first equation is written in standard form and can be graphed using its intercepts. The line is solid because the equal sign is included in the inequality. Since the inequality is less than or equal to, shade the half plane below the line.
The second equation is a little tricky. Rewrite this in slope-intercept form to graph.
\begin{align*}&\qquad \qquad \qquad \qquad \qquad \qquad \Rightarrow \\ &-4y \le -x+12 && y \ge \frac{x}{4}-3\end{align*}
The division by –4 causes the inequality to reverse. The line is solid again because the equal sign is included in the inequality. Shade the half plane above the boundary line because \begin{align*}y\end{align*} is greater than or equal.
When we combine the graphs, we see that the blue and red shaded regions overlap. This overlap is where both inequalities work. Thus the purple region denotes the solution of the system, the feasible region.
The kind of solution displayed in this example is called unbounded, because it continues forever in at least one direction (in this case, forever upward and to the left).
Bounded regions occur when more than two inequalities are graphed on the same coordinate plane, as you will see in Example C.
Writing Systems of Linear Inequalities
In some cases, you are given the feasible region and asked to write the system of inequalities. To do this, you work in reverse order of graphing.
- Write the equation for the boundary line.
- Determine whether the sign should include “or equal to.”
- Determine which half plane is shaded.
- Repeat for each boundary line in the feasible region.
Example B
Write the system of inequalities shown below.
Solution:
There are two boundary lines, so there are two inequalities. Write each one in slope-intercept form.
\begin{align*}y & \le \frac{1}{4} x + 7\\ y & \ge -\frac{5}{2} x - 5\end{align*}
Linear Programming – Real-World Systems of Linear Inequalities
Entire careers are devoted to using systems of inequalities to ensure a company is making the most profit by producing the right combination of items or is spending the least amount of money to make certain items. Linear programming is the mathematical process of analyzing a system of inequalities to make the best decisions given the constraints of the situation.
Constraints are the particular restrictions of a situation due to time, money, or materials.
The goal is to locate the feasible region of the system and use it to answer a profitability, or optimization, question.
Theorem: The maximum or minimum values of an optimization equation occur at the vertices of the feasible region – at the points where the boundary lines intersect.
This theorem provides an important piece of information. While the individual colors of the inequalities will overlap, providing an infinite number of possible combinations, only the vertices will provide the maximum (or minimum) solutions to the optimization equation.
Let’s go back to the situation presented in the opener for this series of Concepts.
Example C
James is trying to expand his pastry business to include cupcakes and personal cakes. He has 40 hours available to decorate the new items and can use no more than 22 pounds of cake mix. Each personal cake requires 2 pounds of cake mix and 2 hours to decorate. Each cupcake order requires one pound of cake mix and 4 hours to decorate. If he can sell each personal cake for $14.99 and each cupcake order for $16.99, how many personal cakes and cupcake orders should James make to make the most revenue?
There are four inequalities in this situation. First, state the variables. Let \begin{align*}p=\end{align*} the number of personal cakes and \begin{align*}c=\end{align*} the number of cupcake orders.
Translate this into a system of inequalities.
\begin{align*}2p+1c \le 22\end{align*} – This is the amount of available cake mix.
\begin{align*}2p+4c \le 40\end{align*} – This is the available time to decorate.
\begin{align*}p \ge 0\end{align*} – You cannot make negative personal cakes.
\begin{align*}c \ge 0\end{align*} – You cannot make negative cupcake orders.
Now graph each inequality and determine the feasible region.
The feasible region has four vertices: {(0, 0),(0, 10),(11, 0),(8, 6)}. According to our theorem, the optimization answer will only occur at one of these vertices.
Write the optimization equation. How much of each type of order should James make to bring in the most revenue?
\begin{align*}14.99p+16.99c=maximum \ revenue\end{align*}
Substitute each ordered pair to determine which makes the most money.
\begin{align*}(0,0) & \rightarrow \$0.00\\ (0,10) & \rightarrow 14.99(0)+16.99(10)=\$169.90\\ (11,0) &\rightarrow 14.99(11)+16.99(0)=\$164.89\\ (8,6) & \rightarrow 14.99(8)+16.99(6)=\$221.86\end{align*}
To make the most revenue, James should make 8 personal cakes and 6 cupcake orders.
For more help with applying systems of linear inequalities, watch this video by http://www.phschool.com/atschool/academy123/english/academy123_content/wl-book-demo/ph-240s.html - PH School.
Guided Practice
Find the solution set to the following system.
\begin{align*}y & > 3x-4\\ y & < -\frac{9}{4}x+2\\ x & \ge 0\\ y & \ge 0\end{align*}
Solution:
Graph each line and shade appropriately.
\begin{align*}y > 3x-4\end{align*}
\begin{align*}y < - \frac{9}{4}x+2\end{align*}
Finally, we graph \begin{align*}x \ge 0\end{align*} and \begin{align*}y \ge 0\end{align*}, and the intersecting region is shown in the following figure.
Practice
Sample explanations for some of the practice exercises below are available by viewing the following video. Note that there is not always a match between the number of the practice exercise in the video and the number of the practice exercise listed in the following exercise set. However, the practice exercise is the same in both. CK-12 Basic Algebra: Systems of Linear Inequalities (8:52)
- What is linear programming?
- What is the feasible region of a system of inequalities?
- How do constraints affect the feasible region?
- What is an optimization equation? What is its purpose?
- You have graphed a feasible region. Where are the maximum (or minimum) points of the optimization equation located?
Find the solution region of the following systems of inequalities.
- \begin{align*}&4y-5x<8\\ &-5x\ge16-8y\end{align*}
- \begin{align*}&5x-y \ge5\\ &2y-x \ge -10\end{align*}
- \begin{align*}&2x-3y \le 21\\ &x+4y \le 6\\ &3x+y \ge -4\end{align*}
- \begin{align*}\begin{cases} y\ge\frac{1}{4} x-3\\ y<\frac{13}{8} x+8 \end{cases}\end{align*}
- \begin{align*}\begin{cases} y\le\frac{3}{4} x-5\\ y\ge -2x+2 \end{cases}\end{align*}
- \begin{align*}\begin{cases} y>-x+1\\ y>\frac{1}{4} x+6 \end{cases}\end{align*}
- \begin{align*}\begin{cases} y>-\frac{1}{2} x+4\\ x<-4 \end{cases}\end{align*}
- \begin{align*}\begin{cases} y\le6\\ y>\frac{1}{4} x+6 \end{cases}\end{align*}
Write the system of inequalities for each feasible region pictured below.
Given the following constraints, find the maximum and minimum values for:
- \begin{align*}&z=-x+5y\\ &x+3y \le 0\\ &x-y \ge 0\\ &3x-7y \le 16\end{align*}
- Find the maximum and minimum value of \begin{align*}z=2x+5y\end{align*} given the constraints. \begin{align*}2x-y & \le 12\\4x+3y & \ge 0\\x-y & \le 6\end{align*}
- In Andrew’s Furniture Shop, he assembles both bookcases and TV cabinets. Each type of furniture takes him about the same time to assemble. He figures he has time to make at most 18 pieces of furniture by this Saturday. The materials for each bookcase cost him $20.00 and the materials for each TV stand cost him $45.00. He has $600.00 to spend on materials. Andrew makes a profit of $60.00 on each bookcase and a profit of $100.00 for each TV stand. Find how many of each piece of furniture Andrew should make so that he maximizes his profit.
- You have $10,000 to invest, and three different funds from which to choose. The municipal bond fund has a 5% return, the local bank's CDs have a 7% return, and a high-risk account has an expected 10% return. To minimize risk, you decide not to invest any more than $1,000 in the high-risk account. For tax reasons, you need to invest at least three times as much in the municipal bonds as in the bank CDs. Assuming the year-end yields are as expected, what are the optimal investment amounts?
Mixed Review
- Solve by elimination: \begin{align*}\begin{cases} 12x+8y=24\\ -6x+3y=9 \end{cases}\end{align*}.
- Solve \begin{align*}36=|5t-6|\end{align*}.
- Determine the intercepts of \begin{align*}y=-\frac{5}{6} x-3\end{align*}.
- Jerry’s aunt repairs upholstery. For three hours' worth of work, she charges $145. For nine hours of work, she charges $355. Assuming this relationship is linear, write the equation for this line in point-slope form. How much would Jerry’s aunt charge for 1.25 hours worth of work?
- Translate into an algebraic sentence: “Yoder is four years younger than Kate. Kate is six years younger than Dylan. Dylan is 20.” How old is each person?
Constraint
A constraint is a limitation.Feasible region
The feasible region is the inner region within a set of four inequalities on a graph.Linear Programming
Linear programming uses the vertices of the feasible region (the area of overlap between multiple inequalities) to determine a maximum or minimum value.solution for the system of inequalities
The common shaded region between all the inequalities in the system.theorem
The maximum or minimum values of an optimization equation occur at the vertices of the feasible region – at the points where the boundary lines intersect.Image Attributions
Here you'll learn to solve linear inequality problems using linear programming.
Concept Nodes:
Constraint
A constraint is a limitation.Feasible region
The feasible region is the inner region within a set of four inequalities on a graph.Linear Programming
Linear programming uses the vertices of the feasible region (the area of overlap between multiple inequalities) to determine a maximum or minimum value.solution for the system of inequalities
The common shaded region between all the inequalities in the system.theorem
The maximum or minimum values of an optimization equation occur at the vertices of the feasible region – at the points where the boundary lines intersect.