geogebra Archivos - Página 7 de 7 - Gestión de Operaciones

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

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

Cómo calcular Gráficamente el Precio Sombra de una Restricción

El Precio Sombra de una restricción en Programación Lineal indica cuánto cambia el valor de la función objetivo (óptimo) ante una variación marginal del lado derecho de una restricción. Se asume que el resto de los parámetros del modelo permanecen constantes. De antemano es conveniente señalar que el Precio Sombra puede ser positivo, cero o negativo y en el Blog iremos discutiendo estos distintos escenarios.

Para obtener los Informes de Sensibilidad de un modelo de Programación Lineal se puede hacer uso de herramientas computacionales como Solver de Excel, sin embargo, en esta oportunidad nos enfocaremos en el cálculo del precio sombra de una restricción en forma gráfica, lo que nos ayudará más adelante a entender los conceptos que fundamentan los resultados de Solver.

Cálculo del Precio Sombra de una Restricción con el Método Gráfico

A continuación calcularemos el precio sombra de una restricción del siguiente modelo de Programación Lineal:

La solución óptima de este modelo es X=100 e Y=350 con valor óptimo V(P)=3.100 según su resolución gráfica con Geogebra o su resolución con Solver de Excel. El siguiente diagrama muestra la solución óptima obtenida gráficamente en el vértice C, que corresponde a la intersección de la restricción 1 (R1: color rojo) y la restricción 3 (R3: color gris), siendo ésta una solución básica factible óptima.

Supongamos que deseamos saber cuánto cambiará el valor óptimo (respecto a su valor actual) si aumenta en una unidad el lado derecho de la restricción 1 pero sin resolver nuevamente el problema. El precio sombra nos permite dar respuesta a dicha interrogante y permite anticipar el nuevo valor óptimo ante una variación marginal del lado derecho de una restricción.

Un variación marginal de un lado derecho implica que la nueva solución óptima se seguirá encontrando con las actuales restricciones activas, es decir, aquellas que se cumplen en igualdad en el óptimo (esto es se conserva la base óptima).

En el caso de la restricción 1 si aumentamos su lado derecho, ésta se desplazará en forma paralela hacia arriba. Si buscamos garantizar que la nueva solución óptima aún se encontrará con R1 y R3 activas llegaremos al vértice donde actualmente se interceptan la R2 y R3 que corresponde a la coordenada X=166,67 e Y=350 (ésta será la máxima variación).

En forma análoga si disminuimos el lado derecho de la restricción 1 y buscamos mantener R1 y R3 activas en el nuevo óptimo, el último punto donde se garantiza esto es el vértice B cuyas coordenadas son X=0 e Y=350 (ésta será la menor variación). Con esta información calculamos el precio sombra de la restricción 1:

Este precio sombra es válido si el lado derecho de la restricción 1 (actualmente b1=1.600) varía entre [1.400,1.733,33]. Por ejemplo, si el lado derecho de R1 aumenta de 1.600 a 1.700 el nuevo valor óptimo será V(P)=3.100+100*1,5=3.250. Análogamente si el lado derecho de R1 disminuye de 1.600 a 1.550 el nuevo valor óptimo será V(P)=3.100-50*1,5=3.025. (Se recomienda corroborar estos resultados gráficamente con TORA o IORTutorial). Notar que si la variación del lado derecho de la restricción 1 está por fuera del intervalo [1.400,1.733,33], no se puede utilizar el precio sombra para predecir cuál será el nuevo valor óptimo.

En un próximo análisis complementaremos el cálculo del precio sombra de las restricciones 2 y 3 en conjunto con otros Análisis de Sensibilidad en la resolución de modelos de programación lineal. Hasta entonces!

Cómo resolver un modelo de Programación Lineal con Geogebra

En los cursos básicos de Investigación de Operaciones (o Investigación Operativa) frecuentemente el tema de introducción y discusión inicial es la formulación y resolución de modelos de optimización lineales para apoyar el proceso de toma de decisiones.

En este contexto se suelen abordar formulaciones matemáticas sencillas como los cubiertas en Programación Lineal y para entender sus propiedades se estudian modelos que consideran 2 variables de decisión para que sea factible y sencillo representarlos gráficamente, de modo de encontrar su solución óptima y valor óptimo (en caso de existir).

Al respecto cabe destacar que aquellas propiedades que se desprenden de la resolución gráfica de modelos lineales se pueden extender a problemas de Programación Lineal de mayor tamaño. Algunos de estos aspectos se detallan en el artículo Teorema Fundamental de la Programación Lineal.

A continuación presentaremos un modelo de Programación Lineal con 2 variables de decisión el cual resolveremos con la ayuda del software libre Geogebra, el cual es muy útil para la representación gráfica de funciones matemáticas, figuras geométricas, entre otras.

El programa se puede descargar gratuitamente tanto a computadores o smartphones, o si se prefiere, ejecutar directamente desde su página www.geogebra.org en Internet.

El siguiente tutorial de nuestro canal de Youtube muestra como resolvemos gráficamente este modelo de Programación Lineal utilizando el software Geogebra.

Una vista final de la representación gráfica del problema lineal propuesto se presenta a continuación:

Con color verde se destaca el polígono que considera todas aquellas soluciones factibles del problema, es decir, aquellos valores para las variables de decisión que satisfacen de forma simultanea el conjunto de restricciones. Dicho dominio de factibilidad se denomina región de puntos factibles o dominio de soluciones factibles.

Adicionalmente con color rojo se observa una linea punteada que representa la curva de nivel de la función objetivo que intercepta el vértice óptimo (solución óptima). La solución óptima es $X_{1}=100$ y $X_{2}=350$ , con valor óptimo $V(P)=3.100$ .

Cabe destacar que existen otras herramientas gráficas que permiten resolver gráficamente un modelo de Programación Lineal en 2 variables. Tal es el caso del software TORA el cual se incluye en el libro de Investigación de Operaciones de H.Taha (ver Cómo Resolver Gráficamente un Modelo de Programación Lineal con TORA) y IORTutorial (Cómo Resolver Gráficamente un Modelo de Programación Lineal con IORTutorial).