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

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.

Grafico Infinitas Soluciones Optimas

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}.

problema no acotado

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

dominio-infactible-problema

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.

solucion-optima-degenerada-

Rating: 3.4. From 9 votes.
Please wait...

, , , , , , , ,

Sin Comentarios aun. Se el primero en comentar!

Deja un comentario