Next, let's talk about three different types of linear programs. So for any linear program, it must be one of the following exactly one of the following, okay? It is either infeasible or unbounded or finitely optimal. So when we say it is finitely optimum, it means there is exactly one, I mean there is one optimal solution, okay? At least one technically. And that optimal solution, of course gives you a finite objective value on that's why we say it is finitely optimal. So a finitely optimal linear program may have a unique optimal solution or multiple optimal solution. Very quickly we will tell you distinguishing an LP from these three situations is important. But checking whether it has multiple optimal solution is not so important. We will show you why. So first an LP may be infeasible, if it's feasible region is empty. So, one example is here, you will try to solve this problem and very quickly through some investigation. You may see that there is no way for you to satisfy all three constraints at the same time, okay? For example, if you look at these two constraints, then pretty much this is the only way for you to satisfy the two constraints. But the third constraint also requires you another thing, so it's impossible to satisfy all the things. Your program is invisible. And that's one thing another possibility is for your program to be unbounded, okay? And LPs unbounded if for any feasible solution, we may find another feasible solution that is even better. If that's the case then there is no way for you to say, there is an optimal solution. So for example, if we are trying to do this thing, we want to maximize X1 plus X2. So we want to move toward the, right or towards the top, and all your constraints are, bounding your decision variables from below, okay? So your decision variables, they have lower bounds, but they don't have upper bounds. Then there is always a case for you to improve. If you say 1 million 1 million is good, I give you 2 million 2 million. So this is an unbounded case, there is no optimal solution because you may always improve. There's one thing that is very important is that an unbounded feasible region does not imply an unbounded linear program. So feasible region is just a feasible region. A program also takes objective value into consideration, all right? So let's take a look at this example. The feasible region is still identical to the previous one, okay? So you have an unbounded unlimited feasible region, but you are trying to minimize this objective function. So you are moving toward the pattern towards the left, very quickly you hit a boundary, there is a point for you to stop. In that case there is an optimal solution. We won't say this is an unbounded linear program. Even though it has an unbounded feasible region, that program itself is not unbounded, all right? So unbounded problem, unbounded region distinguish them. They are different. So if an LP is neither invisible nor unbounded, we would say it is finitely optimum. The last thing I want to say about unboundedness is that, when we say an unbounded the feasible region does not imply unbounded LP. Maybe you would ask yourself whether it is necessary, whether it is necessary for an unbounded LP to have an unbounded feasible region. So, the answer is yes, if your feasible region is already bounded. There's no way for you to improve forever, right? So this is a necessary condition that that thing that is okay, but not so important is that. A linear program sometimes have multiple optimal solutions, like this particular example. All the points lining on this line segment are feasible and optimal, okay? So if the slope of the isoquant line is identical to that of one constraint or you say they are parallel then. It is possible to have multiple optimal solutions. But of course, it does not always guarantee for you to have multiple optimal solutions. It's very easy to just draw a few graphs and then you will see why. So, it's not the case that when you have parallel things, then you have multiple optimal solutions or the answer is no. So, collectively, first, a program is either infeasible or feasible depending on whether there is any feasible solution. Once you have a feasible program, either it is unbounded or it is financially optimal. In this case, you actually have at least one optimal solution either you have only one or you have multiple, okay? So that's the structure of all possible cases for a linear program, but I have to mention one thing is that when we are trying to solve a linear program. Or any mathematical program, mathematically or practically, we typically only want one optimal solution. There is typically no need to find all the optimal solutions, okay? Because in practice, you may only do one thing. Even if you have templates, they all look equally good. You only care about one thing you only just want to do one thing because that's the only thing you may do, okay? You may only execute one plant. So all those algorithms, solvers, whatever, when you input a linear program and asking them to report a solution to you. Pretty much they give you just one optimal solution and. Theoretically, we also don't really care about how to check whether a linear program or whether a mathematical program has multiple optimal solutions. For most cases, we don't care about it. So the important thing is still the first three. Infeasibility, unboundedness, and finite optimality, okay? Each linear program belongs to one of these three. So this part is important, whether there is multiple optimal solution, not so important.
