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

Conformación de Equipos de Trabajo a través de la Programación Entera

La Programación Entera provee una alternativa metodológica para enfrentar los Problemas de Asignación en donde una serie de recursos (mano de obra, horas máquinas, materia prima, etc) se deben asignar a uno o más fines (conformar equipos de trabajo, producción, etc). El siguiente artículo aborda el problema que enfrenta una consultora que debe formar 2 equipos de expertos del área de operaciones en base a 8 ingenieros industriales. Estos 2 equipos los puede escoger de entre 5 equipos de profesionales que trabajan en la consultora. Los datos del problema se muestran en la siguiente tabla:

Cada equipo tiene que estar compuesto por al menos 3 y a lo más 5 expertos. Si el profesional j es asignado al equipo i, la compañía le debe pagar una remuneración rij. Si en la tabla aparece un guion (—), significa que el experto no puede ser asignado a ese equipo: por ejemplo, el profesional 3 no puede pertenecer al equipo 2 ni al 4. Se espera que el equipo i genere un ingreso di.

Se requiere formular y resolver computacionalmente un modelo de optimización que permita determinar la conformación de los equipos, alcanzando la utilidad máxima y cumpliendo las condiciones anteriormente expuestas. Definir claramente las variables de decisión, función objetivo y restricciones.

Variables de Decisión:

Función Objetivo:

Restricciones:

Sólo 2 equipos se seleccionan:

Cada equipo está formado solamente por entre 3 y 5 expertos:

A continuación se presenta un extracto de la implementación computacional del problema de conformación de equipos de trabajo con Solver. Notar que aquellas combinaciones infactibles en términos de asignación de ingenieros a equipos ha sido marcado con color rojo y en particular se le ha asignado un costo significativamente mayor en comparación a aquellas asignaciones factibles. De esta forma se espera que estos casos no sean seleccionados (por cierto también se puede seleccionar paso a paso sólo las celdas factibles al momento de definir las variables de decisión en Solver, omitiendo las situaciones infactibles).

La solución óptima consiste en seleccionar el equipo 1 y 5. En la tercera tabla (filas 16 a 21) se muestra la asignación de ingenieros a dichos equipos (por supuesto aquellos equipos que no se conforman, es decir, equipos 2, 3 y 4 no tienen ingenieros asignados). El equipo 1 se compone de los ingenieros 1, 3 y 4; por otra parte el equipo 5 se compone de los ingenieros 1, 3 y 10. Notar que no existe incentivo económico a conformar equipos con un mayor número de integrantes. Finalmente el valor óptimo (utilidad máxima) es de $16.550.

¿Quieres tener el archivo Excel con la resolución en Solver de este problema?. Recomiéndanos en Facebook, Google+ o Twitter utilizando la herramienta de redes sociales a continuación y accede de forma gratuita e inmediata a la descarga del archivo (el enlace de descarga con el nombre “Descarga el Archivo” se mostrará abajo una vez que nos hayas recomendado).

[l2g name=”Descarga el Archivo” id=”4545″]

Método de la Esquina Noroeste (Algoritmo de Transporte en Programación Lineal)

El Método de la Esquina Noroeste (o esquina superior izquierda) es una heurística que se aplica a una estructura especial de problemas de Programación Lineal llamada Modelo de Transporte, la cual permite asegurar que exista una solución básica factible inicial (no artificial). Otros métodos para la obtención de una solución básica de inicio son el Método de Costo Mínimo y Método de Aproximación de Vogel. En general, el Método de Vogel produce la mejor solución básica de inicio y el de la Esquina Noroeste la peor, sin embargo, el Método de la Esquina Noroeste implica el mínimo de cálculos.

El Método de la Esquina Noroeste comienza en la celda (ruta) correspondiente a la esquina noroeste, o superior izquierda, de la tabla (variable $x_{11}$ ). A continuación una descripción de los pasos:

Paso 1: Asignar todo lo posible a la celda seleccionada y ajustar las cantidades asociadas de oferta y demanda restando la cantidad asignada.

Paso 2: Salir de la fila o la columna cuando se alcance oferta o demanda cero, y tacharlo, para indicar que no se pueden hacer más asignaciones a esa fila o columna. Si una fila y una columna dan cero al mismo tiempo, tachar sólo uno (la fila o columna) y dejar una oferta (demanda) cero en la fila (columna) que no se tachó.

Paso 3: Si queda exactamente una fila o columna sin tachar, detenerse. En caso contrario, avanzar a la celda de la derecha si se acaba de tachar una columna, o a la de abajo si se tachó un reglón. Seguir con el Paso 1.

Método de la Esquina Noroeste

Para ilustrar la aplicación del Método de la Esquina Noroeste consideremos el siguiente problema balanceado de transporte que considera 3 silos productos (oferta) que satisfacen las necesidades de 4 molinos (demanda). El algoritmo de transporte se basa en la hipótesis que el modelo está balanceado, es decir, que la demanda total es igual a la oferta total (si el modelo no está balanceado siempre se podrá aumentar con una fuente ficticia o un destino ficticio para restaurar el equilibrio o balance).

Los costos unitarios de transporte desde el silo i al molino j $c_{ij}$ se representan en la esquina superior derecha de cada cuadro. Por ejemplo el costo unitario de enviar una unidad de producto desde el silo 1 al molino 1 es de $10. Adicionalmente los silos 1, 2 y 3 tienen capacidad u oferta de 15, 25 y 10 unidades, respectivamente. Por otra parte los molinos 1, 2, 3 y 4 tienen requerimientos o demanda de 5, 15, 15 y 15 unidades, respectivamente. El modelo esta balanceado (suma oferta = suma demanda = 50 unidades).

Al aplicar el Método de la Esquina Noroeste al ejemplo anterior se obtienen los siguientes resultados. Las flechas indican el orden en el que se generan las cantidades asignadas:

La cantidad asignada a la celda $x_{11}$ son 5 unidades, dado que si bien el silo 1 tiene capacidad de 15 unidades, el molino 1 sólo necesita (demanda) 5 unidades (no se realizan más asignaciones a la columna 1 correspondiente al molino 1).
A continuación nos movemos a la derecha y asignamos lo máximo posible (10 unidades remanentes) a la celda $x_{12}$ (con lo cual se completa la capacidad del silo 1 y en consecuencia no es posible seguir realizando asignaciones en la fila 1).
Luego asignamos 5 unidades a la celda $x_{22}$ lo cual es por cierto menor que la capacidad del silo 2 pero lo suficiente para satisfacer los requerimientos del molino 2 (ahora no es posible generar asignaciones adicionales a la columna 2).
Nos movemos a la derecha y se asignan 15 unidades del silo 2 al molino 3 ( $x_{23}=15$ ) lo que cubre inmediatamente los requerimientos del molino 3 (no es necesario asignar más en la columna 3).
Nuevamente nos movemos a la derecha y asignamos lo máximo posible (5 unidades que es la capacidad remanente del silo 2, es decir, $x_{24}=5$ ) con lo cual el silo 2 opera a máxima capacidad (ahora ya no es posible nuevas asignaciones en la fila 2).
Finalmente se asignan 10 unidades del silo 3 al molino 4 ( $x_{34}=10$ ) cubriendo la demanda de dicho molino (y la capacidad del correspondiente silo).

En consecuencia la solución básica factible inicial es: $x_{11}=5, x_{12}=10, x_{22}=5, x_{23}=15, x_{24}=5, x_{34}=10$ que reporta un costo del programa (valor en la función objetivo) de: Z=5(10)+10(2)+5(7)+15*(9)+5(20)+10*(18)=$520. Notar que si se implementa computacionalmente el problema anterior haciendo uso de Solver de Excel y utilizando como motor de resolución Simplex_LP se alcanza la siguiente solución óptima (celdas amarillas) con costo mínimo (valor óptimo) de $435.

Problema de Planificación Financiera en Programación Lineal resuelto con Solver

El siguiente artículo trata de un problema de planificación financiera el cual se aborda a través de la Programación Lineal y se resuelve computacionalmente haciendo uso del complemento Solver de Excel. En este contexto se presenta un problema de inversión en distintos instrumentos financieros en los cuales se planifica invertir al inicio de cada uno de los próximos 10 años (horizonte de planificación), considerando los siguientes montos disponibles al comienzo de cada año (independiente de los retornos obtenidos producto de las mismas inversiones en años anteriores).

Los instrumentos disponibles son:

Depósito a plazo (anuales) con un retorno de 4,5% anual.
Bono a 6 años plazo con retorno de 4,9% anual.
Bono a 9 años plazo con retorno de 5,2% anual.

Se busca formular un modelo de optimización que posea los mayores retornos al término del décimo año (o inicio del año 11). Para ello se propone el siguiente problema de Programación Lineal:

Problema de Planificación Financiera

Variables de Decisión: Se establecen las posibilidades de inversión en los distintos instrumentos financieros. Notar que dado el período de maduración de los mismos se define la factibilidad de invertir en ellos en cada uno de los años. Por ejemplo, como el depósito anual tiene una maduración de un año se puede invertir en él en cada uno de los años del período de planificación. No así, por ejemplo, con el Bono a 9 años plazo el cual se puede invertir sólo al inicio del año 1 y 2.

Función Objetivo: Se desea maximizar el dinero obtenido al finalizar el período de planificación correspondiente al término del año 10 (o inicio del año 11).

Restricciones: Para cada año se limita las posibilidades de inversión según los instrumentos disponibles, el presupuesto del período y el retorno de los instrumentos que ya maduraron. Por ejemplo, en el año 1 se puede invertir en cada una de las 3 alternativas respetando el presupuesto de MM$20. En el año 2 nuevamente se puede invertir en las 3 alternativas y el presupuesto disponible corresponderá a los MM$20 de dicho período (según se detalla en la tabla al inicio) y eventualmente se podrá hacer uso del retorno de la inversión del depósito anual realizado en el año 1. Si, por ejemplo, se invierte los MM$20 en el depósito anual a inicio del año 1, entonces el presupuesto disponible para el año 2 será: 20+1,045(20)=MM$40,9.

A continuación se presenta un extracto de los resultados que provee la implementación computacional del modelo anterior haciendo uso de Solver. Las celdas color amarillo corresponde a la solución óptima, alcanzando un valor óptimo de MM$402,64.

Es interesante analizar la estructura de la solución óptima alcanzada. En el año 1 y 2 se invierte la totalidad del presupuesto en el Bono a 9 años plazo; en los años 3, 4 y 5 se invierte de forma exclusiva en los bonos a 6 años plazo; finalmente del año 5 al año 10 se invierte en el depósito anual.

¿Quieres tener el archivo Excel con la resolución en Solver de este problema?. Recomiéndanos en Facebook, Google o Twitter utilizando la herramienta de redes sociales a continuación y accede de forma gratuita e inmediata a la descarga del archivo (el enlace de descarga con el nombre “Descarga el Archivo” se mostrará abajo una vez que nos hayas recomendado).

[l2g name=”Descarga el Archivo” id=”4694″]

Planificación del Arriendo de una Bodega a través de la Programación Lineal

Las bodegas enfrentan requerimientos variables de almacenamiento de un mes a otro. Esto se explica entre otros factores por la estacionalidad y variabilidad de la demanda, cambio en los niveles de producción, retraso en el despacho de los productos, políticas de la empresa, etc. En la actualidad es común que las empresas externalicen la totalidad o parte del servicio de almacenamiento (bodegas) de modo que se utilizan instalaciones de un tercero para guardar productos de inventario. Una decisión relevante en este contexto es determinar cuánto espacio arrendar y por cuánto tiempo, de modo de satisfacer las necesidades de almacenamiento a un costo mínimo.

El siguiente ejemplo toma en cuenta esta situación y propone una política óptima de arriendo de espacio en bodega para una empresa para los próximos 5 meses. Se conoce cuanto espacio necesita en cada uno los próximos meses. Dado que los requerimientos son muy diferentes, podría resultar económico arrendar sólo lo necesario en cada mes de acuerdo a los requerimientos dados. Sin embargo, el costo total para arrendar de una vez por varios periodos consecutivos es más económico que hacerlo mes a mes sobre el mismo lapso de periodos, por lo tanto puede considerarse la opción de ir cambiando en el tiempo la cantidad de superficie arrendada al menos una vez pero no todo los meses, agregando nuevos periodos de arriendo y/o dejando los que expiraron su periodo. Los requerimientos (en miles de m²) y el costo total de arrendar en cualquier mes por periodos de uno, dos, tres, cuatro o cinco meses consecutivos (en $ por m²), se resumen en la siguiente tabla:

Formule y resuelva con Solver un modelo de Programación Lineal que minimice el costo total de arriendo, de modo de satisfacer los requerimientos por espacio en los próximos 5 meses.

Variables de Decisión:

Función Objetivo: Minimizar los costos asociado al arriendo de la bodega durante el período de planificación de 5 meses.

Restricciones:

Por ejemplo los requerimientos de 30 mil m² del primer mes (restricción 1) se pueden satisfacer con arriendos que se gestionan en el mes 1 por una duración de 1, 2, 3, 4 o 5 meses. Análogamente las necesidades del mes 2 (20 mil m²) se pueden enfrentar con arriendos planificados anteriormente (mes 1) con una duración de 2, 3 o 4 meses (notar que no tiene sentido arrendar por 5 meses en el mes 2) como también con arriendos gestionados en dicho período por 1, 2, 3 o 4 meses (se propone al lector seguir dicho razonamiento de modo de corroborar que las restantes restricciones son correctas).

A continuación se muestra un extracto de la resolución computacional del problema anterior haciendo uso de Solver de Excel:

La solución óptima consiste en arrendar 30 m² en el mes 1 por un total de 5 meses, luego en el mes 3 se arriendan 10 m² adicionales por sólo un período, para finalmente en el mes 5 arrendar 20 m² por un mes. De esta forma se satisfacen los requerimientos de espacio en bodega para cada mes del horizonte de planificación a un costo mínimo de $76.500 (valor óptimo).

¿Quieres tener el archivo Excel con la resolución en Solver de este problema?. Recomiéndanos en Facebook, Google+ o Twitter utilizando la herramienta de redes sociales a continuación y accede de forma gratuita e inmediata a la descarga del archivo (el enlace de descarga con el nombre “Descarga el Archivo” se mostrará abajo una vez que nos hayas recomendado).

[l2g name=”Descarga el Archivo” id=”4562″]

Cómo determinar la Duración Óptima de un Proyecto a través del Análisis de Crashing

La Programación Lineal como hemos analizado anteriormente provee una forma eficiente para enfrentar el problema de cómo reducir la duración de un proyecto de la forma más económica posible (Análisis de Crashing) en el contexto de la aplicación del Método de Ruta Crítica (CPM) para la gestión de proyectos. Adicionalmente en algunas situaciones se suele enfrentar costos de penalización en la medida que el proyecto se entregue más tarde de lo comprometido o estimado, como también incentivos por entregas anticipadas que no vayan en desmedro de la calidad del proyecto.

Consideremos el siguiente ejemplo para el cálculo de la Duración Óptima de un Proyecto (el tiempo está medido en días y el costo en dólares):

Por ejemplo la Actividad F tiene una duración normal de 4 días a un costo de 600 dólares y se puede comenzar una vez terminadas las Actividades B y E (predecesores). Si se desea apurar (hacer “crash”) en la Actividad F, el menor tiempo que se puede adoptar es de 2 días (es decir, la reducción máxima es 2 días), donde por cada día que se reduce la duración de dicha actividad se incurre en un costo adicional de 175 dólares. De esta forma, por ejemplo, si se quisiera reducir la duración de la Actividad F de 4 a 3 días, el costo sería de 775 dólares (600+175).

Asuma que la fecha de entrega del proyecto es el día 10. La compañía debe pagar 170 dólares por cada día de atraso. Encuentre el número óptimo de días que debe durar el proyecto a través del análisis de crashing y el costo total del proyecto (incluyendo posibles multas por atraso).

Indique claramente las actividades donde realice crashing. Dibuje el diagrama del proyecto de la alternativa que se propone (el proyecto con el costo más bajo), representando el nombre de cada actividad al interior de los respectivos nodos. Para cada actividad calcule los siguientes indicadores: IC, TC, IL, TL. Luego obtenga explícitamente la holgura de cada actividad y la(s) ruta(s) crítica(s) del proyecto.

A continuación se define un modelo de optimización lineal propuesto para abordar el problema:

Variables de Decisión:

Parámetros:

Función Objetivo: Consiste en minimizar el costo de terminar el proyecto en K días, donde 3.175 corresponde al costo en dólares de desarrollar el proyecto con las actividades en tiempo normal y la expresión en la sumatoria es el costo incremental de disminuir la duración del proyecto.

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:

Definición del tiempo objetivo para el proyecto:

No negatividad de las variables de decisión:

Una vez definido el modelo de Programación Lineal se implementa computacionalmente haciendo uso de Solver de Excel. Para ello será necesario sensibilizar los resultados del modelo para valores del parámetro K en el intervalo de [10,15] días (el lector puede corroborar que la duración del proyecto si cada actividad mantiene su duración normal es de 15 días). La solución óptima se resume a continuación:

El tiempo óptimo para completar el proyecto corresponde a 12 días, con un costo total (incurriendo multas por atraso) de 3.890 dólares. El gráfico a continuación muestra el valor de la función objetivo (costo total) para distintos valores de duración del proyecto.

A continuación desarrollamos el diagrama del proyecto donde se observa que existen 2 rutas críticas: A-B-F y A-C-E-F, con una duración de 12 días. Notar que la única actividad que no es crítica con holgura positiva (de 1 día) es la Actividad D.

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

[sociallocker]Crashing Óptimo[/sociallocker]