<meta http-equiv="refresh" content="1; url=/nojavascript/"> Linear Programming ( Read ) | Algebra | CK-12 Foundation
Dismiss
Skip Navigation

Linear Programming

%
Best Score
Practice
Best Score
%
Practice Now

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.

Guidance

Systems of Linear Inequalities

This lesson moves on to the concept of systems of linear inequalities. In the previous topic, 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 y- 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: Test a point not on the line in the original inequality and shade the half plane that works.

In this topic, 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{cases}2x+3y\le18\\x-4y\le12 \end{cases} .

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 (0, 0) works in the inequality, shade the half plane below the line.

The second equation can be rewritten in slope-intercept form to graph.

&\qquad \qquad \qquad \qquad \qquad \qquad \Rightarrow \\&-4y \le -x+12  && y \ge \frac{x}{4}-3

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 (0, 0) works in the original inequality.

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.

y & \le \frac{1}{4} x + 7\\y & \ge -\frac{5}{2} x - 5

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 look at the following situation.

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 p= the number of personal cakes and c= the number of cupcake orders .

Translate this into a system of inequalities.

2p+1c \le 22 – This is the amount of available cake mix.

2p+4c \le 40 – This is the available time to decorate.

p \ge 0 – You cannot make negative personal cakes.

c \ge 0 – 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)}. To find each of these points, select the inequalities in pairs and solve them as a system of equations.

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?

14.99p+16.99c=maximum \ revenue

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

(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

To make the most revenue, James should make 8 personal cakes and 6 cupcake orders.

Example D

Two oil refineries produce three grades of gasoline: A, B, and C.  At each refinery, the various grades of gasoline are produced in a single operation so that they are in fixed proportions.  Assume that one operation at Refinery 1 produces 1 unit of A, 3 units of B, and 1 unit of C.  One operation at Refinery 2 produces 1 unit of A, 4 units of B, and 5 units of C.  Refinery 1 charges $3000 for what is produced in one operation, and Refinery 2 charges $5000 for the production of one operation.  A consumer needs 100 units of A, 340 units of B, and 150 units of C.  How should the orders be placed if the consumer is to meet his needs most economically?

There are five inequalities in this situation. First, state the variables. Let x = the number of operations ordered at Refinery 1 and y = the number of operations ordered at Refinery 2 .

Translate this into a system of inequalities.

1x+1y \ge 100 – This is the amount of units of gasoline A produced.

3x+4y \ge 340 – This is the amount of units of gasoline B produced.

1x+5y \ge 150 – This is the amount of units of gasoline C produced.

x \ge 0 – You cannot make negative orders at Refinery 1.

y \ge 0 – You cannot make negative orders at Refinery 2.

Now graph each inequality and determine the feasible region.

License: CC BY-NC 3.0

Looking at the feasible region we see it has four vertices. To find each of these points, we select the inequalities whose lines cross at each point and find their intersection. Starting from left to right we have x=0\\x+y=100 , x+y=100\\3x+4y=340 , 3x+4y=340\\x+5y=150 , and y=0\\x+5y=150 . Solving them by substitution or elimination the 4 vertices are at \left (0, 100 \right ) , \left (60, 40 \right ) , \left (100, 10 \right ) , and \left (150, 0 \right ) .

According to our theorem, the optimization answer will only occur at one of these vertices.

Write the optimization equation. How many orders at each refinery should be made to complete the production most economically?

3000x + 5000y &= cost \ of \ production

Substitute each ordered pair to determine which costs the least money.

(0,100) & \rightarrow 3000(0)+5000(100)=\$500,000\\(60,40) & \rightarrow 3000(60)+5000(40)=\$380,000\\(100,10) &\rightarrow 3000(100)+5000(10)=\$350,000\\(150,0) & \rightarrow 3000(150)+5000(0)=\$450,000\\

To be the most economical, 100 orders should be made at Refinery 1 and 10 at Refinery 2.

Guided Practice

1.   Find the solution set to the following system.

y & > 3x-4\\y & < -\frac{9}{4}x+2\\x & \ge 0\\y & \ge 0

2.   The Reliable Appliance store wishes to stock at most 100 refrigerators and stoves.  They are sure they cannot sell more than 50 refrigerators.  Each refrigerator weighs 200 pounds and each stove 100 pounds and they are limited to a total weight of 12,000 pounds.  They make $35 on each refrigerator and $20 on each stove.  How many of each should they stock in order to maximize profits?

Solution:

1. Graph each line and shade appropriately.

y > 3x-4

y < - \frac{9}{4}x+2

Finally, we graph x \ge 0 and y \ge 0 , and the intersecting region is shown in the following figure.

2.  There are five inequalities in this situation. First, state the variables. Let R = the number of refrigerators and S = the number of stoves .

Translate this into a system of inequalities.

1R+1S \le 100 – Stock at most 100.

R \le 50 – Can sell no more than 50 refrigerators.

200R+100S \le 12000 – Total weight limit.

R \ge 0 – You cannot stock negative refrigerators.

S \ge 0 – You cannot stock negative stoves.

Now graph each inequality and determine the feasible region.

License: CC BY-NC 3.0

Looking at the feasible region we see it has five vertices. To find each of these points, we select the inequalities whose lines cross at each point and find their intersection. We have R=0\\S=0 , R=0\\R+S=100 , R+S=100\\200R+100S=12000 , 200R+100S=12000\\R=50 , and S=0\\R=50 . Solving them by substitution or elimination the 5 vertices are at \left (0, 0 \right ) , \left (0, 100 \right ) , \left (20, 80 \right ) , \left (50, 20 \right ) , and \left (50, 0 \right ) .

According to our theorem, the optimization answer will only occur at one of these vertices.

Write the optimization equation. How many of each should they stock in order to maximize profits?

35R + 20S &= profit

Substitute each ordered pair to determine which maximizes profit.

(0,0) & \rightarrow 35(0)+20(0)=\$0\\(0,100) & \rightarrow 35(0)+20(100)=\$2000\\(20,80) & \rightarrow 35(20)+20(80)=\$2300\\(50,20) & \rightarrow 35(50)+20(20)=\$2150\\(50,0) & \rightarrow 35(50)+20(0)=\$1750\\

To make the most profit, they should stock 20 refrigerators and 80 stoves.

Image Attributions

  1. [1]^ License: CC BY-NC 3.0
  2. [2]^ License: CC BY-NC 3.0

Reviews

Email Verified
Well done! You've successfully verified the email address .
OK
Please wait...
Please wait...

Original text