-
Augustin-Louis Cauchy, en el marco del cálculo de variaciones, utiliza por primera vez el método del descenso más pronunciado (gradiente) para sistemas de ecuaciones, un concepto fundamental que sentaría las bases para algoritmos de optimización futuros. -
El matemático estadounidense Gilbert Ames Bliss, también trabajando en cálculo de variaciones, formula problemas que pueden reconocerse como primeras formas de programación lineal, aunque sin el marco general y la notación que se desarrollarían más tarde. -
Kantoróvich aplica sus métodos teóricos a un problema concreto y crucial para el esfuerzo bélico soviético: la optimización de la producción de aleaciones para blindajes de tanques, maximizando su dureza sujeto a restricciones de composición química. Este es uno de los primeros casos documentados de aplicación exitosa de la PL. -
George B. Dantzig, trabajando para la Fuerza Aérea de EE. UU. en el proyecto SCOOP (Scientific Computation of Optimum Programs), formaliza de manera independiente y general la Programación Lineal. Su mayor contribución ese año fue la invención del Método Símplex para resolver problemas de PL de manera eficiente. Este momento es considerado el Big Bang de la PL moderna -
Aunque formulado en 1939 por el economista George Stigler, es en este año cuando se intenta resolver seriamente el "problema de la dieta de Stigler": encontrar la combinación de alimentos más barata que satisfaga las necesidades nutricionales básicas. El método de la "piedra angular" usado para resolverlo manualmente (antes del Símplex) se considera un precursor algorítmico. La solución óptima se encontró finalmente con el Símplex. -
El matemático Julia Robinson publica "On the Hamiltonian Game (A Traveling Salesman Problem)", uno de los primeros estudios formales del ahora famoso "Problema del Viajante" (TSP), un problema de optimización combinatoria íntimamente ligado a la PL y la PL Entera.
-
El método Símplex de Dantzig es programado por primera vez en una computadora, la SEAC (Standards Eastern Automatic Computer) del National Bureau of Standards (NBS). Esto demostró la viabilidad práctica de resolver problemas de PL a gran escala, marcando el inicio de su uso computarizado.
-
Ralph Gomory se une al proyecto SCOOP y comienza a trabajar en el problema de cómo obtener soluciones enteras (no fraccionarias) para problemas donde se necesita (por ejemplo, número de aviones). Sus trabajos culminarían unos años después en el Algoritmo de Planos de Corte de Gomory (1958), el primer método general para Programación Lineal Entera. -
Desarrollos de David Gale, Harold W. Kuhn y Albert W. Tucker culminan en la publicación de su teorema, formalizando por completo la Teoría de la Dualidad en programación lineal. El "Teorema de la Dualidad" y las "Condiciones de Holgura Complementaria de Kuhn-Tucker" se convierten en pilares teóricos fundamentales para entender y resolver problemas de optimización.
-
Ralph Gomory publica su histórico artículo "Outline of an algorithm for integer solutions to linear programs" en el Bulletin of the American Mathematical Society. Este algoritmo revolucionó la capacidad de abordar problemas de optimización discreta. -
Se funda la compañía IBM con su programa MPSX (Mathematical Programming System eXtended), uno de los primeros y más influyentes solvers comerciales de programación lineal y mixta. Llevó la PL del ámbito académico y gubernamental directamente a la industria, permitiendo a las empresas optimizar sus operaciones. -
Victor Klee y George J. Minty construyen un ejemplo patológico de un problema de PL que fuerza al método Símplex a recorrer un número exponencial de vértices (combinaciones posibles). Este "cubo de Klee-Minty" demostró que el Símplex, aunque eficiente en la práctica, tiene un peor caso de complejidad computacional no polinomial, lo que impulsó la búsqueda de algoritmos alternativos. -
El matemático soviético Leonid Khachiyan publica el Algoritmo del Elipsoide, el primer algoritmo de "punto interior" con complejidad temporal polinomial para resolver problemas de Programación Lineal. Aunque una revolución teórica, resultó ser lento en la práctica comparado con el metodo simplex. -
El científico indio Narendra Karmarkar, trabajando en los laboratorios Bell (ATT), anuncia su Algoritmo de Punto Interior, que no solo era polinomial sino también eficiente en la práctica para problemas muy grandes y densos. Esto marcó el desafío más serio al dominio del método Símplex y comenzó una nueva era en la resolución de problemas de optimización. -
Se funda la compañía LINDO Systems, que populariza el uso de solvers como LINDO y LINGO con un lenguaje de modelado accesible para estudiantes e industriales. Junto con otros como GAMS (1980s) y AMPL (1985), democratizó el acceso a la PL al separar la descripción del problema del algoritmo para resolverlo. -
Microsoft incluye el "Solver" de Frontline Systems como una característica estándar en Excel 3.0 para Macintosh (y luego en Windows). Esta integración puso una herramienta poderosa de optimización (incluyendo PL) en el escritorio de millones de usuarios, haciendo la PL omnipresente en el análisis empresarial. -
Surgen y maduran potentes solvers de optimización de código abierto como COIN-OR (2000), GLPK (GNU Linear Programming Kit) y luego CBC (COIN-OR Branch and Cut). Esto eliminó la barrera económica para el acceso a herramientas de alta gama, impulsando la investigación y la adopción en la academia y pequeñas empresas.
-
Los solvers comerciales (Gurobi, CPLEX, FICO Xpress) y de código abierto evolucionan para convertirse en suites de optimización híbridas. Combinan de manera sofisticada técnicas de Planos de Corte, Ramificación y Acotación (Branch-and-Bound), heurísticas y métodos de punto interior para dominar problemas de Programación Lineal Entera Mixta (MILP) a escalas antes impensables.
-
La tendencia actual se centra en usar el Machine Learning para optimizar los propios solvers (aprender estrategias de ramificación, predecir configuraciones óptimas) y en la disponibilidad de solvers de alta potencia como servicios en la nube (Google's OR-Tools, SAS Viya, solvers en AWS/Azure), haciendo la potencia computacional para PL accesible bajo demanda para cualquier empresa.
-
Una acertada gestión de los costos y recursos, apoyada en la tecnología, es fundamental para la toma de decisiones estratégicas.