Okay, so that was about mathematical modeling. And now in this video we will talk about something slightly different. Let's look at some historical events on may be very important maybe not so important about operations research. So probably we want to have some theory about the origin of linear programming. Then we must take a look or talk about this particular person, George Dantzig. George Dantzig is typically considered as the most important beginner for this whole field, operations research. So let me briefly talk about his story. So, George Dantzig, he was a PhD in Statistics and from University of California, Berkeley. So every time I need to talk about these pigs I'm also studied and get my PhD from Berkeley. So we are from the same school okay? But he's very famous for them not. So the interesting thing is that he was a PhD student in Berkeley. And he took a course about Mathematical Statistics, which is very difficult, but George Dantzig is pretty much a genius. So every homework problem can be solved easily in one or two hours. So there was one day he went to the classroom but he was late or maybe he did not get up early enough. So he went to the classroom and he was late. The professor is already talking about several things. And he saw that there are two problems some kind of two mathematical statistics problems written down on the blackboards. So he thought that should be a homework assignment. So he wrote the problem down and then go home. So probably George Dantzig is also having no friends so no one talks about the problems with him. So he went back to his dormitory and salt tried to solve these two problems. After one week, you went back to the classroom and turn it in, turn those problems, solutions and problems solution to the professor. Say, Hey professor, I found these two problems surprisingly difficult, much more difficult than previous assignment. It took me two to three nights to solve these problems. And the professor was really shocked because that two problems was not assignments. That two problems are actually very difficult, famous nobody can solve problems in that day. So turns out more genius just solve these two problems. So that means if you are still in a university and if your professors assign some homework problems to you try to solve them okay? Because that may actually solve very difficult problems. So, when George Dantzig was doing his PhD study, there was World War Two and the United States is fighting with different countries. So he decided to serve to go to the military and he was assigned to the Air Force. Of course, he is not a professional military person, so he is not driving airplanes. What he did is that he helped, he is in the department that is designing the route planning for aircraft. So the thing is that if we want to have a battle with our enemies, or if we want to take a look at some regions, we need to assign airplanes to there, right? So in that case, we need to decide route. Each time when we have one or several airplanes to go for a mission, there must be some orders. You go there first, you go there, you go there, and then all together, we do this, do that, blah blah blah. George followed that plan has a linear flavor. Why is that? Because if your base is here, you need to go here, go there, go there, then you decide your routes. And the oil consumption is typically linear if one gallon of oil can help you go ten miles, then two gallons of oil can help you go 20 miles right. The time consumption is also typically linear. So after he studied he found that many of the problems that are they are trying to solve is a linear problem. And it's also an optimization problem. Obviously, you only have limited amount of time, you only have limited oil. And then you need to go to several different places. You want to maximize the number of places you may visit. Maximize the probability for you to win the battle. Minimize the total amount of time you need to go back to the base, and so on, and so on. All of these are optimization problems, but at the time about 1940,1945, he found no one is able to systematically solve large-scale optimization problems, you may feel shocked. But that was 60 years, 70 years 80 years ago, there was no computer. Their computer is not so popular and no one is trying to solve these problems at that moment. So, he spent some time to think about this problem and eventually invented the so called simplex method. We're not going to talk about the simplex method in this course, but anyway, is the efficient way to solve any scale of linear program in some sense. So if you have ten variables, he is able to solve it. If you have millions of variables he's also able to solve it of course. A computer is needed, but the algorithm is defined by George Dantzig is the first effective solution for linear programming in the world. And after 70 years 80 years, that simplex method is still a very important module in any commercial software nowadays. So, only after George Dantzig invented the simplex method, people started to be able to solve these kind of linear programming problems. Previously people know how to formulate a problem, but no one knows how to solve it. Thanks to George Dantzig. Now we are able to solve all these problems. And then it's not surprising that all kinds of companies organizations, they try to use linear programming to help them solve difficult problems. Here are some successful stories, not just these two, there are a bunch of successful stories, we just need two. For example, United Airlines, these kinds of airline companies, they are doing personnel skilled scheduling problems because typically and in an airport, you either run 24 hours in a day or at least 20 or 60 hours in a day. But no people no single person can work for a consecutive 16 hours, right? So you need to schedule your workers somehow. But in an airport typically the demand is also not so smooth. Sometimes you have peak hours sometimes you have off peak hours. For example, as the morning time you may need a lot of people but during the noon time, the number of people you need may go down. So if you have the number of workers needed like this, this is time, this is the number of workers you need. Then typically you will have some peak hours and off peak hours, something like this. Okay, so this is the situation faced by almost all companies that is trying to do service. So how many people you need to hire, that's a difficult problem. How to assign schedules to them, that's also a difficult problem. In 1992, roughly 30 years ago company like united airline, that scale of company use linear programming to save about to reduce about 50% of flight delays and to save more than $5 million per year. Okay, so linear programming may look very simple to solve, knapsack problems. To solve the core examples we mentioned to you. But if you correctly apply it to a big company like this, that's $5 million per year. Or if you are making food, for example, this company. So with any company, if you are making different kinds of products, in many cases, your customers will come to you and they'll try to make orders, right? They will ask you, Hey, if I order now, when may I get the products I ordered? And sometimes they want a lot but you have no capacity. You need to tell them no, I cannot give you everything but I can promise you 80% of the need, something like that. We need to give a quote to customers, telling them that may I satisfy your order. How much may I satisfy or fulfill and when may I deliver the products to you? When I tried to make this promise, I need to calculate the amount of resources I have and the amount of orders that I already promised. And once I promised this customer I need to quickly update the information so that when next order comes in, I may do the calculation very quickly again. And obviously this problem is difficult because when you are thinking about whether to accept this order, you need to somehow consider the possibility of future orders. You also need to arrange and located your production resources very quickly. If you tell a customer say okay give me three days, I do some calculations and then tell you he will go away. You can only solve the problem in three minutes or three seconds. So, linear programming again is used. This company did this project in 2006 and that's going to save $12 million in a year. So most examples are just examples. Probably, you may also ask, well, why linear programming are so useful can save a company such an amount of million dollars. I will say that's possible. These kinds of successful stories are around the world and it's not news anymore. So if you really want to solve some problems within your organization, within your company and this is the first time for you to heard about linear programming. I will say you really need to take a look at this because this is powerful, and it's not my words. It has so many successful stories around the world in all kinds of industries. So this is proved to be useful. So this is proved to be useful, right? So eventually in 1975 on two scholars, they got the Nobel Prize in Economic Sciences, for their contribution to the theory of optimum allocation of resources. All right, so these two professors, they focus on linear programming. They develop many different important theories in linear programming. That's why they were awarded this award. And the award stays, it is still to their development of the theory of optimum allocation of resources. Okay, so again, resource allocation. The interesting thing is that we spend a lot of time talking about George Dantzig on the inventor of simplex method, but George Dantzig did not get the Nobel Prize. Why is that? Well, the story is the following. George Dantzig invented the simplex method while he served in the military. So the military cannot allow George Dantzig to publish this algorithm. So I need to keep it secret, and we may publish it only after the war is over. So George Dantzig invented that but he published the work after world war two and here, this professor is a Russian professor. He did some works invented some similar things, and the published earlier than George Dantizig. But unfortunately he published that in Russian, so most of the part of the world cannot understand and recognizing the work when it was published. So the impact, George Dantzig has a higher impact. But the committee thinks this professor invented and published the work earlier than that. So that's why the prize was awarded to the other professors not George Dantzig. But at least they still took a photo together and that's a very famous photo. So if you are interested in the full story or the photos here is a reference that you may want to take a look.
