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 email@example.com
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 firstname.lastname@example.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 email@example.com
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 firstname.lastname@example.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 email@example.com
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.