[MUSIC] We have seen how to take the dual of linear programs, but only if they are in a favorable form. Let us see how to transform any linear program so that it is in the desired format. So we'll find an appropriate transformation to take an arbitrarily linear program and put it in the correct form so that we can take the dual easily. What form would we like? Let's say that we want a maximization linear program, max of c.x such that Ax is less than or equal to b. And the vector x is a non-negative in all of its coordinates. How do we take an arbitrary linear program and transform it so that it has this form? Let me prove it by example. Show how it is always possible by taking an example. Here is an arbitrary linear program. Min of 2x1-3x2+x3 such that x1+x2=4, x2-4x3 is greater than or equal to 5 and x2 is nonnegative. We take this and we want to modify it so that it is of that form. There are a few steps to this transformation. First, what is perhaps the easiest step. We have a minimization problem. We want a maximization problem. How do we do that? Transform the min into the max. How do we do that? I-N is changed to A-X, or rather, minimizing f of x is the same as maximizing minus f of x. So instead of minimizing this objective c.x, we can just maximize- c.x. That is, in the present case, we replace the objective minimize 2x1- 3x2 + x3. By the objective max of -2x1 + 3x2- x3. The rest is unchanged. These two linear programs are equivalent to one another and a solution to one is a solution to the other. The objective can easily be translated back and forth and so we have done the first step of transforming our LP to put it into this form. Next step, the form we want we have inequalities everywhere. Here we have some equalities. Let us change this in your program so that the equalities become inequalities. How do we do that? Easy. What does it mean that x1 + x2 = 4. It means that it's less than or equal to four and great than or equal to four. So we can simulate an equality with two inequalities. That is, we take x1 + x2 = 4, equals four. Remove it and create two new constraints. x1 + x2 greater than 4 and less than 4. The size of the LP has at most doubled the number of constraints. And the two LPs again, are exactly equivalent. This was never a very easy transformation. Next, look at this. What we see is that all the inequalities are less than or equal to. Our inequalities are greater than or equal to, less than or equal to, greater than or equal to. Let's make all the inequalities go into the right direction. That is less than or equal to. How do we do it? Same as for the reactive function. We're going to take, for example, x1 + x2 greater than four, and change all the signs. And that reverses the direction of the inequality, namely, x1 + x2 greater than or equal to four is equivalent to -x1- x2 is less than or equal to -4. Similarly x2 -4x3 greater than or equal to 5 is equivalent to -x2 + 4x3 less than or equal to -5. With this other very easy transformation, we have managed to have a maximization problem, where all the constraints are inequalities, and they all go in the direction, some linear function of x is less than or equal, to a constant. So we're almost done here, the only thing left is x must be non negative. x2 must be non negative. But what about x1 and x3? They're allowed to be negative in our linear program. So the last step of the transformation is to reduce our LP to an LP that has non-negative variables only. How do we do this? This is the only part of this transformation where some small idea is needed. And here's the idea. We want to allow x1, say, to be positive or negative in this LP. We want to write this with an LP where the variables are all non-negative. How do we do this? We can say, well, this LP has, it's really the union of two parts. The part where x1 is greater than or equal to zero. And the part where x1 is less than or equal to zero. If x1 is less or equal to zero, then we can write it as minus something else which is nonnegative. So what about combining? The idea is to create two new variables and replace x1, one unconstrained variable, by two variables which I will call x1 + x1 We replace x1, this variable disappears, by two new variables, x1+, x1- such that x1 = x1+- x1 With the constraint that x1+ and x1- both have to be non-negative. So we take this LP, we substitute for every occurrence of x1, x1+- x1-, and add the constraint that x1+ and x1- must be non-negative. Similarly for x3, which is unconstrained, we replace every occurrence of x3 by x3+-x3-. And add the constraint that these two new variables have to be non-negative. The number of variables, at most, doubles. I argue that every feasible solution in the top linear program can be mapped to a feasible solution in the bottom linear program and vice versa. Let's argue this. Let's take a feasible solution in the bottom linear program. We have a vector, x1+, x1-, x2, x3+, x3-, that satisfies all these constraints. With this vector, I define a new vector. x2 will be the same. I will define x1 as x1 + -x1 I will define x3 as x3 + -x3- and that defines a new vector x1, x2, x3 that, by inspection, satisfies all these constraints. Every feasible solution to the bottom LP can be mapped to a feasible solution for the top LP. And the objective function maps to the objective function. Conversely, let's take a feasible x for the top LP. How do we transform it? Easy. Let's say that x1 = 5, and, x3 = 2. I will define a new vector, where the value of x2 is unchanged. The values of x1+, x1- are, five, zero. And the values of x3+ 3x- are, x3 was 2 I said, 2, 0. Then by construction, this new vector, x1 + 1x- x2, x3+ x3- satisfies all the constraints, and the value of the objective function maps to that value. And all these x's are nonnegative. Here's another case. Imagine x1 is minus 5, then I will define x1+ = 0. x1-, 5. This quantity equals minus five. Exactly the value of x1. And again x1+ x1- are non-negative. So in general, given x1, I define x1+ to be either x1 or 0. Whichever one is greater. And x1- to be either 0 or -x1. Whichever one is greater. And then with this, I can map x1 to x1+ x1- similarly for x3. Map every visible solution to the top LP to a feasible solution to the bottom LP. If I look at the bottom LP and I develop the parentheses, what I have is now a linear program in the form I wished. And so without loss of generality, we can assume our linear program is of the form of the blue LP, and that makes it very simple to take the dual intuitively. So we're talking mostly about LPs of a very specific form. But that is without loss of generity. As I hope to have convinced you by working out this specific example in full detail.