El problema de la bolsa de papel
José Padrón C.I 28.462.837 P. no númerica 2 SAIA 2020-1 IUPSM Barcelona
Algoritmo
En matemáticas, lógica, ciencias de la computación y disciplinas relacionadas, un algoritmo (del latín, dixit algorithmus y este del griego arithmos, que significa «número», quizá también con influencia del nombre del matemático persa Al-Juarismi) es un conjunto de instrucciones o reglas definidas y no-ambiguas, ordenadas y finitas que permite, típicamente, solucionar un problema, realizar un cómputo, procesar datos y llevar a cabo otras tareas o actividades.2 Dados un estado inicial y una entrada, siguiendo los pasos sucesivos se llega a un estado final y se obtiene una solución. Los algoritmos son el objeto de estudio de la algoritmia.
El problema de la bolsa de papel (problema de la mochila)
El problema de la bolsa de papel, mayormente conocido como: problema de la mochila (Knaspack problem) es un problema clásico en los problemas denominados COP (por sus siglas en inglés Combinatorial Optimization Problem – Problemas de Optimización Combinatoria) de Inteligencia Artificial. Este problema es considerado NP (Non Probabilistic Problem) ya que existe una combinación exponencial de instancias que, en su totalidad, no pueden ser resueltas. Existen variantes relacionadas con este problema: problema con cantidad de productos limitada, problema con cantidad de productos ilimitada, elección múltiple, elección de un producto de diferentes categorías, como un problema relacionado con el peso de los productos, como un problema relacionado con el monto económico, entre otros. El presente trabajo tiene como objetivo dar un panorama general de este problema y su aplicación en la vida real.
En algoritmia, el problema de la bolsa de papel, mayormente conocido como: 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.
Se define como, Un conjunto de n artículos donde cada artículo es identificado por nx, con un valor entero px, y un peso wx. El problema consiste en elegir un subconjunto de n artículos maximizando el beneficio obtenido considerando el peso total de los artículos seleccionados, sin exceder la capacidad c de la mochila.
Dorta et al., definen el Problema de la mochila de la siguiente manera: Se dispone de una mochila de capacidad C y de un conjunto de N objetos, donde los objetos son indivisibles. Describen a un objeto k que tiene un beneficio bk y un peso pk, para k = 1,2,…, N. Para los autores, el problema consiste en averiguar qué objetos se pueden insertar en la mochila sin exceder la capacidad total de la misma, obteniendo el máximo beneficio.
Velasco se basa en la definición formal del problema: “Se tiene una determinada instancia de KP con un conjunto de objetos N, que consiste de n objetos j con ganancia pj y peso wj, y una capacidad c. (Usualmente, los valores toman números enteros positivos). El objetivo es seleccionar un subconjunto de N tal que la ganancia total de esos objetos seleccionados es maximizado y el total de los pesos no excede a c”.
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.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.
Ejemplo
Un muelle 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 muelle 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. |
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.
La solución sería llevar 3 del C, 1 del B y 2 del A
