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

Problema de Producción y Transporte resuelto con Solver

El siguiente problema de producción y transporte fue enviado por uno de nuestros usuarios de Colombia de la ciudad de Santa Cruz de Lorica: “Una compañía que fabrica Cereal de Maíz tiene dos campos de siembra, el Campo I y el Campo II, y dos molinos, A y B. Las capacidades de suministro mensual de maíz de los Campos I y II son 125 y 245 toneladas, respectivamente. El molino A requiere por lo menos 190 toneladas de Maíz al mes y el B por lo menos 158 toneladas mensuales. Los costos de transporte en unidades monetarias por tonelada de cada Campo a cada molino son los siguientes: 2 del Campo I al molino A, 3 desde el Campo I al molino B, 4 desde el Campo II al molino A, y 5 desde el Campo II al molino B”.

¿Qué cantidad de Maíz debe transportarse desde cada Campo I y II a cada molino A y B de forma que se logre minimizar el costo total de transporte? ¿Cuál es ese costo mínimo? ¿Hay algún envío que no debe realizarse para conseguir dicho costo mínimo?.

Para una mejor comprensión del problema anterior representaremos gráficamente la información anterior donde se puede apreciar los distintos oferentes (Campos) y demandantes (Molinos), además de la capacidad de producción y demanda (en toneladas mensuales) junto a los costos de transporte para cada combinación origen destino.

Problema de Producción y Transporte

1. Variables de Decisión: (con i=I,II y j=A,B)

2. Función Objetivo: Minimizar los costos que se asumen mensualmente por el transporte de cereal desde los campos a los molinos.

3. Restricciones:

Capacidad de Producción de los Campos: La cantidad de toneladas que se transporte desde cada campo a cada uno de los molinos no puede superar su capacidad de producción.

Demanda de los Molinos: Cada molino debe recibir un mínimo de toneladas mensuales de cereal desde los campos.

No Negatividad: Las variables de decisión deben adoptar valores reales no negativos.

A continuación se detalla la implementación computacional del modelo de optimización haciendo uso de Solver de Excel:

Notar que la celda F9 es una fórmula asociada a la función objetivo que pondera los costos unitarios de transporte por las toneladas transportas en cada combinación de origen (campos) destino (molinos). La celda E3 es la suma de C3 y D3 (análogamente E4=C4+D4) representando las restricciones de capacidad. De similar forma la celda C5 es una fórmula que considera la suma de las celdas C3 y C4 (por supuesto D5=D3+D4). Una vez generada la estructura del modelo de Programación Lineal se carga éste en la interfaz de Solver:

La solución óptima (celdas color amarillo) consiste en transportar 125 toneladas del Campo I al Molino B y el Campo II envía 190 y 33 toneladas a los Molinos A y B, respectivamente. El valor óptimo es de 1.300 unidades monetarias.

¿Quieres tener el archivo Excel con la resolución en Solver de este problema?. Recomiéndanos en Facebook o Google+ utilizando la herramienta de redes sociales a continuación y accede de forma gratuita e inmediata a la descarga del archivo.

[sociallocker]Problema de Producción y Transporte[/sociallocker]

Como resolver un modelo de Programación Lineal con OpenSolver

OpenSolver es una excelente complemento de Excel que permite resolver modelos de optimización. En el siguiente artículo se describe cómo resolver un modelo de Programación Lineal con esta herramienta (previa descarga e instalación de OpenSolver en Excel 2010). Para fines académicos consideraremos un modelo lineal con 2 variables de decisión, no obstante se puede extender su aplicación a problemas de mayor tamaño sin inconvenientes.

A continuación necesitamos preparar una planilla Excel que considere los parámetros y variables del modelo (este paso es similar a la carga de un modelo en Solver de Frontline). Se puede apreciar que las celdas B2 y C2 (color amarillo) han sido asignadas a las variables de decisión y la función objetivo (celda azul) corresponde a la celda E2 que es una fórmula que vincula las variables de decisión y los respectivos parámetros que ponderan a éstas. Finalmente las celdas D5 y D6 son fórmulas que representan el “lado izquierdo” de las restricciones del problema (por ejemplo la celda D5 corresponde a B2*B5+C2*C5 o equivalentemente SUMAPRODUCTO(B2:C2;B5:C5)).

Una vez completado el paso anterior se debe ejecutar OpenSolver cuyo menú esta disponible en la pestaña de “Datos” de Excel. Luego se selecciona “Model…” según se muestra a continuación:

La interfaz para implementar el modelo es bastante similar a la versión tradicional de Solver (Frontline). Se define la celda objetivo (E2) en maximización; a continuación se selecciona el rango de variables de decisión (según se muestra en la siguiente imagen) y las restricciones. Si intentas replicar la estructura del ejemplo que desarrollamos en este artículo se debería ver así:

Luego seleccionamos “Save Model” (cambiará la estructura de la planilla la cual adoptará colores lo cual es una de las características de OpenSolver que hacen de este complemento una herramienta intuitiva para el usuario).

Finalmente seleccionamos “Solve”:

El programa se ejecutará y proporcionará (de existir) la solución óptima (X=0 e Y=60) y valor óptimo (V(P)=1.200) del problema de optimización:

Los resultados alcanzados son coincidentes con los alcanzados en la resolución gráfica del problema que hemos abordado en el artículo “Qué significa un Precio Sombra igual a Cero en Programación Lineal“ según muestra la imagen a continuación:

A continuación puedes descargar el archivo con la resolución en OpenSolver de este problema de modo de que puedas familiarizarte con este complemento de Excel: Modelo de Programación Lineal resuelto con OpenSolver

Cómo secuenciar n Trabajos en una Máquina para minimizar Setup

El orden o secuencia en el cual se programan n trabajos en una máquina es significativo a la hora de estimar los tiempos de setup para pasar de un determinado trabajo a otro o incluso comenzar con cualquiera de ellos al inicio de la planificación.

En este contexto se reconoce formalmente como tiempo de setup la cantidad de tiempo necesario para preparar una máquina para realizar una operación diferente y cumplir con las especificaciones del cliente (estos tiempos de setup pueden representar por ejemplo calibración de la máquina, cambio de formatos, limpieza, mantención preventiva, etc).

En el siguiente artículo formularemos y resolveremos un modelo de Programación Entera que permita encontrar una secuenciación óptima de n trabajos en una máquina, lo cual será contrastado con la solución que se puede obtener por simple enumeración de secuencias, naturalmente para un número de trabajos “pequeño” (para fines académicos).

En general si se deben programar n trabajos en una máquina, la cantidad de secuencias posibles son n!.

Por ejemplo si tenemos 3 trabajos (n=3) que debemos asignar a una máquina la cantidad de secuencias posibles son 6 (3!=3*2*1). Lo anterior implica que aún para centros de trabajos pequeños es útil contar con un procedimiento que permita identificar aquella secuencia que minimice el makespan sin tener la necesidad de hacer una evaluación exhaustiva de cada una de ellas.

Consideremos un conjunto de trabajos que necesitan ser asignados a una cierta máquina, todos los cuales están disponibles al inicio de la programación y se conoce los tiempos de proceso y fechas de entrega como muestra la siguiente tabla:

Sin embargo, el tiempo de setup, correspondiente al tiempo requerido para preparar la máquina antes de cada trabajo, depende del trabajo que le precede. A continuación se indica los tiempos de setup aij cuando al trabajo j le precede el trabajo i:

Adicionalmente hay un tiempo de setup a0j asociado al primer trabajo a programar de acuerdo a los siguientes valores:

El objetivo entonces es programar las actividades de modo de minimizar el tiempo de utilización de la máquina (makespan) como resultado de la asignación propuesta. Notar que según lo descrito anteriormente el problema admite 6 secuencias posibles las cuales se enumeran a continuación para poder obtener el makespan de la programación.

Secuencia 1-2-3: 1+9+1+13+3+10=37[t]
Secuencia 1-3-2: 1+9+0+10+1+13=34[t]
Secuencia 2-1-3: 3+13+2+9+0+10=37[t]
Secuencia 2-3-1: 3+13+3+10+3+9=41[t]
Secuencia 3-1-2: 4+10+3+9+1+13=40[t]
Secuencia 3-2-1: 4+10+1+13+2+9=39[t]

Naturalmente la secuencia óptima es 1-3-2 con un makespan de 34[t]. Como el trabajo 1 es el que inicia la secuencia tiene un setup inicial de a01=1 y requiere de 9[t] para ser completado. A continuación sigue el trabajo 3 que dura 10[t] y como es el trabajo 1 el que le precede no se requiere tiempo de setup (a13=0). Finalmente se realiza el trabajo 2 con duración de 13[t], necesitándose 1[t] para pasar del trabajo 3 al trabajo 2 (a32=1).

Para abordar el problema anterior a través de un modelo de optimización definiremos el siguiente problema de Programación Entera que claramente permite extender su aplicación a problemas de mayor tamaño (número de trabajos):

Variables de Decisión:

Para i=1,2,3 y j=0,1,2,3 con i≠j. Por ejemplo si X10=1 esto indica que el trabajo 1 es el que se realiza inmediatamente después del trabajo 0, es decir, el trabajo 1 es el que inicia la secuencia.

Función Objetivo:

En la implementación computacional con Solver de Excel la función objetivo se representa a través de la siguiente fórmula:

Para mayor claridad a continuación un extracto de la pantalla del modelo computacional:

Se busca minimizar el makespan de la secuencia. Notar que se suman las constantes asociadas al tiempo de proceso de cada trabajo (las cuales son independientes de la secuencia y justifican que inicialmente el valor de la celda que representa la función objetivo sea igual a 32[t]) y que eventualmente se pueden omitir de la función objetivo (en dicho caso el valor óptimo representaría la sumatoria de los tiempos de setup de la secuencia y no el makespan de la programación).

Restricciones:

Se deben realizar los 3 trabajos:

A lo más una tarea sigue a la j-ésima al menos que sea la última de la secuencia:

Alternativas infactibles: (celdas color rojo en la planilla de cálculo)

Debe existir un trabajo inicial en la secuencia:

Luego de resolver con Solver el problema anterior se alcanza la siguiente solución óptima y valor óptimo:

Donde se corrobora que la secuencia óptima es 1-3-2 con un makespan de 34[t]. A continuación puedes descargar el archivo Excel con la resolución del problema anterior en el siguiente enlace: Minimizar Tiempos de Setup.

Formulación y Resolución de un Modelo de Programación Lineal para reducir la duración de un Proyecto (Crashing)

En la Gestión de Proyectos uno de los aspectos claves es determinar los costos asociados a terminar el proyecto en un tiempo determinado. Del mismo modo, resulta de particular interés poder enfrentar de forma eficiente el problema de cómo reducir la duración del mismo de la forma más económica posible, partiendo de la premisa que ciertas actividades eventualmente se podrían desarrollar en un tiempo menor al estimado inicialmente luego de asignar una mayor cantidad de recursos. En este contexto el siguiente artículo aborda la problemática anterior a través de la formulación y resolución computacional de un modelo de optimización lineal.

Consideremos el siguiente proyecto que consta de 12 tareas estrictamente necesarias, donde la relación de predecesores, tiempos (en semanas) y costos se resume en la tabla a continuación:

Por ejemplo la actividad I tiene puede comenzar una vez completadas las actividades F y H y su tiempo estimado es de 1,5 semanas con un costo normal de $75. Sin embargo la actividad I se puede apurar (lo que comúnmente se conoce como “crash” o “crashing”) de modo que su duración pueda ser de 0,5 semanas pero con un costo mayor de $135. En consecuencia la máxima reducción permisible para dicha tarea es de 1 semana (1,5 – 0,5 semanas) con un costo adicional de $60. Asumiremos adicionalmente que existe proporcionalidad entre el tiempo de reducción y el costo adicional, por ejemplo, si quisiéramos reducir la actividad I en 0,5 semanas (es decir, pasar de 1,5 a 1,0 semanas) el costo de la actividad sería $105 ($75+0,5*$60) y el costo adicional (sobre el costo normal) es de $30.

A continuación determinamos la duración del proyecto utilizando el Método de Ruta Crítica (CPM), considerando los tiempos normales estimados para cada actividad.

El proyecto tiene una duración estimada de 15,5 semanas y existe una única ruta crítica: A-B-D-G-H-I-K-L (notar que todas las actividades en esta ruta tienen holgura igual a cero). El costo del proyecto es de $2.620 y se obtiene simplemente sumando los costos normales de cada una de las actividades. La notación que hemos utilizado es:

Donde IC: Inicio más Cercano; TC: Término más Cercano; IL: Inicio más Lejano; TL: Término más Lejano; TN: Tiempo Normal, HOLG: Holgura. De esta forma, por ejemplo, la actividad I tiene un tiempo normal de 1,5 semanas y holgura igual a cero, es decir, si se retrasa esta actividad el proyecto también se retrasará.

En este contexto, el siguiente modelo de Programación Lineal permite abordar de forma óptima el problema de cómo reducir la duración del proyecto de la forma más económica posible, mediante la reducción del tiempo de las actividades (en particular de las actividades pertenecientes a la(s) ruta(s) crítica(s)). Cabe destacar que en la actualidad existen softwares que facilita este tipo de procedimientos (Crashing) como por ejemplo WINQSB.

Variables de Decisión:

Parámetros:

Función Objetivo: Se buscar minimizar el costo adicional asociado al proyecto luego de hacer el “crashing” necesario para completar el proyecto en un tiempo determinado. Notar que podríamos agregar en la función objetivo como constante el costo normal del proyecto ($2.620) en donde en dicho caso la interpretación del valor óptimo sería el costo total del proyecto que tiene duración de K semanas.

Restricciones:

Cada actividad se puede reducir (de ser posible) dentro del límite máximo de reducción permisible:

Relaciones de predecesores entre las actividades y el tiempo de inicio y reducción:

Por ejemplo en conjunto las inecuaciones (3) y (4) representan que la semana de inicio para la actividad D será mayor o igual a la semana de término (luego de una eventual reducción) de la que termine más tarde entre sus actividades predecesoras (B y C). Adicionalmente hemos definido una actividad “ficticia” o de término llamada “M” la cual tiene como predecesoras a aquellas actividades que terminan una ruta para el proyecto (no necesariamente crítica) y nos permitirá estimar la duración del proyecto.

Definición del tiempo objetivo para el proyecto:

En la resolución computacional con Solver de Excel se puede simular para distintos valores del parámetro K de modo de ver cómo cambian los resultados. La mínima duración del proyecto estará dada por el menor valor de K que permite generar una instancia factible para el modelo de optimización.

No negatividad de las variables de decisión:

Los resultados se muestran en la tabla a continuación donde la mínima duración del proyecto corresponde a 8,5 semanas con un costo total de $3.295 ($675 adicional al costo normal del proyecto). En las celdas color amarillo (variables de decisión) se puede apreciar la solución óptima donde queda explícito cuándo comienza la actividad y cuánto se reduce respecto a su tiempo normal. Por ejemplo la actividad G comienza al cabo de 2,5 semanas (a contar del inicio del proyecto) y su duración normal se reduce en 1,5 semanas (es decir pasamos de un tiempo normal de 3 a 1,5 semanas).

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

[sociallocker]Muchas Gracias!. Descarga aquí el Archivo Excel con la resolución de este problema[/sociallocker]

Ejemplo de un Problema de Mezcla de Productos en Programación Lineal

Una de las aplicaciones clásicas de los modelos de Programación Lineal son los problemas de mezcla de productos. Si la calidad de un producto que se procesa mediante la mezcla de determinados insumos se puede aproximar de forma razonable a través de una proporción, entonces un modelo de optimización lineal puede resultar de utilidad. El ejemplo a continuación muestra dicha situación para el caso de una refinería:

Problema de Mezcla de Productos en Programación Lineal

Una refinería de petróleos produce dos tipos de gasolina sin plomo: regular y extra, las cuales vende a los distribuidores en US$12 y US$14 por barril, respectivamente. Ambos tipos se preparan a partir del inventario de petróleo nacional refinado y de petróleo importado refinado que tiene la empresa (es decir mediante mezcla), las que deben cumplir las especificaciones que se presentan en la siguiente tabla:

Las características del inventario de petróleos refinados son las siguientes:

Se requiere formular y resolver un modelo de Programación Lineal que permita maximizar el ingreso semanal de la refinería, satisfaciendo los requerimientos previamente detallados.

Variables de Decisión:

Xnr: Barriles de petróleo nacional utilizados en la producción de gasolina regular
Xne: Barriles de petróleo nacional utilizados en la producción de gasolina extra
Xir: Barriles de petróleo importado utilizados en la producción de gasolina regular
Xie: Barriles de petróleo importado utilizados en la producción de gasolina extra

Función Objetivo: Se busca maximizar los ingresos semanales que percibe la refinería en la producción de gasolina regular y extra.

Max 12*(Xnr + Xir) + 14*(Xne + Xie)

Restricciones:

Presión de Vapor: El promedio ponderado de la presión de vapor de los distintos tipos de petróleos que participan de la mezcla no debe superar las 23 unidades (para cada tipo de gasolina).

(25Xnr + 15Xir ) / (Xnr + Xir) <= 23
(25Xne + 15Xie ) / (Xne + Xie) <= 23

Octanaje Mínimo: El promedio ponderado del octanaje de los distintos tipos de petróleos que participan de la mezcla debe ser al menos 88 y 93 unidades para la gasolina regular y extra, respectivamente.

(87Xnr + 98Xir ) / (Xnr + Xir) >= 88
(87Xne + 98Xie ) / (Xne + Xie) >= 93

Demanda Mínima y Máxima: Para cada gasolina se debe producir semanalmente una cantidad de barriles entre el mínimo y el máximo permitido.

50.000 <= Xnr + Xir <= 100.000
5.000 <= Xne + Xie <= 20.000

Inventario: Para la producción de gasolina regular y extra se debe respetar la disponibilidad de barriles de petróleo nacional e importado.

Xnr + Xne <= 40.000
Xir + Xie <= 60.000

No Negatividad: Las variables de decisión naturalmente deben adoptar valores mayores o iguales a cero.

Xnr, Xne, Xir, Xie >= 0

Al implementar el modelo de optimización anterior en Solver se alcanza la siguiente solución óptima y valor óptimo:

Se deben destinar 30.909,09 barriles de petróleo nacional para la producción de gasolina regular, 9.090,91 barriles de petróleo nacional para la producción de gasolina extra, 49.090,91 barriles de petróleo importado para la producción de gasolina regular y 10.909,09 barriles de petróleo importado para la producción de gasolina extra. La política de producción anterior permite generar un ingreso semanal de US$1.240.000.

Una recomendación en la carga computacional es rescribir las restricciones que incluyan proporciones de forma equivalente, de modo de evitar divisiones entre celdas cambiantes (variables de decisión) y adicionalmente denominadores que adopten inicialmente un valor igual a cero. Por ejemplo la restricción: (25Xnr + 15Xir ) / (Xnr + Xir) <= 23 se puede representar de forma análoga de la siguiente forma: (25Xnr + 15Xir ) -23 (Xnr + Xir) <= 0. De esta forma se puede corrobar, por ejemplo, que en la solución óptima la presión de vapor que alcanza la producción de barriles de gasolina regular es de: (25*30.909,09 + 15*49.090,91 ) / (30.909,09 + 49.090,91)=18,8636 (aprox) que es menor o igual al límite de 23 unidades.

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

[sociallocker]Problema Mezcla de Productos[/sociallocker]