Okay, so we have done our preparations, we know what's a standard form. We know what's basic feasible solutions. So later, I'm going to go to the details about the simplex method. But actually, up to now, you already know what's the main focus or the main architecture. We don't want to have algorithms for any kinds of linear programs. So for any linear program, what we will do is to make it a standard form linear program, okay, so standard form, Linear program. And then once we have that, we will use our simplex method to solve it. For a standard form program, we define one thing called basic feasible solution. And we know that's pretty much equivalent to extreme points, although we have no way to prove it to you. But from the examples from the graphs, you already see that, indeed, as long as you use the way of defining space, your feasible solution is to find a basic feasible one. You're going to find a corresponding extreme point as the feasible region of your original problem, they are equivalent. And then we also define one thing called an adjacent basic feasible solution that somehow also corresponds to adjacent extreme points. So all we need to do is to search among adjacent basic feasible solutions. And the simplex method pretty much is a smart way to do the search, okay? I don't want to go through all the basic feasible solutions. I just want to start at one, and then always move to one that is better than the current one. I will keep doing this until I cannot do it anymore. Then I stop and say I'm getting an optimal solution. That's the idea, so let's see how to do this with algebra. So all we need is to search among basic feasible solutions. Geometrically, that means we search among extreme points, and we're moving to an adjacent basic feasible solution by moving along edges. The question is, when we are having some kind of problems like this, at any point, we want to ask, if there are multiple edges to move along, which one should we choose? Okay, that's one problem. And then once we say, okay, I want to move along this direction, somehow I need to check, there is a position for me to stop, I need to know when I should stop. By looking at the graph, everything looks so simple, but we know we are doing n-dimensional problems. There's no way for you to draw n-dimensional graphs. So we need to do all the things with algebra instead of geometric, okay? So that's why we need to define all those basic feasible things. So algebraically, we already know one thing. To move to an adjacent basic feasible solution, what we will do is to replace one basic variable by a nonbasic one, okay? For example, if the current bases is x1, x2, and x3, maybe we would like to replace x1 by x5. By doing so, we're going to move to an adjacent one, and maybe that's better than the current one. So now we know there are two things to do. We're going to select one nonbasic variable, and recall, it's going to enter the basis, for example, this x5. We need to determine which nonbasic variable should enter, and we need to select one basic variable to leave the basis, for example, this x1. Once we know which one to enter, which one to leave, we swap them. And then we're going to get a new solution. That's something we want to do. So the idea is that we want to select entering and leaving variables, all right? So selecting one nonbasic variable to enter means making it nonzero, what does that mean? Previously, we said nonbasic variables, they are all zeroes, okay? We select them, fix them to zeroes, and solve the other basic variables. So making it basic means making it nonzero, or having an attempt to increase it to a positive value, okay? And we all know that when we increase one nonbasic variable to a positive value, some other basic variables, their values must change, because we have all those equations, all right? So we're going to take a look at those basic variables, some of them where values would also increase, then there is no problem. If some of their variables are decreasing, then for those decreasing variables, we will know they cannot be negative, right, because all variables must be nonnegative. So we will keep increasing our nonbasic variables until one basic variable hits 0. That basic variable who hits 0 first is going to leave the basis and become nonbasic. So that set of equations is going to allow us to do all the things here. And we will keep changing the basis until we find an optimal basis, so that's the idea.
