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

Formulación un modelo de Programación Entera para un Plan Maestro de la Producción (PMP)

La Planificación Agregada y el Plan Maestro de la Producción (PMP o MPS según sus siglas en inglés Master Production Schedule) son metodologías ampliamente utilizadas hoy en día en empresas de manufactura para planificar las necesidades de producción de una serie de productos, de modo de responder a un pronóstico de demanda a través de los recursos productivos que se disponen.

En este contexto, la evidencia empírica muestra que existen diversas estrategias que se pueden utilizar para enfrentar la demanda, cada una de las cuales se puede valorar en términos de costos pero también a través de una serie de criterios cualitativos que por su naturaleza son difíciles de estimar en una unidad monetaria.

A continuación se presenta un gráfico con el Pronóstico de Demanda de un producto para el cual propondremos un modelo de optimización que permita cumplir con dichos requerimientos, minimizando los costos asociados a la utilización de los recursos productivos:

Se puede apreciar que la demanda presenta una estacionalidad marcada donde al inicio y final del año los valores son menores a la demanda de un mes promedio (7.817 unidades).

En contraste con lo anterior en los meses de Junio, Julio y Agosto se presenta un peak de demanda, superando en magnitud claramente lo que correspondería a la demanda de un mes promedio. Adicionalmente consideremos los siguientes antecedentes de operación:

Costo de Contratar un Trabajador: US$1.000
Costo de Despedir un Trabajador: US$1.800
Costo de Almacenamiento Unitario Mensual: US$10
Inventario Inicial: 500 unidades
Costo Remuneración (Sueldo) de un Trabajador al Mes: US$600
Número de Trabajadores al Inicio de la Planificación: 100
Unidades de Producto producidas por un Trabajador al Mes: 50

La pregunta inmediata es: ¿Cómo responder a la demanda pronosticada durante el período de planificación al menor costo posible?. Algunas posibles respuestas son:

Fuerza Laboral Exacta: Esto es mediante contratación y despido de trabajadores para responder de forma exacta a las necesidades de cada mes. Con esta alternativa se busca evitar la acumulación de inventario.

Acumulación y Liquidación de Inventario: Producir en mayor volumen en los meses de menor demanda de modo de acumular inventario para enfrentar los requerimientos adicionales de los meses de mayor demanda. Si se considera adecuado se puede utilizar esta alternativa buscando no afectar el tamaño de la fuerza laboral.

Por cierto también se puede utilizar una estrategia mixta o híbrida que mezcle por ejemplo características de las 2 opciones presentadas anteriormente. Este enfoque generalmente es el que permite alcanzar menores costos.

Adicionalmente cabe destacar que en un Plan Maestro de la Producción (PMP) se podrían considerar otras alternativas o variables de ajuste no consideradas en este ejemplo como la utilización de trabajadores en tiempo extraordinario, la subcontratación parcial de la producción, la eventual postergación de demanda, entre otras opciones.

Luego, en relación a los antecedentes de operación previamente detallados, un modelo de Programación Entera para el Plan Maestro de la Producción es:

1. Variables de Decisión:

2. Función Objetivo:

3. Restricciones:

Satisfacer la Demanda (Balance de Inventario): Donde Dt corresponde a la demanda pronosticada para el mes t (parámetros).

Balance Mano de Obra: La cantidad de trabajadores en operación en cada período corresponde a los trabajadores disponibles al final del mes anterior, más los contratados y menos los despedidos en el mes en curso.

Capacidad de Producción: La producción de cada mes se ve limitada por la disponibilidad de trabajadores y el rendimiento mensual (en unidades de producto) que cada uno de éstos tiene.

No Negatividad e Integralidad: Todas las variables de decisión deben adoptar valores no negativos y adicionalmente ser enteras.

El modelo anterior se puede implementar con Solver y What’sBest! obteniendo los siguientes resultados:

Implementación Computacional en Solver: Se alcanza una solución factible con valor en la función objetivo de US$1.468.700.

El detalle de la resolución la puedes revisar en el siguiente tutorial de nuestro canal de Youtube:

Implementación Computacional con What’sBest!: Se alcanza una solución factible con valor en la función objetivo de US$1.468.400, la cual es ligeramente inferior en costos a la solución obtenida con Solver.

La carga del modelo en What’sBest! y la obtención de los resultados anteriores se puede revisar en el siguiente tutorial de nuestro canal de Youtube:

[sociallocker]Problema PMP www.gestiondeoperaciones.net[/sociallocker]

Problema de Plan de Personal en un Call Center (Programación Entera)

Una línea aérea está considerando incorporar vuelos desde y hacia su aeropuerto base y por lo tanto necesita contratar más agentes de servicio al cliente. Sin embargo, no está claro cuántos más debe contratar. La administración reconoce la necesidad de controlar el costo y al mismo tiempo brindar un nivel de atención satisfactorio. Se ha realizado un análisis del número mínimo de agentes de servicio que deben encontrarse de guardia en diferentes momentos del día para proporcionar un nivel satisfactorio de servicio.

Se ha acordado que cada agente trabaje un turno de 8 horas en los turnos mostrados en la tabla anterior. Por ejemplo, el turno 3 va desde las 12:00 hasta las 20:00. Los sueldos de cada turno son diferentes debido a que unos son más deseables que otros. Por ejemplo, a cada agente que cumpla el turno 3 debemos pagarle diariamente $175.

Se busca formular y resolver un modelo Programación Entera que permita a la línea aérea encontrar el plan de asignación de agentes al menor costo posible y que cumpla los requerimientos impuestos.

1. Variables de Decisión: Establecer un plan de asignación de agentes a los distintos turnos de trabajo.

Xi: Número de Agentes asignados al Turno i con i=1,2,3,4,5 con Xi>=0 {Enteros}

2. Función Objetivo: Minimizar el costo total de la asignación de agentes.

Minimizar 170X1+160X2+175X3+180X4+195X5

3. Restricciones: Se busca garantizar que en cada período del día se cuenta con la cantidad mínima de agentes requeridos.

X1 >= 48
X1 + X2 >= 79
X1 + X2 >= 65
X1 + X2 + X3 >= 87
X2 + X3 >= 64
X3 + X4 >= 73
X3 + X4 >= 82
X4 >= 43
X4 + X5 >= 52
X5 >= 25

A continuación implementamos el modelo anterior en Solver. Notar que las celdas color amarillo son las asignadas a las variables de decisión y éstas a la vez vinculan las combinaciones posibles entre turnos y períodos atendidos.

Adicionalmente en la columna I se ha guardado el valor del lado izquierdo de las restricciones que garantizan el mínimo número de agentes por período.

Finalmente la función objetivo (celda color naranjo) corresponde a la suma producto entre las variables de decisión y los parámetros que representan el costo diario por agente en los respectivos turnos (SUMAPRODUCTO(C4:G4;C19:G19)).

La implementación del modelo anterior en la interfaz de Solver es la siguiente:

Alcanzando la solución óptima del problema que considera la asignación de 48, 31, 39, 43 y 25 personas a los turnos 1,2,3,4 y 5, respectivamente, con un costo total (mínimo) de $32.560.

El siguiente video de nuestro canal en Youtube muestra la resolución del problema anterior:

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

[sociallocker]Descargar Aquí Problema Agentes Call Center[/sociallocker]

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.