George Bernard Dantzig
"Los que mandan generalmente mueven las manos y dicen 'He considerado todas las alternativas'. Pero eso es casi siempre basura. Lo mas probable es que no pudiesen estudiar todas las combinaciones."
George B. Dantzig, el creador de la programación lineal, en una entrevista publicada en The College Mathematical Journal, marzo de 1986.
Biografía
George Bernard Dantzig nació el 8 de
Noviembre de 1914 en Portland, Oregon, EEUU. Su padre era profesor de
Matemáticas, se retiró dejando su puesto de Jefe del Departamento de
Matemáticas en la Universidad de Maryland poco después de la Segunda Guerra
Mundial. Su madre era una lingüista especializada en idiomas eslavos.
Dantzig estudió su carrera en la
Universidad de Maryland, donde se graduó en 1936. Le disgustaba el hecho de no
haber visto ni una sola aplicación en alguno de los cursos de Matemáticas que
había tomado allí. Al año siguiente hizo estudios de postgrado en la escuela de
Matemáticas de la Universidad de Michigan. Sin embargo, exceptuando la
Estadística, le pareció que los cursos eran demasiado abstractos; tan abstractos,
que él sólo deseaba una cosa: abandonar sus estudios de postgrado y conseguir
un trabajo.
En 1937 Dantzig dejó Michigan para
trabajar como empleado en Estadística en el Bureau of Labor Statistics. Dos
años después se inscribía en Berkeley para estudiar un Doctorado en
Estadística.
La historia de la tesis doctoral de
Dantzig es ahora parte del anecdotario de las Matemáticas. Durante su primer
año en Berkeley, se inscribió en un curso de Estadística que impartía el famoso
profesor Jerzy Neymann. Este profesor tenía la costumbre de escribir en la
pizarra un par de ejercicios al comenzar sus clases para que, como tarea para
el hogar, fueran resueltos por sus alumnos y entregados en la clase siguiente.
En una ocasión llegó tarde a una de las clases de Neymann y se encontró con dos
problemas escritos en la pizarra. Supuso que eran problemas de tarea y,
consecuentemente, los copió y los resolvió, aun cuando le parecieron "un
poco más difíciles que los problemas ordinarios". Unos días después se los
entregó a Neymann, disculpándose por haber tardado tanto. Aproximadamente seis
semanas después, un domingo a las 8:00 de la mañana, Neymann llegó aporreando
la puerta de Dantzig, explicándole que había escrito una introducción a uno de
los artículos de Dantzig y que quería que la leyera a fin de poder enviar el
artículo para su publicación. Los dos "problemas de tarea" que
Dantzig había resuelto eran, en realidad, dos famosos problemas no resueltos de
la Estadística. Las soluciones de estos problemas se convirtieron en su tesis
doctoral, a sugerencia de Neymann.
El profesor Dantzig centró
básicamente sus desarrollos científicos, cronológicamente, en la RAND
Corporation y las universidades de Berkeley y Stanford en California, con
asignaciones temporales en otros centros como el IIASA en Viena. (Es gozosa la
anécdota que él cuenta como la razón principal para moverse de Berkeley a
Stanford, la "culpa" es de un aparcamiento de coches para los
profesores en la misma puerta de su nuevo Dpto. con tal mala fortuna que este
aparcamiento ya había desaparecido cuando él se incorporó a Stanford).
El trabajo de Dantzig generalizó lo
hecho por el economista, ganador del Premio Nobel, Wassily Leontief. Dantzig
pronto se dio cuenta de que los problemas de planeación con los que se
encontraba eran demasiado complejos para las computadoras más veloces de 1947
(y aun para las de la actualidad).
Habiéndose ya establecido el problema
general de Programación Lineal, fue necesario hallar soluciones en un tiempo
razonable. Aquí rindió frutos la intuición geométrica de Dantzig: "Comencé
observando que la región factible es un cuerpo convexo, es decir, un conjunto
poliédrico. Por tanto, el proceso se podría mejorar si se hacían movimientos a
lo largo de los bordes desde un punto extremo al siguiente. Sin embargo, este
procedimiento parecía ser demasiado ineficiente. En tres dimensiones, la región
se podía visualizar como un diamante con caras, aristas y vértices. En los
casos de muchos bordes, el proceso llevaría a todo un recorrido a lo largo de
ellos antes de que se pudiese alcanzar el punto de esquina óptimo del
diamante".
Esta intuición llevó a la primera
formulación del método simplex en el verano de 1947. El primer problema
práctico que se resolvió con este método fue uno de nutrición.
El 3 de octubre de l947 Dantzig
visitó el Institute for Advanced Study donde conoció a John von Neumann, quien
por entonces era considerado por muchos como el mejor Matemático del mundo. Von
Neumann le habló a Dantzig sobre el trabajo conjunto que estaba realizando con
Oscar Morgenstern acerca de la teoría de juegos. Fue entonces cuando Dantzig
supo por primera vez del importante teorema de la dualidad.
Otro de sus grandes logros es la
teoría de la dualidad, ideado conjuntamente con Fulkerson y Johnson en 1954
para resolver el paradigmático problema del Agente Viajero (resolviendo
entonces problemas con 49 ciudades cuando, hoy día, mediante modernas
implementaciones del método, se resuelven problemas con varios miles de
ciudades y hasta un millón de nodos) es el precursor de los hoy utilísimos
métodos de Branch-and Cut (Bifurcación y corte) tan utilizados en programación
entera para resolver problemas de grandes dimensiones.
Muchos de los problemas a resolver
mediante Programación Matemática se enmarcan en planificación dinámica a través
de un horizonte temporal. Muchos de los parámetros se refieren al futuro y no
se pueden determinar con exactitud. Surge entonces la programación estocástica
o programación bajo incertidumbre. Esta rama, con un gran desarrollo hoy día, y
un tremendo potencial para el futuro, debe su desarrollo a dos trabajos
seminales que de forma independiente son debidos a los profesores E.Martin L Beale
y George B. Dantzig en 1955.
El libro "Linear Programming and
Extensions" (1963), ha sido su gran libro de referencia durante los 42
años que median desde su publicación. Ha cerrado el ciclo de su extensa
bibliografía con el libro en dos tomos "Linear Programming" (1997 y
2003), escrito conjuntamente con N. Thapa.
En 1976 el presidente Gerald Ford
otorgó a Dantzig la Medalla Nacional de Ciencias, que es la presea más alta de
los Estados Unidos en Ciencia. En la ceremonia en la Casa Blanca se citó a
George Bernard Dantzig "por haber inventado la Programación Lineal, por
haber descubierto métodos que condujeron a aplicaciones científicas y técnicas
en gran escala a problemas importantes en logística, elaboración de programas,
optimización de redes y al uso de las computadoras para hacer un empleo
eficiente de la teoría matemática".
El profesor G. B. Dantzig no pudo
conseguir el premio Nobel, pero recibió un cúmulo de distinciones, entre otras
la mencionada anteriormente, el premio Von Neumann Theory en 1975, Premio en
Matemáticas Aplicadas y Análisis Numérico de la National Academy of Sciences en
1977, Harvey Prize en Ciencia y Tecnología de Technion, Israel, en 1985. Fue
miembro de la Academia de Ciencias y de la Academia Nacional de Ingeniería de
EEUU. Las Sociedades de Programación Matemática y SIAM instituyeron hace años
un premio que lleva su nombre, premio que es uno de los más prestigiosos de
nuestra comunidad.
Dantzig se sorprendió de que el método
simplex funcionara con tanta eficiencia. Citando de nuevo sus palabras:
"La mayor parte de las ocasiones el método simplex resolvía problemas de m
ecuaciones en 2m o en 3m pasos, algo realmente impresionante. En realidad nunca
pensé que fuese a resultar tan eficiente. En ese entonces yo aún no había
tenido experiencias con problemas en dimensiones mayores y no confiaba en mi
intuición geométrica. Por ejemplo, mi intuición me decía que el procedimiento
requeriría demasiados pasos de un vértice al siguiente. En la práctica son muy
pocos pasos. Dicho con pocas palabras, la intuición en espacios de dimensiones
mayores no es muy buena guía. Sólo ahora, 52 años después de haber propuesto el
método simplex por primera vez, la gente está comenzando a tener una idea de
por qué el método funciona tan bien como lo hace".
Una precisión acerca de la
terminología: un simplex es un tipo especial de conjunto convexo poliédrico.
Más concretamente, sean P1, P2, . . . , Pn+1 n+1 puntos (o vectores) en R. Se
dice que los vectores tienen independencia afín si los n vectores P1 P2, P1 P3,
. . . , P1 Pn, P1 P son linealmente independientes. Si los puntos tienen
independencia afín, entonces el conjunto convexo más pequeño que contiene los
n+1 puntos en se llama n-simplex. En R, tres puntos tienen independencia afín
si no son colineales. El conjunto convexo más pequeño que contiene tres puntos
no colineales es un triángulo con estos puntos como vértices. Por tanto, un
2-simplex es un triángulo. En R, cuatro puntos tienen independencia afín si no
son coplanares. El conjunto convexo más pequeño que contiene cuatro de tales
puntos es un tetraedro. Este es el 3-simplex. Los triángulos y los tetraedros
son conjuntos poliédricos convexos, no obstante que los conjuntos convexos
poliédricos no son necesariamente simplex. El método simplex fue llamado así
por George Dantzig, aunque no está claro por qué eligió ese nombre. Habría sido
más adecuado llamarlo "método del conjunto convexo poliédrico".
Por último, pero no lo último, es
importante reseñar la aplicación de programación matemática que el profesor
Dantzig fue desarrollando a lo largo de los años para diversos sectores
industriales y de la Administración, destacando a título de ejemplo el proyecto
PILOT, para una mejor planificación del sector energético y, por tanto, un
mayor ahorro energético.
El 13 de Mayo de 2004, George Bernard
Dantzig, murió a la edad de 90 años en su casa de Stanford debido a
complicaciones con la diabetes y problemas cardiovasculares.
George Dantzig y su actuar en la segunda guerra mundial y el pentágono.
Cuando comenzó la Segunda Guerra
Mundial, los estudios de Dantzig en Berkeley fueron suspendidos, y este se
convirtió en la cabeza de la Rama de Análisis de Combate de los Cuarteles
Centrales Estadísticos de Fuerza Aérea de los Estados Unidos, lo cual lo llevó
a lidiar con las logísticas de la cadena de abastecimiento y gestión de cientos
de miles de ítems y personas. El trabajo proporcionó los problemas del
"mundo real" que la programación lineal vendría a resolver.
Además de su trabajo significativo en
el desarrollo del método simplex y la programación lineal, Dantzig también hizo
avances en los campos de la teoría de la descomposición, análisis de
sensibilidad, métodos de pivot complementarios, optimización a gran escala,
programación no lineal, y programación bajo incertidumbre. El primer ejemplar
del SIAM Jornal on Optimization en 1991 fue dedicado a él.
Tobías Dantzig
Tobías Dantzig (19 de febrero de 1884
– 9 de agosto de 1956) fue un matemático ruso-estadounidense del grupo de los
alemanes del Báltico (Deutschbalten o Baltendeutsche), el padre de George
Dantzig, y el autor de NUMBER: The Language of Science (A Critical Survey
Written for the Cultured non Mathematician)(Nueva York, Macmillan, 1930, 1933,
1939, 1954) y Aspects of Science (Nueva York, Macmillan, 1937). El primero de
los libros citados tuvo amplia aceptación del público no matemático y un
comentario elogioso de Albert Einstein.
Nacido en Letonia, Dantzig estudió
matemáticas con Henri Poincaré en París. Tobias se casó con una estudiante de
la Universidad de la Sorbona, Anja Ourisson, y la pareja emigró a los Estados
Unidos de América en 1910. Trabajando un tiempo en Oregón como leñador,
constructor de caminos y pintor de edificios, Dantzig recibió su doctorado en
matemáticas de la Universidad de Indiana en 1917.1 Él enseñó en la Universidad
de Columbia, en la Universidad Johns Hopkins, y en la Universidad de Maryland.
Dantzig murió en Los Ángeles en 1956
Jerzy
Neyman: profesor de estadistica de George Dantzig
ENTREVISTA A GEORGE BERNARD DANTZIG PUBLICADA EN THE
COLLEGE MATHEMATICAL JOURNAL, EN MARZO DE 1986.
«Considere el problema de asignar 70 hombres a 70
empleos. Una 'actividad' consiste en asignar el i-ésimo hombre al j-ésimo
empleo. Las restricciones son dos: en primer lugar hay 70 hombres, cada uno de
los cuales debe asignarse a un puesto, y en segundo lugar, cada uno de los 70
puestos existentes debe estar ocupado. El nivel de una actividad puede ser 1,
lo cual indica que está siendo usada, o 0, lo cual significa que no. En
consecuencia hay 2 x 70 = 140 restricciones y 70 x 70 = 4900 actividades con
4900 variables correspondientes de decisión uno-cero. Por desgracia también hay
factorial de 70 permutaciones o formas de hacer las asignaciones. El problema
consiste en comparar estas factorial de 70 formas y elegir la que sea la óptima
o 'mejor' según algún criterio previamente establecido.»
«En el ejemplo anterior, factorial de 70 es un
número muy grande. A fin de tener una idea de qué tan grande es, supóngase que
se hubiese tenido una computadora IBM del tipo main-frame en el instante en el
que ocurrió el Big Bang hace quince millones de años. ¿Habría podido, entre ese
entonces y ahora, examinar todas las soluciones posibles? ¡No! No obstante,
supóngase que se hubiese tenido una computadora aun más poderosa, una que
pudiese examinar mil millones de asignaciones por segundo. La respuesta
seguiría siendo negativa. Aun si la Tierra se llenase con computadoras cuyas
rapideces fueran de nanosegundos, todas ellas trabajando en paralelo, la
respuesta aun sería no. Sin embargo, si existiesen diez Tierras, todas llenas
con computadoras del tipo mencionado, todas programadas en paralelo desde el
instante del Big Bang hasta que el Sol fuese una esfera fría, entonces quizás
la respuesta podría ser sí. Lo notable es que el método Simplex, con la ayuda
de una computadora moderna, puede resolver este problema en una fracción de
segundo.»
«Cuando el problema de la planeación fue formulado
inicialmente para la Fuerza Aérea, no existía la noción exacta de una función
objetivo, la idea de una meta claramente definida. Por supuesto, teníamos sólo
un falso respeto hacia el concepto de objetivo. En el discurso de los militares
escuché a menudo decir, 'nuestro objetivo es ganar la guerra'. En el mundo de
los negocios se escucharía quizás 'nuestro objetivo es obtener ganancias'. Sin
embargo, era imposible hallar alguna relación directa entre la meta establecida
y las acciones emprendidas para tal fin.»
«Si se estudiaba con cuidado el paso siguiente, se
podía ver que algún líder había promulgado un montón de reglas básicas que, en
su concepto, llevarían a la meta. Esto distaba mucho de lo que sería
honestamente estudiar todas las combinaciones alternativas de las acciones a
seguir para elegir la mejor combinación. Los que mandan generalmente mueven las
manos y dicen 'He considerado todas las alternativas'. Pero eso es casi siempre
basura. Lo más probable es que no pudiesen estudiar todas las combinaciones. Antes
de 1947 era inconcebible pensar en la existencia de una herramienta como la
programación lineal que permitiese examinar millones de combinaciones. No había
algoritmo o herramienta computacional que pudiera hacer eso.»
«No descubrí el modelo de la programación lineal en
un instante, sino que tuvo un proceso de evolución. Se dedicó casi un año
completo a la tarea de decidir si mi modelo podría ser utilizado en la
formulación de problemas prácticos de distribución de tiempos. Como usted sabe,
la planeación y la distribución de tiempos se llevaron a una escala inmensa
durante la guerra. El funcionamiento de la Fuerza Aérea fue equivalente al
funcionamiento de la economía de toda una nación. En el proceso intervinieron
cientos de miles de personas. La logística tuvo una magnitud difícil de
entender para alguien que no haya estado allí. Mi colega Marshall Wood y yo
revisamos miles de situaciones tomadas de nuestra experiencia durante la
guerra.»
«Las reglas básicas empleadas en la planeación se
expresaban en un formato completamente distinto del que se emplea en la
actualidad para formular un programa lineal. Lo que hicimos fue revisar estas
reglas una por una y demostrar que casi todas ellas podían reformularse
aceptablemente en un formato de programación lineal. Pero no todas. En algunos
casos era necesario tomar en cuenta el carácter discreto de las variables y las
no convexidades.»
«Cuando formulé por primera vez mi modelo de
programación lineal, lo hice sin una función objetivo. Estuve luchando por
algún tiempo con la adición de reglas básicas para elegir de entre las
soluciones factibles la que en algún sentido fuese 'óptima'. Pero pronto
abandoné esta idea y la sustituí por la de una función objetivo a ser
maximizada. El modelo que formulé no estaba hecho específicamente para fines
militares. Podía aplicarse a toda clase de problemas de planeación; todo lo que
tenía que hacerse era cambiar los nombres de las columnas y los renglones, y
entonces era aplicable a un problema de planeación económica lo mismo que a un
problema de planeación industrial.»
FUENTES:
FUENTES:
Jerzy Neyman (16 de abril de 1894, en Moldavia – 5 de agosto de 1981, California) fue un matemático polaco. Fue el segundo de cuatro hijos de Czesław Spława-Neyman y Kazimiera Lutosławska. Publicó muchos libros relacionados a experimentos y estadísticas. Neyman ideó la forma en la cual la FDA testea los medicamentos en la actualidad.
