Criterios para la Rapidez de Convergencia del Método Simplex

En un artículo previo respecto a Cómo resolver un modelo de Programación Lineal con el Método Simplex de 2 Fases, se consideró en una iteración intermedia (es decir, en un tableau que representa una solución básica factible no óptima) la entrada a la base de una variable no básica que no era aquella con el costo reducido más negativo. Dicha situación por cierto no tuvo incidencia respecto a alcanzar los resultados del modelo en cuanto a su solución óptima y valor óptimo, no obstante, dicha situación afecto la rapidez de convergencia del Método Simplex.

Entendemos por rapidez de convergencia en este caso, el número de iteraciones necesarias en la aplicación del Método Simplex para, comenzando en una solución básica factible inicial llegar a una solución básica factible óptima.

Se debe destacar que si bien es frecuente que en la bibliografía básica asociada a cursos de Investigación de Operaciones se considere como criterio privilegiar la entrada a la base de aquella variable no básica con el costo reducido más negativo esto NO garantiza un menor número de iteraciones en el Método Simplex.

Ejemplo Criterio Costo Reducido Más Negativo en el Método Simplex

Como forma de corroborar lo anterior retomaremos el modelo de Programación Lineal que fue presentado en el artículo mencionado anteriormente:

ejemplo-simplex-dual

La resolución del problema anterior se aborda a través del Método Simplex de 2 Fases, incorporando X_{4} y X_{5} como variables de excesoX_{6} y X_{7} como variables auxiliares, de las restricciones 1 y 2, respectivamente. Esto da origen al siguiente problema de la Fase 1.

fase-1

Luego de algunas iteraciones del Método Simplex se alcanza la siguiente tabla:

tabla-3-fase-1

A continuación podríamos seleccionar como variable que ingresa a la base tanto a X_{1}, X_{2}  o X_{4}, al tener cada una de estas variables no básicas un costo reducido negativo.

Luego, y según lo descrito anteriormente, podemos privilegiar la entrada a la base de la variable X_{2} que tiene el costo reducido más negativo. En consecuencia el mínimo cuociente se calcula en la columna de la variable X_{2}, siendo éste: Min\begin{Bmatrix}\frac{1/4}{1/4};\frac{1}{3/2}\end{Bmatrix}=2/3, por tanto X_{1} deja la base. Se actualiza la tabla con esta nueva información obteniendo lo siguiente que representa el fin de la Fase I:

rapidez-de-convergencia-fas

Eliminamos las columnas de las variables auxiliares X_{6} y X_{7} y adicionalmente actualizamos el vector de costos reducidos considerando la función objetivo original.

inicio-fase-2-convergencia

Luego llevamos a cero los costos reducidos de las variables X_{3} y X_{2}:

fase-2-rapidez-convergencia

Ahora entra la variable X_{1} a la base. El criterio de factibilidad o mínimo cuociente determina que Min\begin{Bmatrix}\frac{1/12}{1/3};\frac{2/3}{2/3}\end{Bmatrix}=1/4 la variable X_{3} deja la base. Se actualiza la tabla:

tabla-final-fase-2-rapidez-

Que corresponde a la tabla final de la Fase II donde X_{1}=1/4X_{2}=1/2X_{3}=0 y que por cierto demuestra la equivalencia en los resultados obtenidos cuando en la tabla  intermedia de la Fase I se ingresa a la base a la variable X_{1}. Cabe destacar que una forma alternativa de resolver el problema anterior que evita la aplicación de las 2 Fases del Método Simplex es a través del Método Simplex Dual.

Ejemplo Criterio Costo Reducido Negativo en el Método Simplex

Consideremos el siguiente problema de Programación Lineal:

ejemplo costo reducido negativo método simplex

El lector puede corroborar que luego de llevar a la forma estándar el problema anterior, pasando a minimización la función objetivo y agregando como variables de holgura las variables x_{3}x_{4} se dispone de una solución básica factible inicial en el origen (vértice A de la siguiente gráfica).

gráfico costo reducido negativo

Si se privilegia la entrada a la base de aquella variable no básica con el costo reducido más negativo se debería seleccionar inicialmente la variable x_{2} la cual permite concluir con las iteraciones del Método Simplex y alcanzar la solución óptima al cabo de 3 iteraciones (vértice D). Por el contrario si inicialmente se ingresa a la base la variable x_{1} se alcanza la solución óptima al cabo de 1 iteración. Se recomienda al lector verificar estos resultados.

Este sencillo ejemplo demuestra que NO necesariamente garantiza una mayor rapidez de convergencia del Método Simplex el considerar como criterio de entrada a la base aquella variable no básica con el costo reducido más negativo.

Rating: 4.7/5. From 3 votes.
Please wait...

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *