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 función objetivo (lineal) por maximizar o minimizar, sujeta a ciertas restricciones en la forma de igualdades o desigualdades.

Conceptos clave:

• Función objetivo: La función por optimizar (maximizar o minimizar)

• Restricciones: Representan condiciones que es preciso satisfacer. Sistema de

igualdades y desigualdades (≤ Ó≥ )

SOLUCIÓN GRÁFICA DE PROBLEMAS DE PL.

Cuando un modelo de programación lineal se expresa en términos de dos variables puede resolverse con procedimientos gráficos.

Conceptos clave:

Conjunto factible: Es el conjunto de puntos que integran la región de resolución.

Solución factible: Cada punto que integra la región (plana) que resuelve el problema.

Solución óptima: Constituye la solución al problema de programación lineal.

METODO 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.

Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución.

El método del simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta.

PROCEDIMIENTOS PARA LA REALIZACION DEL METODO SIMPLEX:

1. Si todos los elementos en el renglón cero son mayores o iguales a cero detenerse, la solución actual es óptima. Si no, seleccione el elemento más negativo del renglón cero de la tabla simplex.

2. Examine los elementos en la columna pivote (excepto el elemento en el renglón cero), si todos ellos son menores o iguales a cero entonces la solución es no acotada. En caso contrario y sólo con los elementos positivos de la columna pivote, divida de forma correspondiente cada elemento en el LADO DERECHO entre su respectivo elemento en la columna pivote y

seleccione el menor cociente,

3. La columna pivote indica la variable entrante y El renglón pivote indica la variable saliente. A partir de operaciones básicas entre renglones, esto es, multiplicación por un escalar y/o suma de renglones, actualice la tabla hasta obtener el sistema equivalente con el nuevo conjunto de variables básicas. Repita el PASO PRINCIPAL.

METODO SIMPLEX DUAL

Aprovechando las propiedades de los problemas asociados primal y dual, se desarrolló el método dual-simplex que se aplica: en algunos casos de análisis de sensibilidad, como ocurre en cambios de los recursos del problema; también para resolver problemas de objetivo mínimo y al menos una restricción de tipo >=, o para

...