So next we're going to talk about several theorems regarding dualities. Pretty much we have introduced that when you have a primal program, you're going to have a dual program. It is unique and it has some relationship with your primal program. Previously, what we know is that the dual program provides some upper bound, lower bounds for your primal problem. Now we're going to tell you more. It turns out that all those primal and dual relationships may help us understand what are the conditions that a primal solution or a dual solution, what are the properties that those optimal solutions may have. Let's take a look. Duality provides many interesting properties. Today in this lecture, we're going to specifically talks about the standard form primal. Our primal program would be this one. You may say is a equality constraint greater than or equal to lets say it is a maximum problem. This is standard form problem. We already know that how to obtain this dual program. It's going to be a minimization problem. b goes to your objective values, c goes to your right-hand side, and you're going to see that for this equality constraint, it gives you unrestricted inside variables. Then lastly, for this maximization problem, because your variables are non-negative, so you're a minimization problem. You are constraints provides some lower bounds, it's greater than or equal to. Given all of this, we're going to illustrate those properties. Even though we have other primal dual pairs. Turns out that all the properties that we're going to introduce may still be obtained by other primal-dual pairs. If you are interested, you may try all the properties, all the proofs by yourself. Or you may just convince yourself that because pretty much all those linear programs are equivalent. Somehow, once we use this relationship to provide you the proofs, to provide you the theories, then for all others it all applies. Our first property is called weak duality. The weak duality thing is actually something odd, you already know it. The dual program provides an upper bound for your primal linear program. Of course, this is because there we're talking about a maximization problem. So we have an upper bound. If your primal is a minimization problem, your dual provides a lower bunk. So more precisely is here. For a linear program, it is defining one, is this one. If x and y are primal and the dual feasible, for any pair of primal dual feasible solutions. We're going to see that their objective values has some relationship. The primal is going to be less than or equal to the dual for any primal dual feasible solution. Lets quickly tried to prove this. As long as x and y are primal and dual feasible. Then your c transpose x is going to be less than or equal to y transpose a, x. Why is that? Because c transpose is less than or equal to y transpose a. This is the fact that y is dual feasible. It also needs that x should be non-negative. This is another property you need to have because you are primal is feasible. Given this and that, we're going to see that c transpose x is going to be less than or equal to y transpose Ax. Then Ax is less than or equal to b. In particular, we are having the equality. Once you replace x by b, you certainly will obtain the fact that c transpose x is less than or equal to y transpose b. For any primal dual pairs, as long as they are feasible solutions, we have this weak duality. We know its values is going to be that primal is smaller, dual is larger. This somehow help us to understand one condition. The condition is called the sufficiency of optimality. We now have a sufficient condition for optimal solutions. Let's take a look. Suppose x-bar and y-bar, they are primal and dual feasible. Here you have two feasible solution. It happens that your c transpose x-bar and y-bar transpose b, they are identical. If it happens that they are identical, then very quickly you may say they are primal and the dual optimal. What does that mean? You gave me a primal solution, you give me a dual solution. They are both feasible, and if they're objective values are the same, then you know, they must be optimal. Let's try to see this. Suppose your y is dual feasible. You know, you're going to have these weak duality condition. Then if it turns out that you have this pair of x-bar and y-bar, such that their objective values are the same. Then what does that mean? That means your y-bar can generate an objective value that is less than or equal to any feasible dual solution. This is because that your y transpose b equals c transpose x bar, and the c transpose x-bar is less than or equal to y transpose b for any y, this is how we show that y bar is dual optimal. For x-bar is pretty much the same. Graphically may be, you may understand this in this way. Suppose this is your primal problem. You try to maximize something. So you have c transpose x for any solution. For your dual program, you try to minimize something. So this is your y transpose b. If it happens that you get a solution such that y bar transpose b equals c transpose x-bar. Then it turns out that you are going t see y-bar is better than all your y and your x-bar is better than your x. Given all these conditions, now if we have a primal feasible solution, now we do have a way to show that it is optimal. Previously when you don't have this condition, you'll typically have no way to show that it is feasible. You need to take optimal, you need to take a look at, for example, is basis, Take a look at is reduced costs. Then even all the reduced costs are non-negative. You say, ''you sees optimal.'' Now we don't need to look at is reduced costs. All we need to do is to see whether we may find a dual feasible solution, such that their objective values are identical. If that is the case, then your x-bar would be an optimal solution. This provides us a new way to check whether x-bar is primal optimal.
