In this video, I'll talk about how to solve the linear programming problems with two variables
using the graphical method.
For a maximization problem, an optimal solution is a point in the feasible region with the
largest objective function value.
If it's a minimization problem, an optimal solution is a point in the feasible region
with the smallest objective function value.
For a LP problem with two variables, we can solve it graphically by following these steps.
Step 1.
Find the feasible region.
I already introduced how to do that in a previous video.
Step 2.
Find the slope s of the objective function.
Step 3.
Draw a line with slope s that intersects with the feasible region.
Step 4.
Move the line in parallel towards the direction that increases the objective function for
a maximization problem.
If it is a minimization problem, we need to move the line towards the direction that decreases
the objective function.
Step 5.
The last intersection point or points before leaving the feasible region will be the optimal
solution or solutions.
For example, this is a maximization problem with two variables.
The feasible region is the shaded area.
To find the slope of the objective function, we re-write it and x2 = z/2-3x1/2, so the
slope is -3/2.
We draw any line that has a slope s and intersects with the feasible region.
Now let's find which direction to move the line.
If we increase x1, what happens to z?
It will increase.
If we increase x2, what happens to z?
It will also increase.
So in general we should move towards the top-right corner.
Now let's move this line in parallel towards the top-right corner, and we find that the
last intersection before we leave the feasible region is this point.
After this point, the line will no longer intersect with the feasible region.
It is the intersection point of two constraints.
2x1+x2=9 and x1+2x2=9.
The point is (3, 3).
Let's plug these values into the objective function, z*=15.
This is the unique optimal solution to this problem.
If we modify the objective function, and change this coefficient from 3 to 4, then we can
find in this figure that the feasible region will not change.
But the slope will be changed from -3/2 to -2.
It is the same as the slope of the first constraint C1.
Now let's move this line in parallel towards the top-right corner, and we find that the
last intersection before we leave the feasible region is this line segment.
We will have an infinite number of optimal solutions between point (3,3) and point (4.5,0).
z*=18.
In this example, the constraints are changed so they both have a greater than or equal
to sign.
So, the feasible region is changed to this unbounded area.
Now let's move this line in parallel towards the top-right corner, and we find that no
matter how far we move the line, we will always intersect with the feasible region.
That means, the z value can be arbitrarily large.
So the problem is unbounded.
In this example, the first constraint is still a less than or equal to, but the RHS is changed
to 4.
The second constraint is greater than or equal to constraint.
So, the feasible region of the first constraint C1 is below this line.
And the feasible region of the second constraint C2 is above this line.
However, there is no intersection, and the feasible region of the problem is an empty
set.
So the problem is infeasible.
That means, there is no optimal solution.
Okay, that is how to solve different cases of linear programming problems using the graphical
method.
Thanks for watching.