George Dantzig

 A Legend In Operation Research

by Lingqing Yao

Everyone works in operation research should know the name of George Dantzig, because he played fundamentally important role in this field. His invention of simplex method, and his remarkable academic life made him a legend till today. 

 Lingqing Yao is a PhD Candidate at Polytechnique School of MOntreal in Industrial engineering

 Lingqing Yao is a PhD Candidate at Polytechnique School of MOntreal in Industrial engineering

George Dantzig worked for US Army Air Force during World War II, his job was specialized on planning with data collected from the air combat. At that time, computer was still in prototype, and he did his job with a hand calculator.

Dantzig’s colleagues challenged him to mechanize the military planning so that he might not get bored with the tedious work. Dantzig formulate the problem into a linear programming problem while he realized that the planning goals could be expressed as a linear objective function. The simplex method was developed to solve the linear programming problem in roughly about one year’s time. The method was revolutionary that Dantzig found an efficient way to get the optimal solution by only checking extreme points on the boundary of linear constraints without diving into enormous feasible solutions within the boundary. The following paragraph gives a simple example which graphically shows the principle of Simplex method.

Minimize: Constraints:

 Figure. 1. Graphically solve the minimizing problem (The domain of feasible solution to the problem is confined by the black polygon area.)

 Figure. 1. Graphically solve the minimizing problem (The domain of feasible solution to the problem is confined by the black polygon area.)

From the Figure 1, the optimal solution of the problem is:

and the optimal value of the problem is:

A widespread story of Dantzig came from his Phd study with Professor Jerzy Neyman at UC Berkeley. While one day Dantzig was late for the class, Neyman wrote two famously unsolved problems on the blackboard before he arrived. Dantzig took the two problems as homework and worked quite hard to solve them in a few days and he thought his assignment was overdue. Six weeks later, excited Neyman invited him to publish a paper since he solved two most famous statistics problems. An interview with Dantzig was hilarious: “A year later, when I began to worry about a thesis topic, Neyman just shrugged and told me to wrap the two problems in a binder and he would accept them as my thesis.”

This reminds me what our instructor, Ms. Sylvie Gendreau said in the class, to be positively thinking is Sooooo important.

Dantzig refused an offer from UC Berkeley after he finished his Phd because his wife thought the salary was too low to raise a baby. In 1966 he became Professor in Stanford and developed a department of operation research in one year and retired there years later.


References:

George B. Dantzig. 1990. Origins of the simplex method. In A history of scientific computing, Stephen G. Nash (Ed.). ACM, New York, NY, USA 141-151.

http://www-groups.dcs.st-and.ac.uk/history/Biographies/Dantzig_George.html

https://en.wikipedia.org/wiki/George_Dantzig

https://en.wikipedia.org/wiki/Simplex_algorithm