Variante del Problema de la Mochila: Maximizando Peso y Valor hasta el Límite.
Estoy tratando de desarrollar un algoritmo (probablemente utilizando OR Tools en Python) para resolver un problema que parece estar relacionado con el problema de la mochila.
- Tengo un conjunto de elementos en la Ubicación A
- Quiero llevarlos a la Ubicación B
- Cada elemento tiene un peso y un valor
- Solo puedo llevar una cantidad X de peso
- Tengo miedo de que me roben en el camino, así que solo quiero llevar hasta una cantidad Y de valor
Si estoy tratando de planear mi primer viaje desde la Ubicación A a la Ubicación B, ¿cómo puedo seleccionar los elementos de tal manera que:
– Maximice el peso que se carga, hasta un límite de X (minimice la capacidad de peso desperdiciada)
– Maximice el valor que se carga, hasta un límite de Y (minimice la capacidad de valor desperdiciada)
Un ejemplo ficticio:
– Mis límites son 5kg y $50
– Tengo 10 de Item C (peso: 0.1kg, valor: $10)
– Tengo 10 de Item D (peso: 1kg, valor: $1)
La solución “fácil” es hacer 4 viajes:
– 5x Item C ($50, 0.5kg)
– 5x Item C ($50, 0.5kg)
– 5x Item D ($5, 5kg)
– 5x Item D ($5, 5kg)
Pero la solución más inteligente es hacer solo 3 viajes:
– 4x Item C + 4x Item D ($44, 4.4kg)
– 4x Item C + 4x Item D ($44, 4.4kg)
– 2x Item C + 2x Item D ($22, 2.2kg)
He trabajado con el solucionador lineal de OR Tools, pero solo maximizando un valor teniendo múltiples restricciones. ¿Cómo puedo maximizar múltiples valores (peso cargado y valor cargado) con múltiples restricciones?
davy.ai
Para resolver este problema, puedes utilizar la formulación del Problema de la Mochila en OR-Tools con algunas modificaciones. En lugar de maximizar solo el valor, debes maximizar dos objetivos (peso y valor) sujetos a restricciones. Este es un problema de optimización multiobjetivo y se puede resolver utilizando el método de suma ponderada o el método de restricción-épsilon.
Para el método de suma ponderada, primero defines un peso para cada objetivo (por ejemplo, 0.5 para peso y 0.5 para valor). Luego, creas una nueva función objetivo como la suma de los objetivos ponderados. Añades dos restricciones lineales, una para el peso y otra para el valor, que limitan la suma del peso o valor de los elementos seleccionados para que sea menor o igual a X e Y, respectivamente. El último paso es llamar al solucionador para maximizar la nueva función objetivo sujeta a las dos restricciones.
Para el método de restricción-épsilon, primero eliges uno de los objetivos (por ejemplo, peso) y lo estableces como restricción. Luego, añades otra restricción que limita el otro objetivo (por ejemplo, valor) para que sea menor o igual a un cierto valor (por ejemplo, Y). Resuelves el problema para obtener la solución óptima para el primer objetivo sujeto a la segunda restricción. Luego, repites el proceso con el otro objetivo como restricción.
En general, resolver este problema implica crear una formulación de la Mochila con múltiples objetivos y restricciones, lo cual se puede implementar utilizando OR-Tools en Python.