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

### Linear Programming Problem-Maximizing Tents Produced

Date: 10/6/95 at 19:10:9
From: Christina Ching
Subject: Maximizing tent profits

Hi. I really need help. Actually, I need you to see if this
problem is correct.  The problem is:

A manufacturer of a lightweight mountain tent makes a standard
model and an expedition model.  Each standard tent requires one
labor hour from the cutting department and 3 labor hours from the
assembly department. Each expedition tent requires 2 labor hours
from the cutting department and 4 labor hours from the assembly
department. The maximum labor hours available per week in the
cutting and assembly departments are 32 and  84, respectively.  In
addition, the distributor, because of demand, will not take more
than 12 expedition tents per week.  If the company makes profit
of \$50 on each standard tent and \$80 on each expedition tent, how
many tents of each type should be manufactured each week to
maximize the weekly profit?

When I did this problem, I got 28 standard tents and 0 expedition
tents.  Is that right?

Christina
ching@mvhs.fuhsd.org

Date: 10/7/95 at 1:43:54
From: Doctor Andrew
Subject: Re: Maximizing tent profits

gave me the chance to look up this kind of problem in one of my
books.  Problems where you are given a set of constraints of this
form, and an equation to maximize are called Linear Programming
Problems. (actually the equations must not have any exponents or
anything like that; that is what linear means) It turns out that
you don't have to just use blind trial and error to solve these
problems.  George Dantzig, a famous Mathematician, invented
(simultaneously with a Russian mathematician whose name I don't
remember) a method for doing this kind of problem called the
Simplex Method.

Don't worry; this isn't going to be a long math lecture.  This
method is really intuitive.  On a piece of graph paper you could
draw the region you can choose pairs from (a number for each kind
of tent) by putting one kind of tent on the x-axis and the other
on the y-axis.  Each constraint (by constrain I mean those
inequalities 1x + 3y < 32 and 2x+4y < 84 and x <= 12) would be a
line which you can only pick values on one side of.  What you'll
get are 3 intersecting lines.  Between these lines and the axes is
the area you can pick values from.  You can shade this region if
you want; I did.  All the Simplex Method says is that any points
that maximize your function (50x+80y) will be at a corner of this
region.  In this example there are 4 corners, two at the
intersections of the three lines, and the other two at the
intersection of the lines and the axes.  So you would try these
three points and see which one maximizes your function; you are
guaranteed that there are no other points that could do better.

Why the Simplex Method works isn't too difficult to understand. If
you pick a point in the middle of the shaded region, you can
obviously do better by picking a point further towards the edge
because you'll get more tents.  So we know that we need only
consider points on those lines.  Now suppose we pick a point in
the middle of one of those two lines.  We know that 8 standard
tents are worth 5 explorer tents.  The line gives us a slightly
different tradeoff: that we can have, for example, 3 standard
tents for every 1 explorer tent.  Unless these ratios (8/5 and
3/1) are equal there is definitely a direction we want to move
along that line to increase our profit; we don't want to stay in
the middle of the line.  If the ratios are equal, it doesn't
matter where we pick on the line (a corner is just as good as any
other point).  So, with this example, we can see in general that
any maximum point will be at one of the corners of the region.
This stays true if you added a third type of tent.  Instead of a
graph on paper, you would have a three-dimensional region with a
bunch of corners.  And no need to stop there.  Four tents means 4
dimensions.  I know it's hard to imagine a corner in 4 dimensions
(I certainly can't do it) but they exist and the method would work
just as well for any number of dimensions.

I hope this helps and that this little bit about the Simplex
Method didn't leave you confused.  I'd be glad to clarify anything

-Doctor Andrew, The Geometry Forum

Date: 10/8/95 at 17:41:38
From: Christina Ching
Subject: Re: Maximizing tent profits

I got for my answer. 12 standard tents and 6 expedition tents. Is

I have a question about that 1x + 3y < 32 and 2x + 4y < 84.
Shouldn't it be 1x + 3y <= 32 and 2x + 4y <= 84?

Christina
ching@mvhs.fuhsd.org

Date: 10/8/95 at 19:45:40
From: Doctor Andrew
Subject: Re: Maximizing tent profits

I'm ashamed to say that the example inequalities were wrong.  The
two I gave don't even intersect!  I added up the number of hours
on each type of tent, not the number of hours and each type of
labor.  See if you can figure out what the correct inequalities
are (you're right, they will use the <= symbol).

right.  In fact (12,6) isn't a corner with the correct
inequalities, so we know it isn't correct.  Give it another shot,
and get back to me.  Good luck!

-Doctor Andrew,  The Geometry Forum

Date: 10/8/95 at 17:41:38
From: Christina Ching
Subject: Re: Maximizing tent profits

So, the inequalities are 1x + 4y <= 32 and 2x + 3y <= 84?
But then if this is the right inequality, then there should be 0
expedition tents. But that can't be right, can it?

If the points where the lines intersect aren't whole number, such
as 6 2/3, it can't be correct because one can not make 2/3 of a
tent. Right?  Or am I confusing you?

Christina
ching@mvhs.fuhsd.org

Date: 10/9/95 at 9:16:9
From: Doctor Andrew
Subject: Re: Maximizing tent profits

>So, the inequalities are 1x + 4y <= 32 and 2x + 3y <= 84?
>But then if this is the right inequality, then there should be 0
>expedition tents. But that can't be right, can it?

It could be right, but those aren't the right inequalities.

Try this.  Let x be the number of standard tents and y be the
number of expedition tents.  So 1x+2y hours are spent on assembly
and 3x+4y on cutting.  (I assume that you actually wrote cutting
where you should have written assembly in the top paragraph.)
This will make the intersection whole numbers.  In real life they
won't always intersect at whole numbers but in this case they
don't.

-Doctor Andrew,  The Geometry Forum

Date: 10/9/95 at 18:11:46
From: Christina Ching
Subject: Re: Maximizing tent profits

Okay. I did used the right inequalities, I think. I used 1x + 2y<=
32 and 3x + 4y <=84 and y<=12 and x>=0 and y>=0.  So my answer is
12 standard tents and 10 expedition tents, right?  Hopefully this
is right, because this problem is soooo confusing!!!
Okay. I'm calm. It's just frustrating, wouldn't you agree?

Date: 10/9/95 at 20:20:34
From: Doctor Andrew
Subject: Re: Maximizing tent profits

A little, but I really like learning this stuff again.  It's been
a while since I last saw the Simplex method, but it's fun to pull
it out of the hat again.

Maybe you could tell me what the corners are and the profit at
each one. You earned 50(12)+80(10)=600+800=\$1400.  That's pretty
good but I think I've got a corner that's even better, and it
doesn't look like your answer is a corner.  (12,10) is on the line
1x+2y=32 but its not on y=12,x=0,y=0 or 3x+4y=84.  A corner has to
be on at least two lines.  Keep at it, you're almost there.  If
send them.  I think it's really a great thing to understand.

-Doctor Andrew,  The Geometry Forum

Date: 10/10/95 at 11:41:36
From: Christina Ching
Subject: Re: Maximizing tent profits

Okay. I made a little mistake.  Wait, first of all, the points
(12,10) are on two lines.  It's on y<=12 and on 1x + 2y <=32.
There can't be another point higher than that or better than that
because then the inequality 1x + 2y <= 32 wouldn't have to be
there, y'know?

Date: 10/10/95 at 20:20:34
From: Doctor Andrew
Subject: Re: Maximizing tent profits

The point (12,10) is on X<=12, but not y<=12.  But even if it was
a corner, you should still check the other corners to make sure
it's the best one.

-Doctor Andrew,  The Geometry Forum

Date: 10/10/95 at 22:2:51
From: Christina Ching
Subject: Re: Maximizing tent profits

Okay. Don't I feel stupid now. The inequalities I used were:
1x + 2y <= 32
3x + 4y <= 84
y <= 12
x => 0
y => 0

So the corners I got were:
(0,0)  (0,12)  (8,12)  (10,6)  (28,0)

So (0,0) would give me \$0
(0,12) would give me \$960
(8,12) would give me \$1360
(10,6) would give me \$980
(28,0) would give me \$1400>

That would mean that to maximize the profit, they would have to
make 28 standard tents and 0 expedition tents. But I don't think
that you can have 0 tents, can you?

Christina
ching@mvhs.fuhsd.org

Date: 10/10/95 at 22:40:21
From: Doctor Andrew
Subject: Re: Maximizing tent profits

You can.  I'll bet that you could come up with an example where
you would, but I claim that there is a point better than \$1400. I
suggest you look at the corner I marked above.  Don't get too
frustrated; you're almost there!

-Doctor Andrew,  The Geometry Forum

Date: 10/11/95 at 18:13:7
From: Christina Ching
Subject: Re: Maximizing tent profits

Hey!!!!!! I got it!!!! It's (20,6), right? Woo hoo!!!! Aren't you
proud of me now? I feel so relieved.......and highly intelligent
at the moment.  But now the feeling has passed. But I'm happy that
I got it now. Hip hip hurray. But, of course, I couldn't have done
it without you. THANK YOU!!!!!!!

Christina
ching@mvhs.fuhsd.org

Associated Topics:
High School Linear 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