solver Archivos - Página 11 de 12 - Gestión de Operaciones

Restricción con Precio Sombra Negativo en Programación Lineal

En Programación Lineal, el Precio Sombra se refiere a una tasa de cambio del valor óptimo ante una modificación marginal del lado derecho de una restricción, entendiendo como marginal una modificación que permita mantener las actuales restricciones activas para el problema (se conserva la base óptima). En este tipo de análisis se asume que el resto de los parámetros del modelo permanecen constantes.

En artículos anteriores hemos analizado Cómo calcular el Precio Sombra de una Restricción Gráficamente y en forma complementaria Cómo interpretar los Informes de Sensibilidad de Restricciones de Solver de Excel. Esto sin duda es una buena base conceptual para entender el significado del Precio Sombra de una restricción.

En esta oportunidad nos referiremos a una situación que a priori podría parecer anómala, pero que definitivamente no lo es: que una restricción asociada a un modelo de Programación Lineal tenga un Precio Sombra negativo.

Para ilustrar este escenario utilizaremos nuevamente el Modelo de Transporte el cual se representa esquemáticamente a continuación:

La resolución computacional de este modelo utilizando Solver de Excel se resume a continuación:

Notar que la Planta 1 tiene un exceso de capacidad de 40.000 unidades (diferencia entre su capacidad de 160.000 y las 120.000 unidades que despacha).

Por el contrario la Planta 2 funciona a máxima capacidad (despacha 120.000 unidades). El Informe de Sensibilidad de restricciones reporta lo siguiente:

La restricción de capacidad de la Planta 2 tiene un Precio Sombra negativo de magnitud -1. Esto significa que si se incrementa en una unidad la capacidad de la Planta 2 (a 120.001 unidades) el nuevo valor óptimo será 939.999.

Análogamente, cualquier cambio en la capacidad de la Planta 2 en el intervalo [120.000-40.000,120.000+40.000]=[80.000,160.000] generará una modificación del valor óptimo del problema proporcional al Precio Sombra de la restricción de capacidad de dicha planta.

Por ejemplo, si la capacidad de la Planta 2 aumenta a 130.000 unidades, el nuevo valor óptimo será:

$V(\bar{P})=V(P)+\Delta b\cdot \pi =940.000+(130.000-120.000)\cdot -1=930.000$

Por el contrario, si la capacidad de la Planta 2 disminuye a 110.000 unidades, el nuevo valor óptimo es:

$V(\bar{P})=V(P)+\Delta b\cdot \pi =940.000+(110.000-120.000)\cdot -1=950.000$

¿Por qué se produce este fenómeno?. Básicamente por una reasignación debido a que resulta ser relativamente más conveniente generar despachos desde la Planta 2 en comparación a la Planta 1 (que tiene capacidad ociosa y por tanto un Precio Sombra igual a cero).

Problema de Producción e Inventario resuelto con Solver de Excel

La Programación Lineal nos permite abordar distintos problemas de naturaleza real algunos de los cuales ya hemos tratado en artículos anteriores como el Problema de Transporte, el Problema de Mezcla de Productos y el Problema de la Dieta.

En el siguiente artículo analizaremos otra aplicación clásica conocida como el Problema de Producción e Inventario cuyas extensiones y variantes se pueden consultar adicionalmente en la categoría del Plan Maestro de la Producción.

El Problema de Producción e Inventario consiste básicamente en determinar una política de producción en el tiempo que permita satisfacer ciertos requerimientos de demanda, respetando las limitantes de producción y a un costo mínimo.

Este tipo de modelos se puede extender para varios productos, sin embargo, en esta oportunidad consideraremos un solo producto para su ilustración.

En este contexto, consideremos los siguientes antecedentes de producción que se presentan a continuación:

Luego, definimos el siguiente modelo de optimización lineal:

Supuesto: se dispone de un inventario inicial de 50 unidades, es decir, I0=50.

1. Variables de Decisión:

Xt: Unidades a producir en el mes t (t=1,..,6 con t=1 => Enero; t=6 => Junio)
It: Unidades a almacenar en inventario al final del mes t (t=1,..,6 con t=1 => Enero; t=6 => Junio)

2. Función Objetivo: Minimizar los costos de producción (destacados con color azul) y costos de inventario (destacados con color rojo) durante el período de planificación definido por:

60X1 + 60X2 + 55X3 + 55X4 + 50X5 + 50X6 + 15I1 + 15I2 + 20I3 + 20I4 + 20I5 + 20I6

De forma compacta (parametrica) se puede representar la función objetivo como:

$Minimizar\sum_{t=1}^{6}[C_{t}\cdot X_{t}+H_{t}\cdot I_{t}]$

Donde $C_{t}$ es el costo unitario de producción en el mes t (por ejemplo $C_{1}=60$ ) y $H_{t}$ es el costo unitario de almacenar unidades en inventario durante el mes t (por ejemplo $H_{1}=15$ )

3. Restricciones:

a) Satisfacer los requerimientos de demanda (conocida como restricción de Balance de Inventario).

Por ejemplo, el inventario disponible al final del mes de Enero será el resultado de la producción del mismo mes, más el inventario inicial (que se asume un dato, en este caso 50 unidades) menos la demanda satisfecha durante el mes de Enero.

X1 + 50 – I1 = 100 (Enero)
X2 + I1 – I2 = 130 (Febrero)
X3 + I2 – I3 = 160 (Marzo)
X4 + I3 – I4 = 160 (Abril)
X5 + I4 – I5 = 140 (Mayo)
X6 + I5 – I6 = 140 (Junio)

Notar que la restricción se Balance de Inventario impuesta para un producto se puede generalizar como: $X_{t}+I_{t-1}-I_{t}=d_{t}$ , donde $d_{t}$ representa la demanda estimada (parámetro) para el mes t.

b) Respetar la capacidad máxima de producción mensual (oferta).

Se establece que la oferta o producción máxima mensual no puede superar la capacidad de producción.

X1<=120 X2<=120 X3<=150 X4<=150 X5<=150 X6<=150

O simplemente $X_{t}\leq O_{t}$ donde $O_{t}$ es la capacidad de producción máxima del mes t (parámetro).

c) Condiciones de no negatividad.

De forma natural y dada nuestra definición cada variable de decisión debe ser no negativa.

Xt >= 0 It >= 0 Para todo t

El siguiente tutorial muestra cómo implementar este Modelo de Producción e Inventario correspondiente a la Programación Lineal en Solver de Excel:

La solución óptima se muestra a continuación con un valor óptimo de $43.450. Se puede apreciar que se producen en total 780 unidades entre Enero y Junio las cuales junto al inventario inicial de 50 unidades permiten satisfacer los requerimientos de demanda mensualmente.

¿Quieres tener el archivo Excel con la resolución en Solver de este problema?.

[sociallocker]

MUCHAS GRACIAS!. DESCARGA AQUÍ EL ARCHIVO

[/sociallocker]

Instalación del Complemento Solver en Excel 2003

El complemento de Solver de Excel es una poderosa herramienta que permite resolver modelos de optimización utilizando una planilla de cálculo (Excel). En artículos anteriores hemos mostrado Cómo resolver Modelos de Programación Lineal utilizando Solver y algunas aplicaciones clásicas como el Problema de Transporte y Problema de la Dieta.

Las características de Solver han evolucionado en las distintas versiones de Office y en esta oportunidad mostraremos cómo activar este complemento en la versión del año 2003 y 2007. Para ello se deben seguir los siguientes pasos:

Paso 1: Abrir el programa Excel y en el menú de Herramientas seleccionar Complementos.

Paso 2: Seleccionar la opción Solver y luego Aceptar.

Paso 3: Puede ser necesario aprobar la ejecución del complemento como muestra la imagen a continuación. En este caso se debe seleccionar Sí

Paso 4: Una vez completada la activación de Solver el complemento estará disponible en el menú de Herramientas de Excel.

Una alternativa a Solver es el complemento de Excel OpenSolver el cual se puede descargar gratuitamente desde www.opensolver.org. En el artículo Cómo resolver un modelo de Programación Lineal con OpenSolver mostramos su utilización en un problema sencillo. Adicionalmente What’sBest! resulta ser otra excelente alternativa para Solver y desarrollado para Excel. En el siguiente tutorial detallamos cómo descargar e instalar What’sBest!.

Interpretación del Informe de Sensibilidad de Restricciones de Solver

Continuando con el Análisis de Sensibilidad (o Análisis Postoptimal) en la resolución de modelos de Programación Lineal, en este artículo analizaremos la interpretación del Informe de Sensibilidad (o Informe de Confidencialidad en algunas de las versiones de Office que datan del año 2010 a la fecha) de restricciones de Solver, comúnmente conocido como el análisis del Precio Sombra de cada una de las restricciones.

Por ejemplo, la versión de Solver disponible con Office 365 ofrece la siguiente interfaz para obtener el Informe de Sensibilidad (luego de alcanzar la solución óptima del problema en su escenario base).

En el caso de la versión de Solver compatible con Office 2007 y Office 2003, la interfaz es la siguiente:

De modo de ilustrar su correcta interpretación, a continuación consideraremos nuevamente nuestro ejemplo de Programación Lineal:

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

Las filas del Informe de Restricciones corresponden a las restricciones 1 y 2, respectivamente.

En el caso de la restricción 1 el Precio Sombra es de 1,2 y el valor de la restricción (lado derecho) es igual a 12. Para dicho parámetro (lado derecho) se permite un aumento de de 9,33 y una disminución de 4, es decir, el lado derecho de la restricción 1 puede variar entre [8, 21,33] (12-4, 12+9,33) y el Precio Sombra de magnitud 1,2 seguirá siendo válido (es decir, se conserva la base óptima).

Esto significa que si, por ejemplo, el lado derecho de la restricción 1 aumenta en 1 unidad y el resto de los parámetros del modelo permanecen constantes, el nuevo valor óptimo será: V(P)=20,8+1*1,2=22.

Ahora bien, si por ejemplo, el lado derecho de la restricción 1 disminuye a 10 el nuevo valor óptimo será: V(P)=20,8-2*1,2=18,4.

Finalmente si la variación del lado derecho esta fuera del intervalo [8, 21,33] NO se puede utilizar el Precio Sombra para poder predecir cuál será el nuevo valor óptimo. Esto se debe a que la nueva solución óptima ya no se encontrará con las mismas restricciones activas, es decir, cambia la base óptima.

Al respecto recomendamos ver el tutorial sobre Cómo calcular gráficamente el Precio Sombra de una Restricción.

De forma análoga, para la restricción 2 el Precio Sombra es de 0,4 y este valor es válido si su lado derecho varía entre [9, 24] (16-7, 16+8). Por ejemplo, si el lado derecho de la restricción 2 aumenta en 3 unidades (y el resto de los parámetros permanece constante) el nuevo valor óptimo será: V(P)=20,8+3*0,4=22.

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.