Método Simplex

METODO SIMPLEX

El método simplex es un procedimiento general para resolver problemas de programación lineal, fue creado en 1947 por el matemático George Dantzig. El método simplex es un procedimiento algebraico, sin embargo sus conceptos fundamentales son geométricos.

Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando 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 el anterior.

El método simplex se utiliza para resolver problemas de programación lineal en los que intervienen tres o más variables y es extraordinariamente eficiente. El algebra matricial y el proceso de eliminación de Gauss-Jordán para resolver un sistema de ecuaciones lineales constituye la base del método simplex.

Preparación para el método simplex.

1. Convertir las desigualdades en igualdades: esto se lleva a cabo introduciendo variables de holgura.

2. Igualar la función objetivo a cero

3. Escribir la tabla inicial simplex, en la cual deben aparecer las variables del problema y los coeficientes de las igualdades obtenidas asi como los coeficientes de la función objetivo.

4. Encontrar la variable de decisión que entra en la base y la variable de holgura que sale de la base. Para determinar la variable de decisión es en base a la función objetivo y se selecciona el coeficiente negativo mayor. Si no hay coeficiente negativo significa que se ha alcanzado la solución óptima.

La columna en la que se encuentra la variable negativa se le llama columna pivote. Para indicar el renglón pivote se tienen que dividir los valores solución entre la columna pivote, ya que se tengan los resultados seleccionamos el de menor valor. En donde se unan la columna y el renglón pivote será el elemento pivote.

5. Encontrar los coeficientes del la nueva tabla dividiendo la fila pivote entre el elemento pivote, para convertirlo en uno.

6. Finalmente se lleva a cabo la reducción Gaussiana la cual consiste en convertir en ceros los restantes términos de la columna y así se obtienen los nuevos coeficientes de los otros renglones incluyendo el de la función objetivo.

...