Following the previous idea, now we actually have more. Now we are able to character our dual optimal solution. What does that mean? That means, as long as we have solved our primal problem, then we are able to obtain a dual optimal solution directly. This is very interesting result. Basically, it says, well, if you have a problem, if you have a linear program, you call it the primal, you have an optimal solution for that. If you want to find a dual optimal solution for the dual, you don't need to solve the dual program. You don't. All you need to do is to look at your primal optimal solution and do a little bit things, and then you get your dual optimal solutions. This again tells us that you may say that the primal and the dual problems, they are equivalent because once you solve A, you then solve B. Then see how to do this. Consider a pair of linear programs. If x bar is primal optimal given a basis, in that case, once we know what's the basis, what's the optimal basis, then this equation is going to give us a dual optimal solution. Your dual may have multiple optimal solutions that's possible. But anyway, this is going to be one dual optimal solution, C B transpose A B inverse. The interesting thing is that this is not your first time to see this, c_B transpose A_B inverse. Obviously you'll have the memory. It is part of your reduced costs equation. Let's how to understand this. Well, first, B is optimal. If B is optimal, then the reduced costs would be non-negative. There are several numbers here, thus the reduced costs for all those non-basic variables, they would all be non-negative if your B is really optimal. Then let's say, c_B transpose would be c_B transpose A_B inverse A_B, because this is nothing but one inverse, multiply the other. If we express c_B transpose in that way, now let's take a look at this particular thing. Consider the quantity y bar transpose A. So y bar is defined in this way. y bar transpose A, if you replace y bar by this one, you are going to get a c_B transpose A_B inverse A. Here, A is a matrix that maybe decomposed into A_B and A_N according to your basis under the set of non-basic variables. You may replace A by A_B and A_N. If you do that, then this multiplication becomes two parts. You'll have c_B transpose A_B inverse A_B and you'll have c_B transpose A_B inverse A_N. Your c_B transpose A_B inverse A_B, becomes c_B transpose. That makes sense because you have this one. A_B inverse and A_B, they cancel each other, and then your A_B transpose A_B inverse A_N can be related to your c_N transpose. This particular quantity is greater than or equal to your c_N transpose according to this one. That's how you get this inequality. That's how you get this greater than or equal to. Then immediately you may see that this particular thing gets to your c transpose. What does that mean? That means this quantity y bar satisfies the fact that y bar transpose A greater than or equal to c transpose. That's a condition you need for feasibility. You y bar can be shown to be dual feasible if you define y bar in this way. Then your y bar transpose b is c_B transpose A_B inverse b, and you know what's that, that's c_B transpose x_B, because this guy is your x_B, then it goes to c transpose x. According to our previous condition, this immediately tells you that given your x bar with basis B, if you are y bar is constructed in this way, then y bar would be feasible and having the same objective value with your c transpose x bar. In that case, you're going to say that, "We're going to have this particular condition". Their objective values are the same, in the first, they are both optimal according to the previous one. This can prove that y bar is optimal. Here more precisely which you say this is x bar and this is x bar. This pair of x bar and y bar, they have the same objective value that shows they are both optimal and it completes this proof. Next, now we are able to consider this strong duality. Now, the fact that this guy is dual optimal, help us to have this condition called strong duality. Consider a pair of linear programs that are primal and the dual pairs, if you have x-bar and y-bar, if they are primal and dual optimal, then we know their objective values would be identical, or the other way, if you know they are primal and dual feasible, and they have the same objective values, then they are primal and the dual optimal. This is an if and only if condition. Strong duality pretty much says, well, when you have two programs and they promote your pairs, their objective values must be identical. The bound provided by your dual program must be tight in some sense. If you are able to find two solutions, their objective values are the same and they are feasible, then they are optimal. To prove this if and only if statement, note that the first part where you have this condition and you have that condition, this implies the optimality. This has been done by Proposition 3. Then let's consider the other way. Suppose that you get c_b transpose a_b inverse, and you know it is a dual optimal solution. That means the objective value must be c_b transpose a_b inverse times b, because that's pretty much y transpose b. Given that this was going to be equal to the primal optimal objective value c transpose x, according to our discussions in the previous slides. Now, as long as your y-bar is dual optimal, then we know our y-bar transpose b is going to be c_b transpose a_b inverse b, because y-bar k can be considered as c_b transpose a_b inverse b. Then that's going to be c transpose x-bar. Pretty much you would feel that everything looks so similar because that's true, because they are all implying each other. Take a look at all of them and try to convince yourself that somehow this is an if and only if statement. Pretty much this is applying to all conditions. It doesn't really matter whether you have a unique optimal solution or multiple optimal solution. You always have strong duality for your linear programs. This has direct implication. Strong duality certainly implies weak duality, because strong duality says they are equal, weak duality says they are equality. Strong duality implies weak duality. Weak duality says there is a bound, strong duality says the bound is tight and that there's no way for you to get a better bound. All of this says that the primal and the dual linear programs, they are equivalent. Once you solve a, you get b immediately. Then this actually may be generalized to the three possible types of linear programs. If your primal has a finite optimal solution, we know your dual must also have a finite optimal solution, otherwise they cannot be equal. This is possible. Then once your primal is finitely optimal, there is no way for your dual to be infeasible or unbounded. There's no way. Suppose your primal is unbounded. Well, if your primal is unbounded, that means you may maximize your objective value to infinity. If that's the case, there is no way for your dual to have an optimal solution or to have an unbounded situation. In fact, there is no way for your dual to have any feasible solution. Because once you have a feasible solution, that provides an upper bound, but your primal has no upper bound, so the only possibility is for your dual to be infeasible. Lastly, if your primal is infeasible, then you don't really have a lot of information about the dual. You only know that it cannot be the case that your dual has a solution. If your dual has a feasible solution, there's no way that your primal has no feasible solution. There are two possible cases. Where your primal is infeasible, maybe your dual is infeasible, or maybe your dual is unbounded. Both are possible. We may provide many examples showing you that this is true, that is true, but I don't think we need to do that one by one. All you need to do is to understand that. Now because of all those strong duality things, as long as we know one condition, we know what happens to the primal. We actually have a way to predict what's going to happen for your dual according to this particular table.
