Date: Thu, 8 Oct 1998 07:09:25 -0600 (CST)
Who is asking: Teacher
What is the history of operations research and the study of linear programming?
The first major developments in operations research came out of the
military services in World War II. Because of the war effort, there was
an urgent need to allocate scarce resources to the various military
operations and to the activities within each operation in an effective
manner. The American and British military management put together a
team of top notch scientists to do research on military operations.
Their efforts were allegedly instrumental in winning the Air Battle of
Britain, the Island Campaign in the Pacific, the Battle of the North
Atlantic, and others. Many of these new ideas and techniques
were adopted by industry in the industrial boom which followed the war.
This further fueled the development of operations research.
The advent of computers made the implementation of these techniques possible
on a large scale.
Linear programming is one important area within operations research. George B. Dantzig developed the simplex method in 1947 while working at the Pentagon. Other early pioneers in this area were von Neumann,
Kantorovich, Leontief, and Koopmans. The latter three were given
Nobel Prizes in economics for their work. In 1979, a Russian mathematician,
Khachian, had a major theoretical breakthrough regarding interior-point methods.
Shortly thereafter, Karmarker claimed to have an interior-point algorithm
whose performance was outstanding - much faster than the simplex method on
several "test problems". Karmarker worked for industry and couldn't release
the details of his algorithm. This sparked much controversy in the mathematical
community as without the details, there was no way to verify Karmarker's claims.
It has since been accepted that interior-point methods are more
effective at solving some types of problems, whereas the simplex
method is the clear winner on others. For many problems, it
is difficult to tell into which category they fit.
As an interesting aside, here is an anecdote from Dantzig's college days
at Berkeley that has even made it into ministers' sermons. Apparently he
arrived late one day for a graduate level statistics class. The professor
Dr. Neyman, had written two problems on the board which Dantzig quickly copied
down. After struggling for a period of time he finally apologetically handed
in the complete solutions to the homework problems. The professor read the solutions and was ecstatic - Neyman had presented the problems as examples
of famous unsolved problems in statistics. Dantzig himself admits that he
might not have solved the problems had he known that they were supposed to