Let's consider the following linear program, and this program is very similar to previous ones, it's just that now the right-hand side 6 and 8 are to make our calculations easier. With this particular solution, the standard form would be adding x_3 and x_4 to make them equalities. This should be fine. Now we know we need to keep track of the objective value, because whenever we say we improve, that means our objective value is increased or decreased according to the objective function. We want to keep improving. That say we use z to be 2x_1 plus 3x_2 to denote our objective value. Because this is so common, sometimes we just call it the z value in the field of operations research. When we talk about linear programming, integer programming, whatever, the z value is typically used to denote the objective value. One thing we want to do is that we want to keep track of this z value. We know where you are maximizing z, and also all other variables except z must be non-negative. Maybe we may say that as long as we know these two things by ourselves, all the remaining things may be expressed in these three equations. Here we have three equations. Previously, we have two that are about constraints. We now express the objective function as a third equation. It's here. Pretty much the last two are the constraints. They are nothing different, they are nothing special. We simply add the first one, z minus 2x_1 minus 3x_2 equals 0. This is going to be again, another equation that must be satisfied throughout the whole process. Whatever x_1 and x_2 you have, somehow the z value must satisfy this equality. That makes sense. Pretty much what we are doing is to take the objective function and express it as an equality. This constraint, which is not really a constraint, which is actually an objective function. This constraint would be called the zeros constraint throughout the process. What we will do is to take a look at this system of three equations and keep modifying the values for x so that we may find feasible solutions with higher values of z. To start the search process, we need to first have an initial basic feasible solution. In general, an LP is solved with two stages. In the first stage, we will search for an initial basic feasible solution. Somehow, we need to find a way to do this. Let's assume we already have an initial basic feasible solution. Then in the next stage, we will keep moving along edges until we find an optimal basic feasible solution. Somehow we will first focus on the second stage. That's as soon, we already have an initial basic feasible solution. Let's tell you how to find an optimal one. Then at the end for today's lecture, we will tell you how to find an initial one. We need to somehow first have an initial basic feasible solution. Luckily, for this particular example, this is very easy. If we look at this system again, all we need to do is to select two columns. We want to select two columns to make this system solvable. How about this? Let's select x_3 and x_4. If we say x_3 and x_4 are the set of basic variables, then all we need to do is to say, hey, x_3 is 6, x_4 is 8, and then we're done. This is indeed feasible. This is a situation that selecting x_3, x_4 definitely works. Because of what? Because for the two columns, they form an identity matrix. When we want to solve A_B X_B equals small b, that's just means I X_B equals small b, and then X+B equals small b. Also, you know small b is non-negative according to the definition for standard form. That's why your X_B is also non-negative and is a basic feasible solution. Is not the case that you always have an identity matrix here for free, it is because that here, the two constraints originally are less than or equal to. You add slake variables for each constraint, and then you get this identity matrix. We have this by chance. Later we will show you how to deal with other cases in finding a basic feasible solution initially, but here let's take it as given and see what should we do. Now we're going to start from our basic feasible solution, the initial one from 0068. These two variables, x_1 and x_2, they are non-basic, so they are 0. X_3 and x_4, they are basic, so that's positive 6 and 8. The current basic feasible solution gives us the objective value, which is zero. Why is that? Because if you're plugging this solution to your objective role, you too see that your z is zero. I hope that makes sense. Somehow we now want to move to our adjacent basic feasible solution. That means we need to select either x_1 or x_2 to enter the basis. Which one should we do? Well, the zeros row or the zeros constraint is going to give us some hint, so there's no s here. The hint is that we may look at their coefficients so that we know what's the impact of increasing that particular variable to z. You do see this negative two here. What does that mean? That means if your x_2 is increased by one, your z must be increased by two so that the equality still holds. Similarly, if you see this negative three, you understand that if you increase x_2 by one, you are going to increase z by three so that the equality still holds. Somehow that means, oh, that's good. Because increasing x_1 or x_2 both would increase our value for z, and this is a maximization problem. So we want z to be as large as possible. Choosing x_1 or x_2 both would increase our objective value z. But of course, we need to somehow pick one. Let's assume we will choose x_1 to enter. You may want to ask, what's the point of not choosing x_2? Because choosing x_2 seems to be better. But very quickly we'll show you why it is not always the case. If we want to increase x_1, let see what's going to happen, and let see the how to select a leaving variable. Now x_1 goes up from zero. If x_1 goes to one, goes to two, we need to keep an eye on the impact of the basic variables. Basic variables originally are six and eight. Once you increase x_1 by one from the two equations, you may see that if x_1 is increased by one, you were x_3 must have decreased by one. That's why six becomes five. If x_1 is increased by one, x_4 must be decreased by two. That's why your eight becomes six, so 0, 0, 6, 8 becomes 1, 0, 5, 6 becomes 2, 0, 4, 4 and so on and so on. Very quickly you would see that our x_2 remains zero because we are not changing that a non-basic variable, it's remains zero. Very quickly we will get to a point, 4, 0, 2, 0 when x_4 becomes zero. X_4 becomes zero before x_3 becomes zero. So x_4 hits zero the first, that means our x_4 should be the leaving variable. Previously our basis is x_3 and x_4. We know x_1 would enter, x_4 would leave. What does that mean? Later we will change x_4 to x_1. If you go back to see what we were trying to do, we first see which entering variable may benefit the objective function and we see which basic variable hits zero the first. That allows us to do all the checking, all the determinations. For the leaving variable, actually determining which one would hit the zero first is also very simple. All we need to do is to look at the ratio of the right hand side values under the entering column. For this particular example, we focus on the coefficients for x_1, because x_1 enters, so this 1, 2 is the entering column, and the right-hand side is 6, 8. 6 divided by 1 is 1, the one is here. Which means you may increase x_1 up to six before you may require x_3 to become zero. 8 divided by 2 is 4, that means you may increase x_1 up to four before you make x_4 becoming zero. This ratio directory tells us that the second ratio is smaller, four is less than six. So x_4, which corresponds to the second ratio is going to hit zero first, and that's somehow tells us that our case, so x_4 will be the leaving variable. Once we know, we will change from x_3, x_4, to x_3, x_1, we may resolve the whole system. Or if you keep an eye on what we are doing, we know we would stop at 4, 0, 2, 0. That's our x_2. Now, our z-value would be increased to eight that's indeed an improvement. Pretty much that's the idea we need to do with the simplex method. Take a look at the zeros row to see which non-basic variable should enter, and we do some kind of ratio test between the right-hand side column and the entering column to see which basic variable would hit heat zero first. Then we are able to change to our new basis, and then we may do it again, again, and again.
