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.
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).
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).
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.
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.
