Now it's pretty much the time to summarize the general rule. In general, if our primal LP is something like this. Here we have three variables, three constraints. Variables are of any type, constraints are of any type. Then we are able to write down our dual LP, without knowing any numbers specifically, because it's always the same. Whatever you have as the primal objective function, that goes to the right hand side. Whatever you have for your primer right-hand side, that goes to your dual objective function. Also you would see that the constraint coefficients are somewhat transposed. Here you have 11, 12, 13. Here you would have 11, 12, and 13. You may again ask, why is that? Well, the answer is simple, because your Y_1, Y_2, Y_3, these dual variables, they are multiplied with all the things here. A_11, A_12, A_13, they would be multiplied with Y_1. That's why in your dual program, A_11, A_12, A_13, they lie in the same column. Finally, other sign constraints, and that is the sign of your functional constraints. I'm not going to repeat everything. Your dual variables may have sign constraints. They are determined according to the sign or the direction of your primal constraints. Also your primal variable may have size, that's going to determine the side or the direction for your inequalities or constraints in your dual program. That's pretty much everything we need to know for the primal dual pair. We know, for a maximization problem, we look for an upper bound. We want to minimize that upper bound. Therefore that particular value to be an upper bound, you need to satisfy a few constraints. That's pretty much the dual program. When we are writing down all the things in symbols, then we have different ways of doing the expressions. For example, maybe we are talking about a standard form. If it is a standard form, then we also know how to write down it's dual. Maximization becomes minimization, c goes to the right hand side, b goes to the objective function. As these are all equality. These Y_1, Y_2, Y_3, they would be unrestricted in sign. They can be anything. Because all these variables are non-negative, so you will see that in your dual program, the constraints are all greater than or equal to. This in matrix representation, we would write things in a much more compact way. We would see that we are maximized c transpose x subject to A_x equals b, and x greater than or equal to 0. This translates to the dual variable y. Y would be multiplied with b, so we typically write y transpose b, and then we somehow need A transpose y. But typically, we write y transpose A, just to preserve the direction of A. Y transpose A would be compared with c transpose to make sure that in the dimension of your vectors are equal. In this case you have a greater than or equal to constraints, because your x is non-negative. For a minimization linear program, it's dual program may also be obtained with a slightly different rules. For a minimization problem, it's dual, is to maximize the lower bound. Because we are doing a similar thing in a different direction, all those directions and variables rules must be reversed. When you're primal is a minimization problem. For your dual, it will be a maximization problem. Then when you multiply Y_1 and Y_2 to these two constraints, lets take a look at how we do the derivations. We hope that our primal objective function is bounded below. We hope this 3_x1 plus 4_x2 plus 8_x3, eventually may be greater than or equal to 6_Y1, plus 4_Y2. Then we are able to maximize the lower bound, by solving this linear program. We need to make sure that we preserve these directions one-by-one. For the first one, we need to make sure that our three is greater than or equal to Y_1 plus 2Y_2. Why is that? Because our x_y is positive. We need 3 to be greater than or equal to Y_1 plus 2Y_2. As our x_2 is non-positive, now we need 4 to be less than or equal to 2Y_1 plus Y_2. Then multiplied with a negative x_2 is going to reverse the thing. Finally, as our x_3 can be anything, pretty much we need 8 to be equal to 3Y_1 plus 2Y_2, that's going to help us preserve these particular equality. The first inequality here, relies on our setting for dual functional constraints. Then we do some arrangements. We are going to say y_1 x_1, y_1x _1 is here, right, and y_1, x_2, y_1 x_2 is here. We pretty much do some arrangements. Here we need to make sure that our dual variables their sign are set reasonably. Here, when we are doing just some arrangements, actually list may be modified to an equality. Because nothing really changed. We simply rearrange terms. But of course it doesn't matter whether we write it as equality or greater than or equal to. From the second to the last. Now, what do we have? Because we know x_1 plus 2x_2 plus 3x_3 is greater than or equal to 6. What we need is to make sure that our y_1 should be none negative to preserve less the sign. On the contrary, because your four is greater than or equal to that thing. Your four is greater than or equal to this term. If you want to have this greater than or equal to relationship, your y_2 must be non-positive. Everything makes sense and everything has its reason. Any single rule you said to your dual program has a reason, has a role. It is because that we collect all of this so that we are able to get this bounding condition. Here is a table that I would use to summarize all the rules. Up to here, this is a summary or this is a memorization. For me, I don't typically memorize this. I just use the intuition, I just introduced to think about all the things. But still you may find this useful when you are a beginner in this particular thing. If your primal is a maximization problem, once you see a corresponding thing, take a look at its property and then you know in the duo how to set the corresponding thing with a different sign. We saw corresponding sign. For example, for your maximization problem if you have a non-negative variable, you are going to have a greater than or equal to constraint in the dual. If your primal is a minimization problem and you have, for example, an equality constraint, that tells you that in your maximization primal, that variable should be unrestricted in sign. Whenever you need to find your duo, take a look at whether you are talking about a maximization problem or a minimization problem to determine that direction for you to move. For a maximization problem, go from left to right, for a minimization problem go it from right to left. Duality actually shares a lot of interesting and useful properties. For example, it is unique and also it is symmetric. I'm not going to prove this to you, but actually you are able to prove this by yourself. The statement is that for any primal linear program, there is a unique dual. I think it makes sense, right? Because according to the way we construct the duo, you have no other choice. It must be like that. Then the duo of the duo goes back to the primal. I think you just need to try a few examples and then you will see this is definitely true according to the way we construct the primal duo pair. The last page are just two examples that I think I will leave this to you as your own exercise. When you have a minimization problem, you get to a maximization thing. For example, for this minimization problem, if you see a greater than or equal to constraint, this directly tells you that that corresponding duo variable must be non-negative. Why is that? Because whenever you are doing all the things, if you say your y_3 is here, y_3 would be multiplied with this particular left hand side and this particular eight. What we want is that all the combinations we get eventually gives us a lower bound. We want that this particular thing has a lower bound of whatever we may obtain here. Somehow to maintain that lower bound thing, we need to make sure that your six and your 8y_3 is low, and that means your y_3 must be positive or non-negative till two this greater than or equal to constraint.You need to try this for a several times to make sure that you know how to do all the explanations. The thing that you are considering lies at the right-hand side of a greater than or equal to constraint. Well, that means our y_3 must be non-negative. You need to be able to fluently say all of these so that you really know why we construct a list dual program and how the older rationale behind is constructed. This of course still gives you a question is about, what is the whole point of doing all of this? It seems that we are just looking for upper bound and a lower bounds. Not really true because later we are going to tell you the relationship between primal and dual actually gives you a lot of theorems, a lot of theories that characterize the optimal solution for a linear program. Later we will see how is that.
