In this video, I'll talk about the graphical meaning of the simplex method in solving a
LP problem.
For a maximization LP problem with two or three variables, we can follow these 4 steps
to search for the optimal solution.
Step 1: Draw the feasible region.
Step 2: Find an extreme point to the LP problem and calculate the z-value.
We talked about in a previous video that an extreme point corresponds to a BFS.
Step 3: Check the current extreme point's adjacent points (or adjacent BFSs) and their
z-values.
Step 4: If no adjacent point has a larger z-value than the current extreme point, then
the current extreme point is an optimal solution.
Otherwise, move from the current extreme point to the adjacent point with the largest z-value
and return to step 3.
This procedure is for a maximization problem.
If you have a minimization problem, you need to change step 4 so that if no adjacent point
has a smaller z-value than the current extreme point, then the current extreme point is an
optimal solution.
Otherwise, move from the current extreme point to the adjacent point with the smallest z-value
and return to step 3.
Alternatively, you can also change the minimization problem to a maximization problem by maximining
the opposite of the objective function.
Now let me show you an example in two dimensional space.
For this problem with two variables, the feasible region is marked by the shaded area.
We have a total of 4 extreme points (or BFSs), A, B, D, and F. Note that point C and point
E are not extreme points or BFSs.
Suppose the current extreme point is point A. Now let's check its z value.
We plug these values into the objective function.
ZA=3*0+2*0, which is equal to 0.
Now let's check point A's adjacent extreme points B and F. ZB=3*4.5+2*0, which is 13.5.
ZF=3*0+2*4.5, which is 9.
ZB is larger than both ZA and ZF.
So, we move to point B and it is the current extreme point.
Now let's check point B's adjacent extreme points A and D.
We already know ZA=0.
ZD= 3*3+2*3, which is 15.
ZD is larger than both ZA and ZB.
So, we move to point D and it is the current extreme point.
Now let's check point D's adjacent extreme points B and F.
We already know ZB=13.5 and ZF=9.
So, ZD is still the largest.
Therefore, we stop and point D is the optimal solution.
So we have gone through the path A, B, and D.
Now let me show you an example in three dimensional space.
For this problem with three variables, the feasible region is bounded by the triangular
prism.
We have a total of 6 extreme points (or BFSs), A, B, C, D, E, F.
Suppose the current extreme point is point A. Now let's check its z value.
We plug these values into the objective function.
ZA=0+2*0+3*0 is still 0.
Now let's check point A's adjacent extreme points B, C, and D.
We find that ZB=4, ZC=8, and ZD=15.
ZD is the largest.
So, we move to point D and it is the current extreme point.
Now let's check point D's adjacent extreme points A, E, and F. ZA=0, ZE=19, and ZF=23.
ZF is the largest.
So, we move to point F and it is the current extreme point.
Now let's check point F's adjacent extreme points C, D, and E. ZC=8, ZD=15, and ZE=19.
So, ZF is still the largest.
Therefore, we stop and point F is the optimal solution.
So we have gone through the path A, D, and F.
Okay, that is the graphical explanation of the simplex method for solving a LP problem.
Thanks for watching.