Linear Programming

Date: 01/30/97 at 12:26:53
From: Justin Anderson
Subject: Linear Programming  (Adv. Algebra)

A nutition center sells health food to mountain climbing teams.  The 
Trailblazer mix package contains one pound of corn cereal mixed with 
four pounds of wheat cereal and sells for $9.75.  The Frontier mix 
package contains two pounds of corn cereal mixed with three pounds of 
wheat cereal and sells for $9.50.  The center has 60 pounds of corn 
cereal and 120 pounds of wheat cereal available.  How many packages of 
each mix should the center sell to maximize its income?

Find the inequalities and vertices.

I have spent a lot of time on this, asked three adults for help, 
referred to my book, and still can't solve this problem.  This has 
been very frustrating to everyone who has looked at it.  Can you help?

Date: 01/31/97 at 15:19:37
From: Doctor Daniel
Subject: Re: Linear Programming  (Adv. Algebra)

Hi Justin,

I'm really sorry you've been having so much trouble solving your 
problem. Fortunately, I think you've come to the right place!  Your 
problem isn't easy, but it is pretty straightforward once you have the 
right ideas.

The problem you've asked is a linear programming problem.  This isn't
programming in the sense of C or Java.  Rather, you're being asked to 
find a program, which is values for a bunch of variables, where the 
values from your program maximize the income of the center.  The 
"linear" in the description of the problem is because the amount of 
money the store gets from selling the product is a linear function; if 
it sells 2 units of Trailblazer, it gets twice as much money than if 
it sells 1 unit.

I'll try to talk you through solving this problem and then I'll give a 
little more information about linear programming.

First: What are the variables of this problem?  What are the aspects 
of the situation which we can control?  Well, there are only two: how 
much Trailblazer we make, and how much Frontier we make.  So we'll 
have two variables which we control:

   f = # of units of Frontier produced
   t = # of units of Trailblazer produced.

Second: What are we trying to maximize?  We're trying to maximize the 
income of the store, which is $9.75 per unit of Trailblazer and $9.50 
per unit of Frontier.  So we want to maximize:

   9.75 t + 9.5 f

Last: What are the constraints we have to work within?  This can be 
the most confusing part of the formulation of a linear program. 
Basically, the question is to find which resources are limited, or if 
some of our variables maybe need to always be more than zero.  

Here, it's clear: We can't make less than zero of either product, and 
we need to not use more corn or wheat than we have.  The first of 
these is easy; we just know that:

   t >= 0
   f >= 0

But the second one isn't so easy.  Or is it?  The amount of corn we 
use equals one pound per unit of Trailblazer, and 2 pounds per unit of 
Frontier, and the total is less than 60.  So this gives this 
inequality:

   t + 2f <= 60

I'll let you look at it, but it's not hard to see that the constraint 
for wheat is:

   4t + 3f <= 120

Whew!  We've finished stating our problem in formal math notation.  (I 
bet you're thrilled.)  Here it is:

Maximize 9.5f + 9.75t, subject to the constraints:

        t >= 0
        f >= 0
   t + 2f <= 60
  4t + 3f <= 120.

It turns out that if you plot these inequalities in the plane, they'll
define a closed region, which is shaped kind of like a squashed 
trapezoid. Inside this region, the problem is "feasible," which means 
that if you made as many of f or t as the variables said, you wouldn't 
need more resources than you had, or make a negative number of one of 
the products.  Outside this region, the problem is infeasible; one of 
the essential constraints is violated.

Here's a plot of this information:

   

It's a useful theorem of linear programming that the "objective 
function" (what we're maximizing) will always either be infinite, or 
reach its maximum at one of the vertices of the feasible region.  
(There's actually a third possibility: the problem could be 
infeasible, meaning that its feasible region is empty.  But this 
problem isn't like that.)  Since the feasible region is closed, it's 
also not infinite.  So to finish the problem, we have to compute the 
vertices of the region, compute the objective function at all of them, 
and pick the best.  

First, trivially, f = 0, t = 0 is a corner.  The objective function 
there is 0.
Also, f = 0, t = 30 is a corner. Then we get $9.75*30 = $292.50.
Also, t = 0, f = 30 is a corner. Then we get $9.50*30 = $285.  

(I could see all of those intersections just by looking at them.)

Lastly, t = 12, f = 24 is a corner; that's the intersection of the 
corn constraint with the wheat constraint.  (I cheated to find this 
one; you might just solve the system of equations like you probably 
learned in algebra class.) Anyhow, there, we get 

   $9.75*12 + $9.50*24 = $345.  

That's all the corners, so we see that the best answer is this one; we
produce 12 units of Trailblazer and 24 units of Frontier.  This gives 
a total profit of $345.  It also does use up all of the corn and all 
of the wheat.

I think it's good to stop now, look back, and consider.  To solve a 
linear program, we:

1) Identify the "decision variables."  Here, they were the amount of 
   each product to produce.

2) Figure out the "objective function" in terms of the decision 
   variables. For us, it was the formula for the profit which we 
   wanted to maximize.

3) Compute the inequalities that represent constraints of the problem.  
   For us, it was the bounded resources, plus the requirement that we 
   make nonnegative amounts of each product.

Then, if the problem is 2-dimensional, you plot it, look at the 
corners of the feasible region, compute the objective function at all 
of them, and return the corner giving the biggest one.

Linear programming is REALLY important, actually.  Not in the case of 
little problems with only a couple variables, but in much bigger 
problems.  Why?  It's a good, simple model for problems with bounded 
resources, fairly simple relationships between the uses of the 
resources, and, moreover, there are fairly easy ways to solve it 
(which don't involve looking at all the corners of the feasible 
region).  So I wish you much luck with it, Justin!
 
-Doctor Daniel,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/