Qué es una Solución Óptima Degenerada en Programación Lineal

En la aplicación del Método Simplex al hacer el cálculo del mínimo cuociente o condición de factibilidad, se puede romper un empate en la razón o cuociente mínimo en forma arbitraria. En este caso, al menos una variable básica será cero en la siguiente iteración, afirmándose en este caso que la nueva solución es degenerada. La implicancia práctica de dicha condición indica que el modelo tiene al menos una restricción redundante.

Solución Óptima Degenerada

Consideremos el siguiente modelo de Programación Lineal el cual resolveremos a través del Método Simplex y que de forma complementaria representaremos gráficamente con Geogebra:

problema-solucion-degenerad

Llevamos el problema anterior a su forma estándar de minimización, agregando x_{3}x_{4}, como variables de holgura de las restricciones 1 y 2, respectivamente.

forma-estandar-solucion-deg

Que da origen a la siguiente tabla inicial del Método Simplex:

tabla-inicial-degenerada

Para favorecer la rapidez de convergencia del algoritmo seleccionamos x_{2} como la variable que ingresa a la base. A continuación calculamos el criterio de factibilidad (mínimo cuociente): Min \begin{Bmatrix}{\frac{8}{4}, \frac{4}{2}}\end{Bmatrix}=2 (al existir empate seleccionaremos arbitrariamente la variable x_{3} como aquella que deja la base. Luego se actualiza la tabla:

primera-iteracion-degenerad

Ahora x_{1} ingresa a la base. El criterio de factibilidad determina que: Min \begin{Bmatrix}{\frac{2}{1/4}, \frac{0}{1/2}}\end{Bmatrix}=0 x_{4} deja la base. Se realiza entonces una nueva iteración:

optimo-degenerado-simplex

Se alcanza la solución óptima degenerada del problema lineal. Notar que x_{1}=0, x_{2}=2, x_{3}=0, x_{4}=0, V(P)=18. Como éste es un problema bidimensional, la solución está sobredeterminada y una de las restricciones es redundante tal como se corrobora en la representación gráfica:

solucion-optima-degenerada-

En la práctica conocer que algunos recursos (como los asociados a una restricción) son superfluos puede ser valioso durante la implementación de la solución. Desde el punto de vista teórico, la degeneración tiene dos implicaciones: se genera el fenómeno de ciclos o círculos (es posible que el Método Simplex repita una serie de iteraciones sin mejorar el valor de la función objetivo, tal como se observo en el ejemplo anterior e incluso eventualmente nunca terminar los cálculos); el segundo aspecto teórico surge al examinar las iteraciones 1 y 2. Las dos, aunque difieren en la clasificación de las variables básicas y no básicas, producen valores idénticos para todas las variables y el valor objetivo ( x_{1}=0, x_{2}=2, x_{3}=0, x_{4}=0, V(P)=18).

Rating: 4.8/5. From 5 votes.
Please wait...

, , , , , ,

Sin Comentarios aun. Se el primero en comentar!

Deja un comentario