Okay, so pretty much we are done with all the basic concepts. Now the last two things that we need to do is for our simplex method to be able to deal with unbounded LPs and infeasible LPs. So let's see How may we do that So, somehow if we give you a problem and asked you to use the simplex method to solve it, we need to see whether an LP is unbounded, okay. So we need to first review when will be an LP be unbounded. If you have a feasible region something like this, that is unbounded and you may find an improving direction, along that direction you may move forever. Suppose that's the case for example here. If you want to move along this direction, then along this feasible direction feasible, improving direction. You may move forever. That's going to create a condition for us to see that your LP is unbounded. So, if we correctly understand this, then when we run the simplex method this can be easily checked in a simplex tableau. So let's use the following example to give you an illustration. So this is a maximization problem and we are going to add slack variables. So once we do that we now have slack variables, everything looks fine. So we have our tableau. So we're going to run one iteration because our negative 1, reduce cost is negative So we're going to enter X1, and we do some pivoting. We do the ratio test very quickly, we see 1 as our pivot, and then we do some pivoting we get to the second tableau. So for our second Tableau again, this should be entering and the X4 would be the only thing that we may do the living variable because the denominator if the denominator is negative, that rose should be eliminated during the ratio test. So once we do that again, we pivot at one, and then we get to our third tableau. In this particular tableau, there is one variable that can serve as the entering variable. And when we want to do the ratio test, the ratio test fails. What do we mean? We see that all the denominators are negative and we actually know precisely what does that mean. This is X3, so when we increase X3 by 1, that's going to increase X1 by 1. All right. And that's also going to increase your X2 by 1 half. So, it doesn't really matter whether it's 1, 1 half, or whatever. What's important is that if you see the denominators to be negative, that means increasing that non-basic value is going to increase your Basic variables, okay. And if that's the case, there is no variable that should leave. Increasing X 3 makes X 1 and X 2 become larger. There's no reason. Then to stop, and this entering X3 is an improving direction that is unbounded. You may keep increasing X3, increasing, increasing, increasing, increasing, there's no way to stop and then your problem is unbounded. So graphically, if you plot the feasible region and the iso profit line for that particular example, you would see that we first start at 00. 1 iteration 2 iteration. And after we reach 3, 2, we still find an improving direction. And along that direction, we may move forever. That's going to be an unbounded, improving direction. Diametrically both non binding constraints okay? You have 2 constraints that are non binding right. So at this point, the 2 non binding constraints one is this one should be non negative, the other one should be non negative. If you move along this direction, there's no way for you to hit those constraints. Geometrically we may say that these constraints are behind us, behind us along the direction. So there's no way to hit the constraints. So, generally, if we are talking about detecting unboundedness then we look at the reduced cost. For suppose we are talking about minimization problem, whenever we see any column in any Tableau satisfying this condition, such that your reduced cost is positive and all those denominator numbers are non positive, then we know this LP is our mandate, okay? Or if you talk about the maximization problems that we just showed an example to you, the condition says that your reduced cost should be negative, okay? Whenever you have an improving direction, which is indicated by your reduced cost, such that it is unbounded which is indicated by the Entering columns, then you have an unbounded linear programme. So it doesn't really matter how you start, as long as you keep running the simplex iterations and eventually at one point, you see this, you see a condition like this problem is unbounded and then you're done. You can conclude that these problems are bounded and stop running your simplex method. So that's how your simplex method may detect and report on boundedness okay.
