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