programación entera Archivos - Página 7 de 8

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.

Cómo lograr un buen desempeño en un curso de Investigación de Operaciones

¿Cómo lograr un buen desempeño en un curso de Investigación de Operaciones?. Esta es una pregunta que usualmente recibimos de nuestros usuarios y probablemente te represente. En el Equipo de Gestión de Operaciones estamos convencidos que esto depende de varios factores y en este artículo te compartiremos nuestra visión al respecto.

1. Participa activamente en la sala de clases: Te recomendamos ser un ente activo del proceso de enseñanza. Si tienes dudas de las materias que el docente este explicando no dejes de preguntar. De seguro tu profesor no tendrá problemas en explicar nuevamente algo que no haya quedado suficientemente claro.

2. Apoya tus estudios con un libro guía: Disponer de un texto guía es una gran ayuda cuando se requiere profundizar en un aspecto teórico de las materias y adicionalmente para revisar casos y ejercicios resueltos. Si cursas un curso introductorio de Investigación de Operaciones te recomendamos conseguir un libro que cubra las principales temáticas del área como la Programación Lineal, Programación Entera, Programación No Lineal y Cadenas de Markov. En nuestra experiencia docente te recomendamos los siguientes textos que los puedes adquirir a precios económicos: Investigacion de Operaciones – Hillier y Lieberman y Investigación de Operaciones, Taha 7° Edición.

3. Explota el potencial de Excel: El tamaño (cantidad de variables de decisión y restricciones) de los modelos de optimización que te sean asignados en clases son generalmente para un fin académico y por tanto no deberías tener inconvenientes en poder implementarlo en Solver o What’sBest!. En nuestro Blog podrás encontrar una serie de artículos que hemos dedicado a estas poderosas herramientas de resolución.

4. Descarga el Libro de Apuntes de Programación Lineal: Nuestro objetivo es ser un apoyo para tus estudios formales de Gestión e Investigación de Operaciones y en este contexto hemos desarrollado un libro de apuntes de programación lineal el cual podrás descargar de forma gratuita si nos recomiendas en las redes sociales.

5. Accede a Recursos Gratuitos para la Investigación de Operaciones: Te recomendamos leer nuestro artículo 7 Recursos Gratuitos para el estudiante de Investigación de Operaciones donde podrás encontrar datos útiles para tus estudios.

Esperamos que estos consejos te ayuden a lograr el objetivo de aprender y en consecuencia aprobar las materias de Investigación de Operaciones.