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

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.

Formulación de un Problema de Asignación en Programación Entera

El siguiente problema fue enviado por uno de nuestros usuarios de la ciudad de Valparaíso, Chile:

En un evento atlético de gimnasia las competencias comprenden cuatro disciplinas: salto, barras asimétricas, viga de equilibrio y manos libres. Cada equipo debe presentar 5 deportistas por disciplina. Un deportista puede participar como especialista en una o dos disciplinas o bien como un all-rounder que participa en las cuatro disciplinas. Al menos 3 de los miembros del equipo deben ser all-rounder. Un deportista es evaluado en una escala de 1 a 10. De acuerdo a las estadísticas del equipo de gimnasia de la universidad, se tienen las siguientes calificaciones para cada uno de los 6 miembros del equipo actual:

Formule y resuelva un modelo de Programación Entera que permita seleccionar a los 5 deportistas que presentará la universidad en cada disciplina del evento.

A continuación detallamos la formulación de este problema de Programación Entera:

1. Variables de Decisión:

Con i=1,…,6 (deportistas) y j=1,….,4 (deportes)

2. Función Objetivo: Maximizar el puntaje a obtener por los deportistas

Donde Pij representa el puntaje que tiene el deportista i en la disciplina j. Estos valores son parámetros del modelo y son los que se resumen en la tabla del enunciado. Por ejemplo: P13=9.

3. Restricciones:

Si un deportista es all-rounder se debe asignar a todas las disciplinas:

Deben haber al menos 3 deportistas all-rounder:

Se requiere de exactamente 5 deportistas por disciplina:

Límite de disciplinas por deportistas según su categoría:

7 Recursos Gratuitos para el estudiante de Investigación de Operaciones

En Internet existen recursos gratuitos valiosos para los estudiantes de los cursos de Investigación de Operaciones (conocido también como Investigación Operativa) que son de gran ayuda para complementar los conceptos tratados en el aula y la bibliografía. En el siguiente artículo ponemos en disposición de nuestros lectores algunos recursos que recomendamos:

1. Solver: Es sin duda la principal herramienta para resolver modelos de optimización de tamaño reducido utilizado por los alumnos de cursos de ingeniería. Este complemento de Excel se puede descargar desde el sitio web de Frontline en su versión comercial (Premium Solver Pro) para implementar modelos de mayor tamaño.

2. What’sBest!: Es la alternativa a Solver dado que funciona integrada en una planilla de cálculo (Excel). La interfaz es intuitiva y seguramente quién domine Solver no demorará mucho en aprender los elementos básicos de este programa. What’sBest! ha sido desarrollado por la empresa de software Lindo.

3. AMPL: Es un lenguaje de programación matemática que permite abordar la formulación y resolución de modelos de optimización de programación lineal, programación entera y programación no lineal (entre otros). Esta plataforma es popular para modelos de mayor complejidad que requieren para su resolución de algoritmos especializados.

4. GAMS: Es una herramienta de formulación matemática alternativa a AMPL que permite formular y resolver modelos de optimización de complejidad mayor.

5. NEOS Solvers: Es un portal que consolida una gran variedad de solvers (algoritmos) que permiten resolver distintas categorías de modelos de optimización formulados en un lenguaje matemático determinado (como AMPL y GAMS). El procedimiento es el siguiente: se selecciona un solver que permita resolver nuestro modelo (depende del lenguaje de programación matemática y el tipo de modelo), se sube el archivo del modelos (y/o datos) y se obtienen los resultados online.

6. Geogebra: Es un excelente programa que nos ayuda a graficar distintas formas geométricas y en particular resolver gráficamente modelos de optimización lineales o no lineales. Este programa se puede descargar gratuitamente e instalar en nuestro computador o alternativamente utilizar su aplicación web directamente sin necesidad de descargar el programa.

7. Método Simplex (ProgramacionLineal.net): Es una herramienta que permite resolver modelos de programación lineal a través del método simplex, mostrando paso a paso las respectivas iteraciones, solución óptima y valor óptimo.

8. Linear Programming: Versión en inglés de los principales artículos de este Blog que trata sobre la Investigación de Operaciones y en particular de la Programación Lineal, con recursos educativos y ejercicios resueltos.