degenerado Archivos - Gestión de Operaciones

En la resolución de un modelo de Programación Lineal se pueden enfrentar ciertos casos especiales que merecen particular atención. Estos casos (infinitas soluciones óptimas, problema no acotado sin solución óptima, problema infactible, solución óptima degenerada) se pueden detectar a través de la aplicación del Método Simplex según hemos tratado previamente en el Blog. A continuación un resumen de dichos escenarios:

Infinitas Soluciones Óptimas: Se detecta cuando luego de alcanzar una solución básica factible óptima, al menos una variable no básica tiene costo reducido igual a cero. La siguiente imagen representa esta situación donde la solución óptima (infinitas) se alcanza en el tramo entre los vértices B y C. En efecto se puede representar de forma general las soluciones óptimas como: $(x,y)=\lambda (0,3)+(1-\lambda )(2,2)$ con $0\leq \lambda\leq 1$ .

Problema No Acotado: En las iteraciones del Método Simplex un problema no acotado se detecta cuando al calcular el criterio de factibilidad o mínimo cuociente que determina la variable que deja la base, todas las entradas en la columna de la variable no básica entrante son negativas o cero, por tanto no existe denominador válido (mayor a cero) que permita determinar el pivote. En la siguiente representación gráfica se puede apreciar que las curvas de nivel de la función objetivo crecen en la dirección del vector gradiente, donde en particular el dominio de soluciones factibles es no acotado para los valores que puede adoptar la variable $x_{2}$ .

Es importante destacar que el hecho que un dominio de soluciones factibles sea no acotado no implica necesariamente que el problema de Programación Lineal no tiene solución.

Problema Infactible: Si al finalizar la Fase I del Método Simplex de 2 Fases el valor de la función objetivo es distinto a cero, entonces el problema lineal es infactible, es decir, el dominio de soluciones factibles es vacío al existir restricciones incompatibles (por ejemplo en el gráfico a continuación el área azul no se intersecta con el área color rojo).

Solución Óptima Degenerada: Cuando se presenta un empate el el cálculo de la condición de factibilidad del Método Simplex, al menos una variable básica será cero en la siguiente iteración, caso en el cual se dice que la nueva solución es degenerada. Esto implica que el modelo tiene al menos una restricción redundante.

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:

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

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

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:

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:

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:

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$ ).

Etiqueta: degenerado

Casos Especiales en la Programación Lineal detectados con el Método Simplex

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

Solución Óptima Degenerada