Theodore Motzkin

Transcription

In this video i'm going to summarize the ideas for solving systems of linear inequalities. We actually have worked through a few examples of solving linear inequalities using a method which is known as Fourier-Motzkin elimination method. Well the method is based on the following observation: Supposed that I have a system of linear inequalities. Say every inequality is greater than or equal to. Now, pick a variable. Put that on the left hand side and everything else constants and other variables on the right side. So rewrite our system in the following manner, and we normalize the coefficients of x so that the coefficient of x is either 1 or -1. So my system looks like this. Now say I have p of these constraints up here, q of these in the middle and r of these. So these r inequalities do not have the variable x. They may have some other stuff. To eliminate x, all we need to do is to make sure that each of these lower bounds from one of these p inequalities is at most the upper bound given by one of these q inequalities. Remember that -x greater than equal to something is the same as saying x is upper bounded by the negative of this right hand side over here. Alright. so we want every upper bound to be at least every lower bound. And so combining these p and q inequalities, what we get is p times q new inequalities without x. And of course we have to copy these over. If we solve this system of linear inequalities over here without x, then we get extend that solution by finding a suitable value for x that will satisfy the original system. And conversely, anything that satisfies the original system, if we throw away the x value, will satisfy this new system of inequalities that is without x. And that's the key to the Fourier-Motzkin elimination method. So in summary, what you do is if you want to eliminate a variable, first rewrite the inequalities so that that variable you are interested in is on the left hand side, everything else is on the right hand side, all the coefficients of that variable are either 1, -1, or 0. And for each inequality in which the variable appears positively you pair it up with an inequality in which the variable appears negatively. So you have p inequalities of the former and q of the latter, and you'll get p times q new inequalities. If the new system cannot be solved by inspection, you can apply this method again. Pick another variable and apply the method. And you can actually do this until you get down to one variable, in which case it is very easy to see if there is a solution. We can now use this to prove a fundamental fact in linear programming. In linear programming, there's a theorem that says: If you have a linear programming problem, it is not infeasible, that means there is a solution that satisfies all the constraints, and if it is not unbounded, that that means that if you have a minimization problem, the objective function value cannot be arbitrarily negative, then you must be able to find an optimal solution. And the way we prove this is as follows. So first of all, we can assume without loss of generality that we are looking at a minimization problem that looks like this. Well, the reason is if you have a constraint that looks like this a transpose x equal to b, well you can rewrite this as a pair of inequalities. Satisfying this equation is the same as satisfying these two inequalities at the same time. Now if you have a less than or equal to inequality, you can turn it into a greater than or equal to inequality by by multiplying both sides by -1. So that means we can assume that all our linear constraints are greater than or equal to. And we don't have to worry about maximization problem because maximizing is equivalent to minimizing the negative of the function. Let's say we're given this problem. Now we have seen an example in which we can convert this problem into something that has only one variable in the objective function. Effectively, minimizing z subject to z greater than or equal to c transpose x Ax greater than or equal to b is equivalent to our original problem. If this new problem has an optimal solution, then that solution will give us an optimal solution for the original problem. And if this is infeasible, you know the original problem is infeasible. If this new problem is unbounded, then the original problem is unbounded, and so on. So basically, these two problems are equivalent. Now, what I'm going to show is that if we look at this new problem only one of three things can happen. uh... there is no solution, the problem is unbounded, or that the problem has an optimal solution. So let me call this problem P'. Solving P' amounts to finding among all solutions to this system, one that has the minimum z value if it exists. So that's our goal, right? Solving this minimization problem is basically looking at that all the solutions to this system, find one that has the minimum possible value for z. Because, it is just a system of greater than or equal to inequalities. We can apply Fourier-Motzkin elimination method to eliminate all the variables except z. And what do we know about this final system? Well, it has no variable other than z. And every solution for the original system here, the z value must satisfy that final system. And if we have a z value that satisfies the final system, we can extend that to a solution to the original system. If we use Fourier-Motzkin elimination method to eliminate all the variables except z, the final system will tell us one of three things: it has no solution, in which case P' is infeasible, there's no inequality of the form z greater than equal to gamma, well that means z can be as negative as we want, in that case the original problem is unbounded, or there are inequalities of this forms: z greater than or equal to gamma. Now they might not be just one of them but there might be a bunch. So if they are a bunch of them, well there are only finitely many of them because Fourier-Motzkin elimination method cannot introduce an infinite number of new inequalities. So in the end if we do have something that says that z greater than or equal to gamma, we might have a bunch of these, so we might end up with a number of these, maybe k of these, all we have to do is we pick z to be the largest among all these gammas. Then well uh... the largest gamma gives us a lower bound that z has to satisfy and we cannot pick anything smaller because what it has to satisfy z has to be at least that value, right? So if the problem is not infeasible, and is not unbounded, then you will a bunch of these inequalities and the maximum value on the right hand side of these inequalities will be the optimal the optimal value for P'