EL PROBLEMA DE LA MOCHILA.
El problema de la mochila es un tipo particular de programación entera con sólo una restricción. Cada artículo que puede ir en la mochila tiene un tamaño y un beneficio asociado. La mochila tiene una capacidad máxima. ¿Qué se debe llevar en la mochila para maximizar el beneficio total? A modo de ejemplo supongamos que hay tres artículos como se muestra en la Tabla 3, y suponga que la capacidad de la mochila es 5.
Sea mochila(k,l,P) el problema:
– El problema de la mochila 0-1 es mochila(1,n,C).
Principio de optimalidad:
Sea y1,…,yn una secuencia óptima de valores 0-1
para x1,…,xn.
– Si y1=0, entonces y2,…,yn forman una secuencia
óptima para el problema mochila(2,n,C).
– Si y1=1, entonces y2,…,yn forman una secuencia
óptima para el problema mochila(2,n,C-p1).
Demostración: Si existe una solución mejor
para el problema correspondiente,
entonces es mejor
que para el problema mochila(1,n,C),
en contra de la
hipótesis.
Problema de la mochila
En algoritmia, el problema de la mochila, comúnmente abreviado por KP (del inglés Knapsack problem) es un problema de optimización combinatoria, es decir, que busca la mejor solución entre un conjunto finito de posibles soluciones a un problema. 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.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. 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 de operaciones.
Problema de la Mochila
Un armador tiene un carguero con capacidad de hasta 700 toneladas. El carguero transporta contenedores de diferentes pesos para una determinada ruta. En la ruta actual el carguero puede transportar algunos de los siguientes contenedores:
El analista de la empresa del armador desea determinar el envío (conjunto de contenedores) que maximiza la carga transportada. Para ello se propone el siguiente modelo de Programación Entera:
Variables de Decisión:
Función Objetivo: Consiste en maximizar la carga que transportará el carguero.
Restricciones: El peso de la carga transportada no puede exceder la capacidad máxima del carguero.
Al implementar computacionalmente el problema anterior haciendo uso de OpenSolver se alcanzan los siguientes resultados:
La solución óptima consiste en transportar los contenedores C1, C2, C3, C4, C8, C9 y C10, con un valor óptimo de 700 (toneladas), es decir, se utiliza la capacidad completa del carguero. Notar que otra solución óptima consiste en transportar los contenedores C1, C3, C4, C5, C6, C7, C8 y C9 lo que reporta un similar valor en la función objetivo.
Comentarios
Publicar un comentario