Programación Entera Archivos - Página 7 de 9

Solver, Premium Solver Pro y What’sBest! en la resolución del Problema de Localización y Transporte

¿Qué complemento de Excel es mejor para resolver un modelo de optimización: Solver, Premium Solver Pro o What’sBest!?. Esta consulta fue enviada por uno de nuestros seguidores de México y en este artículo trataremos de presentar algunos argumentos que permitan al lector formar una opinión al respecto. Para ello utilizaremos como caso aplicado la resolución del Problema de Localización y Transporte (Programación Entera Mixta). A continuación te presentamos los resultados que alcanzamos con Solver, Premium Solver Pro y What’sBest!.

Resolución con Solver: Se alcanza una solución factible con un costo total asociado de US$12.617.919.

Resolución con Premium Solver Pro: Se alcanza una solución factible con un costo total de US$12.414.340.

Resolución con What’sBest!: Se alcanza una solución factible con un costo total de US$12.414.340. Notar sin embargo que la solución óptima difiere de la alcanzada al implementar el modelo con Premium Solver Pro aun cuando tiene asociado idéntico valor de la función objetivo.

Comentarios: Se puede apreciar que la versión básica de Solver genera una solución factible con un costo mayor a la obtenida tanto con Premium Solver Pro y What’sBest!. Lo anterior sugiere la conveniencia de implementar este tipo de problemas con una herramienta de resolución mejorada. Adicionalmente, en la medida que un modelo de optimización crece en tamaño y complejidad es recomendable poder contrastar los resultados obtenidos con distintas herramientas de resolución de modo de tener una mayor claridad si las soluciones obtenidas son sólo factibles o eventualmente óptimas. A continuación encontrarás un tutorial que hemos subido a Youtube con la resolución del problema de localización y transporte.

Formulación de un Problema de Localización y Transporte (Programación Entera Mixta)

Un modelo de Programación Entera Mixta (PEM) es un híbrido entre la Programación Lineal (PL) y la Programación Entera (PE), es decir, corresponde a una categoría particular de modelamiento matemático con características similares a la Programación Lineal pero donde un subconjunto de las variables de decisión deben adoptar valores enteros o binarios. Este característica de la Programación Entera Mixta permite representar situaciones de naturaleza real como los problemas que consideran la inclusión de costos fijos. En este contexto el siguiente artículo aborda la formulación de un Problema de Localización y Transporte el cual se describe a continuación.

Una ciudad tiene 10 zonas o áreas urbanas cada una de los cuales genera una determinada cantidad de basura (en toneladas) durante el periodo de planificación según se describe a continuación:

La basura generada debe ser transportada a centros de depósitos o vertederos entre un total de 5 candidatos posibles, cada uno de los cuales tiene un costo fijo de construcción en dólares.

Adicionalmente se ha estimado el costo de transportar una tonelada de basura desde una zona a cada uno de los potenciales centros de depósito, el cual depende básicamente de la distancia a recorrer y el tipo de transporte seleccionado.

Formule un modelo de Programación Entera Mixta que permita seleccionar los centros de depósito a construir y la política de transporte de basura que minimiza los costos totales.

1. Variables de Decisión: Sea i=1,…,10 las Zonas y j=1,…,5 los Depósitos:

2. Función Objetivo: Con el propósito de trabajar con una notación compacta podemos definir el siguiente conjunto de parámetros para el modelo de optimización:

Tij: Costo de transportar una tonelada de basura desde la Zona i al Depósito j
Fj: Costo fijo de construcción del Depósito j

La función objetivo en consecuencia se puede representar a través de la siguiente expresión:

3. Restricciones:

Se debe despachar (transportar) la totalidad de la basura que genera cada Zona (definimos para ello el parámetro Ai como la cantidad de basura en toneladas que genera la Zona i).

Se debe respetar la capacidad de almacenamiento de basura para cada Depósito, utilizándolo sólo en caso que se decida su construcción. Para ello definimos el parámetro Cj como la capacidad de almacenamiento de basura en toneladas del Depósito j. Lo anteriormente expuesto explica la ponderación de la capacidad por la variable binaria para cada j.

Finalmente establecemos condiciones de no negatividad para Xij>=0 Para todo i,j y Yj{0,1} para todo j.

¿Quieres saber cuál es la solución de este problema?. Te recomendamos leer el siguiente artículo: Solver, Premium Solver Pro y What’sBest! en la resolución del Problema de Localización y Transporte.

Problema de Corte de Rollos en Programación Entera (Premium Solver)

En el artículo anterior abordamos una aplicación clásica de la Programación Entera conocida como el Problema de Corte de Rollos («Cutting Stock Problem») el cual en esta oportunidad resolveremos utilizando la versión Premium de Solver. Si bien el tamaño y complejidad del modelo permitiría enfrentar su resolución sin mayores inconvenientes con la versión tradicional de Solver, utilizaremos Premium Solver Pro para efectos ilustrativos del uso de esta herramienta mejorada.

En este contexto recordemos las características del modelo de optimización de corte de rollos que consiste en minimizar una función de pérdida de material sujeta a restricciones que permiten satisfacer la demanda de rollos de menor tamaño y que incluye adicionalmente condiciones de no negatividad e integralidad para las variables de decisión:

2X1+X2+X3+X8+X9+X13>=150
X2+3X4+2X5+X6+X8+2X10+X11+X14>=200
X2+3X3+2X5+3X6+5X7+X9+X10+2X11+4X12+X14+3X15>=175
Xi>=0 Enteros (i=1,…,15)

Con el objetivo de implementar en Premium Solver Pro el problema anterior creamos en Excel una estructura que resuma la información del problema y que facilite su resolución. La imagen a continuación considera en las celdas con color amarillo las variables de decisión (15 variables) y en la celda J20 (color celeste) la función objetivo.

A continuación para definir las variables de decisión seleccionamos «Decision» y luego «Normal». Notar que previamente se ha seleccionado el rango de celdas que queremos definir como variables de decisión (en este ejemplo las 15 celdas en color amarillos).

Para restringir el valor que adopten las variables de decisión a números enteros se debe ir a «Constraints», «Variable Type/Bound», «Integer» como muestra la siguiente imagen:

Ahora nos posicionamos en la celda J20 que contiene la función objetivo (esta celda contiene una fórmula que es la sumaproducto de la pérdida de material en [cm] asociada a cada patrón de corte ponderada por la cantidad de veces que se utiliza un esquema de corte definido). Luego en «Objective» seleccionamos «Min».

En el siguiente paso corresponde incorporar las restricciones de demanda para el problema. Notar que dado que las restricciones de demanda de rollos de 45[cm], 30[cm] y 18[cm] son todas del tipo «>=» las podemos incorporar todas de forma simultanea tal se muestra a continuación:

Finalmente estamos en condiciones de poder resolver el modelo de optimización con Premium Solver Pro. A la derecha de la planilla de cálculo encontraremos la interfaz del programa que resume las características del problema que hemos implementado.

Seleccionamos el icono con flecha verde que esta en la esquina superior derecha de la imagen anterior para resolver el modelo, obteniendo la solución óptima y valor óptimo que se muestra a continuación:

La solución óptima consiste en utilizar 150 veces el patrón de corte 3 (X3=150) y 100 veces el patrón de corte 10 (X10=100), omitiéndose el uso de los otros esquemas de corte. Con esto la pérdida de material (total) asciende a 350[cm] de papel, logrando satisfacer la demanda para cada tipo de rollo (notar que para el caso de los rollos de 18[cm] se producen 550[u] siendo la demanda de 175[u]). En nuestro canal de Youtube puedes revisar la implementación y resolución computacional del modelo anterior.

Formulación del Problema de Corte de Rollos en Programación Entera

El Problema de Corte de Rollos (conocido también por «Cutting Stock Problem») es una de las aplicaciones clásicas de la Programación Entera que consiste en determinar cómo cortar un rollo de papel en dimensiones más pequeñas, de modo de satisfacer las demandas u ordenes de los clientes y al mismo tiempo minimizar la pérdida de material.

En este contexto, el Problema de Corte de Rollos se puede extender fácilmente a otra serie de aplicaciones prácticas como la industria textil, muebles, acero, etc, donde se dispone de un insumo que se debe cortar para poder utilizarlo como materia prima o venderlo directamente a los clientes y en donde en dicho proceso se incurre necesariamente en una pérdida de material.

A continuación presentaremos un ejemplo del problema de corte de rollos de papel, donde se dispone de rollos de 100[cm], 80[cm] y 55[cm] y los clientes demandan rollos más pequeños de 45[cm], 30[cm] y 18[cm]. Notar que dependiendo el esquema o patrón de corte a utilizar existe una pérdida de papel (en [cm]) asociada. Por ejemplo, el esquema de corte 1 representado en la imagen a continuación considera cortar un rollo de 100[cm] en 2 rollos más pequeños con una pérdida de 10[cm].

Al resumir las posibles combinaciones de cortes para los rollos se identifican 15 patrones. Adicionalmente los clientes demandan 150[u], 200[u] y 175[u] de los rollos de 45[cm], 30[cm] y 18[cm], respectivamente.

Para el problema anterior consideremos el siguiente modelo de Programación Entera:

1. Variables de Decisión:

Xi: Número de Rollos cortados bajo el esquema o patrón de corte i (con i=1,…,15 que representa las distintas combinaciones posibles)

2. Función Objetivo:

Minimizar la pérdida de material total que esta dada por la ponderación de la pérdida en centímetros asociada a cada esquema de corte por la cantidad de veces que se utiliza el esquema respectivo.

Minimizar 10X1+7X2+X3+10X4+4X5+16X6+10X7+5X8+17X9+2X10+14X11

+8X12+10X13+7X14+X15

La notación anterior se puede expresar de forma equivalente y compacta definir el conjunto de parámetros Pi que indica la pérdida en centímetros asociada al patrón de corte i. La función objetivo en este caso sería:

3. Restricciones:

Se debe satisfacer la demanda de rollos de 45[cm], 30[cm] y 18[cm]. En este contexto las restricciones son:

Rollos de 45[cm]: 2X1+X2+X3+X8+X9+X13>=150
Rollos de 30[cm]: X2+3X4+2X5+X6+X8+2X10+X11+X14>=200
Rollos de 18[cm]: X2+3X3+2X5+3X6+5X7+X9+X10+2X11+4X12+X14+3X15>=175

Por ejemplo en el caso de los rollos de 45[cm] se puede satisfacer la demanda de 150[u] sólo con el esquema de corte 1, 2, 3, 8, 9 y 13. En el lado izquierdo de la respectiva restricción se pondera la variable por la cantidad de rollos de la dimensión requerida obtenidos al utilizar el esquema de corte seleccionado.

Finalmente definimos condiciones de no negatividad e integralidad para las variables de decisión: Xi>=0 Enteros. Para i=1,…,15. En este tipo de aplicaciones es natural requerir un número entero para el valor que adopten las variables de decisión dada la naturaleza del problema formulado.

Cómo descargar e instalar Premium Solver en Excel 2010

Solver es sin duda junto a What’sBest! la herramienta más popular para resolver modelos de optimización utilizando Microsoft Excel como plataforma. En efecto la versión gratuita que utilizamos de Solver es desarrollada por Frontline Systems Inc, empresa que ofrece un importante número de herramientas y motores de resolución que son de gran utilidad para enfrentar problemas de naturaleza real aplicados en la industria.

En el siguiente artículo nos referiremos a cómo descargar e instalar la versión de prueba de Premium Solver que está disponible en forma gratuita por un período de 15 días y la cual nos permite enfrentar la resolución de modelos de Investigación Operativa significativamente mayores tanto en el número de variables de decisión como restricciones, que aquellos posibles de abordar con la versión tradicional de Solver.

Adicionalmente, al contar con algoritmos de resolución mejorados se favorece la confiabilidad de las soluciones encontradas y los tiempos de procesamiento.

A continuación presentamos el procedimiento detallado para descargar e instalar la versión de prueba de Premium Solver en un computador con Excel versión 2010.

Paso 1: Ingresar a Frontline Systems Inc, completando la información requerida en el formulario de suscripción.

Paso 2: Descargar la versión de prueba compatible con la versión de Excel que dispongamos. En este tutorial se muestra la instalación de la versión de 64 bits. Una vez que estamos seguros de nuestra elección seleccionamos «Download Now».

Si tienes Excel 2010 y deseas saber de cuántos bits es la versión que utilizas ejecuta Excel y en el menú Archivo selecciona la opción Ayuda. En la esquina inferior derecha se mostrará la cantidad de bits de tu versión bajo el titulo «Acerca de Microsoft Excel».

Paso 3: Revisa tu cuenta de correo electrónico (la que proporcionaste en el formulario de suscripción del Paso 1) y anota las 2 contraseñas que te han sido asignadas (en la imagen a continuación éstas han sido protegidas con color azul y rojo).

Paso 4: Una vez completada la descarga ejecuta el archivo «SolverSetup64.exe» (o el nombre que corresponda según la versión de Excel que estés utilizando).

A continuación se desplegará el asistente para la instalación del programa. (Seleccionar «Next»).

Ahora debemos ingresar los password que hemos recibido por correo electrónico (Paso 3) para continuar con la activación del programa:

Luego debemos aceptar los acuerdos de la licencia del programa y seleccionar «Next».

En estos momentos la licencia del programa ya ha sido activada y continuamos el proceso de la instalación seleccionando «OK».

Se debe seleccionar la carpeta donde se instalará el programa y podemos en este punto seleccionar simplemente aquella ubicación que el programa selecciona por defecto.

Es el momento de seleccionar el producto que deseamos activar. En este caso hemos seleccionado «Premium Solver Pro» que corresponde a la versión mejorada de la versión de Solver que se utiliza generalmente para fines académicos.

El asistente de instalación nos solicitará confirmar la instalación que hemos seleccionado («Install»).

Finalmente hemos completado la instalación del programa Premium Solver Pro y ya estamos en condiciones de poder utilizarlo para resolver modelos de optimización utilizando Microsoft Excel como plataforma.