¿Qué es una solución degenerada?

Una vez estuve explorando la simulación por computadora de fiestas, dada la distancia social preferida de cada persona de una a otra (y una mesa de comida y bebida, que diferentes personas experimentaron diferentes patrones de necesidad de visitar): ¿cuánto tiempo le toma a esta persona consumir un beber y cuál es la fuerza de sus ganas de conseguir otro?

Naturalmente comencé a probar con lo que llamé la “fiesta degenerada”. Aunque parezca que podría ser emocionante y un poco arriesgado participar, en mi sentido, la fiesta degenerada consistía en una persona y la mesa de comida y bebida.

Eso es lo que significa “degenerar” en un sentido matemático / computacional.

Página 1

Un LPAn LP degenerado es degenerado si en una solución factible básica, una de las variables básicas adquiere un valor cero. La degeneración es un problema en la práctica, porque hace que el algoritmo simplex sea más lento. 8 (2) −x2 + x3≤ 0 (3) x1, x2, ≥ 0. (4) Forma estándar.z = x1 + x2 + x3 (5) s1 = 8− x1− x2 (6) s2 = – x2 + x3 (7 ) Tenga en cuenta que una de las variables básicas es 0. Elegimos x1 como la variable entrante y s1 como la variable saliente.z = 8+ x3− s1 (8) x1 = 8− x2− s1 (9) s2 = x2− x3 ( 10) Observe nuevamente que una de las variables básicas es 0. Sin embargo, el pivote anterior aumentó el valor de la función objetivo de 0 a 8. Ahora elegimos x3 como la variable entrante y s2 como la variable saliente. Estas fueron nuestras únicas opciones. Z = 8+ x2− s1− s2 (11) x1 = 8− x2− s1 (12) x3 = x2− s2 (13) Tenga en cuenta que la función objetivo no aumentó. Esto ocurre debido a la degeneración. Ahora elegimos x2 como la variable entrante y x1 como la variable saliente.z = 16− x1− 2s1− s2 (14) x2 = 8− x1 − s1 (15) x3 = 8− x1 − s1 – s2 (16) 1

Página 2

Como todos los coeficientes de las variables en la función objetivo son negativos, ahora tenemos la solución óptima, (x1, x2, x3, s1, s2) = (0, 8, 8, 0, 0) con valor objetivo 16. Observe que en el solución final, las variables básicas son todas distintas de cero. En un LP degenerado, también es posible que incluso en la solución final, algunas de las variables básicas sean cero. Otra cosa a tener en cuenta es que x1 era una variable entrante en una iteración, y una variable saliente en otra. En general, una variable puede ser una entrada y salir de la base muchas veces en el curso del algoritmo simple.