Metodo Simplex

Historia:

El Método Simplex fue creado por el Dr. George Bernard Dantzig en 1947 y es un método para la resolución de problemas en los cuales se busca el máximo de una función lineal sobre un conjunto de variables que satisfaga un conjunto de restricciones.

Reseña Del Dr. George Bernard Dantzig

Fue un matemático reconocido por desarrollar el método simplex y es considerado como el "padre de la programación lineal". Nació el 8 de Noviembre de 1914 en Portland, Oregon, EEUU. Su padre era profesor de Matemáticas, se retiró dejando su puesto de Jefe del Departamento de Matemáticas en la Universidad de Maryland poco después de la Segunda Guerra Mundial. Su madre era una lingüista especializada en idiomas eslavos.

Dantzig se graduó de matemáticas en 1936 en la Universidad de Maryland donde enseñaba su padre. Obtuvo el Master en Ciencias en 1937 en la Universidad de Michigan. Éste no disfrutaba con las matemáticas puras, pues señalaba frecuentemente que sólo disfrutó de los cursos relacionados con estadísticas. Dantzig fue a Washington a trabajar como Junior Statiscian en el Bureau of Labor Statistics, labor que llevó a cabo desde 1937 hasta 1939. Comenzó a interesarse en los estudios de matemáticas al leer trabajos de uno de los fundadores de la teoría estadística, el polaco radicado en los Estados Unidos, Jerzy Neyman. En 1939 comenzó a trabajar como su asistente en los cursos que dictaba en Berkeley, mientras trabajaba en su doctorado.

Durante la II Guerra Mundial Dantzig dejó los estudios y pasó a trabajar de 1941 a 1946 en la llamada Combat Analysis Branch, de la Fuerza Área de los Estados Unidos, donde obtuvo reconocimientos por su labor. Su trabajo era coleccionar y analizar datos sobre misiones aéreas, efectividad de los bombardeos y pérdidas de aviones. Esta actividad era caracterizada por el desarrollo de planes minuciosos llamados “programas”.

Al final de la guerra George pasó a la Universidad de California en Berkeley, pero el Pentágono le hizo una oferta mejor pagada, así que se dedicó a la labor de mecanizar el proceso de planeamiento siendo Asesor Matemático en el Departamento de Defensa.

Es en 1947 que Dantzig hace su más famosa contribución: el Método Simplex de Optimización. Éste fue el resultado de una labor que buscaba simplificar los usuales métodos de planeamiento que utilizaban calculadoras de mesa. Le llamó “programación” por el término usado en el argot militar. Dantzig realizó la mecanización bajo el supuesto de que el programa poseía una estructura relativamente simple, desde el punto de vista matemático, llamado Modelo Lineal. Con su uso se lograba hacer los cómputos con mayor rapidez y exactitud.

El método desarrollado por Dantzig es catalogado como uno de los más importantes en toda la historia de las matemáticas aplicadas, pues por el uso del Simplex es posible tomar decisiones óptimas en muchas clases de problemas prácticos de gran complejidad.

Otro de sus grandes logros es la teoría de la dualidad, ideado conjuntamente con Fulkerson y Johnson en 1954 para resolver el paradigmático problema del Agente Viajero (resolviendo entonces problemas con 49 ciudades cuando, hoy día, mediante modernas implementaciones del método, se resuelven problemas con varios miles de ciudades y hasta un millón de nodos) es el precursor de los hoy utilísimos métodos de Branch-and Cut (Bifurcación y corte) tan utilizados en programación entera para resolver problemas de grandes dimensiones.

El 13 de Mayo de 2004, George Bernard Dantzig, murió a la edad de 90 años en su casa de Stanford debido a complicaciones con la diabetes y problemas cardiovasculares.

Fundamentos básicos:

 Simplex.

En geometría, un simplex o n-simplex es el análogo en n dimensiones de un triángulo. Es la envoltura convexa de un conjunto de (n + 1) puntos independientes afines en un espacio euclídeo de dimensión n o mayor, es decir, el conjunto de puntos tal que ningún m-plano contiene más que (m + 1) de ellos. Se dice de estos puntos que están en posición general. Un 0-símplex es un punto; un 1-símplex un segmento de una línea; un 2-símplex un triángulo; un 3-símplex es un tetraedro; y un 4-símplex es un pentácoron (en cada caso, con su interior).

El método simplex es un método que sirve para resolver problemas de programación lineal. Este método fue inventado por George Dantzig en el 1947. La primera formulación del método simplex fue en el verano de 1947. El primer problema práctico que se resolvió con este método fue uno de nutrición.

 Método Simplex

Es una técnica popular para dar soluciones numéricas del problema de la programación lineal. Es un método numérico para optimización de problemas libres multidimensionales perteneciente a la clase más general de algoritmos de búsqueda. Según Rodríguez (2009) este Método “…comienza con alguna solución factible, y sucesivamente obtiene soluciones en las intersecciones que ofrecen mejores funciones de la función objetivo. Finalmente, este método proporciona un indicador que determina el punto en el cual se logra la solución óptima...” (p. 1)

Permite encontrar una solución óptima en un problema de maximización o minimización, buscando en los vértices del polígono. 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.

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.

El método simplex es muy eficiente en la práctica, en general, teniendo 2m a 3m iteraciones en la mayor parte (donde m es el número de restricciones de igualdad), y que convergen en la hora prevista para el polinomio de ciertas distribuciones de insumos al azar. La aplicación del método del Simplex, se utiliza cuando el problema es de un tamaño suficientemente grande.

Está diseñado para problemas de programación lineal cuya matriz tiene la propiedad de diseminación (el número de no-cero es pequeño). Hay implementaciones del método simple para la solución de problemas de programación lineal con las matrices de restricción escasa.

Se han desarrollado diversas variantes del método simplex que tienen en cuenta las particularidades de las diversas clases especiales de problemas de programación lineal (problemas de bloque, los problemas de transporte y otros).

Capítulo I: Planteamiento del problema

El Problema De Maximización Simplex

 Formulación Inicial :

Utilizando el siguiente ejemplo estableceremos la formulación inicial símplex y demostraremos la mecánica del método y su interpretación.

El gerente de la Relojería la Torre desea conocer la ganancia máxima que se puede obtener de la producción y venta de dos clases de relojes económicos digitales de pulsera. La ganancia que se obtiene por la producción y venta de un reloj de hombre es de $4 y de $6 para un reloj de mujer. La empresa cuenta con 120 horas semanales para la producción de los relojes y 100 horas para la inspección y empaque de estos. La fabricación de un reloj de hombre requiere 2 horas de producción y 2 horas de inspección y empaque. Mientras que un reloj de mujer requiere 4 horas de producción y 3 horas de inspección y empaque.

La formulación del problema para esta situación es la siguiente:

Maximizar Z = $4X1 + $6X2

Sujeto a: 2X1 + 4X2 ≤ 120 (horas de producción)

2X1 + 3X2 ≤ 100 (horas de inspección y empaque)

(X1, X2 ≥ 0)

Donde X1 = cantidad de relojes de hombre que se producen semanalmente.

X2 = cantidad de relojes de mujer que se producen semanalmente.

Luego de formular el problema procedemos a trabajar primero con las restricciones y luego con la función objetivo. Comenzamos cambiando los signos de las restricciones de desigualdades a igualdades. El método símplex requiere la conversión de las restricciones con signos de desiguales a igualdades estrictas. Esto se debe a que el método usa álgebra de matrices en donde todas las relaciones matemáticas serán a base de ecuaciones lineales y que a su vez deben contener todas las variables. Llamaremos a este procedimiento como aumento de las restricciones y de la función objetivo.

 Aumento De Las Restricciones y de la Función Objetivo

El aumento de las restricciones y de la función objetivo surge porque el método símplex comienza por definición en el origen es decir en el punto (0,0) y de este punto al valor de las restricciones existe una diferencia.

...