El Método Simplex es un algoritmo que nos permite resolver modelos de Programación Lineal que en ciertas ocasiones permite identificar casos excepcionales como infinitas soluciones óptimas o que el problema es no acotado. En este contexto el Método Simplex rescata las condiciones establecidas en el Teorema Fundamental de la Programación Lineal.
En la aplicación del Método Simplex, un problema no acotado se detecta cuando en una iteración cualquiera existe una variable no básica con costo reducido negativo y todos los elementos en la columna de dicha variable son negativos o cero. Es decir, no se puede seleccionar un pivote para determinar la variable que debe dejar la base.
Consideremos el siguiente modelo de Programación Lineal:
Si resolvemos gráficamente dicho modelo nos podemos percatar que éste es no acotado. Notar que el dominio de soluciones factibles (área sombreada o achurada) es no acotado dado que crece indefinidamente en la dirección de la variable X2.
Las curvas de nivel de la función objetivo crecen a su mayor tasa en la dirección del vector gradiente
¿Cómo podemos detectar esta situación (Problema No Acotado? utilizando el Método Simplex?
Para ello llevamos el modelo a su forma estándar, agregando X3 y X4 como variables de holgura de la restricción 1 y 2, respectivamente. Lo anterior define la siguiente tabla inicial del método:
Notar que X2 es la variable no básica con el costo reducido más negativo y siguiendo ese criterio debería ser aquella que ingresamos a la base. Sin embargo, no es factible hacer el criterio de factibilidad o mínimo cuociente debido a que los elementos en la columna de X2 son negativos o cero. En esta instancia ya se puede afirmar que el problema es no acotado.
Observación: Se puede verificar que si seleccionamos X1 como la variable que entra a la base y se aplica una iteración del Método Simplex se llegara a una conclusión similar a la presentada anteriormente.