Matemáticas/Programación Lineal/Historia

Inicio de sus desarrollo

El desarrollo de la programación lineal se considera entre los avances científicos más importantes del siglo XX, pues su impacto ha sido extraordinario. Actualmente es una herramienta de uso común que ha beneficiado a muchas organizaciones en distintos países con ahorros de cualquier índole, por lo que su uso se está ampliando rápidamente a todos los sectores de la sociedad. Una gran mayoría de los cálculos científicos en computadoras usan la programación lineal proliferando las publicaciones y libros sobre esta materia de gran aplicación.

Antecedentes

Uno de sus antecedentes se registra con el método de análisis de insumo-producto que desarrolló el economista W. Leontief; también se debe reconocer al economista y matemático soviético L.V. Kantorovich, quien ya en 1939 formuló y resolvió un problema de programación lineal para la organización y planeación de la producción; otro antecedente es, la interpretación de Hitchcock a "un problema de tipo de transportación" en 1941. El problema de la dieta, fue analizado por Stigler en 1945. El gran impulso de la programación lineal para la industria y los negocios se identifica con el doctor George Dantzig, matemático norteamericano de origen, que desarrolló el algoritmo Simplex, un método sistemático de resolución para problemas modelados con programación lineal. Esto ocurrió en 1947 cuando se ocupó, con Marshal Wood y asociados, de un proyecto para la Fuerza Aérea de los Estados Unidos. Se organizó un grupo de investigación con el título de Proyecto SCOOP (Scientific Computation of Optimum Programs). Actualmente las principales aplicaciones de la PL son del área industrial; también, aunque en menor parte, en el campo urbano y social.

Los años cincuenta

A partir de 1950, un número cada vez mayor de investigadores (matemáticos y economistas) aislados o constituyendo grupos contribuyen al desarrollo de las diferentes ramificaciones de la programación lineal; en particular, la "Rand Corporation" con G. B. Dantzig y W. Orchard-Hays, después L. R. Ford, D. R. Fulkerson, y D. Gale; el departamento de matemáticas de la Universidad de Princenton con A. W. Tucker y H. W. Kun; la "Graduate School of Industrial Administration" del "Carnegie Institute of Technology" con A. Charnes y W. Cooper. Los dos primeros grupos trabajan en la teoría matemática de los programas y su instalación en computadoras; los resultados se publicaron en la "Rand Corporation" en la serie de "Rand notes on linear programming and extensions" (desde 1953 a 1961); se deben mencionar las de Dantzig sobre los desarrollos teóricos, las de W. Orchard_Hays sobre la instalación de los programas de cálculo en máquinas, las de L. R Ford y D. R. Fulkerson sobre las redes de transporte; es necesario citar especialmente en el activo del grupo de Princenton, el método "húngaro" de H. W. Kun, para los problemas de asignación, la publicación de la notable colección de notas "Linear Inequalities and Related Systems" en 1956 y el método de Gomory para el cálculo de los problemas lineales en números enteros a finales del año 1958. El equipo del "Carnegie Tech" desarrolló la PL en aplicaciones industriales, se interesó en aspectos teóricos particulares como: degeneración, errores de redondeo, el Simplex revisado, variables acotadas.

Años recientes

El problema de la resolución de un sistema lineal de inecuaciones se remonta, al menos, a Fourier, después de quien nace el método de eliminación de Fourier-Motzkin. La programación lineal se plantea como un modelo matemático desarrollado durante la Segunda Guerra Mundial para planificar los gastos y los retornos, a fin de reducir los costos al ejército y aumentar las pérdidas del enemigo. Se mantuvo en secreto hasta 1947. En la posguerra, muchas industrias lo usaron en su planificación diaria.

Los fundadores de la técnica son George Dantzig, quien publicó el algoritmo simplex, en 1947, John von Neumann, que desarrolló la teoría de la dualidad en el mismo año, y Leonid Kantorovich, un matemático ruso, que utiliza técnicas similares en la economía antes de Dantzig y ganó el premio Nobel en economía en 1975. Leonid Khachiyan en 1979 fue el primero en demostrar que el problema de la programación lineal se solucionaba en tiempo polinomial, sin embargo, el mejor avance en los principios teóricos y prácticos en el campo se produjo en 1984, cuando Narendra Karmarkar introduce un nuevo método del punto interior para resolver problemas de programación lineal.

El ejemplo original de Dantzig de la búsqueda de la mejor asignación de 70 personas a 70 puestos de trabajo es un ejemplo de la utilidad de la programación lineal. La potencia de computación necesaria para examinar todas las permutaciones a fin de seleccionar la mejor asignación es inmensa; el número de posibles configuraciones excede al número de partículas en el universo. Sin embargo, toma sólo un momento encontrar la solución óptima mediante el planteamiento del problema como una programación lineal y la aplicación del algoritmo simplex. La teoría de la programación lineal reduce drásticamente el número de posibles soluciones óptimas que deberán ser revisadas.

En los últimos años, lo notable y más prometedor parece ser: La programación lineal en números enteros por R. Gomory, el principio de descomposición de Dantzig y Wolfe, los programas lineales estocásticos, el algoritmo de punto interior de Narendra Karmarkar, con aportaciones importantes de un matemático ruso I. Dikin en 1967, redescubierto, después de la publicación de Karmarkar por varios investigadores: E.R.Barnes, T. M.Cavalier y A.L.Soyster. Además R.J.Vanderbei, M.S.Meketon y B.A.Freedman publicaron en 1986, "A modification of Karmarkar's Linear Programming Algorithm". Al inicio la programación lineal se llamó "programación en estructura lineal". En 1948, Tjalling Koopmans sugirió a George Dantzing simplificar el nombre.