Let's start our introduction and we will start from our standard form. We want to define one kind of linear program and we will call it the standard form. The standard form linear program is a special type of linear program. If we say it is a standard form, then the following things must be true. All the right-hand side values are non-negative, all the variables are non-negative and all the constraints are equalities. Right-hand side may need a specific definition. RHS is the abbreviation of right-hand side. That somehow means, when you are given a constraint, we typically always put those things that are associated with variables, we put it at the left-hand side, and then the only constant, we put it at the right-hand side. If we do that, pretty much the right-hand side is just the single constant and then we would always put the constant at the right-hand side when we are doing linear programming formulation. Suppose we do that, it doesn't really matter whether you have less than or equal to, greater than or equal to or equality, we always call the right-hand side, that single constant right-hand side. Also mentioned that there is no restriction on the objective function. It doesn't really matter whether you have a maximization or minimization, whatever, so all the requirements are unconstraints. Somehow we need to convince you that for any linear program, we may convert it to a standard form. Let's try to do this. The first requirement says that, "all your right-hand side must be non-negative, " also I hope this is not too weird for you. As long as you have a negative right-hand side, that switch the two sides or let's flip the sign for the two sides. Suppose we say, you have 2x_1 plus 3x_2 less than or equal to negative four, all we need to do to make this guy positive, is to multiply each side by negative one. Then once we do that, we're going to say, "Negative two, x_1 minus 3x_2 must be greater than or equal to 4." Other VSD, these two constraints are equivalent, so we don't really change anything. All we did is to change the right-hand side to be non-negative, and we can do that for any constraint. Then we need a non-negative variables. If a variable actually is non-positive, we may replace it by again negative x_1. For example, if you say okay, negative 2x_1 plus 3x_2 must be less than or equal to 4, and your x_i is non-positive, then all we need to do is to replace your x_1 by negative x_1, then that new x_1 would be non-negative, and then your constraint would be fixed to negative 2x_1 plus 3x_2 less than or equal to 4. Again, we don't really change anything. We simply change the sign of these variables. One thing that may be not so intuitive is the case that when you are, x_i is free. Suppose you have a free variable, it may be positive, negative or whatever. We may again, replace these free variable by two non-negative variables, and then we would set x_i to be x_i prime minus x_i prime prime. Somehow, these two new non-negative variables, we may use their difference to express x_i, and intuitively, this one means the positive side and this one means the negative side. What does that mean? That means if you are original x_i takes a positive value, we would like x_i prime to be that positive part. If it is negative, then we would take x-i prime prime. Make it a positive value, so that the negative side of x_i prime prime goes back to your original x_i. An example may be even more easier to understand. Suppose you have a constraint like this and you're x_1 is unrestricted in sign, then we replace x_1 by two other variables, x_i prime and x_i prime prime. They are all non-negative, and we replace x_1 by x_1 prime minus x_1 prime prime, so we also modify these constraint. Then how does that work? It doesn't really take away any flexibility. Your original x_i may still be 5, for example, then you are x_i prime is 5, x_i prime prime is 0, that's fine. Your x_i may be negative eight, then you would have x_i prime to be 0 and x_i prime prime to be 8. Somehow after this conversion, any possible value in your original constraints, may be expressed by your new setting, so it doesn't really take away any flexibility. How about your requirement 3? Requirement 3 says, "Oh, the constraints should be equality." For any less than or equal to constraint, we're going to add a slack variable. This slack variable somehow express what the difference? What that gap between your variable's value and that right-hand side? This slack variable may be added into this constraint while it is non-negative, so that the constraint becomes an equality. If you have a greater than or equal to constraint, typically we say you may minus a surplus or excess variable. Like this, x_3. You say, "Okay the left-hand side is greater than a right-hand side, then we add these x_3. We subtract your left hand side by x_3, to make the thing equality." In all cases you may see that either your slack variable or your a surplus variables, they have physical meanings. The meaning is that, well, x_3 either is a slack or is a surplus. It is representing the value of the gap between the two sides. For ease of association in this course, we will always call off them slack variables somehow is just filling that gap between the two sides. We don't really specifically use surplus or excess, is just some notions that some other people may use. But we always use slack variables, either this one or that one, so it measures the gap between left-hand side and the right-hand side and you will see it very often.
