Today we're going to talk about linear programming, including the simplex algorithm which ranks as one of the most important algorithms of the twentieth century so certainly has to be included in any course on algorithms. And so what is linear programming? well you'll have a fairly clear idea after the end of the lecture. And in effect you can take an entire course on linear probing, programming. or actually do graduate study in linear programming. or get a high-paying job in linear programming. Programming so it's quite a bit to define. so we talk about shortest paths and, Maxwell's problem solving models, and linear probing, programming is a general problem solving model, that works in a lot of contexts. so shortest path max flow, that's fighting the minimum or the maximum of, some kind of quantity. And a good way to think of linear probing is, programming where it's most, not often used in practice, is you want to allocate scarce resources among a number of competing activities. And you want to do it, in, in a way that, minimizes costs or maximizes something. That's the basic idea. And, it encompasses, a huge number of, problems that, we've considered, And even, plenty of problems that we haven't considered. so this is, an example, of a linear program that we're going to use, throughout this lecture. So it's got, a couple of, components. So, So one of'em is called an objective function. and so we say, we have some variables. and we want to maximize the objective function. And so our, our goal is to find values of the variables that'll maximize the objective function, subject to constraints in the acquaint, constraints are linear inequalities. and usually, including that the variables are positive. so, there's two steps the first is whatever problem you have you have to formulate it like this that's reduction. You take your problem and you convert it into this form. And, then the second thing is to solve it. that's what linear program, programming is. And, it's significant because it's widely applicable to re al world problems. there's fast commercial. programs out there that. will solve huge linear programs. and it's a key sub-routine for solving even more difficult problems. But it's the idea that it's. a widely applicable model that we can actually do solutions for huge problems. For example, airlines use linear programming to schedule the planes and pilots and flights. And Delta recently claimed that linear programming, programming saves it over a $100 million per year. so, it's general and we can solve problems. That's what linear programming is. And very general. Here's just a short list of problems where you can find papers where people used linear programming to solve these problems. From direct mail advertising to, as I mentioned, airline crew assignment there's problems in science Ising spin glasses in physics, sports scheduling, baseball and basketball in electrical engineering and designing computers, or blending petroleum products. All kinds of things, so a huge number of applications. It's a very general model. so let's take a look at. a little more detail of a full application. And we're gonna do it based on a classic paper in Scientific American in 1980. that certainly, I don't know if it was intended, but certainly does appeal to college students, cuz it's all about using linear programing to, to decide how to best make beer and ale. That's why it's called the brewers problem. So here's the idea. So, for example, to try to make sure that everybody understands what linear program, programming really is. It was developed by Bob Bland who also contributed to, a lot to the practice of linear program, programming as well. Okay. So the small brewery is supposed to produce both ale and beer. Now, there's raw materials that go into both ale and beer. There's a few other things but the main ones are corn. hops and malt, and the brewery has a certain amount of each one. say it's got 480 pounds of corn, 160 ounces of hops, and 1,190 pounds of malt. So that's the resources that are available. Now there's, they k now how to make two things. They know how to make ale and they know how to make beer. And there's a recipe for the ale and the beer that uses these scarce resources. So to make a barrel of ale, you need five pounds of corn, four ounces of hops and 30. Five pounds of malt. and to make a barrel of beer you need much more corn and less malt and a little bit more hops. So that's the recipes for those two things. And the other thing is that there's different profitability. So you can make $thirteen per barrel of ale and $23 per barrel of beer. So the brewer's problem is what do we do? How much ale and how much beer should we make? so, the pro- situation is that depending on how much ale or how much beer you make you have different amount of profit. So let's say, someone says, well let's make it all out of ale. Le, let's make as much ale as we possibly can. so turns out that 34 barrels of ale is the most that you could possibly make, because that uses up all your malt. so you need 35 pounds of malt per barrel and 34 times 35 is 1190. That's all that you have. so, if you make 35, 34 barrels of ale, that's the max that you can make. and then, if you do that 34 times thirteen is $442 of profit that you make if you make all ale . what if you make all beer? Well, if you make all beer, then corn is the limiting resource. You need a lot of corn to make beer. you're going to need fifteen pounds per barrel. You can only make 32 barrels. and you have plenty of the other resources. but if you did make all beer, you'd make $736. So, if you're going to make all beer or all ale, you're gonna go with the all beer. but you can do things in between. The if you used up all the hops it would be 19.5, well you can't really make a half barrel so we're not going to consider that case. But if you could it still wouldn't be as good as all beer. but what about this mix here? If we're making twelve barrels of ale and 28 barrels of beer. then the amount of hops that you need. you can multiply it out. That would use up all the hops. About 160, o unces of hops that you've got. so that's, restricted by the number of hops, And also uses up all the corn, that you've got. and if you do twelve <i>, thirteen, for the ale. And 28 <i>23 for the beer. you make</i></i> a profit of $800. So out of these alternatives, that's the one you're going to choose. Make twelve barrels of ale, and 28, barrels of beer, and you're going to maximize your profits. that's the brewer's problem and now the question is can we do better? We've just been fooling around a little bit and seeing which one uses up resources is there some way that we can do better? so that's really the brewer's problem. I got the scarce resources. I've got the objective function. I want to maximize my problems while sticking to the resource constraints. So, this is a linear programming formulation of the Brewer's problem. It's a mathematical formulation of the problem. And all we're doing is expressing these various constraints with math. so A is the number of barrels of ale that I wanna make, and B is the number of barrels of beer. my profit is $thirteen for each barrel of ale, and $23 for each barrel of beer. So I want to maximize 13A plus B, and then I'm subject to all these constraints that are given to me by the recipes. the And, for the ale, it's, it's the five units of corn, four units of hop, and 35 units of malt. And for the beer, it's fifteen, four, and twenty. so, if I make A barrels of ale and B barrels of beer, then I'm subject to this constraint. And it's all, all the corn that I have. And so forth. And of course I have to pick a positive number of, barrels of ale and beer. That's a mathematical formulation of the problem. so that's linear programming. That's reducing the Brewer's problem to a mathematical formulation. so now, we wanna look at, try to get a better understanding or geometric intuition on what this thing means, in so. Of the key ideas is the thing called feasible region. So, we have two variables. So, we are gonna plot all the possible points, all the possible amounts of ale and beer we can make just in the xy plane. So, it's positive xy plane, because we are gonna make positive amount of beer and positive amount of ale. In the other constraints, actually defined half plains so that is, the amount of corn has to be, you have to have 5A plus 15B less or equals 480. If you draw the line out of 5A plus 15B equals 480, which is this line here, and it intersects way out there. Than, everything, above this line is not feasible. We don't have that much. And everything below that line is possibly feasible. And, actually, all we do is just intersect all the half blanks including the half blank above the X axis, and to, the right of the Y axis. And if you do that, you'll get a complex, convex polygon. it's and all the points inside are things that we could possibly do. so it's a first idea. We have inequalities that satisfy all those inequalities simultaneously defines a complex convex region like this. and what about the objective function? Well that's just another line. And so that's a line of slope If you take 13A23B plus 23B that's the objective function, and any point, if you, look at where this line of the same slope, intersects the, convex region, you can see that what we're going to be looking at is, we want the one that, goes up the highest. you can't get higher profit if you, if you have a line that is a bigger number then you're not going to be in a feasible, feasible region. So that you can see, it's a, the objective function defines the slope of a line. And what we found, want to find is, you think of it the other way. The line coming in from positive infinity. Where does it hit the feasible region? that's where our profit's gonna be maximized. so just the geometry tells us that the optimal solution is going to be at an extreme point. in this case it's where you know, we have two variables. It's where two constraints intersect. so that's already a huge improvement in terms of solving the problem rather than having to consider this infinite number of points that describe the amount of ale and amount of beer that we might make. we only have to consider this finite set of points which are the extreme points in the feasible region and one of those is going to be our optimal. . So, that brings us to the standard form of a linear program in general. In general, we have way more than two variables. and we have lots of different linear equations. so what we're going to do is and actually we're going to get rid of in, inequalities and just deal with equalities. And we'll talk about that in a minute. and this is just to try to get a form that makes all the problems seem the same so that we can work with them. And this again is the power of reduction. We're just using reduction to get the problem in a form that we can fully understand it and solve it. so the general statement of a linear program, it's going to be you've got some variables. and the, you want to and the variables you are going to assist are all positive. and the objective function is a linear combination of those variables. That just means we multiply by constants and add them. All the constraints also will be linear equations. However many constraints there are, there can be any number of constraints. the constraints might be redundant, the problem might be over constraints all of that has to be dealt with in a linear programming solution, and you don't have things like multiplying together variables or any thing like that. so your input is the coefficient, for the objective function. And also the coefficients for all the linear equations and also the radiant sides. in your output I use the result of solving the linear program and problem. It's the values of the X's that maximize your objection function subject to all the constraints. now people define standard forms of linear programs in different ways. And you can find all different sorts of slightly different standard forms. this one is really convenient to express as a matrix. where A and, A is a matrix and B and C are vectors. and it's just those and X is a vector, column vector. you're just sat isfying maximizing The that's, that's just saying the same thing in much more compact notation. so as I mentioned, there's no really widely agreed notion of standard form. So you'll find different standard forms in different context, usually. So now our brewer's problem didn't have equalities, it had inequalities. So we have to convert that to the standard form basically get rid of the inequalities. And it's really easy to do, and once you get used to this idea, then we'll use it again later on. so the first thing is, is, so instead of Mm-hm. maximizing a linear combination, we're actually going to, just maximize a single variable. And we're going to add that and, and then make the objective function an equation. so when I maximize Z, subject to the constraint that 13A plus 23B minus C equals zero. That's the same as maximizing 13A plus 23B. And then we just add slack variables to convert each of the inequality, it's called a variable that takes up the slack. so if five A plus fifteen B has got to be less than or equal to 480, that's the same as saying that five A plus fifteen B plus something positive has to equal 480. so, it's just saying the same thing. add a slack variable SC. And say that it's got to be positive. So now we have a bunch of equations. and just all positive variables. So it's, it's more variables, but less variability. we've kind of got a variable for everything in the system. so that's a conversion of the brewer's problem to the, standard form of linear programming. now just a little bit more about the geometry before we get to the solution. Again, the, inequalities to find half spaces, so when you intersect them you get something convex. You can't get something like this because the half space will just chop it off. So that's really important and that's in two dimensions. so convex just means that if you have two points that are in the set everything in the line between them is also in the set. an, an extreme point is something that you, you can't write as a linear combination of something in the set. so that's just the geometry of it. and that's in two dimensions. and this is very intuitive in two dimensions. In higher dimensions it's hard to really trust your intuition so that's why we have these specific geometric definitions. Now the extreme point property still holds even in higher dimensions. This is three dimensions and now after three dimensions, we really have to use our imagination. But still the same idea of a bunch of intersecting half spaces in higher dimensions. And the same basic idea holds if just you stick with the basic math definitions. And so they all intersect. And the good news is that still, inside is an infinite number of all possible solutions, but there is only a finite number of these plains and so they intersect, there's only a finite number of intersections. That's a good news rather than having to examine infinite number of points. We just have to examine a finite number of these external points but the bad news is that there could be a lot of them, it can be exponential in number of constraints. So that's the extreme point property. Now, it's, because of this idea of the extrema has to be where the solution is. if you find a, a local optimum, place that's just, better than, everybody connected to it, that's just going to be actually a global option that follows from convexity. so, if the, it's actually a good situation that if you can just get to a place that, you can't improve from, then, you're in good shape. That's a kind of test, that's the geometry of the, linear programming problem.