Historia de la programacion lineal

HISTORIA DE LA PROGRAMACION LINEAL

La programación lineal empieza en la segunda guerra mundial para planificar los gastos y retornos y así optimizar los costes del ejército y producir mayores gastos en el ejército enemigo. Fue un secreto militar hasta 1947, año en el que muchas empresas empezaron a utilizarlo para reducir costes y mejorar su productividad que a día de hoy se sigue utilizando a lo largo de todo el mundo.

Joseph Fourier fue el pionero en la resolución de ecuaciones lineales por eliminación en 1826, gracias al cual, posteriormente los siguientes matemáticos fundaron la programación lineal:

George Bernard Dantzig (1914-2005, Estados Unidos):

Es considerado el padre de la programación lineal y creador del algoritmo del simplex. Nació en Portland en 1914, estudio las carreras de matemáticas y física en la universidad de Maryland y posteriormente se doctoro en la universidad de Berkeley (California). Cuenta el mito que George un día llego tarde a clase y copio de la pizarra dos problemas de estadística que aun nadie había resuelto, él pensó que era tarea para casa y al cabo de unas semanas dio con la solución de ambos demostrando una gran capacidad de síntesis y un don para la resolución matemática.

Dantzig se alisto a las Fuerzas Aéreas en la segunda guerra mundial como jefe de la rama de análisis de combate de los cuarteles centrales estadísticos. Este trabajo el permitió gestionar cientos de miles de personas e ítems propiciándole un trabajo con problemas del mundo real, los cuales pudiera resolver mediante la programación lineal. Termino la guerra y se doctoro en Berkeley, al finalizar sus estudios le persuadieron para que volviera a las fuerzas aéreas en la USAF donde por primera vez en 1947 propuso el método del simplex para resolver un problema de programación lineal por primera vez. En 1952 implemento la programación lineal en los ordenadores de la empresa corporativa Rand. A partir de aquí su vida se dedica a la docencia en la universidad de Stanford hasta que se jubiló en los años 90. Además de lo mencionado también realizo avances en análisis de sensibilidad, programación no lineal, optimización a gran escala, programación bajo incertidumbre y un largo etcétera.

El método Simplex es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución.

Jhon Von Neuman (1903-1957, Budapest – Estados unidos)

Es considerado como uno de los matemáticos más importantes de la historia moderna. Era superdotado y recibió clases de matemáticas impartidas por profesores universitarios desde los 10 años. Se doctoro en matemáticas en Budapest en 1926, donde trabajo hasta pero en 1933 la llegada de los nazis al poder hizo que los profesores judíos fuesen siendo expulsados de sus puestos. Von Neuman ya se había establecido en América y se le eligió como uno de los primeros profesores del Instituto de Estudios Avanzados de junto con Albert Einstein, Oswald Veblen, Hermann Weyl y James W. Alexander.

Cuando estallo la segunda guerra mundial el gobierno norteamericano puso en marcha el famoso Proyecto Manhattan al que von Neumann se unió en 1943. Su aportación más importante radicó en el diseño del método de implosión que fue utilizado en Alamogordo, la primera detonación de una bomba atómica de la historia, y que luego volvería a usarse en la de Nagasaki.

En 1947 formulo la importantísima teoría de la dualidad la cual dice que: “Cada problema de programación lineal ( Primal ) está estrechamente relacionado con otro problema simétrico a él, denominado problema dual”.

El dualismo es una teoría que surge como consecuencia de una profundización en el estudio de la programación lineal porque la distribución de los recursos y la formación de los precios son dos aspectos del mismo problema. Entonces la doble formulación de la programación lineal no se debe considerar como un simple ejercicio matemático, sino que una y otra versión del problema viene a explicar dos aspectos económicos distintos para una misma situación problemática. Una propiedad fundamental de la relación entre el primal y el dual es que la solución óptima de cualquiera de estos problemas proporciona la solución óptima para el otro.

INTRODUCCION

En la actualidad la Programación Lineal es una herramienta de uso normal que ha ahorrado miles o millones de pesos a muchas compañías o negocios, incluyendo empresas medianas en los distintos países industrializados del mundo; su aplicación a otros sectores de la sociedad se está ampliando con rapidez. Una proporción muy grande de los cálculos científicos en computadoras está dedicada al uso de la programación lineal.

El tipo más común de aplicación abarca el problema general de asignar recursos limitados entre actividades competitivas de la mejor manera posible es decir, en forma óptima.

La variedad de situaciones a las que se puede aplicar esta descripción es sin duda muy grande, y va desde la asignación de instalaciones de producción a los productos, hasta la asignación de los recursos nacionales a las necesidades de un país; desde la selección de una cartera de inversiones, hasta la selección de los patrones de envío; desde la planeación agrícola, hasta el diseño de una terapia de radiación, etc. No obstante, el ingrediente común de todas estas situaciones es la necesidad de asignar recursos a las actividades eligiendo los niveles de las mismas.

El objetivo principal de este trabajo es la comprensión de todos los procedimientos de la programación Lineal enfocada a ejemplos reales.

PROGRAMACION LINEAL

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, que denominaremos 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.

ESTRUCTURA BÁSICA DE UN PROBLEMA DE PROGRAMACIÓN LINEAL (PL)

Un problema de PL consta de una

...