Chapter 5.4 - Simplex Method

0:08 in the last lecture we talked about linear programming and I sketched out how linear programs roughly work another words essentially how we optimize we introduce essentially extra variables or slack variables in order for us to actually solve a constraint optimization problem where we have linear constraints and a linear objective function so I want to talk about the Simplex method which is a Simplex method is basically the

0:38 underlying algorithm of how the linear program works so I didn't really show how the linear program works I mostly highlighted how we set it up but then the actual finding of Solutions in other words once you find a feasible solution how do you improve the feasible solution and you walk yourself from one feasible solution to another where you improve your objective function that is related to What's called the Simplex method so this is the entire idea of the Simplex method is going to

1:06 take solutions that maybe one feasible solution we have and get me to another feasible solution and I want to be able to improve as I do this okay so remember here is our linear program here's how it's set up and structured the important observation here is that I have n variables I'm going to try to find in other words I have n control variables but I have M constraints so in many ways this is like an underdetermined system because I only

1:39 have M constraints on these n variables it means I have in some sense an infinite number of solutions available to me due to this sort of undetermined system scenario and so you know how I'm going to find the best solution get that I have an infinite number to work with and so we're going to find a a way to do that using what's called a Simplex Tableau or which you show here in a moment okay so first of all we start

2:08 with this and what we're going to do is we're going to write this in a form since I actually have M constraints here what I could do for these M constraints is just simply say look focus in on M of those n variables let's call them X1 right here so we have X1 through X of M and then what I'm going to do is say well I have x one of the ways I can think about it is X1 is plus some set of

2:33 variables using m+1 M plus2 and all the way n so in other words from the N plus first variable to nth variable in many ways I could find a feasible solution where I just lock in X1 through X of M and then the x of m + one through X of n are now essentially free for me to play with because it's an underdetermined system and I have an infinite number of possibilities I could simply play with

2:59 these if I can satisfy everything with the first M variables and then that gives me freedom to do what I want with the other remaining n minus M variables and the way we're going to do this is we're going to use essentially something like a gaussian elimination it's actually more like Lu decomposition that we' done previously to find a best way to represent this solution so the way to think about it is in this variable set here we have a set

3:27 of basic variables those are the first M and non-basic variables which is M +1 to n so the basic variables one way to think about it that's all I need to satisfy the constraints because there's M constraints and the non-basic variables are free for me to play around with and so what we're going to do is figure out how do I in fact play around with these so that I can actually improve my minimization of the objective

3:55 function remember these are all feasible Solutions but I'm trying to give you the best feasible solution that has the lowest that actually minimizes my objective function okay so this is just in other words this is related to the constraints and what we're now trying to focus in is how do the constraints how can I pick those constraints to minimize the objective functions so we're going to rewrite this in gy elimination form and we're going to start off initially by just simply

4:23 saying all the variables X of n + 1 to X of n are zero because it's an underdetermined system I'm just going to go ahead and do that remember I'm looking just for a feasible solution at this point and this is a basic feasible solution in other words it has as many zeros as I can possibly put in there which is all the extra constraints remember I have M constraints to satisfy n variables and so I can

4:49 pick n minus n of these variables do zero and then I make the work of X1 through X of M do all the work of satisfying the remaining constraints of that linear system so that's just an N byn at that point that becomes an M byn system of of equations and I have these M variables control variables to satisfy it so the way we're going to actually do this is create what's called a Simplex Tableau I'm going to sort of in some

5:17 sense this is very much when you put when you do Gan Elation gussian elimination right you put it into sort of an abstract form of this type and this is exactly what we're going to do simp in the Simplex Tableau we're going to think about our variables X1 through X of M and then these are all those are the basic variables and those here are the non-basic variables and they have some values and they're going to satisfy

5:41 the constraint which is over here on this side over here okay so so one way to think about this is if I rewrite this for each of the variables in this underdetermined system from the first equation X1 is equal to whatever the right hand side is plus a sum of all my non-basic variables in other words whatever they want to pick them to be X2 Y2 minus the sum of all the other variables as well this is

6:07 sort of this un undetermined system with an infinite number of solutions but really what I want to do is not just think about solving the constraints now I want to minimize the objective function so I can always write now now that I have this feasible solution I can write my function f that I'm trying to minimize as has a function of these variables X1 X of n but of course I now have a different representation of these

6:36 variables and particular when I start looking at I have the objective function F0 which is what it is in terms of the basic variables and then the non-basic contributions as well okay and so the idea here is in terms of the objective function is written in terms of these non-basic variables and what I really would like to do is figure out can I use the non-basic variables to help me lower this F okay and this gets right down to this

7:07 theorem about the Improvement of basic feasible Solutions so the goal here is if you're given a non-degenerate basic feasible solution you can read it here it's it's just it is important but of course what we're really trying to aim for is that there's a theorem here that guarantees that essentially I can basically start off with a feasible set of solutions and constru construct a next feasible set of solutions and there's a condition a theorem under which I can find the

7:34 optimal condition optimality which is if there's some basic feasible solution that satisfies C of Jus X ZJ X of J greater than zero for all the JS then the solution is in fact optimal and this is actually what we're going after we're going to do an iterative procedure to get towards this it's actually not even going to be iterative procedure you'll find it's going to be very much like L composition we're going to just basically keep Transforming Our

7:59 variables into the be the best feasible solution possible so let's go back to our Tableau and for this example here the way we've structured it here is you know our non-basic variables our basic variables and what we're going to do essentially is very much like what we did in Lu we're going to try to actually make these zeros we're going to try to use our non-basic variable X4 in such a way to improve the objective function so the

8:28 idea here is to do something like Gan elimination to make these zeros so this is not that hard to do in many ways because right now the objective function if I look at what we have here the objective function is I add up to all the variables this is V basic variable X1 X2 X3 and right now I'm starting off with the the basic variables there's three of them the non-basic variables is just starting with zero remember I have

8:53 a I have a feasible solution with this and the function f takes on a value of eight so my goal now is to figure out how do I use these variables to improve the eight okay and so the way I'm going to try to do this is sort of through gination I'm going start off with the variable X4 then move to X5 and so forth and so you can sort of basically compute how you're going to do elimination of

9:19 of the subsequent rows and you're using you're really concentrating on the fourth variable to do row elimination just like we would in Lu or G elimination and this produced is then the following so this looks a lot like Lu because in some sense this constant comes up now shows up here remember this used to be just an identity what shows up here is essentially a factor that needed to eliminate this to be zero this factor is what eliminated this to be

9:46 zero and now I have this new form this is the new Tableau so now when I look at my variables in this thing I've no longer X4 to be zero in fact now X4 is two and I've made X one Z so this is a new basic solution feasible Solution by this transformation and then this new basic solution f is six and now I go through it again and I try to eliminate again so you still see

10:16 I have only three new variables so in other words I know I can get away since I have these three constraints with three nonzero X's I I just don't know which ones they are and so what this is doing through this Tableau structure is finding out which three variables can I use that are nonzero that actually lower this F so it's a basic feasible solution and I'm progressing from one basic feasible solution to the next to the next to the

10:45 next in a essentially it's not even sort of an iteration scheme it's just a a it's something like Galaxy elimination I'm just changing rows and columns and elimination and now you have this F is equal to 6 so this sets up an archit Ure for walking through feasible Solutions and marching you to the best optimal feasible Solution that's the basic optimal feasible solution this Simplex method is the heart of the linear program so it is a Progressive

11:15 technique just walks you to the solution base of these constrained optimization problems so it's a powerful technique it's the underlying algorithm underneath the linear program and it's built into python mat lab almost all the programming languages so easy to use by you and you can see at least how it kind of works in practice