Problema de la mochila

Ejemplo del problema de la mochila: dada una mochila con una capacidad de 15 kg que puedo llenar con cajas de distinto peso y valor, ¿qué cajas elijo de modo de maximizar mis ganancias y no exceder los 15 kg de peso permitidos?

En algoritmia, el problema de la mochila, comúnmente abreviado por KP (del inglés Knapsack problem) es un problema de optimización combinatoria. Modela una situación análoga al llenar una mochila, incapaz de soportar más de un peso determinado, con todo o parte de un conjunto de objetos, cada uno con un peso y valor específicos. Los objetos colocados en la mochila deben maximizar el valor total sin exceder el peso máximo.

Historia

El problema de la mochila es uno de los 21 problemas NP-completos de Richard Karp, establecidos por el informático teórico en un famoso artículo de 1972. 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.

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. Sin embargo, la estructura única del problema, y el hecho de que se presente como un subproblema de otros problemas más generales, lo convierten en un problema frecuente en la investigación.

Definición

Para esta sección, consideremos n tipos de ítemes, que van del 1 al n. Cada tipo de ítem i tiene un valor v_i y un peso w_i. Usualmente se asume que los valores y pesos no son negativos. Para simplificar la representación, se suele asumir que los ítemes están listados según su peso en orden creciente.

El peso máximo o capacidad soportada por la mochila es W.

La formulación más común del problema es la del llamado problema de la mochila 0-1, que restringe el número x_i de copias de cada tipo de ítemes a cero o uno. Matemáticamente, el problema queda formulado de la siguiente manera (como un problema de programación lineal):

• maximizar $\qquad \sum_{i=1}^n v_ix_i$
• tal que $\qquad \sum_{i=1}^n w_ix_i \leqslant W, \quad \quad x_i \in \{0,1\}$

El problema de la mochila acotado restringe el número $x_i$ de copias de cada tipo de ítem a un valor entero máximo $c_i$, quedando matemáticamente formulado como:

• maximizar $\qquad \sum_{i=1}^n v_ix_i$
• tal que $\qquad \sum_{i=1}^n w_ix_i \leqslant W, \quad \quad x_i \in \{0,1,\ldots,c_i\}$

El problema de la mochila no acotado, también conocido como UKP (del inglés unbounded knapsack problem) no considera cotas superiores para el número de copias de cada tipo de ítem.

Métodos de resolución

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.

Existe otra forma de resolver este tipo de problema, a través de los denominados algoritmos voraces. 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.

Ejemplo: si continuamos con el ejemplo de “Escribe bien S.A.” vemos que la solución intuitiva que aportamos se corresponde con el método de algoritmos voraces comentado en el párrafo anterior.

Si quisiéramos resolver el problema mediante programación lineal entera tendríamos que plantear el modelo, del mismo modo que hicimos con Costuritas S.L. al comentar cómo se expresa un problema que solucionar por este método.

Otro sistema para resolver el problema de la mochila es mediante algoritmos genéticos que son métodos de optimización que tratan de hallar (xi,...,xn) tales que sea máximo.

Algoritmos voraces

a) Aplicación del método:

Partimos de la formulación del problema de la mochila aportada anteriormente:

Maximizar [Sumatoria (bi*xi) desde i= 1 hasta n]

sujeto a: xi Є {0,1} con i =1,..., n

[Sumatoria (ci*xi) desde i=1 hasta n] < P

La utilización de un algoritmo voraz consiste en introducir en la mochila según orden decreciente de utilidad (beneficio) los diversos objetos. En una primera etapa, se adicionarán unidades enteras hasta que, por motivo de capacidad, no sea posible seguir introduciendo enteros y haya que añadir la porción que quepa del siguiente objeto.

b) Concepto de solución óptima:

Teorema: si se ordenan los objetos de forma de 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.

Algoritmos genéticos

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. Se basan en el proceso genético de los organismos vivos, por imitación de este proceso, los Algoritmos Genéticos son capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de una adecuada codificación de las mismas. Para utilizar un algoritmo genético hacen falta tres elementos:

Descripción de la población de individuos: cada individuo representa una solución factible a un problema dado. A cada individuo se le asigna un valor ó puntuación, relacionado con la bondad de dicha solución.

Función de evaluación (llamada función de ajuste): encontrar una expresión matemática que puntúe a cada individuo de forma que nuestro ideal sea un máximo o un mínimo.

Selección o Mecanismos de reproducción: la función de selección de padres más utilizada, es la denominada función de selección proporcional a la función objetivo, en la cual cada individuo tiene una probabilidad de ser seleccionado como padre que es proporcional al valor de su función objetivo, es decir, indica que cada objeto de la mochila tendrá una probabilidad de ser seleccionado que dependerá de la relación que exista entre beneficios y el peso que ocupa.