Typical Algebraic Linear Programming Problem
Date: 08/07/2004 at 10:21:21 From: Louise Subject: Linear Programming A manufacturing plant has a contract to supply 72 machines per week. For this, they employ x artisans and y apprentices, but can not accomodate more than 16 employees. The ratio of apprentices:artisans may not be more than 9:2, or smaller than 1:2. An artisan can manufacture 9 machines per week, and an apprentice can produce 6 machines per week. 1. Represent the information as inequalities 2. Represent the inequalities graphically, and indicate the feasible region 3. An artisan earns $600 per week and an apprentice $300. Use the graph to determine how the manager of the plant has to employ to ensure minimum expenses. 4. What are the minimum expenses per week? I know that I need to write equations for all the conditions and graph them to find the feasible region, then check the corner points, but I'm struggling. Can you help?
Date: 08/09/2004 at 12:11:51 From: Doctor Mike Subject: Re: Linear Programming Hi Louise, This technique involves finding straight lines which form the boundaries of a region of the plane containing all possible solutions. A point (x,y) inside or on the boundary will give a solution which satisfies all the requirements. The BEST solution will happen where two of those boundary lines intersect. Which two? You have to check ALL of them. The thing you want to check at each of these intersections is the total expenses, that is, the total amount to pay out to all the employees. Since there are x artisans each making $600 per week and y apprentices each making $300 per week, the expenses for a week are given by 600x + 300y Now we need to find all the possible points (x,y) to try in that expression and see which one gives the smallest result for expenses. The first step is to find the straight line equations that represent the constraints given in the problem. These equations may start out as inequalities. For example, you are told that there can not be more than 16 employees. That becomes the inequality x + y <= 16 (I use "<=" for "less than or equal to") Every ordered pair (x,y) which satisfies this INEQUALITY satisfies the requirement about the number of employees. The pair (2,7) is in that region, and the sum 2 + 7 is 9, which certainly is less than 16. Every ordered pair (x,y) which satisfies the EQUATION x + y = 16 is ON the boundary, or edge, of the region. The pair (2,14) is on that boundary line since 2 + 14 = 16. Let's look at the other requirements or constraints in the problem. Since each artisan makes 9 machines per week and each apprentice makes 6, the total number of machines produced in a week is 9x + 6y. The total number of machines must be at least 72, though they can make more than that and put the extras in inventory. So this constraint is 9x + 6y >= 72 Putting that in slope/intercept form, we get y >= -1.5x + 12 Now for what may be the hard part: the ratios. That's a fancy way of talking about fractions. Since the ratio of apprentices to artisans has to be less than 9:2, we can write y/x <= 9/2 Similarly, the ratio has to be greater than 1:2, so y/x >= 1/2 You should review what you've learned about working with inequalities to see that these mean the same as the inequalites 2y <= 9x and 2y >= x Finally, remember that x and y stand for the number of employees of a certain type, so these numbers cannot be less than zero and must be integers since you can't have negative or partial employees. We now have 4 constraints on the feasible region. Let's write them all out in original form and in slope/intercept form: x + y <= 16 y <= -x + 16 9x + 6y >= 72 y >= -1.5x + 12 2y <= 9x y <= 4.5x 2y >= x y >= 0.5x So there you have the 4 boundary lines. Get out a piece of graph paper and draw a sketch to show those boundary lines. I've made one you can look at here: As you may recall, for each inequality you will shade on one side of the boundary line or the other, depending on whether the inequality is greater than or less than. I think the easiest way to determine which side to shade is to simply try a point like (0,0) or (1,1) in the original statement and see if it makes the inequality true. If it does, shade the side that contains that point. If it doesn't, shade the other side. Once you've tested and shaded all four inequalities, you want to find the overall region that makes all four statements true. Here's my picture showing that region: So any (x,y) point that falls within that shaded region meets all four conditions of the problem. The question then becomes choosing which of those possible points gives the smallest value for the weekly expenses, which we talked about above as 600x + 300y Again, it's known that the extreme values (maximum or minimum) will occur at one of the corners of the feasible region. So we only need to test those four points to see which one gives the smallest result. Finding the coordinates of the corners involves solving a system of equations. For example, the left-most corner is at the intersection of these two lines y = 4.5x y = -1.5x + 12 By substituting the first equation into the second for y, we get 4.5x = -1.5x + 12 6x = 12 x = 2 Substituting x = 2 into the first equation yields y = 4.5(2) y = 9 Thus, the coordinates of the left corner are (2,9). Hiring 2 artisans and 9 apprentices would result in weekly expenses of $3900: 600x + 300y 600(2) + 300(9) 1200 + 2700 3900 Now you need to find and check the other three corners to see which one results in the lowest expenses. This can be a lot of work, and you need to be careful at each step to make sure you don't make calculation errors. Sometimes you can save yourself some work, though. Often in these problems, the lines intersect at clean integer points, so drawing your graph very accurately may let you find the coordinates of a corner point without having to do more algebra. Also, keep in mind what your variables represent. In this problem, they represent numbers of people, so we know that they can't be non-integer values, which may save some time. This problem is very typical of linear programming problems. It is not overly easy, but also it is not overly complicated. Go through ALL the details of this problem and you'll understand the linear programming process better. Good luck. Write back to us to say how you are doing or if you have further questions. - Doctor Mike, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.