infinitas soluciones 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.

Una de las posibilidades a las que nos podemos enfrentar cuando resolvemos un modelo de Programación Lineal a través del Método Simplex es el caso de múltiples o infinitas soluciones óptimas.

Esto significa que existe un tramo de soluciones factibles que reportan idéntico valor para la función objetivo y que no es posible mejorar.

En este contexto si luego de aplicar las iteraciones que resulten necesarias por el Método Simplex a un modelo de Programación Lineal (tabla óptima o tableau óptimo) se verifica que una variable no básica óptima tiene costo reducido igual a cero, esto permitirá afirmar que estamos ante el caso de infinitas soluciones.

Ejemplo Infinitas Soluciones Óptimas Método Simplex

Consideremos el siguiente modelo de Programación Lineal:

Llevamos el modelo a su forma estándar para proceder con la aplicación del Método Simplex, con S1 y S2 como variables de holgura de la restricción 1 y 2, respectivamente.

La tabla inicial con S1 y S2 como variables básicas iniciales es:

Y entra a la base. Luego para determinar la variable que deja la base utilizamos el criterio del mínimo cuociente: Min {12/4 ; 16/3} = 3 ==> S1 deja la base. Con esta información actualizamos la tabla realizando operaciones fila:

Luego de una iteración encontramos la solución óptima, donde Y y S2 son variables básicas. La solución básica factible óptima es X=0 Y=3 S1=0 S2=7. El valor óptimo es V(P)=6.

Notar que X (variable no básica) tiene costo reducido igual a cero lo que determina la existencia de múltiples o infinitas soluciones óptimas, de modo que la solución actual es uno de los vértices óptimos.

El siguiente diagrama muestra la Resolución Gráfica del problema con el software Geogebra donde la solución óptima que hemos encontrado en la aplicación del Método Simplex corresponde al vértice B.

Notar que la línea punteada de color azul corresponde a una curva de nivel de la función objetivo que tiene la misma pendiente que la restricción 1 (pendiente -1/2).

¿Cómo podemos obtener el vértice C que es solución óptima a través del Método Simplex? Una alternativa sería forzando la entrada a la base de la variable X en la tabla óptima. Luego calculamos cuál de las actuales variables básicas deja la base según el criterio del mínimo cuociente: Min {3/1/2 ; 7/5/2} = 14/5 ==> S2 deja la base. Actualizando la tabla obtenemos:

La nueva solución óptima (con idéntico valor óptimo) es X=14/5 Y=8/5 S1=0 S2=0, que corresponde al vértice C en el gráfico anterior. Ahora la variable no básica S2 tiene costo reducido igual a cero en la tabla óptima que señala el caso de múltiples soluciones óptimas (en este ejemplo el tramo BC).

Etiqueta: infinitas soluciones

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

Cómo detectar Infinitas Soluciones con el Método Simplex

Ejemplo Infinitas Soluciones Óptimas Método Simplex