<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

Estimated10 minsto complete
%
Progress
Practice Linear Programming

MEMORY METER
This indicates how strong in your memory this concept is
Progress
Estimated10 minsto complete
%
Applications of Systems of Inequalities

The following diagram shows a feasible region solution for a system of linear inequalities

If , at what point on the graph is the value of the largest?

### Applications of Systems of Inequalities

A system of linear inequalities is often used to determine the maximum or minimum values of a situation with multiple constraints. For example, you might be determining how many of a product should be produced to maximize a profit.

In order to solve this type of problem using linear inequalities, follow these steps:

Step 1: Make a table to organize the given information.

Step 2: List the constraints of the situation. Write an inequality for each constraint.

Step 3: Write an equation for the quantity you are trying to maximize (like profit) or minimize (like cost).

Step 4: Graph the constraints as a system of inequalities.

Step 5: Find the exact coordinates for each vertex from the graph or algebraically.

Step 6: Use the Vertex Theorem. Test all vertices of the feasible region in the equation and see which point is the maximum or minimum.

#### Let's put the steps above into practice:

1. Evaluate the expression for the given feasible region to determine the point at which has a maximum value and the point at which has a minimum value.

The maximum value of occurred at the vertex (6, 3). The minimum value of occurred at the vertex (–4, 0).

Note that using the vertices of the feasible region to determine the maximum or the minimum value is a branch of mathematics known as linear programming. Linear programming is a technique used by businesses to solve problems. The types of problems that usually employ linear programming are those where the profit is to be maximized and those where the expenses are to be minimized. However, linear programming can also be used to solve other types of problems. The solution provides the business with a program to follow to obtain the best results for the company.

1. A company that produces flags makes two flags for Nova Scotia-the traditional blue flag and the green flag for Cape Breton. To produce each flag, two types of material, nylon and cotton, are used. The company has 450 units of nylon in stock and 300 units of cotton. The traditional blue flag requires 6 units of nylon and 3 units of cotton. The Cape Breton flag requires 5 units of nylon and 5 units of cotton. Each blue flag that is made realizes a profit of $12 for the company, whereas each Cape Breton flag realizes a profit of$15. For the nylon and cotton that the company currently has in stock, how many of each flag should the company make to maximize their profit?

Let ‘’ represent the number of blue flags. Let ‘’ represent the number of green flags.

Step 1: Transfer the information presented in the problem to a table.

Units Required per Blue Flag Units Required Per Green Flag Units Available
Nylon 6 5 450
Cotton 3 5 300
Profit(per flag) $12$15

The information presented in the problem identifies the restrictions or conditions on the production of the flags. These restrictions are known as constraints and are written as inequalities to represent the information presented in the problem.

Step 2: From the information (now in the table), list the constraints.

• The number of blue flags that are produced must be either zero or greater than zero. Therefore, the constraint is
• The number of green flags that are produced must be either zero or greater than zero. Therefore, the constraint is
• The total number of units of nylon required to make both types of flags cannot exceed 450. Therefore, the constraint is
• The total number of units of cotton required to make both types of flags cannot exceed 300. Therefore, the constraint is

Step 3: Write an equation to identify the profit.

Step 4: Graph the listed constraints to identify the feasible region.

The feasible region is the area shaded in teal blue.

Step 5: Algebraically, determine the exact point of intersection between the constraints. Also, the -intercept of the feasible region must be calculated. Write the constraints as linear equations and solve the system by elimination.

The -intercept for the inequality must be calculated. Write the inequality as a linear equation. Set ‘’ equal to zero and solve the equation for ‘’.

The -intercept of the feasible region is (75, 0).

The -intercept is (0, 60). This point was plotted when the inequalities were put into slope-intercept form for graphing.

The following graph shows the vertices of the polygon that encloses the feasible region.

Step 6: Calculate the profit, using the profit equation, for each vertex of the feasible region:

The maximum profit occurred at the vertex (50, 30). This means, with the supplies in stock, the company should make 50 blue flags and 30 green flags to maximize their profit.

### Examples

#### Example 1

Earlier, you were asked at what point on the graph is the value of , where , is the largest.

The following diagram shows a feasible region that is within a polygonal region.

The linear function  will now be evaluated for each of the vertices of the polygon.

To evaluate the value of ‘’ substitute the coordinates of the point into the expression for ‘’ and ‘’.

The value of , for each of the vertices, remains constant along any line with a slope of . This is obvious on the following graph.

As the line moved away from the origin, the value of increased. The maximum value for the shaded region occurred at the vertex (9, 4) while the minimum value occurred at the vertex (0, 0). These statements confirm the vertex theorem for a feasible region:

If a linear expression is to be evaluated for all points of a convex, polygonal region, then the maximum value of , if one exists, will occur at one of the vertices of the feasible region. Also, the minimum value of , if one exists, will occur at one of the vertices of the feasible region.

#### Example 2

For the following graphed region and the expression , find a point where ‘’ has a maximum value and a point where ‘’ has a minimum value.

The vertices of the polygonal region are (–7, –1); (2, 5); (6, 1); and (0, –4).

The maximum value of ‘’ occurred at the vertex (2, 5). The minimum value of ‘’ occurred at the vertex (–7, –1).

#### Example 3

The following table shows the time required on three machines for a company to produce Super 1 and Super 2 coffee percolators. The table also shows the amount of time that each machine is available during a one hour period. The company is trying to determine how many of each must be made to maximize a profit if they make $30 on each Super 1 model and$35 on each Super 2 model. List the constraints and write a profit statement to represent the information.

Super 1 Super 2 Time Available
Machine A 1 minute 3minutes 24 minutes
Machine B 3 minutes 2minutes 36 minutes
Machine C 3 minutes 4 minutes 44 minutes

Let ‘’ represent the number of Super 1 coffee percolators. Let ‘’ represent the number of Super 2 coffee percolators.

The number of Super 1 coffee percolators that are made must be either zero or greater than zero. Therefore, the constraint is

The number of Super 2 coffee percolators that are made must be either zero or greater than zero. Therefore, the constraint is

The total amount of time that both a Super 1 and a Super 2 model can be processed on Machine A is less than or equal to 24 minutes. Therefore, the constraint is

The total amount of time that both a Super 1 and a Super 2 model can be processed on Machine B is less than or equal to 36 minutes. Therefore, the constraint is

The total amount of time that both a Super1 and a Super 2 model can be processed on Machine C is less than or equal to 44 minutes. Therefore, the constraint is

The profit equation is

#### Example 4

A local paint company has created two new paint colors. The company has 28 units of yellow tint and 22 units of red tint and intends to mix as many quarts as possible of color X and color Y. Each quart of color X requires 4 units of yellow tint and 1 unit of red tint. Each quart of color Y requires 1 unit of yellow tint and 4 units of red tint. How many quarts of each color can be mixed with the units of tint that the company has available? List the constraints, complete the graph and determine the solution using linear programming.

Table:

Color X Color Y Units Available
Yellow Tint 4 units 1 unit 28
Red Tint 1 unit 4 units 22

Constraints: Let ‘’ represent the number of quarts of Color X paint to be made. Let ‘’ represent the number of quarts of Color Y paint to be made.

The number of quarts of Color X paint that are mixed must be either zero or greater than zero. Therefore, the constraint is

The number of quarts of Color Y paint that are mixed must be either zero or greater than zero. Therefore, the constraint is

The total amount of yellow tint that is used to mix Color X and Color Y must be less than or equal to 28. Therefore, the constraint is

The total amount of red tint that is used to mix Color X and Color Y must be less than or equal to 22. Therefore, the constraint is

Equation: The company wants to mix as many quarts as possible. They want to maximize the value of given by .

Graph:

Vertices:

The three points in the feasible region are . The company wants to maximize . The point that produces the maximum value is .

The company should mix 6 quarts of Color X paint and 4 quarts of Color Y paint.

#### Example 5

A local smelting company is able to provide its customers with iron, lead and copper by melting down either of two ores, A or B. The ores arrive at the company in railroad cars. Each railroad car of ore A contains 3 tons of iron, 3 tons of lead and I ton of copper. Each railroad car of ore B contains 1 ton of iron, 4 tons of lead and 3 tons of copper. The smelting receives an order for 7 tons of iron, 19 tons of lead and 8 tons of copper. The cost to purchase and process a carload of ore A is $7000 while the cost for ore B is$6000. If the company wants to fill the order at a minimum cost, how many carloads of each ore must be bought?

Let ‘’ represent the number of carloads of ore A to purchase. Let ‘’ represent the number of carloads of ore B to purchase.

Step 1: Transfer the information presented in the problem to a table.

One Carload of ore A One Carload of ore B Number of tons to fill the order
Tons of Iron 3 1 7
Tons of Lead 3 4 19
Tons of Copper 1 3 8

Step 2: From the information, list the constraints.

The number of carloads of ore A that must be bought is either zero or greater than zero. Therefore, the constraint is

The number of carloads of ore B that must be bought is either zero or greater than zero. Therefore, the constraint is

The total number of tons of iron from ore A and ore B must be greater than or equal to the 7 tons needed to fill the order. Therefore, the constraint is

The total number of tons of lead from ore A and ore B must be greater than or equal to the 20 tons needed to fill the order. Therefore, the constraint is

The total number of tons of copper from ore A and ore B must be greater than or equal to the 8 tons needed to fill the order. Therefore, the constraint is

Step 3: Write an equation to represent the cost in dollars of carloads of ore A and y carloads of ore B.

Step 4: Graph the listed constraints to identify the feasible region.

[Figure10]

The feasible region shows that there are an infinite number of ways to fill the order. The feasible region is the large shaded area that is sitting above the graphed lines.

[Figure11]

Step 5: Algebraically, determine the exact point of intersection between the constraints. Also, the -intercept of the feasible region must be calculated. Write the constraints as linear equations and solve the system by elimination.

The -intercept for the inequality must be calculated. Write the inequality as a linear equation. Set ‘’ equal to zero and solve the equation for ‘’.

The -intercept of the feasible region is (8, 0).

The -intercept is (0, 7). This point was plotted when the inequalities were put into slope-intercept form for graphing.

The following graph shows the vertices of the region borders the feasible region.

[Figure12]

Step 6: Calculate the cost, using the cost equation, for each vertex of the feasible region:

The minimum cost is located at the vertex (1, 4). Therefore the company should buy one carload of ore A and four carloads of ore B.

### Review

For each graphed region and corresponding equation, find a point at which ‘’ has a maximum value and a point at which ‘’ has a minimum value.

A small manufacturing company makes $125 on each DVD player it produces and$100 profit on each color TV set it makes. Each DVD player and each TV must be processed by a cutting machine (A), a fitting machine (B) and a polishing machine (C). Each DVD player must be processed on Machine A for one hour, on Machine B for one hour and on Machine C for four hours. Each TV set must be processed on Machine A for two hours, on Machine B for one hour and on Machine C for one hour. Machines A, B, and C are available for 16, 9, and 24 hours per day respectively. How many DVD players and TV sets must be made each day to maximize the profit?

1. List the constraints and state the profit equation.
2. Create a graph and identify the feasible region.
3. Determine what the company must do to maximize their profit.

April has a small business during the winter months making hats and scarves. A hat requires 2 hours on Machine A, 4 hours on Machine B and 2 hours on Machine C. A scarf requires 3 hours on Machine A, 3 hours on Machine B and 1 hour on Machine C. Machine A is available 36 hours each week, Machine B is available 42 hours each week and Machine C is available 20 hours each week. The profit on a hat is $7.00 and the profit on a scarf is$4.00. How many of each should be made each week to maximize the profit?

1. List the constraints and state the profit equation.
2. Create a graph and identify the feasible region.
3. Determine what the April must do to maximize her profit.

Beth is knitting mittens and gloves. Each pair must be processed on three machines. Each pair of mittens requires 2 hours on Machine A, 2 hours on Machine B and 4 hours on Machine C. Each pair of gloves requires 4 hours on Machine A, 2 hours on Machine B and 1 hour on Machine C. Machine A, B, and C are available 32, 18 and 24 minutes each day respectively. The profit on a pair of mittens is $8.00 and on a pair of gloves is$10.00. How many pairs of each should be made each day to maximize the profit?

1. List the constraints and state the profit equation.
2. Create a graph and identify the feasible region.
3. Determine what the Beth must do to maximize her profit.

A patient is prescribed a pill that contains vitamins A, B and C. These vitamins are available in two different brands of pills. The first type is called Brand X and the second type is called Brand Y. The following table shows the amount of each vitamin that a Brand X and a Brand Y pill contain. The table also shows the minimum daily requirement needed by the patient. Each Brand X pill costs and each Brand Y pill costs . How many pills of each brand should the patient take each day to minimize the cost?

Brand X Brand Y Minimum Daily Requirement
Vitamin A 2mg 1mg 5mg
Vitamin B 3mg 3mg 12mg
Vitamin C 25mg 50mg 125mg
1. List the constraints and state the cost equation.
2. Create a graph and identify the feasible region.
3. Determine what the patient must do to minimize his/her cost.

A local smelting company is able to provide its customers with lead, copper and iron by melting down either of two ores, X or Y. The ores arrive at the company in railroad cars. Each railroad car of ore X contains 5 tons of lead, 1 ton of copper and 1 ton of iron. Each railroad car of ore Y contains 1 ton of lead, 1 ton of copper and 2 tons of iron. The smelting company receives an order and must make at least 20 tons of lead, 12 tons of copper and 20 tons of iron. The cost to purchase and process a carload of ore X is $6000 while the cost for ore Y is$5000. If the company wants to fill the order at a minimum cost, how many carloads of each ore must be bought?

1. List the constraints and state the cost equation.
2. Create a graph and identify the feasible region.
3. Determine what the company must do to minimize their cost.

To see the Review answers, open this PDF file and look for section 5.7.

### Notes/Highlights Having trouble? Report an issue.

Color Highlighted Text Notes

### Vocabulary Language: English

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.

1. [1]^ License: CC BY-NC 3.0
2. [2]^ License: CC BY-NC 3.0
3. [3]^ License: CC BY-NC 3.0
4. [4]^ License: CC BY-NC 3.0
5. [5]^ License: CC BY-NC 3.0
6. [6]^ License: CC BY-NC 3.0
7. [7]^ License: CC BY-NC 3.0
8. [8]^ License: CC BY-NC 3.0
9. [9]^ License: CC BY-NC 3.0
10. [10]^ License: CC BY-NC 3.0
11. [11]^ License: CC BY-NC 3.0
12. [12]^ License: CC BY-NC 3.0
13. [13]^ License: CC BY-NC 3.0
14. [14]^ License: CC BY-NC 3.0
15. [15]^ License: CC BY-NC 3.0
16. [16]^ License: CC BY-NC 3.0
17. [17]^ License: CC BY-NC 3.0

### Explore More

Sign in to explore more, including practice questions and solutions for Linear Programming.