Now, we'll look at an algorithm for
solving the linear programming problem and
leaves the brewer's problem as an example.
this algorithm was developed by George
Dantzig right after World War II. and it,
it was in response to a very important
practical problem which was the logistics
of the Berlin airlift. and again, scarce
resources and particular constraints and
you want to maximize an objective
function. and this algorithm that was
developed by Dantzig again, is very, very
widely used today and certainly one of the
top ten scientific algorithms ever, I'd
say. so, it's a very simple generic idea.
we're going to start at some extreme
point. And then, we're going to perform
this operation called pivoting that moves
us from one extreme point to an ad, an
adjacent one that at least doesn't
increase the object, doesn't decrease the
objective function. And we just keep going
until we get stuck where there's an
extreme point that is not better than any
of its adjacent ones. and then we have an
optimal solution. so, in our brewer's
problem we start at the origin and just,
you know, simply move from one extreme
point to the other until we find an
optimal solution. and what's remarkable is
that really Linear Algebra sets us up to
do this solution. if you're familiar with
solving simultaneous equations this uses
the same basic idea. the difference is
that we've got many more unknowns and
equations usually certainly not an equal
number and so we have to take care of that
situation and also, we have the objective
function playing a role. so but still, the
basic idea is to get it down to solving
simultaneous equations. so, there's first
the idea of a basis, that's just a subset
of the variables. and, so, we pick a
subset of the variables. and then we're
always going to be working with something
called a basic feasible solution. so the
idea is you have a subset of the
variables. so let's say, that's M in this
case. there's three variables in the
basis. and the idea is that you set the
other variables to zero. so now, you've
got M equations and M unknowns cuz you,
you just set M minus N to zero. and so,
that gives you values for your basis. and
the idea is that a basic feasible solution
corresponds to an extreme point on the
simplex. so, for example, if all the
flacks, slack variables are in the basis
and that, we set the others to zero, we
set A and B to zero. then, that's what
that says, that's the value of A and B
when the slack variables are all in the
basis. if B is in the basis and, and HS
and HM are in the basis then B is zero and
then, if you solve for the three
equations, you get that A is 32 and so
forth. So basic feasible solution is if
you have M constraints it's a subset of
size M, so that you have an M by M system
equation to solve assuming the others to
be zero. and for the algorithm so it's
called the simplex algorithm, because this
thing that's the intersection of the half
plane, it's just called a simplex And it's
going to move along the simplex with, it's
basic feasible solutions, are extreme
points on the simplex. And the simplex
algorithm is going to move along from one
point to another. now, there's some
solutions that are infeasible that are not
on the simplex. if it's, it says, if it's
unique and feasible, it's a basic feasible
solution. It could be like if you pit A,
B, and S sub H to be in your basis, you
set the other ones to zero it's, it's not
feasible, it's outside of the simplex. So,
we won't even consider those. okay. So,
so, so to get things started what we need
to do is initialize. And I'll initialize
in that case, at the origin, when A and B
are equal to zero. and these three slack
variables are the basis. and then the
solution is really easy in that case.
here's our equations. we set A and B to
zero, so that cancels out all of that
stuff. So, that tells us the values of SC,
SH and SM in, in that case. so, that's
easy to solve in that case. so one basic
variable per row this started as the basis
at and since they are non-basic variables
to zero to solve three equations to get
the answer, you don 't have to do any work
for that. So, that's how we initialize
things from that. you can initialize right
from the constraints of the problem. All
that's in here is our recipe for ale and
our recipe for beer and our profit margins
for the two different drinks. okay. So now
it starts to get interesting. And we're
going to perform an operation called a
pivot. and we'll talk about how to choose
the pivot in a minute. So right now, let's
say, we're going to choose to pivot on
this entry right here. What that means is,
what we're going to do just as you do in
Gaussian elimination you're going to pick
this element and then you're going to
solve for that variable. and then
substitute that solution into all the
other equations so that these entries
become zero. So, we solve for B equals,
you take 480 minus five, A minus SC divide
by fifteen.
This equation says that's what B is.
Substitute it in these other equations and
that puts B into the basis and takes some
other variable out. and at the start, you
just might think about how do you figure
out which variable it replaces. if we do
the math here here's what the system of
equation looks like. so that's just
substituting B into the other equations,
including the objective function. and now
our basis is B, SH, and SM. A and FC are,
are zero and our objective function says,
that Z equals 36, 736. So, that's called a
pivot. it picked a variable substitute
into the other equations puts it into the
basis and makes the other entries in this
column zero. so, why choose that
particular variable? well look at the
objective function and its coefficient is
positive, so if we B is sitting at zero.
And if we increase it to some positive
number, we're going to increase our
objective function. so, as long as the
coefficient objective function is
positive, that tells us the column. We can
also do it on A in this case and then Y,
that row. well you have to make sure that
the right-hand side always stays bigger
than zero. and so, what uses to choose the
row is the minimum ratio rule. So, if you
ta ke the right-hand side over the
coefficient, you want the one that's
smallest because when you do the
substitution that will make sure that the
right-hand side is positive. so that's the
choice of the pivots. So now, we're in
this situation and we just do the same
thing. So we want to look for something
that's got a positive coefficient in the
objective function. And then, we want to
do the minimum ratio rule. and that turns
out to be that we pivot on column one row
two. and we just that's 32 plus 450 SC
minus SH divided by eight thirds is three
eighths. substitute that into everything
and that's going to eliminate A everywhere
else and it will put see, since we're
substituting for A, A comes out of the
basis in the objective function and
something else will go in. And again,
think about what it is that goes in. and
then we wind up in this situation here. so
that's again, just doing the math. Now,
what's interesting about having done the
math here now we don't have any positive
coefficients in the exec, in objective
function. so, these two variables are zero
now but if we take them out of the basis
and get a bigger value that's going to be
no good. so we'll stuck. And that's the
same as, same as the time that we stop
pivoting. if we to go in any direction
from where we are we're not going to do as
well. and that is optimal because first of
all any solution is going to satisfy the
current system of equations. so in
particular whatever values you give SC and
SA, it's got to satisfy this equation but
that's going to since they're positive,
you can't do better than 800. so you might
as well just be happy when they're zero
which is where they are. so it's as simple
as that, you know? So, the current value
has 800, so it's optimal, you're not going
to do better. and so that's a, a sketch of
a simplex algorithm. It's simply a matter
of choosing a pivot element and then
pivoting and then keep going until you
can't choose a pivot element. it's really
remarkably simple when you think about it.
That's the simplex algor ithm for linear