PHPSimplex

Biographie de George Bernard Dantzig

George Bernard Dantzig est né le 8 de Novembre de 1914 à Portland, dans l'état de l'Oregon aux États-Unis. Fils de Tobias Dantzig, mathématicien russe et Anja Ourisson, linguiste française spécialisée en langues slaves, qui ont émigré aux États-Unis en 1910, après de s'être marié.

Au début des années vingt, la famille Dantzig a déménagé de Baltimore à Washington dans l'état du Maryland, où Anja a travaillé comme linguiste dans la Bibliothèque du Congrès et Tobias a donné des cours comme professeur de mathématiques dans l'Université de Maryland, jusqu'à la retraite en laissant son poste de Chef du Département de Mathématiques peu après de la Seconde Guerre Mondiale.

Le petit George a étudié dans le Powell Junior High School et le Central High School. Déjà, enfant, il éprouve une grande fascination pour la géométrie, incité par son père qui lui proposait des problèmes compliqués de géométrie projective.

George Dantzig a fait ses études universitaires à l'Université du Maryland où il obtient la licence de Mathématiques et Physique en 1936. Cependant, déçu de n'avoir vu aucune application réelle des mathématiques dans les matières dispensés.

L'été de cette même année il s'est marié avec Anne Shmuner, et le couple décida de déménager à Ann Arbor. Il a continué avec ses études là-bas, grâce à la bourse Horace Rackham, avec un master en Mathématiques dans l'Université de Michigan. Sauf la Statistique, il avait l'impression que les cours étaient très abstraits, ce pour cela qu'il désirait une seule chose: finir ses études et envisager le monde de travail.

Ainsi, en 1937, il quitta le Michigan pour travailler dans un projet d'étude de marché («Urban study of consumer purchase») comme statisticien dans le Bureau of Labor Statistics. Pourtant, deux années après il décida de compléter ses études avec un Doctorat en Statistique sous la supervision du célèbre professeur Jerzy Neyman dans l'Université de Berkeley, en Californie.

Pendant sa première année à Berkeley il a eu une anecdote considérée comme une légende jusqu'à ce que des années après, Dantzig a corroboré sa véracité. En 1939, George assistait aux cours de Statistique donné par le professeur Jerzy Neyman, qui avait l'habitude de mettre des exercices au tableau au début des cours pour les faire à la maison. Un jour George est arrivé en retard aux cours et il a noté les deux problèmes du tableau en croyant que c'était du travail. Quelques jours après il les a donnés aux professeur Neyman, en excusant avoir pris plus de temps que d'habitude puisqu'ils étaient «un peu plus difficiles que les problèmes ordinaires». Six semaines plus tard, quand Jerzy Neyman a vérifié les notes consciencieusement et il a compris la grande découverte qui pouvait représenter, il s'est présenté chez son élève un dimanche à la première heure du matin. Il se tracassait pour proposer à Dantzig la publication d'un article fondé sur la résolution de ces exercices car il s'agissait de deux célèbres problèmes non résolus de Statistique. Après cet évènement, et la suggestion de Neyman, George Dantzig décida d'élaborer sa thèse de doctorat sur ces problèmes.

Cependant, il ne put finir son doctorat seulement en 1946 car quand les États-Unis ont commencé la confrontation de la Seconde Guerre Mondiale à la fin de 1941, il a arrêté pour la deuxième fois ses études et il a déménagé à Washington pour rejoindre l'United States Air Force. Là, il était chef de la subdivision civile d'analyse de combat dans le Centre de Contrôle Statistique (U.S.A.F. Headquarters Statistical Control). Son métier consistait à rassembler des donnés et à analyser les combats aériens (chiffres de missions, bombes larguées, aéronefs perdues, les taux de désertion, etc.), de même qu'à batailler avec les logistiques de la chaîne d'approvisionnement et la gestion de centaines de milliers de types différents de ressources matérielles et humaines. Toute cette planification se mettait en place avec des techniques manuelles, c'est pour cela que ses problèmes, apparemment insolubles, ont stimulé la recherche d'un nouveau modèle mathématique et ils mirent en place la version préliminaire de l'optimisation linéaire. Pour le travail réalisé pendant la Seconde Guerre Mondiale il a reçu une médaille pour l'exceptionnel service civile fourni au Département de la Guerre («War Department's Exceptional Civilian Service Medal») en 1944.

A la fin de la guerre, il est rentré à Berkeley pour finir son doctorat interrompu. Une fois le titre obtenu, on lui a offert un poste dans l'Université, qu'il a rejeté car un poste qu'il juge trop modeste mais avec un bon salaire (quatorze mille dollars annuel). En réalité, il a été dissuadé par sa femme qui pensait que cet argent serait insuffisant avec un enfant en charge.

En juin 1946, il considérait encore des offres de travail à Washington. Finalement, dissuadé par ses collègues de l'U.S.A.F. il accepta le poste de conseiller mathématicien pour l'Air Force. Il a travaillé sur une méthodologie qui calculait la durée des étapes d'un programme de déploiement, entraînement et approvisionnement logistique de manière plus rapide et efficace que la technique utilisée jusqu'alors. Il s'agissait d'essayer de mécaniser tout le procès de planification. Cela lui a permis de faire ses grandes découvertes.

S'appuyant sur la méthode entrée-sortie, conçu par l'économiste russe Wassily Leontief en 1939 (dont le travail a reçu le prix Nobel), il a établi le problème général d'Optimisation Linéaire. Pourtant, les problèmes posés étaient assez complexes pour les ordinateurs les plus rapides de l'époque. Il était fort nécessaire de développer une méthode capable de trouver des solutions dans un délai raisonnable. Sur ce point, l'intuition géométrique que Dantzig avait fait à sa jeunesse entrait en jeu. Selon ses propres déclarations: «J'ai commencé à observer que la région faisable était un corps convexe, c'est-à-dire, un ensemble polyédrique. Par conséquent, le procès pourrait s'améliorer si on faisait des mouvements autour des bords d'un sommet à l'autre. Cependant, ce procédé s'est avéré être inefficace. En trois dimensions, la région pourrait se voir comme un diamant à faces, arêtes et sommets. Dans le cas de beaucoup de bords, le procès mènerait à un parcours au long d'eux avant de qu'on peut atteindre le sommet optimal du diamant». Dans l'été de 1947 il effectua la première formulation de la méthode du Simplexe.

Le premier problème pratique résolu avec cette nouvelle méthode a été celui de la nutrition (ou problème de la diète) qui avait posé George Joseph Stigler à la fin de la décennie précédente, vu l'intérêt de l'armée américaine pour trouver un régime équilibré afin de nourrir ses troupes, respectant des conditions minimales de nutrition et étant économique. Le problème, qui se composait de 9 équations et 77 inconnues, a été résolu manuellement après 120 jours de travail. On a démontré que le résultat obtenu ne différait d'à peine quelques centimes de la solution trouvé avec les méthodes heuristiques, faisant de la méthode du Simplexe un vrai succès.

Dans cette époque, précisément en juin 1947, les Air Force ont établi un groupe de travail dédié à améliorer les procès de planification à grande échelle dit Proyect SCOOP (Scientific Computation of Optimal Programs). George est resté comme chef mathématicien de ce groupe jusqu'à 1952.

Le 3 d'octobre 1947 Dantzig visite le Institute for Advanced Study (IAS), un centre de troisième cycle indépendant situé à Princeton (New Jersey) où l'on fait des recherches dans divers domaines scientifiques. C'est là qu'il connait John von Neumann, considéré comme le meilleur mathématicien du monde, qui lui a parlé de son travail avec Oscar Morgenstern sur la théorie des jeux. Au fil du 1944, ce couple avait réalisé des recherches sur les jeux à somme nulle (des jeux où tous les participants connaissent a priori les stratégies et les conséquences du reste), qui ont mené à l'algorithme «minimax» qui affirme l'existence d'un coup consistant à minimiser sa perte maximum (d'où son nom). En conséquence de ses recherches ils publient le livre «Theory of Games and Economic Behavior». Ainsi, George a eu connaissance de l'importance de la Théorie de la dualité.

Au début des années 50, en juin 1952, il commença à travailler dans la RAND Corporation (Research ANd Development), une corporation fondé en 1948 pour l'United State Air Force à des fins de recherche et développement. Sa tâche était d'appliquer la méthode du Simplexe dans les ordinateurs, afin d'obtenir des résultats dans le moindre délai.

Dans l'image suivante on peut remarquer la couverture d'un de ses mémorandums de recherche publié dans la RAND. Sa référence est RM-1264 et il fut publié en 1954 sous le titre Notes on Linear Programming: The generalized Simplex method for minimizing a linear form under linear inequality restrains. A disposition pour téléchargement sur la page officielle de RAND: www.rand.org/pubs/research_memoranda/RM1264.html

En 1954, Dantzig avec d'autres collègues mathématiciens, Delbert Ray Fulkerson et Selmer Martin Johnson, ont remporté un vrai succès dans le domaine de l'optimisation combinatoire en trouvant la solution du problème du Voyageur de Commerce, reconnu en anglais comme TSP, Traveling Salesman Problem. Il faut trouver l'itinéraire optimale pour un vendeur qui doit visiter un ensemble déterminé de villes et doit accomplir les conditions suivantes: la distance totale parcourue doit être minimale, doit visiter chaque ville une seule fois et retourner au point de départ une fois une fois l'itinéraire terminé. Le problème résolu se composait de 49 villes, une pour chaque Etat des États-Unis (Alaska et Hawaii ne seront pas des états qu'à partir de 1959). Ils ont appliqué des techniques récentes d'optimisation linéaire donnant lieu au Méthode des plans sécants (Cutting-Plane method), précurseur de l'algorithme par séparation et évaluation. Les résultats de cette recherche se sont publiés dans l'article Solution of a large-scale Traveling Salesman Problem. Ce type de problèmes a des applications diverses au-delà de trouver une route minimale en logistique, de nos jours on l'utilise dans des domaines comme la conception de puces, le processus de séquence du génome, des observations astronomiques de la NASA, etc.

En général, les problèmes présentent des paramètres à une haute composante aléatoire ou l'absence de la fiabilité des données, dues entre d'autres facteurs, l'impossibilité de pouvoir déterminer l'exactitude de son avenir. Par exemple, dans un problème d'investissement en bourse, le temps affecte à la solution et à cela s'ajoute l'incertitude de si les valeurs en bourse se tiendront ou s'ils s'écrouleront catastrophiquement. Cela a donné une nouvelle branche dans l'Optimisation linéaire en 1955, dénommé Programmation stochastique, fortement développé à nouveau par George Bernard Dantzig et exprimé dans son livre Linear Programming under Uncertainty. Dans le même domaine, Evelyn Martin Lansdowne Beale a aussi effectué des recherches de façon parallèle et indépendante depuis l'Angleterre.

Cependant, les recherches de George Dantzig ne seront pas seulement ceux indiqués ci-dessus mais aussi dans l'application de variables discrètes, le problème du sac à dos, réseau et routes de chemin plus court, la méthode du Simplexe vérifiée, et bien plus encore. Un exemple de cela est une autre méthode largement employé aujourd'hui: le principe de décomposition, déroulé avec Philip Wolfe, entre 1959 et 1960. La méthode dite de Dantzig-Wolfe, établie des règles pour trouver une solution aux problèmes de grande taille, c'est-à-dire, qu'ils utilisent d'importantes quantités de données et de variables. À titre indicatif, il y a une double méthode à celle-ci, reconnue comme méthode de Décomposition de Benders, fortement exploité actuellement en Programmation stochastique.

En 1960, Dantzig rentre à l'Université de Berkeley, où il commence une brillante carrière comme professeur du département d'Ingénierie industrielle, professeur principal et conseiller de ses étudiants en doctorat. La même année, il fonde le Centre de Recherche opérationnelle (Operations Research Center) et il se nomme directeur.

Pendant cette période à Berkeley, il a écrit son livre de référence Linear Programming and Extensions, publié en août 1963. Cette publication rassemble le travail fait dans le Pentagone et dans la RAND Corporation où ils décrivent, parmi d'autres, la méthode du Simplexe, de sa théorie de base jusqu'à son usage pour résoudre des problèmes réels de différent type. On peut télécharger ce livre en format PDF sur la page officielle de RAND: http://www.rand.org/pubs/reports/R366.html

Autour de l'année 1963, Dantzig a proposé à l'administration de l'Université de Stanford (Palo Alto) la création d'un programme entre les départements de Recherche Opérationnelle des deux universités, bien que la proposition ait été refusée. Trois ans après, Dantzig commençais à travailler à l'Université de Stanford comme enseignant dans le département de Recherche Opérationnelle et d'Informatique théorique. George utilise une anecdote pour expliquer qu'une des raisons de sa mutation de Berkeley à Stanford était que la place pour se garer se trouvait dans la même porte du département où il travaillerait. Pourtant, il n'a pas eu de chance.car à sa venue, tout le parking avait disparu, même sa place bien aimé.

Les progrès en informatique pendant les années 60 ont permis d'affronter la résolution des problèmes réels en temps infini. Pour cette raison, Dantzig a fondé en 1967 à l'Université de Stanford le Systems Optimization Laboratory (SOL) pour la recherche de base et appliquée de programmation mathématique à grande échelle: élaboration d'algorithmes, formulation de modèles et production de software. Les taches de ce laboratoire comprenaient des problèmes de planification d'investissements au fil du temps, des dessins d'ingénierie et optimisation, des systèmes physiques, biologiques et écologiques, de la planification urbaine et des systèmes de transport. Parmi les projets de SOL, le plus important fut le projet PILOT pour l'amélioration dans la planification et l'économie dans le secteur énergétique des États-Unis.

George Dantzig a visité plusieurs fois l'International Institute of Applied Systems Analysis (IIASA), placé à Laxenburg (ville à 30 km de Vienne, Autriche). L'IIASA est une organisation non gouvernementale d'investigation où l'on réalise des études scientifiques dans divers domaines comme l'économie, la technologie, l'environnement ou le social. En 1973, il a passé une année sabbatique avec sa femme Anne, en contribuant comme chef du groupe de méthodologie dans les installations de l'IIASA. Une anecdote vécue par George Dantzig expose son intérêt sur l'optimisation de problèmes réels. Pendant son séjour, un jour, George s'est aperçu d'un camion spécialement long arrêté devant son bureau et, il doutait quant aux avantages d'une telle longueur, il demanda au gestionnaire Ruth Steiner sur le contenu du camion, sa provenance, la route, et comment il était possible de circuler dans les rues étroites. Les réponses de Ruth étaient qu'il transportait des meubles de Salzburg, par l'autoroute et en manouvrant pour passer dans les rues. George a étudié les données, et peu après il dit à Ruth qu'ils pouvaient économiser 40% des coûts avec 4 camions plus petits. Il suggéra de le dire à l'entreprise.

George continua son métier comme professeur dans l'Université de Stanford jusqu'en 1973, quand il obtient sa chaire C. A. Criley en Science du Transport («C. A. Criley Endowed Chair in Transportation Science»). Il prit sa retraite officiellement en 1977 bien qu'il soit resté en activité jusqu'en 1985 comme professeur émérite.

Les recherches détaillés et excellentes faits au fil de sa vie et les formidables résultats, découvertes et apports à la science ont été déterminants pour gagner des nombreux prix et de la reconnaissance. Malgré tout il n'a jamais gagné le prix Nobel.

Ainsi en 1975, George Bernard Dantzig a été le premier lauréat du prix John von Neumann Theory Prize remis par l'Institute for Operations Research and the Management Sciences grâce à son travail perpétuel et à la contribution dans ces domaines.

On le cite maintenant, «Pour l'invention de l'optimisation linéaire et la découverte des méthodes qui ont conduit aux applications scientifiques et les techniques à grande échelle de problèmes importants de logistique, planification et optimisation de réseaux, et pour l'emploi des ordinateurs pour en faire un usage efficace de la théorie mathématicienne découverte», il a reçu en 1975 la Médaille National de la Science dans la discipline de mathématiques, statistique informatisé («National Medal of Science in the Mathematical, Statistical, and Computer Sciences discipline»). Celle-ci est la plus grande distinction en sciences aux Etats unis, la cérémonie a eu lieu le 18 octobre 1976 à la Maison Blanche, où le président Gerald Ford a remis le prix.

George Dantzig a reçu des doctorats «honoris causa» dans de nombreuses Universités provenant du monde entier. On peut souligner que celui de son université alma mater du Maryland en 1976, en citant «L'Optimisation linéaire de Dantzig a été une des principaux moteurs de l'apparition d'une nouvelle discipline mathématicienne dans le domaine de la prise de décisions, dite Recherche opérationnelle dans les années 50».

En reconnaissance de son engagement, il a obtenu des distinctions tant au niveau national qu'internationaux. Certaines ont été le Prix de l'Académie nationale des sciences en Mathématiques appliquées et Analyse numérique («National Academy of Science Award in Applied Mathematics and Numerical Analysis») en 1977, le Harvey Prize en Science et Technologie de l'Université de Technion («Harvey Prize in Science and Technology») d'Israël, en 1985, et la Médaille d'Argent de la Société Britannique de Recherche opérationnelle («Silver Medal of the British Operational Research Society») en 1986. Il a eu l'honneur d'être la première personne admise dans le Hall of Fame de l'International Federation of Operational Research Societies (IFORS).

Le groupe d'anciens étudiants du professeur Dantzig composé de W. Cottle, E. L. Johnson, R. M. van Slyke, y R. J. B. Wets, ont fondé en son honneur le prix Dantzig Prize en 1982. Ce prix est décerné tous les 3 ans par la Mathematical Optimization Society (MOS) et la Society for Industrial and Applied Mathematics (SIAM).

Tout au long de sa vie, il publia de nombreux travaux et quelques livres, cependant, le livre «Linear Programming» composé de deux volumes dans lesquels il a exposé les idées principales de ses études et investigations, considéré comme la Bible de l'Optimisation linéaire et la Recherche opérationnelle. Le premier, sous-titré «Introduction» et publié en 1997 ; le deuxième, «Theory and Extensions», en 2003. Tous les deux ont été écrits conjointement avec Mukund N. Thapa. Le premier volume, comme son nom l'indique, traite des aspects de base de l'Optimisation linéaire et les applications réels, bien que dans le deuxième on élargit la théorie, et on ajoute des variantes de la méthode du Simplexe, des méthodes de points intérieurs et même la théorie des jeux, parmi d'autres.

Dantzig, lui-même, s'est surpris de l'efficace de la méthode du Simplexe, tel qu'on peut le vérifier dans une interview de 1999. Selon ses propres termes: «La plupart des occasions la méthode du Simplexe résolvait des problèmes des équations en 2ème ou en 3ème étapes, quelque chose d'impressionnant. En fait, je n'ai jamais pensé qu'elle serait si efficace. Dans cette époque, J'avais encore de l'expérience avec de problèmes de grandes dimensions et je ne faisais pas confiance en l'intuition géométrique. Par exemple, je pensais que le procédé exigeait autant d'étapes d'un sommet au suivant. Dans la pratique, il faut très peu d'étapes. Plus simplement, l'intuition en espaces de grandes dimensions n'est pas un bon guide. C'est juste maintenant, 52 ans après avoir proposé la méthode du Simplexe pour la première fois, que les gens commencent à avoir une idée du pourquoi la méthode marche si bien comme elle le fait».

Le 13 mai 2005, George Bernard Dantzig, décèda à l'âge de 90 ans dans sa maison de Stanford suite à des complications avec le diabète et des problèmes cardio-vasculaires.