Word Lesson: Linear Programming

By M Ransom

In order to solve problems which require application of linear programming, a graphical approach, it is necessary to

know how to find points of intersection for lines
know how to graph linear functions
know how to apply the graphical approach to linear programming

A typical problem requiring the method of linear programming, a graphical approach, provides linear constraints and an objective function, which is to be either maximized or minimized. We will refer for graphing purposes to a graphing calculator. An example of this type of problem is the following:

Bob builds tool sheds. He uses 10 sheets of dry wall and 15 studs for a small shed and 15 sheets of dry wall and 45 studs for a large shed. He has available 60 sheets of dry wall and 135 studs. If Bob makes

390 profit on a small shed and

520 on a large shed, how many of each type of building should Bob build to maximize his profit?

Let s represent the number of small sheds and represent the number of large sheds. Then the constraints upon this problem are the following:

The objective profit function is

P(s, ) = 390s + 520

We solve 10s + 15 = 60 and 15s + 45 = 135 for and enter these into the calculator under the Y= menu, shading below these lines to see the region defined by the constraints.

= (-2/3) s + 4
= (-1/3) s + 3

We graph in the first quadrant since both s and are greater than or equal to zero. The screens from the calculator are shown below.

We maximize the objective function P(s, ) = 390s + 520 by evaluating it at the vertices: (6,0), (3,2), and (0,3).

We have:

The final equation shows us that Bob can maximize his profit at $2340 if he can sell 6 small sheds and not make any large sheds.

Notice that in order to maximize the objective function, the given information must be converted into inequalities, graphed, and the objective function must be evaluated at the vertices of the polygonal region graphed.

Notice also that the minimum value would be obtained at the vertex (0, 0) which we did not previously evaluate since it would give a value of $0 for the profit.

Remember: Both the minimum and maximum values of the objective function are found at the vertices.

Directions and/or Common Information:

No audio files were recorded for this example.

A company makes a product in two different factories. At factory X it takes 30 hours to produce the product and at factory Y it takes 20 hours. The costs of producing these items are $50 at factory X and$ 60 at factory Y. The company’s labor force can provide 6000 hours of labor each week and resources are $12,000 each week. How should the company allocate its labor and resources to maximize the number of products produced?

Directions and/or Common Information:

No audio files were recorded for this set of examples.

Josie is on a diet. Daily, she needs three dietary supplements, A, B and C as follows: at least 16 units of A, 5 units of B, and 20 units of C. These can be found in either of two marketed products Squabb I and Squabb II. The Squabb I pill cost $10 and the Squabb II pill costs$ 20. How many of each pill should Josie buy to satisfy her dietary needs and at the same time minimize costs?

minimum cost $63; 1.38 of Squabb I and 2.46 of Squabb II </li> <li>minimum cost$ 70; 3 of Squabb I and 2 of Squabb II

An agriculture company has 80 tons of type I fertilizer and 120 tons of type II fertilizer. The company mixes these fertilizers into two products. Product X requires 2 parts of type I and 1 part of type II fertilizers. Product Y requires 1 part of type I and 3 parts of type II fertilizers. If each product sells for $2000, what is the maximum revenue and how many of each product should be made and sold to maximize revenue?

max revenue is $112,000; 24 product X and 32 product Y </li> <li>max revenue is$ 120,000; 60 product X and 0 product Y

To summarize, the linear programming method graphical approach is applied to an objective function, given constraint conditions. The maximum (and minimum) values of this function are found at the vertices of the region defined by the constraints. The most difficult part of the problem is to organize the constraints properly into linear inequalities. This graphical approach can be used if there are only two variables. Situations involving more variables require other methods. One commonly used method is called the “simplex method” and can be found in some texts on Finite Mathematics as well as Matrix Algebra and Operations Research.