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.