Método Simplex

Método simplex

Algoritmo:

Paso 1. Convertir las desigualdades en igualdades al sumarles una variable de holgura hi . Esta variable representa la cantidad que le falta a la desigualdad para ser igualdad. Las variables de holgura siempre son positivas. No se incluye la CNN:

Paso 2. Escribir la función objetivo como una igualdad a cero sumando las variables de holgura con coeficiente cero y conservando positivo el coeficiente de Zmax , es decir:

Paso 3. Formar la tabla símplex o tabla inicial.

Paso 4. Verificamos si todos los coeficientes asociados al renglón de Z son mayores o iguales a cero. Si es así, entonces la solución en la tabla es la óptima y el proceso termina. Si no es así, se continúa.

Paso 5. De los coeficientes del renglón Z se toma el que tenga el mayor valor negativo (número menor) y se selecciona toda la columna. La variable de esta columna es la que entra al sistema (pasa a ser básica).

Paso 6. Se divide el término de la columna “Solución” entre el elemento correspondiente de la columna seleccionada en el punto anterior, y de los resultados de la división se selecciona el menor valor positivo y todo el renglón asociado a este valor. Ésta es la variable que sale de la base (pasa a ser no básica). Nota: Las divisiones entre cero o entre números negativos no se toman en cuenta. Si todas son negativas o indeterminadas el problema no tiene solución y el proceso termina.

Paso 7. La celda que se encuentra en la intersección de la columna con el renglón seleccionado contiene un elemento al que, por medio de operaciones elementales entre renglones, se convierte en elemento pivote y los demás elementos de su columna, en ceros; con esto se obtiene una nueva columna de la matriz identidad.

Paso 8. Se repite el proceso desde el Paso 4 operando sobre matrices hasta obtener todos los coeficientes del renglón Z, con valores mayores o iguales a cero.

Ventajas del Método simplex:

· Es un método heurístico. Se basa en consideraciones geométricas y no requiere el uso de derivadas de la función objetivo.

· Es de gran eficacia incluso para ajustar gran número de parámetros.

· Es fácil de implementar y usar, y sin embargo tiene una alta eficacia.

· Se puede usar con funciones objetivo muy sinuosas pues en las primeras iteraciones busca el mínimo más ampliamente y evita caer en mínimos locales fácilmente.

Desventajas del Método simplex:

· Converge más lentamente que otros métodos pues requiere mayor número de iteraciones.