Let's try more examples. Suppose our variables are no longer all non-negative. Let's say, we now have less than or equal to variables, less than or equal to zero, and we have unrestricted in sign variables. Supposed that's the case, still, we should try to find y1 and y2 to combine these two constraints, right? After the linear combination, we get this. Then now, what's interesting is that instead of having four less than or equal to 2y1 plus y2, actually, what we need is the opposite. We now need four to be greater than or equal to 2y1 plus y2. Why is that? Because your x2 is actually non-positive. You know your x2 would be negative two, negative five, negative whatever if your four is less than or equal to 2y1 plus y2. You actually cannot make sure that the second expression is an upper bound of the first expression, because your x2 is non-positive. What you need is to make this a smaller numbers, smaller than four, this is something you need. Then lastly, your x3 is unrestricted in sign. If your x3 can be positive or negative or zero, if you want to make sure that the second expression is an upper bound of the first expression, you need to make sure that your 3y1 plus 2y2 must be exactly eight. Otherwise, if this number is greater than eight, it's possible for me to make x3 very small, a negative number to reverse all the things. Pretty much because the coefficient comparison happens when x3 can be anything. If you want to have this less than or equal to, you really need to make sure that your eight is exactly identical to 3y1 plus 2y2. So this somehow tells us an immediate result. According to the sign of our variables, we will know how to compare the outcome of linear combination and the objective coefficients. The primal and the dual pairs would be changed a little bit. For the primal, you'll see that the variables are somewhat different, their signs are different. For the dual, everything pretty much the same. It's just that, these two things would be changed. If you can see that we have the previous example, this example, actually, we may make some conclusions or make some findings. First, some observations are here. If your primal is doing a maximization, then you'll try to minimize the upper bound so your dual would be a minimization problem. Those primal objective values would become your right-hand side values for constraints, because you'll need to make sure that the outcome of the linear combination has some connection, has some relationship with the original objective coefficients. Then, your primal right-hand sides would become dual objective values, because this is the place for you use y1 and the y2 to do the linear combinations, so you want to minimize that. That's why in your dual, you see the numbers as the primal right-hand side. Moreover, what we also have is the following. We would know that if your primal has a greater than or equal to variable, I mean non-negative variables, then in your dual, you're going to have a greater than or equal to constraint. If your primal has a non-positive variable, in your dual, you will have a less than or equal to constraint. I hope you really don't need to memorize these. I hope you really know why it is because of the derivations we did last time in the previous page. If you have a free variable, you will have an equality constraint. In many cases, this is the easiest to memorize. But I hope, again, you don't need to memorize it, you really know why it is the case. Maybe after these observations, you would ask your next question. Here, we have less than or equal to constraints. What's going to happen if we have greater than or equality primal constraints? Let's take a look. Let's modify our constraints a little bit. Now, we have greater than or equal to constraints and inequality constraints. Still, we have y1 here, y2 there, we'll still do the linear combination. Now, y1 multiplies this left-hand side, plus y2 multiplies this left-hand side. What we want is still, we want 6y1 plus 4y2 may be an upper bound for whatever you have at your left-hand side. If that's the case, now, let's think about the following thing. Six is here, this coefficient is here. If you know six is less than or equal to the left-hand side, this immediately tells you if you want to have this less than or equal to condition, then your y1 must be non-negative because this is greater than that. Your y1 must be, for example, negative, so that then you'll still have this less than or equal to relationship. Then similarly, here, what you are doing is to compare four and then this particular value. In that case, because these two sides are equal, so if they are lessened, it doesn't really matter what's your value for y2. It eventually cancels each other. If that's the case, then your y2 can be of any sign. Now, we have the primal and the dual linear programs. When your right-hand side becomes greater than or equal to, your dual variable now becomes less than or equal to zero. When you have an equality here, you give unrestricted in sign variable. This somehow completes the discussion about constructing a dual program. The rules here are: for the primal less than or equal to constraint, our dual becomes a non-negative variables. For greater than or equal to constraint, our dual becomes non-positive. If our primal constraint is equality, then your dual would become a free variable.
