In this video, I'll talk about how to find basic feasible solutions to a LP problem in
the standard form. The BFSs will be used later in the simplex method.
Let's consider a LP problem in the standard form that contains n variables and m constraints.
We assume n ≥ m. We can get a basic solution by setting n – m
variables equal to 0 and solving for the remaining m variables. The n-m variables are called
non-basic variables (or NBVs), and the remaining m variables are called basic variables (or
BVs). The total number of basic solutions is equal
to n choose m or n choose n-m, which is n factorial divided by m factorial times (n-m)
factorial. Not every basic solution is feasible. If all
the variables are nonnegative in a basic solution, then this basic solution is a basic feasible
solution (or BFS). Let's check the concept of BFS using this
LP problem with two variables. First of all, we need to introduce two slack
variables to make the constraints equations. Now the problem is in the standard form.
We have n=4 variables, x1, x2, s1, and s2. m=2 equations. So, we need to pick n-m=2 NBVs
and set them to 0, and solve for the remaining m=2 BVs.
N choose m, or n choose n-m is equal to 6. We can use six possible combinations to choose
NBVs. They are listed in the left column. For the first combination, x1=x2=0. We plug
these values into the equations. This part will be 0. So s1=9, and s2=9. Because both
BVs are nonnegative, so, this is a BFS. You can do this for all other combinations.
The second and the fifth are not BFSs because they have negative values.
Now we introduce some theorems. First, the feasible region of any LP problem
is a convex set. This is because every linear constraint will split the space in half. Each
half space is a convex set. The intersection of convex sets is a convex set. Therefore,
the feasible region is a convex set. Second, the BFSs of a LP problem are actually
the extreme points of the feasible region. Third, any LP problem has a finite number
of BFSs. This is because they have a finite number of extreme points in the feasible region.
And last, if a LP problem has an optimal solution, there must be an extreme point that is optimal.
To illustrate these theorems, let's re-check this example.
This is the original problem. The feasible region is the shaded area. It is indeed a
convex set. This tables shows the BFSs. The first BFS
(0, 0) corresponds to this extreme point. The second BFS (0, 4.5) corresponds to this
extreme point. The third BFS (4.5, 0) corresponds to this
extreme point. And the last BFS (3, 3) corresponds to this
extreme point. We only have 4 BFSs, which is a finite number.
The other two are not BFSs. The last theorem says "If a LP has an optimal
solution, there must be an extreme point that is optimal".
You can use the graphical method to solve this LP problem, and you will find this point
A is the optimal solution, z=15. Point A is an extreme point.
Now, compare the last theorem with this statement. The theorem says "If a LP has an optimal solution,
there must be an extreme point that is optimal". This statement says "If a LP has an optimal
solution, then this optimal solution must be an extreme point". True or false?
The answer is False. I'll just show you a counterexample.
This is the original problem, and the optimal solution is a single point.
If we modify the objective function, and change this coefficient from 3 to 4, then we will
have infinite number of optimal solutions between point (3,3) and (4.5,0).
Now, let's check this statement again. This LP problem does have an optimal solution,
actually more than one optimal solution. Let's just consider the middle point, which
is an optimal solution. However, it is not an extreme point. This
is a counterexample. So the statement is false. Now, I'll introduce another concept. For any
LP with m constraints, two BFSs are adjacent if they have m – 1 BVs in common.
Let's check this BFS table and the graphical meaning.
The standard form of the original problem has two equality constraints. So, m=2, and
m-1 = 1. If two BFSs share one BV, they are adjacent.
The first BFS has two BVs, s1 and s2. Let's find BFSs that are adjacent to this one.
s2 is a BV in this basic solution, however, it is not a BFS, so it is not adjacent to
the first BFS. s1 is a BV in this BFS, so it is adjacent
to the first BFS. s2 is a BV in this BFS, so it is also adjacent
to the first BFS. s1 is a BV in this basic solution, however,
it is not a BFS, so it is not adjacent to the first BFS.
There is no s1 or s2 in the last BFS, so it is not adjacent to the first one.
The graphical meaning is easier to understand. An adjacent point to this extreme point is
the direct neighbor. Now, let's check the concepts introduced in
this video using an example with three variables. x1>=0 means we are considering the space from
this plane x2-x3 and going to the right. x2>=0 means we are considering the space from
this plane x1-x3 and going inside. x3>=0 means we are considering the space from
this plane x1-x2 and going up. x3<=5 means we are considering the space from
this plane and going down. x1+x2<=4 means we are considering the space
from this plane and going towards the origin 0.
Therefore, their intersection is the feasible region bounded by this triangular prism in
three dimensional-space. Let's change it to the standard form by adding
two slack variables s1 and s2. Now, we have n=5 variables, m=2 equations.
We set n-m=3 NBVs to 0 and solve for the m=2 remaining BVs.
There are a total of 10 possible combinations. They are listed in this table. Plug the NBVs
into the two equations and solve for BVs. You will find there are 6 BFSs and others
are infeasible. Now, let's check the first BFS and try to
identify its adjacent BFSs. We have a total of m=2 equations, so we only
need to find m-1=1 common BV. The BVs are s1 and s2. This BFS has s1, this
one has s2, and this one has s2. So they are all adjacent BFSs. These two don't have s1
or s2, so they are not adjacent. It is easier to find the adjacent BFSs to
this point graphically. They are just its direct neighbors.
Okay, that is how to find basic feasible solutions to a LP problem in the standard form. If a
LP problem has more than three variables, we cannot represent it graphically. However,
all the introduced theorems are still true for the problem.
Thanks for watching.