Linear ProgrammingDate: 04/10/2003 at 18:51:15 From: Mike Subject: Linear Programming An office manager is purchasing new file cabinets. The office has 60 square feet of floor space available, and $600 to spend. Cabinet A requires 3 square feet of floor space, holds 12 cubic feet, and costs $75. Cabinet B requires 6 square feet of floor space, holds 18 cubic feet, and costs $50. How many of each kind of cabinet should the manager buy to maximize the storage capacity? I don't have any idea how to do this problem. Can you help? Date: 04/11/2003 at 00:26:23 From: Doctor Annie Subject: Re: Linear Programming Hi Mike - Thanks for writing to Dr. Math. This problem can be solved by using a method known as linear programming. It's a pretty neat technique - let's take a look. Obviously the manager has lots of possible ways to buy cabinets. For example, since cabinet B uses 6 square feet of floor space and he has 60 square feet to fill, he could just buy 10 of cabinet B for $500. Or, since cabinet A costs $75, he could spend all $600 buying 8 of cabinet A. He could also buy some of each type, as long as his total purchase doesn't cost more than $600 or cover more than 60 square feet of floor space. So how does he get the most possible storage space in his new cabinets? I'm going to start by making a table that shows all the information we are given about cabinets A and B: Floor space Storage (sq ft) Price (cu ft) ---------------------------------------- | A | 3 | 75 | 12 | ---------------------------------------- | B | 6 | 50 | 18 | ---------------------------------------- Let's define variables. Since we are solving for how many of each kind of cabinet to buy, we'll just use A and B: Let A = the number of A cabinets bought B = the number of B cabinets bought Now we can modify the chart a little bit. Since each A cabinet uses 3 square feet of floor space, buying 'A' of them will require 3A square feet of floor space. The same thinking applies to the whole chart: Floor space Storage (sq ft) Price (cu ft) ----------------------------------------------- | A | 3A | 75A | 12A | ----------------------------------------------- | B | 6B | 50B | 18B | ----------------------------------------------- | Totals | 3A + 6B | 75A + 50B | 12A + 18B | ----------------------------------------------- The 60 square feet and $600 are called "constraints" - however many of each cabinet he buys, he can't exceed either figure. So we know that each total must be less than or equal to the constraint: 3A + 6B <= 60 75A + 50B <= 600 Notice that these are both linear inequalities, and we can graph them. Let's start with the first one, which says the total floor space used by the new cabinets can be less than or up to 60 square feet, but not more than that. Solving for B, we get: 3A + 6B <= 60 6B <= -3A + 60 B <= -1/2 A + 10 Graphing, using A as the horizontal axis and B as the vertical, we get: The line itself contains points such as (10,5) where the combination of A and B cabinets totals exactly 60 square feet. (Remember the number for the horizontal axis records the number of A cabinets, and the vertical records the number of B cabinets, so (10,5) means buying 10 of cabinet A and 5 of cabinet B.) The yellow region contains points such as (5,2) where the combination of A and B cabinets totals less than 60 square feet. So any point on the line or in the yellow region meets the constraint that the total square feet of floor space must be 60 or less. I've cut the region off at the axes since you can't have a negative number of file cabinets. Doing the same thing with the $600 constraint, we'll get a graph of all possible points where the total money spent on the cabinets is $600 or less: 75A + 50B <= 600 50B <= -75A + 600 B <= -3/2 A + 12 Now we're getting to the fun part! Since we can't exceed either 60 square feet or $600, we're really interested in any points that work for both graphs above. So let's put the two graphs on the same axes and see where they overlap: The green region is the part that works for both of the constraints, so any point in there (such as (4,2)) is a possible combination of cabinets the office manager could buy. We call that area the "feasible region". But there are still a lot of possible points in there! This is where the really cool part comes in. It has been proven that the answer that will provide the maximum will be one of the points found at a vertex of the feasible region. In this case there are four vertices: (A,B) = (0,0) (8,0) (2,9) (0,10) So one of those four will give us the maximum storage capacity. Remember from our second chart that the total storage capacity is expressed as 12A + 18B since each A cabinet holds 12 cubic feet and each B holds 18. For our final step, we need to evaluate 12A + 18B for each vertex and see which gives the largest result: (A,B) 12A + 18B ----- --------- (0,0) 12(0) + 18(0) = 0 + 0 = 0 (8,0) 12(8) + 18(0) = 96 + 0 = 96 (2,9) 12(2) + 18(9) = 24 + 162 = 186 (0,10) 12(0) + 18(10)= 0 + 180 = 180 By a nose, buying 2 of the A cabinets and 9 of the B cabinets will give the greatest possible storage capacity of 186 cubic feet. And that's linear programming! The basic steps are to write inequalities based on the information in the problem, using the constraints. Graph all the inequalities on one graph, and find the region that makes all of them true. That's your feasible region. Finally, check each vertex of the feasible region in whatever expression you are trying to maximize to see which gives the largest result. Write back if you have any further questions on this process, and good luck! - Doctor Annie, The Math Forum http://mathforum.org/dr.math/ Date: 04/14/2003 at 09:30:24 From: Mike Subject: Thank you (Linear Programming) Thanks, Dr. Annie! That really made sense the way you explained it. I think I understand linear programming now. |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/