• Author / Uploaded
• Javier Ayala

Citation preview

INDICE Introducción .................................................................................................................................. 1 1.

Historia del problema de la mochila...................................................................................... 2

2.

Definición del problema de la mochila ................................................................................. 3

3.

Casos en los que se presenta ................................................................................................. 5

4.

Métodos de resolución .......................................................................................................... 6 4.1.

Formulación Lineal ........................................................................................................ 6

4.2.

Aproximaciones ............................................................................................................. 7

4.2.1.

Aproximaciones a través de coeficiente de rendimiento ..................................... 7

4.2.2.

Evaluación de la heurística .................................................................................... 7

5.

Planteamiento del problema .................................................................................................. 7

6.

Aplicaciones a la sociedad .................................................................................................. 10

7.

Conclusiones ....................................................................................................................... 12

Bibliografía ................................................................................................................................. 13

UNIVERSIDAD NACIONAL DE SAN AGUSTÍN DE AREQUIPA

Introducción En el presente trabajo se van a detallar aspectos del modelo de volumen-carga, conocido también como el modelo de la “mochila” de programación dinámica, en el curso de Investigación de Operaciones II. Aspectos como su historia a través del tiempo, su introducción a los modelos de solución, definiciones, el método en sí y casos en los que se va a presentar la necesidad de utilizarlo, cómo se va a plantear el problema, entre otros. El problema de la mochila recoge una situación que se presenta con cierta frecuencia en los ámbitos económico e industrial, donde la mochila suele representar una restricción presupuestaria (cantidad máxima de recursos de los que se dispone) y donde la utilidad de los objetos seleccionados se equiparara a un beneficio económico por adquirir o llevar al cabo ciertas acciones. Así, dicho problema se presenta cuando debemos elegir qué objetos seleccionar de modo que nuestro beneficio sea lo mayor posible, es decir, el máximo sin exceder su capacidad.

1

UNIVERSIDAD NACIONAL DE SAN AGUSTÍN DE AREQUIPA

1. Historia del problema de la mochila 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. El problema de la mochila se ha estudiado durante varios siglos, con obras tempranas que datan de 1897, una de ellas es el artículo de George Mathews Ballard. No se sabe cómo se originó el nombre "problema de mochila", aunque el problema se mencionó como tal en los primeros trabajos del matemático Tobias Dantzig (1884–1956), lo que sugiere que el nombre pudo haber existido en el folclore antes de problema matemático había sido completamente definido. El problema de la mochila cuadrática fue introducido por primera vez por Gallo, Hammer y Simeone en 1960. Un estudio de 1998 del repositorio de algoritmos de la Universidad de Stony Brook mostró que, de los 75 problemas algorítmicos, el problema de la mochila era el 18º más popular y el 4º más necesario después de los kd-trees, los árboles de sufijos y el problema del empaquetado de contenedores. Un estudio de 1998 del Repositorio de Algoritmos de la Universidad de Stony Brook mostró que, de los 75 problemas algorítmicos, el problema de mochila era el 19 más popular y el tercero más necesario después de los árboles de sufijos y el problema de empaquetado de contenedores. Los problemas de mochilas aparecen en los procesos de toma de decisiones del mundo real en una amplia variedad de campos, como encontrar la forma menos desperdiciadora de cortar materias primas, selección de inversiones y carteras, selección de activos para la titulización respaldada por activos , y generando claves para el Merkle-Hellman y otros criptosistemas de mochila.

2

UNIVERSIDAD NACIONAL DE SAN AGUSTÍN DE AREQUIPA

Una de las primeras aplicaciones de los algoritmos de mochila fue en la construcción y calificación de las pruebas en las que los examinados tienen la opción de elegir las preguntas que responden. Para ejemplos pequeños, es un proceso bastante simple proporcionar a los examinados una opción de este tipo. Por ejemplo, si un examen contiene 12 preguntas, cada una con un valor de 10 puntos, la persona que realiza la prueba solo necesita responder 10 preguntas para lograr la puntuación máxima posible de 100 puntos. Sin embargo, en las pruebas con una distribución heterogénea de valores de puntos, es más difícil proporcionar opciones. Feuerman y Weiss propusieron un sistema en el que los estudiantes reciben una prueba heterogénea con un total de 125 puntos posibles. Se les pide a los estudiantes que respondan todas las preguntas lo mejor que puedan. De los posibles subconjuntos de problemas cuyos valores de puntos totales suman 100, un algoritmo de mochila determinaría qué subconjunto otorga a cada estudiante la puntuación más alta posible. 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.

2. Definición del problema de la mochila 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

3

UNIVERSIDAD NACIONAL DE SAN AGUSTÍN DE AREQUIPA

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. 

El problema más común que se resuelve es el problema de la mochila 0-1, que restringe el número 𝜒𝒾 de copias de cada tipo de artículo a cero o uno. Dado un conjunto de n elementos numerados de 1 a n, cada uno con un peso o 𝜔𝒾 y un valor o 𝜐𝒾 , junto con un peso máximo capacidad W, 𝑛

𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 ∑ 𝜐𝒾 𝜒𝒾 𝑖=1 𝑛

𝑡𝑎𝑙 𝑞𝑢𝑒 ∑ 𝜔𝒾 𝜒𝒾 ≤ 𝑊 𝑦 𝜒𝒾 ∈ {0,1} 𝑖=1

Aquí 𝜒𝒾 representa la cantidad de instancias del artículo i que se incluirán en la mochila. De manera informal, el problema es maximizar la suma de los valores de los artículos en la mochila para que la suma de los pesos sea menor o igual a la capacidad de la mochila. 

El problema de mochila acotado (BKP) elimina la restricción de que solo hay uno de cada artículo, pero restringe el número 𝜒𝒾 de copias de cada tipo de artículo a un valor entero no negativo máximo 𝑐 : 𝑛

𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 ∑ 𝜐𝒾 𝜒𝒾 𝑖=1 𝑛

𝑡𝑎𝑙 𝑞𝑢𝑒 ∑ 𝜔𝒾 𝜒𝒾 ≤ 𝑊 𝑦 0 ≤ 𝜒𝒾 ≤ 𝑐 𝑖=1

4

UNIVERSIDAD NACIONAL DE SAN AGUSTÍN DE AREQUIPA



El problema de la mochila ilimitada (UKP) no establece un límite superior en el número de copias de cada tipo de artículo y se puede formular como se indicó anteriormente, excepto que la única restricción en 𝜒𝒾 es que es un entero no negativo 𝑛

𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 ∑ 𝜐𝒾 𝜒𝒾 𝑖=1

𝑛

𝑡𝑎𝑙 𝑞𝑢𝑒 ∑ 𝜔𝒾 𝜒𝒾 ≤ 𝑊 𝑦 𝜒𝒾 ≥ 0 𝑖=1

3. Casos en los que se presenta a) Problema de la mochila simple o mochila supercreciente Serie de condiciones que hacen que pueda ser planteado como un problema de la suma de subconjuntos(problema NP-completo) que, si tiene solución, esta será única. Dados: Un conjunto de m números enteros positivos S= {S1, S2,..., Sm}, ordenados de menor a mayor, donde la secuencia de los elementos cumplen la condición de que el elemento i-ésimo es mayor que la suma de los anteriores elementos (es una secuencia supercreciente). Matemáticamente. Un valor W que es el resultado de alguna de las posibles sumas de esos elementos, Se debe encontrar S'= {Sa, Sb,..., Sj}, siendo S' el subconjunto de S cuya suma sea igual al valor W. Observar que en un problema de la mochila 0.1, si para cada tipo de ítem el beneficio y los pesos son idénticos (v1 = w1), entonces el problema quedaria formulado de la siguiente forma. 𝑛

𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 ∑

𝑤𝑖𝑥𝑖 𝑖=1

5

UNIVERSIDAD NACIONAL DE SAN AGUSTÍN DE AREQUIPA

𝑛

𝑡𝑎𝑙 𝑞𝑢𝑒 ∑

𝑤𝑖𝑥𝑖 ≤ 𝑊 𝑖=1

𝑌 𝑥𝑖 ∈ {0,1} 𝑖−1

𝑠𝑒 𝑣𝑒𝑟𝑖𝑓𝑖𝑐𝑎 𝑤𝑖 > ∑

𝑤𝑗 𝑗=1

Variables de decisión 0 = si el valor del subconjunto es mayor que W, ese valor no estará en el subconjunto y por tanto en la posición correspondiente del vector solución habrá un 0 1 = se recorre el valor porque es menor que W

b) Problema de la mochila de múltiple elección Si en un problema de la mochila 0-1 los ítems están subdivididas en k clases denotadas por Ni y exactamente un ítem tienen que ser tomando de cada clase. 𝑘

𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 ∑

∑ 𝑖=1

𝑣𝑖𝑗𝑥𝑖𝑗 𝑗 ∈𝑁𝑖

𝑘

𝑡𝑎𝑙 𝑞𝑢𝑒 ∑

∑ 𝑖=1

∑

𝑤𝑖𝑗𝑥𝑖𝑗 ≤ 𝑊 𝑗 ∈𝑁𝑖

𝑥𝑖𝑗 = 1 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 1 ≤ 𝑖 ≤ 𝑘 𝑗 ∈𝑁𝑖

𝑦 𝑥𝑖𝑗 ∈ {0, 1} 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 1 ≤ 𝑖 ≤ 𝑘 𝑦 𝑗 ∈ 𝑁𝑖

4. Métodos de resolución 4.1. Formulación Lineal

Para poder resolver el problema con este método definiremos: -

C como la capacidad de la mochila

-

Pi como el beneficio unitario obtenido por ingresar al producto i en la mochila

-

wi como el peso del producto i

-

n como la cantidad de productos

-

c, pi y wi como los valores enteros y positivos

6

UNIVERSIDAD NACIONAL DE SAN AGUSTÍN DE AREQUIPA

𝑛

∑

𝑤𝑖𝑥𝑖 ≤ 𝑐

(𝑐𝑎𝑝𝑎𝑐𝑖𝑑𝑎𝑑)

𝑖=1 𝑛

max → 𝑧 = ∑

𝑝𝑖𝑥𝑖

(𝑓𝑢𝑛𝑐𝑖𝑜𝑛𝑎𝑙)

𝑖=1

4.2. Aproximaciones

4.2.1. Aproximaciones a través de coeficiente de rendimiento Una solución intuitiva pero que puede no ser óptima podría elaborarse ordenando los productos en forma descendente según la proporción.

𝑟𝑖 =

𝑝𝑖 𝑤𝑖

Y metiendo elementos de esta lista ordenada hasta que no se pueda ingresar el siguiente elemento a la mochila. Desde este punto en adelante, siempre se asumirá que los elementos del conjunto se encuentren ordenados según esta proporción.

4.2.2. Evaluación de la heurística Pese a que la heurística propuesta en el punto anterior tiende a funcionar adecuadamente en la mayoría de los casos, existen casos patológicos que pueden tener como consecuencia un rendimiento desastroso, definiendo a: -

Z como el valor de la solución óptima.

-

Z’ como el valor de la solución obtenido aplicando la heurística.

-

El índice de performance de la heurística, si es óptimo sería 1.

5. Planteamiento del problema

7

UNIVERSIDAD NACIONAL DE SAN AGUSTÍN DE AREQUIPA

Considere un excursionista que debe preparar su mochila, además considere que el excursionista tiene una serie de objetos de utilidad, pero solo puede llevar una cantidad limitada de objetos. El problema consiste en elegir un subconjunto de objetos, de tal forma que se maximice la utilidad que el excursionista obtiene, pero sin rebasar la capacidad de su mochila. El problema consta de los siguientes elementos: Datos: 𝑛: 𝑛ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑜𝑏𝑗𝑒𝑡𝑜𝑠 𝑎𝑗 : 𝑝𝑒𝑠𝑜 𝑑𝑒 𝑐𝑎𝑑𝑎 𝑜𝑏𝑗𝑒𝑡𝑜 𝑗 𝑐𝑗 : 𝑢𝑡𝑖𝑙𝑖𝑑𝑎𝑑 𝑑𝑒 𝑐𝑎𝑑𝑎 𝑜𝑏𝑗𝑒𝑡𝑜 𝑗 𝑏: 𝑐𝑎𝑝𝑎𝑐𝑖𝑑𝑎𝑑 𝑚á𝑥𝑖𝑚𝑎 𝑑𝑒 𝑙𝑎 𝑚𝑜𝑐ℎ𝑖𝑙𝑎 Variables: 𝑥𝑗 {

1 𝑠𝑖 𝑒𝑙 𝑜𝑏𝑗𝑒𝑡𝑜 𝑗 𝑠𝑒 𝑚𝑒𝑡𝑒 𝑒𝑛 𝑙𝑎 𝑚𝑜𝑐ℎ𝑖𝑙𝑎 0 𝑛𝑜 𝑠𝑒 𝑚𝑒𝑡𝑒 𝑒𝑛 𝑙𝑎 𝑚𝑜𝑐ℎ𝑖𝑙𝑎

Restricciones: La capacidad máxima de la mochila no debe excederse: 𝑛

∑ 𝑎𝑗 𝑥𝑗 ≤ 𝑏 𝑗=1

Función a maximizar: El objeto de este problema es maximizar la utilidad, que se debe expresar como: 𝑛

𝑍 = ∑ 𝑐𝑗 𝑥𝑗 𝑗=1

Ejemplo: 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: Contenedor C1 Peso

C2

C3 C4

100 155 50

C5 C6 C7 C8

112 70

80

60

C9

C10

118 110 55

8

UNIVERSIDAD NACIONAL DE SAN AGUSTÍN DE AREQUIPA

El analista de la empresa del armador ha de determinar el envío (conjunto de contenedores) que maximiza la carga transportada. Este problema puede formularse como un problema tipo mochila. Las variables son: 𝑥𝑗 {

1 𝑠𝑖 𝑒𝑙 𝑐𝑜𝑛𝑡𝑒𝑛𝑒𝑑𝑜𝑟 𝑗 𝑠𝑒 𝑐𝑎𝑟𝑔𝑎 0 𝑠𝑖 𝑛𝑜 𝑠𝑒 𝑐𝑎𝑟𝑔𝑎

Solución: La función objetivo es maximizar la carga que transportará el carguero: 𝑍 = 100𝑥1 + 155𝑥2 + 50𝑥3 + 112𝑥4 + 70𝑥5 + 80𝑥6 + 60𝑥7 + 118𝑥8 + 110𝑥9 + 55𝑥10 Y la restricción es que el peso de la carga transportada no puede exceder la capacidad máxima del carguero: 100𝑥1 + 155𝑥2 + 50𝑥3 + 112𝑥4 + 70𝑥5 + 80𝑥6 + 60𝑥7 + 118𝑥8 + 110𝑥9 + 55𝑥10 ≤ 700 Téngase en cuenta que el peso de cada contenedor es igual a su utilidad, debido a que en este problema la utilidad es el peso. Haciendo uso de Open Solver.

La decisión óptima es transportar los contenedores: C1, C2, C3, C4, C8, C9, C10. El valor óptimo es 700, lo que indica que el carguero está completo.

9

UNIVERSIDAD NACIONAL DE SAN AGUSTÍN DE AREQUIPA

6. Aplicaciones a la sociedad El objetivo del problema de la mochila es encontrar un subconjunto de objetos con el cual se maximice el beneficio o utilidad que proporcionan los objetos mientras que satisface la restricción de no sobrepasar la capacidad (espacio o peso) de un contenedor o depósito (en este caso la mochila) donde serán colocados los objetos. Se puede emplear, como ejemplo, el uso de contenedores en las aduanas, donde se requiere enviar ítems de diferentes pesos, tamaños y valores de beneficio. Por otra parte, en la misma aduana, es necesario almacenar, de manera temporánea, los contenedores mismos, por lo que este problema puede ser resuelto con base en la solución propuesta para el problema de la mochila. Haciendo una ejemplificación con alguna situación también tenemos el caso del ladrón: Un ladrón acaba de entrar a una bóveda con una mochila de capacidad limitada, en este caso de C kilos; dentro de ella se encuentra con N objetos de V valores diferentes, algunos más valioso que otros, y un peso P. Lamentablemente no puede cargar todos los objetos así que debería de escoger aquella combinación de tal manera que la suma de sus valores sea el máximo y la suma de sus peso no rebase la capacidad de la mochila. En aspectos de criptografía, en el caso de descifrar contraseñas, este problema se puede ver como un número de contenedores que pueden tener n valores cada uno. En otro sentido, cuando es necesario traducir un texto encriptado, en el momento de identificar los espacios, cada palabra puede fungir como un contenedor de ni ítems (caracteres de la palabra), donde cada carácter i puede tener n posibles artículos. El problema de la mochila (Knapsack Problem), KP por sus siglas en inglés, es un problema de optimización combinatoria de formulación sencilla, aunque su resolución es compleja tiene una variedad de aplicaciones como la planificación de la producción,

10

UNIVERSIDAD NACIONAL DE SAN AGUSTÍN DE AREQUIPA

modelización estratificada, planificación de la capacidad de instalaciones, etc. Como parte de la aplicación del problema de la mochila en la vida real se utiliza para modelar diferentes situaciones: 

La selección de proyectos, donde cada proyecto se puede como un contenedor de diferentes ítems tales como: personas, recursos, etc.



En la solución de problemáticas donde es necesario detectar patrones de corte.



En situaciones donde se problemas de distribución de carga (física, eléctrica, etc.).



Cuando se requiere abastecer vehículos de transporte y entrega de productos de diferentes tamaños que deben ser colocados en múltiples compartimentos de igual o diferente tamaño,



Asignación de procesadores y datos en sistemas distribuidos.



En los sistemas de apoyo a las finanzas, al buscar el equilibrio entre el capital y el rendimiento financiero.



Al cargar un barco un avión, en donde se debe de llevar todo el equipaje sin ser sobrecargado para evitar problemas

Actualmente existe un gran interés en implementar nuevas técnicas de optimización como son las meta-heurísticas (Algoritmos genéricos que pueden ser implementados para resolver diferentes problemas de optimización a través de variaciones mínimas). Los Algoritmos de Optimización de Colonia de Hormigas son una meta-heurística bioinspirada basada en el comportamiento de las hormigas naturales, en la forma de como estas establecen el camino más corto entre el hormiguero y su fuente de alimentos a través de una sustancia denominada feromona. La construcción de la solución por parte de una hormiga es guiada por una información heurística que depende del problema y por los rastros de feromonas que se encuentran depositados en los caminos.

11

UNIVERSIDAD NACIONAL DE SAN AGUSTÍN DE AREQUIPA

Alaya, Solnon, y Ghédira en el 2004 implementaron un algoritmo de optimización con colonias de hormigas para resolver el problema de la mochila multidimensional el cual es el algoritmo más reciente.

7. Conclusiones En este documento se ha realizado un profundo análisis del “Problema de la Mochila”, analizando su historia, características y aplicaciones; con la finalidad de obtener una comprensión más amplia de los conceptos teóricos aprendidos en el salón de clases. La aplicación del problema de la mochila es complejo, y requiere de un análisis profundo y minucioso de todas las variables implicadas, para lo cual se requiere de personas experimentadas en el tema, además de recabar toda la información disponible. Como parte del desarrollo integral del curso, además de fomentar la investigación e innovación, se ha realizado el análisis de la aplicación del problema de la mochila para la empresa “Ele Operador Logístico E.I.R.L.”, donde se tuvo que elegir entre dos tipos de cargas, con diferentes atributos y utilidades. De este análisis se obtuvo que para la empresa resulta más factible para la empresa transportar los vegetales, debido a que nos orece u índice mucho mayor de utilidad. Durante el análisis del caso aplicativo, se tuvo varias limitaciones, con respecto a las dimensiones de los productos, además de que esto tuvo que adecuarse a las medidas del camión, sin exceder la carga máxima que éste debía transportar.

12

UNIVERSIDAD NACIONAL DE SAN AGUSTÍN DE AREQUIPA

Bibliografía CryptoWiki. (2004). Crypto Wiki. Obtenido de Crypto Wiki: https://cryptography.fandom.com/wiki/Knapsack_problem#cite_note-16 Karp, R. M. (1972). Reducibility Among Combinatorial Problems. Nueva York. Mathews, G. (1897). On the partition of numbers. Proceedings of the London Mathematical Society. Skiena, S. S. (1999). On the partition of numbers.

13