Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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

I'm afraid it's not.  But I'm glad you asked about it because it 
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 
about it.

-Doctor Andrew, The Geometry Forum


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

Okeee. I read your message and followed your advice. This is what 
I got for my answer. 12 standard tents and 6 expedition tents. Is 
that correct? I'm not too sure about the answer.

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).

You may have used these inequalities so your answer doesn't seem 
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 
you have any questions about the Simplex method in general please 
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/