All right, hi everyone, welcome back. We're going to do one more problem here. This is going to be sort of the largest problem. I want to say largest though and not most difficult because again, we're always sort of looking for the same thing whenever we do a linear programming problem, what are variables? What are the constraints, what is the objective we want to maximize or minimize something? Here's what, it's called the busing problem and part of it is just a little difficult to sort of decipher what's going on here. So we're going to spend a little bit of time working through this one, pause the video, read the problem if you haven't done so already and then we'll work through it together. If you want to try to start to model this problem, that would be good too. All right, let's begin. Hopefully you paused the video and read this one on your own. So what I want to do here is draw a picture to sort of help motivate this one and you'll see how this one is a little different than the other ones. First off, Johns Hopkins is setting up three charter schools in Baltimore city. Kyoko High School, Devon High School and Manny High School named after former students of mine. Each high school has the capacity of 900 students. The mayor hires your company to sign accept the students to these new schools. Buses will be provided to students who live more than walking distance to find is 1.5 miles to the school. Baltimore city has been partitioned into five neighborhoods A, B, C, D and E. Kyoko High School is in sector B, Devon C, Manny High School in E. All right, so first off let's drop it. Never been to Baltimore, here's my rough sketch generally of Baltimore city give or take. And for no good reason we're going to divide it up into five segments. So let's do that here and we have one, two, three, four and we'll say one more for five, great. And we're calling these neighborhoods A, B, C, D. And we'll put E over here, fantastic. Now we have some high schools that live in these neighborhoods. So Kyoko High school is in sector B. So we'll put a little high school here, there's my school for Kyoko High School. Devon High School is in sector C. So there's another high school here in sector C. And Manny High School is in sector E. One more high school, yes, they all look the same from Manny High School here in sector E. Now if a student lives in a sector and is assigned to the high school in that sector, the student can walk, okay? So if I'm a little student and I live and B, I can go right to B, I walk, I don't have to take the bus. Now I don't get a bus even, not even an option. But if I get assigned to say another high school, well then I have to take the bus, okay? So there's my little bus and I have to take the bus. So all students must be assigned a school, you can't leave anyone out, makes sense. I want to minimize. So this is the first time that we've seen this. I want to minimize the total student miles traveled by bus. So there's lots of ways that we can bus all these kids around. We have the table here below with the distance and you can imagine if we picked randomly, maybe it's not the best way to minimize the miles, okay? So a student miles going to be the number of students and basically how many miles are traveling and then we add them all up. So just for the table below here, I have distance in miles from the sector to the school. So just to read the first column I have sector A and it's five miles. So right, so the distance between A and B here is five miles. My picture obviously not drawn to scale from B it's Devon High School sector C. It's eight miles and Aanny High School in sector E, it's six miles and I have 700 students to assign. So this problem is going to show the importance of labeling your variables. So think about what you have to do. I have all these students in A right? 700 in total and they have to get to assign a school, they can't be assigned to a high school in A, there is no high school in A. So they have to get assigned to B and E and C somehow some way and I have to do it for all 700. So let's think about this for a second. How am I going to model this problem? And I have to do the same for sectors B, C, D and E. What's the best way to do it? Well as usual, let's set up our variables and what I'll do is I'll work maybe below this time in row 20 and I'm going to set these up in a particular way that hopefully this makes sense. Before you see me right out the actual term like number of students from A to assign to high school B, number of students that's a little wordy. Can also do it in terms of just generic letters you've seen me do that before. X1, X2, X3 for the investment problem I did that. This one here, I'm going to be a little clever and I'm going to try to say, look, I'm going to signing students from A to B, from A to C, from A to E. I'm going to do this, I'm just going to call it AB. This is going to be my variable cell. And also just to mix up the template because again, this is going to be a little trickier. We're going to go AB, AC and AE. So I'm going to label one of these just realize what this is. This is the number of students to assign from A to the high school in B. You can see why I'm not going to write all this out here. So maybe I'll merge and center just to have this and then we'll continue the pattern in the entire time and that'll be what AB stands for. And what I want to do is, this is the variable cell that I'm after. How many students do I have to do, right? What's the right number to do meeting all the constraints? Minimizing the total bus miles and going along. So when I do it this way right, I have five sectors, A, B, C, D and E and three high school. How many decision variables am I going to have while A to B, A to C, A to E, B to B, B to C and B to E, there's three more. So for every sector you have three sort of decisions to make five times three is 15. So now we're going to have a problem and this is going to be large when we do in the entire class. But you can imagine they get as large as you want. Take an Excel can handle up to 200 of these. I just don't want you to be scared if you have to like write out 15 variables. I guess is that a normal thing to do, is that allowed? Yes, of course. So we have BB, DC, DE, CB, CC and CE. And then of course DB, DC, DE. So we write it all out again, just use as many cells as needed and last but not least EB, EC and EE. And sometimes you can even go down the page. Excel does not care if you go across a row or down a column, but we're going to be consistent here, we're going to label this with our green cells and we can throw in some numbers here, some dummy numbers just to make sure our spreadsheet is working as always. Not a bad idea, usually considered best practice is to throw in some dummy numbers. So the way to interpret this is with these numbers here, I'll do one, two, three is I'm going to send one student from A off to Kyoko High School in sector B and two students from sector A to Devon High School in sector C and then three students from A to E. Now, obviously this is wrong, if this were the answer, I would send six students and six students only. That's kind of a problem because remember I have 700 students to fill, so I have to figure out how to send these seven students that's obviously a constraint. But once we have this variable cells set up, we can do our objective. So our objective here is to what? This is a minimum, this is I think the first minimum that we've seen together in the videos. I've done a lot of maximizing profits or return on investment. But now I want to minimize my student bus miles, my student bus miles. So how do I know how many miles that it takes? Well now this is where the table comes in. If I send and a student from A to B, that student's traveling five miles. And from A to sector C that's eight and then from A to E that's six. So I'll put all of these below here and I'll mention what they are, they come right from the table. It'll take me a second to fill this out. But these are your miles traveled. So we have five, eight, six. Now notice it goes right to BB. So that zero because remember those students are walking four, 12, four, 0, seven, seven, two, five, 12, seven and zero. So zero corresponds to students have to walk, but we only care about bus miles traveled. All right, So we check all that that looks great. And now our objective is going to be the student bus miles. This is what we want to minimize and we will color code our objective cell gray. And how do I calculate this number for every student from A to B? They travel five miles. So I would multiply it by all the students here, two students are traveling eight miles that be 16 and that would contribute to my total. So once again, we're using our favorite formula, sum product, we take all the students comma and all the miles that they have. Yes, they're 15 of them, but that is okay. Close the parenthesis hit Enter and everything is great. We'll use the formula text to show the actual formula and I have my variables and I have my objective. A lot of students struggle here. If you notice, it's actually relatively simple so far. The hardest part is just deciphering the question. A lot of students struggle just to set this up, even though it kind of follows the same template. So hopefully you got somewhere, got a good start on how to do this. But you can see here the challenge of how to define the variables, how to label the variables. That is extremely important to set up a problem especially one that you want to pass off to somebody for readability. So now let's do our constraints. Let's think about what we have read the problem again. Really, what's the constraint? I have to send all these students out, right? So I have to send out all 700 students, but also in the problem, what do we want to do here? Each high school has a capacity of 900 students right there. So I have to send everybody out and I can't over send, I can't send 900. So, doesn't matter which one we do first. But let's do the 900 in school B perhaps and 900 in school A, notice again one sentence giving rise school C. One sentence is giving rise to more than one constraint, that is pretty normal. So we have 900 in school B, 900 in school C and 900 in school E. Okay so how do I do this? My constraint table always goes to my variable cells and then one, two, three more. We're almost getting off the page here. Let me zoom in a little bit to see everything. I'll put some borders on this just to make this more readable. But let's think about who's getting sent to B. Let me label this first, the left hand side sign and then my right hand side and were told remember that I can't send anymore. So let than equal, less than equal and less than equal than 900. These are all numbers no formulas, okay? I just now need to count some way somehow who is getting sent to school B. So think about this for a second. What do I want to do? I just want to count something, I just want the number to appear. We've seen this a couple times now, you just put a one in the table. You just put a one so this will take A to B and Remember B to B, these are the kids from B going to B and they contribute zero. But I still like to count them right? I absolutely need to make sure they're counted in terms of the total. I'm sending students from sector C to school in B and sector D and there's a pattern here which you can start to to see. So if I put five ones in here corresponding to this section, these are once I do my sum product formula, this will be counting some product. Little number of students sent to B, let's see that actually happened. So highlight the green cells, highlight across, hit Enter and hold and behold there are five students so far that are being sent to B. And if I change something like let's change A to B to be five, you can see the number over here has changed to nine. So what this is doing is multiplying one times five, one times one so there's six. Another one times one is seven, there's eight. And another one. So it's multiplying and adding as we go, I'll do the formula text. I'm going to run our room here. So I'll do it up here and I'll do it just for one of them. The pattern will be the same and there it is. So that is your formula. Remember as always, I want to put the dollar signs in place. So I'll highlight it, I'll do function F is the keyboard shortcut. You can certainly type them in directly if you'd like and then I just have to keep track of all the students going to C. And because of the way I listed these out, there's a nice pattern here. It's just going to be a one to the right of everything, right? So this will keep track of who's going to C from A, who's going to C from B etc, work your way across. I'll drag our formula down and last but not least who's getting sent to the high school in sector E. Well we have students from A students from B, students from C, students from D and students from E. So you get this nice little pattern here corresponding to everything and you can check using our dummy numbers that these are all being added up correctly, that we can check it against this cap of 900 when we actually do the right thing. Okay so that is the restriction on every school. That's the first part, I also have five sectors. I have to sign all students for the sector into the high school. So I have 700 students for A. So let's write that down. 700 in A, I got 500 B, I have 100 in C, I have 800 in D and I have 400 in E, five sectors. A bunch of students that need to go, each one of these is a constraint. You have to assign the students to a school, they don't have to go to a school in a different sector but they have to get assigned to a school. Okay so how do I count how many students are being assigned from A, keyword here being from A. So I add up the students from A, from A and from A. There are three possibilities corresponding to the three columns of A, right there. One, two and three. These ones when I do my sum product right? Blanks are treated as zeros. They count up the numbers, five plus two plus three. These are all the students from A going to B, all the students from A going to C, all the students for A. So when this number equals and this is slightly new as well equals notice by the way, if you type equals and hit Enter, it actually works okay. I thought sometimes you might need like the single apostrophe, if it's not working for you you can do the single apostrophe equals and that also gets it as well. That says I'm not actually wanting a formula. I don't want to be less than or equal here. That's a problem because I don't it's not acceptable to send 600. I really do want to equal 700 students from A, 500 students, 100, 800 and 400. If you remember in solver there was a sign of equality in that dropdown menu you can select equals here as you go through. So we will actually use equal not less than equal here. And then this is the nice thing here, there's a pattern to this. The first three are students from A, the next three are students from B, the next three are students from C and you work your way across. This often happens, this sort of pattern in the constraint table. When you get a large constraint, you're often doing things different ways in different times, to different pieces of the process and a pattern tends to emerge. It's hard to decipher, it may take a couple of times a practice to come up with good variable names, but you'll figure it out. And of course, remember once you make something in Excel, you can always go back and clean it up, make the spreadsheet more readable, minimize something's remove some duplication. That is okay, I've done this problem many times in class, which is why I'm able to sort of do it directly. But the first time we do it, you come up with an idea and then you polish it along the way. So we have all of our formulas cleaned up, we have all the patterns here, we're counting everything and we read the question one more time just to make sure we didn't miss anything, we're good to go. If you want, you can tell how difficult this will be by hand to try to figure this out, we're going to jump right to solver. So let's go to data, let's go to solver and here we go. So the spreadsheet actually is across long but not that bad. But the color coding certainly helps. Our objective is the gray cell for me it's in B 24 I want to minimize. So this is the first time we're going to do a minimum problem together and I want to change the variable cells, these are the green ones. So I highlight all 15 green cells. That is okay again 200 is your max and 15 is still relatively small subject to the constraints. All right so let's add some constraints together here, I have my nice constraint table. We can batch upload these. The first three will be the left hand side. This will be saying don't assign any more than 900 please. We want that to be less than or equal. You can certainly sign a high school less which is not more. So the sign will not change and then the right hand side will do in the batch we'll do one, two, three we'll get all 900. So I want to add another one and now here comes my equality. So, remember the second one here is inequality and this is the five sectors. So one, two, three, four, five. I want that to equal and then their corresponding populations so that now is done and I hit okay. So there's two batches, you can certainly do this individually. It's kind of a pain. I wouldn't but you can do it individually as you go along. I want the check box to make unconstrained variables non-negative. And I want to change my solving method to simplex LP and I'm ready and I feel good about it. I hit solve, solver found a solution. All constraints are optimally and optimalilty conditions are satisfied, wonderful. You say thank you solver. You hit okay, again this is something that I don't think anyone would have been able to find by hand or at least easily at all. But with solver it literally takes a couple of clicks and a few seconds. And what this does, don't forget your summary sentence here. What you just found is mildly amazing. You have minimized the bus miles traveled. So we send 400 students will just do for A, from A to B. And the remaining, remember there were a total of 700 here. So 400 and the remaining 300 will go to E, the high school in E. And you would do the same for, do the rest etc, stare at this. This is pretty cool. Students in B, you're going to send all the way to minimize this. You're going to send all the students in B to the high school in B and that will minimize the travel. They can walk and then you send out the rest here. So that takes care of all of them in B but some high schools unfortunately, you have to send these out and you get your answer. So the final answer would be for a minimum of 5400, I'll say student bus miles total miles that students are traveling on the bus. And you can imagine different combinations would give really, really different answers. If you try to mix this up, just try it you can see how this objective, even if you meet all the feasible conditions, all the constraints, it can be really large. And again, the power of solver coming into play here. So solver will find you the answer, but it's only as good as the spreadsheet is set up, your job to set up the spreadsheet, make it readable and in a way to pass it off to someone else to go now do say a budget or some other forecasting, all right? So go over this one again, the hardest thing here to do is take this problem and set up the variables, but once you have that the rest kind of falls nicely into place. All right, great job on this example. We'll see you next time