There certainly is a reason for us to consider basic solutions. It is because we want the definition of basic feasible solutions. What's that? Well, it's one kind of basic solutions that is feasible, which means it satisfies the non-negativity constraints. We know we have two sets of constraints. We have one set of functional constraints, and in a standard form, they are all equalities. By the definition of basic solutions, all basic solutions satisfy Ax equals b. That's one thing. Also, we know whenever one solution satisfies Ax equals b, the X_B may be obtained by A_B inverse b, and we have no way to tell whether this is non-negative or non-positive or are possible. If that Solution X_B happens to satisfy X non-negative, then all the constraints will be satisfied, and then we call it a basic feasible solution. The definition is here, a basic feasible solution to a standard form problem is a basic solution which all the basic variables are non-negative. We know we have six basic solutions in this particular example. We may see that the middle two solutions have negative terms as one of their basic variables. In that case they are not basic feasible solutions. The first, second, fifth and sixth solutions are basic feasible solutions because all the values are non-negative. When we want a basic feasible solution, there must be a reason. The reason is because they are just extreme points. Our theorem is here, for a standard form linear program, a solution is an extreme point solution of the feasible region if and only if it is a basic feasible solution to the linear program. What's this? We are talking about standard form linear programs. For a standard form linear program, pretty much we know how to list all the basic feasible solutions. Because according to Ax equals b, we are able to list all the basic solutions. Then we check non-negativity. We are able to list all the basic feasible solutions, and it turns out that they are exactly the set of extreme points to your original feasible region. If that's the case, then the implication is clear, all we need to do is to deal with basic feasible solutions. For a standard form linear program, if there is an optimal solution, there is an optimal basic feasible solution. Later when we formally introduce the simplest method, we will only focus on basic feasible solutions. Unfortunate thing is that we don't really have time and enough mathematical tool to prove Theorem 1 to you, but intuition are easy to be obtained. Let's take a look at some graphs to give you that intuition. Of course, you know that intuitions are never rigorous, but at least they help us understand what we're talking about and to give us some insights. Our example is still this one. We were talking about this particular example. There, our original formulation says that 2x_1 plus x_2 should be less than or equal to six, and x_1 plus 2x_2, that should be less than or equal to six. When we want to get a standard form, we plus x_3 here, plus x_4 here, and those constraints become equality. That allows us to do all those listing for basic feasible solutions. Because we have four variables and we have two constraints, each basis should contain two variables as basic variables. Once we fix the two variables, we're going to solve a two by two linear system, and then try to obtain the values. Sometimes they are all non-negative, sometimes some of them are negative. After all the enumeration, we will be able to check whether they are basic feasible solutions or not, or say it in another way, we are able to list all the basic feasible solutions. In this case, we actually may distinguish two sets of variables, X_1 and X_2 are original variables, and X_3 and X_4 are slack variables. You may consider X_1 and X_2 are some production quantities for tables, for chairs, whatever, and the six are the amount of resources you have. Resource 1, maybe that's machine hour, Resource 2, that may be the labor hours, and then x_3 and x_4, they are just the amount of resource that you have not used, something like that. Your solution basically is dealing with original variables. Here, each point for example, B, tells you that 3,0 is a solution. You want to make three units of Product 1, two units of Product 2, and so on. What do we mean by having a basic feasible solution and convert that back to your original problem? Of course, is to focus on the original variables. Your basic feasible Solution 1, has four variables, and we only focus on the original one. Your first basic feasible solution says, please set x_1 to be two and x_2 to be two. Your second basic feasible solution says that, okay, I want 3,0 and so on and so on. In total, we have four basic feasible solutions, and it happens that we also have four extreme points, 1, 2, 3, 4. We have four extreme points for the feasible region for the original problem. In the original problem, you only have x_1 and x_2. That's how your feasible region looks like these parts, and we may see that the Solution A, 2,2 is here, Solution B, 3,0 is here, solution E, 0,3, is here, and solution F, 0,0, is here. It turns out that may be, you may have a list of basic solutions. You don't know what are they, but that's fine. Because as long as you have a list of basic feasible solutions to your standard form, somehow they would be having some one to one correspondence with your extreme points to your original problems. If you want to solve your original problems, all you need to do is to focus on their extreme points. That just means you need to get your standard form and focus on their basic feasible solutions, then you are done.
