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 , thirteen, for the ale. And 28 23 for the beer. you make
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.