Problema de la mochila
[1] Ha sido intensamente estudiado desde mediados del siglo XX y se hace referencia a él en el año 1897, en un artículo de George Mathews Ballard.
[2] Si bien la formulación del problema es sencilla, su resolución es más compleja.
Algunos algoritmos existentes pueden resolverlo en la práctica para casos de un gran tamaño.
A continuación se define formalmente el problema.
distintos tipos de ítems, que van del 1 al
Cada tipo de ítem i tiene un beneficio asociado dado por vi y un peso (o volumen) wi.
Para simplificar la representación, se suele asumir que los ítems están listados en orden creciente según el peso (o volumen).
Por otro lado se tiene una mochila, donde se pueden introducir los ítems, que soporta un peso máximo (o volumen máximo) W. El problema consiste en meter en la mochila ítems de tal forma que se maximice el valor de los ítems que contiene y siempre que no se supere el peso (o volumen) máximo que puede soportar la misma.
El problema se puede expresar matemáticamente por medio del siguiente programa lineal: Si
es infinito entonces se dice que se trata del problema de la mochila no acotado también llamado a veces problema de la mochila entera.
En otro caso se dice que se trata del problema de la mochila acotado Observar que en un problema de la mochila 0-1, si para cada tipo de ítem el beneficio y los pesos son idénticos (vi=wi), entonces el problema quedaría formulado de la siguiente forma Por tanto si existe un vector xi tal que
Este problema se ha resuelto tradicionalmente mediante programación lineal entera.
El hecho de que se trate de programación lineal hace referencia a que la función a optimizar y las inecuaciones que constituyen las restricciones han de ser lineales, es decir, han de ser funciones cuyas incógnitas estén elevadas exclusivamente a la unidad.
Una aproximación voraz consiste en que cada elemento a considerar se evalúa una única vez, siendo descartado o seleccionado, de tal forma que si es seleccionado forma parte de la solución, y si es descartado, no forma parte de la solución ni volverá a ser considerado para la misma.
Con este método no siempre es posible dar una solución a un problema.
b) Concepto de solución óptima: Teorema: si se ordenan los objetos de forma decreciente en cuanto a su relación (utilidad/ponderación = bi/ci), y se introducen en la mochila enteros en este orden mientras quepan, y cuando no quede capacidad para uno entero se añade la porción que aún tenga cabida, el resultado al que se llega es una solución óptima.
Consisten en métodos adaptativos de optimización que tratan de hallar (xi,...,xn) tales que [Sumatoria (bi*xi) desde i= 1 hasta n] sea máximo.
Pueden usarse para resolver problemas de búsqueda y optimización.
