Okay, let's continue. So previously, we have mentioned a few examples and they are all widely used and they are important, they showed us about the nonlinear programming formulation. And then we're going to move on to linearization techniques. So pretty much we want to give you some functions or some situations that you do see nonlinear functions. But there is a way to linearize them and in many cases through the help of binary variables, okay, so that's the how to do that. Let's start with this application or start with this example. So basically what we want to do is that we want to allocate $1,000 to two persons in a fair way. So we adopt the following measurement of fairness. So the fairness is defined in this way. The smaller the difference between the two amounts, the fairer the allocation is, okay? So obviously the answer is to give each person 500. But we want to ask, how may we formulate a linear program to make this happen? So that's the what's this. Let's say we want to choose xi, and xi is the amount allocated to person i. So maybe I would formulate this program. So when I do this, I want to minimize the difference subject to the sum would be 1000, and that's all I have. But then if I do this, obviously this formulation is not correct. Why is that? Because with this formulation, obviously, my best solution is that x1 would be 1000 and x2 would be 0, that difference goes to negative 1000, which is optimal. But actually, this is not fair at all, right? Because the way we formulate the difference is not so good. What we actually should do is that we should introduce, for example, absolute function here, okay? Either x1 is greater than x2, or x2 is greater than x1. We should always that the greater one to minus the smaller one, okay? So if that's the case, then this seems to be a much better formulation. However, the absolute function is nonlinear. Why is that? Because pretty much it looks in this way. This is x, this is your absolute value of x. If you are having 5, it goes to 5. If you have -3, it goes to 3, right? So your absolute function, absolute value function is nonlinear. So we cannot just leave a nonlinear function here. That does not give us a linear program. We want to ask, is it possible to linearize the problem as a linear program? Of course, there's a way, otherwise it cannot be an example, right. So, let's see how to do this. So the first thing is that, okay, I don't like that absolute value function. So I'm going to replace it by another variable called w. So I now want to minimize w. And I need to make sure that w is still equal to this absolute value of this difference. So from here to here, actually I didn't change anything. I simply called this difference, the absolute value of the difference a min, which is w. And then there's a key step. I'm going to argue that changing this equality to greater than or equal to does not change the program. Well, let's see why is that. Suppose, we change this to greater than or equal to, and we do some observation about this program. We would see that because we are minimizing w, okay? When we are minimizing w and w only appears in one constraint, and w is lower bounded by the right hand side. Then in this case, there cannot be no optimal solution where w is really greater than the right hand side, okay? As long as this is true, it cannot be optimal. Well, why is that? Suppose you have an optimal solution, saying that you have w, x1, x2, and if it satisfies this particular strict inequality. Then all you need to do is to further decrease w, there is a room, right? So, your original solution cannot be optimal. If you have an optimal solution, obviously, that optimal solution must make this inequality binding. And if that's the case, it has nothing different from saying an equality there, all right? So the idea is important and idea is simple. If you put it as an inequality, then at an optimal solution, this must be binding. So it doesn't really change your optimal solution. From here to here, the feasible region of course is different, but the optimal solution is not changed. So now, we also know that for this particular thing, the absolute value function can be expressed as the maximum of two things. So maybe you would like to review your graph. So this is x, this is the absolute value of x. Why do we say it is a maximum of two because pretty much this is your x, this is your -x. Okay, and your absolute value function is this part. Does that make sense? So it's always taking the maximum between the two functions. That's why it takes a maximum there. So suppose that's the case now, because we are talking about x2-x1. First we have x2-x1, and then we have x1-x2, the absolute value function is taking the maximum of these two, makes sense. So if that's the case, then let's take a look at the formulation. Pretty much we will say w should be greater than or equal to the maximum of these two, then I actually can do this. I'm going to say then that means w should be greater than or equal to the first term, and w should be greater than or equal to the second term. So suppose the left hand side is true. In this case, your w is greater than the maximum of these two, then w naturally needs to be greater than or equal to either one. If w is greater than or equal to either one, then of course, w is greater than or equal to the maximum of these two, right? So this is again, something we can do. So now, we finally reach a formulation with no maximum function or no absolute value function. All we need to say is that we want to minimize w, such that w is greater than or equal to x2-x1, and w value is greater than or equal to x1-x2. So somehow one of them would be greater, and then w would be lower bounded by that greater amount, w becomes the absolute value of that two amounts. That's how the formulation makes sense. So lastly, maybe we may try to solve this LP and then really show you we would get a one-half, one-half allocation. Well, that's not too hard. You have one, two, three decision variables. But actually, you have an equality constraint that always allows you to remove one variable, for example, x2. So we're going to replace x2 by 1000 minus x1, then our formulation becomes this one. Now maybe we may use graphical approach to solve this problem. So let's say I have x1, let's say I have w. So x1 must be non-negative, w is unrestricted in sight. And then all I need to do is to plot these two particular functions. So if my x1 is 0, w would be greater than or equal to 1000. Or if x1 is 0, then w will be greater than or equal to negative 1000. So that's one part. Or if my x1 is 500, I will see the right hand side becomes zero, right hand side becomes zero, so it's here, okay? So my first constraint is here, my second constraint is here, and we all want w to be as large as possible. So, I mean regarding the constraints, so the feasible region is this part, okay? w is lower bounded by these two constraints. So once we know all of these, if we want to minimize w, then the best thing we may do is to reach here, because we want to minimize w. So my ultimate solution is here which is 500 and the 0, the difference is 0, I'm going to allocate 500 to player one, and then player two also get 500, world peace.
