Let's take a look at what's needed to implement the simplex algorithm in Java. so there's a basic idea that's very straightforward and that's the first thing we have to do is just put everything in an array. and, that's going to be a simple thing to do. So, we have in this case our input is our recipe for a recipe for beer. and our profit which is our objective function. and then, all the slack variables. so we put our matrix A, our M equations, and unknowns in this part of the array. And then, we put our slack variables next to them and then the right-hand sides of the equations which is B. and then the initial values of the objective function, and we'll have to put in the constraints that everything's positive. and so that's where we start, it's a tableau, it's really a the matrices and vectors that we have of input to the problem, all put into a single array. And, and that's again just to reduce the amount of code you have to worry about. so the idea is that when we run the algorithm, what all we're doing is transforming a few entries in this array. and when we're done, this is the representation of the equations that we ended up with, with before. and what they tell us is the immediately, they tell us the value of the objective function. And not only that, they tell us what, how many barrels of beer and ale to make cuz we're sitting at point where we have our A and B A and B in the basis. And the, and the therefore, the slack variables are zero so it tell us immediately that we better make 28 barrels of beer and twelve barrels of ale. so that's the idea. we just work with the elements in this tableau. And then, all we're going to do is write the code to build the tableau and then to do the pivots. and this is very straightforward Java code so it's going to be 2-dimensional array, clearly. we have our number of constraints and our number of variables. so and so we'll write a constructor that takes the, the constraints. and the, then the array of five for the constraints and the coefficients for the object ive function as argument. so it picks out m and n, and so how big an array do we need? m + one n + n + one. So we just make that array and just fill it in from our argument. Fill in first the coefficients and then put the initial values of the slack variables along the diagonal here. Java rays are initialized to zero so we're going to have to initialize all of the others. and then, you put the objective function in the right-hand side of the constraint equations into the tableau simple as that. So, every one of those lines of that code is completely transparent so that's building the initial, initial values of the tableau. so now we have to find the column that is going to, we're going to pivot on. So, we're going to need to pivot on some entry in the array. It's going have to be in row p and column q in the rule we've given, which is called Bland's Rule. Remember, Bland is the one who wrote the classic Scientific American article about beer. So, we use Bland's Rule to just go through and look at the last row, which is the objective function and look for a positive. So that's all it does, it just goes through and looks for positive. if it finds positive it returns that column, and that's what we're going to use. so it's the first one that's positive. If you line them up positive, it always returns the first one. and if it can't find one, then it's optimal we can stop. So that's the entering column. we also have to find the entering row. and to find the entering row, we use the minimum ratio rule. so we just go through for all of possible rows we just do this calculation involving the ratio between the current element and the element that we would pivot on. we only worry about the positive ones and so, it's just a little check. And again, if there's a tie, you choose the first one and a simple calculation going through all the entries to figure out which row gives you the means ratio and then return p. so now, we have p and q where we want to pivot. that's in, and so we have the values p and q and we just go throu gh and do the pivot. and then, this is the same calculation that you do for Gaussian elimination. scale everything, zero out in q, and then and then scale the row And then, I'm not going to do the details of that calculation. that's what you get when you solve for one variable, substituting into the other equations. It's the same calculation as for when you're solving for simultaneous equations. and that's it. the simplex algorithm is just until you get a -one return from Bland, you just compute q, you compute p and pivot. And, and keep going and going until you're done. And then, to look at your maximized value, just look in the corner. not too much code to implement the bare bones implementation of simplex. It's a fairly straightforward algorithm. Now, what's remarkable about it is, remember, in multiple dimensions the number of points in the simplex could be high, could be exponential. But what's remarkable about this simplex algorithm, and still today, even somewhat mysterious, but certainly very mysterious for the first several decades that it was used, is that it seems to find the answer after just a linear number of pivots. this, all those points out there on the simplex. but when Delta Airlines is scheduling it's airline pilots or another company is looking for a way to drill or whatever, Walmart's trying to move its trucks around. these huge problems with millions of variables it's linear time. It could be exponential time, but it's linear time. That's why it's been so effective. now, you could use other pivoting rules and there are certainly been a huge amount of research on trying to figure out exactly what to do. nobody knows a pivot rule that'll guarantee that the algorithm is fast, it runs in polynomial time. most of them are known to be exponential in the worst case, but the real, again, the real-world problems maybe aren't worst case. and certainly people have looked at all different ways to look at it to try to understand why this simplex algorithm usually takes polynomial time. this is a, a recen t paper on the topic. now there are things that can happen during the execution of the algorithm that we've glossed over. one, one thing is that you could get stuck in that you could have a new basis. You could make this substitution but still wind up at the same extreme point. Like if a line, a bunch of lines intersect at the same extreme point. so that's called stalling. and that would be that, that's not a good situation that you have to watch out for. and the other thing is when you have this kind of degeneracy, you could, you could get in a cycle where you go through different basis always corresponding the same extreme point. It doesn't seem to occur in practice in the way that we implement it and the way that anyone would implement it. Just choosing the first one, that's Bland's rule is going to guarantee that at least you, you don't get caught in an infinite loop which would be bad. That doesn't seem to happen anyway. But it's a problem to think about. there's a number of other things that have to be thought about in order to actually try to use this to schedule airlines or whatever. so you, you, you, you certainly have to be careful to avoid stalling. one thing is that there tend to be, most of the equations tend to involved relatively few variables. and people who have experience with calculating these systems of equations know that in some situations you can find yourself filled up with lots of non-zero values. so you want to take a, a rule that meant implements of things with sparse matrix with, so your amount of space you take is proportional to the number of non-zero entries. so, and we, we looked a couple of times at some data structures of that sort, and that's certainly a consideration in simplex implementations. the other thing that we haven't talked about much in this course, but whenever you're working with floating point approximations of real numbers, and you're making a lot of calculations you have to make sure that you have control over the errors in the calculations. and scientific compu tation is certainly concerned with keeping control of that situation and something that we haven't talked about much in this course. and the other thing is that actually it could be the case that your constraints are unfeasible, there's no way to satisfy them. and it's a bad idea to run simplex for unfeasible situation cuz it won't ever get to the optimum. So typically, what we have to do in practice is run a different simplex algorithm on con transformed version of the problem. And there's theory, really interesting theory behind that all. and it's, you use the same code to figure out in-feasibility, but something has to be done. and the other possibility is there aren't enough constraints. so that you missed with one of those half-planes. You missed somewhere, and then it gets infinite. and that's also a situation that you want to avoid. And with the code that we gave, that would be the case where you use Bland's Rule to find a column, and. You're looking for a row and there's no row, so you have to check for that as well. and each one of these things is complicate, complicated enough that in this case we'd probably say the best practices. don't, don't go in and try to implement a simplex unless you're prepared to devote a really substantial amount of time to it. and there's really, no need to do that nowadays because basic implementations of simplex are readily available in many different programming environments. and routinely, nowadays, people solve LPs with millions of variables airline and they're so easy to reduce practical problems to an AP, and LP. Just throw in another constraint. Any constraints that you might have a certain pilot doesn't want to be scheduled early in the day, or late in the day, or union rules, or whatever. You just put all these things in as constraints without worrying that much about it. And then, add more variables, whatever you need to do. and then send it to an industrial strength solver and people nowadays solve LPs with huge numbers of variables. And not only are there solv ers. Nowadays, there's modeling languages that make it even easier to write down the LP. and so, there's plenty of resources available to make use of the simplex algorithm nowadays. and it's important. This is a really, you know, important quote from just a few, few years ago that's worth reviewing. so, they have this is so widely used. They have benchmarks on how well linear programming implementations do. So, even in 1988, it's not all that far back, they have a benchmark that would have taken 82 years to solve and even that's just a guess. and using the best linear programming algorithms of the day would take 82 years. Just fifteen years later, you could solve the same problem in one minute, that's a factor of 43 million. of this, factor of 1000 was due to increased processor speed, so fifteen years we have computers that are 1000 times faster but 43,000 is due to algorithm improvements. And there has been more even since then. So, the importance of knowing good algorithms and working with good algorithms is unquestioned, in this case. and, of course, this algorithm is still being heavily, heavily studied. so, it's starting with Dantzig's simplex algorithm and other basic knowledge about the algorithm and about linear programming that was applied in practice in nineteen 48. The, the basic idea of linear programming actually precedes Danlig, Dantzig, and actually wound up with a Nobel Prize. but what's interesting is rhere was, that algorithm was so good, there was actually not much development on it for about three decades. But then, an amazing surprising result Khachiyan proved that you could solve linear programming problems in polynomial time. that was quite a quite a shock at the time and we'll talk more about that in the last lecture of the course. And then since then, knowing that there are algorithms that potentially could beat simplex, people have actually developed algorithms that do beat simplex. And so, there's still a great deal of research going on, on the simplex on implementations of linear programmi ng solvers. So that's quick outline of what it means to implement and solve linear programs.