Lectura 1

LINEAR PROGRAMMING
GEORGE B. DANTZIG
Department of Management Science and Engineering, Stanford University, Stanford, California 94305-4023

The Story About How It Began: Some legends, a little about its historical significance, and comments about where its many mathematical programming extensions may be headed.

L

inear programming can be viewed as part of a great revolutionarydevelopment which has given mankind the ability to state general goals and to lay out a path of detailed decisions to take in order to “best” achieve its goals when faced with practical situations of great complexity. Our tools for doing this are ways to formulate real-world problems in detailed mathematical terms (models), techniques for solving the models (algorithms), and engines for executing the stepsof algorithms (computers and software). This ability began in 1947, shortly after World War II, and has been keeping pace ever since with the extraordinary growth of computing power. So rapid has been the advance in decision science that few remember the contributions of the great pioneers that started it all. Some of their names are von Neumann, Kantorovich, Leontief, and Koopmans. The first twowere famous mathematicians. The last three received the Nobel Prize in economics. In the years from the time when it was first proposed in 1947 by the author (in connection with the planning activities of the military), linear programming and its many extensions have come into wide use. In academic circles decision scientists (operations researchers and management scientists), as well as numericalanalysts, mathematicians, and economists have written hundreds of books and an uncountable number of articles on the subject. Curiously, in spite of its wide applicability today to everyday problems, it was unknown prior to 1947. This is not quite correct; there were some isolated exceptions. Fourier (of Fourier series fame) in 1823 and the wellknown Belgian mathematician de la Vallée Poussin in1911 each wrote a paper about it, but that was about it. Their work had as much influence on Post-1947 developments as would finding in an Egyptian tomb an electronic computer built in 3000 BC. Leonid Kantorovich’s remarkable 1939 monograph on the subject was also neglected for ideological reasons in the USSR. It was resurrected two decades later after the major developments had already taken placein the West. An excellent paper by Hitchcock in 1941 on

the transportation problem was also overlooked until after others in the late 1940’s and early 1950’s had independently rediscovered its properties. What seems to characterize the pre-1947 era was lack of any interest in trying to optimize. T. Motzkin in his scholarly thesis written in 1936 cites only 42 papers on linear inequality systems,none of which mentioned an objective function. The major influences of the pre-1947 era were Leontief’s work on the Input-Output Model of the Economy (1933), an important paper by von Neumann on Game Theory (1928), and another by him on steady economic growth (1937). My own contributions grew out of my World War II experience in the Pentagon. During the war period (1941– 45), I had become anexpert on programming-planning methods using desk calculators. In 1946 I was Mathematical Advisor to the US Air Force Comptroller in the Pentagon. I had just received my PhD (for research I had done mostly before the war) and was looking for an academic position that would pay better than a low offer I had received from Berkeley. In order to entice me to not take another job, my Pentagon colleagues, D.Hitchcock and M. Wood, challenged me to see what I could do to mechanize the planning process. I was asked to find a way to more rapidly compute a time-staged deployment, training and logistical supply program. In those days “mechanizing” planning meant using analog devices or punch-card equipment. There were no electronic computers. Consistent with my training as a mathematician, I set out to...