<img src="https://d5nxst8fruw4z.cloudfront.net/atrk.gif?account=iA1Pi1a8Dy00ym" style="display:none" height="1" width="1" alt="" />

Linear Programming

Maximize and minimize quantities using linear inequality systems

Estimated11 minsto complete
%
Progress
Practice Linear Programming
Progress
Estimated11 minsto complete
%
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?

Linear Programming

This lesson moves on to the concept of systems of linear inequalities. Recall 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.

Let's solve the following system of inequalities:

\begin{align*}\begin{cases} 2x+3y\le18\\ x-4y\le12 \end{cases}\end{align*}.

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 the problem above 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.

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.

Let's write the system of inequalities shown in the graph below:

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.

There is an important theorem that is used in optimization problems: 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 tells us that 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 solve the following problem using system of inequalities:

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.

Examples

Example 1

Earlier, you were told that a bracelet requires 10 beads and 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?

There are four inequalities in this situation. Let \begin{align*}b\end{align*} be the number of bracelets made and \begin{align*}n\end{align*} be the number of necklaces made.

The system of inequalities for this situation is:

\begin{align*}10b + 20n \le 1000\end{align*}-This is the amount of available beads.

\begin{align*}10b + 40n \le 1600\end{align*}-This is the available time to make the jewelry.

\begin{align*}b \ge 0\end{align*}-You cannot make negative bracelets.

\begin{align*}n \ge 0\end{align*}-You cannot make negative necklaces.

Now, graph each inequality and determine the feasible region.

The feasible region has four vertices: {(0, 0), (0, 40), (40, 30), (100, 0)}. According to the theorem, the optimization will only occur at one of these vertices.

Now, write the optimization equation: \begin{align*}5b+7.5n = maximum\space revenue\end{align*}.

Substitute each ordered pair to determine which makes the most money.

\begin{align*}(0,0) & \rightarrow \0.00\\ (0,40) & \rightarrow 5(0)+7.50(40)=\300\\ (40,30) &\rightarrow 5(40)+7.50(30)=\425\\ (100,0) & \rightarrow 5(100)+7.50(0)=\500\end{align*}

The craftsman can at most make 500 if he makes 100 bracelets. Example 2 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*} 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. Review 1. What is linear programming? 2. What is the feasible region of a system of inequalities? 3. How do constraints affect the feasible region? 4. What is an optimization equation? What is its purpose? 5. 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. 1. \begin{align*}&4y-5x<8\\ &-5x\ge16-8y\end{align*} 2. \begin{align*}&5x-y \ge5\\ &2y-x \ge -10\end{align*} 3. \begin{align*}&2x-3y \le 21\\ & x+4y \le 6\\ &3x+y \ge -4\end{align*} 4. \begin{align*}\begin{cases} y\ge\frac{1}{4} x-3\\ y<\frac{13}{8} x+8 \end{cases}\end{align*} 5. \begin{align*}\begin{cases} y\le\frac{3}{4} x-5\\ y\ge -2x+2 \end{cases}\end{align*} 6. \begin{align*}\begin{cases} y>-x+1\\ y>\frac{1}{4} x+6 \end{cases}\end{align*} 7. \begin{align*}\begin{cases} y>-\frac{1}{2} x+4\\ x<-4 \end{cases}\end{align*} 8. \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: 1. \begin{align*}& z=-x+5y\\ & x+3y \le 0\\ & x-y \ge 0\\ &3x-7y \le 16\end{align*} 2. 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*} 3. 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 him20.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.
4. 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

1. Solve by elimination: \begin{align*}\begin{cases} 12x+8y=24\\ -6x+3y=9 \end{cases}\end{align*}.
2. Solve \begin{align*}36=|5t-6|\end{align*}.
3. Determine the intercepts of \begin{align*}y=-\frac{5}{6} x-3\end{align*}.
4. 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?
5. 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?

Notes/Highlights Having trouble? Report an issue.

Color Highlighted Text Notes