Programación Lineal Archivos - Página 16 de 17

Interpretación del Informe de Sensibilidad de Celdas Cambiantes (Solver)

Cuando Resolvemos un modelo de Programación Lineal con Solver de Excel utilizamos una estimación de los parámetros (constantes) los cuales generalmente hacen referencia a disponibilidad de recursos, precios, costos, etc. En este contexto nos interesa simular el impacto en los resultados ante variaciones marginales de dichos parámetros sin la necesidad de resolver un nuevo modelo de optimización.

Este objetivo se puede alcanzar a través de los Informes de Sensibilidad de Solver los cuales se pueden generar una vez resuelto un escenario base para un modelo de optimización lineal, seleccionando la opción “Sensibilidad” (o Confidencialidad en versiones recientes de Office) según se muestra a continuación:

El siguiente análisis explica cómo interpretar el Informe de Sensibilidad de Celdas Cambiantes de Solver para el siguiente modelo de Programación Lineal:

Con solución óptima X=14/5 Y=8/5 y valor óptimo V(P)=20,8. El Informe de Celdas Cambiantes corresponde a:

Notar que en la última columna se ha marcado con color rojo la palabra Aumento que debiese decir Disminución (este tipo de error se observa generalmente en las versiones más antiguas de Office).

El Informe de Sensibilidad de Celdas Cambiantes nos indica el intervalo de variación para cada parámetro de la función objetivo que permite mantener la actual solución óptima (asumiendo que el resto de los parámetros permanece constante).

Por ejemplo, el coeficiente que actualmente pondera a la variable X en la función objetivo de maximización es 4. El aumento permisible de 4 nos indica que el actual parámetro podría aumentar en dicha magnitud y la solución óptima actual se mantendría.

Análogamente se podría disminuir en 1 unidad (disminución permisible) y se conserva la solución actual.

En conclusión, el Intervalo de Variación para el parámetro que pondera a la variable X en la función objetivo que conserva la actual solución óptima es entre [3,8].

Siguiendo un procedimiento similar se puede demostrar que el intervalo de variación para el parámetro asociado a la variable Y en la función objetivo que conserva la actual solución óptima es entre [3,8] (sólo es una coincidencia que sean los mismos intervalos para cada parámetro).

Por ejemplo, un cambio en uno de los parámetros de la función objetivo afecta la pendiente de ésta (curvas de nivel) que en la medida que se encuentre en el intervalo de variación previamente determinado mantendrá al vértice C como solución óptima del problema.

Una forma sencilla de corroborar estos resultados es mediante el Método Gráfico en Programación Lineal. Adicionalmente en el artículo Análisis de Sensibilidad Método Gráfico se detalla el procedimiento para obtener los intervalos de variación para los parámetros tanto en la función objetivo como en las restricciones del problema. Recomendamos revisar ambos artículos de modo de favorecer la comprensión de este tipo de análisis.

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

Problema de la Dieta en Programación Lineal resuelto con Solver de Excel

Una de las aplicaciones clásicas de la Programación Lineal es el Problema de la Dieta. El objetivo es seleccionar un conjunto de alimentos dados que permitan satisfacer ciertos requerimientos nutricionales y preferencias y que adicionalmente tenga un costo mínimo.

En este contexto en el Servidor NEOS se puede encontrar un conjunto de antecedentes que permiten comprender el contexto histórico del Problema de la Dieta y cómo se puede abordar de forma eficiente a través de modelos de optimización. Al igual que varias de las aplicaciones de la Investigación de Operaciones este problema tiene un origen militar.

Para efectos de este tutorial y con el objetivo de ilustrar esta aplicación consideremos el siguiente listado de alimentos con su perfil nutricional y costo monetario:

Se desea proponer una dieta que contenga al menos 2.000 (Kcal) , al menos 55 gramos de proteína y 800 (mg) de calcio. Adicionalmente para garantizar cierta variedad en la dieta se establece límites de porciones por día en los alimentos. Con esta información se requiere encontrar la dieta que tenga el menor costo asociado y permita satisfacer los requerimientos anteriores.

Para ello definimos el siguiente modelo de Programación Lineal:

1. Variables de Decisión: Xi : Porciones de alimentos a consumir durante el día del alimento i (Con i=1 ==> Avena, …. i=6 ==> Porotos).

2. Función Objetivo: Minimizar 30X1+240X2+130X3+90X4+200X5+60X6

3. Restricciones:

Mínimo de Calorias (KCal): 110X1+205X2+160X3+160X4+420X5+260X6 >= 2.000
Mínimo de Proteínas: 4X1+32X2+13X3+8X4+4X5+14X6 >= 55
Mínimo de Calcio: 2X1+12X2+54X3+285X4+22X5+80X6 >= 800
Variedad de la Dieta: X1<=4 X2<=3 X3<=2 X4<=8 X5<=2 X6<=2
No Negatividad: Xi>=0 Para todo i.

La implementación de este modelo en Solver de Excel para obtener su solución óptima y valor óptimo se muestra en el siguiente tutorial:

La Solución Óptima es X1=4, X2=0, X3=0, X4=2,08, X5=1,68, X6=2 y el Valor Óptimo (costo de la dieta) es $764,07.

Como el modelo es de Programación Lineal se permiten valores fraccionarios para las variables de decisión. Por tanto si buscamos solo valores enteros para las variables de decisión en ese caso debemos definir un modelo de Programación Entera el cual revisamos en el siguiente artículo: Problema de la Dieta en Programación Entera resuelto con Solver de Excel.

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 el Método Simplex

Existen algunas herramientas en Internet que permiten resolver modelos de Programación Lineal utilizando el Método Simplex. Este tipo de aplicaciones resultan de bastante utilidad para los estudiantes de ingeniería que desean verificar si los resultados que obtienen en la aplicación manual del método resultan ser correctos.

En esta oportunidad revisaremos la interfaz para resolver modelos de Programación Lineal con el Método Simplex disponible en el sitio web ProgramacionLineal.net. Para ello utilizaremos un modelo lineal en 2 variables que previamente resolvimos gráficamente con el complemento Solver de Excel y el software Geogebra.

Cómo resolver un modelo de Programación Lineal con el Método Simplex

El siguiente tutorial muestra cómo implementamos este modelo de optimización con la herramienta de resolución del Método Simplex:

La última tabla del Método Simplex luego de la resolución con esta aplicación y eliminando la columna p (no es necesaria) es la siguiente:

La Solución Óptima (que corresponde a una solución básica factible óptima) es x=100 e y=350 (x e y son las variables básicas de las filas 1 y 3 respectivamente). El valor óptimo es V(P)=3.100. Notar que la solución óptima corresponde al vértice C de la representación gráfica del problema propuesto que se muestra a continuación:

Importante: Las variables s1 y s3 son variables no básicas en la actual solución óptima y por tanto su valor es cero. La variable s2 es la variable básica de la fila 2 y toma el valor de 400. Notar que las variables s1, s2 y s3 son inicialmente las variables de holgura necesarias para llevar el modelo de Programación Lineal a su forma estándar.