May 25, 2005
George B. Dantzig, operations research giant, dies at 90
By Dawn Levy
George Bernard Dantzig, professor emeritus of operations research and of computer science who devised the "simplex method" and invented linear programming (which is not related to computer programming), died May 13 at his Stanford home of complications from diabetes and cardiovascular disease. He was 90 years old. A funeral service has been held.
"George B. Dantzig is regarded by most experts as having been the initiator of and leading figure in the revolutionary scientific development of mathematical programming as a powerful method for optimally managing resources in literally thousands of applications in industry and government in the last three decades," said Arthur F. Veinott Jr., professor of management science and engineering. "So pervasive is the influence of Dantzig's simplex method that experts have estimated that from 10 percent to 25 percent of all scientific computation is devoted to it. Indeed, that method is probably the single most widely used algorithm originated in the last six decades."
In 1947, Dantzig devised the simplex method, an important tool for solving linear programming problems in diverse applications, such as allocating resources, scheduling production and workers, planning investment portfolios and formulating marketing and military strategies.
"It is one of the great algorithms of the 20th century," said Gene Golub, the Fletcher Jones Professor of Computer Science. "Indeed, [Dantzig] actually created a field in devising the simplex method, namely mathematical programming."
Dantzig explained his methods in Linear Programming and Extensions, a classic work published in 1963. Nobel Prize winner Kenneth J. Arrow, the Joan Kenney Professor of Economics and Professor of Operations Research, Emeritus, described the methods in a nutshell: "Linear programming is a way of choosing interdependent activities, with inputs and outputs, so as to achieve an optimum in some dimension (e.g., profits or some index of welfare). The simplex method starts with a guess at a set of activities which are run in some measure. Then a set of prices are chosen to make the activities operate at zero profit. If none of the unchosen activities are profitable at these prices, then the initial set is optimum. If one is profitable, it is chosen, and one of the previously chosen ones is eliminated. The process is then repeated. In the end, the optimal set of activities will be arrived at."
Today, most large firms use linear programming to price products and manage supply chains. Transportation firms use it to choose the cheapest way to consolidate, coordinate and route shipments of many products from globally distributed suppliers to distant markets subject to capacity constraints. The petroleum industry uses it for exploration, blending, production scheduling and distribution. The iron and steel industry uses it to evaluate iron ores, explore the addition of coke ovens and select products. Paper mills use it to reduce trim loss. Governments use it to evaluate policy alternatives. Other applications include scheduling construction projects, refuse collection and nurses; controlling water and air pollution; selecting advertising media and compensation policies; assigning personnel to jobs; racially balancing schools; targeting weapons; rotating crops; developing bidding strategies; and designing structures.
"Practical applications often involve hundreds of thousands of variables and tens of thousands of equations," Veinott said. "The virtually simultaneous development of linear programming and computers led to an explosion of applications, especially in the industrial sector."
Linear programming and the simplex algorithm together "enabled mankind for the first time to structure and solve extremely complex optimal allocation and resource problems," said collaborator Mukund Thapa.
"Since World War II, there has been no individual whose work has had a greater impact on the mathematical sciencesand especially its applications to concrete problemsthan George B. Dantzig," said Veinott.
Indeed, Tjalling C. Koopmans, who shared the Nobel Prize in economics with Leonid Kantorovich for contributions to the theory of optimum allocation of resources, was so upset that Dantzig was not included in the 1975 award that he considered turning down the honor, according to many published accounts.
Dantzig was born in Portland, Ore., on Nov. 8, 1914, to mathematician Tobias Dantzig and translator Anja Ourisson. He received his bachelor's degree in mathematics and physics from the University of Maryland in 1936, the year he married Anne S. Shmuner. In 1938, he received his master's degree from the University of Michigan. He served as a junior statistician for the U.S. Bureau of Labor Statistics from 1937 to 1939.
During his first year as a doctoral student at the University of California-Berkeley, Dantzig arrived late to the class of Jerzy Neyman, one of the great founders of modern statistics. On the blackboard were two problems that Dantzig assumed to be homework.
"A few days later I apologized to Neyman for taking so long to do the homeworkthe problems seemed harder to do than usual," Dantzig once recalled. It turned out the conundrums, which Dantzig solved, were two famous unsolved problems in statistics.
Dantzig served as chief of the combat analysis branch of the Army Air Forces from 1941 to 1946, the year he received his doctorate in mathematics from UC-Berkeley. He was a mathematical adviser to the military (1946-1952), a research mathematician at the RAND Corp. (1952-1960) and chair and professor of the Operations Research Center at UC-Berkeley (1960 to 1966).
"About 1963, I proposed to the [Stanford] administration an interdepartmental program in operations research, which they backed, although gingerly," Arrow said in an e-mail interview. "Although there was considerable talent in different departments, there was no senior committed scholar. I spoke to George and got some encouragement. [Gerald] Lieberman, the chair of the Operations Research program (later provost), and I managed, with some difficulty, to get the university to make a good offer, which was accepted. The program became a department, perhaps the best in the country. (It has now been absorbed in the Department of Management Science and Engineering.)"
Dantzig came to Stanford in 1966, serving on the faculty of the departments of Operations Research and Computer Science. In 1973, he was appointed the C. A. Criley Professor of Transportation Sciences. His research focused on optimization of large-scale systems and the development of energy and economic planning models.
In 1975, President Gerald Ford awarded Dantzig a National Medal of Science "for inventing Linear Programming and for discovering the Simplex Algorithm that led to wide-scale scientific and technical applications to important problems in logistics, scheduling and network optimization, and to the use of computers in making efficient use of the mathematical theory."
His other awards included the War Department Exceptional Civilian Service Medal, the John von Neumann Theory Prize, the National Academy of Sciences Award in Applied Mathematics and Numerical Analysis, the Harvey Prize, the Silver Medal of the Operational Research Society (U.K.), the Alfred Coors American Ingenuity Award and a Fellows Award from the Institute for Operations Research and the Management Sciences (INFORMS).
Dantzig was a member of the National Academy of Sciences and the National Academy of Engineering and a fellow of the Econometric Society, the Institute of Mathematical Statistics, the American Association for the Advancement of Science, the American Academy of Arts and Sciences and the Operations Research Society of America. He was a president of the Institute of Management Science and first chair of the Mathematical Programming Society. He received honorary doctorates from at least eight universities and wrote at least 120 technical articles.
With Thomas L. Saaty, he wrote the book Compact City: A Plan for a Livable Urban Environment. After his retirement in 1997, he co-wrote Linear Programming 1: Introduction and Linear Programming 2: Theory and Extensions. At the time of his death he was working on a science fiction novel titled In His Own Image.
Said Arrow: "Some great scholars cast deep shadows, so that nothing grows in their neighborhood. George was just the opposite. He shortly attracted a group who flourished in his appreciation of their work and who rapidly showed wider and wider degrees of application."
Dantzig shepherded more than 50 graduate students to their doctorates. "George Dantzig had a kindly personality, free of conceit or condescension," said Richard W. Cottle, professor emeritus of management science and engineering. "For a man with such an impressive scientific reputation, he had a magical way of putting people at ease. This was especially effective with doctoral students and junior faculty, many of whom he generously supported. He was, at once, gentle, attentive to their ideashowever naïveand eager to welcome them into one of his many spheres of activity. He found just the right way to nurture the potential within them, to further their development and to incorporate their accomplishments into the goals of his large research program."
Dantzig is survived by his wife, Anne S. Dantzig; sons David and Paul Dantzig and daughter Jessica Klass; grandchildren Audra Zelvy and Aron and Jeremy Dantzig; and great-grandchildren Ivy and Brian Zelvy.
Donations in Dantzig's memory can be made to the Department of Management Science and Engineering, Stanford University, Terman Engineering Center, Room 320A, Stanford, CA 94305. For further information, contact Richard W. Cottle at (650) 725-0558.
A photo of Dantzig is available on the web at http://newsphotos.stanford.edu.