Casos especiales en la aplicación del método simplex

Esta sección considera cuatro casos especiales que se presentan en la aplicación del método simplex.

1. Degeneración

2. Optima alternativa

3. Soluciones no acotadas

4. Soluciones inexistentes (o no factibles)

Nuestro interés en el estudio de estos casos especiales es doble:

1. presentar una explicación teórica de la razón de estas situaciones y
2. proporcionar una interpretación practica de lo que podrían significar estos resultados especiales en un problema de la vida real.

Degeneración

En la aplicación de las condiciones factibles del método simplex, un empate de la razón mínima debe romperse arbitrariamente con el propósito de determinar la variable de salida.

Cuando esto sucede, una o más de las variables básicas serán cero en lo siguiente. En este caso, la nueva solución es degenerada.

No hay nada alarmante en el hecho de abordar una solución degenerada, con excepción de un pequeño inconveniente teórico que en breve expondremos. Desde el punto de vista práctico, la condición revela que el modelo tiene por lo menos una restricción redundante. Para poder proporcionar más perspectivas de los impactos teóricos y prácticos de la degeneración, consideramos un ejemplo numérico. La ilustración gráfica debe mejorar la comprensión de las ideas que son la base de esta situación especial.

Óptimos alternativos

Cuando la función objetivo es paralela a una restricción no acotada (es decir, una restricción que se satisface como una ecuación por medio de la solución optima), la función objetivo asumirá el mismo valor optimo en mas de un punto de la solución. Por esta razón se conocen como óptimos alternativos.

Solución no acotada

En algunos modelos de PL, los valores de las variables se pueden incrementar indefinidamente sin violar ninguna de las restricciones, lo que significa que el espacio de la solución es no acotado por lo menos en una dirección. Como resultado, el valor objetivo aumentara (un caso de maximización) o disminuirá (un caso de minimización) indefinidamente. En este caso, tanto el espacio de la solución como el valor objetivo optimo son no, acotados.

La no acotación en un modelo solo indica una cosa: el modelo esta mal construido. Las irregularidades mas probables en estos modelos son que no se han tornado en cuenta una o mas restricciones no redundantes y que los parámetros (constantes) de algunas restricciones no se calcularon correctamente.

Solución no factible

Si las restricciones no se satisfacen simultáneamente, el modelo no tiene una solución factible. Esta situación nunca puede ocurrir (suponiendo constantes no negativas en el lado derecho), debido a que las holguras proporcionan una solución factible.

Para otros tipos de restricciones, utilizamos variables artificiales. Aun cuando las artificiales se penalizan para forzarlas a cero en la optima, esto solo puede ocurrir si el modelo tiene un espacio factible. De lo contrario, por lo menos una variable artificial será positiva en la iteración optima.

Desde el punto de vista practico, un espacio no factible indica la posibilidad de que el modelo no este formulado correctamente.

Fuente: Apuntes de Investigación de operaciones de la UNIDEG