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:
La resolución del problema anterior se aborda a través del Método Simplex de 2 Fases, incorporando
Luego de algunas iteraciones del Método Simplex se alcanza la siguiente tabla:
A continuación podríamos seleccionar como variable que ingresa a la base tanto a
Luego, y según lo descrito anteriormente, podemos privilegiar la entrada a la base de la variable
Eliminamos las columnas de las variables auxiliares
Luego llevamos a cero los costos reducidos de las variables
Ahora entra la variable
Que corresponde a la tabla final de la Fase II donde
Ejemplo Criterio Costo Reducido Negativo en el Método Simplex
Consideremos el siguiente problema de Programación Lineal:
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
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
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.