Hello, this is Mr. T with a tutorial on linear programming. The purpose of linear programming is to optimize a function. Optimize means to either maximize or minimize that particular function. In this case though, that function is subject to a set of constraints that limit the particular values for x and y that we can choose.
These constraints are usually provided as a system of inequalities. In the last lesson we... learned how to graph systems of inequalities to find the solution space.
Linear programming was invented during the World War II by mathematicians to support the war effort and they came up with methods to optimize the amount of cargo that they could load on ships and planes. This technique was kept secret during the war because we didn't want that to get to our enemies. After the war it was published and has been adopted by many large corporations for managing their resources.
When we graph the system of inequalities that form the constraints, they form usually a closed-in space, which I've shown in the diagram here. Over here we've shown the diagram. So we have, we had four inequalities here, a vertical line, a horizontal line, and these two lines here. And they formed a solution space which is called the feasible region. So when we are trying to optimize...
the objective function, we could pick any point in the feasible region as well as the points along the boundaries. As you can see, if we wanted to check all the points in the feasible region, it would be impossible because there's an infinite number of points. However, the concept of linear programming says that the maximum and minimum values for the objective function will occur at the corners or the vertices. So we only have to check a point.
We only have to check points at each of the corners of the vertices. So we can find the x and y coordinates of the vertices and substitute those into our objective function and decide which one provides the max and the min. So we have here an example. We have an objective function. At this point we don't know what that stands for.
Maybe it's profit or something. And the function is determined to be 5x minus 3y. there was a system of equation inequalities that were graphed to form this feasible region, all the possible solutions, and we're supposed to find the optimum values. So remember, our optimum values will be at the the vertices. So this vertices the coordinates are.
This vertices the coordinates are. At this vertices our coordinates are. And at this vertices our coordinates are.
The easiest way is to form a table where we input our x. our y values and we then compute our objective function for each of those. So if we fill in our table we have 0, 2 3, 4 going around the diagram, 6 2 and 0, negative 2. So now we can calculate p by substituting in.
So here we have 5 times 0 minus 3 times 2, we get negative 6. Here we have 5 times 3 minus 3 times 4. That's 15 minus 12. We get 3. Here we have 5 times 6 minus 3. times 2, 30 minus 6 is 24, and finally 5 times 0 minus 3 times negative 2 is a positive 6. Now we can compare our p-values and find the max and min. Here we see we have a minimum and the maximum. So for our function we have the minimum is negative 6 at the point 0,2 and maximum is 24 at 6,2.
Hello, in our next linear programming example we will... We'll work the problem more completely, meaning we'll take a word problem, we will determine from the word problem our objective function and our constraints. graph our constraints to find our feasibility region and our vertices and Then by making the table we'll figure out the answer to our problem here So we have a farmer that has some some land to plant He's got 240 acres and he's decided that he wants to plant corn and or oats based on the prices that he can achieve.
He knows he can make $40 of profit per acre for his corn and $30 of acre for oats. And he's trying to figure out how much to plant. Now if we didn't have any other constraints, obviously he would want to plant all corn. But the corn takes more labor to harvest than the oats. It takes two hours of labor for each acre for the corn and one acre for the oats.
And he only has 320 hours to spend on labor. So what mix of corn and oats should he plant to maximize his profit? So on a linear programming problem, we need an objective function.
That's what we're going to optimize. So in this case, our objective is to... maximize profit.
So our objective is profit. So we need an equation for profit. Let's here decide here we're going to let x be our number of acres of corn and y will be our number of acres. Of oats. So the profit, we get $40 of profit per acre for corn, so 40x for our profit, 40 times the number of acres of corn, and then we get $30 of profit for the oats, which is our y value.
So this is our objective function. Now we need to figure out our constraints. Well, obviously we can't have negative acres of corn or oats.
So those both have to be positive, meaning when we do our graph we're only going to be in our first quadrant. Now we have a constraint on how much land we can plant. So acres of corn is x and we add to that our acres of oats and that has to be less than or equal to our land, so 240 acres. And then we're also constrained on labor.
So we've spent two hours per acre of corn, so 2x is the number of hours we'll spend for the corn, and one hour per acre of oats, so y, and that has to be less than or equal to 320. So now we have our inequalities, our constraints, so we can search for our feasible region, and we have our objective function. So our next step will be to graph the constraints. So I've rewritten those on the page here. So these two constraints are going to put us in the first quadrant here.
So when I set up my x and y axis, I only am showing the first quadrant here. I have x, which is corn on our y x axis, and we have oats here for our y axis. And so I've implicitly have those two constraints. So let's do this constraint in blue.
This is in standard form, so we can find our x and y intercepts. So our x intercept for this constraint would be 240, right here. And our y intercept is also 240. So we can draw a line connecting those.
And we're just going to go here for the first quadrant because we know where from our other constraints were not in any of the other quadrants. My line's off a little bit. And here our y-intercept, which is OATS, would be 320. Let's do that one in red.
And our x, if we divide by, hide the y and divide by 2, we get 160. That's here. Let's draw that line. And now we have our feasible region is in here is our feasible region.
So just highlight this here. The pen is pretty fat here so I can't get too close to the lines. So that's our feasible region. Let's put an F in there for feasible region. And remember linear programming says that if we find the corners or the vertices of our feasible region Those are the points that we need to examine to find our solution for our optimization problem.
So from the graph we know that we have a point here of. We have the point here with x of 160 and y of 0. And we have the point here of 240 and... I'm sorry, I put that in the wrong place. So on this one, x is 0 and y is 240. And now we need to find this one. Now we could probably guess maybe this was going to intersect here, but on these, to find the exact intersection, we're going to treat our two constraints as...
equations, the boundary lines, so we have x plus y equals 240, and we have 2x plus y equals 320, and to find the intersection, that's solving this system of equations. I'm going to use linear combinations, so if I multiply my top equation by negative 1, so multiply by negative all the way across, I can add the two equations together and my y's are canceling out. out so I have X equals and here I have 80. Putting back into my original first equation here I get 80 plus Y equals 240 and I can subtract my 80 and I get y equals 160. So this intersection here is 80, 160. So let's put that over in our table here. So here I make zero profit. Here I'm going to make 40 times 160, which is 6400. Here I'm going to make 240 times 30, so we've got two zeros here.
That's going to be 7200. And here we can multiply. We've got 80 times 40, which is 3200. And now we have 160 times 30, which is 4800. And that adds up to be $8,000. And we are looking for maximum profit, so our maximum profit happens here.
So our answer of our question is we want to plant 80 acres of corn and 160 acres of oats. And that will yield us our maximum profit. So, and I guess that's it.