Programación Lineal

CAPÍTULO 2

PROGRAMACIÓN LINEAL

2.1. El modelo de Programación Lineal
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-JosephFourier (17681830) fue el primero en intuir, aunque de forma imprecisa, los métodos de lo que actualmente llamamos programación lineal y la potencialidad que de ellos se deriva. En 1939, 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 unaextensa 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-Kantorovitch. En los años posteriores a la Segunda Guerra Mundial, en Estados Unidos seasumió 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 y simplificaciónde 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. Respecto al método simplex, que estudiaremos después, señalaremos que su 21

22

Q. MARTÍN MARTÍN

estudio comenzó en 1951 y fue desarrollado por Dantzig. Los fundamentos matemáticos de laprogramación lineal se deben al matemático norteamericano de origen húngaro John Von Neumann (1903-1957), quien en 1928 publicó su famoso trabajo sobre Teoría de juegos. La Programación Lineal es un conjunto de técnicas racionales de análisis y de resolución de problemas que tiene por objeto ayudar a los responsables en las decisiones sobre asuntos en los que interviene un gran número de variables. El nombreProgramación Lineal no procede de la creación de programas de ordenador, sino de un término militar, programar, que significa realizar planes o propuestas de tiempo para el entrenamiento, la logística o el despliegue de las unidades de combate. La Investigación Operativa en general y la programación lineal en particular recibieron un gran impulso gracias a los ordenadores. Uno de los momentos másimportantes fue la aparición del Método del Simplex. Este método, desarrollado por G. B. Dantzig en 1947, consiste en la utilización de un algoritmo para optimizar el valor de la función objetivo teniendo en cuenta las restricciones planteadas. Partiendo de uno de los vértices de la región factible, por ejemplo el vértice P, y aplicando la propiedad: si la función objetivo no toma su valor mínimoen el vértice P, entonces existe una arista que parte del vértice P y a lo largo de la cual la función objetivo no aumenta, es decir, se pasa a otro vértice donde el valor de función objetivo sea menor o igual que el alcanzado en P. Iniciarse en la técnica de programación lineal teniendo como referencia al método científico: la representación o modelo en formulación matemática lineal de algunosproblemas elegidos, será nuestro objetivo en este capítulo. La Programación Lineal es una de las técnicas agrupadas como programación matemática, aplicable a problemas de asignación de recursos limitados, con actividades competitivas hacia un objetivo común, que puede ser de maximizar beneficios o minimizar pérdidas. Se utiliza un modelo matemático con representación válida de la problemática en...