Let's consider this example. Let's say we have a linear program which looks pretty much similar to the previous ones. But now, for the first constraint is actually greater than or equal to instead of less than or equal to. In this particular case, we would not have a trivial basic feasible solution. Because if you just get a very typical standard form, you don't have an identity matrix by free. In that case, we would construct our phase 1 standard form linear program. We would add these artificial variable x_5 after we do the standard form thing. Don't forget, we still always first to those slake variables. We introduce low slake variables because they are meaningful. Then when we see we need some more variables to create the identity metrics we need, then we introduce artificial variables. In this particular example, x_3 and x_4, they are slakes and x_5 is an artificial variable. We introduce that x_5 and then we get another linear program where we want to minimize x_5, minimize the sum of all artificial variables. Don't forget, we need artificial variables because we need identity matrix. Because x_4 already may serve as a part of the identity matrix, we only need one artificial variable. Let's take a look at this example. Pretty much, what we try to so is to solve our previous example. From this tableau maybe, you may also take a look and understand what we are trying to do. We want to maximize or minimize whatever subject to 2x_1 plus x_2 or x_1 plus 2x_2, according to here, minus x_3 plus x_4. We want to solve this particular linear system. Maybe we are given this formulation and we have no idea whether there is a feasible solution or not. Then our strategy, as we mentioned, is to artificially add one variable called x_5. If we do that, we say x_5 is artificial and we're going to see whether we may run some simplex iterations to take away this x_5. That's why we want to minimize x_5 subject to all these things. That's going to be translated into this tableau. In this tableau, one thing to keep in mind is that, is this a valid tableau? No, because we try to say x_4 and Xx_ are our basic variables. But if that's the case, why there is an identity matrix here, your objective role are not all zero. In that case, we need to adjust the zeros row with elementary row operations. We need to first do some adjustments and that the way to do it, of course, is to adjust the row 0 by adding row 1 to row 0. This is not a simplex iteration because we are not really doing pivoting. All we are doing is to make the two columns satisfying the conditions, the requirements for basic columns. Once we do that, now, we are ready. We may take a look at Lowe's reduce costs. The current basic feasible solution here, 0, 0, 0, 6, 6, which corresponds to an infeasible solution to the original LP. Why do we know it is infeasible? Because our artificial variable x_5 is still positive. Somehow that means this 0, 0 is not a feasible solution to the original problem or this 0, 0, 0, 6 is not a basic feasible solution to the original standard for. Let's try to remove it. This guy is a minimization problem. We need to look at positive reduce costs. We enter x_1, we do the ratio test, x_5 should leave. Once we do that, we are done. We know x_5, [inaudible] for the basis. There is the fact that whenever an artificial variable leaves the basis, we will not need to enter it again because there is no benefit at all. We know if we want to save some time in doing handwriting calculations, we may remove that column. That's why from the left to the right, after one iteration, one column disappear. The column for x_5 for the artificial variable disappears. We first find the entering column and the leaving column. We know x_5 is leaving, so we take it away, we remove it. With the remaining four columns, we do all the usual pivoting and then we're done. We're done with our new tableau and in this way, the new tableau says that x_1 and x_4 should be our basis for the original problem. A feasible basis for the original problem would be x_1 and x_4. If you select that, that corresponding AB matrix on the two columns is going to form an invertible matrix A_B. The A_B inverse b is going to be non-negative. Actually, you also know that it's 3, 3. Now let's construct the phase II linear program. First, if we are trying to maximize x_1 plus x_2, we may add that objective function back by reverting their size. You're going to see negative one and negative one in your zeros row. That makes sense. But also the system valid tableau, again, it's not because column 1 here, ideally, the number here should be zero, but now it's negative one. We need to fix the system again. Let's adjust the 0th row again. Here we are in the phase-II LP. We need to first do adjustments to make this number 0 so that now we have a valid tableau where the basic columns are having identity, as the constraints side having zeros as the objective sides. Now all we need to do is the remaining very typical simplex method. We are solving a maximization problem. This one enters ratio test, these two will leave. Then we go to our second tableau. There is an entering variable, there is a leaving variable, and eventually we are done. Now we find an optimal, basic feasible solution. We're going to see that x_1 and x_3 should be our basic variables. Their are values should be 6 and 6, and that somehow gives us 6, 0, 6, 0 as our basic feasible solution that is optimal. Again, we may graphically take a look at our search paths. Originally, we start from x_0, because originally our solution, or basic feasible solution is this one. If we exclude our artificial variable, then initially x_0 is this one. This corresponds to the initial point here. Then we do one iteration to get to our initial basic feasible solution. As a result of phase I is this point, you are going to have x_1 being 3 and x_2 being 0 and some others. After two iterations, we then get to x_3, which is optimal as a result of our phase II solution. Hopefully you would also go back to take a look at these tableaus, solutions, formulations again and try to do all the things by yourselves. Go through all these examples so that you really know everything, do the calculations. Pretty much that's the end for our discussions, introductions for the simplex method. It may not be easy at the beginning because there are so many things to mention, but hopefully you get the idea. Pretty much, we want to move along edges to find an extreme point solution. To do that with computers, we need to convert everything into algebra. That's why we define standard form, basic feasible solutions, reduce cost ratio test so that we may iteratively find the entering variable, leaving variables. Sometimes we need to update the system to make the calculations easier. I hope you'll not just memorize these ideas, you may also appreciate the beauty under that. The design itself is elegant, that's why it can be a classic algorithm. That's pretty much all I have at this moment.
