Linear Programming 1: Maximization -Extreme/Corner Points

Linear Programming 1: Maximization -Extreme/Corner Points


Welcome to the first video in this Linear
Programming series. In this video, we will graphically solve a
basic maximization linear programming problem using the extreme or corner point approach.
What we have here is a linear programming or LP model.
The X and Y in this model are referred to as Decision Variables.
They tell us what quantity to buy, produce, sell, or transport, and so on.
The “2X + 5Y” here is referred to as the objective function which we want to maximize.
In linear programming, we either maximize or minimize the objective.
The next 2 lines are called constraints. They are restrictions that shape how you attain
the objective. Let’s call them C1 and C2 for reference
purposes. Since we’re dealing with real life objects,
we do not expect them to have negative values. So the last line here tells us that both X
and Y have to be greater or equal to 0. We call them the non-negativity constraints.
To solve this model graphically, we begin by finding points that satisfy the constraint
lines. For the first constraint, when x=0, y equals
8. And when y=0, x=16.
For the second constraint, when x=0, y equals 15.
And when y=0, x=9. Now when drawing the graph, we usually just
stay in the first quadrant here where both X and Y are positive, because of the non-negativity
constraints. So for the first constraint, we have the points
(0, 8) and (16, 0). We join those two points for the constraint
line. We do the same for constraint 2: (0, 15) and
(9, 0) and then draw the constraint line. Since these constraints are less than or equal
to constraints, they will be satisfied in the region below the lines towards the origin.
Therefore, the region satisfying both constraints simultaneously is this one here.
It is called the feasible region. That is, any point in this region is a feasible solution.
In particular, the optimal or the best solution will occur at an extreme point or corner point
of the feasible region. These are the corner points for this feasible
region. Let’s label them 1 to 4. The optimal solution to this Linear Programming
problem will occur in at least one of them. To decide which one is optimal, we will find
the coordinates of the points, plug them into the objective function and then choose the
best. At corner point 1, the coordinates are clearly
(0, 0). At point 2, (0, 8).
At point 4, (9, 0). Now those are easy to see.
For corner point 3, we can see that the coordinates are (6, 5) by eyeballing. That is, looking
at it very closely. But eyeballing is not usually the best way to go when finding the
intersection of 2 lines, especially when manually drawing the graph.
So let’s see a way to solve the 2 equations simultaneously to determine the actual coordinates.
Here are the lines for the 2 constraints. Now suppose I choose to eliminate X, note
that the coefficient of X here in C2 is 5, then I can simply multiply the first equation
by 5 to give 5X + 10 Y=80. And then subtract C2 from the new equation.
So 5X cancels 5X. 10Y minus 3Y is 7Y.
And 80 minus 45 gives 35. And on dividing both sides by 7, we have Y
=5. To now find X, we substitute Y=5 into any
of these 3 equations. Suppose we choose C1. Then we have X + 2(5)
=16. That is, X + 10=16.
X=16 -10 And X=6.
So the X, Y coordinates for extreme point 3 are indeed (6 and 5).
Next we determine the optimal solution point by finding the corner point that gives the
best value of the objective function. The objective function was to maximize 2X + 5Y. As you case see here the objective function
or its value is sometimes represented with Z.
So now, the x-y coordinates at point (1) are (0, 0).
And substituting that in the objective function gives 2(0) + 5(0) which equals 0.
At point (2) we have (0, 8), so the objective function value is 2(0) + 5(8) which equals
40. The coordinates at point 3 are (6, 5), so
Z equals 2(6) + 5(5) which equals 37. And finally at Point (4) with (9, 0), Z=2(9)+ 5(0) which gives 18. So here we have it. Point (2) provides the
highest value of the objective function. So the optimal solution occurs at point (2) and
it is X=0, and Y=8. And The corresponding objective function value
is 40. And that concludes the solution to this LP problem. Thanks for watching.

100 thoughts on “Linear Programming 1: Maximization -Extreme/Corner Points”

  1. Joshua, you are truly a very talented teacher.  You have taken anyone who has viewed this video step by step and made them understand a LP.  I  thank you for your videos.  I subscribe to them and watch them regularly .

  2. with your explanation, I was able to understand in less than 10 minutes what I could not understand in 10 hours hahha..thank you s much

  3. Very nice video and explanations. You just made the chapter Linear Programming a piece of cake. Keep making such nice videos. Thankyou very much 😊.

  4. Thank you for these videos, great explanation of Linear Programming as these videos greatly helped me passing my Business Strategy Decisions courses.

  5. thanks a lot, it really helps me to know how to scratch the graph and find the optimal choice point part for my exam. You are a saviour. all the best

  6. u r the best believe me…i was really confusing but in few min u did so much easier…thaaaaaanks aloooot…super like

  7. Timothy John Corpuz

    The best and easily digestible for LP so far. This is better than our An hour and a half session explaining LP by our professor

  8. more clear to me know> I don't know what magic my professor did in class. He's a great professor but for some reasons he just copied the final answer.

  9. omg thank you very much for uploading this! I was trying to find a good one to watch and immediately clicked ur video,keep up the good work and good luck👏

  10. Thank you so so much. Your summarization was spot on and the detail between the corner points and Zeda was the missing link (6,5), this was the learning I needed to help with understanding the basics. I was worried about missing this part and building a bad foundation for the next few weeks in class.

  11. Thank you so much for this video my professor doesn't explain linear programming well. I was so stressed since midterms are coming up but I feel more confident about doing the exam now! 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *