¿Qué es la solución degenerada?

La Degeneración en la Programación Lineal: Un Punto Crítico en el Espacio Factible

La programación lineal, una herramienta fundamental en la optimización de recursos, se basa en la búsqueda del mejor resultado (máximo o mínimo) de una función lineal, sujeta a un conjunto de restricciones, también lineales. Este proceso nos lleva a explorar un espacio factible, un polígono definido por las intersecciones de las restricciones. Dentro de este espacio, la solución óptima se encuentra, invariablemente, en uno de sus vértices. Sin embargo, existe un fenómeno particular que puede complicar el proceso de búsqueda: la degeneración.

¿Qué es una solución degenerada? En la programación lineal, una solución degenerada se presenta cuando tres o más rectas que delimitan la región factible convergen en un único vértice. En otras palabras, más restricciones de las estrictamente necesarias se satisfacen simultáneamente en ese punto. Mientras que en un vértice no degenerado se intersectan únicamente dos rectas (en dos dimensiones) o n hiperplanos (en n dimensiones), en un vértice degenerado concurren más de las mínimas necesarias.

Este fenómeno, aunque aparentemente simple, puede generar complicaciones en algunos algoritmos de resolución, como el método simplex. La degeneración puede provocar ciclos, donde el algoritmo se queda “atrapado” revisando repetidamente el mismo vértice degenerado sin avanzar hacia la solución óptima. Esto se debe a que el valor de la función objetivo no mejora al moverse entre vértices degenerados adyacentes, creando una falsa sensación de estancamiento.

Imagine un triángulo como región factible. Un vértice degenerado sería como si añadiéramos una cuarta recta que, casualmente, pasara exactamente por uno de los vértices originales del triángulo. Esta recta, aunque define una restricción adicional, no modifica la forma del espacio factible, pero sí introduce una complejidad innecesaria al análisis.

Es importante destacar que la existencia de una solución degenerada no implica necesariamente que el problema sea irresoluble. Existen técnicas específicas para manejar la degeneración en el método simplex, como la regla de Bland o la perturbación lexicográfica, que permiten “desbloquear” el algoritmo y continuar la búsqueda de la solución óptima.

En resumen, la degeneración en programación lineal representa un punto crítico en el espacio factible, donde la convergencia de múltiples restricciones puede complicar la búsqueda de la solución óptima. Si bien no invalida el problema, requiere una consideración especial en los algoritmos de resolución para evitar ciclos y asegurar la convergencia hacia el resultado deseado. La comprensión de este concepto es fundamental para una aplicación eficiente y robusta de las técnicas de programación lineal.