Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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/
```
Associated Topics:
High School Basic Algebra

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search