Hello everybody, welcome back to our unit on linear programming. Today, what we're going to do is we're sort of going to put everything on sort of a more solid, rigorous basis. So remember last time what we did is we had this factory problem, where what we wanted to is we wanted to maximize. In terms of M and W, this 200M + 100W, this is linear expression. Subject to the following list of linear inequality that they had dissatisfied. And so in general, basically, just this is where the linear programming is. It says we want to find real numbers, x1 through xn that satisfy a bunch of linear inequalities, so a11x1 + a12x2 +..., is at least to b1, and then a bunch more of those. And subject to these constraints, we would like a linear objective function, v1x1 + v2x2 + etc., to be as large or possibly as small as possible. To clean up the notation a bit, we're really going to store this by having a matrix A that encodes the coefficients of all these inequalities along with vectors b and v. And our output should be a vector x and Rn. Such that A times x is at least b. And what I mean by this is that if you multiply the matrix A by the vector x, then you get a new vector where the first component of that is bigger than the first component of b. The second component is at least the second component and so on and so forth. And note that if you just unroll what that means it's exactly the system of linear inequalities that we had on the previous slide. Now subject to this constrain, we would like v * x to be as large or as small as possible. So linear programming turns out to be incredibly useful because them are an extraordinary number of problems that can be put into this framework. To begin with the factory example that we solved in the last lecture was exactly of this form. Optimize a linear function with respect to some linear inequality constraints. But there's a ton more problems that fit into this. One of them is the diet problem, which was studied by George Stigler in the 1930s and 40s. And intuitively, it's a very simple problem. How cheaply can you purchase food for a healthy diet? This is really important if you say, need to feed and army full of soldiers for example and you want to be cheap. So how do you do this? Well, you got a whole bunch of variables for every type of food that you could possibly eat. You need to know how many servings per day of that food you're going to have. So you've got a variable x of bread, x of milk, x of apples, so on and so forth. And then you've got a bunch of constraints. Firstly, for each type of food, you need to have a non-negative number of servings of that food. It wouldn't do to have minus three servings of bread a day. And additionally, you need to have enough nutritional content, you need to have sufficiently many calories per day. So many calories do you have? That's just the (Cal / serving bread) x bread + (Cal / serving milk) x milk + so on and so forth over every type of food. And this should be at least 2,000 or whatever your minimum calories per day for your diet is. And in addition to this constraint, we have another similar looking constraint for each other nutritional need. Vitamin C, protein, What have you. And so we have a bunch of linear inequalities as our constraints on these variables. And subject to these constraints, we want to minimize our total cost. And the cost of our diet is the (cost of serving a bread) x bread + (cost of serving milk) x milk+ so on and so forth. So we want to minimize a linear function of these variables, subject to a bunch of linear inequality constraints. This is a linear problem. You can solve it and it would tell you in some sense the cheapest diet that you could live on. Unfortunately, I should worn you that actually doing this is maybe not the best idea. When you solve this, the solution tends to optimized for a few very efficient foods for getting calories and protein. And then maybe a few random things to like fill in your other dietary needs very cheaply. But I mean It might say that you should eat mostly potatoes and peanut butter and then a bunch of vitamin pills or something. And so, these tend not to produce diets you'd actually want to consist entirely on. But maybe if you want to think about what can I do to eat more cheaply, it's something to look at. So another problem that fits very nicely in this linear programming formulation is network flow. It turns out that the network flow problems that we discussed in the last lecture are actually just a special case of linear programing problems. So if you want to solve max flow, then you've got a bunch of variables, f sub e, the flow along each edge e. And they satisfy some constraints, for each edge e, f sub e if between 0 and the capacity of the edge. And then for every vertex that's not a source or a sink, you have conservation of flow. So the total flow into that vertex is the same as the total flow out of that vertex. Now when you first look at this, this might not seem to be an inequality, it's an equality, not an inequality. But you could actually just write it by writing down two linear inequalities. You could say the flow into the vertex is at least the flow out of the vertex. And on the other hand, the flow into the vertex is at most the flow out of the vertex. And so we put these two inequalities together, it's equivalent to this one equality. So once we put these constraints on, we now have an objective function we'd like to subject to these constraints, maximize the flow. That's the total flow going out of sources minus the total flow going in to sources, which is a nice linear function. And so this maximal problem is just a special case. When you phrase it this way, it's exactly a linear problem. Now a lot of the time, when you look at a linear program, it's exactly what I said. You're subject to these constraints, there's a unique maximum value which attains the best possible value of the objective function. However, there are a couple of edge cases that you need to keep in mind where things don't quite work out this way. The first is you could actually have a system where there is just no solution. You could have constrains say x is at least 1, y is at least 1, and x + y is at most 1. If you have the system of constrains which is graphed here, there's actually no solution. Because if x and y are each at least 1, x + y needs to be at least 2. So there's no solution to the system, so you can't even start with trying to find a maximum. It could also be the case that even though your system has solutions there's no actual optimum. And a way that this could happen is as follows, if you have the system where x is at 0, y is at least 0, x- y is at least 1, there's actually no maximum value for x here. Basically, the region is graphed here, but it says you could higher and higher and higher up. x is actually unbounded in this system. And so in some sense, your solution should say that there's no maximum. Now just to review this I've got three pretty simple systems here, each with two equations and two unknowns. Now one of these systems has no solution. One of them has solutions but no solution with a maximum x value, it's unbounded. And the third one actually does have a unique maximum x value. And so I'd like you to take a little while to think about which one of these is which. Okay, so if we actually graph these three systems, A it turns out has no solution. One equation says we're supposed to be bigger than one, the other one says we have to be less than zero, you can't do both of those. B if you write it down does have a unique maximum at I think x equals one and a half, as plotted there, it's the red point. And C, although it does have plenty of solutions, if you graph this region. You'll note that you sort of slide up along this line, x equals y, you can make the x value as large as you want. And so there is our R solutions, but there's no max. In any case, that's all that I had to say about this basic introduction to linear programs. Come back next time and we'll start by looking at a special case of dealing with linear equalities rather than inequalities.
