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.
La programación dinámica nos ayuda a optimizar los problemas sin verificar todos los casos posibles, pues van a aquellos que mejor lo resuelven, para el algoritmo de la mochila lo que queremos es llenarla con objetos que sea muy valiosos y de menor peso.
ejemplo: ingreso n: cantidad de objetos y Cap: capacidad máxima de la mochila
Los datos del problema se pueden expresar en términos matemáticos.
- Los objetos están numerados por el índice i variando de 1 a n.
- Los números wi y pi representan el peso y el valor del número i.
- La capacidad de la bolsa se denomina en esta formula W.
Existen muchas manera de llenar la mochila, para decidir a cada uno de ellos debemos de decir para cada objeto si lo metemos a la mochila o no, pudiendo utilizar el código binario que cuando xi = 1, metemos el objeto a la mochila, o xi = 0, se pone afuera, y para ir llenando esta mochila podemos utilizar un vector de contenido, que comprende: X = (x1, x2, ..., xn), entonces podemos expresar una función del contenido del vector.
Para un contenido dado X, el valor total de la bolsa es:
De la misma manera, la suma de los pesos de los objetos es:
El problema entonces lo podemos enunciar como un contenido de vectores X = (x1, x2, ..., xn), que tienen componentes de ceros y unos, teniendo como máximo la restricción de la función z(X).
Esto quiere decir que la suma de los pesos (o sea, la función w(X)), de los objetos que pusimos en la mochila no deben de superar la capacidad de esta, (o sea, la W).
Podemos decir que:
- z(X) es una función objetivo (como su nombre lo dice, representa el objetivo del problema, esta expresión se maximiza o se minimiza.
- Un vector X que cumple con la restricción W en la tercera formula se le nombra factible (o sea, que se pude hacer).
- Si tenemos un resultado máximo en z(X), entonces X es óptimo.
Se le pueden agregar otras restricciones según tengamos un caso, en esta liga, encontramos diferentes casos singulares.
Con esto podemos argumentar que tenemos un problema de decisión cuando para decidir a cada uno de ellos debemos de decir para cada objeto si lo metemos a la mochila o no, que cuando xi = 1, metemos el objeto a la mochila, o xi = 0, se pone afuera y podemos decir que es un problema de optimización porque podemos encontrar funciones objetivo, valores óptimos utilizando las declaraciones matemáticas.
El problema es NP-completo porque se puede representar como una toma de decisiones mediante el reemplazo del máximo, utilizando la siguiente pregunta:
Dado el número k, existe un valor xi para el cual
Existe un vinculo entre la version de decisión y la version de optimización del problema en que si existe un algoritmo polinomial que resuelve la versión de decisión, por lo tanto, las dos versiones del problema son de dificultad similar.
El problema de optimización es NP-hard, su resolución es al menos tan difícil como el problema de decisión.
La prueba de que el problema es NP-completo fue presentado por Michail G. Lagoudakis, se puede encontrar en la misma liga
Algoritmos existentes
Algoritmo Greddy o voraz: La idea es añadir un objeto prioritario mas efectivo hasta la saturación de la mochila. La complejidad de estos algoritmos se basa en la inversa de la calidad esperada.
 |
| Las dos fases del algoritmo voraz |
Podemos ver las dos fases del algoritmo voraz.
A) el ordenamiento de las cajas según un interes (en este caso en peso en $/kg)
B) si es posible la entrar a la mochila.
Algoritmo genético: se utiliza a menudo en problemas de optimización difíciles, como este, facil de implementar y obtener rapidamente una solución.
 |
| Ejemplo de la evolución de una población con un algoritmo genetico. |
Programación dinámica: El problema de la mochila tiene la propiedad que le permite utilizar el metodo de resolución de programación dinámica.
Este algoritmo tiene una complejidad en tiempo y espacio que tiene como ventajas la velocidad y no hay necesidad de ordenar las variables, pero como desventajas es que gasta mucha memoria, por lo tanto no puede ser solución para problemas grandes.
Aplicaciones en la vida real
En la vida real, se utiliza para modelar diferentes situaciones:
- en los sistemas de apoyo a las finanzas: para encontrar el mejor equilibrio entre el capital y rendimiento financiero.
- en la carga del barco o avión: todo el equipaje debe ser llevado, sin ser sobrecargado.
- en el corte de materiales: para minimizar las caídas.
- entre otras...
Referencias
Videos
https://youtu.be/ZGD7te3FntI
No hay comentarios.:
Publicar un comentario