[MUSIC] We have seen on the special example, how to construct a new Linear program called the dual of the original Linear program. Now let us continue exploring the properties of duality. This, was our original example and that was the dual that we built. What was the property of the dual that guided our construction? The property was that, if you take any feasible x, any a feasible y the feasible y's are bound the best possible value. The main value of all feasible axises and that is true for all y's, including the one that maximizes this value. Therefore, we have the following lemma. If we look at the minimum value of the objective function of the primal LP, it is greater than or equal to the maximum value of the objective function of the dual LP. That is called the weak duality theorem in the general case and it is a very useful observation. We actually proved it in this special case by reasoning. So, you can see that it is not a very difficult statement. It's really a lemma more than a theorem. Now, we have worked on constructing the dual of a special example that was a minimization linear problem. What happens if we try to take the dual of a linear program that is a maximization linear program? Does the same principle also work? Let's try it. So,we have a maximization problem. Namely, the one we just built, this one. So, let's try to start from this maximization linear program and construct it's dual by a similar reasoning. In other words, we have to think about bounding the value of the optimal feasible solution. How do we prove a lower bound? For a maximization problem, it's easy. All we have to do is exhibit a feasible vector (y1,y2) that's satisifes all constraints. And then its value will be less than equal maximum possible value. So, that's the lower bound. How do we prove another bound? For the upper bound, it's a little more complicated. So again, what we will do is construct a convex combination of the constraints, 1', 2', 3', such that the coefficient of y1 is at least 10. And the coefficient of y2 is at least 6. Notice that before, when we are working on the other linear program, we were trying to have a coefficient of x1 be at most something and x2 be at most something. Now, it's at least 10 and at least 6. And then what happens? So, we multiply z1 times constraint 1 prime. z2 times constraint 2 prime. z3 times constraint 3 prime such that, the resulting coefficient of y1, z1-z2+3z3 is at least 10. This 10 and the resulting coefficient of y2 is at least 6, this 6. Then, once we have that, we can deduce an upper bound for the optimal value. How? The right hand side, 7z1 plus z2 plus 5z3, will be an upper bound on the optimal value of this linear program. So that, with that reasoning, we deduce the dual linear program of that problem. The best upper bound, the the tightest one, is the one that is minimum. Minimize the 7z1+z2+5z3 such that two constraints are satisfied, z1-z2+3z3 is a least 10 and 5 z1+2z2-z3 is at least 6. And the zI's are all non-negative. That new Linear program. It's a minimization LP and that is called the dual of the one that we started from. So now we have two examples of duality. We started from a minimization problem and we built a maximization problem, the dual LP. Now, we started from a maximization problem and we built a minimization problem, the dual LP. But there is a surprise here. If we put all this side by side, the LP we started from, the dual reconstructed, then that was our example of a maximizational key. The dual that we built, the dual of the dual. Then, the dual of the dual is the primal. Up to renaming z1, z2, z3 and calling them x1, x2, x3. It's exactly the same thing. So, the dual of the dual is the primal. That is a general property of duality. It's actually an invariate of duality. It works not just for linear programming duality, but also for planar graph duality or other dual structures that exist in mathematics. Whenever something is called dual, you can be sure that the dual of the dual is the primal. So that is one property of linear programming duality. Now we will see some other properties by looking at the geometry of duality.
