Linear Programming 1: Maximization -Extreme/Corner Points

Linear Programming 1: Maximization -Extreme/Corner Points

Articles , , , , , , , , , , , , 36 Comments



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.

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

Leave a Reply

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