Next, let's talk about our second topic is about the graphical way to solve a linear program. Pretty much this is something that I believe many of you already know. Maybe you would quickly skim through the material, skim through the PowerPoints or PDF and then if you think you are comfortable, you may skip this part or otherwise I will still talk about this particular thing somehow quickly. Suppose I have a linear program. In general, there can be thousands of decision variables, hundreds of constraints, but that's assumed I only have two decision variables for a while. I may solve this problem through a graphical approach. Let's use this particular example to show you the process. I want to maximize 2x_1 plus x_2 subject to 1, 2, 3, subject to three inequality constraints. They are functional constraints and both of my decision variables, x_1 and x_2, they should be non-negative. Let's see how to do this. The step one is to draw the feasible region. I have three functional constraints. These three functional constraints may be depicted on your two-dimensional plane. X_1 less than or equal to 10 is here, and x_1 plus 2x_2 less than or equal to 12 is here. x_1 minus 2x_2 greater than or equal to negative 8 is here. I hope I don't need to talk about how to depict these lines. Find two points that are on the line and then connect them. Pretty much it, that's the way. Both two variables, they should be non-negative. Altogether, this is your feasible region, this is something we can do. Then we should take a look at the objective function. We want to draw some isoquant lines. They are lines such that for all the points on a line, on the isoquantum line, they share the same objective value. When you are talking about profits or when you are talking about cost, they may be called as isoprofit line, isocost line, and so on and so on. In general, we call them isoquant lines. Or in economics we are sometimes calling them indifferent curves, indifferent lines. Back to this example, how do we do that? We are trying to maximize 2x_1 plus x_2. We know this point 2,0 and at this 0,4, they corresponds to the same objective value. So we connect these two lines by dotted lines or dashed lines. This is an isoquant line such that all the points on it share the same objective value. There can be multiple isoquant lines, but I guess you agree that they will be parallel to each other. I depicted two for you. Once we have those isoquant line up obviously we want to push them somewhere so that we may get improvements. I want to maximize this particular thing. I may compare these two isoquant line. On the isoquant line one, I'm going to get 4 as my objective value. For isoquant 2, so they are 4,0 or 0,8. We can see that its objective value is 8. So 8 is greater than 4. I want to get improvements. I want to maximize my objective value. I somehow need to push toward the right or towards the top. For a maximization problem, I want to increase my objective value, or for minimization problem, I want to decrease my objective value. I may identify this direction either to the right or to the left, either to the top or to the down and then now I should push the isoquant line because I want to keep finding better solution, better solution, better solution until I cannot do it anymore. I want to push it to the end of the feasible region. From this example is here, right? I push it toward the end until I hit this particular corner. I would stop when any further step makes all the points on the isoquant line infeasible. If that's the case, that simply tells me, okay, I should stop because I have no more resources. I have no more way to improve. This is the last position that I should stop. If that's the case, that's actually an optimal solution. There's no way for you to find a better isoquant line with a feasible point on it, then this one is optimal. To obtain it's numeric value we should identify the binding constraints at the optimal solution we just obtained. Maybe is here, then we know the tool binding constraints are here. Sometimes you have more than two binding constraints, but typically you have two. Sometimes you may also see that if your isoquant line happens to be parallel to some of your constraints. Maybe, you will see several points all having one binding constraints and they seem to be optimal. If that's the case, then still you are going to have some corner points that have two constraints binding at that optimal solution. Anyway, you should find at least two. If you have three, you have five, pick any of two. If you have only one, move to the left or to the right a little bit until you may find two. Once I have two binding constraints, what should I do? I know for this optimal solution that two constraints are binding. If they are binding, I may set them to equalities, instead then two equalities, and then solve this linear system. Because my optimal solution must satisfy these two equalities. Then I may use a high-school algebra or possible ways that you learned to solve this problem. For example, here, we may quickly see that an optimal solution, I should say a unique solution to this system is 10 and 1. X1 is 10, x2 is 1. That's going to be an optimal solution for our linear program. Pretty much when we want to solve a linear program, we do some search until we may find a linear system of equations so that the unique solution for this one changes or it can be converted to an optimal solution for your linear program. That's the idea. For example, maybe you want to use Gaussian elimination to do all the solving things. I'm not going to go to the details. If you have learned Gaussian elimination, you know whether we are doing well trying to, in each iteration eliminate some coefficients. They eventually get 10 and 1 as our values. If you haven't learned it never mind because we don't use it in this particular module. Basically, what you should do is to use whatever way you have to find the values for x1 and x2. The last thing to do is to plug in your optimal solution back to your objective function to get your objective value, in this example is 21. As a beginner, sometimes we get confused about optimal solution and the objective value. Whenever we are talking about solution, we are talking about the x values, the values of your decision variables. On the contrary, when we are talking about objective value, I hope we all know what's that, is the outcome of plugging in all your decision variables value, into your objective function and then the value you obtain. If a problem asking you to find an optimal solution, write down the values for your decision variables. If I ask for objective value, that's the other thing, don't get confused about these two things. Basically, that's the whole process of solving a linear program when there are only two variables. When we are pushing the isoquant lines, we mentioned about when to stop or where to stop. Intuitively, we always stop at a corner. Sometimes we stop at a corner, for example, here, if we are pushing along this direction, then eventually we stop here. We get to optimal solution one. Sometimes we are pushing along another direction, then eventually we get another optimal solution, is also possible. As we mentioned, that our isoquant line is parallel to a line, I should say constrained. In that case, you may see that there are several possible ways to define an optimal solution. Then as we mentioned, you must be able to find at least one point where you still have two constraints binding on this optimal solution. The fact is that if you have a linear program where there is at least one optimal solution, then there is at least one optimal solution lining on a corner. Is this intuition still true for more than two variables LP, then result is yes. Think about some three-dimensional linear program. You push, you stop until you hit a corner. Pretty much that's right. You will have no way to imagine about four-dimensional, eight-dimensional, but maybe, you may convince yourself that indeed this would be correct even if we are at a higher dimensional. We would not go into details about proving these things mathematically or we don't need to do that. If just want to apply linear programming, all we need to do is to trust and believe in this fact. Many mathematicians, they have proven this. All we need to do is to trusting this fact. We don't need to worry too much about the definition of corners. We don't need to worry too much about why this is true, at least in this particular module, we don't need to worry about that too much. That's pretty much how to solve a problem, a linear program with graphical approach when it is possible. Hopefully through this process, you also agree that for linear programs, we are always pushing until we hit a corner or say it in another way. If we look at it from the management perspective, that's somehow means if you are trying to identify an optimal solution for a linear program that must be restricted by some constraints. It is because that you have constraints so that the problem is worse off time to solve. You have a lot of things to do, but you have limited resources, you have limited amount of time, you have limited budgets. That's why you need to solve the problem. You need to allocate your resources. You need to somehow deplete some resources so that, that plane is an optimal solution. So that's some properties that we should all agree with about linear programming.
