Problema de la mochila | Knapsack Problem | Programación lineal

Alexagre Ingeniería

9 Sept 202305:35

Summary

TLDREn este vídeo se aborda el problema de la mochila, un problema de programación lineal donde se debe maximizar el beneficio de los artículos a llevar en un viaje. Se presenta el caso de Janet, quien debe seleccionar artículos para un campamento y cuya capacidad de maletín es limitada. Se utiliza un enfoque binario para decidir qué llevar y se programa en Excel con el Solver para encontrar la solución que maximiza el beneficio sin exceder el espacio disponible. Al final, se determina qué artículos son esenciales y se ofrece una solución óptima que permite a Janet planificar su equipaje eficientemente.

Takeaways

🏕️ Janet quiere llevar ciertos artículos para acampar, pero no caben todos en su maletín.
📚 Los artículos incluyen un libro, elementos de aseo, un reloj, una navaja suiza, un peluche, un juego portátil, un encendedor, alimentos, cubiertos, un abrelatas, un celular y ropa.
📏 El maletín tiene un espacio limitado de 30 unidades, por lo que debe elegir los artículos que más beneficios le proporcionen.
🔢 Janet asigna un valor de beneficio a cada artículo, dependiendo de la utilidad que le brindan durante su campamento.
✏️ El problema se plantea como un caso de programación lineal, donde la función objetivo es maximizar el beneficio total.
📊 Cada artículo tiene un espacio determinado, y la suma de estos no debe superar las 30 unidades disponibles en el maletín.
⚖️ Las variables de decisión son binarias: toman el valor de 1 si el artículo se elige y 0 si no se elige.
🖥️ Se usa Excel y el Solver para programar la función objetivo y las restricciones de espacio, ajustando las celdas correspondientes.
✅ Solver encuentra la solución óptima, sugiriendo que Janet debe llevar los elementos de aseo, el juego portátil, cubiertos, el libro, el celular, el encendedor y la navaja.
🎯 El beneficio máximo obtenido es de 57, cumpliendo con la restricción de espacio sin incluir alimentos, lo cual puede indicar que Janet buscaría alternativas como cazar.

Q & A

¿Qué problema se estudia en el guion del video?
-Se estudia el problema de la mochila, que es un problema de programación combinatoria donde se debe maximizar el beneficio de los artículos a llevar dentro de un límite de capacidad.
¿Quién es la persona principal en el guion del video?
-La persona principal en el guion es Janet, quien desea ir a un bosque en una montaña y necesita elegir qué artículos llevar en su maletín.
¿Cuál es el límite de capacidad del maletín de Janet?
-El límite de capacidad del maletín de Janet es de 30 unidades de espacio, que pueden ser litros o decímetros cúbicos.
¿Cuál es el objetivo de Janet al elegir los artículos para su campamento?
-El objetivo de Janet es maximizar el beneficio de los artículos que lleva al campamento, teniendo en cuenta el espacio limitado de su maletín.
¿Cómo determina Janet el beneficio de cada artículo?
-Janet determina el beneficio de cada artículo de acuerdo a lo que le proporciona en su campamento, asignando un valor numérico a cada uno.
¿Cuál es la función objetivo en el problema de la mochila descrito en el guion?
-La función objetivo es maximizar Z, que representa el beneficio total de los artículos seleccionados para llevar al campamento.
¿Qué restricciones se tienen en cuenta en el problema de la mochila?
-Las restricciones son que el espacio total ocupado por los artículos en el maletín debe ser menor o igual a 30 unidades y que las variables de decisión son binarias (1 si se lleva el artículo, 0 si no).
¿Cómo se programa la función objetivo en Excel según el guion?
-Se programa la función objetivo en Excel como una suma producto entre la columna de beneficio y la columna de decisión, lo que representa el beneficio total de los artículos seleccionados.
¿Cómo se implementa la restricción de espacio en Excel?
-Se implementa la restricción de espacio en Excel mediante una fórmula que suma el producto del espacio ocupado por cada artículo y su decisión de llevarlo, asegurándose de que el resultado no exceda los 30 unidades de capacidad.
¿Qué solución encontró el solver en Excel para el problema de la mochila?
-El solver encontró una solución que maximiza el beneficio en 57 unidades, eligiendo artículos como los elementos de aseo, el videojuego portátil, los cubiertos, el libro, el celular, el encendedor y la navaja, sin exceder el límite de capacidad del maletín.
¿Qué artículo importante no se incluyó en la solución final y por qué podría ser relevante?
-El artículo de alimentos no se incluyó en la solución final. Aunque no se menciona explícitamente en el guion, es relevante porque generalmente los alimentos son esenciales para cualquier campamento.