To solve a standard form linear problem, to find an optimal solution, instead of searching among all extreme points, we would search among all basic feasible solutions. These two things are equivalent. They have one-to-one correspondence. But extreme points are defined geometrically. You cannot find two points in the set such that. It would be very difficult to list all your extreme points given a feasible region. But bfs are algebraically defined and listing off them is easy. Well, equations, well, adjacent, well, non-negativity. Basic feasible solutions are easy to obtain and easy to check. Checking whether a solution is basic feasible is easy, and in particular it's easy for a computer. To search among basic feasible solutions, we would be keep moving to a better adjacent basic feasible solution from the current one. There are so many bfs, so many basic feasible solutions. Some of them are adjacent, nearby, or being neighbors to each other. The definition's here, two bases are adjacent if exactly one of their variables is different. That means the n-1 variables are all the same. Two basic feasible solutions are adjacent if their associated bases are adjacent. Somehow that means, for example, if you are talking about these four extreme points, we know they somehow have their corresponding basic feasible solutions. Then that means we will see that this extreme point and that extreme point, if they are adjacent, they look like neighbors. Then we will have exactly one of their variables being different. One thing to remind you is that we're talking about variables not values. Let's see a graph. The example is here. This is the graph we just mentioned it to you. This is the set of basic solutions or basic feasible solutions. A pair of adjacent basic feasible solutions, corresponds to a pair of adjacent extreme points. That means they are on the same edge. On the some edge is geometrically determined proposition or geometrically determined property. The same edge, the same edge, same edge, same edge. Graphically you may see B and F they are neighbors, they are on the same age, so they are adjacent. Then for B and F, we may see that, oh, okay, indeed they have one variable the same and one variable different. They only have one variable different. That means they are adjacent. On the other hand, A and F. Well, if you look at A and F, then for A is x_1, x_2, for F is x_3, x_4. They have two variables different, then in that case they are not adjacent. If you want to check whether two points are on the same edge, well, that's not very easy for a computer, especially if you are in a unidimensional space. That's not a very easy task to check. But if you want to check whether two solutions are adjacent when they are basic feasible solutions, then that's very easy because for each basic feasible solution, you know what's the basis, you know, what are the columns that are selected to form these basis. In that case, you may easily check, oh, okay, there is only one different, then in that case you may say they are adjacent or not. What we will do in running the simplest method is that we will try to search among all the basic feasible solutions. In each step, what we will do is to look at all its adjacent basic feasible solution. We will try to switch from one basic feasible solution to another one, where the another one must be adjacent to the original one. By doing so, we are moving along edges. Graphically you'll see, we may move from F to B, from B to A, from A to E, and so on. We always move along edges. That again, makes sense because we know the solution must somehow lie on boundaries. There is really a reason for us to focus only on boundary points, only on extreme points, or only on basic feasible solutions. Let's conclude all we have now, given all these concepts, how would you search among basic feasible solutions? Well, is simple, whenever I am at any basic feasible solution, all I need to do is to check all my adjacent basic feasible solution. I'm going to see whether there is one that is better than my current solution. If that's the case, there should be some improving direction. I may move from here to there and to improve myself. If I cannot find one, then I would conclude that, okay, the current basic feasible solution is optimal. That's the simple idea. Pretty much you, we may say we want to move along edges when we are talking about the geometric interpretation. But the geometric interpretation is uneasy for a computer to do, so, we move to the concept of basic feasible solution. For basic feasible solution to check adjacent ones are easy. For example, if I give you a solution where I have this set of variables being a basis, then all I need to do is to ask, well, if I fix all of this, then my x_1 may be changed to x_4, x_7, and so on, then is there anyone that is better than mine? Or I may fix x_1 and the x the others, I may ask what if x_2 becomes x_4 and x_7 and so on and so on and so on? Pretty much this allows us a systematic way to check all the adjacent basic feasible solutions. Somehow, we move to a better one and then we can get improved. Of course, this is still not the full picture of the simplest method. Because given any basic feasible solution, the way I just listed is the complete enumeration, that's still too big, that's still too inefficient. The simplest method is going to provide us the idea in an elegant way. That's how to do this.
