Programación lineal

Programación lineal: su historia
En los siglos XVII y XVIII, grandes matemáticos, como Newton, Leibnitz, Bernoulli y, sobre todo, Lagrange, que tanto habían contribuido al desarrollo del cálculo infinitesimal, se ocuparon de obtener máximos y mínimos condicionados de determinadas funciones.
Posteriormente, el matemático francés Jean Baptiste-Joseph Fourier (1768-1830) fue el primeroen intuir, aunque de forma imprecisa, los métodos de lo que actualmente llamamos programación lineal y la potencialidad que de ellos se deriva.
Si exceptuamos al matemático Gaspar Monge (1746-1818), quien en 1 776 se interesó por problemas de este género, debemos remontarnos al año 1 939 para encontrar nuevos estudios relacionados con los métodos de la actual programación lineal. En eseaño, el matemático ruso Leonid Vitalevich Kantorovitch publica una extensa monografía titulada Métodos matemáticos de organización y planificación de la producción en la que por primera vez se hace corresponder a una extensa gama de problemas una teoría matemática precisa y bien definida, llamada hoy en día programación lineal.
En 1941-1942 se formula por primera vez el problema de transporte,estudiado independientemente por Koopmans y por Kantorovitch, razón por la cual se suele conocer con el nombre de problema de Koopmans-Kantorovftch.
[pic]Koopmans, Dantzig y Kantorivich
Tres años más tarde, G. Stigler plantea otro problema particular conocido con el nombre de régimen alimenticio optimal.
En los años posteriores a la Segunda Guerra Mundial, en Estados Unidosse asumió que la eficaz coordinación de todas las energías y recursos de la nación era un problema de tal complejidad, que su resolución y simplificación pasaba necesariamente por los modelos de optimización que resuelve la programación lineal.
Paralelamente a los hechos descritos se desarrollan las técnicas de computación y los ordenadores, instrumentos que harían posible la resolución ysimplificación de los problemas que se estaban gestando.
En 1947, G. B. Dantzig formula, en términos matemáticos muy precisos, el enunciado estándar al que cabe reducir todo problema de programación lineal. Dantzig, junto con una serie de investigadores del United States Departament of Air Force, formarían el grupo que dio en denominarse SCOOP (Scientific Computation of Optimum Programs).Respecto al método simplex, que estudiaremos después, señalaremos que su estudio comenzó en 1951 y fue desarrollado por Dantzig en el United States Bureau of Standards SEAC COMPUTER, ayudándose de varios modelos de ordenador de la firma International Business Machines (IBM).
Los fundamentos matemáticos de la programación lineal se deben al matemático norteamericano de origen húngaroJohn (Janos) Von Neumann (1903-1957), quien en 1928 publicó su famoso trabajo Teoría de juegos. En 1 947 conjetura la equivalencia de los problemas de programación lineal y la teoría de matrices desarrollada en sus trabajos. La influencia de este respetado matemático, discípulo de Dávid Hilbert en Gotinga y, desde 1 930, catedrático de la Universidad de Princeton de Estados Unidos, hace que otrosinvestigadores se interesaran paulatinamente por el desarrollo riguroso de esta disciplina.
La Programación Lineal es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de ecuaciones lineales, optimizando la función objetivo, también lineal.
Consiste en optimizar (minimizar o maximizar) una función lineal, denominada función objetivo,de tal forma que las variables de dicha función estén sujetas a una serie de restricciones que expresamos mediante un sistema de inecuaciones lineales.


Historia de la programación lineal


[pic]

El problema de la resolución de un sistema lineal de inecuaciones se remonta, al menos, a Joseph Fourier, después de quien nace el método de eliminación de Fourier-Motzkin. La programación...