Linear Programming

Date: 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.