Linear Programming is a mathematical method used to find solutions to real-world problems. It is based on graphing constraints and finding where they intersect. These intersections bound a possible set of solutions called the feasible region. Then, based on this region we find the point(s) that maximize or minimize the objective function.
One nice part of Linear Programming is that we will only be working in Quadrant I. This is due to the fact that we do not allow the possibility of negative values.
For example, linear programming is often used in farming. A farmer uses his land to grow more than one crop. Each crop produces different amounts and sells for different prices. Therefore, a farmer must decide how much of each crop to plant in order to maximize his profits. Thus, he will not plant crops to lose money, so that takes away one possible set of negative values, and he can't plant negative amounts of crops, the least he could plant is zero, so now we do not have the possibility of any negative values. Therefore, we must work in Quadrant I.
The Corner Point Principle states that the min or max will occur at one of the vertices of the feasible region. So, after we have found the feasible region, we need only test the corners to find where the min or max occurs.
The constraints that are used to make the edges of the feasible region are some linear inequalities. We learned how to graph these in topic 4. So, any point in the feasible region will make all of the constraints true. What we then want is to find the min or max depending on the situation. For example, if the function we are looking at deals with profits, we would find the max, but if the function that we are looking at deals with costs, then we would find the min.
Example 1: A farmer plans to use his fields to plant corn and wheat.
Corn yields 113.5 bushels per acre and sells for $3.15 a bushel.
Wheat yields 35.8 bushels per acre and sells for $4.45 a bushel.
His constraints are:
1. no more than 120 acres of corn and wheat.
2. at least 20 acres and no more than 80 acres of corn.
3. at least 30 acres of wheat.
Find out how many acres of corn and wheat must be planted in order to maximize revenue.
First: We must define our variables, x and y. We choose x and y because that way we know what values will be plotted along the x and y axes.
Let x = corn and y = wheat
This means our initial graph will look like:
Now, we must use our contraints to write inequalities.
1. no more than 120 acres of corn and wheat. This means that corn + wheat must be less than or equal to 120. Giving us the inequality: x + y < 120. (Remember that it should be less than or equal to but our technology only uses the less than. So, this is in a form ready for our computer or TI-83 to graph)
2. at least 20 acres and no more than 80 acres of corn. This means that corn must be between 20 and 80. Written as an inequality, this gives us: 20 < x < 80.
3. at least 30 acres of wheat. This means that wheat must be greater than or equal to 30. Written as an inequality, this gives us: y > 30.
Now, we graph these inequalities on the same set of axes in order to find our feasible region.
The trapezoidal area where the three colors intersect is the feasible region. If we zoom in on that region, it looks like:
.
Now, we ned a function to maximize. For this problem, it is a revenue function. So, where does his revenue come from. For corn, it is:
(number of bushels of corn) * (price per bushel) * (number of acres of corn)
Substituting what we know, the expression becomes: (113.5)(3.15)(x)
Next, do the same thing for wheat.
(number of bushels of wheat) * (price per bushel) * (number of acres of wheat)
Substituting what we know, the expression becomes: (35.8)(4.45)(y)
Total Revenue is found by adding the revenue from corn and the revenue from wheat. This yields the objective function:
Total Revenue = (113.5)(3.15)(x) + (35.8)(4.45)(y)
Finally, now that we have our objective function we need to find the maximum. As stated earlier, the maximum happens at one of the corner points. Here, our feasible region is a trapezoid, so there are four corner points. There are several ways to find these, the easiest of which is to use the graphing calculator to find the corner points.
Now, all that we have left to do is to substitute the values of the corner points into our objective function and find the largest value. To do this, one usually makes a table.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Thus, the max occurs at the corner point (80, 40). This means that the farmer should plant 80 acres of corn and 40 acres of wheat.
Objective function: S = 2x + 3y
Constraints:
x > 0
y > 0
5x + y > 20
x + y > 12
x + 2y > 16