Optimizing resources with Linear Programming

George Bernard Dantzig biography

Photo of George Bernard Dantzig

George Bernard Dantzig Ourisson was born in 8 November 1914 in Portland, Oregon, USA. His father was Mathematics' professor, who left leaving his job as Boss of Mathematics's Apartment in the University of Maryland just after Second World War. His mother was a linguist specialized in Slavic idioms.

Dantzig studied his course at the University of Maryland, where he tooks a degree in 1936.He disliked the fact of don't see any application at any course of Mathematics that he tooks there. Next year, he took a studies of postgrade at the Mathematics School of the University of Michigan.However, excepting the Statistics, it seemed him that courses was too abstract; So abstract, that he only desired a thing: abandoning his postgrado's studies and getting a job.

In 1937, Dantzig left Michigan to work as employee in Statistics at Bureau of Labor Satistics. Two years later, he enrolled in Berkeley, to study a Statistics' Doctorate.

The history of Dantzig's doctoral thesis is a part of the anecdotes' collection of Mathematics.During his first year in Berkeley, he enrolled at Statistics' course that was giving the famous professor, Jerzy Neymann. This professor used to writing on the blackboard a couple of exercises when his classrooms began in order to, like task for the home, be resolved for his pupils and delivered at the following classroom. In an occasion, Dantzig reached later to Neymann's classrooms, and noticed that on the blackboard was written two problems. He supposed that problems were homeworks and, logically, he copied and resolved them, even though they seemed him "a little harder than the ordinary problems". A few days later he delivered them to Neymann, apologizing to have delayed so much.Approximately six weeks after, a Sunday's morning at 8:00, Neymann came beating Dantzig's door explaining him that he wrotten an introduction to one of Dantzig's goods and he was wanting and that he read it in order to be able to send the article for his publication. The two problems of task that Dantzig had resolved were, in reality, two famous problems non resolved of Statistics. The solutions of these problems became his doctoral thesis, to Neymann's suggestion.

Nevertheless, Dantzig finished off his doctorate to 1946. Just after the beginning of Second World War he joined to United States Air Force and worked with ombat Analysis Branch of Statistical Control. After receiving his Doctorate, he returned to Air Force like Mathematicas' adviser of the U. A. Air Force Controller. Was in that work where he found the problems wich took him to do his big discoveries. Air Force needed a faster way to calculate the duration time of the stages of a program of display, workout and logistic supply.

The professor Dantzig basically centered his scientific developments, chronologically, in the RAND Corporation and Berkeley's and Stanford's universities in California, with temporary assignments in another centers like the IIASA in Vienna. (The anecdote that he tells like the principal reason to move from Berkeley to Stanford, the guilty is a parking for professors just in front of his new Department door, with such bad luck that this parking had disappeared when he became incorporated to Stanford).

Dantzig's work generalized the made for the economist, winner of the Nobel Prize, Wassily Leontief. Early, Dantzig noticed that the problems of planning wich he against with them were too much complexes for 1947 fastest computers (and even for the ones belonging to the present time).

Once established the general problem of Linear Programming was necessary to find solutions in a reasonable time.Here Dantzig's geometric intuition yielded results : "I began noticing that the feasible region is a convex body, that is, a polyhedral set.Therefore, the process would be able to be improved if the movements were maded along the borders from one extreme point toward the following. However, this procedure seemed to be too inefficient. In three dimensions, the region could be visualized like a diamond with faces, edges and vertex. In the cases of many borders, the process would take an a journey along them before the diamond's point optimal corner would be reached".

This intuition carried the first formulation of the Simplex Method in the summer of 1947. The first practical problem that got worked out with this method was one of nutrition.

The October 3 l947 Dantzig visited the Institute for Advanced Study where meet for first time to John Von Neumann, who ,at that time, was considerate for a lot of people like the best Mathematician of the world. Von Neumann chatted with Dantzig about the work that he was realizing with Oscar Morgenstern about game theory.That moment went when Dantzig knew about the important theorem of duality for the first time.

Another one of his grand achievements is the theory of duality, dreamt up together with Fulkerson and Johnson in 1954 to resolve the Traveling Salesman's paradigmatic problem (resolving then problems with 49 cities when, nowadays problems get worked out, by means of modern implementations of the method, with several thousands of cities and even one million nodes) is the predecessor of useful todays Branch-and-Cut methods so utilized in entire programming to resolve problems of grand dimensions.

Many of the problems to resolve with Mathematical Programming delimit in dynamic planning through a temporary horizon.Many of parameters refer to the future and they can not be determined accurately. Rise then stochastic programming or programming under uncertainty. This branch, with a great development nowadays, and a dreadful potential for the future, he owes his development to two seminal works than of independent form were owed thanks to the professors E.Martin L Beale and George B. Dantzig in 1955.

Thus, becomes of great utilization the named method Descomposition of Dantzig-Wolfe (developed together with Philip Wolfe in 1956-1960) (whic dual is the Benders' Descomposition, so used nowadays in stochastic Programming) in order to resolve problems belonging to Structured Linear Programming.

The book "Linear Programming and Extensions" (1963), has been his great referential book during the 42 years that mediate from his publication. The cycle of his extensive bibliography has turned off with the book in two tomes "Linear Programming" ( 1997 and 2003 ), article together with N. Thapa.

In 1976 the president Gerald Ford granted Dantzig with the Science National Medal, that is the higher award of United States in Science branch. In the ceremony at White House, George Bernard Dantzig was dated "to have invented the Linear Programming, in order to have discovered methods that led to scientific applications and large-scale techniques to important problems in logistics, elaboration of programs, nets optimization and to the use of computers to do an efficient job of the mathematical theory".

The professor G. b. Dantzig could not get the reward Nobel, but received an accumulation of distinctions, among others the before mentioned, reward Von Neumann Theory in 1975, reward in Applied Mathematics and Numerical Analysis of the National Academy of Sciences in 1977, Harvey Reward in Science and Technology of Technion, Israel, in 1985. Was a member of Science's Academy and of Ingeniería's Academy Nacional of USA. The Mathematical Programming and SIAM Societies instituted several years ago a reward that takes his name, reward that is one of the more prestigious belonging to our community.

Dantzig got surprised because the simplex method work with so efficiency. Quoting again his words: "the heft of occasions the Simplex Method resolved problems of m equations in 2m or in 3m steps, something really impressive. In reality I never thought that the method got to be so efficient. Until then I not yet had experiences with problems in bigger dimensions and did not trust in my geometric intuition. For example, mi intiuition says me that the procedure needs too steps to reach one vertex to the following. In practice, are very few steps. Saying with few words, intuition in spaces of bigger dimensions is not very good guide. Only now, 52 years after I proposed the Simplex Method for first time, the people is beginning to have an idea of why the method works so well like it does".

A precision about terminology: One simplex is an especial polyhedral convex united type. More concretely, be P1, P2,. . . , Pn +1 n +1 points ( or vectors ) in R. It is said that vectors have related independence if them n vectors P1 P2, P1 P3,. . . , P1 Pn, P1 are P independent lineally. If points have related independence, then the convex smaller set that he contains the n+1 points in is named n-simplex. In R, three points have related independence if not they are colinear. The convex smaller set that no contains three points colinear a triangle with these points as like vertex. Therefore, a 2-simplex is a triangle. In R, four points have related independence if they are no "co-plane". The convex smaller set that contains four of such points is a tetrahedron. This is the 3-simplex. Triangles and tetrahedrons are united polyhedral convex, regardless of that convex polyhedral sets are not necessarily simplex. The Simplex Method was called thus by George Dantzig, although it is not clear why he elected that name. It should be more suitable call it "Set Polyhedral Convex Method".

Finally, but no the last thing, he is important to depict the programming mathematical application than the professor Dantzig went developing to long of years for various industrial sectors and of Administration, highlighting for example the project PILOT, for a better planning of the energetic sector and, therefore, a bigger energetic saving.

May 13, 2004, George Bernard Dantzig, he died to the age of 90 years at his house of Stanford due to complications with diabetes and problems cardiovasculars.


Copyright ©2006-2014 PHPSimplex. All rights reserved.
Follow us on Twitter

Version 0.9

Copyright ©2006-2014. All rights reserved.

Developed by:
Daniel Izquierdo Granja
Juan José Ruiz Ruiz

English translation by:
Luciano Miguel Tobaria

French translation by:
Ester Rute Ruiz