Let's give you another example which may make you understand more, so in this particular case, we want to maximize x1 subject to 3 less than or equal to constraints with two non-negative variables. We get to the standard form by adding three slake variables, and then we prepare our initial tableau, pretty much for constraints we simply record everything. We just copy and paste all the numbers. For the zeros row I hope you'll still understand why we want to have a negative multiplication there. We will go in to multiply each value by negative one because that's the way for us to get the equation with respect to z. Once we have that, we know this is a set of basic variables, that's for x3, x4, and x5. We get this because there's a identity metrics here with all zeros there so we get this for free. Then for the other x1 and x2, that's now basic. Okay. For this maximization problem, we look for negative numbers in the zeros row, because we do these form so often on those negative numbers, positive numbers in the zeros row are so important. Starting from now, we will give them a special name. They will be called the reduced cost. The numbers in the zeros row are called reduced cost. Why is that? Well, the name somehow means if you consider this as the minimization problem, okay. I want to minimize the total cost for us to produce something. In that case, your C transpose x, those CR cost per unit, something like that, okay. You are looking for a way to increase the production of some variables so that you may decrease the total cost. If you want to do that you look for positive numbers in the zeros row and if those positive numbers tells you if you increase this variable by one unit, how much of the cost would you reduce? That's why these values are called reduced cost in general. Okay so we look for negative reduced costs for maximization problems. We can see that, okay, so this one should be an entering column, entering variable. We're going to choose x1 to enter and then we want to divide the right-hand side column by the entering column. We want to use 4 to be divided by 2, 8 to be divided by 2, and the 3 to be divided by 0. Here we are going to ignore this particular division. We're going to enter a leaving variable by considering just x3 and x4. Why is that? Because if you think about the effect of entering x1, when x1 goes up, if this number is 0, what does that mean? That means it has no impact on x5. Okay. When x1 goes up, your x5 would still remain to be 3 forever. That means your x5 has no way to hit 0. x5 or constraint 3 does not create any problem for you or you may say constraint 3 is not in front of you. If you move along increasing x1, okay. This 0 happening in the denominator tells us that increasing x1 does not affect x5. We only focus on the first two rows and pick the one with the smaller index. We will call this as the ratio test. x1 should enter, x3 should leave and then we say we pivot at 2, or we do the next tableau by pivoting at 2. We consider this number 2 as our pivot. We multiply the first constraint by one half and then do some elementary row operations to get this 0, get this 0, that allows us to get our next tableau. For the next tableau, we have the identity metrics here and there for variables x1, x4, and x5. Now we have the new basic feasible solution, which is 2,4,3 for x1, x4, and x5 and for the others, that's 0. We want to know whether we should continue. Okay, so we look at the zeros row again, we identify a negative reduced cost. Then for this maximization problem, there should be an entering variable so your x2 would enter. Now you apply the ratio test again. Well, you may see that now we have a negative number at the denominator. What does that mean? That means if you increase x2, increase x2, that's going to make your x1 even larger. That means constraint 1 has no way to prevent you from keep improving your x2. Constraint 1 is again not in front of you. If that's the case, you again, you may eliminate constraint 1 from the selection of a leaving variable. You only consider 4 divided by 2 and a 3 divided by 1 and then very quickly you will see that row 2 wins the ratio test with a smaller ratio. x2 should enter, x4 should leave. We have a pivot, which is this number 2, and then we pivoting. Once we do it again, we may see that we get a third basic feasible solution, which is 3,2,0,0,1. It is optimal. Why? Because all the reduced costs are now non negative. There's no way for us to improve this solution and then we report this as an optimal solution. Typically in this case we would write x star as our optimal solution and that corresponding optimal objective z value is called z star so our z star in this case would be 3. Graphically, you may verify the correspondence again. We have two initial original variables, x1 and x2. Every time when you get a basic feasible solution, if you focus on x1 and x2, focus on the two variables, okay. Then we would see that they indeed corresponds to some extreme points for the original feasible region. Also, when we say that we do one iteration, next iteration, we always move along edges. It should be quite clear. We always do iterations when we find an improving direction and once we move along that improving direction, there are some constraints in front of us and the ratio test would tell us when to stop. That's how we get the improvement and that's how we do iterations. The simplex method do all the things in algebra. That's how a computer program may be correctly constructed to execute the simplex method. But still we know it has some correspondence with the geometric ideas. Okay, so I hope we may appreciate how the simplex method is decided or is defined so that it somehow simulate the geometric search, but in an algebraic way. That somehow make the computer search feasible.
