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

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″]

Problema de la Mochila en Programación Entera resuelto con OpenSolver

El Problema de la Mochila (conocido también como Knapsack Problem o simplemente KP) es un problema clásico de la Investigación de Operaciones y en particular de la Programación Entera. Consiste en un excursionista que debe preparar su mochila, la cual tiene una capacidad limitada y por tanto no le permite llevar todos los artículos que quisiera tener en la excursión. Cada artículo que el excursionista puede incluir en la mochila le reporta una determinada utilidad. Luego el problema consiste en seleccionar un subconjunto de objetos de forma tal que se maximice la utilidad que el excursionista obtiene, pero sin sobrepasar la capacidad de acarrear objetos.

En este contexto existen varias aplicaciones que guardan una similitud conceptual con el Problema de la Mochila y en consecuencia nos podemos beneficiar de la formulación y resolución de un modelo de optimización matemática para dicho propósito. Consideremos el siguiente ejemplo:

Problema de la Mochila

Un armador tiene un carguero con capacidad de hasta 700 toneladas. El carguero transporta contenedores de diferentes pesos para una determinada ruta. En la ruta actual el carguero puede transportar algunos de los siguientes contenedores:

El analista de la empresa del armador desea determinar el envío (conjunto de contenedores) que maximiza la carga transportada. Para ello se propone el siguiente modelo de Programación Entera:

Variables de Decisión:

Función Objetivo: Consiste en maximizar la carga que transportará el carguero.

Restricciones: El peso de la carga transportada no puede exceder la capacidad máxima del carguero.

Al implementar computacionalmente el problema anterior haciendo uso de OpenSolver se alcanzan los siguientes resultados:

La solución óptima consiste en transportar los contenedores C1, C2, C3, C4, C8, C9 y C10, con un valor óptimo de 700 (toneladas), es decir, se utiliza la capacidad completa del carguero. Notar que otra solución óptima consiste en transportar los contenedores C1, C3, C4, C5, C6, C7, C8 y C9 lo que reporta un similar valor en la función objetivo.

¿Quieres tener el archivo Excel con la resolución en OpenSolver 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 Mochila[/sociallocker]

Problema de Selección de Cartera de Proyectos a través de la Programación Entera

La Programación Entera provee una forma eficiente de enfrentar los problemas de selección de proyectos a ejecutar dentro de una cartera de potenciales proyectos a realizar, donde cada uno de éstos tiene asociado un tiempo de ejecución, requerimientos de fondos de inversión y necesidades adicionales. El siguiente artículo aborda la formulación de un modelo de optimización de Programación Entera que permita seleccionar los proyectos a realizar que maximice el Valor Presente Neto (VPN) del conjunto, respetando restricciones presupuestarias, políticas de inversión y de disponibilidad de personal.

Problema de Selección de Cartera de Proyectos

Consideremos una empresa que tiene en carpeta 8 proyectos, cada uno de los cuales con una estimación del VPN, la necesidad de financiamiento (en dólares) y los requerimientos de personal. La información se resume en la siguiente tabla:

Por ejemplo, el Proyecto 1 requiere de 120 profesionales para ser realizado, con una inversión inicial de 15 millones de dólares y representa un Valor Presente Neto (VPN) de 8 millones de dólares. Asumiremos que la empresa dispone de 155 profesionales, un presupuesto para inversión de 40 millones de dólares. Adicionalmente para efectos de minimizar el riesgo la empresa debe ejecutar al menos 4 proyectos. Los proyectos 3 y 6 son excluyentes, es decir, sólo uno de los 2 puede ejecutarse.

Variables de Decisión:

Probablemente el lector se pregunte si es equivalente definir Xi: dólares a invertir en el Proyecto i. El problema subyacente a dicha formulación es asumir que si, por ejemplo, se invierte 7,5 millones de dólares en el Proyecto 1 se obtiene un VPN de 4 millones de dólares, es decir, que el VPN es proporcional al dinero invertido. Recordar que la proporcionalidad es un supuesto básico de la Programación Lineal donde claramente no provee una forma realista de representación en este caso, donde la naturaleza de la decisión es realizar o no un proyecto, sin dejar espacio para decisiones «intermedias».

Función Objetivo:

Consiste en maximizar la sumatoria del Valor Presente Neto de los proyectos (en millones de dólares). En este contexto el valor óptimo corresponderá a la suma del VPN de aquellos proyectos que finalmente se llevaran a cabo.

Restricciones:

Se debe respetar la disponibilidad de trabajadores:

La inversión total no puede superar el presupuesto disponible:

Al menos se deben realizar 4 proyectos para efectos de diversificación del riesgo:

Los proyectos 3 y 6 son excluyentes:

Luego de implementar computacionalmente el problema anterior con Solver se alcanza los siguientes resultados:

La solución óptima consiste en desarrollar los proyectos 2, 4, 5, 6 y 7 lo que reporta un VPN de 10,7 millones de dólares (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=»4355″]

Ejemplo del Problema del Flujo Máximo en Programación Entera resuelto con Solver

Este tipo de problemas (Problema del Flujo Máximo) es similar al Problema de Ruta más Corta, pero ahora se busca determinar el flujo máximo entre un nodo fuente y un nodo destino, los que están enlazados a través de una red, con arcos con capacidad finita, tal como se presenta en la siguiente figura. Notar que los números asignados a cada uno de los arcos representan los flujos máximos o capacidades correspondientes a cada arco.

Problema del Flujo Máximo

Desde el punto de vista de la Programación Entera podemos plantear la situación de la siguiente forma:

Variables de Decisión:

Función Objetivo: Maximizar las unidades que salen del nodo de origen (1) a los que éste conecta (2, 4 y 5) o alternativamente maximizar las unidades que llegan al nodo de destino (8) desde los que conectan a él (3, 6 y 7).

Restricciones:

Restricciones de Flujo Máximo: La cantidad de unidades que sale de cada nodo de origen a un nodo de destino no puede superar la capacidad detallada en el arco, por ejemplo, del nodo 1 al nodo 2 sólo se pueden enviar 7 unidades.

Restricciones de Balance de Flujo en los Nodos: Debe existir un equilibrio entre la cantidad de unidades que llega a un nodo y las que de éste salen, por ejemplo el número de unidades que se envía desde el nodo 1 al 4 (si es que así fuese el caso) debe ser igual a lo que desde el nodo 4 se envían al nodo 3 y 6.

No Negatividad e Integralidad: Las variables de decisión de decisión deben cumplir las condiciones de no negatividad. Adicionalmente exigiremos que éstas adopten valores enteros aún cuando se podría flexibilizar dicha situación lo que daría origen a un problema de Programación Lineal.

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

Notar que el flujo máximo de unidades que puede llegar al nodo de destino son 32 unidades (valor óptimo) donde cualquiera de las funciones objetivos propuestas proporciona el mismo resultado (en particular hemos utilizado la primera de ellas). Los valores de las celdas en color amarillo representan la solución óptima, es decir, la cantidad de unidades que fluyen en cada combinación de un nodo origen destino.

En el siguiente tutorial de nuestro canal de Youtube se detalla la implementación computacional que permite alcanzar los resultados anteriormente expuestos:

¿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=»4352″]

Problema de Corte Ensamblado y Producción de Sillas resuelto con Solver

Una empresa de Rústicos “El Viejo Baúl” fabrica entre muchos otros productos tres tipos de sillas A, B y C, las cuales se venden a precio de 11, 13 y 12 dólares cada una y respectivamente. Las sillas pasan por tres procesos, Corte, Ensamblado y Pintado, para lo cual se dispone máximo de 17, 13 y 15 horas respectivamente a la semana para dedicar a estas operaciones a estos productos. La silla tipo A requiere 3 horas para corte, 1 hora para ensamblado y 3 horas para pintura. La silla tipo B requiere 1 hora para corte, 4 horas para ensamblado y 3 horas para pintura. Y finalmente la silla tipo C, requiere de 5 horas para corte, 2 para ensamblado y 2 horas para pintura. De acuerdo a la anterior información:

a. Resuelva el problema con variables continuas y señale los resultados para cada variable.

Variables de Decisión: Se estable el nivel de producción semanal para cada una de las variedades de silla según se detalla a continuación:

Función Objetivo: Maximizar los ingresos semanales asociados a la producción y venta de las sillas.

Restricciones: En los procesos de corte, ensamblado y pintura se debe respetar la disponibilidad de horas semanales. Adicionalmente se deben satisfacer las condiciones de no negatividad.

La implementación computacional del problema anterior con Solver de Excel permite alcanzar los siguientes resultados:

Donde la solución óptima es A=1,914286, B=1,828571 y C=1,885714 con valor óptimo V(P)=67,45714.

b. Modifique las condiciones de las variables y elíjalas enteras (integer) y observe el cambio entre la respuesta del punto a y esta nueva hallada.

Al definir las variables de decisión enteras estamos frente a un modelo de Programación Entera (siendo el escenario inicial un problema de Programación Lineal). Los resultados son:

La solución óptima es A=1, B=2 y C=2 con valor óptimo V(PE)=61.

c. Concluya qué sucedió entre variables continuas y variables enteras.

Es importante observar que el dominio de soluciones factibles del problema entero (parte b) es un subconjunto del dominio de soluciones factibles del problema lineal (parte a). Por tanto es natural que al no obtener una solución con valores enteros para las variables de decisión en el problema inicial, el valor óptimo necesariamente disminuirá en la variante entera de dicho problema de maximización (V(PE)<V(P)). También se puede destacar que la solución entera no necesariamente se alcanza al aproximar los resultados fraccionarios de una solución de un problema lineal al entero inferior o superior más cercano. En consecuencia, para abordar de forma eficiente la resolución de un modelo que considere valores enteros para las variables de decisión requiere de una alternativa algorítmica específica como por ejemplo el Método Branch and Bound.

A continuación encontrarás un enlace de descarga del archivo Excel utilizado para la resolución del problema de corte, ensamblado y producción de sillas. En el archivo se incluyen 2 hojas que corresponden a la parte a) y b) del problema propuesto. Produccion de Sillas.