GEORGE BERNARD DANTZIG Y LA HISTORIA (Y EL FUTURO) DE LA PROGRAMACIÓN LINEAL
 |
| George Bernard Dantzig |
George Bernard Dantzig nació el 8 de
noviembre de 1914 en Portland, Oregon. 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 en Maryland"1. Al año siguiente hizo estudios de posgrado
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 posgrado 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, llevó un curso de Estadística con el famoso Jerzy Neymann. En una
ocasión llegó tarde a una de las clases de Neymann. En la pizarra estaban
escritos dos problemas que él supuso eran problemas de tarea. Dantzig,
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 llegado tarde.
Aproximadamente seis semanas después -a las
8:00 de un domingo por 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.
No obstante, Dantzig terminó su doctorado
hasta 1946. Poco después del comienzo de la Segunda Guerra Mundial se unió a la
Fuerza Aérea de Estados Unidos y trabajó con el Combat Analysis Branch of Statistical
Control. Después de recibir su Doctorado, regresó a la Fuerza Aérea como el
asesor de Matemáticas del U. S. Air Forcé Controller. Fue en ese trabajo donde
encontró los problemas que le llevaron a hacer sus grandes descubrimientos. La
Fuerza Aérea necesitaba una forma más rápida de calcular el tiempo de duración
de las etapas de un programa de despliegue, entrenamiento y suministro
logístico.
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). La siguiente es la explicación de Dantzig acerca de las
dificultades que tuvo que encarar: "Un ejemplo sencillo ilustra la
dificultad fundamental de formular un problema de planeación utilizando un
enfoque de análisis de actividades. 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 el factorial de las 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 mainframe 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 aún más poderosa, una que
pudiese examinar mil millones de asignaciones por segundo. La respuesta
seguiría siendo negativa. Aún si la tierra se llenase con computadoras cuyas
rapideces fueran de nanosegundos, todas ellas trabajando en paralelo, la
respuesta aún 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".
Antes de que Dantzig pudiese descubrir el
método simplex, le fue necesario primero tener un modelo práctico de
Programación Lineal. He aquí la descripción de Dantzig del proceso:
"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 hacia la
meta. Esto distaba mucho de lo que sería honestamente estudiar todas las
combinaciones alternativas de las acciones para elegir la mejor combinación.
Los que mandan, generalmente mueven las manos y dicen "He considerado
todas las alternativas", pero 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 ahí. 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".
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 1947 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 platicó a Dantzig del 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.
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".
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, 50 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
Rn+1. Se dice que los vectores tienen
independencia afín si los n vectores P1P2, P1P3,…,
P1Pn, P1Pn+1 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 Rn+1 se
llama n-simplex. En R3, 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 R4, 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. Véase la figura adjunta:
Los triángulos y los tetraedros son conjuntos
poliédricos convexos, no obstante que los conjuntos convexos poliédricos no son
necesariamente simplex. Por ejemplo, en A3 un
rectángulo es un conjunto convexo poliédrico pero no es un simplex (véase la
definición precedente). El método simplex fue llamado así por George Dantzig,
aunque no es claro por qué eligió ese nombre. Habría sido más adecuado llamarlo
"método del conjunto convexo poliédrico".
El profesor 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.
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.
Siguiendo cronológicamente, en 1979 el ruso
L. G. Khachiyan presentó un algoritmo para resolver problemas de Programación
Lineal denominado algoritmo del elipsoide, el cual consiste en ir reduciendo la
región de factibilidad encerrándola en elipsoides de volúmenes decrecientes.
Telgen en su estudio, en lugar de analizar el
número de iteraciones por problema, hace un análisis del número de operaciones
por iteración y obtiene:
Simplex: (3 + d) m2 + dmn
Khachiyan: (3 + d) n2 + dmn
Donde
d: densidad de la matriz de coeficientes
tecnológicos
m: número de ecuaciones
n: número de variables
De los trabajos de Telgen se puede concluir
que el algoritmo de L.G. Khachiyan es atractivo solamente en problemas en los
que el número de restricciones es mayor que el número de desigualdades, pero en
ese caso puede ser más indicado la utilización del algoritmo simplex dual.
En 1984, Narendra Karmarkar (nació en 1956) Matemático
de la India que trabajaba en AT & T Bell Laboratories creó un nuevo y
poderoso algoritmo de Programación Lineal que resuelve muchos problemas complejos
de esta área con mayor rapidez y de manera más eficiente que cualquier otro
método conocido hasta ahora. Este método alternativo para la Programación Lineal
evita la lentitud mediante la búsqueda de rutas a través del interior de la
región factible. Las posibles aplicaciones del algoritmo de Karmarkar son
importantes para muchas industrias, incluyendo las comunicaciones telefónicas y
las aerolíneas. Elegir rutas para los millones de llamadas de larga distancia, por
ejemplo, significa decidir cómo usar las líneas telefónicas existentes, los
amplificadores y las terminales de los satélites para obtener la mayor ventaja.
Encontramos otro ejemplo en las empresas de líneas aéreas. La compañía American
Airlines trabajó con el doctor Karmarkar para ver si este algoritmo podría
reducir los costes de combustible. De acuerdo con Thomas Cook, director de
investigación operativa de American Airlines.
 |
| NARENDRA KARMARKAR |
En la década de 1980, científicos de losLaboratorios
Bell aplicaron el algoritmo de Karmarkar a un problema de complejidad sin
precedentes: decidir cuál es la manera más económica de construir conexiones
telefónicas entre ciudades de los Estados Unidos, de manera que las llamadas
puedan llegar de una ciudad a otra, pasando por ciudades intermedias.
El trabajo con estos problemas en los
Laboratorios Bell implicaba manipular problemas de Programación Lineal de cerca
de 800000 variables, que el algoritmo de Karmarkar puede resolver en 10 horas
de tiempo de computador. Los científicos involucrados en este proyecto creían
que el problema podría haber tardado semanas en resolverse si se hubiera usado el
método del simples o el del elipsoide. El algoritmo de Karmarkar ha sido
incorporado a un programa de computador denominado AT & T KORBX Linear
Programming System.
El futuro
Parte importante del futuro de la
Investigación de Operaciones corresponde a la Programación Multicriterio, a la
Programación Multiobjetivo y las Metaheurísticas.
La Programación Multicriterio corresponde a
problemas con decisión de objetivos de tipo discreto y la Programación
Multiobjetivo está relacionada con problemas de tipo continuo.
Una Metaheurística es un método de solución
general, que proporciona, tanto una estructura general como criterios
estratégicos para desarrollar un método heurístico específico que se ajusta a un
tipo particular de problema.
Entre las nuevas metaheurísticas se
encuentran:
- Recocido Simulado.
- Búsqueda Tabú.
- GRASP.
- Redes Neuronales.
- Algoritmos Genéticos.
- Algoritmos Meméticos.
- Particles Swarm Optimization (Optimización
de Nube de Partículas).
1Las citas que aparecen en esta reseña se han
tomado de la entrevista con Dantzig que fue publicada en la edición de marzo de
1986 de The College Mathematical Journal, páginas de la 293 a la 314. Los
entrevistadores fueron Donald J. Albers y Constance Reíd.
Aquí van los anuncios
Comentarios