la versión original de esta historia apareció en la revista Quanta.
En 1939, al llegar tarde a su curso de estadística en UC Berkeley, George Dantzig, un estudiante de posgrado de primer año, copió dos problemas de la pizarra, pensando que eran una tarea. Encontró que la tarea era “más difícil de hacer de lo habitual”, relataría más tarde, y se disculpó con el profesor por tomarse algunos días más para completarla. Unas semanas más tarde, su profesor le dijo que había resuelto dos famosos problemas abiertos de estadística. El trabajo de Dantzig serviría de base para su tesis doctoral y, décadas más tarde, de inspiración para la película Good Will Hunting.
Dantzig recibió su doctorado en 1946, justo después de la Segunda Guerra Mundial, y pronto se convirtió en asesor matemático de la recién formada Fuerza Aérea de Estados Unidos. Como ocurre con todas las guerras modernas, el resultado de la Segunda Guerra Mundial dependió de la asignación prudente de recursos limitados. Pero a diferencia de guerras anteriores, este conflicto fue verdaderamente de escala global y se ganó en gran parte gracias al puro poder industrial. Estados Unidos simplemente podría producir más tanques, portaaviones y bombarderos que sus enemigos. Sabiendo esto, los militares estaban intensamente interesados en los problemas de optimización, es decir, cómo asignar estratégicamente recursos limitados en situaciones que podrían involucrar cientos o miles de variables.
La Fuerza Aérea encargó a Dantzig que encontrara nuevas formas de resolver problemas de optimización como estos. En respuesta, inventó el método simplex, un algoritmo que se basó en algunas de las técnicas matemáticas que había desarrollado mientras resolvía sus problemas de pizarra casi una década antes.
Casi 80 años después, el método simplex sigue estando entre las herramientas más utilizadas cuando es necesario tomar una decisión logística o de cadena de suministro bajo restricciones complejas. Es eficiente y funciona. “Siempre ha corrido rápido y nadie ha visto que no lo sea”, dijo Sophie Huiberts del Centro Nacional Francés de Investigación Científica (CNRS).
Al mismo tiempo, hay una propiedad curiosa que durante mucho tiempo ha ensombrecido el método de Dantzig. En 1972, los matemáticos demostraron que el tiempo necesario para completar una tarea podía aumentar exponencialmente con el número de restricciones. Entonces, no importa qué tan rápido pueda ser el método en la práctica, los análisis teóricos han ofrecido consistentemente los peores escenarios que implican que podría llevar exponencialmente más tiempo. Para el método simplex, “nuestras herramientas tradicionales para estudiar algoritmos no funcionan”, dijo Huiberts.
Pero en un nuevo artículo que se presentará en diciembre en la conferencia Foundations of Computer Science, Huiberts y Eleon Bach, estudiante de doctorado en la Universidad Técnica de Munich, parecen haber superado este problema. Han hecho que el algoritmo sea más rápido y también han proporcionado razones teóricas por las que los tiempos de ejecución exponenciales que se han temido durante mucho tiempo no se materializan en la práctica. El trabajo, que se basa en un resultado histórico de 2001 de Daniel Spielman y Shang-Hua Teng, es “brillante”. [and] hermosa”, según Teng.
“Es un trabajo técnico muy impresionante, que combina magistralmente muchas de las ideas desarrolladas en líneas de investigación anteriores, [while adding] algunas ideas técnicas nuevas y genuinamente interesantes”, dijo László Végh, un matemático de la Universidad de Bonn que no participó en este esfuerzo.
Geometría óptima
El método simplex fue diseñado para abordar una clase de problemas como este: supongamos que una empresa de muebles fabrica armarios, camas y sillas. Casualmente, cada armario es tres veces más rentable que cada silla, mientras que cada cama es el doble de rentable. Si quisiéramos escribir esto como una expresión, usando a, byc para representar la cantidad de muebles producidos, diríamos que la ganancia total es proporcional a 3a + 2b + c.
Para maximizar las ganancias, ¿cuántas unidades de cada artículo debe fabricar la empresa? La respuesta depende de las limitaciones que enfrenta. Digamos que la empresa puede producir, como máximo, 50 artículos por mes, por lo que a + b + c es menor o igual a 50. Los armarios son más difíciles de fabricar (no se pueden producir más de 20), por lo que a es menor o igual a 20. Las sillas requieren madera especial y su oferta es limitada, por lo que c debe ser menor que 24.
El método simplex convierte situaciones como ésta (aunque a menudo implican muchas más variables) en un problema de geometría. Imagine graficar nuestras restricciones para a, b y c en tres dimensiones. Si a es menor o igual a 20, podemos imaginar un plano en una gráfica tridimensional que es perpendicular al eje a, atravesándolo en a = 20. Estipularíamos que nuestra solución debe estar en algún lugar sobre o debajo de ese plano. Asimismo, podemos crear límites asociados con las otras restricciones. Combinados, estos límites pueden dividir el espacio en una forma tridimensional compleja llamada poliedro.