Applications of Linear Programming Section 2.2 PDF

Preview

Summary

Section 2 of chapter 2 of Finite Mathemetics...

Description

Section 2.2 – Applications of Linear Programming A company known as Summer Breezes produces two types of ceiling fans, a standard model and a deluxe model. The company is interested in maximizing their profit, but only has a certain number of hours to operate and has a limited amount of material to produce each type of ceiling fan. Since linear programming problems maximize or minimize objective functions subject to certain constraints, this company can use linear programming in making important decisions. In this section, we will look at situations similar to the one above. A word problem will be given, and we will set up a linear programming problem and solve it using the graphical method from Section 2.1. Example 1: Stay Hydrated produces water bottles, filtered and unfiltered. The profit for each filtered water bottle is $18, and the profit for each unfiltered water bottle is $10. The amount of time (in minutes) it takes to manufacture and package each type of water bottle is given below: Filtered

Unfiltered

Manufacture

12

6

Package

8

2

The company has at most 40 hours a week available in the manufacturing department and at most 20 hours a week available in the packaging department. How many of each type of water bottle should be produced per week to maximize profit? Solution: Let x represent the number of filtered water bottles, y represent the number of unfiltered water bottles, and P represent profit. The profit for each filtered water bottle is 18, so the profit for x of these bottles is 18x . The profit for each unfiltered water bottle is $10, so the profit for y of these bottles is 10y The objective function for the profit is therefore P = 18 x + 10 y . Since the company wishes to maximize profit, we want to start the linear programming problem as follows: Maximize P = 18 x + 10 y The time given in the table is in minutes, but the time available per department is given in hours. We need to state all numbers in either minutes or hours. We will choose to convert the information given in hours to minutes.

Math 1313

Page 1 of 15

Section 2.2

40 hours ×

60 minutes = 2400 minutes 1 hour

20 hours ×

60 minutes = 1200 minutes 1 hour

There are at most 2,400 minutes a week available in the manufacturing department and at most 1,200 minutes a week available in the packaging department. Each filtered water bottle takes 12 minutes to manufacture and each unfiltered water bottle takes 6 minutes to manufacture, so the total manufacturing time for both types of bottles is 12x + 6 y . Since the manufacturing department has at most 2400 minutes available, we obtain the constraint 12 x + 6 y ≤ 2400 Each filtered water bottle takes 8 minutes to package and each unfiltered water bottle takes 2 minutes to package, so the total packaging time for both types of bottles is 8x + 2 y . Since the packaging department has at most 1200 minutes available, we obtain the constraint 8x + 2 y ≤ 1200 The company cannot produce a negative number of each type of water bottle, so we also have the constraints x≥0 y≥ 0 The linear programming problem is as follows: Maximize P = 18 x + 10 y

 12 x + 6 y ≤ 2400  8x + 2 y ≤ 1200  subject to:   x≥ 0  y ≥ 0 We now use the graphical method from Section 2.1 to solve the linear programming problem. The intercepts of 12 x + 6 y = 2400 are shown below:

12 x + 6 y = 2400

12 x + 6 y = 2400

12 x + 6 ( 0 ) = 2400

12 ( 0 ) + 6 y = 2400

x = 200

y = 400

The test point ( 0, 0) satisfies the inequality 12x + 6 y ≤ 2400, so we shade the half-plane containing ( 0, 0 ) . Math 1313

Page 2 of 15

Section 2.2

The intercepts of 8 x + 2 y = 1200 are shown below: 8x + 2 y = 1200

8 x + 2 y = 1200

8x + 2( 0) = 1200

8 ( 0 ) + 2 y = 1200

x = 150

y = 600

The test point ( 0, 0) satisfies the inequality 8x + 2 y ≤ 1200 , so we shade the half-plane containing ( 0, 0 ) . The inequality x ≥ 0 represents the y-axis along with the first and fourth quadrants. The inequality y ≥ 0 represents the x-axis along with the first and second quadrants. The intersection of these two inequalities is therefore the first quadrant along with the axes bounding that quadrant. The feasible set is shown below.

We can see from the diagram that the feasible set is bounded, so this problem will have an optimal solution. We can identify the corner points ( 0, 0) , ( 0, 400) , (150, 0 ) based on our graph and the known intercepts. To find the remaining corner point, we need to solve the following system of equations:

 12 x + 6 y = 2400   8x + 2 y = 1200 We will choose to eliminate y, so we multiply the second equation by − 3 :

Math 1313

Page 3 of 15

Section 2.2

12x + 6 y = 2400 + −24x − 6 y = −3600 − 12x

= − 1200

x = 100 We then substitute x = 100 into either equation to find the value of y. 12 x + 6 y = 2400 12 (100 ) + 6 y = 2400 6 y = 1200 y = 200 The final corner point is (100, 200) , shown in the feasible set below.

Finally, we substitute each corner point into the objective function to determine the optimal solution.

Math 1313

Vertex of Feasible Set

Value of P = 18 x + 10 y

( 0, 0 )

P = 18 ( 0 ) + 10 ( 0 ) = 0

( 0, 400)

P = 18 (0 ) +10 (400 ) = 4000

(150, 0 )

P = 18 (150) + 10 (0 ) = 2700

(100, 200 )

P = 18 (100 ) + 10 ( 200 ) = 3800

Page 4 of 15

Section 2.2

The maximum is $4,000 and it occurs at ( 0, 400) . This means that Stay Hydrated should manufacture 0 filtered water bottles and 400 unfiltered water bottles to maximize their profit. *** Example 2: Horsing Around makes horse saddles in both a child size and an adult size. Each child saddle requires 20 hours of assembly and 15 hours of finishing. Each adult saddle requires 30 hours of assembly and 10 hours of finishing. The company has a maximum of 300 hours available per week in the assembly department and a maximum of 150 hours per week in the finishing department. The profit for each child saddle is $255 and the profit for each adult saddle is $375. If the company wants to maximize their profit, how many child and adult horse saddles should be produced per week? What is the maximum profit? Solution: Let x represent the number of child saddles, y represent the number of adult saddles, and P represent profit.

The profit for each child saddle is $255, so the profit for x of these saddles is 255x . The profit for each adult saddle is $375, so the profit for y of these saddles is 375y . The objective function for the profit is therefore P = 255 x + 375 y . Since the company wants to maximize profit, we want to start the linear programming problem as follows: Maximize P = 255 x + 375 y Each child saddle takes 20 hours to assemble and each adult saddle takes 30 hours to assemble, so the total assembly time for both types of saddles is 20x + 30 y . Since the assembly department has at most 300 hours available, we obtain the constraint 20 x + 30 y ≤ 300 Each child saddle takes 15 hours to finish and each adult saddle takes 10 hours to finish, so the total finishing time for both types of saddles is 15x + 10y . Since the finishing department has at most 150 hours available, we obtain the constraint 15 x + 10 y ≤ 150 The company cannot produce a negative number of each type of saddle, so we also have the constraints x≥0 y≥ 0 The linear programming problem is as follows: Math 1313

Page 5 of 15

Section 2.2

Maximize P = 255 x + 375 y

 20x + 30 y ≤ 300   15 x + 10 y ≤ 150 subject to:   x≥ 0  y ≥ 0 We now use the graphical method from Section 2.1 to solve the linear programming problem. The intercepts of 20 x + 30 y = 300 are shown below: 20 x + 30 y = 300

20 x +30 y = 300

20 x + 30 ( 0 ) = 300

20 (0 ) + 30 y = 300

x = 15

y = 10

The test point ( 0, 0) satisfies the inequality 20 x + 30 y ≤ 300 , so we shade the half-plane containing ( 0, 0 ) . The intercepts of 15 x + 10 y = 150 are shown below: 15 x + 10 y = 150

15 x + 10 y = 150

15 x + 10 (0 ) = 150

15 ( 0 ) + 10 y = 150

x = 10

y = 15

The test point ( 0, 0) satisfies the inequality 15x + 10 y ≤ 150 , so we shade the half-plane containing ( 0, 0 ) . The inequalities x ≥ 0 and y ≥ 0 together represent the first quadrant, along with the axes bounding that quadrant. The feasible set and corner points are shown below.

Math 1313

Page 6 of 15

Section 2.2

We can see from the diagram that the feasible set is bounded, so this problem will have an optimal solution. We can identify the corner points ( 0, 0) , ( 0, 10) and (10, 0) based on our graph and the known intercepts. To find the remaining corner point, we need to solve the following system of equations:

 20 x + 30 y = 300   15x + 10 y = 150 We will choose to eliminate y, so we multiply the second equation by − 3 : 20x + 30 y = 300 + −45x − 30 y = −450 − 25x

= − 150

x=6 We then substitute x = 6 into either equation to find the value of y. 20x + 30y = 300 20 ( 6 ) + 30 y = 300 30 y = 180 y= 6 The final corner point is (6, 6) , shown in the feasible set below.

Finally, we substitute each corner point into the objective function to determine the optimal solution.

Math 1313

Page 7 of 15

Section 2.2

Vertex of Feasible Set

Value of P = 255x + 375y

( 0, 0)

P = 255 ( 0) + 375 ( 0 ) = 0

( 0,10)

P = 255 (0 ) + 375 (10 ) = 3750

(10, 0)

P = 255 (10 ) + 375 (0 ) = 2550

( 6, 6)

P = 255 ( 6 ) + 375 ( 6 ) = 3780

The maximum is 3780 and it occurs at (6, 6 ) . This means that Horsing Around should produce 6 child horse saddles and 6 adult horse saddles per week to maximize their profit. The maximum profit is $3,780. *** Example 3: A chef owns a vegetable field. He has determined that each year, he needs to fertilize his field with at least 1200 pounds of calcium and at least 600 pounds of magnesium to yield the best harvest. Each bag of Brand I fertilizer contains 6 pounds of calcium, 2 pounds of magnesium and 1 pound of sulfur. Each bag of Brand II fertilizer contains 3 pounds of calcium, 3 pounds of magnesium and 1 pound of sulfur. How many bags of Brand I and Brand II should be used to meet the minimum fertilizer requirements and also minimize the amount of sulfur added to the vegetable field? Solution: Let x represent the number of bags of Brand I, y represent the number of bags of Brand II, and S represent the amount of sulfur.

Each bag of Brand I contains one pound of sulfur, so the amount of sulfur in x bags is x pounds. Each bag of Brand II contains one pound of sulfur, so the amount of sulfur in y bags is y pounds. The objective function for the amount of sulfur is therefore S = x + y . Since the company wants to minimize the amount of sulfur being used, we start the linear programming problem as follows: Minimize S = x + y Each bag of Brand I contains 6 pounds of calcium, so the amount of calcium in x bags is 6x pounds. Each bag of Brand II contains 3 pounds of calcium, so the amount of sulfur in y bags is 6y pounds. Since the vegetable field needs at least 1200 pounds of calcium, we obtain the constraint

Math 1313

Page 8 of 15

Section 2.2

6x + 3y ≥ 1200 Each bag of Brand I contains 2 pounds of magnesium and each bag of Brand II contains 3 pounds of magnesium, but since the vegetable field needs at least 600 pounds of magnesium, we obtain the constraint 2x + 3y ≥ 600 The company cannot purchase a negative number of bags of each type of fertilizer, so we also have the constraints x≥0 y≥ 0 The linear programming problem is as follows: Minimize S = x + y

   subject to:   

6x + 3y ≥ 1200 2x + 3y ≥ 600 x≥ 0 y≥0

We now use the graphical method from Section 2.1 to solve the linear programming problem. The intercepts of 6 x + 3 y = 1200 are shown below: 6x + 3y = 1200

6 x + 3 y = 1200

6x + 3( 0) = 1200

6 ( 0 ) + 3 y = 1200

x = 200

y = 400

The test point ( 0, 0) does not satisfy the inequality 6 x +3 y ≥1200 , so we shade the half-plane not containing ( 0, 0) . The intercepts of 2 x + 3 y = 600 are shown below. 2x + 3y = 600

2 x + 3 y = 600

2x + 3( 0) = 600

2 ( 0 ) + 3 y = 600

x = 300

y = 200

The test point ( 0, 0) does not satisfy the inequality 2 x +3 y ≥ 600 , so we shade the half-plane not containing ( 0, 0) . Math 1313

Page 9 of 15

Section 2.2

The inequalities x ≥ 0 and y ≥ 0 together represent the first quadrant, along with the axes bounding that quadrant. The feasible set and corner points are shown below.

Notice that the feasible set is unbounded, so this problem may or may not have an optimal solution. We can identify the corner points ( 0, 400) and ( 300, 0 ) based on our graph and the known intercepts. To find the remaining corner point, we need to solve the following system of equations:

 6 x +3 y =1200   2 x +3 y = 600 We will choose to eliminate y, so we multiply the second equation by − 1 : 6x + 3y = 1200 + −2x − 3y = −600

4x = 600 x = 150 We then substitute x = 150 into either equation to find the value of y. 6x + 3y = 1200 6( 150) + 3 y = 1200 3y = 300 y = 100 The final corner point is (150, 100) , shown in the feasible set below.

Math 1313

Page 10 of 15

Section 2.2

Next, we substitute each corner point into the objective function to determine the optimal solution.

Vertex of Feasible Set

Value of S = x + y

(0, 400)

P = 0 + 400 = 400

(300, 0 )

P = 300 + 0 = 300

(150,100 )

P = 150 +100 = 250

The minimum value appears to be 250, which occurs at (150,100 ) . Since the feasible set is unbounded, this may or may not represent the minimum. Let us test some points in the feasible set near the suspected optimal solution of (150, 100 ) : For test point (151, 100) : S = x + y = 151 + 100 = 251 For test point (150, 101) : S = x + y = 150 + 101 = 251 For test point (151, 101) : S = x + y = 151 +101 = 252 We could go on testing and would not find any points in the feasible set which yield a function value less than 250. (Note: If we wanted to instead maximize the amount of sulfur, this objective function would have no maximum.) The chef should use 150 bags of Brand I and 100 bags of Brand II each year to minimize the amount of sulfur added to the vegetable field. The minimum amount of sulfur added is 250 pounds. ***

Math 1313

Page 11 of 15

Section 2.2

Example 4: A body builder wants to build lean muscle using two types of supplement packets. Each packet of Brand I contains 10 grams of fat, 3 grams of carbohydrates and 15 grams of protein. Each packet of Brand II contains 5 grams of fat, 6 grams of carbohydrates and 30 grams of protein. He has decided that from these two types of packets, he would like to take in a maximum of 40 grams of fat per day and a minimum of 150 grams of protein per day. How many packets of each brand should he take per day to minimize the intake of carbohydrates? What is the minimum intake of carbohydrates? Solution: Let x represent the number of packets of Brand I, y represent the number of packets of Brand II, and C represent the number of grams of carbohydrates. Brand I contains 3 grams of carbohydrates per packet, so there are 3 x grams of carbohydrates in x packets of Brand I. Brand II contains 6 grams of carbohydrates per packet, so there are 6y grams of carbohydrates in y packets of Brand II. The objective function for the number of grams of carbohydrates is therefore C = 3 x + 6 y . Since the body builder wants to minimize carbohydrates, we want to start the linear programming problem as follows: Minimize C = 3 x + 6 y Brand I contains 10 grams of fat per packet, so there are 10x grams of fat in x packets of Brand I. Brand II contains 5 grams of fat per packet, so there are 5 y grams of carbohydrates in y packets of Brand II. Since the body builder wants to take in no more than 40 grams of fat per day using these packets, we obtain the constraint 10 x + 5 y ≤ 40 Brand I contains 15 grams of protein per packet, so there are 15x grams of protein in x packets of Brand I. Brand II contains 30 grams of protein per packet, so there are 30 y grams of protein in y packets of Brand II. Since the body builder wants to take in at least 150 grams of protein, we obtain the constraint 15 x + 30 y ≥ 150 The body builder cannot take in a negative number of either type of packet, so we also have the constraints

x≥0 y≥ 0 The linear programming problem is as follows:

Math 1313

Page 12 of 15

Section 2.2

Minimize C = 3 x + 6 y

 10 x + 5 y ≤ 40   15 x + 30 y ≥ 150 subject to:   x≥ 0  y ≥ 0 We now use the graphical method from Section 2.1 to solve the linear programming problem. The intercepts of 10 x + 5 y = 40 are shown below: 10 x + 5 y = 40

10 x + 5 y = 40

10 x + 5 ( 0 ) = 40

10 ( 0 ) + 5 y = 40

x=4

y=8

The test point ( 0, 0) satisfies the inequality 10 x + 5 y ≤ 40 , so we shade the half-plane containing

(0, 0) . The intercepts of 15 x + 30 y = 150 are shown below: 15 x + 30 y = 150

15 x + 30 y = 150

15 x + 30 ( 0 ) = 150

15 ( 0 ) + 30 y = 150

x = 10

y=5

The test point ( 0, 0) does not satisfy the inequality 15x + 30 y ≥ 150 , so we shade the half-plane not containing ( 0, 0) . The inequalities x ≥ 0 and y ≥ 0 together represent the first quadrant, along with the axes bounding that quadrant. The feasible set and corner points are shown below.

Math 1313

Page 13 of 15

Section 2.2

We can see from the diagram that the feasible set is bounded, so this problem will have an optimal solution. We can identify the corner points ( 0, 5) and (0, 8) based on our graph and the known intercepts. To find the remaining corner point, we need to solve the following system of equations:

 10x + 5y = 40   15x + 30 y = 150 We will choose to eliminate y, so we multiply the first equation by −6 : − 60 x − 30 y = −240 + 15 x + 30 y = 150 − 45x = −90

x=2 We then substitute x = 2 into either equation to find the value of y . 10x + 5 y = 40 10 ( 2 ) + 5 y = 40 5y = 20 y= 4 The final corner point is (2, 4 ) , shown in the feasible set below.

Finally, we substitute each corner point into the objective function to determine the optimal solution.

Math 1313

Page 14 of 15

Section 2.2

Vertex of Feasible Set

Value of C = 3 x + 6 y

( 0,8)

C = 3 ( 0 ) + 6 (8 ) = 48

( 0,5)

C = 3 ( 0 ) + 6 (5 ) = 30

( 2, 4)

C = 3 ( 2) + 6 ( 4 ) = 30

The minimum is 30 and it occurs at two adjacent corner points, ( 0,5) and ( 2, 4) . Recall the following from the Fundamental Theorem of Linear Programming from Section 2.1: If the optimal solution occurs at two adjacent vertices of the feasible set, then the linear programming problem has infinitely ma...