LINEAR PROGRAMMINGGEORGE B. DANTZIGDepartment of Management Science and Engineering, Stanford University, Stanford, California 94305-4023The Story About How It Began: Some legends, a littleabout its historical significance, and comments about whereits many mathematical programming extensions may beheaded.Linear programming can be viewed as part of a greatrevolutionary development which has given mankindthe ability to state general goals and to lay out a path ofdetailed decisions to take in order to “best” achieve its goalswhen faced with practical situations of great complexity.Our tools for doing this are ways to formulate real-worldproblems in detailed mathematical terms (models), tech-niques for solving the models (algorithms), and engines forexecuting the steps of algorithms (computers and software).This ability began in 1947, shortly after World War II,and has been keeping pace ever since with the extraordinarygrowth of computing power. So rapid has been the advancein decision science that few remember the contributions ofthe great pioneers that started it all. Some of their namesare von Neumann, Kantorovich, Leontief, and Koopmans.The first two were famous mathematicians. The last threereceived the Nobel Prize in economics.In the years from the time when it was first proposedin 1947 by the author (in connection with the planningactivities of the military), linear programming and its manyextensions have come into wide use. In academic circlesdecision scientists (operations researchers and managementscientists), as well as numerical analysts, mathematicians,and economists have written hundreds of books and anuncountable number of articles on the subject.Curiously, in spite of its wide applicability today toeveryday problems, it was unknown prior to 1947. Thisis not quite correct; there were some isolated exceptions.Fourier (of Fourier series fame) in 1823 and the well-known Belgian mathematician de la Vallée Poussin in 1911each wrote a paper about it, but that was about it. Theirwork had as much influence on Post-1947 developments aswould finding in an Egyptian tomb an electronic computerbuilt in 3000 BC. Leonid Kantorovich’s remarkable 1939monograph on the subject was also neglected for ideolog-ical reasons in the USSR. It was resurrected two decadeslater after the major developments had already taken placein the West. An excellent paper by Hitchcock in 1941 onthe transportation problem was also overlooked until afterothers in the late 1940’s and early 1950’s had independentlyrediscovered its properties.What seems to characterize the pre-1947 era was lack ofany interest in trying to optimize. T. Motzkin in his schol-arly thesis written in 1936 cites only 42 papers on linearinequality systems, none of which mentioned an objectivefunction.The major influences of the pre-1947 era were Leon-tief’s work on the Input-Output Model of the Economy(1933), an important paper by von Neumann on Game The-ory (1928), and another by him on steady economic growth(1937).My own contributions grew out of my World War IIexperience in the Pentagon. During the war period (1941–45), I had become an expert on programming-planningmethods using desk calculators. In 1946 I was Mathemat-ical Advisor to the US Air Force Comptroller in the Pen-tagon. I had just received my PhD (for research I haddone mostly before the war) and was looking for an aca-demic position that would pay better than a low offer Ihad received from Berkeley. In order to entice me to nottake another job, my Pentagon colleagues, D. Hitchcockand M. Wood, challenged me to see what I could do tomechanize the planning process. I was asked to find a wayto more rapidly compute a time-staged deployment, train-ing and logistical supply program. In those days “mecha-nizing” planning meant using analog devices or punch-cardequipment. There were no electronic computers.Consistent with my training as a mathematician, I setout to formulate a model. I was fascinated by the work ofWassily Leontief who proposed in 1932 a large but simplematrix structure which he called the Interindustry Input-Output Model of the American Economy. It was simple inconcept and could be implemented in sufficient detail tobe useful for practical planning. I greatly admired Leontieffor having taken the three steps necessary to achieve a suc-cessful application:1. Formulating the inter-industry model.2. Collecting the input data during the Great Depression.3. Convincing policy makers to use the output.Leontief received the Nobel Prize in 1976 for developingthe input-output model.Subject classification: Professional: comments on.Area of review: Anniversary Issue (Special).Operations Research © 2002 INFORMSVol. 50, No. 1, January–February 2002, pp. 42–47420030-364X/02/5001-0042 $05.001526-5463 electronic ISSNDantzig / 43For the purpose I had in mind, however, I saw that Leon-tief’s model had to be generalized. His was a steady-statemodel and what the Air Force wanted was a highly dynamicmodel, one that could change over time. In Leontief’smodel there was a one-to-one correspondence between theproduction processes and the items being produced by theseprocesses. What was needed was a model with alternativeactivities. Finally it had to be computable. Once the modelwas formulated, there had to be a practical way to com-pute what quantities of these activities to engage in thatwas consistent with their respective input-output character-istics and with given resources. This would be no meantask since the military application had to be large scale,with thousands of items and activities.The activity analysis model I formulated would bedescribed today as a time-staged, dynamic linear programwith a staircase matrix structure. Initially there was noobjective function; broad goals were never stated explic-itly in those days because practical planners simply had nowaytoimplement such a concept. Noncomputability wasthe chief reason, I believe, for the total lack of interest inoptimization prior to 1947.A simple example may serve to illustrate the fundamen-tal difficulty of finding a solution to a planning problemonce it is formulated. Consider the problem of assigning70 men to 70 jobs. Suppose a value or benefit vijwouldresult if the ith man is assigned to the jth job. An activityconsists in assigning the ith man to the jth job. The restric-tion are: (i) each man must be assigned a job (there are 70such), and (ii) each job must be filled (also