Algoritmo simplex

1. E.E.S.T.Nº2 6º 3ª Investigación Operativa Bustamante Diego, Miño Ezequiel y Raichs Mara ALGORITMOS SIMPLEX

2. Definición En la optimización, el termino  algoritmo simplex  habitualmente se refiere a un conjunto de métodos muy usados para resolver problemas de  programación lineal , en los cuales se busca el máximo de una  función lineal  sobre un conjunto de variables que satisfaga un conjunto de  inecuaciones lineales .

3. Historia 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 lineal se plantea como un modelo matemático desarrollado durante la Segunda Guerra Mundial para planificar los gastos y los retornos, a fin de reducir los costos al ejército y aumentar las pérdidas del enemigo. Se mantuvo en secreto hasta 1947. En la posguerra, muchas industrias lo usaron en su planificación diaria. Los fundadores de la técnica son George Dantzig , quien publicó el algoritmo simplex en 1947, John von Neumann , que desarrolló la teoría de la dualidad en el mismo año, y Leonid Kantoróvich , un matemático ruso que utiliza técnicas similares en la economía antes de Dantzig y ganó el premio Nobel en economía en 1975. En 1979 otro matemático ruso, Leonid Khachiyan , demostró que el problema de la programación lineal era resoluble en tiempo polinomial . Más tarde, en 1984, Narendra Karmarkar introduce un nuevo método del punto interior para resolver problemas de programación lineal, lo que constituiría un enorme avancen los principios teóricos y prácticos en el área. (STAMATO-LOPEZ 6to 3ra EET N°2)

4. Características 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. Es aplicable a problemas de PL multidimensionales. Tiene como base el algebra matricial y el proceso de eliminación de Gauss- Jordan . Es un proceso de búsqueda que se vuelve sorprendentemente eficiente para solucionar problemas muy grandes.

5. Variante Método Simplex Primal: Parte de una solución básica FACTIBLE(Punto extremo del polígono de soluciones) y se continua iterando a través de soluciones básicas factibles sucesivas hasta alcanzar el optimo valor. Método Simplex Dual: Trata con soluciones básicas INFACTIBLES hasta la ultima iteración, donde la solución básica asociada debe ser factible.

6. Funcionamiento Pasos lógicos: 1-Convertimos las desigualdades en igualdades, agregando tantas variables de holgura como restricciones tengamos. 2-Igualamos a cero la función objetivo. 3-Trasladamos valores a la tabla. En Variables básicas, los nombres de las variables de holgura y la de la función objetivo. En Z los coeficientes que tiene la variable Z de cada igualdad. En X1 los coeficientes de X1 de cada igualdad. En X2 los coeficientes de X2 de cada igualdad. En X3 los coeficientes de X3 de cada igualdad. En X4 los coeficientes de X4 de cada igualdad. En solución los valores que se encuentran a la derecha del igual de cada igualdad. 4-Iteración , hasta que Z tenga valores positivos. Ubicamos el menor valor de la fila de Z para hallar columna pivote. Dividimos la solución por el valor de la celda de la columna respectiva para hallar la fila pivote. Donde se encuentre el resultado menor es la fila pivote. Con el valor de la celda pivote dividimos toda la fila pivote. Para el resto de las filas se utiliza la siguiente fórmula: Multiplico el valor de la celda pivote por el valor de la nueva fila de la columna respectiva y se la resto a la vieja celda.

7. Ejemplo z = 2x1 + 3x2 x1 + 3x2 <= 6 3x1 + 2x2 <= 6 x1, x2 >= 0 *Conversión* x1 + 3x2 + x3 = 6 3x1 + 2x2 + x3 = 6 z - 2x1 – 3x2 = 0

8. Tabulación

9. Iteración a) Ubicar el menor valor en fila Z

10. b) Divido solución por los valor respectivos de la columna pivote.

11. c) Divido la fila por el valor de la celda pivote.

12. d) Aplico la formula para el resto de las filas: Multiplico el valor de la celda pivote por el valor de la nueva fila de la columna respectiva y se la resto a la vieja celda

13. Al estas los valores de z en positivo, se halla la solución óptima. X1 = 0,85 X2 = 1,72 Z = 6,85

14. Ejercicios

15. En un grafico 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. Podemos ver un claro ejemplo en la siguiente imagen…

16. Ejemplo El ejemplo original de Dantzig de la búsqueda de la mejor asignación de 70 personas a 70 puestos de trabajo es un ejemplo de la utilidad de la programación lineal. La potencia de computación necesaria para examinar todas las permutaciones a fin de seleccionar la mejor asignación es inmensa; el número de posibles configuraciones excede al número de partículas en el universo. Sin embargo, toma sólo un momento encontrar la solución óptima mediante el planteamiento del problema como una programación lineal y la aplicación del algoritmo simplex. La teoría de la programación lineal reduce drásticamente el número de posibles soluciones óptimas que deberán ser revisadas.