0:03

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.

Â