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.