Todos hemos escuchado alguna vez la pregunta de: ¿Qué te llevarías a una isla desierta? Esta pregunta pasar por tener que elegir entre un numero determinado de ítems, que nos reporta un beneficio y que a la vez tienen un peso en nuestra “mochila”.
Si hay pocos ítems, la decisión puede ser sencilla. Sin embargo, cuando el número de opciones es elevado, hay numerosas combinaciones que pueden ser beneficiosas y que suponen costes – o pesos- similares. En este segundo caso, no es sencillo determinar cual de todas es la mejor combinación.
Este tipo de problema es conocido en investigación operativa como “El problema de la mochila” ó Knapsack.
Para visualizar, entender e incluso resolver este tipo de problemas, he desarrollado una aplicación que permite hacer configuraciones distintas del problema y resolverlo con distintas técnicas. Además, permite comparar entre los distintos algoritmos utilizados.
El siguiente paso sería conectarlo a una aplicación SCADA, para que puedan tomarse las decisiones de forma automatizada, ejecutando las acciones correspondientes en nuestros PLC.
Contenido
- Aplicación en la Industria
- Modelo matemático
- Problemática en la resolución
- Soluciones
- Aplicación práctica: PHS Knapsack
- Descargar el código
Aplicación en industria
En la industria, nos enfrentamos continuamente a problemas de decisión similares a este:
- Activación de líneas productivas con energía limitada: elegir que líneas activar sin superar los limites de consumo eléctrico.
- Selección de tareas de mantenimiento durante paradas técnicas: tiempo limitado.
- Gestión de las cargas de camiones: maximizando el valor transportado.
Modelo matemático
Este tipo de problemas se modelan de la siguiente forma:
Problemática en la resolución
A medida que aumenta el número de ítems, el número de combinaciones posibles crece de forma exponencial.
Esto hace que encontrar la solución exacta sea computacionalmente inviable en muchos casos.
En la práctica, es imposible evaluar todas las combinaciones cuando hay muchos elementos.
Por eso, se recurre a algoritmos aproximados que dan buenas soluciones en poco tiempo, aunque no sean perfectas.
Soluciones
Cuando el número de ítems es bajo o moderado, se puede usar una solución exacta. Pero cuando el problema crece, es necesario recurrir a métodos más eficientes.
1. Soluciones exactas
- Evalúan todas las combinaciones posibles para encontrar la mejor.
- Son fiables, pero lentas cuando hay muchos ítems.
- Se basan en técnicas como programación dinámica o ramificación y poda (branch and bound).
- OR-Tools de Google permite aplicar estas técnicas de forma eficiente en problemas pequeños o medianos.
2. Soluciones aproximadas (heurísticas)
- No garantizan la mejor solución, pero son rápidas y prácticas.
- Usan reglas simples para encontrar buenas combinaciones (ej: seleccionar ítems con mejor valor/peso).
- Muy útiles en sistemas industriales que requieren resultados en tiempo real.
3. Metaheurísticas
- Algoritmos más avanzados inspirados en la naturaleza (genéticos, recocido simulado, enjambre de partículas…).
- Ideales para problemas grandes y complejos con múltiples restricciones.
- Dan soluciones muy cercanas a la óptima con bajo coste computacional.
OR-Tools, la librería open source de Google, combina varias de estas técnicas y permite resolver el problema de la mochila tanto de forma exacta como aproximada, según el tamaño y la urgencia del problema.
Es ligera, rápida, y perfecta para integrarla con soluciones industriales en Python.
Aplicación práctica: PHS Knapsack
La aplicación desarrollada, trata de hacer visible la problemática de forma didáctica, así como presentar los distintos algoritmos (open source) que existen para solucionarla. Para ello, he desarrollado con Co-Pilot “Agent” en Visual Code, una aplicación en Streamlit que muestra todo esto.
La aplicación es muy sencilla, y básicamente lo que hacemos es determinar el número de Ítems que podemos echar en nuestra mochila, dándole beneficios, pesos aleatorios y con un peso máximo de la mochila. Con esto ejecutamos los distintos algoritmos y vemos como cada uno resuelve el problema, para entender las diferencias entre ellos.
Con la aplicación podemos:
- Modificar número de Ítems, beneficio y peso de los elementos.
- Seleccionar entre algoritmos distintos de resolución.
- Comparativa de los algoritmos utilizados.
Aquí un video con un ejemplo:
Descarga el código
El programa PHS Knapsack esta hecho con Streamlit y desarrollado en Visual Code. Os dejo por aquí el enlace al código fuente:
Una vez descargado y arrancado en Visual Code, debéis seguir los siguientes pasos:
2- Crear un entorno:
pyhton -m venv venv3- Activar el entorno
source venv/bin/activate4- Instalar requerimientos
pip install -r requirements.txt5- Ejecutar la aplicación
streamlit run app.pyAdemás os recomiendo encarecidamente, el uso de copilot Agent para continuar desarrollando la aplicación a vuestro gusto.