We now have algebraically solved our problem. Maybe we want to visualize it as an example. So initially we are at here (0,0), when the non-basic variables are X1 and X2. So they are all zero. After one iteration, we move to another basic feasible solution, which is (4,0) for X1 and X2. At the moment your X3 is also positive, but regarding the original solution, you do not need to take a look at X3. So after one iteration, we move to (4,0). After two iterations, we move to our second solution, if you do not count the initial one. So we moved to 10 over three, and four over three. By simplex method, we conclude that it is optimal. Graphically, we may also see that it is indeed optimal. So this not just verifies the solutions correctness, it also visualize how we move along ages to search among extreme points. It's not just true for this particular example. It's true for all the linear programs. As long as you use the simplex method to move along basic feasible solutions, graphically, you always move along ages. So to summarize all the things we just did. To run the simplex method, first, we need to find an initial basic feasible solution with its basis. In general, we haven't told you how to do that, but very quickly we will show you how to do that. Then among all those nonbasic variables, we take a look at the zeros row to see whether we may find the coefficient with the right side. If we are talking about a minimization problem, we look for positive coefficient. If we are talking about maximization problem, we look for negative coefficients, as in our example. If the nonbasic variable has the correct sign, we choose one to enter. Up to here, we haven't told you how to choose one to enter. It turns out that if you want to run the simplex method, this is an issue. Sometimes you may think about, "Well, how about this? I'm going to choose the one with the most significant coefficient." So what do we mean by most significant? If you have negative two and negative three, the negative three has the larger absolute value, and you may consider that as most significant. But we know this is not always the best. Because when you increase, when you try to increase your Z value, even though negative three tells you that when you increase that variable by one, your Z is going to be increased by three, which is better than two. But you have no way to tell what's going to happen if you increase X2 by one, or two, or three, or whatever. You have not looked at the constraint. You don't know how far you may move your solution by increasing X2. If you really need to do that, you need to look at the constraints, at least. So there's no way to say that entering X2 is definitely better than increasing X1. Entering X2 is not necessarily better than increasing X1, if you just look at their objective coefficients. So I hope that makes sense. So in practice, people actually don't really look at the most significant coefficient. People typically suggest you, for example, to just use the indexes. If X1 and X2 are both okay, then lets just pick X1. It's actually a more widely used algorithm or implementation to run the simplex method. So the reason cannot be told by this moment, but anyway, being able to select one variable to enter when you have multiple candidates is an important issue. If you don't want to learn more, I will suggest you just to pick the one with a correct sign and the smallest index. So after we do that, we need to do some kind of ratio tests, from the basic in the right-hand side columns. One basic column would be considered to be the entering column. So actually what we are talking about is the column for an entering nonbasic columns. So we have one entering variable. For that entering variable is typically nonbasic. Nonbasic. So for that nonbasic column and the right hand side column, we would do the ratio test to determine which basic variable should leave. Again, there may be a tie-breaking thing that we need to consider. If the right-hand side columns and the denominator columns, or the entering columns, if the ratio has some time so that you have multiple numbers, not multiple basic variables hitting zero at the same time, you somehow need to make a decision about which one to leave. Again, if you have no way to tell, I would suggest again the smallest index. Take a look at each basic variable, which hits zero for the first, and then pick the one with the smallest index. That's the idea. If you have some denominator, which is zero or negative due to the ratio test, I hope you also agree that we don't need to do that. Why is that? Because that somehow means when you increase that particular entering variable, this denominator being zero means it has no impact on that particular basic variable. Or if it's negative, that means that basic variable actually also increase when you increase that nonbasic variable. So in either way, there's no way for this variable to hit zero. You should ignore them directly. So once you do all of this, we would find a new basis and then we need to make the system fit the requirements for basic columns. We need to have an identity matrix, four constraints, and we need to have zeros in the objective function. Once we fix the constraints, we fits the system with elementary row operations. We redo everything. We do everything until we are done. So that's the general way of running the simplex method.
