Linear ProgrammingDate: 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 little more information about linear programming. 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/