A Mathematician Who Solved Major Problems
SCOTT SIMON, host:
The US military and other gigantic enterprises rely on sophisticated computer programs to figure out what equipment and supplies they could, should or might need, from the number of troops and aircraft to the number of $700 toilet seats installed in submarines, the screws needed to hold them in place. The mathematics behind many of these computer programs is known as linear programming. It was developed by the US Air Force during the Second World War. The leading figure in its development was a young mathematician named George Dantzig. Last week Mr. Dantzig died at his home in Palo Alto, California. Our math guy Keith Devlin joins us to talk about his life.
Keith, thanks very much for being with us.
Hi, Scott; nice to be here.
SIMON: Well, help us understand linear programming, first.
DEVLIN: OK, so linear programming, it's a method for planning, for optimization. It's used if you want to allocate resources or production planning, worker scheduling, routing telephone calls. You can use it for planning investment portfolios, market planning, military strategies, any situation where you have an awful lot of variables that you need to juggle in order to optimize something to find the best solution. Linear programming--it's one of the most amazing pieces of genius in the history of mathematics. It takes ...(unintelligible)...
SIMON: Let me--to try and understand it first, let me interject, and I mean this sincerely.
DEVLIN: Yep. Sure.
SIMON: Is this--can you even begin to contemplate doing linear programming with a pencil and a piece of paper?
DEVLIN: You can do very simple examples of it where there are three or four parameters, but once you've got a large number of parameters, no, you can't use a pencil and paper. This is a product of the computer age. It's really no accident that these techniques were developed at the same time as modern computers were being developed. And, in fact, Dantzig himself not only developed this method, he introduced a method for solving the linear programming problem called the simplex method and turned that into a computer program, an algorithm, the simplex algorithm, which is--in fact, until computers started to be used for e-mail on the World Wide Web in the '80s and '90s, the single most important use of computers, the biggest user of computer time in the entire world was running the simplex algorithm to solve linear programming problems. I mean, no large organization cannot exist, or stay in business, without the simplex algorithm to solve linear programming problems.
One of the first applications was in the early post-war, early post-Second World War era, when food was scarce and there was an issue of what was the best diet for people. George Dantzig himself was able to map out a good minimal-priced optimal diet whereby people could be healthy, could grow up to be reasonably fit adults, with a minimal expenditure of money, and thereby, of course, the US government was able to direct farmers to grow various kind of crops, various kind of animals and livestock and so forth.
SIMON: There's a story about him, which I love, I read recently. I want to get you to tell it, about when he was a young student, handing in a test paper.
DEVLIN: Oh, yeah, this was when he first went out to--he got his master's degree by then and he went back to--this was in the late '30s--Berkeley to start to pursue a PhD, and he was enrolled in a statistics class and he went--he arrived late for class one day and on the back door there were a couple of problems written down and he thought `Oh, that must be the homework for tonight.' So he wrote the problems down and took them home and, you know, usually it took him an hour or two to solve the problem. This one--these two seemed hard, and it took him a few days, but he eventually got them out and he went along to the professor and apologized profusely for being late and said, you know, he just found these more difficult than usual. Six weeks later, early one Sunday morning, George was woken up by someone banging excitedly on the front door. So he went down, I guess in his pajamas, and there was the professor. And the professor was just overjoyed because he said, `You know, you've just solved two of the most difficult unsolved problems in statistics. We've got to write them up and submit them for publication right away.' And from that point on, it was clear that George Dantzig was no ordinary statistician.
SIMON: Our math guy, Keith Devlin, who's executive director for the Center for the Study of Language and Information(ph) at Stanford University and the author of "The Math Instinct: Why You're a Mathematical Genius"--Doesn't apply to all of us, I'm sure--along with "Lobsters, Birds, Cats and Dogs(ph)."
Keith, thanks very much.
DEVLIN: OK; my pleasure, Scott.