Welcome.
In this tutorial, I will solve this LP problem using graphical approach
and use it to explain the special case of alternative or multiple optimal solutions.
Let’s begin by finding points for drawing the constraint lines.
For the first constraint line, when x = 0, y is 60, and when y = 0, x is 120.
For the second, when x is 0, y is 60, and when y = 0, x is also 60.
For the third, when x is 0, y is also 0.
So to find another point, we can rewrite the inequality as
x greater or equal to 2y.
We can then pick a reasonable value for either x or y and calculate the other.
For instance, if y is 50, x is 2 times 50 which gives 100.
Let’s now draw the graph.
Here are the constraints along with (x,y) coordinate pairs obtained earlier.
Since the highest x-value we have here is 120, and the highest y is 60, we can go
up to 120 on the x-axis, and up to 60 on the y-axis.
For the first constraint, we have (0, 60) and (120,0).
We join the points for the constraint line.
For the second, we have (0, 60) and (60, 0), and that’s the line.
For the third constraint, we have a point at (0,0) and another at (100, 50) and that
that’s the line in gray.
Now, the first constraint is a “less than” constraint, satisfied below the line in the
direction of the origin here.
The second is a “greater than” constraint, satisfied above the line away from the origin.
The third constraint however is not as innocent as it looks because it has a negative sign.
You should exercise extra caution when determining the direction satisfying a constraint with
negative coefficient.
I will suggest choosing a test point on either side of the line and then testing to see if
that point satisfies the given constraint.
Let’s take this point (0, 30) for example.
Putting it in the left side of the constraint gives -60 which is not greater than zero.
In other words, the constraint is not satisfied in that direction.
Just to confirm that it is satisfied in the opposite direction, let’s try this point
(40, 0).
Substituting (40, 0) gives 40 on the left side, which is clearly greater than 0.
So the third constraint is satisfied in this direction here.
By observing the directions of the arrows,
we see that the region satisfying all three constraints simultaneously is this one here
…which we call the Feasible Region.
Now the LP concept states that the optimal solution will occur at one of these four corners
or extreme points of the feasible region.
It is easy to investigate all 4 extreme points here as they all fall on grids but I’m just
going to use the objective function or isoprofit line (profit, since this is a maximization
problem).
The objective function is to maximize Z = 5X + 10Y
I can create an instance of the line by simply multiplying 5 and 10 here, which gives 50, and drawing the
line 5x + 10y = 50.
But that won’t really display well on this graph here
so I can use multiples of 50 like 100 or 200.
Let’s just use 100.
So for the profit line, when x = 0, y = 10, and when y = 0, x = 20.
Thus we have an instance of the profit line here.
We now move the profit line increasingly until it touches the most extreme or corner point
of the feasible region.
But here we have it touching 2 corners simultaneously and lying entirely on a constraint line.
These two corners are candidates for the optimal solution.
The coordinates at the top here are easily identified to be x = 60 and y = 30.
And plugging it into the objective function gives Z = 600.
The coordinates at the corner down here are x = 120 and y = 0.
And that also gives Z = 600.
In other words, we have alternative or multiple optimal solutions.
This essentially happens when a constraint touching an optimal solution point, that is
a binding constraint, is parallel to the objective function line.
Note that the left side of the first constraint is 1x + 2y.
And when you multiply that by 5, you obtain the objective function.
Note also that not only these 2 corners are optimal solutions.
Every point on the line between them is also optimal and will give a Z value of 600.
For example, the value of Z at this point (80, 20) is 600,
and the Z value at (100, 10) here is also 600.
And that’s it for this video.
Thanks for watching.