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